【ITニュース解説】Semi-Linearizability: Cut Coordination, Keep Invariants

地理的に離れた場所にサーバーが分散しているシステム、いわゆる地理分散システムでは、データの整合性を保ちながら高い性能を達成することが大きな課題となっている。これまでのアプローチでは、全ての操作に対して最も厳格な整合性であるリニアライザビリティを求めると、世界中のサーバー間で綿密な調整が必要となり、処理に時間がかかってしまう。一方、調整を減らして速さを優先すると、データの一貫性が失われ、矛盾が生じるリスクが高まるという二者択一の状況が一般的だった。Semi-linearizability（セミリニアライザビリティ）という新しい考え方は、この問題を解決するための第三の道を提供する。これは、システム内の操作が互いにどのような順序関係を必要とするかを見極め、本当に厳密なグローバルな順序付けが必要な操作にだけ高度な調整を行う一方で、多くの一般的な操作は個々のサーバーで高速に処理し、後で非同期に伝播させることで、性能と整合性の両立を目指すものである。

Semi-linearizabilityでは、全ての操作に一律の整合性を適用するのではなく、操作の種類に基づいて必要な整合性のレベルを区別する。具体的には、操作を三つのカテゴリに分類する。一つ目は「強操作（Strong operations）」で、これはシステム全体で厳密な順序付けと確定的な実行を必要とする操作である。二つ目は「弱操作（Weak operations）」で、これは各サーバーで即座に処理され、その結果は後から非同期に他のサーバーへ伝えられる操作だ。ただし、これらの操作の因果関係（ある操作が別の操作の結果に依存する関係）は維持される必要がある。三つ目は「半操作（Semi operations）」または「中間操作」と呼ばれ、特定の方向において追加の順序制約が必要となる、強操作と弱操作の中間的な性質を持つ操作である。このモデルの核心的な洞察は、多くのアプリケーションにおいて操作間の依存関係が「非対称」であるという点だ。例えば、オンラインオークションでは、オークションを終了する操作は、それまでの全ての有効な入札を考慮して勝者を決定する必要がある。しかし、個々の入札操作自体は、他の全ての入札と厳密にグローバルな順序で処理される必要はない。Semi-linearizabilityはこのような非対称性を明確にし、それぞれの操作に最適な調整方法を割り当てることを可能にする。

DeMon（デーモン）というプロトタイプシステムは、このSemi-linearizabilityの概念を具体的な技術で実現している。DeMonは主に三つの要素を組み合わせて動作する。一つ目は「因果ブロードキャスト（Causal broadcast）」で、これは弱操作を各サーバーで高速に実行し、その結果を他のサーバーに非同期に、かつ因果関係を保ちながら伝播させる仕組みだ。これにより、弱操作は即座にクライアントに応答を返し、その後の処理はバックグラウンドで行われるため、非常に低いレイテンシ（処理遅延）を実現できる。二つ目は「ターゲットコンセンサス（Targeted consensus）」で、これは強操作に対してのみ適用される合意形成プロトコルである。Paxos（パクソス）などのコンセンサスアルゴリズムのように、少数の強操作だけを対象として、システム全体でそれらの順序を厳密に決定する。これにより、全ての操作をグローバルなログに記録するような重い処理を回避できる。三つ目は「ウォーターマーク（Watermarks）」と呼ばれるもので、これはベクタークロック（分散システムにおける時間管理の仕組みの一つ）のような情報を使って、特定のサーバーがこれまでにどの弱操作を認識しているかを要約したものだ。強操作が提案される際、このウォーターマークが付加され、コンセンサスプロセスはウォーターマークの情報に基づいて、どの弱操作までを考慮して強操作を確定させるべきかを判断する。

具体的な処理の流れは以下のようになる。まず、あるサーバーが弱操作を受け取ると、そのサーバーはすぐにその操作をローカルに適用し、クライアントに応答を返す。その後、その弱操作は因果ブロードキャストを通じて他のサーバーに非同期に伝播される。一方、強操作が提案される際には、提案元のサーバーが現在のウォーターマークを付加し、ターゲットコンセンサスにかける。コンセンサスによって強操作が確定し、各サーバーに適用される際、サーバーはその強操作に付加されたウォーターマークを確認する。そして、ウォーターマークが示す時点までに処理されるべき弱操作が、強操作の確定より前に正しく適用されていることを確認する。もし、まだ適用されていない弱操作や、強操作の確定と矛盾する形でローカルに適用されていた弱操作があれば、それらを調整するために、必要に応じてロールバック（元に戻す）したり、リプレイ（再適用）したりといった処理が行われる。この仕組みにより、頻繁に発生する弱操作は非常に高速に処理され、DeMonの報告によれば、一般的な操作で最大四桁も処理速度が向上する事例がある一方で、強操作は正確性とリニアライザビリティを保証できる。

オンラインオークションを例にとると、この非対称な依存関係とSemi-linearizabilityの有効性がよく理解できる。オークションには主に二種類の操作があるだろう。一つは「入札（Bid）」操作で、これはユーザーが高い頻度で行う操作だ。入札は個々のサーバーでローカルに処理され、因果ブロードキャストによって他のサーバーに伝えられる。この操作に必要なのは、最終的に全てのサーバーでデータが一致することと、入札が因果関係に基づいて伝播されることである。もう一つは「オークション終了（CloseAuction）」操作で、これは比較的まれに発生するが、勝者を決定するという決定的な操作だ。オークション終了操作は、その時点までの全ての関連する入札を正確に把握し、その順序を決定して勝者を確定する必要があるため、厳密な整合性が求められる。

