分散キーバリューストアって何？ ─ 整合性・可用性・障害対応の設計を学ぶ！

キーバリューストアの設計

概要

この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。

本記事では、多くの分散システムの基盤となるキーバリューストアの設計について解説します。

本記事で扱うインターフェースは get と put の2つと非常にシンプルですが、これを大規模・高可用な分散システムとして設計しようとすると、データ分散・レプリケーション・整合性・障害対応など多くの論点が現れます。本記事ではそれらを順に整理していきます。

キーバリューストアとは

キーバリューストア（key-value store）とは、一意のキーに値を紐付けて格納する非リレーショナルなデータベースである。中心となる操作は値の保存と取得だが、実際の製品では削除・有効期限（TTL）・アトミックなインクリメント・範囲スキャンなど、より多くの操作を備えるものも多い。

キーは短い文字列やそのハッシュ値であることが多く、値はテキスト・JSON・画像などの任意のデータを取り得る。代表的なキーバリューストアには以下がある。

システム	特徴
Amazon Dynamo	高可用性を重視した分散キーバリューストア。本記事の設計の下敷き
Apache Cassandra	Dynamoの設計を継承したワイドカラムストア
Redis / Memcached	インメモリで高速。キャッシュ用途で広く利用される

設計の要件

本記事では、Alex Xu の設計演習にならい、次の2操作を提供するキーバリューストアを設計する。

• put(key, value): キーに対応する値を保存する
• get(key): キーに対応する値を取得する

また、すべての性質を同時に最大化することはできないため、以下の目標・前提のもとでトレードオフを取る。

• 大規模データの格納: 巨大なデータ量を格納できる
• 高可用性: 障害時でも素早く応答する
• 高スケーラビリティ: サーバー追加で負荷をさばける
• 自動スケーリング: トラフィックに応じてサーバーが自動増減する
• 調整可能な一貫性（tunable consistency）: 要件に応じて一貫性の強さを選べる
• 低レイテンシ: 読み書きが高速である
• 値のサイズは小さい（10KB未満）とする

単一サーバーのキーバリューストア

まずは1台のサーバーで考える。最も単純な実装は、キーと値のハッシュテーブルをメモリ上に保持する方法である。メモリアクセスなので高速だが、すべてのデータをメモリに載せるのは容量的に困難である。

同一サーバー内でも、次の最適化で格納できるデータ量を増やせる。

• データの圧縮を行う
• 頻繁にアクセスされるデータのみメモリに置き、残りはディスクに格納する

しかし、これらを尽くしても1台のサーバーの容量・処理能力には限界がある。大規模データと高可用性を実現するには、複数サーバーへの分散が必要になる。

CAP定理

分散システムを設計するうえで避けて通れないのがCAP定理である。CAP定理は、分散システムが以下の3つの保証を同時にすべて満たすことはできず、最大2つまでしか満たせないことを示す。

保証	意味
一貫性（Consistency）	どのノードにアクセスしても、常に同じ最新のデータが読める
可用性（Availability）	一部ノードが障害でも、リクエストに必ず応答が返る
分断耐性（Partition Tolerance）	ノード間の通信が分断されても、システムが動作し続ける

現実のネットワークでは通信障害（ネットワーク分断）は避けられないため、分断耐性（P）は事実上必須である。したがって実質的には、分断が起きたときに一貫性（C）と可用性（A）のどちらを優先するかの選択になる。

分類	優先する性質	振る舞い（分断発生時）
CPシステム	一貫性	最新でないデータを返すくらいなら、応答を拒否する（例: 銀行取引）
APシステム	可用性	たとえ古いデータでも応答を返し、整合性は後で解決する

例えば3ノード（n1, n2, n3）でn3が分断された場合を考える。

• CPを選ぶ: n1・n2への書き込みをブロックし、一貫性を守る（可用性は犠牲）
• APを選ぶ: n1・n2で書き込みを受け付け続け、n3の復帰後にデータを同期する（一貫性は一時的に犠牲）

