sile/main.md

## main.md

      
    Raw
  

              main.md
            
          
    要約: 『Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services』

概要


著者: Seth Gilbert、Nancy Lynch、発行年: 2002
いわゆる"CAP定理"の話:

「分散環境では 一貫性(Consistency) と 可用性(Availability) と 分断耐性(Partition tolerance) の三つを同時に達成することはできない」


その不可能性の証明と、その制限を非同期環境および部分的同期環境でどう緩和するか、が述べられている

1 導入

2000年にBrewerさんが以下のような推測を述べた:

Webサービスが以下の三つの性質を(同時に)保証することはできない

一貫性(Consistency)
可用性(Availability)
分断耐性(Partition tolerance)


いずれも実世界のWebサービスには望ましく、また期待される性質でもある

この論文の構成:

Brewerの推測の意図について議論（1節)
その概念を形式化し、推測を証明 (2節)
この実際の困難に対する、いくつかの実世界での解決策の形式化、を試みる (3,4節)

WebサービスとCAP:

一貫性:

今日の大半のWebサービスは、強い一貫性を持つデータを提供することを試みている
ACIDデータベースのデザインに対する大量の研究がある

Atomic: トランザクションは「完全に成功(commit)」するか「完全に失敗」するかのどちらか
Consistent: コミット結果は、その後の全てのトランザクションによって認識される
Isolated: 未コミットなトランザクションは他から見えない
Durable: コミット結果は永続化される


分散Webサービスを構築するための新しいフレームワークの大半は、そのようなデータベースに依存している

課金情報や商取引を扱う場合に、ACID的な強い一貫性が重要なのは明白


可用性:

同様にWebサービスは、高可用性も期待されている
クライアントからの全てのリクエストは成功し、応答が返されるべき

「ネットワークが繋がっている限りはサービスを提供可能であること」が目標


分断耐性:

高度に分散したネットワーク上では、ある程度の障害耐性を提供することが望ましい

一つのノードがクラッシュしたり、一つの通信リンクが故障した場合でも、サービス自体は期待通りに動作を続ける


望ましい障害耐性性質は、ネットワーク分断により、複数のコンポーネント群に分断された場合でも生き残る能力

ノードクラッシュ、は分断の一種とモデル化できる(ので明示的には扱わない)


2 形式的なモデル

この節では"一貫性がある"、"可用性がある"、"分断耐性がある"といった言葉の意味を形式的に定義する。
2.1 アトミックデータオブジェクト


「一貫性のあるサービス」というアイディアを形式化する最も自然な方法は、それを アトミックデータオブジェクト として見ること
アトミック(ないし線形化可能性)一貫性は、今日の大半のWebサービスに期待される条件
アトミック性:

全操作(i.e., クライアントから発行されたリクエスト群)に全順序を定められる
その順序は、各操作の実時間順序を反映している
=> 外部からは「単一ノードでリクエスト群が処理されている」ような挙動として観測可能 (e.g., 直前にwriteされた値がreadされる)


サービスを利用するユーザが最も理解しやすいモデル

2.2 可用性のあるデータオブジェクト


分散システムが継続的に利用可能(可用性がある)と言えるためには、

故障していないノードに対するリクエストには、応答が返されるべき
つまりシステムで使用されているアルゴリズムは最終的には終了(terminate)しなければならない


ある面では、これは可用性の弱い定義:

終了までの上限が定められていないので


別の面では、(分断耐性という条件が課された場合には)可用性の強い定義ともみなせる:

深刻なネットワーク障害が発生した場合でも、全てのリクエストは終了しなければならない


2.3 分断耐性


上述のアトミック性と可用性の定義は、分断耐性の必要性によって条件付けされる
"分断"は「コンポーネントを跨いで送信されたメッセージの消失」としてモデル化可能:

ネットワークが複数のコンポーネント群に分断された場合、あるコンポーネントに属するノードから、別のコンポーネントのノードに送られた全メッセージが消失する
任意のメッセージの消失は「一時的な分断」としてモデル化可能


つまり分断耐性を考慮すると、アトミック性および可用性は「任意のメッセージが消失する」ようなケースでも達成される必要がある

ネットワーク全体の故障時を除いて、システムが不適切な応答を返すことを許さない
単一ノードでも生存しているなら、それは正しい応答を返さなければならない


