データ指向アプリケーションデザイン第９章: 一貫性と合意
ch09 一貫性と合意
耐障害性をもつシステムを構築する最も最善の方法は、有益な保証をもつ汎用的な抽象概念を見出し、それを一度だけ実装し、アプリケーションをその保証に依存させること
分散システムにおいても、分散システムにおける問題をアプリケーションがいくつか無視できるようにしてくれる抽象概念がある
- 例えば、合意 (consensus): すべてのノードが何かについて同意すること
一貫性の保証
レプリケーションを行うデータベースのほとんどは少なくとも結果整合性を提供する
- ある程度待てば最終的には読み取りリクエストに対してすべて同じ結果を返すようになること
- 収束性という言葉の方が合っている
分散一貫性モデルとトランザクション分離モデル
線形化可能性
考え方の背景
- 同時に異なる二つのレプリカにクエリを投げると異なる結果が返ってくることがある（結果整合性）
- データベースがレプリカが一つしかないように見せる方がシンプル
- クライアントはデータを同じように見ることになり、レプリケーションラグを気にする必要がない
線形化可能性
- 原子的一貫性、強い一貫性、即時一貫性、外部一貫性と呼ばれることがある
- 線形化可能性とは最新性の保証 (recency guarantee) を意味する
- データベースから読み取りを行う場合、読み取られる値が最新であり、古くなったキャッシュやレプリカからの値でないことを保証する
システムを線形化可能にする条件
- 3 つのクライアントが読み書きする例でどういう条件が必要か考える
- パターン 1:
レジスタに対する操作
線形可能性である場合のレスポンス
- クライアント A の最初の読み取り => 間違いなく 0 が返ってくる
- クライアント A の最後の読み取り => 書き込みが完了した後に始まっているので間違いなく 1 が返ってくる
- 書き込み処理と重なって実行された読み取り => 0 または 1 が返ってくる
これだけだと線形可能性であるための条件としては不十分
- 読み取りと書き込みが並行している場合に、新旧の値のいずれかが返ってくるとなると、読み取りのたびに異なる値が返ってくる可能性がある
- これはデータのコピーが一つしかなく、常に最新の値が返ってくるという線形可能性に違反する
そこで制約を加える
どこかの時点で x の値が 0 から 1 にアトミックに変更され、あるクラインアントの読み取りに対して新しい値 1 が返されたら、 それ以降の読み取りはすべて新しい値を返さないといけない
もっと複雑な例
追加の操作
- cas(x, v_old, v_new) => r: クライアントがアトミックな compare-and-set 操作を要求したという意味
線形化可能にするためには、操作のマーカーを連結する線が常に時間軸の中で前に進み、決して後ろに戻らないこと
- 操作のマーカー（垂直線）：データベースが処理を実行したタイミング
- このモデルはトランザクションの分離は想定されていないため、値はいつでも他のクライアントによって書き換えられる
線形化可能な直感イメージは上記の通りだが、形式的な定義も存在する。この定義にしたがっているかどうかテストすることも可能だが、演算負荷が非常に高い。
線形化可能性と直列化可能性
直列化可能性
線形化可能性
- レジスタの読み書きにおける最新性の保証(ここのオブジェクトに関すること)
データベースは、直列化可能性と線形化可能性を同時に提供できる
- 厳密な直列化可能性、強い単一コピーの直列化可能性と呼ばれる
- 2PL による直列化可能性の実装や完全順次実行の実装はこれにあたる
直列化可能なスナップショット分離 (SSI)は、線形化可能ではない
線形化可能性への依存
- 線形化可能性が役立つ場面は？
ロックとリーダー選出
- 単一リーダーのレプリケーションを利用するシステムは、単一のリーダーしかいないことを保証する必要がある
- リーダー選出の方法の一つはロックを使うこと
- このロックは線形化可能でなければならない
制約及びユニーク性の保証
- ユーザー名、メールアドレス、ファイルストレージサービスのファイルパスに対するユニーク性
- これらを書き込まれる際に保証したいなら線形化可能性でなければならない
クロスチャネルタイミングの依存関係
- メッセージキューとファイルストレージのように二つの異なる通信チャネルが合った場合に、線形化可能性の最新性の保証がない場合にレース条件が発生する
線形化可能なシステムの実装
データのコピーが一つしかないように振る舞い、データに対するすべての操作はアトミックであるというのが線形化可能性
- 合意アルゴリズム（線形化可能)
- マルチリーダーレプリケーション（線形化可能ではない)
リーダーレスレプリケーション（おそらく線形化可能ではない）
線形化可能性とクオラム
- 厳密なクオラムでも線形化可能にできない
- パフォーマンス低下を受け入れることができるのであれば、Dynamo スタイルのクオラムを線形化可能にすることはできる
- 読み取りの際にはアプリケーションに結果を返す前に読み取り修復を同期的に行う
- 書き込みの際には書き込みの送信前にノードのクオラムの最新状態を読み取れるようにする
線形化可能にすることによるコスト
- アプリケーションに線形可能化が必須である場合、一部のレプリカが他のレプリカからネットワークの問題で切り離されてしまったら、 切り離されているレプリカは利用できない（ネットワークの問題が解消されるのをまつか、エラーを返す）
アプリケーションに線形可能化が必須でない場合、レプリカが切り離されてしまったとしても、それぞれのレプリカが独立してリクエストを処理できるような方法で書き込みを受け付けることができる
- ネットワークの問題が生じても利用できるが、その動作は線形化可能ではない
CAP 定理の対象範囲は非常に狭い
- 1 つの一貫性モデル（線形化可能性）と 1 種類のフォールト（ネットワーク分離）だけを対象とする
線形化可能性とネットワーク遅延
線形化可能性を持っているシステムは少ない...
- マルチコア CPU の RAM でさえ線形化可能ではない
- メモリバリア、フェンスが使用されないかぎり...メモリからの読み取りの最新性は保証されない
- マルチコア CPU の RAM でさえ線形化可能ではない
なぜ線形化可能性をもつシステムが少ないのか
- ひとえにパフォーマンス影響のせい。耐障害性よりもパフォーマンスを重視するケースの方が多いため、線形化可能性を捨てて、
パフォーマンス向上を図る
- 線形化可能にすると、そうしない場合と比較すると必ず読み書きのパフォーマンスが悪化する
- ひとえにパフォーマンス影響のせい。耐障害性よりもパフォーマンスを重視するケースの方が多いため、線形化可能性を捨てて、
パフォーマンス向上を図る
順序の保証
- 順序は重要な概念
順序と因果関係
- 順序は因果関係を保つのに役立つ
- 因果律はイベント間に順序関係を発生させる
因果律に基づく順序と全順序の違い
全順序があれば任意の二つの要素を比較できるので、必ず大小関係を判断できる
線形化可能性: 操作に全順序がある
線形化可能は因果律を暗に含む
因果律における依存関係の補足
- 因果律を保持するためには、ある操作に対してどの操作が先行したのかを知る必要がある
シーケンス番号の順序
シーケンス番号、タイムスタンプを使ってイベントの順序づけを行うことができる
- 物理クロックでなくて良い。論理クロック(操作を特定するための数値の並びを生成するアルゴリズム)で問題ない。
因果的でないシーケンス番号生成器
シングルリーダーではない、マルチリーダーやリーダーレスの場合、シーケンス生成は以下のようになる
- 各ノードが独立して、自分用のシーケンス番号の集合を生成できる(A ノードは偶数、B ノードは奇数等)
- 24 時間制のクロックから取得したタインプスタンプを各操作に割り当てる(LWW)
- あらかじめ、シーケンス番号のブロックを割り当てておく(A ノードは 1-1000、B ノードは 1001 - 2000 等)
カウンタをインクリメントする方法よりもスケーラビリティがあり、パフォーマンスが高いかもしれない...
ランポートタイムスタンプ(lamport timestamp)
- ただし、全順序があるだけでは不十分なケースがある
- 例えばユーザ名に対するユニーク制約のようなものを実装する場合
- 順序がいつまでに確定するのかがわからなければならない
- 同じユーザ名を全順序中でその操作よりも先に要求しているノードが他にはないことが確実になってはじめて、その操作が成功したと安全にいえる
- 順序がいつまでに確定するのかがわからなければならない
- 例えばユーザ名に対するユニーク制約のようなものを実装する場合
全順序のブロードキャスト
シングルリーダーレプリケーションは、リーダーの単一の CPU コアですべての操作を並べることによって全順序を保証する
- リーダーに障害があった場合にはどうする？
- 単一ののリーダーで処理できる以上のスループットだった場合は？
これらの問題は全順序のブロードキャスト、アトミックブロードキャストと呼ばれる
全順序のブロードキャストは通常ノード間のメッセージ交換プロトコルとして記述される
- 非形式的には二つの安全性が常に満たされていなければならない
- 信頼できる配信: メッセージがロストしてはいけない
- 全順序づけされた配信: メッセージはすべてのノードに同じ順序で配信されなければならない
- 非形式的には二つの安全性が常に満たされていなければならない
全順序ブロードキャストの利用
全順序ブロードキャスト = 線形化可能な CAS = 合意
分散トランザクションと合意
- 合意は分散コンピューティングにおいて最も基本的で重要な問題
合意は難しい。少なくとも以下のことを理解していないといけない。
ノード群の合意をとることが重要な状況
- リーダー選出
- アトミックコミット
FLP 帰結(合意の不可能性)
アトミックなコミットと 2 相コミット
- トランザクションの原子性: 複数の書き込みの途中で問題が生じた場合のシンプルなセマンティクス
- 失敗する(中断する）か、成功するかのどちらか
- データベースに中途半端な状態の結果を残さない
- セカンダリインデックス（主たるデータとは別のデータ構造）と主たるデータの一貫性も保つ
単一ノードから分散アトミックコミットへ
- 単一ノードの実行されるトランザクションは、原子性は一般にストレージエンジンによって実装される
単一ノードのデータベースにおける永続性の提供の仕組み
単一ノード上では、トランザクションのコミットはデータが永続性を持ってディスクに書き込まれる順序に依存している
- データの書き込み -> コミット
2 相コミット(2PC)
- コーディネータ（トランザクションマネージャー）が登場する
アプリケーションがコミットできる準備が整ったら、コーディネータはフェーズ 1 を開始する
- コーディネータは準備リクエストを各ノードに送信し、それらがコミットできるかを問い合わせる
- コーディネータは参加者からのレスポンスを追跡する
すべての参加者が yes を返し、コミットの準備が整っていることを示してきたら、コーディネータはフェーズ 2 でコミットリクエストを送信する => 実際にコミットが行われる
いずれかの参加者が no を返したら、コーディネータはフェーズ 2 ですべてのノードに中断リクエストを送信する
2PC 詳細
- 分散トランザクションを開始したい場合、アプリケーションはコーディネータに対してグローバルユニークなトランザクション ID を要求する
- アプリケーションは、各参加者上で単一ノードのトランザクションを開始し、それらのトランザクションに対してグローバルユニークなトランザクション ID を添付する
アプリケーションコミットの準備が整ったら、コーディネータはグローバルなトランザクション ID をタグづけした準備のリクエストをすべての参加者に送信する
準備のリクエストを受信した参加者は、いかなる環境下でもそのトランザクションを間違いなくコミットできることを確認する
- トランザクションの全データをディスクに書き込めること、制約違反の有無のチェックを行う
コーディネータは準備のリクエストに対するレスポンスのすべてを受け取ったら、トランザクションをコミットするか中断するか最終的に判断する
- コーディネータはコミットポイント(クラッシュが生じたとしてもコミットするか中断するかを下した判断がわかるようにするポイント)を残す
コミットポイントの判断がディスクにかかれたら、コミットもしくは中断のリクエストがすべての参加者に送られる
コーディネータの障害
- もしコーディネータに障害が発生した場合は、参加者はコーディネータのリカバリを待つこと以外に 2PC を完結させる方法はない
- 参加者同士で通信して互いの状況を知って何らかの同意を得るということは可能だが、2PC にはこうしたプロトコルはない
スリーフェーズコミット
2 相コミットはブロッキングアトミックコミットプロトコルと呼ばれる
- これは 2PC がコーディネータのリカバリを持って行き詰まってしまう場合があることからきている
2PC に代るものとして 3PC が提唱された
- ただしネットワークの遅延に上限があり、ノードのレスポンスタイムにも上限があることを想定している
- ので現実的なシステムでは 3PC で原子性を保証することはできない
- ただしネットワークの遅延に上限があり、ノードのレスポンスタイムにも上限があることを想定している
分散トランザクションの実際
2PC はパフォーマンス上のペナルティを伴うケースが多い
分散トランザクションとは何か？2 種類ある
exactly-once なメッセージ処理
- ヘトロジニアスな分散トランザクションは多様なシステムを結合する
XA トランザクション
- X/OpenXA: ヘトロジニアスな技術間での 2 相コミットの標準
未確定状態中のロックの保持
- 未確定状態で行き詰まったトランザクションは、ロックの影響を受ける
コーディネータからの障害のリカバリ
- orphaned 未確定トランザクションが生じる可能性がある
分散トランザクションの限界
- コーディネータは一種のデータベース扱い
- 単一マシン上でコーディネータが動作している場合にはシステム全体にとっての単一障害点になる
- アプリケーションサーバはステートレスで、永続化すべきステートはデータベースに保存することがほとんど。コーディネータはアプリケーション側のライブラリとして提供されることがほとんどなので、ステートレスなアプリケーションサーバにステートが持ち込まれることになる
- SSI と共に動作することはできない
- 一つの参加者が壊れたら、他のすべてに影響が及ぼされる(つまり、XA トランザクションは障害を増加する傾向にある)
耐障害性をもつ合意
- 合意とは、複数のノードが何かについて同意すること
合意の問題は以下のように形式化される
- 1 つ以上のノードが値を提案 (propose)する
- それらの値の中から一つを決定 (deside)する
合意が満たさなければいけない性質
- 一様同意 (uniform agreement)
- 2 つのノードが異なる決定をしていないこと
- 整合性 (integrity)
- 2 回決定をしているノードがないこと
- 妥当性 (validity)
- ノードが値 v を決定したら、v を提案しているノードがあること
- 終了性 (termination)
- クラッシュしていないすべてのノードは最終的に何らかの値を決定すること
- 一様同意 (uniform agreement)
合意のシステムモデル
- クラッシュしたノードは突然消え去り、決して戻ってこないことを前提としている
- 2PC は終了性の要件を満たすことができない
- クラッシュしたノードは突然消え去り、決して戻ってこないことを前提としている
合意アルゴリズムと全順序ブロードキャスト
耐障害性をもつ合意アルゴリズムとして最も広く知られているもの
- VSR (Viewstamped Replication)
- Paxos
- Raft
- Zab
これらのアルゴリズムは、一様同意/整合性/妥当性/終了性という同意の形式的性質を直接利用せずに、値の並びを決定することによって全順序ブロードキャストになっている
- 全順序ブロードキャストは、メッセージが厳密に一度だけ、同じ順序でメッセージがすべてのノードに配信されなければならない
- 全順序ブロードキャストは、複数回に渡って合意をとることと等価
シングルリーダーレプリケーションと合意
- リーダーの選出を自動で（管理者の手を介在することなく）行う場合には、合意が必要
エポック番号とクオラム
合意プロトコルでは、内部的に何らかのリーダーを使っているがユニーク性は保証していない。その代わりに弱い保証を与える
- エポック番号
- Paxos の場合: 投票番号
- VSR の場合: ビュー番号
- Raft の場合: 期間番号
- エポック番号
現在のリーダーが落ちたと考えられるたびに、ノード間で新しいリーダーを選出するための投票が始まる
- この選出に対してインクリメントされるエポック番号が与えられる
- エポック番号は全順序をもち、単調増加する
- 二つの異なるエポック番号があり、二つの異なるリーダーが選出されたら、大きいエポック番号をもつリーダーが優先される
- この選出に対してインクリメントされるエポック番号が与えられる
リーダーは何かを決定する前にまず自分より大きいエポック番号を持ち、衝突する判断をするかもしれない他のリーダーがいないことを確認する必要がある
- リーダーはクオラムから投票を集める
- 投票には 2 回のラウンドがある
- 1 回目はリーダー選出のための投票
- 2 回目はリーダーの提案に対する投票
- 2 つの投票のクオラムには重複部分が必要
- 最初のリーダー選出の投票に参加したノードは、2 回目のリーダーの提案に対する投票にも参加していなければならない
- 投票には 2 回のラウンドがある
- リーダーはクオラムから投票を集める
2PC と合意は似ているけれど違う
- コーディネータは選出されないが、合意におけるリーダーは選出される
- 2PC ではすべての参加者の yes が必要だが、合意は過半数で良い
合意の限界
- 合意によって強固な安全性が提供されて、耐障害性を保てる
全順序ブロードキャストを提供するため、線形化可能でアトミックな操作を実装できる
限界点
- 合意プロトコルにおける投票は同期レプリケーションの一種であるため、パフォーマンス上の問題が発生する可能性がある
- 処理を行う上で厳密な過半数を必要とする
- 投票に参加するノード集合が固定の集合であることが前提とされることが多い
- 動的なメンバーシップの拡張を加えたアルゴリズムの理解はまだそれほど進んでいない
- 障害が発生しているノードの検出をタイムアウトに依存している
- ネットワーク遅延の影響によりリーダー選出プロセスが頻繁に起きてパフォーマンスを損なう可能性がある
- Raft にはよく知られた問題がある
- ネットワークが全体的には正しく動作しており、特定の一つのネットワークリンクで信頼性が低い状態が続いている場合、継続的にリーダー湿布が 2 つのノード間で行き来し続けてしまったりして効果的な処理を進められなくなる
メンバーシップと協調サービス
- ZooKeeper, etcd は「分散キーバリューストア」「協調及び設定サービス」と説明される
- 普通のユーザーがデータベースを利用するように ZooKeeper や etcd を使うことは滅多にない
- 通常は何らかの他のプロジェクトを通じて間接的に利用することがほとんど
ZooKeeper の場合以下のプロジェクトから依存されている
- HBase
- Hadoop YARN
- OpenStack Nove
- Kafka
ZooKeeper や etcd は完全にメモリ内に収まる少量のデータを保持するように設計されている（永続性のためにディスクへの書き込みは行われる）
分散システムを構築する上で有益な機能群
- 線形化可能ででアトミックな操作
- 操作の全順序
- 障害検出
- 変更通知