本記事で設計するキーバリューストア（Dynamo型）は、可用性を重視するAPシステムを前提に、後述の仕組みで結果整合性（eventual consistency）を担保する。

分散キーバリューストアのコンポーネント

分散キーバリューストアは、以下のコンポーネントを組み合わせて構築する。ここから順に見ていく。

• データパーティション
• データレプリケーション
• 一貫性（Quorum合意）
• 非一貫性の解決（バージョニング）
• 障害の処理（検知・一時的障害・恒久的障害）

データのパーティショニングとレプリケーションではコンシステントハッシュを前提とします。仕組みの詳細は、前回の記事「コンシステントハッシュって何？ ─ 分散システムのデータ分散を支える仕組みを学ぶ！」を参照してください（同シリーズ）。

データパーティション

大規模データを1台に収めることはできないため、データを分割して複数サーバーに分散配置する。このとき課題になるのが「①データを均等に分散する」「②ノード追加・削除時の移動を最小化する」の2点であり、これを解決するのがコンシステントハッシュである。

コンシステントハッシュを使うと、次の利点が得られる。

• 自動スケーリング（automatic scaling）: サーバーの追加・削除時に再配置されるキーが平均 K/N 個で済むため、負荷に応じてサーバーを自動で追加・削除しやすい
• サーバー性能差への対応（heterogeneity）: サーバーのスペックに応じて仮想ノード数を調整できる

データレプリケーション

高可用性と耐久性のため、各データをN台のサーバーに複製（レプリケーション）する。コンシステントハッシュのリング上で、キーの位置から時計回りに最初のN個のノードにそのデータのコピーを配置する。

下図はN=3の例で、key の位置から時計回りに最初の3ノード（A・B・C）がそれぞれレプリカを保持する。

このとき注意点が2つある。

• 仮想ノードを使う場合、時計回りに進む中ですでに選んだ物理サーバーの仮想ノードはスキップし、N台の異なる物理サーバーが揃うまで選ぶ（同じ物理サーバーに複数のレプリカが乗るのを防ぐため）
• 信頼性を高めるため、レプリカは別々のデータセンターに配置し、高速な専用線で接続することが望ましい

一貫性（Quorum合意）

複数のレプリカに分散したため、読み書きの一貫性を揃える仕組みが必要になる。ここで用いるのがQuorum合意（quorum consensus）である。以下の記号を定義する。

• N: レプリカの数
• W: 書き込みQuorum。書き込みが成功と見なされるには、W台のレプリカから確認応答が必要
• R: 読み込みQuorum。読み込みが成功と見なされるには、R台のレプリカから応答が必要

なお、W と R は 1 ≤ W ≤ N、1 ≤ R ≤ N の範囲の値をとる。書き込み・読み込みとも最低1台のレプリカに関与する必要があり（0台では保存も取得もできない）、レプリカ数 N を超える台数は要求できないためである。

WとRの値を調整することで、レイテンシと一貫性のトレードオフを制御できる。

設定	効果
W = 1	1台の応答で書き込み完了。書き込みが高速だが一貫性は弱い
R = 1	1台の応答で読み込み完了。読み込みが高速だが一貫性は弱い
W + R > N	読み込みと書き込みのレプリカ集合が必ず重なり、強い一貫性が保証される
W + R <= N	強い一貫性は保証されない（結果整合性）

書き込みと読み込みの調整役として、コーディネーター（coordinator）がクライアントとノードの間に立ち、Quorumの条件（W台・R台の応答）を満たすまでレプリカと通信する。以下、N=3, W=2, R=2（W+R=4 > 3）を例に、書き込みと読み込みの流れを見る。

書き込みでは、コーディネーターは全レプリカ（r1・r2・r3）へ書き込みを送り、W=2台の確認応答（ack）が揃った時点でクライアントに成功を返す（残りの応答は待たない）。

