全ての三台集合を列挙する
この実験では五台A〜Eから三台を選ぶ集合を全て作り、読取り集合と書込み集合の全組を検査します。N=5、R=3、W=3です。前提はクォーラムのガイドです。実ネットワークを起動せず、固定メンバーの集合と保存済みの版を扱う決定的なPython模型です。故障したRaftクラスタを動かした証跡ではありません。最初に検査する性質を集合の交差へ限定し、応答の順序や値の選択へ進むところで、別の規則が必要なことを確認します。
五台から三台の選び方は10通りで、読書きの組は100通りです。それぞれの共通部分が空でなく、最小の台数が1になることをassertします。どの集合が選ばれても交差するという計算と、ある一例でCが共通だったという確認を区別できます。Nを変える拡張では、RとWが実際に選べる件数かも確認してください。空の組を生成してallが真だったという結果を、存在しないクォーラムの安全性と読まないことが重要です。
停止して残った台数と分断を分ける
コードをquorum.pyへ保存し、Python 3.12以降でpython quorum.pyとして実行します。標準ライブラリだけを使います。全台、ABCの三台、ABの二台が使える場合を並べ、R台・W台の条件を満たせるかを表示します。ABCなら両方可能、ABならどちらも不足です。この出力は通信の状態を実際に測ったのではなく、到達できる集合を入力として置いた結果です。ノードが生きていても呼出し元から届かなければ、その呼出しの集合には使えません。
三対二の分断では、ABCの側は三台を選べますが、DEの側は選べません。少数側が独自に更新してよいという規則は、この模型には入れていません。代替ノードを入れる場合は、固定メンバーという前提を変えるので別の検査が必要です。乱数やsleepは使わず、同じ入力が同じ結果になります。起動や片付けの必要なサーバーもありません。これにより集合の計算だけを再現し、実プロセスの停止の影響と混ぜずに学べます。
保存の不足と選択の誤りを別に作る
最初の版の例ではnewをB、Cだけに置き、A、D、Eはoldのままにします。A、D、Eの読取りは書込みの予定集合ABCとAで交わりますが、版2の耐久な三台確認を満たしていません。したがって古い値が返っても、正しくW=3で確定した更新の保証を破った反例ではありません。保存したつもりの台と、本当にその版を確認した台を区別するための故意の違反です。コード中のコメントもその前提を示しています。
次にAもnewへ変え、A、B、Cの三台へ版2がある状態を作ります。読取り順をD、A、Eとすると、最大の版はnewですが、最初のDはoldです。今度は保存の三台条件を満たし、収集した版を選ばない実装が古い値を返す反例になります。二つの状態を同じ「クォーラムが失敗した」でまとめず、どの前提を外したかを説明します。tupleの比較はこの単純な版番号の模型で、並行書込みの全てを順序付ける実装ではありません。
from itertools import combinations
nodes=set('ABCDE');R=W=3
reads=[set(x) for x in combinations(sorted(nodes),R)]
writes=[set(x) for x in combinations(sorted(nodes),W)]
assert all(r&w for r in reads for w in writes)
assert min(len(r&w) for r in reads for w in writes)==1
for alive in [set('ABCDE'),set('ABC'),set('AB')]:
can_read=len(alive)>=R;can_write=len(alive)>=W
print('alive',''.join(sorted(alive)),'read',can_read,'write',can_write)
assert len(set('ABC'))>=W and len(set('DE'))<W
versions={'A':(1,'old'),'B':(2,'new'),'C':(2,'new'),'D':(1,'old'),'E':(1,'old')}
write_set=set('ABC');read_order=['A','D','E']
assert set(read_order)&write_set=={'A'}
first=versions[read_order[0]]
newest=max(versions[n] for n in read_order)
assert first==newest==(1,'old')
print('intersection exists, but write of version 2 was acknowledged by B,C only')
# This deliberately violates durable W=3 acknowledgment for version 2.
# A second counterexample keeps W=3 but chooses the first returned stale value.
versions['A']=(2,'new');read_order=['D','A','E']
assert max(versions[n] for n in read_order)==(2,'new')
assert versions[read_order[0]]==(1,'old')
print('durable W=3, read quorum intersects; first response is still old')
assertした性質を結果へ対応させる
正常なら全台と三台でreadとwriteがTrue、二台でFalseとなり、二つの版の反例の説明が表示されます。交差と最小台数は全組合せでassertし、版の選択も具体的な値で比較します。掲載コードはこの入力で正常終了しています。実行時間やネットワーク遅延の測定はありません。集合が交差したという事実を、各ノードが再起動後も値を保持したという証拠へ読み替えないでください。辞書に入れた状態は入力であり、永続化の実験ではありません。
式R+W>Nが通っているかだけでなく、どのノードがどの版を返したかを出力の横へ書くと、二つの反例を追いやすくなります。Aの状態を変えた行が、保存の前提を回復する点です。読取り順を変えた行が、最初の応答と最大版を分ける点です。実装へ移す場合には、全応答をいつまで集めるか、失敗した書込みの版をどう扱うか、版の割当てと修復を追加で設計します。模型の短さでその責務が消えたとは考えません。
反例の変更点を一つずつ保存する
最初の反例を直すにはAへnewを置き、実際の版2の保持を三台へ増やします。この変更だけでは、Dの最初の応答を返す誤りは直りません。次に全応答の比較へ変えると、この単一更新の模型ではnewが見つかります。保存と選択という二つの条件を一度に直して結果だけ見ると、どちらが必要だったかを説明しにくくなります。前後の辞書と読取り順を別に残します。
Rを2へ変えたときの交差失敗も、保存の不足とは別です。DEだけを読む集合には、ABCへ全て保存していてもnewがない反例を作れます。集合、版の保持、応答の収集、返す値を四段で検査します。並行書込み、ノード再起動、設定変更がないこの模型では、それらの追加の安全性は未検証です。小さい模型でどの前提を外すとどのassertが失敗するかを理解すると、本物の履歴を調べるときの問いを具体化できます。
失敗したassertの理由も入力の前提へ戻して説明します。
Rを二つへ変える課題
課題はR=2、W=3へ変えて、交差しない組を探すことです。解答は書込みABCと読取りDEです。元のallのassertは失敗し、その失敗は新しい設定が元の交差保証を満たさないことを正しく示します。結果に合わせてassertを削除するのでなく、条件の違いを記録し、保証を変える設計かを判断します。次にW=5、R=1なら交差は保ちますが、一台に届かないと書込みが進まないことを台数の検査で確認できます。
追加課題は、最初のoldを返す代わりに全応答の最大版を使えば線形化可能性が証明できたかです。解答は、この一書込みの反例は直せても、全ての並行履歴や故障した書込み、メンバー変更を検査していないので証明にはならない、です。検査した範囲を具体的に説明してください。終了後に削除するDBや止めるプロセスはありません。模型から実装へ進むときは、入力で仮定した状態をどう現実に確かめるかを次の問いにします。