3 非同期ネットワーク

3.1 不可能性の帰結

推測の証明には、非同期ネットワークモデルを使用する:

時計がない
ノードはメッセージ送受信と、ローカルの計算によって決定を行わなければならない

定理1


非同期ネットワークモデルで、以下の性質を保証する読み書きデータオブジェクトを実装することは不可能

可用性
アトミック一貫性


メッセージ消失が生じ得る全てのフェアな実行において、上記が成り立つ

"フェア": 「特定のノードの処理だけが永遠に実行される」といった不公平がない


証明

背理法によって証明:

棄却される仮定: 「CAP全てを満たすアルゴリズムが存在する」

=> 不整合が生じる応答を返すような実行を構築することで矛盾を証明


ネットワークは最低でも二ノードで構成されていることを仮定

二つの互いに疎な非空の集合に分割: {G1, G2}
G1とG2の間の全てのメッセージは消失する


証明(ざっくり):

v0をアトミックオブジェクトの初期値とする
σ1を「G1でwrite操作が行われた」実行とする

=> 可用性の要求により、v0の値は上書きされる


σ2を「G2でread操作が行われた」実行とする

=> 可用性の要求により、v0の値が返される


σを「σ1とσ2を結合した」実行とする

=> 可用性およびアトミック性の要求により、read操作はG1に上書きされた値を返すべき
=> ただし、G2からはσ2とσの実行を区別できないので、実際にはv0が返る
=> アトミック性に違反している(矛盾があるので証明完了)


帰結1.1


非同期ネットワークモデルでは メッセージ消失が実際には発生しなかった場合でも、以下の性質を保証する読み書きデータオブジェクトを実装することは不可能

可用性
アトミック一貫性


! 若干元の論文から変更している(簡単のために)
証明


非同期モデルにおいては「メッセージ消失」と「転送チャンネルにおける任意の遅延」の区別は不可能
つまり「メッセージが消失しなかった実行ならCAを満たすアルゴリズム」が存在するなら、メッセージが消失した実行(i.e., 全ての実行)でも同様のアルゴリズムが存在することになり、それは定理1と矛盾する(ので存在し得ない)
!「分断が存在しないことが確実に分かっている」なら話しは別 (see: 3.2.2節)

3.2 非同期モデルにおける解決策

アトミック性、可用性、分断耐性の三つを同時に満たすことは無理だけど、任意の二つ、であれば可能。
3.2.1 アトミック、分断耐性


可用性が要求されないケース

アトミックデータと分断耐性を達成するのは容易
=> リクエストを全て無視する(無意味な)システムでも、要求は満たす


より強いliveness条件を提供することも可能

「もし実行内の全メッセージが配送されるなら、システムは可用性を持ち、かつ、全ての操作は終了する」


簡単な中央集権的なアルゴリズムは、この要求を満たす:

オブジェクト毎に、対応する単一の中央ノードが存在
ユーザからのリクエストは、そのノードに転送されて処理される


多くの分散データベースは、この種の保証を提供する:

特に分散ロックやクォーラムに基づくアルゴリズムでは
もし特定の故障パターンが生じた場合には、liveness条件は弱められて、サービスは応答を返せなくなる
もし失敗が存在しないなら、livenessは保証される


3.2.2 アトミック、可用性


もし分断が存在しないなら、アトミックかつ可用なデータの提供が可能なことは明白

3.2.1節の中央集権アルゴリズムも、この要求を満たす


イントラネットやLAN内で実行されるシステムは、この種のアルゴリズムの一例

3.2.3 可用性、分断耐性


アトミック一貫性が要求されないなら、高可用性と分断耐性を提供することは可能

もし一貫性要求がないなら、サービスは全てのリクエストに対して初期値を返すことが可能


可用性と分断耐性の構成のもとで、弱められた一貫性を提供することもできる

ウェブキャッシュはその一例
4.3節では、可能な弱い一貫性条件のいくつかを考察する


4 部分的同期ネットワーク

4.1 部分的同期モデル


定理1の不可能性の帰結を緩和を試みる最も自明な方法は、実世界では、大半のネットワークは純粋に非同期ではない、ということを認識すること
もし、ネットワーク内の各ノードが時計を持つことが許されるなら、よりパワフルなサービスを構築することが可能
この論文の残りでは、部分的同期モデルについて議論する:

全てのノードは時計を有する
全ての時計は、同じレートで増加する

時計自体は同期されておらず、同じ時間に異なる時刻を表示するかもしれない
=> タイマーとして利用可能


さらに、全てのメッセージは決まった時間(t.msg)以内に配送されるか、ないしは消失する、と仮定

受信メッセージの処理までに要する時間はt.local
処理自体には時間を要しない
=> タイムアウト、によってメッセージ消失が判定可能となる


4.2 不可能性の帰結

常にCAPを満たすことは、部分的同期モデルでも不可能。
定理2


部分同期ネットワークモデルで、以下の性質を保証する読み書きデータオブジェクトを実行することは不可能:

可用性
アトミック一貫性


証明


定理1の証明と似ているので省略
大事なのは「同期性を導入しても、分断への本質的な対応にはならない」ということ

同期性の導入により「メッセージ消失(or 特殊化すればノードダウン)」は判定可能になる
ただ、そもそもメッセージ(情報)が伝わらないのであれば、そこで正しい判断(アトミック性)を行うことはできない


4.3 部分的同期モデルにおける解決策

では「部分的同期モデルは、非同期モデルに比べて何が嬉しいのか？」といった話:

部分的同期モデルでは、帰結1.1のアナロジーは発生しない
帰結1.1の証明は「ノードがメッセージ消失に気づけない」ということに依存している

=> 部分的同期モデルでは、タイムアウトを用いることで消失が検出可能


以下のような部分的同期アルゴリズムがある:

全てのメッセージが配送（ie., 分断がない)されるなら、アトミックデータを返す
メッセージが消失した場合にだけ、不整合な(典型的には古い)データを返すだろう


3.2.1節の中央集権アルゴリズムは、その一例:

読み込みリクエストにおいて、あるメッセージが中央ノードに送られる (書き込みでもほぼ同様)
もし中央ノードからの応答が受信されたら、そのノードはリクエストされたデータを配送する
もし、応答が2 * t.msg + t.local以内に受信されないなら、ノードはそのメッセージが消失したと判断する
次に、クライアントに応答が送られる (一番最近に中央ノードから取得した値を返す)


このケースでは、アトミック一貫性が破られる可能性はある

4.4 より弱い一貫性条件

要約: 「タイマーを上手く使えば、分断が実際に発生していない実行ではアトミック性を保証し、分断が発生してアトミック性が一時的に崩れたとしても一定期間後に回復するようにすることが可能」

「全てのメッセージが配送される実行でアトミックデータを保証する」ことが有用なのと同様に「メッセージが消失するような実行で何が生じるか」を指定することも同様に重要である
この節では、一つの弱い一貫性条件について議論する:

分断がある場合に古いデータが返されることを許容する
返される古いデータの品質に関して形式的な要求が課される


この一貫性保証は、メッセージが消失しない場合には、可用性とアトミック一貫性を要求する

つまり、非同期モデルでは不可能（帰結1.1より)


この一貫性モデルは、メッセージが配送されるなら、アトミック性がいずれ復元されることを保証する
ここではアトミック性よりも弱い「Delayed-t一貫性」を定義する

アトミック性と似たような半順序を定義
ただし「全てのメッセージが配送されている期間の操作群に関して」だけ正しい半順序が維持されれば良い


定義3


読み書きオブジェクトを用いた、ある時間付きの実行σは、以下が成立するならDelayed-t一貫、といえる:

a. Pは半順序

i. 全ての書き込み操作を順序付ける
ii. 読み込み操作は、対応する書き込みを反映して順序付け


b. 全ての読み込みによって返される値は、P内の直前の書き込み操作によって書かれた値

i. 先行する書き込みがない場合には初期値


c. P内の順序は、各ノードでsubmitされた読み書きリクエストの順序と一貫している
d. (アトミック性) もし実行内の全てのメッセージが配送され、かつ、操作θが操作φが始まる前に完了したなら、φは半順序P内でθに先行しない
e. (弱い一貫性) tよりも長い、メッセージ消失が存在しない期間が存在すると仮定する。加えて、ある操作θがその期間が始まる前に完了し、別の操作φが、その期間が終わった後に終了したと仮定する。それなら、φは半順序P内でθに先行することはない。


