Erlang で高効率なカウントを実現する：カウンターとアトミック変数を活用した手法

ElixirConf EU で、Elixir の高階並行性パターンに関する研修を無事に終えて参りました。エラングのプロセスモデルは私にとって非常に大好きですが、過去数年間に OTP チームが本プロセスモデルから「脱却」することを主眼とした素晴らしい機能もまた、大変気に入っております。多くのプログラミング言語は、可変で高速なデータ構造を起点とし、そこからスレッド隔離や並行機能などを構築してきます。しかし、エラングは逆向きのアプローチを取っています。すなわち、まず並行性の基本要素、不変のデータ、プロセス単位ごとのメモリといった基盤から始め、次にそれらの領域を安全に（！）変更できるような「脱出用出口」を導入するというわけです。

ETS は、比較的変更可能で共有されたメモリ空間が必要となる際の誰もが知っている、かつまず手にする標準的な機能です。しかし、最近の OTP リリースでは、ツールボックスへいくつか素晴らしい追加機能が加わりました。本稿では、主に「物の数を数える（counting）」ことに特化した

:atomics

および

:counters

の二つに焦点を当てて解説します。

Atomics（アトミックス）

アトミックス配列とは、ヒープの外部にある共有で可変な N × 64 ビット整数（有符号または無符号）のブロックのことです。「やや口ごもるような言い回し」ですが、以下のように分解して考えられるでしょう：

• Off-heap（ヒープ外）：プロセスのヒープ内には存在せず、BEAM のどこか魔法のような場所にあります。
• Shared（共有）：特定のどのプロセスも所有しておらず、それを BEAM が管理しています。
• Mutable（可変）：この小さなデータ構造を更新した際、実際にはメモリ内のバイトデータを直接変更します。これに対して、エラング/Elixir のデータ構造は不変であるため、更新時にはコピーが行われます。

「配列（array）」という名称は、

:atomics

データ構造を作成するたびに N 個の整数からなる配列が生成されることを意味します。

ref = :atomics.new(n, [])
:atomics.add(ref, 1, 23)

# 異なるプロセスでも実行可能... それとも共有されているからです。
Task.async(fn -> :atomics.add(ref, 1, 19) end)
|> Task.await()

:atomics.get(ref, 1)
#=> 42

注：スクリプトの再読出しやコンテキストによる表現です。元のエラングコードを踏襲しつつ、日本語で自然に解釈しています。

より具体的な例としては、以下のようになります。

ref = :atomics.new(n, [])

# 初期値の設定（ここでは単なる参照取得や別のプロセスからの操作を示唆）
:atomics.add(ref, 1, 23)

%% 異なるプロセスで追加を行う... それは共有されているためです。
{_, Ref} = spawn_monitor(fun() -> atomics:add(Ref, 1, 19) end),
receive
  {'DOWN', Ref, process, _Pid, _Reason} ->
    atomics:get(Ref, 1)
end
%=> 42

エラングは、その背後でどのようにデータが構成されているか（下層構造）を隠蔽しており、ここでは単に参照（ref）を返すのみです。配列自体は非常に低レベルなデータ構造であり、例えばオーバーフローチェックはありません：無符号整数を使用して $2^{64} + 1$ のような値を設定しようとした場合、単に 1 に巻き戻されます（wrap around）。このデータには特定のどのプロセスも所有しておらず、参照されているアトミックス配列への最後の参照が失われるとガベージコレクションの対象となります。

:atomics

が提供する恩恵は、これらの整数に対する超高速な原子操作です。これらは CPU 命令にほぼ直接マッピングされるため、「高速」という言葉は実際の意味での速度を指します。

数字の増減（adding/getting）自体はそれほど面白くないかもしれませんが、逆に面白いのは

add_get/3

のような演算です。これは、指定された配列インデックスの値に原子的に加算を行い、加算後の値を取得する機能を備えています。

atomics:add_get(Ref, 1, 10)
%=> 52

「原子的操作（Atomically）」とは、数値を増やすとそれと同時にその値を読み取るまでの間に何らかの操作が発生しないことを意味します。したがって、他のプロセスからその間に変更を加えられ、呼び出し元が値を読み返す前にレース条件（race condition）を引き起こすことはあり得ません。

また行える原子操作の一つに、指定されたインデックスの値を交換し、元の値を取得するものがあります。

atomics:exchange(Ref, 1, 0)
%=> 52
atomics:get(Ref, 1)
%=> 0

最後に、並行環境での同期によく使用される、よく知られた演算の一つです：Compare-and-swap（CAS）。有符号整数の現在の値を「期待する値」として提供し、「望む値」を提供し、もし現在の整数が期待する値と等しい場合のみ、その望む値に原子的に設定するという仕組みです。

atomics:compare_exchange(Ref, 1, 10, 42)
# => 0 (旧値)
atomics:compare_exchange(Ref, 1, 0, 42)
# => :ok
atomics:get(Ref, 1)
# => 42

:atomics

アレイは、同じアレイ内の異なるセル間で、操作がシーケンシャルに一貫している（sequentially-consistent）という順序を保証します。例えば、ライタープロセスが以下を実行したとします。

atomics:put(Ref, 1, 42),
atomics:put(Ref, 2, 19)

その場合、リーダープロセスは、最初のインデックスの値を見ることはあっても、それと同時に第二インデックスの値だけが見えるということは決して起こりません。これは Visibility（可視性）の問題であり、操作が見えたら、それ以前に行われたすべての操作も保証されて見えるからです。BEAM の世界であれば当然の前提かもしれませんが、そのような性質こそがこの単なる整数のコレクションを、マルチスレッドおよび並行処理のための強力な同期プリミティブへと変えるのです。

