データ指向アプリケーションデザイン 9章 整理

※ 図は僕の想像なので、誤っている可能性もあります。

9章 一貫性と合意 (fault-tolerance を持つ分散システムを構築する為の algorithm と protocol)

本章の目的: Application が分散システムにおいて幾つかの問題 (Network fault, process 障害, clock 同期遅延等) を無視出来るようにする抽象概念を探っていく

• Consensus (合意)
  • 分散システムにおける重要な抽象概念
  • 全 node が何かについて合意すること
  • ex. Failover 時にどの node が leader になるかについて、全 node が同意していることが重要
    • そうでない場合、split brain 等の fault 発生の可能性

9.1 一貫性の保証

• Replication を行う DB は 結果整合性 (eventual consistency) ≒ 収束性 を提供している
  • Replication の lag は生じるものの(非一貫性)、最終的には解消される
    • lag の大きさ ≒ 保証の弱さ
      • Network 遅延や並列性が極端に高い等の fault があった場合に、結果整合性の edge case となる
• 強い保証を提供する一貫性モデルは、代価としてパフォーマンスや耐障害性の低下を伴う
• 分散一貫性モデルと transaction 分離レベルの階層は深く関連しているものの、両者の主眼は異なる
  • 一貫性モデルは遅延や fault に対し replication 状態を調整することが主眼
  • transaction 分離は競合状態を避けることが主眼

9.2 線形化可能性

• 線形化可能性 (linearizability) = 原子的一貫性 (atomic consistency) = 強い一貫性 (strong consistency) = 即時一貫性 (immediate consistency) = 外部一貫性 (external consistency) = 最新性の保証 (recency guarantee)
• 線形化可能性とは Register (key/行) の読み書きにおける最新性を保証すること
• 例えば replica data (copy) が1つしか無く、当該の data に対する全操作が atomic であるかのようにシステムに見せること
  • 1 つの client の書き込み後、即時に全 client が当該の値を見れるようにする必要がある
    • ex. 図9-1: 線形化可能性違反の例
      • Bob は Alice の後に select を実行しているが古い結果が返っている
    • ex. 図9-2: 不完全な線形化可能性の例
      • W/R の処理が並行しているタイミングは Register (key/行) の値は書き込み前・後どちらかも返る可能性がある
        • 新旧不定の値が返ることを regular register と呼ぶ
    • ex. 図9-3: ある程度完成されている線形化可能性の例
      • W/R の処理が並行しているタイミングでも、最初に Write で取得された値を他 client へ返す
    • ex. 図9-4: 完成されている線形化可能性の例
      • W/R の処理がシーケンスに行われる
      • Network 遅延による処理タイミングに影響を受けたとしても、sequence が保たれていれば問題無い
        • D の Write ではなく A の Write により (Network 遅延により) B の Read が1になるのは問題無い
      • compare-and-set 操作により平行して他 client から値が書き換えられていないかをチェックすることで atomic が保たれる
      • B は最後の Read で線形化可能性に違反している
        • C の Write と並行して A が4の値を Read している為、2を Read することは出来ない
• 直列化可能性 (Serializabile) との違い
  • 直列化可能性は transaction の分離性であり、複数の並行に稼働する transaction それぞれの結果が、いかなる場合もそれらの transaction を時間的重なりなく逐次実行した場合と同じ結果となることを指す
  • Register (key/行) の読み書きにおける最新性(順序)を保証すること
    • 複数の操作を transaction としてグループ化しないので、競合のマテリアライズのような対策を講じなければ、書き込みスキューのような問題を防げない
  • Read Skew Anomaly (書込スキュー) は防げない
• DB は直列化可能性と線形化可能性を共に提供可能
  • 厳密な直列化可能性 (strict serializability), 強い単一コピーの直列化可能性 (string one-copy serializability) と呼ばれる
  • 2Phase Lock や完全な順次実行は線形化可能性を持つ典型例だが、直列化可能なスナップショット分離からの読み取りは線形化可能ではない

9.2.2 線形化可能性への依存