Semi-linearizabilityを適用した場合の動作はこうなる。まず「入札」操作は弱操作としてマークされる。各サーバーは入札を受け取ると、すぐにローカルでその入札をデータベースに反映し、クライアントに応答を返す。その後、この入札情報は因果ブロードキャストによって他のサーバーに非同期に伝播される。次に、「オークション終了」操作は強操作としてマークされる。この操作を提案するサーバーは、その時点までに把握している弱操作（つまり入札）の状況を示すウォーターマークを付加し、コンセンサスプロセスにオークション終了操作を提案する。コンセンサスによってオークション終了操作が確定すると、そのウォーターマークを基準にして、最終的な勝者が決定される。例えば、あるサーバーで入札が行われたが、それがまだ他のサーバーに伝播しておらず、その状態でオークション終了操作が確定した場合、確定に使われたウォーターマークにその入札が含まれていなければ、その入札は勝者決定の対象外となる。後からその入札情報が伝播してきても、すでにオークションは終了しているため、その入札は無視されるか、あるいは終了後の状態として処理される。このアプローチにより、頻繁に行われる入札操作のレイテンシは大幅に削減され、同時に、オークション終了という重要な操作の正確性は保たれるのである。

実際にSemi-linearizabilityをシステムに導入するために必要な要素はいくつかある。第一に「因果ブロードキャスト」で、これは弱操作を因果関係を保ちながら全てのサーバーに非同期に届けることで、同期的なグローバル調整なしにデータの一貫性を実現する。第二に「ウォーターマーク（ベクタークロック）」で、各サーバーがどの弱操作までを観測したかを要約する情報として機能し、強操作がグローバルな順序を確立する際の基準となる。第三に「ターゲットコンセンサス」で、これは本当にグローバルな順序付けが必要な強操作に対してのみコンセンサスアルゴリズムを実行する。全ての書き込みをグローバルなログに記録する必要はなく、必要な操作だけに重い調整を適用する。第四に「分断時のポリシー（Fail-open vs fail-closed policy）」を決定する必要がある。これは、ネットワーク障害などでシステムが分断された場合に、弱操作の実行を許可するか（フェイルオープン）、あるいは安全が保証されるまでブロックするか（フェイルクローズ）という選択である。強操作に関しては、その正確性を保証するために常にフェイルクローズであるべきだ。

システムをSemi-linearizabilityモデルに移行するための実践的なチェックリストも存在する。まず、アプリケーションの各API（操作）を洗い出し、それぞれの操作がどのような一貫性（インバリアント）を維持する必要があるかを特定する。次に、どの操作がどの他の操作の結果を考慮する必要があるかを明確にし、非対称な依存関係を見つけ出す。その後、洗い出した各操作を「弱」「半」「強」のいずれかに分類する。この際、可能な限り多くの操作を弱操作としてマークし、強操作は少数にとどめることが理想である。分類が完了したら、弱操作に対してはローカルでの高速実行と非同期での因果ブロードキャストを実装する。強操作に対してはターゲットコンセンサスを導入し、提案時にはウォーターマークを付加して、弱操作の現在の状態を伝えるようにする。また、強操作が確定した際に、ローカルに適用済みの弱操作との矛盾をどのように解決するか（ロールバックしてリプレイするか、あるいは補償ロジックを適用するか）という調整ロジックを設計する必要がある。分断時のポリシーを選択し、最後にベンチマークテストを用いて、実際のワークロードでの性能と正確性を検証することが重要となる。

もちろん、このアプローチにはトレードオフや注意点も存在する。弱操作のパスで低いレイテンシを実現する代償として、システム全体での即時的なグローバルなデータ可視性は失われる。つまり、一部のクライアントは、弱操作が全てのサーバーに伝播して最終的に一致するまでの間、異なる一時的なデータ状態を見る可能性がある。また、強操作が確定し、ウォーターマークが一部の弱操作を排除するような状況では、すでにローカルで適用されていた弱操作をロールバックしたり、正しい順序でリプレイしたりする複雑な処理が必要になる。そして何よりも重要なのは、操作の分類を正しく行うことである。もし、本来強操作であるべきものを誤って弱操作とマークしてしまった場合、システムの一貫性が破綻し、データが不正確になるリスクがある。

Semi-linearizabilityは、一般的な操作が単純な更新であり、少数の操作のみがグローバルな調整を必要とするような地理分散アプリケーション、例えばオークション、リーダー選挙、決済システムの最終確定ステップなどで特に有効である。また、頻繁に実行される操作の処理遅延がシステムのボトルネックとなっており、それらの操作に関しては最終的なデータ一致を受け入れられる場合に適している。

結論として、Semi-linearizabilityはデータ整合性を「リニアライザビリティか、あるいは不整合か」という二択ではなく、「操作ごとの設計判断」へと転換させる考え方である。因果ブロードキャスト、ウォーターマーク、ターゲットコンセンサスといった技術を組み合わせることで、頻繁に利用される経路（ホットパス）での処理をローカルで高速に保ちながら、稀にしか発生しないが重要な操作に対しては厳密な調整を適用することが可能となる。DeMonの実験結果が示すように、頻繁な入札操作を弱操作とすることでレイテンシを劇的に削減しつつ、オークション終了操作はコンセンサスによって正確性を維持できる。地理分散サービスを構築する際には、操作を分類し、その非対称な依存関係をうまく活用することで、必要以上に高度な調整を行っている部分を削減できる可能性を秘めている。