この時点で確実に新しい値を持つのは、ack を返した r1・r2 の2台である（r3 にも書き込みは送られるが、反映済みとは限らない）。続く読み込みでは、コーディネーターはR=2台の応答が揃うまで待つ。レプリカは N 台しかないため、書き込み集合 {r1, r2} と読み込む2台は完全には分けられず、必ず1台以上重なる（鳩の巣原理）。つまり、たとえ r3 が古くても、どの2台を読んでも最新値を持つレプリカが必ず含まれる。

読み込む2台	最新値を含むか
r1, r2	✅ 両方が最新
r1, r3	✅ r1 が最新
r2, r3	✅ r2 が最新

読み込み側は、得られた応答のうちバージョンが最新のもの（バージョン番号やベクタークロックで判定）を採用すればよいので、古い値を読まずに済む。これが W + R > N で強い一貫性が保証される仕組みである。逆に W + R <= N だと、書き込み集合と読み込む集合が重ならないケースが生じ、古い値を読みうる。

一貫性モデル

レプリカが複数あると、書き込みが全レプリカへ伝わるまでにタイムラグが生じ、その間はレプリカ間でデータが食い違う。この「書き込みの結果がいつ・どの順序で読み手に見えるか」についてシステムが与える保証の取り決めを一貫性モデル（consistency model）という。保証を強くするほど古いデータを読みにくくなるが、その分レイテンシや可用性を犠牲にしやすいというトレードオフがある。前述の N・W・R の設定は、このうちどの一貫性モデルを実現するかを左右する。

代表的な一貫性モデルは次の通りで、Dynamo型のシステムでは結果整合性（eventual consistency）が選ばれることが多い。

一貫性モデル	説明
強い一貫性	常に最新の書き込み結果が読める。古いデータは返さない
弱い一貫性	最新の書き込みが読めるとは限らない
結果整合性	弱い一貫性の一種。更新はやがて全レプリカへ伝搬するため、新しい書き込みが止まれば十分な時間の後にすべて一致する

非一貫性の解決：バージョニングとベクタークロック

APシステムでは、同じキーに対して別々のレプリカでほぼ同時に書き込みが起きることがある。このとき単純に「タイムスタンプが新しい方を採用」すると、本当は両方が有効な更新だった場合に片方が黙って失われてしまう（更新の消失）。そこで、2つのバージョンが「どちらが新しいのか」なのか「並行して作られた別物（競合）なのか」を正しく見分ける仕組みが要る。それがバージョニングとベクタークロック（vector clock）である。

バージョニングは、更新のたびに上書きせず新しいバージョンを作る考え方である（gitのコミットのように、履歴が枝分かれしうる）。

ベクタークロックは、各バージョンに「どのサーバーが何回更新したか」を記録した印で、[サーバー:更新回数] の組の集合で表す。更新のたびに担当サーバーのカウンタを1増やす。これを比べれば、バージョン同士の**親子関係（どちらが後か）**が分かる。

次のバージョン履歴を例に見る。

• D1 → D2（順番に更新／競合なし）: 同じ Sx で2回更新すると D1（[Sx:1]）→ D2（[Sx:2]）となる。D1 の全カウンタは D2 以下（Sx:1 ≤ Sx:2）なので、D1 は D2 の祖先＝D2 が新しいとすぐ分かり、D2 を採用すればよい。
• D3 と D4（別サーバーで同時に更新／競合）: D2 を起点に、Sy で更新すると D3（[Sx:2, Sy:1]）、Sz で更新すると D4（[Sx:2, Sz:1]）ができる。D3 は Sy の更新を、D4 は Sz の更新を互いに相手が持たないため、どちらも相手の祖先ではない → 並行に作られた＝競合。自動では決められないので、クライアントが両者をマージして解決する（gitのコンフリクト解決と同じ発想）。

判定ルールをまとめると次のようになる。

• バージョン X の全カウンタが Y の対応カウンタ以下 → X は Y の祖先（Y が新しい、競合なし）
• 互いに相手より大きいカウンタを持つ → 競合（クライアントがマージ）

ベクタークロックのデメリットもある。

• 競合の解決ロジックをクライアント側で実装する必要がある
• [サーバー:更新回数] のペアが増え続けうる。実際には上限（閾値）を設けて古いペアを切り詰めることで対処する