• 単一 leader の replication を利用する場合の、"単一である"という保証はどうするのか?
  • lock を使う
    • leader になろうとする単一 node が線形化可能性で lock を取得する実装にし、全 node が lock を保持している node を把握している必要がある
    • 分散ロックマネージャー (Distributed lock manager) である Apache ZooKeeper, etcd を利用する
      • Fault tolerance を持ちながら linearizability (線形化可能) な操作を実装し、時間軸上のあらゆる点において、2つの client が同じ lock を保持することはない
        • 厳密には ZooKeeper と etcd では Write は線形化可能だが、Read では replica の何れかから値が返される為、返された値が古い場合がある
          • これはそれぞれの独自機能で防ぐことが可能
    • Oracle Real Application Cluster (RAC) は lock を disk の page 毎に仕様し、同一の disk storage を複数 node が共有する
      • database node 間通信に専用の cluster inter connect network を使用している
  • ユニーク制約を保証したいのであれば、linearizability (線形化可能性) が求められる
    • 2 client が並行して同じ名前で record を作成しようとした時にどちらかにエラーが返されるようにしたい場合や、並行して同じ flight や映画館の予約を行わないことを保証したい場合
    • lock と似ていて、選択した名前に対する lock を client が取得することと同意
  • cross-channel coupling in time-dependent (クロスチャンネルタイミング依存関係)
    • 図9-5: では、file storage が linearizability であれば問題無いが、そうでない場合競合 risk がある
      • もし resize module が古い version の画像を fetch してしまった場合は、storage と resize 後の画像が恒久的に一貫しない
      • linearizability による最新性の保証が無ければ、file storage, messaging queue という2つの異なる通信 channel 間で競合条件が生じる
  • linearlizability = data copy は1つしか無いように振る舞い、data に対する全操作は atomic である ということなので、最もシンプルな回答は本当に data を1つしか持たないということだが、耐障害性が無くなる
  • fault-tolerance を持たせる一般的なやり方は replication を利用すること
  • single leader replication
    • Read に leader を使う為には、leader がどれなのか確実に知っておく必要がある
    • asynchronous replication の場合、failover により commit された書込みさえも失われる可能性があり、これは durability(永続性), linearizability(線形化可能性) のどちらも違反となる
  • Consensus algorithm (合意アルゴリズム, linearizability)
    • single leader replication like で、且つ split brain や古い replica を回避する手段を持つ
      • ZooKeeper etcd 等
  • Multi leader replication
    • Write を 複数 node 上で並行処理し、async に他 node へ replication する為、linearizability ではない
    • replica が1つではない為、解決が必要な Write の競合が生じる場合がある
  • Leader less replication
    • 恐らく linearizability では無い
    • Quorum の R/W を必須とすることで強い一貫性が得られると言われるが、それは正しくない
      • 時刻同期に基づく衝突の解決法である Last Write Win を Cassandra が採用している
        • Clock には skew がある為、timestamp が事象の順序と一貫であることを保証出来ない為、ほぼ確実に linearizability 不可能
      • ex. 図9-6: A の request 完了後に B が request しているのに B には古い値が見え、A は新しい値が見えている
        • performance 低下を許容するのであれば、Read 時に同期的に読み取り修復を行い、書き込み時には書込み送信前に node の quorum の最新状態を読み取れるようにすれば、linearizability にすることは可能
          • Cassandra は quorum の read の時は読み取り修復の完了を待つが、同じ key に対する write が並行している場合、衝突解決に LWW を用いていることから linearizability では無い
  • DC 間で network 断が発生した場合
    • multi leader DB では片方の DC からの write は async に他方の DC へ replication されるので、write は queueing されていき、network 復帰時点で交換される
    • single leader DB では linearizability な read をすることが出来ない
    • CAP theorem (CAP 定理)
      • Linearizability を必要としない application は network の問題に対する耐性を高めることが出来る知見
        • 他の replica から切り離されてもそれぞれの replica が独立して request を処理出来るような方法で書込みを受け付ける (ex. multi leader)

9.3 順序の保証

• 順序と因果関係
  • 因果律: 質問と回答の間には因果関係がある
    • まずは行を作成しなければ、その行を更新することは出来ない
    • 因果関係には一貫性があり、その時点より前に生じている操作の結果は見えるが、後に発生している操作は見えない
      • read skew (nonrepeatable read) の問題は、因果律に違反が生じている状態でデータを読み取ろうとしていること
      • write skew は2つの transaction が、何の情報を参照しているかという因果関係に依存している
      • 線形化可能性に違反している場合は、因果律に対しての違反でもある
    • snapshot 分離は、因果律において一貫している (causally consistent) と言える
