誰が新しいリーダーか
分散合意とは、一部の機械が壊れたり、通信が遅れたりしても、複数の機械が1つのリーダーや1つの値に同意することです。機械どうしが、全員に聞こえる会議室を持っていないからこそ、決め方が必要になります。
プライマリが応答しなくなったとき、2台が「自分が新しいプライマリだ」と言い出したら、どうなるでしょうか。
このレッスンのゴール
メモ
機械どうしが多数決でリーダーや値を決める仕組みを説明できます。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 合意 | 複数の機械が、同じ1つの答えを選ぶこと | |
| 過半数 | 全体の半分を超える数 | |
| クォーラム | 決めるのに必要な、最小の台数 | 5台なら3台 |
| リーダー選出 | 仕事をまとめる機械を、1台だけ選ぶこと | |
| 任期 | リーダーの代が変わるたびに増える番号 | |
| スプリットブレイン | 2台以上が、同時に自分がリーダーだと思う状態 |
学生が入力するセルは、このプレビューでは空白です。
多数決なら、二つのグループは同時に決められない
過半数は、全体の半分を超える数です。5台なら3台、4台なら3台です。決めるのに必要な台数をクォーラムと呼びます。
5台が3台と2台に分かれても、決められるのは3台のグループだけです。2つの過半数には必ず重なる機械があるので、二つのグループが別々の答えを決めることはありません。
例: 台数ごとの過半数
| 全体の台数 | 過半数 | 止まってよい台数 |
|---|---|---|
| 3台 | 2台 | 1台 |
| 4台 | 3台 | 1台 |
| 5台 | 3台 | 2台 |
| 6台 | 4台 | 2台 |
| 7台 | 4台 | 3台 |
学生が入力するセルは、このプレビューでは空白です。
過半数を台数ごとに数える
# 台数ごとの過半数と、止まってよい台数を表にします。
for n in [3, 4, 5, 6, 7]:
need = n // 2 + 1
print(n, "台のとき、過半数は", need, "台。止まってよいのは", n - need, "台")
# [3, 4, 5, 6, 7] に 9 を足して、もう一度実行してみましょう。
5台の過半数を計算する
echo $((5 / 2 + 1))ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
6台の過半数を計算する
echo $((6 / 2 + 1))ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
リーダーは、過半数の票で選ぶ
リーダー選出では、リーダーを待つノードが、自分を候補にして票を集めます。各ノードは、1つの任期に、1票しか投じません。
過半数の票を得た候補が、新しいリーダーです。票が割れて誰も届かなければ、任期を1つ進めて、もう一度選びます。古い任期のリーダーが戻っても、新しい任期の言うことを聞きます。
例: 5台の選挙
| ノード | 投票先 | 結果 |
|---|---|---|
| n1 | n1 | n1に1票 |
| n2 | n1 | n1に2票 |
| n3 | n3 | n3に1票 |
| n4 | n1 | n1に3票。過半数に届いた |
| n5 | 連絡がつかない | 票なし |
学生が入力するセルは、このプレビューでは空白です。
票を数える
# 5台のノードが、1票ずつ投じました。None は、連絡がつかなかったノードです。
votes = ["n1", "n1", "n3", "n1", None]
counts = {}
for vote in votes:
if vote is not None:
if vote in counts:
counts[vote] = counts[vote] + 1
else:
counts[vote] = 1
print(counts)
print("必要な票:", len(votes) // 2 + 1)
# 3つ目の "n3" を "n1" に変えると、どうなるでしょうか。
書く台数と読む台数は、重なる必要がある
値を書くときに w 台、読むときに r 台へ尋ねるとします。全体が n 台のとき、w と r を足して n を超えれば、読む台数の中に、必ず最新の値を持つ機械が1台は含まれます。
足して n 以下なら、読んだ機械が全部古い、ということが起こり得ます。
例: 3台の書く台数と読む台数
| 書く台数 | 読む台数 | 合計 | 必ず重なるか |
|---|---|---|---|
| 2台 | 2台 | 4 | 重なる |
| 1台 | 1台 | 2 | 重ならない |
| 3台 | 1台 | 4 | 重なる（書き込みが遅い） |
| 1台 | 3台 | 4 | 重なる（読み取りが遅い） |
学生が入力するセルは、このプレビューでは空白です。
小さなクライアント v を作る
v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
2台の確認を、0.1秒待つ
v WAIT 2 100ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
半数に届けば決まると考えがちです。ちょうど半数では、6台が3台と3台に分かれたとき、二つのグループが別々の答えを決めてしまいます。過半数は、半分を超える数です。