Counters（カウンター）

:atomics

と非常に近縁のもので、よりシンプルな API および異なるメモリモデルを持っています。

:counters

もまた、別個のメモリ空間にある 64 ビット整数からなるアレイですが、ここでは整数は有符号のみであり、原子操作プリミティブ（exchange や CAS など）はありません。

ref = :counters.new(n, [:write_concurrency])

:counters.add(ref, 1, 23)
:counters.add(ref, 1, 19)

:counters.get(ref, 1)
#=> 42

:atomics.add_get/3

で得られるような「書き込んだ直後に読む」という原子的な方法は、ここでは存在しません。

ここで本番に面白い部分と、

:atomics

との主な違いにあるのが、背後にあるデータ構造です。ここでは、配列は各スケジューラ（scheduler）ごとの 1 つの整数から構成されています。つまり、単要素カウンターのアレイであっても、私のマシンでは実際には 14 個の整数になります（なぜなら、以下の通り 14 のスケジューラが動作しているからです）。

System.schedulers_online()
#=> 14
erlang:system_info(schedulers_online).
%=> 14

このアーキテクチャにより、書き込みは極めて高速になります。なぜなら、同じコアに対して競合が生じないからです。各スケジューラは独自の整数アレイを持ち、書き込みはローカルに行われるため、その操作が行われたスケジューラの整数だけが変わり、他には影響しません。

一方、コストがかかるのは読み出し側です：

counters.get/2

は、実質的に各スケジューラの整数を合計して総値を取得します。

:counters.put/3

を用いてカウンターを特定する値に設定する場合も、より高価な操作であり、これは各スケジューラの整数を 0 にリセットし、そのうちのどれか 1 つだけに加算を行うことにより実現されます。

このデータ構造を用いたカウンターでは、読み出しがすべての書き込みを順序立てて見ることは保証されていません。並行して読むプロセスは、カウンターの一貫したスナップショットを見ることができません。書き込み A が書き込み B よりも前に発生する場合でも、戻り値の合計には両方、A のみ、B のみが反映される可能性があります。これは、読み込みが各スケジューラのセルをスキャンする時点でどのセルにデータが入ったか（landed）によるからです。書き込み操作は失われることはなく、いずれも必ず見ることはできますが、並行しているリーダーには将来的に一貫性がある結果しか期待できません。

ベンチマーク

それぞれの戦略の性能感を把握するために、ET を基準にしていくつかのベンチマークを実行しました。ET には

ets:update_counter/4

という機能があり、これを用いて

:counters

や

:atomics

のような用途にも部分的に利用できます。

今回の特定のベンチマークでは、ループ内でカウンターを 1 インクリメントさせるとともに、並行する書き込み数を可変にして、スケールアップに伴う変化を確認しました。

• 値が高いほど良い（＝高速）。
• 両軸とも対数スケール。

スペック

ベンチマーク実行に使用したマシンのスペックです：

• オペレーティングシステム：macOS
• CPU: Apple M4 Pro
• 利用可能なコア数：14 コア
• 利用可能なメモリ：24 GB
• Elixir: 1.19.2
• Erlang: 28.1
• JIT の有効化：true

書き込みプロセスが 1 つの場合、すべての解決策は同様に動作します。コアレベル間やエラングプロセス間の競合はありません。

書き込みプロセスが増えるにつれ、状況はより興味深く変化してきます。ET の性能はマシンのコア数（今回は 14 コア）を超えると著しく低下します。

atomics

（および

[:atomics]

モードのカウンター）は ET よりも優れたパフォーマンスを発揮し、書き込みが増えるにつれて安定したスループットを維持しています。

:counters

は予期通り非常に高い性能を示します。書き込みを並行化させることで、書き込みプロセス同士が共有リソースを争うことがなくなるため、スループットは向上します。マシンのコア数に達する点までは、書き込みプロセスを増やすにつれてスループットが増加し、競合がないため並列化が有効です。その後、パフォーマンスは停滞しますが、重要なのは劣化するわけではないことです。

結論

BEAM上で

:atomics

と

:counters

という2つの興味深いデータ構造について考察しました。我々の業界の多くの物ごとと同様に、適切なツールを選ぶことが重要です。

• :atomics は、真に原子的なプリミティブ（CAS, exchange, atomic add-and-get など）が必要で、かつ整数のアレイを実際の同期プリミティブへと変化させるシーケンシャル一貫性の保証が必要な場合に適しています。実用例として、Broadway のレート制限機能は

  :atomics

  を基盤として実装されています。
• :counters は、書き込みが多く読み出しは稀な場面に最適です（ヒットカウンターやリクエストカウンターなど）。多くのプロセスから番号を増やす際、それらのプロセス同士が同じキャッシュラインを争わない状況であれば特に有効です。ETS もまだ重要な役割を果たしますが、この種の特定の課題に対しては、

  :atomics

  および

  :counters

  の二つのアプローチの方が、より良いパフォーマンスと厳密なセマンティクスを提供します。

私がこれらの機能すべてに惹かれるのは、その背後にある哲学です。エラングは、狭く範囲が限定されたプリミティブを設計し、必要に応じてプロセスモデルからの脱出用出口として機能させました。これらは、同様の仕事を行うあらゆる言語で見られるものの中でもほぼ最も高速です。

リソース

• Counters のドキュメント
• Atomics のドキュメント
• Kjell Winblad 著『Decentralized ETS Counters for Better Scalability』