• 因果律に基づく順序と全順序の違い
  • 全順序で2つの要素の大小を判断出来る
    • 自然数における全順序の要素判定が可能
  • 集合には全順序が無い
    • {a,b}と{b,c}は比較不能(incomparable)であり、集合は半順序 (partially ordered) である
      • ある集合が他集合の全要素を含んでいる場合に、大きいといえる場合があるが、それ以外は incomparable である
  • 線形化可能なシステムにおける操作は全順序
    • data copy が1つしか無いように system が振る舞い、全操作が atomic であれば、2つの操作のどちらが先に実行されたかは必ず決まる
  • 2つの出来事が並行に行われている場合、因果関係があっても順序が無い為 incomparable である
    • つまり因果律は全順序ではなく半順序である
• 因果律の一貫性より強い線形化可能性
  • 線形化可能性は因果律の順序を保持・保証している
    • 代償としてパフォーマンスや可用性が損なわれ、ネットワーク遅延が大きい場合は特に問題になる可能性がある
      • パフォーマンスや可用性の面で結果整合性のシステムに近い性格を持ちつつ因果律を保持する新しい DB が研究されている
• Sequence number の順序
  • Sequence number, timestamp を利用してイベントを increment することで、因果律との一貫性を持つ全順序を提供することが可能
    • この時の timestamp は時刻の clock ではなく論理 clock で良い
  • 単一の single leader が存在せず、各 node が sequence 番号を生成したり物理 clock から取得した timestamp を各操作に付与した場合は、因果律に対する一貫性を持たない
    • 複数の node 間の操作で、sequence の生成が順序を正しく補足出来ない為
• Lamport timestamp
  • 因果律に対し一貫性を持つ sequence number を生成する (シンプルな) 方法
    • Lamport timestamp は node ID, counter のペアになっており、それぞれの timestamp がユニークになる
      • ここでは同期 clock は一切関連しない
      • ある node が受信したリクエストに含まれる値が、自身の値よりも大きい場合は node は自身の値を直ぐに最大値に更新する
    • 図9-8 のポイントとしては、node1 の counter が1の後 increment を経て6となっている部分
      • 最大の couter 値が操作と共に順序付けて increment されていく限りにおいて、Lamport timestamp による順序付けが因果律と一貫することが保証されている
  • Timestamp による順序付けでは不十分
    • 分散システムにおける課題を Lamport timestamp による因果律との一貫性では全て解決出来ない
      • 2人のユーザーが同じユーザー名で並行にアカウント作成しようとした場合に、timestamp では十分ではない
      • ユーザーからのリクエストで 即座に成功・失敗を判断したい場合 、並行して他 node が処理途中に障害が起きていたりネットワークの問題で接続不可となっていることを考慮すると、耐障害性を持っているとは言えない
        • 全順序がいつまでに確定するのか、確定時期を把握する必要がある (全順序の broadcast)
• 全順序の broadcast
  • single leader replication は1つの node を leader として選出し、全ての操作を leader 上の single core で順に処理することにより操作の全順序を決定する
    • 操作の throughput が single leader の処理を超える場合の scalability と leader の failover が問題となる、この問題を解決出来るのが、全順序の broadcast (atomic broadcast)
  • state machine replication の原則を持つ
    • 信頼できる配信: message が1つの node に配信された場合、他の全 node へ配信されなければならない
      • message が配信された時点で順序が確定する
    • 全順序付された配信: message は全 node に同じ順序で配信されなければならない
      • message の配信は log への追記と同じようなもの (replication log, WAL)
    • node, network 障害が発生しても、信頼性と順序付け, 一貫性を保つ(retry し続ける)
  • 非同期であり、決まった順序で信頼性を保ち配信されることが保証されているが、いつ配信されるかは保証されない
    • これに対して線形化可能性は最新性を保証しており、Read の際に Write の最新値が見える
      • 線形化可能な compare-and-set 操作を、全順序 broadcast と組み合わせて利用すれば、線形化可能な storage を構築出来る
        • 全 node が書込みの commit や中断に合意するのを保証する
        • 書込みは線形化可能になるが、読み取りは古い場合があり線形化可能性は保証されていない (逐次一貫性: sequential consistency)
      • 上記とは逆に、線形化可能な storage から全順序 broadcast を構築する方法
        • 全順序 broadcast で送信した message に線形化可能な increment-and-set 操作を行い、整数を register へ保存。次に register から取得した値を sequence number として message へ添付し全 node へ配信することで実現可能

