分散KVストアの設計

要件と規模の見積もり

まず解くべき問題を定義します。対象は get(key) / put(key, value) の2操作だけを持つ分散KVストアです。値は不透明なバイト列（数KB程度、例として1KB上限）とし、範囲スキャンや二次インデックス、トランザクションは要求に含めません。この割り切りが後段の設計自由度を生みます。

非機能要件こそが本質です。(1) 高可用性を最優先し、書き込みは常に受け付けたい（"always writeable"）。(2) 単一障害点を作らない。(3) ノード追加で線形にスケールする。(4) レイテンシは読み書きともp99で数十ms以内。可用性を最優先する以上、CAP定理の下では分断時に強一貫性を諦め結果整合性を選ぶ、というのが最初の大きな判断です（CAP定理）。

規模をフェルミ推定で桁感だけ掴みます。1億ユーザーが1日平均50回書き込む前提だと、書き込みは 1e8 * 50 / 86400 ≒ 5.8万 QPS、読み書き比を10:1とすれば読み取りは約58万QPS、合計で約64万QPS。1レコードをキー・値・メタで平均1.5KBとし、保存件数が5000億件なら生データは 5e11 * 1.5KB = 750TB。レプリケーション係数 N=3 と将来ぶんの余裕を見て実効ストレージは約2.5〜3PB。帯域はピーク書き込みで 5.8万 * 3(複製) * 1.5KB ≒ 260MB/s、レプリカ間トラフィックを含めても数GB/s帯に収まる、という桁感です。

大枠の設計

APIは薄く保ちます。put はコンテキスト（後述のバージョン情報）を任意で受け取り、get はバージョンと値の組を返す形にします。

get(key)            -> (value, context)      # context にバージョン（ベクタークロック）を同梱
put(key, value, context)                     # 更新時は直前 get の context を渡す

全体構成は「調整役（coordinator）＋対称なノード群」です。中央のマスターを置くとそこが単一障害点になるため、全ノードが同格で、どのノードもリクエストの受け口（coordinator）になれる構成を採ります。リクエストは任意のノードに届き、そのノードがキーの担当ノード群へ転送・集約します。

キーの配置先は一貫性ハッシュで決めます（一貫性ハッシュ、シャーディング戦略）。hash(key) をリング（0〜2^m-1の環）上の点に写像し、そこから時計回りに最初に出会うノードが第1担当、続くN-1台が複製先です。素朴なハッシュ分割（hash(key) mod ノード数）だとノード数変化でほぼ全キーが再配置されますが、一貫性ハッシュならノード追加・削除の影響は平均して 1/ノード数 のキー範囲に限定されます。

素朴な一貫性ハッシュはノードがリング上で偏ると担当量が不均等になります。そこで各物理ノードを多数の仮想ノード（トークン）としてリング上へばら撒き、負荷を平準化します。仮想ノード数を性能に比例させれば、異なる性能のマシンを混ぜても公平に負荷分配できます。

主要コンポーネントの深掘り

レプリケーションとクォーラム（W+R>N）

各キーはリング上の担当ノード群（preference list）へN重に複製します。読み書きの強さはクォーラムで調整します。書き込みはW台からの成功応答を待ち、読み取りはR台から集めます。ここで W+R>N を満たすと、任意の読み取りクォーラムと直近の書き込みクォーラムが必ず1台以上重なり、最新値を含むレプリカを最低1つは読めることが保証されます（鳩の巣原理）。

Wを小さくすると書き込み可用性が上がる代わりに耐久性が下がり、Rとの和が N 以下なら重なりが消えて古い値を読む窓が開きます。この綱引きをアプリ要件でチューニングできるのがクォーラム型の強みです。強一貫性が要る系はPaxos/Raftなどの合意で単一の順序を作りますが、可用性最優先の本設計はあえてそれを避けます（合意アルゴリズム、レプリケーションとシャーディング）。

結果整合性とベクタークロック

W+R>N でも、ネットワーク分断中に別々のレプリカへ並行書き込みが入ると、同一キーに複数の版が生まれます。どちらが新しいかを実時刻で決めると時計ずれで更新を取りこぼすため、ベクタークロック（[ノード, カウンタ] の並び）で因果関係を追跡します。あるバージョンAの各カウンタがBの対応値すべて以下ならAはBの祖先で安全に破棄でき、どちらも他方を包含しなければ並行（衝突）と判定します。衝突版は捨てずに保持し、次の get で複数版をクライアントへ返して意味論に沿った統合（例: ショッピングカートの和集合）を促します。

# 例: ベクタークロックによる因果判定
v1 = [(A,2),(B,1)]      # ノードA,Bでの更新回数
v2 = [(A,2),(B,2)]      # v1 の各成分 <= v2 → v1 は v2 の祖先（v2 を採用）
v3 = [(A,3),(B,1)]      # v2 と v3 は互いに包含せず → 並行（衝突。両版を保持）

障害時の書き込み: ヒンテッドハンドオフ

担当ノードが一時的に落ちても書き込みを止めないために、ヒンテッドハンドオフを使います。本来の担当が不在なら、代替ノードが「これは本来Xのデータ」というヒント付きで一時的に受理し、Xの復帰を検知したら手渡して自分からは消します。これで一時障害中も"always writeable"を保てます。恒久的なノード離脱に伴うレプリカ修復にはマークルツリーで差分だけ同期する手法を併用します。

読み取り時の修復: read repair

読み取りでR台を照合したとき版がずれていれば、read repairで最新版を古いレプリカへ書き戻し、遅延収束させます。読み取り経路に相乗りするため追加コストが小さく、よく読まれるキーほど速く整合します。

メンバーシップ: ゴシップ

「今どのノードが生きていて、リング上のどのトークンを持つか」を中央管理者なしで共有するために、ゴシッププロトコルを使います。各ノードは定期的にランダムな相手とメンバーシップ表とトークン割り当てを交換し、状態は指数的に全体へ伝播します。障害検知も同様にゴシップで広め、一時的な無応答を恒久離脱と誤認しないよう注意深く扱います。中央レジストリを置かないことで、そこが単一障害点になるのを避けます。

ローカル保存: LSMツリー

各ノードのディスク保存はLSMツリーを採用します。書き込みをまずWALとメモリ上のMemTableへ追記し、満杯になったらソート済みSSTableとして順次書き出す構造で、ランダム書き込みを高速なシーケンシャル書き込みに変換します。書き込み主体のKVワークロードと相性が良く、存在しないキーの探索はブルームフィルタで無駄読みを削れます（LSMツリー、ブルームフィルタ、WAL）。

ボトルネックとトレードオフ

横にスクロール

最大のトレードオフは強一貫性を捨てたことそのものです。可用性と分断耐性を取った結果、アプリは「複数版が返る」「一時的に古い値が見える」前提でロジックを書く必要が生じます。この負担を許容できない、たとえば残高のように取り違えが致命的なデータでは、Paxos/Raftベースの強一貫ストアを選ぶべきで、KVストアという同じ看板でも設計は根本から変わります。

もう一つは運用の複雑さです。仮想ノード数・N/W/R・ゴシップ間隔・コンパクション戦略と、つまみが多く相互に影響します。強力に調整できる反面、既定値のまま運用すると偏りや増幅で足をすくわれます。クライアント側でリング情報を持てば調整役ホップを省いてレイテンシを削れますが、クライアントとサーバーの結合が強まりデプロイの独立性が下がる、というのもよくある綱引きです。

関連する基盤技術はデータベース、負荷分散やルーティングはネットワーク、配信の到達保証はメッセージキューの配信保証も参照してください。