CAP の availability 模擬

通信が切れた瞬間、どちらかを諦めることになる

同じデータを 3 台のサーバーに置いて、1 台が壊れても続けられるようにしておきます。ここまでは誰も反対しません。厄介なのは、サーバーが壊れるのではなく、サーバー同士をつなぐ回線が切れるときです。

東京の 2 台と大阪の 1 台がつながらなくなったとします。東京側で値を v2 に更新しても、大阪には届きません。

この状態で、大阪のサーバーに読みに来た人がいます。返せるものは 2 つしかありません。

• 手元にある v1 を返す。応答は返るが、その値は古い
• 「今は答えられない」とエラーを返す。古い値は出さないが、そのユーザーにとってサービスは止まっている

どちらを選んでも何かを失います。前者は正しさ（Consistency）を、後者は答えを返し続けること（Availability）を諦めています。回線が切れている間は、両方は取れません。CAP 定理が言っているのはこれで、覚えるべきは 3 文字の名前ではなく、この二択が必ず来るという事実のほうです。

解説

現場の話 — 銀行の残高は後者を選びます。古い残高を見せるくらいならエラー画面を出して止めます。SNS のいいね数は前者です。少し古い数字が見えても誰も困らないので、止めるほうが損だと判断されています。いいね数が一瞬戻って見えるのは、この設計の副作用です。

何台が同じことを言えば信じるか

答えを返すほうを選んだシステムでも、たまたま聞いた 1 台の言い分をそのまま信じるわけではありません。全台に聞きに行って、過半数が同じ値を答えたらそれを採用します。多数決なので quorum read と呼ばれます。

5 台のうち 3 台が v2、1 台が v1、1 台は落ちていて答えない、という状況なら v2 を採ります。1 台落ちていても答えが出せるので、止まらずに済みます。

ここでの過半数は「半分」ではなく「半分より多い」です。台数ごとに書くと次のようになります。

• 3 台なら 2 票
• 4 台なら 3 票
• 5 台なら 3 票

台数を 2 で割って切り捨て、1 を足すとこの数が出ます。半分ちょうどで合意にしてしまうと、4 台が 2 票と 2 票に割れたときに両方とも合意扱いになり、どちらを返すかがその場の順番で決まってしまいます。

割れたときは、答えないという答えを返す

a が 2 票、b が 2 票。どちらも過半数に届いていません。ここで無理に多いほうを選ぶと、たまたま同点だった値を「全員が合意した値」として配ることになります。届かなかったのなら、合意なしとして返すのが正しい振る舞いです。

課題では、答えないノードを空文字で表します。票の集計には入れません。ただし、過半数を計算するときの台数は、落ちている台も含めた全体のままにします。落ちている台が増えるほど合意が成立しにくくなる、という関係をそのまま再現するためです。

やってみよう

quorumRead(replicas) を完成させてください。

1. 空文字は集計から外す。過半数の計算に使う台数は replicas の長さのまま
2. 残った値ごとに票数を数える
3. 過半数に届いた値があればそれを返す。無ければ空文字を返す

票を数える部分は、第 4 章でやった出現回数の数え上げと同じ形です。新しく覚えることはありません。

1. 空文字（dead node）は集計から除外する
2. 過半数は len // 2 + 1 で計算する
3. 過半数を取った値があれば返し、なければ空文字を返す