9.4 分散 transaction と合意

• 合意 (consensus) とは、複数の node を"何かについて"合意させることで、合意を取ることの例は次の通り
  • leader election (選出)
    • ex. split brain 対策としての合意
  • atomic commit 問題
    • Transaction の atomic を保つ為、全 node に対し transaction の結果 (abort, rollback, commit) について合意させる必要がある
  • consensus の不可能性 (FLP:Faulty Process 帰結)
    • node が crash する risk があるなら、合意に達する algorithm は存在しないという証明
      • clock 同期や timeout を使わない前提の制約の強い環境での証明であり、その制約が無い場合は合意可能
• atomic な commit と 2 phase commit
  • atomic は失敗した transaction が DB に中途半端な処理結果を残したり更新することを防ぐ
  • atomic は secondary index が主データと一貫した状態を保つことを保証する
  • client が node に対し transaction を commit すると、DB はその書込みにdurability(永続性)を持たせ(WAL)、commit log を disk 上の log に追記する
    • DB が途中で crash した場合は WAL から transaction を recovery 出来る
  • 複数の node が1つの transaction に関わっていた場合は、commit 要求を全 node へ送り、個々の node 上で独立して transaction を commit しても、一部の node で失敗する可能性がある
  • transaction に関わる他の node も commit しようとしていることが確実な場合に、一度だけ実行するようにしなければならない
  • 2 phase commit は複数 node に跨る atomic な transaction を実現する algorithm
    • 全ての node が commit するか、もしくは全ての commit が中断するかの二択
    • 2PC transaction は複数の node (transaction の参加者と呼ばれる) にて、 coodinator (transaction manager) 経由で以下の手続きを行う
      • phase1. Coodinator が各 node に commit 出来るかを問い合わせ
      • phase2. 全 node が問題無ければ commit request を送信
        • いずれかの node に問題があった場合、phase2. で中断 request を送信する
    • 2PC は2つの帰還不能点を持つ
      • phase1.でyesを返した時点で全 node は間違いなく commit 出来ることを約束している
      • coodinator が決断をした時点で atomic が保証される
      • 図:9-10 coodinator がデータベース1に commit する前に crush してしまい、node は commit すれば良いのか abort すれば良いのか判断出来ない状態になってしまう
  • atomic commit には node が crush したかどうかを教えてくれる仕組み (perfect failure detector) が必要
    • 分散 transaction が2PC で実装されている場合、評価が分かれる
      • 重要な安全保証を提供しているとみなされたり、パフォーマンスを損ない、運用上の問題の原因となるとみなされたり、両極端な評価である
    • 分散 transaction には2種類あり、どちらも atomic な commit を保証しなければならない
      • database 内部の分散 transaction
        • node 間にまたがる内部的な transaction をサポートしている。この場合、transaction に参加している全ての node は同じ database software を実行している
      • ヘテロジニアスな分散 transaction
        • 参加者は2つ以上の database, message broker 等、異なる技術を利用している場合
          • X/Open XA (eXtended Architecture) transaction はヘテロジニアスな技術間での2PCの標準
            • application process が crush したり server が落ちた場合、coodinator も落ちてしまう為、未 commit の transaction を持つ node は未確定の状態となる
            • application server 上には coodinator の log あるため、coodinator の library は log を読み取り各 transaction の commit/abort の結果を recovery する
            • 上記が終わって coodinator は database driver の XA callback を利用して node に commit/abort を要求出来るようになる
    • 未確定状態中の lock の保持
      • dirty write を避けるため、変更行の排他 lock を取得し、直列化可能な分離レベルが必要な場合、2PLを利用するDBも読み取り業に対する共有 lock を取得しなければならない
      • DB は transaction が commit/abort されるまでは lock を解放できない
        • 2PC を利用する場合、未確定状態の間 lock を保持しておく必要があり、coodinator が20min crush した場合、lock は 20min 保持される
        • これらの lock が保持されている間、他 transaction は lock 行を変更出来ず、読むことさえ lock されるかもしれない
    • もし coodinator が結果を判断できなくなってしまった transaction があった場合、手作業で transaction の commit/rollback している node があるかを確認し、他 node にも適用する必要がある