この保証は、メッセージ消失時にあるstaleデータが存在することは許容するが、一度分断が回復すれば、その不整合が続く期間にタイムリミットを設けることができる。
これは、結果整合データのアイディアに関連している

しかしながら、私たちは、データが一貫性を持つまでにどれだけ掛かるか、の明示的な時間上限が欲しかった


4.3節の中央アルゴリズムの亜種としてDelayed-t一貫性を持つアルゴリズムができる。
Cを中央ノードと仮定し、アルゴリズムは以下のようになる:

ノードAでの読み込み:


Aは、最も最近の値に対するリクエストをCに送る


もしAがCから応答を受けたなら、それをクライアントに返す


もしAが(タイムアウトにより)メッセージが消失したと判断したら、もっとも最近のシーケンス番号の値 or 初期値、をクライアントに返す


ノードAでの書き込み:


Aは、Cに新しい値を送信する


もしAがackをCから受信したら、Aはackをクライアントに返し、停止する


もしAがタイムアウトによりメッセージが消失したと判断した場合、ackをクライアントに返す


まだ、AがCからackを受けとっていないなら、新しい値をCに送る（再送）


もしAがタイムアウトによりメッセージが消失したと判断したなら、Aはステップ4をt - 4*t.timeout秒以内に繰り返す


Cで新しい値が受信された:


Cは、そのシーケンス番号を1増加させる


Cは、全てのノードにその値とシーケンス番号を送る


もしCが(タイムアウトにより)メッセージが消失したと判断したなら、欠けたノードにt - 2*t.timeout秒以内に再送する


全てのノードからackを受け取るまで、ステップ3を繰り返す


! 要するに再送制御は入っているだけ
定理4

修正された中央集権的アルゴリズムはDelayed-t一貫性がある
証明


書き込み操作の順序は、中央ノードによって全順序化される

シーケンス番号が付く


各読み込み操作には、それが読んだ書き込み操作と同じシーケンス番号が付く（？）

というよりは、読んだ書き込み操作に従って並べられる(sequenced)、的な感じ？


全てのメッセージが配送されるなら、このアルゴリズムはアトミック

TODO: その理由 (まあ中央ノードがリクエストを受け取った順序に従って逐次化しているので…)


いくつかのメッセージが消失した場合は、結果の実行はアトミックではないかもしれない
それでも、弱い一貫性は満たされる:

ある書き込み操作がAwで生じた(開始した)と仮定する:

その後に、全てのメッセージが配送される期間(t)が経過
この期間の終わりに、Awは中央ノードにメッセージを配送している (再送ロジックにより)
かつ、中央ノードも他の全てのノードに新しい値を配送している（再送ロジックにより)
=> よって、この期間の後のいずれの操作も、このwrite操作に(P内で)先行することはない


ある読み込み操作がBrで発生(開始)したと仮定する:

その後に、全てのメッセージが配送される期間(t)が経過
Brは、以下のどちらかから値を受信している必要がある:

A) 中央ノードから
B) Brでのより早い書き込み操作から


Aのケースでは、Cは確実に、Brによって返された値よりも(等しいか or)新しい値を全てのノードが受信していることを確実にしている
Bのケースでは、その期間の終わりでは、BrがCに値を送信し、それをCが他の全てのノードに転送している


=> つまり、この期間の後にいずれの操作も、このread操作に(P内で)先行することは無い


5 結論


この論文では、ネットワーク内に分断が存在する場合には、確実にアトミックで一貫性のあるデータを提供することが不可能であることを示した

ただし"一貫性"、"可用性"、"分断耐性"の内の二つであれば、達成することは可能


非同期モデルでは、

時計が利用不可能なので、不可能性の帰結はかなり強い
メッセージ消失時に古いデータを返すことを許容した場合にでも、一貫性のあるデータを提供することが不可能


しかし部分的同期モデルでは、

一貫性と可用性の間で現実的な妥協を達成することが可能
特に、今日の大半の実世界システムは"大半の時間に大半のデータ"を返すように落ち着くことを強制されている


このアイディアを形式化し、それを達成するアルゴリズムを学ぶことは、将来の理論的な研究の興味深い対象である