j3259の日記： 分散システムにおける信頼性と総意（クォーラム・コンセンサス）

分散システムで一番かっこいいというか、分散っぽいのが quorum concensus じゃないかと思う。
例によって適当な訳語が見つからず、この分野を知る日本人が少ないのか全員原文を読んでるかのどっちかだと思う。
Quorum を辞書で引くと、

The minimal number of officers and members of a committee or organization, usually a majority, who must be present for valid transaction of business.

委員会や組織において有効な業務の執行に出席が必要とされる最小役員数、通常過半数。

英和辞書では

(議決に要する)定足数

Consensus は

An opinion or position reached by a group as a whole.

あるグループが全体として到達した意見または立場。

で、まこれは「総意」でいけなくもないけど、総意だと全会一致って雰囲気が強い。全会一致じゃないから多数決したり欠席の奴は無視したり頑張ってるわけだけど、ま、全体として到達した総意ってことで。

定足数総意よりもクォーラム・コンセンサスの方が言いやすいだろうし、分かりやすい。

----

まずは一歩下がって分散システム(distributed system)とは何か。
- 複数のプロセスが協調して何らかを行うこと
この場合のプロセスとはメモリで実行されてるプログラムという意味でのプロセス。
分散システムのメインテーマは（信頼性の低い）部品からいかに全体として信頼できるシステムを作れるかということ。

信頼性(reliability)とはなにか
- 耐故障性（フォルトトレランス fault-tolerance）
- 高/持続可用性(availability)
- パフォーマンス
- 回復性(recoverability)
- 一貫性(consistency)
- セキュリティ
- プライバシー

セキュリティの話はその分野で色々やってるので、とりあえず分散システムにおける「信頼性」からは省く。
かなり強引にまとめると、信頼性を回復性と可用性に絞って考えることができ、それぞれ
- 回復性(recoverability) - トランザクション
- 可用性(availability) - レプリケーション（複製処理）
にて実現される。他の項目は後からついて来るという事にする。

トランザクションの ACID 特性
- アトミック性(atomicity)
- 一貫性(consistency)
- 独立性(isolation) -- 履歴が直列化可能(serializable)である
- 永続性(durability)

回復性とは
- 干渉無しでもサーバがまともな状態で再起動できること
-- 連鎖ロールバック(cascade rollback)を避けるため strict 2 phase locking (2PL) を使う

可用性とは
- 部分が故障してもシステム全体として機能し続ける事
- 継続して機能し続けるために、重要なデータは複製する

トランザクションを使ったサーバの複製は大別して二つの方法がある
- レプリケーション（複製化）を特別な場合とみなす
-- プライマリサーバと"warm standby"状態なバックアップサーバ
-- 一般的な商用製品はこれ
-- (conflict) serializability
- 分散トランザクションを使って複数のサーバにデータを複製化する
-- "1-copy serializability" (1SR)

データが複数のサーバに存在して、さらにトランザクションを使う場合、つまり分散トランザクションをどうやるかという話になる。
ここで出てくるのが、2相コミット(2PC; 2 phase commit)など。
2PC は調整役が落ちると他の参加者がブロックするという弱点がある。で、ロックを掛けてブロックしてるわけだから、このリソースを誰かが読み込もうとした場合そいつもブロックされる。で、調整役が帰ってこないと参加者全員がブロックされたままという状態になる。

問題点
- 2PC をどうやって耐故障にするか
- 複製の一つが到達できない場合にオブジェクトをどうやって書き込みするか

複数のサーバにデータを複製化
- 良い点: 可用性、読み込み（read-only request）のパフォーマンス
- 悪い点: 書き込み時のパフォーマンスの悪化

----

「一レプリカ」直列可能性 (1SR; 1-copy serializability)
- 複製化された複数のデータアイテムに対して複数のクライアントから実行されたトランザクションの効果が一つのデータアイテムに対して直列して実行された場合と同じである事

トランザクションに対して故障と回復も直列化されなければいけない
- トランザクションT に認められる故障は T以前に起こったものでなければいけない
- レプリカにおいて回復したデータがあったとしても、トランザクション T が回復より先に起こった場合は T より到達不能でなければいけない

リードワン・ライトオール(ROWA; Read-One Write-All)
- 読み込みは一つのレプリカから行い、書き込みは全コピーに行う
- 1SR は満たしてるんだけど、全員に書き込んだらやっぱり遅い。あと全員につながらない状況でも使いたい。

利用可能レプリカ法(available copies)
- 読み込みは利用可能なレプリカのうちの一つから行い、書き込みは利用可能なレプリカの全コピーに行う
- 利用可能なレプリカが毎回変わるしネットワーク分割が起きるから 1SR を満たさない

