CAP の availability 模擬
CAP の availability 模擬
このレッスンで分かること
- 複数のサーバー（ノード）にまたがって動く分散データベースを設計するとき、必ずぶつかる壁があります
- CAP 定理が言っているのは、「3 つすべてを完全には満たせない
- 図のポイント (テキスト併記)
CAP の availability 模擬 とは
CAP 定理の Availability（可用性）を、複数ノード上の最新値を多数決で返す関数として実装します。
複数のサーバー（ノード）にまたがって動く分散データベースを設計するとき、必ずぶつかる壁があります。それが CAP 定理 です。CAP は次の 3 つの英単語の頭文字を取っています。
- C =
Consistency（強整合性）どのノードに読みに行っても、必ず最新の値が返る - A =
Availability（可用性）一部のノードが落ちても、システムは応答を返し続ける - P =
Partition tolerance（分断耐性）ネットワークが分断されても動き続ける
CAP 定理が言っているのは、「3 つすべてを完全には満たせない。ネットワーク分断（P）が起きたとき、C と A のどちらかを諦めるしかない」 ということです。
図のポイント (テキスト併記)
-
一般的な銀行系の DB は
CP寄り、Cassandra や DynamoDB などのクラウドストレージはAP寄りで設計されている
一般的な銀行系の DB は
CP寄り、Cassandra や DynamoDB などのクラウドストレージはAP寄りで設計されている。
Availability を模した「多数決リード」
今回の課題では、複数ノードに保存された値から 「過半数（quorum）のノードが同意した値」を返す 処理を実装します。これは AP システムでよく使われる quorum read の単純化版です。
例えば 5 ノードある DB が次のように値を保持しているとします。
| node | value |
|---|---|
| n1 | "v2" |
| n2 | "v2" |
| n3 | "v1" |
| n4 | "v2" |
| n5 | ""（ダウン中） |
5 ノード中、v2 が 3 票、v1 が 1 票、空文字（ダウン中）が 1 票。過半数（3 票以上）を取った v2 が「合意された値」として返ります。1 ノードが落ちていても答えを返せるので Availability が確保されている わけです。
Python
def quorumRead(replicas):
counts = {}
for v in replicas:
if not v:
continue
counts[v] = counts.get(v, 0) + 1
total = len(replicas)
quorum = total // 2 + 1 # 過半数
for v, c in counts.items():
if c >= quorum:
return v
return "" # 合意なしは空文字を返す過半数（majority）は
len // 2 + 1。5 なら 3、3 なら 2、4 なら 3。
コードでの考え方
入力は replicas: list[str]。空文字 "" は 「ダウン中ノード」 とみなして集計から外します。出力は 過半数を取った値、または合意できなければ空文字 ""。
JavaScript
function quorumRead(replicas) {
const counts = {};
for (const v of replicas) {
if (!v) continue;
counts[v] = (counts[v] || 0) + 1;
}
const quorum = Math.floor(replicas.length / 2) + 1;
for (const [v, c] of Object.entries(counts)) {
if (c >= quorum) return v;
}
return "";
}ダウン中ノードを表すのに
nullを使いたいところだが、今回は言語横断で動かしやすい空文字""で代用する。
よくある間違い
過半数の計算を len / 2 （ちょうど半分）にすると、5 ノード中 2 票でも合意とみなしてしまう バグが起きます。半分より多い を意味する len // 2 + 1 を使いましょう。
また、最初に過半数を超えた値で return しない と、複数の値が両方とも閾値を超えたとき（実際は起きないが）の振る舞いが曖昧になります。1 つ見つけたら即 return が安全です。
CAP の現実 — eventual consistency
AP システムは、Network partition の最中は一時的に値が割れることを許容します。やがてノード間でレプリケーションが終わると全ノードが同じ値に揃う、これを eventual consistency（結果整合性） と呼びます。SNS の「いいね数が一瞬古く見える」「分散キャッシュが少し遅れて反映される」のはこの仕組みです。
「即時に正確」を取るか「常に応答が返る」を取るか — 設計者の宿題は永遠に終わらない。
やってみよう
replicas 配列を入力に、過半数を取った値（または空文字 ""）を返す quorumRead を実装してください。空文字は集計から除外する、過半数は len // 2 + 1 という 2 点に注意。
よくある質問
Q. このトピックを覚える意味は何ですか？
A. 分散 DB や NoSQL を選定するとき、DynamoDB・Cassandra・MongoDB など各サービスが「CP 寄り」「AP 寄り」のどちらで設計されているかを判断する土台になります。マイクロサービス間でデータを共有する設計や、レプリケーションの遅延を許容するかどうかの議論でも、CAP 定理の理解は不可欠です。
Q. 実務でこの知識を使う場面は？
A. API の Content-Length 計算、ファイルアップロードのサイズ制限、画像処理での色深度計算など、低レベルな数値を扱う場面で頻出します。OS・ネットワーク・暗号の理解にも繋がるため、CS の共通言語と思って習得しておくと一生使える知識です。
Q. 他の章とどう繋がりますか？
A. 後続の章で扱うデータ構造（スタック・キュー）、アルゴリズム（探索・ソート）の基礎になります。CAP 定理で「整合性と可用性のトレードオフ」を掴んでおくと、後続の疎結合・密結合やトランザクション処理（ACID）でなぜ設計上の制約が生まれるのかが腹落ちしやすくなります。分散環境における整合性の難しさを先に体感することで、ACID がなぜ重要なのかも理解が深まります。
次のレッスン
次は URL ルーティング で、MVC アーキテクチャにおける URL と Controller の対応付け（ルーティング）の仕組みを実装しながら学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- CAP 定理 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. CAP 定理 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン**
要件
- 空文字（dead node）は集計から除外する
- 過半数は
len // 2 + 1で計算する - 過半数を取った値があれば返し、なければ空文字を返す
入出力例
test-cases.txt
quorumRead(["v2","v2","v1","v2",""]) → "v2"
quorumRead(["v1","v2","v3"]) → ""
quorumRead(["v1","",""]) → ""
quorumRead(["v1","v1","v1"]) → "v1"
quorumRead(["a","a","b","b"]) → ""
quorumRead(["x","x","x","",""]) → "x"