• 分散 transaction の限界
  • 多くの coodinator はデフォルトで高可用性を持たないか基本的な replication しかサポートしていない
    • coodinator に障害があれば、他の application server は未確定状態の transaction が保持している lcok により block されてしまう為
  • coodinator が application server の一部になっている場合、stateless にすることが難しい
  • XA は幅広いデータシステムに適合しなければならない
  • 2PC において transaction commit が成功するために全 node が反応を返す必要があり、node のどこか一部が破壊された場合分散 transaction は障害を増幅する可能性がある (耐障害性を損なう)

9.4.3 耐障害性を持つ合意

• 合意は1つ以上の node が値を提案し、合意アルゴリズムはそれらの値の中から1つを決定する
  • 複数顧客が並行して最後の席を購入する場合、各 node は受け持っている顧客 ID を提案し、決定内容は席を購入出来た顧客となる
• 合意アルゴリズムは次の性質を持つ
  • 一様同意 (uniform agreement)
    • 2つの node が異なる決定をしていないこと
  • 整合性 (integrity)
    • node が複数回決定を下していないこと
  • 妥当性 (validity)
    • node が値 v を決定後、u を提案する node が存在すること
  • 終了性 (termination)
    • crash していない全 node は最終的に何らかの値を決定すること
    • いかなる合意アルゴリズムも終了性を保証するには過半数以上の node が正しく動作している必要がある
    • 半数は quorum を形成可能
• 合意のシステムモデルにおいて crash した node は決して復帰しないことを前提とする

9.4.3.1 合意アルゴリズムと全順序 broadcast

• 全順序 broadcast では message が一度だけ同じ順序で全 node へ配信されなければならない
• 合意の同意性から全 node は同じ message を同じ順序で配信することを決定する
• 整合性から message が複製されることは無い
• 妥当性から message が壊されたり改変されることもない
• 終了性から message が失われることは無い

9.4.3.2 シングルリーダーレプリケーションと合意

• Split brain の問題はだれが leader かについて全 node が同意しなければ database の一貫性が損なわれることとなる

9.4.3.3 Epoch 番号と quorum

• Leader がユニークであることを (弱く) 保証している合意プロトコルは Epoch 番号と呼ばれ、各 epoch 内で leader がユニークであることを保証する
• 新しい leader が選出される度に、現在の leader が落ちたと考えられる度に、node 間で新しい leader 選出投票が始まり、leader は epoch 番号を元に決定される
• 2PC との違い
  • 2PC においては coodinator は選出されるものではない
  • 耐障害性を持つ合意アルゴリズムにおいては投票は過半数 node からのみ必要なのに対し 2PC は全 node から yes という返答が必要になる

9.4.3.4 合意の限界

• 合意のアルゴリズムは不確実性を持つシステムに同意、整合性、妥当性をもたらし、耐障害性を保つ
  • node の過半数が動作しており、到達可能であれば処理が進められる
• 半面、合意のアルゴリズムは代償を伴う
  • 非同期 replication 下では commit が failover の際に失われる可能性がある (が、パフォーマンス向上の為に多くの場合このリスクを許容している)
  • node の動的な追加や削除は簡単には行えない
  • 障害の検出を timeout に依存しているが、ネットワーク遅延が大きい場合は node が誤って leader に障害が生じていると判断し頻繁に leader 選出が行われる場合はパフォーマンスが顕著に劣化する場合がある

9.4.4 メンバーシップと協調サービス