障害の処理

大規模分散システムでは障害は日常的に発生する。ここでは「障害の検知」「一時的障害への対応」「恒久的障害への対応」を扱う。

障害検知（ゴシッププロトコル）

1台が「あのノードは落ちている」と判断しただけでは不十分で、通常は2台以上が同意して初めて障害と見なす。全ノードに問い合わせるマルチキャスト方式は台数が増えると非効率なため、ゴシッププロトコル（gossip protocol）を使う。

• 各ノードはメンバーシップリスト（各ノードIDとハートビートカウンタ）を保持する
• 各ノードは定期的に自身のハートビートカウンタを+1し、各メンバーのカウンタを含むメンバーシップリストを、ランダムに選んだ数ノードへ送る
• 受け取ったノードは、メンバーごとにより新しいカウンタでリストをマージする。これにより、直接やり取りしていないノードの生死も伝わる（推移的な伝搬）
• あるノードのカウンタが一定時間増えていないと気づいたノードは、それをゴシップで他ノードへ伝える。複数のノードが同様に確認して初めて「ダウン」と確定し、その情報を全体へ伝搬する

例えば、s0 が保持するメンバーシップリストが次の状態で、s2 のカウンタだけ長く増えていないとする。

ノード	ハートビートカウンタ	状態
s0	128	正常
s1	97	正常
s2	50	長く増えていない（疑い）
s3	110	正常

s0 はこの「s2 が怪しい」という情報をゴシップで広め、s1・s3 も同じく s2 の停止を確認して初めて s2 は「ダウン」と確定し、その情報が全体へ伝搬する。

一時的障害の処理（Sloppy Quorumとヒント付きハンドオフ）

厳密なQuorumを守ろうとすると、一部ノードの障害で読み書きができなくなり可用性が下がる。これを緩和するのがSloppy Quorum（緩いQuorum）である。

• 障害ノードを無視し、リング上で最初に見つかったW台（書き込み）・R台（読み込み）の健全なノードで処理する
• ダウンしたノード宛ての書き込みは、別の健全なノードが肩代わりして受け取り、そのデータを「本来の担当ノード」を示すヒント（hint）付きで一時的に保持する
• 元のノードが復帰すると、肩代わりしたノードはデータを引き渡し（ヒント付きハンドオフ、hinted handoff）、自分の一時コピーを破棄する

これにより、一時的なノード障害があっても書き込み・読み込みを継続できる。

恒久的障害の処理（アンチエントロピーとマークル木）

ノードの恒久的な故障や、障害中に届かなかった書き込みなどで、同じデータを持つはずのレプリカ同士の中身がズレることがある。これを検出して揃え直す作業がアンチエントロピー（anti-entropy）である。ただし、レプリカ間で全データを1件ずつ突き合わせるのは転送量が大きく非効率なため、マークル木（Merkle tree）を使って食い違う部分だけを少ない通信で特定する。

マークル木は、次のように作るハッシュの木である。

• データ（キー範囲）を複数のバケットに分ける
• 各バケットの中身をハッシュ化して葉とする
• 隣り合う子ノードのハッシュ値を連結してハッシュ化し、親ノードとする（元データではなくハッシュ同士を束ねる。これを繰り返す）
• 最上位のルートハッシュが、全データを1つに要約した値になる

下図は、2つのレプリカ（A・B）がそれぞれ作ったマークル木を並べたもので、B3 のバケットだけが食い違っている場合に、ハッシュがずれる経路（ルート→右の枝→B3）を赤で示している。

比較は上から順に、対応するノードのハッシュを突き合わせる（赤＝食い違う、色なし＝一致）。

1. まず両レプリカのルートハッシュを比較 → 食い違う（赤）。「どこかが違う」と分かるが、位置はまだ不明
2. 子を比較 → 左 ハッシュ(B1,B2) は一致するのでその下は辿らない。右 ハッシュ(B3,B4) が食い違うので下る
3. さらに子を比較 → B3 が食い違うと判明 → B3 のバケットだけを同期する

