データ指向アプリケーションデザイン | 第09章 一貫性と合意
発表者: イ・ホジュン、チョ・ソンジク
この章では、耐障害性を備えた分散システムを構築するために使われるアルゴリズムとプロトコルを紹介する。
一貫性保証
複製データベースでは、結果整合性のような弱い保証が一般的である。システムはいずれ収束するかもしれないが、それがいつかは分からない。より強い保証は理解しやすいが、性能や耐障害性を下げることがある。
線形化可能性
線形化可能性は、広く使われる最も強い一貫性モデルの1つである。複製されたシステムを、データのコピーが1つしかないかのように振る舞わせる。また、書き込みが完了した後の読み取りは、その値またはそれ以降の値を返すという最新性保証を提供する。
図9-1. 線形化可能でないシステムはユーザーを混乱させる。
読み取りが書き込みと重なっている場合、古い値を返すことも新しい値を返すこともある。しかし、いったんどこかの読み取りが新しい値を返したなら、その後のすべての読み取りは、同じクライアントか別のクライアントかに関係なく、新しい値を返さなければならない。
図9-3. 読み取りが新しい値を返した後は、後続の読み取りも新しい値を返さなければならない。
線形化可能性は、各操作が効果を持ったように見える一点を時間軸上に選ぶことで可視化できる。
図9-4. 各読み書きが効果を持つように見える時点を可視化する。
線形化可能性はロックやリーダー選出に役立つ。システムに誤って2つのリーダーが存在してはならない。ZooKeeperやetcdのようなコーディネーションサービスは、この目的のために線形化可能な操作を提供することが多い。
通信チャネル間のタイミング依存性を避ける場合にも役立つ。たとえば、Webサーバーがファイルストアに画像を書き込み、画像リサイズワーカーへメッセージを送る場合、ワーカーが古いファイルを見てはいけない。
線形化可能なシステムの実装
線形化可能性とは、データのコピーが1つだけあり、そのデータに対するすべての操作が原子的であるかのように振る舞うことである。本当にコピーが1つだけでは障害に耐えられないため、実際にはレプリケーションが必要になる。
レプリケーション方式によって性質は異なる。
- 単一リーダーレプリケーションは、読み取りがリーダーを通るか、最新であることが別の方法で保証されれば、線形化可能になり得る。
- 合意アルゴリズムは線形化可能性を提供できる。
- 複数リーダーレプリケーションは一般に線形化可能ではない。
- リーダーレスレプリケーションは、追加の調整を入れない限り通常は線形化可能ではない。
線形化可能性とクォーラム
w + r > nを満たすクォーラム読み書きは線形化可能に見えることがあるが、それでも競合は起こり得る。Dynamo風のリーダーレスシステムは、性能コストとより強い調整が必要になるため、一般に線形化可能性を提供しない。
図9-5. クォーラム読み書きでも競合条件が発生することがある。
線形化可能性のコスト
ネットワークが分断されると、システムは線形化可能性と可用性のどちらを取るか選ばなければならないことがある。
図9-7. ネットワーク分断では線形化可能性と可用性の選択が必要になる。
CAP定理は、ネットワーク分断が発生した場合、線形化可能性を要求するシステムは完全な可用性を保てないことを述べている。これはネットワークが常に分断されるという意味ではないが、通信が失敗したときにどう振る舞うかを設計で決める必要がある。
順序保証
順序、因果関係、一貫性は密接に関連する。あるイベントが別のイベントの原因であるなら、すべてのノードはその因果順序で観測すべきである。因果順序は全順序より弱いが、多くの混乱する履歴を排除できる。
シーケンス番号とタイムスタンプはイベントの順序付けに役立つ。分散システムでは物理時計が不完全なので、Lamportタイムスタンプのような論理時計が因果関係を表すためによく使われる。
全順序ブロードキャストは、すべてのメッセージをすべてのノードへ同じ順序で届ける。これは合意と同等の力を持ち、複製状態機械の基本的な構成要素である。
分散トランザクションと原子的コミット
原子的コミットは、トランザクションのすべての参加者がコミットするか、すべてがアボートするかを保証する。複数ノードまたは複数システムにまたがるトランザクションでは特に重要である。
2フェーズコミット（2PC）はコーディネータと参加者を使う。
- コーディネータがprepare要求を送る。各参加者はコミット可能か確認し、その判断を復旧可能にするための十分な情報を永続ストレージへ書く。
- すべての応答を受け取った後、コーディネータはコミットまたはアボートを決定し、その決定を記録する。
- コーディネータは最終決定をすべての参加者へ送り、参加者はそれに従ってコミットまたはアボートする。
prepareフェーズが完了する前に問題が起これば、コーディネータはアボートできる。参加者がprepare済みになった後に問題が起こると、参加者はコーディネータの最終決定を待たなければならない。この間、リソースがブロックされる。
3フェーズコミットはブロックを避けるために提案されたが、ネットワーク遅延とノード応答時間に上限があることを仮定する。この仮定は多くの分散システムでは現実的ではない。
実際の分散トランザクション
分散トランザクションの評価は分かれる。原子的コミットによって安全性を提供する一方で、運用上の問題や性能問題を引き起こすことがある。
大きく2種類がある。
- データベース内部の分散トランザクションは、同じ分散データベースのノード間で行われる。データベースは自分に合ったプロトコルを選び、最適化できる。
- 異種分散トランザクションは、異なるベンダーの2つのデータベースや、データベースとメッセージブローカーなど、異なるシステムにまたがる。共通プロトコルが必要である。
XAは、2フェーズコミットで異種分散トランザクションを実装するための標準である。トランザクションコーディネータとリソースマネージャの間のインターフェースを定義し、多くのリレーショナルデータベースとメッセージブローカーが対応している。
XAではコーディネータが失敗すると、トランザクションが疑わしい状態に残ることがある。参加者は最終決定が分かるまでロックを保持しなければならない。コーディネータのトランザクションログが失われたり、ソフトウェアバグがあったりすると、管理者が経験的決定を手動で下す必要がある。
分散トランザクションでは、コーディネータを高可用化しない限り単一障害点になる。コーディネータがアプリケーションサーバーに組み込まれると、トランザクションログをローカルに持つため、そのサーバーは状態を持つ。XAは参加システムの共通部分の機能しか提供できないという制約もある。
耐障害性を持つ合意
合意とは、複数のノードが1つの値に同意することである。合意アルゴリズムは次の性質を満たすべきである。
- 一様合意: 2つのノードが異なる値を決定しない。
- 完全性: どのノードも2回決定しない。
- 妥当性: ノードが値
vを決定したなら、vはどこかのノードによって提案された値である。 - 終了性: 故障していないノードは最終的に何らかの値を決定する。
最初の3つは安全性の性質である。終了性は活性の性質であり、障害とタイミングに関する仮定を必要とする。合意アルゴリズムは一般に、過半数のノードが利用可能であり、ビザンチン障害は扱わないと仮定する。
合意と全順序ブロードキャスト
全順序ブロードキャストは合意と同じ核心的性質を持つ。すべてのノードが同じメッセージを同じ順序で配信し、メッセージは重複せず、破損せず、最終的に配信される。
単一リーダーレプリケーションは、リーダーが書き込み順序を決めるため全順序ブロードキャストに似ている。しかしリーダーが失敗した場合、新しいリーダーについて合意しなければならない。それを安全に解くには、合意またはすでに合意を提供しているサービスが必要になる。
エポック番号とクォーラム
合意システムでは、リーダーの権限を区別するためにエポック番号、term、ballotなどを使う。リーダーは通常、クォーラムと通信することで、自分がまだ有効なリーダーであることを示さなければならない。これにより、古いリーダーが新しいリーダー選出後も書き込みを受け付け続けることを防ぐ。
2フェーズコミットとの違いは、耐障害性を持つ合意では過半数が利用可能であれば進行できるのに対し、2PCはコーディネータが悪いタイミングで失敗するとブロックする点である。
合意の制約
合意はクォーラムへの同期レプリケーションを必要とするため、レイテンシが増える。過半数が利用可能でなければならないので、多くのノードを失うとシステムは利用できなくなる。ノード集合の変更は慎重に行う必要があり、レイテンシが不安定なネットワークでは再選出や性能低下が繰り返されることがある。
メンバーシップとコーディネーションサービス
ZooKeeperやetcdのようなシステムは、合意の上に少数のコーディネーションプリミティブを提供する。
- 線形化可能な原子的操作。
- 操作の全順序化。
- リースとセッションによる障害検出。
- データ変更時の変更通知。
これらのプリミティブは、作業のノード割り当て、サービス探索、リーダー選出、メンバーシップ追跡、クラスタ設定に役立つ。
まとめ
線形化可能性は単純なメンタルモデルを提供するが、ネットワーク分断時には可用性を犠牲にする。原子的コミットは参加者間のall-or-nothingな決定を調整するが、ブロックすることがある。合意は障害があっても分散システムが安全に同意できるようにし、コーディネーションサービスはロック、リース、メンバーシップ、通知といった実用的なプリミティブとしてそれを公開する。