ローカル確認付き利用可能レプリカ法(available copies with local validation)
- ネットワーク分割には対応できない

- 楽観的アプローチ
-- それぞれの分割ネットワークで書き込みを許す
-- 再び接続した時点で矛盾を解決する
-- もしオペレーションの衝突があった場合は一方をアボートする
-- バージョンベクトルを使って書き込みをバリデート
-- 先行グラフ(precedence graph)を使って read/write 衝突を検知

- 悲観的アプローチ: サイト・クォーラム
-- 分割ネットワークでの書き込みを制限する
-- 別々の分割ネットワークで矛盾するトランザクションが実行されるのを防ぐ

単純に過半数を使った場合、矛盾することがある
- x のレプリカ {x_A, x_B, x_C } がある
- T_1 からは A と B のみが利用可能
- T_2 からは B と C のみが利用可能

T_1: r1[x_A] -> w1[x_A] -> w1[x_B] -> c1 （r1 は読み込み、w1 は書き込み、c1 はコミット）
T_2: r2[x_C] -> w2[x_B] -> w2[x_C] -> c2

クォーラム・コンセンサス
- 複製されたオブジェクト各々に書き込み定足数(Q_w; update quorum) と読み込み定足数(Q_r; read quorum)がある。

Q_w + Q_r > (レプリカの数)
かつ Q_w + Q_w > (レプリカの数)

を満たさなければいけない。
簡単に言うと、書き込みクォーラムは過半数以上。読み込みクォーラムは「全レプリカ数 - 書き込みクォーラム + 1」ということになる。

クォーラムの例
- x が {A, B, C, D, E} に複製されてるとする
- 可能な値は？
-- Q_w = 1, Q_r = 5 （Q_w + Q_w ＞ 5 を満たしてない）
-- Q_w = 2, Q_r = 4 （同様）
-- Q_w = 3, Q_r = 3
-- Q_w = 4, Q_r = 2
-- Q_w = 5, Q_r = 1 （可用性の違反）
- おそらく Q_w = 4, Q_r = 2 が良いだろう。
-- 普通は読み込みの方が頻繁に起こるから読み込みクォーラムが低い方が速い
-- Q_w = 5 は ROWA（リードワン・ライトオール）で、一つでもレプリカが落ちたら書き込みが止まる事になる。よって可用性「部分が故障してもシステム全体として機能し続ける事」を違反する事になる。

クォーラムの有効性
- クォーラムの読み込みは過去の書き込みクォーラムと少なくとも一つのプロセスと交差する必要がある
- 同様に、クォーラムの書き込みは他のクォーラム書き込みと交差する必要がある
よって、グループのサイズが N の場合

Q_r + Q_w > N かつ
Q_w + Q_w > N が必要となる

複製されるデータのバージョン
- 複製されるデータアイテムはバージョン付けされてる必要がある
- つまり、単に "X_p = 3" ということはできない
-- X_p は [7, q] というタイムスタンプを持つ。タイムスタンプは単純増加し、引き分けを解決するためにプロセス番号を持つ。
-- X_p は 3 という値を持つ

データの読み込み
- Q_r個のプロセスが応答するまで RPCを送信する
- タイムスタンプが最大の値を使う。
-- まずタイムスタンプ項で比べる
-- 引き分けになった場合はプロセス番号で比べる
- プロセス自身がレプリカを持っていたとしても信用にならない（他でデータが書き込まれてるかもしれないから）

データの書き込みは面倒
- インクリメンタル書き込みはサポートできない(x = x + 1)
-- 誰も自分のレプリカを信用できないため
- 書き込みを始める際、定足数分に書き込めるか分からない
-- コミットプロトコルを使う必要がある
- バージョン番号の決定に投票を使う
1. 「x := 3」を書き込みたいと提案する
2. メンバーは変数に読み込みロックを掛け、要求を書き込み申請キューに入れ（ディスクなど耐クラッシュ性あるもの）、
「了解。現在の時刻を [t, pid]と提案する」と返信する。
この時間は論理時間。pid はメンバー自身のプロセス番号。
3. 元の提案者はQ_w に達することを願いつつ返事を集める
4. （Q_w 以上）提案された [t, pid] の最大値を計算し、その時刻でコミットする
4. （Q_w 未満）中止

書き込みはどこにあるのか？
- 各メンバーが申請中で未コミットの書き込みキューを持つ
-- クラッシュして再起動しても覚えてる
自分が提案した論理時刻と書き込みをリクエストしてきたクライアントは直後にキューに書いておく。
まだコミットされてない場合は、別のクライアントから読み込み要求が来ても古い値を返さなくてはならない。