• ZooKeeper, etcd の API は指定された key に対する値を読み書きし key に繰り返し処理を進めていくといった点で database と同じであり、データベースと同じであれば何故わざわざ合意アルゴリズムを実装する必要があるのか?
  • ZooKeeper, etcd はメモリ内に収まる少量のデータを保持するよう設計されており、耐障害性を持つ全順序 broadcast アルゴリズムを用いて全 node に replication される
  • 複数機能の組み合わせにより、分散協調の為に有益な作りとなっている
    • 線形化可能で atomic な操作
      • atomic な compare-and-set 操作を利用した複数 node 間における安全なロック
      • 線形化可能であることを保証する
      • 分散ロックは有効期限を持つ lease である為、client に障害があった場合も最終的には解放される
    • 操作の全順序
      • fencing token によるロックのインクリメント化 (transaction id:zxid, version number:cversion) による全操作の全順序付け
    • 障害検出
      • client は ZooKeeper の server と長時間に渡る session を管理し client,server 間で heatbeat による死活チェックを実施
      • session が保持するロックは、session timeout 時に自動解放可能
    • 変更通知
      • client は他 client が作成したロック及び値の変更を読み取り監視出来る為、client の増減や障害検知、通知が可能

9.4.4.1 node への処理割り当て

• ZooKeeper, Chubby が得意な構成
  • サービスを提供する複数インスタンスがあり、内1つを leader として選出する必要のある構成
  • partitioning されたDB, messaging, file storageの内、どの node にどの partition か判断が必要な環境
• 数千 node が稼働している場合過半数の投票を実行するのは現実的では無いが、ZooKeeper を固定数(3,5 node)の node 上で動作させ、過半数の投票はこれらの間でのみ実施する方法もある

9.4.4.2 サービスディスカバリー

• サービス名に対応する IP address をルックアップする方法としては DNS が使われてきた。
• DNS は高パフォーマンス、高可用性を実現する為に複数レイヤーで caching を利用しており、DNS からの読み取りは線形化可能ではない
  • 信頼性・可用性・ネットワーク障害への耐性が重要であり、DNS query からの読み取り結果が古くともそれは問題だと見なされない
• 合意システムの中には read only のキャッシュを扱う replica をサポートするものがあり、投票に参加せずに leader 選出の合意が可能である

9.4.4.3 メンバーシップ

• membership service は、active で cluster member となっている node を判断するのに利用出来る
• 通常 network 遅延には上限が無い為、他 node に故障が生じているかを信頼性を持って判断することは不可能だが、合意と障害検出を組み合わせればどの node が生きて落ちているか node 間で合意出来る
• membership service は、どういった node 群によって membership が構成されているのかについて、全 node 間で共有できる

まとめ

• 一貫性と合意
  • 一貫性モデルである線形化可能性が目標とするのは replication されたデータがあたかも1つしか無いように見せ、当該データに対する操作が atomic に働くようにすること
  • DB が single thread のプログラムにおける変数のように振る舞う反面、速度が落ちるという欠点がありネットワーク遅延が大きい環境では顕著になる
• 因果律
  • イベントに順序を定義し、因果的に関連している書き込みは全てのプロセスによって同じ順序で観測されなければならない
  • 弱い一貫性モデルを提供する
  • 因果律の順序を lamport timestamp 等で捕捉する場合、他 node への同じ名前の並行書き込みが行われていないか知る必要 (合意) があった
• 合意
  • 全 node が決定に同意すること
  • 線形化可能な compare-and-set register
    • 並行して他 client から値が書き換えられていないかをチェックし値を設定するかどうかを決定することで atomic が保たれる
  • atomic な transaction の commit
    • DB は分散トランザクションを commit するか中断するか決定しなければならない
  • 全順序 broadcast
    • message system は配信順序を決定しなければならない
  • lock と lease
    • 複数 client が一斉に lock, lease を取得しようとした場合、lock はどの client が取得に成功するか決定する
  • membership/協調サービス
    • 障害検知の仕組み(timeout 等)を利用しどの node が生きているか、落ちているかを決定しなければならない
  • unique 制約
    • 複数 transaction が並行して同じ key の下で衝突する record を作成しようとした場合、制約はどの record を登録するか決定しなければならない
• もし single leader に障害があった場合、対処方としては3つ
  • leader の復帰を待ち、それまでの間はリクエストをブロックする
  • 手動で failover を行い、新 leader node と設定を手動で行う
  • 合意アルゴリズムにより自動で新しい leader を選出する
• ZooKeeper 等のツールは application から利用できる合意、障害検出、membership 管理、耐障害性を提供する
• leader less application は合意を用いず、単純に線形化可能性が無いことへ対処し、分岐や合流を伴うバージョン履歴を持つデータを扱えるようにするのみで良い