もし手順1でルートハッシュが一致していれば、その1回の比較だけで「全データ同一・同期不要」と分かる。全データを突き合わせず、木の高さ（O(log n)）ぶんのハッシュ比較と、実際に違うバケットの転送だけで済むため、同期コストを大幅に削減できる。

データセンター障害への対応

停電・災害・ネットワーク断などでデータセンターごと失われることもある。これに備え、データは複数のデータセンターにレプリケーションしておく。一方のデータセンターが落ちても、別のデータセンターから読み書きを継続できる。

システムアーキテクチャ ─ 全体設計の統合

ここまでに見たコンポーネントをすべて組み合わせると、最終的なアーキテクチャは以下のようになる。特徴は、すべてのノードが対等（decentralized）で、どのノードもコーディネーターになれる点である。

このアーキテクチャは、次のような特徴を持つ。

• 中央のマスターを持たない: 全ノードが同じ機能を備え、対等に振る舞う。特定のノードに依存しないため、単一障害点がない
• どのノードもコーディネーターになれる: クライアントの get / put は、それを受けた1ノードがコーディネーターとして裁く。担当はリクエストごとに変わりうる
• データ配置は自動的に決まる: コンシステントハッシュにより、どのキーをどのノードが持つかが一意に定まり、中央の割り当て役を必要としない
• データは複数ノードに複製される: 各データはリング上の N ノードにレプリケーションされ、一部のノードが落ちても別のノードから読み書きできる（可用性・耐久性の土台）
• 一貫性と障害対応は各ノードの協調で保たれる: Quorum合意による読み書き、障害検知（ゴシップ）・復旧（ハンドオフ・アンチエントロピー）を、ノード同士が対等にやり取りして実現する

書き込みパス

1台のノードが書き込みを受け取ったとき、内部では次のように処理する（Cassandra等のLSMツリー方式）。

• コミットログへの追記により、クラッシュ時もデータを復元できる
• 書き込みはまずメモリ（memtable）に反映され高速
• memtableが一定サイズを超えると、ソート済みのSSTableとしてディスクに書き出される

読み込みパス

読み込みでは、まずメモリを見て、なければディスクのSSTableを探す。

SSTableが多数あるとき、どのSSTableにキーが含まれるかを線形に探すのは遅い。そこでブルームフィルタ（Bloom filter）を使い、「このSSTableにキーが含まれない」ことを高速に判定して探索範囲を絞り込む。

ブルームフィルタとは：ある要素が集合に含まれるかを、少ないメモリで高速に判定するデータ構造。「含まれない」という判定は必ず正しく、「含まれるかもしれない」という判定はまれに外れる（偽陽性はあるが偽陰性はない）。この性質により、「確実に含まれない」SSTableを読まずにスキップできる。

まとめ

キーバリューストアの設計で登場した「機能」と「対応する技術」を整理する。

実現したいこと	用いる技術
大規模データの格納	コンシステントハッシュによるパーティション
高可用性	レプリケーションとQuorum合意（N/W/R）
並行更新の競合解決	バージョニングとベクタークロック
一時的なノード障害への耐性	Sloppy Quorumとヒント付きハンドオフ
恒久的障害時のレプリカ同期	アンチエントロピーとマークル木
ノード障害の検知	ゴシッププロトコル
データセンター障害への備え	複数データセンターへのレプリケーション

• CAP定理: 分断耐性は必須のため、実質的にCP（一貫性優先）かAP（可用性優先）かを選ぶ。本設計は可用性を重視したAP型
• 調整可能な一貫性: N・W・Rの値で一貫性とレイテンシのトレードオフを制御し、W + R > N なら強い一貫性が得られる
• 結果整合性: 並行更新はベクタークロックで検知し、競合はクライアント側で解決する
• 障害への多層的な対応: 検知（ゴシップ）・一時対応（ハンドオフ）・恒久対応（マークル木）を組み合わせる

参考文献

この記事は以下の情報を参考にして執筆しました。

• 「システム設計の面接試験」（Alex Xu 著 / インプレス）