QCon New York 2017: システム内のイベントの順序付け

Samsaraのソフトウェア技術者であるKavya Joshi氏が、QCon New York 2017で、happens-before原則について詳細に解説した。その中で氏は、分散型キーバリューストアであるRiakがノード間の因果関係の確立にベクトルクロックを使用している方法を解説するとともに、Goの並列処理プリミティブに注目し、それがhappen-before制約を自然に表現できる点について説明した。

現代的なソフトウェアシステムでは、スケール性を確保するために、演算処理をさまざまなノードに分割する方法が一般的である。これが結果として、データ競合(data race)に結び付く可能性がある、と氏は説明する。

“データ競合は一般的に、２つのスレッドが同じ共有メモリに並列的にアクセスし、少なくとも一方のアクセスが書き込みであった場合に発生します。”

データ競合は非決定的か、あるいは未定義の結果を生じる傾向があるため、特にデバッグが難しくなる可能性があることを説明した上で、氏は、happens-beforeを扱うためにはそれを理解することが重要だ、と述べた。

happens-beforeは、本質的には、並列システムにおいてイベントの順序付けを行なう手段である。例えば次の場合には、X < Y であると言える。

1. XとYが同じアクタ上で発生した。これは単一ノードあるいは単一スレッド内では、順序がシーケンシャルであると保証されているためだ。
2. 両者が同期ペアである。例えば、あるノードからフェッチされて他のノードを更新した場合、あるいはミューテックスでロックされた場合がこれに当たる。
3. 推移性から暗示される、例えば X < Y < Z のような中間イベントは、順序付けを証明することが可能である。

これらの条件がいずれも満たされない場合、イベントは同時であり、何らかの競合解決策が必要であることを意味する。このためにJoshi氏は、3つの戦略を概説している。

1. 最後の書き込み(最も高いタイムスタンプを持つイベント)を優先する。この方法は、キャッシュのような不変データには適切だが、それ以外ではデータを失う可能性がある。
2. データを自動的に統合する。
3. アプリケーションに競合を返して、処理を任せる。

結果整合型の分散キーバリューストアであるRiakに関して、Joshi氏は、ベクトルクロック(vector clock)を使用して先に起きたことを立証する方法を説明した。本質的にこれはノード単位に格納された論理クロックであり、ペアワイズ最大(pair-wise max)を通じて比較することによって、イベントが同時かどうかを判断することができる。クロックの比較を可能にするために、Riakのクライアントは、因果コンテキスト(causal context)オブジェクトを通じてそれらを伝搬する。

Joshi氏はGo言語の並行性についても言及し、おもにチャネルについて、goroutine間でのスレッドセーフなデータ共有手段としてミューテックスとの比較を行なった。チャネルを使用することによってコードが簡略化されるとともに、処理の論証も容易になる。特に氏が強調したのは、wait-until-emptyセマンティクスによりwait-and-norifyなどのパターンが不要になる点で、“チャネルはユーザに対して、happens-before制約を可能にすると同時に、それを強制するのです”、と説明している。

結論として氏は、RiakなどのキーバリューストアとGoなどの言語は異なるものではあるが、データ競合および競合解決といった並列性の解決において採用しているアプローチには類似性がある、という点を指摘した。さらに氏は、happens-beforeは1978年に確立した古いアイデアだが、今日のコンカレントシステムにおいても適用可能な、重要な原則であることも指摘している。