本文へスキップ

キーバリューストアのシステム設計:パーティショニング、レプリケーション、クォーラム

ハッシュリング、レプリケーション、R + W > N のクォーラム、競合解決、hinted handoff、gossip、LSM まで、Dynamo 型のストアを設計します。

· 創業者・開発者

公開日:

A から F までの 6 台のサーバーがリング上にあり、キー k は A の直前にハッシュされます。カートサービスが A に put(k, ctx, v) を送り、A は B(ack)と C(停止中)に複製します。破線の hinted write は D に届き、D が後で C に渡します。パネルには N = 3、W = 2、R = 2 と LSM の書き込みパスを示します。

カートサービスはクリックのたびに書き込みを行い、12 月には 1 件のカート追加も拒否できません。ピーク中にはディスクが故障し、ラックスイッチが不安定になり、データセンターがネットワークから切り離されることもあります。単一のプライマリデータベースでは、そのどれもが障害につながります。

2007 年の Amazon の Dynamo 論文は、こうした状況でも書き込みを受け付け続けるストアを説明しました。Cassandra と Riak KV は、そのクラスタリングの考え方の多くを取り入れています。この記事では Dynamo 型のストアを API からストレージエンジンまで設計し、実在のシステムを比較して、結果を図にします。

要件と API

Dynamo のインターフェースは 2 つの操作です。

get(key)                 -> [value, ...], context
put(key, context, value) -> ok

get は、競合するバージョンと不透明なコンテキストを返すことがあります。次の put はそのコンテキストを返送し、どのバージョンを置き換えるかを伝えます。要件は次のとおりです。

  • 常に書き込み可能であること。ノードやリンクが停止していても書き込めます。
  • 予測可能なテールレイテンシ。 論文の SLA の例は、ピーク時 1 秒あたり 500 リクエストで、リクエストの 99.9% を 300 ms 以内に処理することです。
  • 小さな値と単一キー。オブジェクトは通常 1 MB 未満で、複数キーにまたがる操作はありません。
  • 段階的なスケール。ノードを 1 台ずつ増やします。

容量の見積もりは、値を 1 KB、コンパクションの余裕としてディスクを半分使用と仮定します。10 億キーは 1 TB、3 コピーで 3 TB になるため、図のリングと同じく 1 TB のノードが 6 台必要です。1 秒あたり 30,000 回の書き込みなら、3 コピーでレプリカへの書き込みは 90,000 回、1 ノードあたり 15,000 回です。

CAP と PACELC の要点

CAP は、ネットワーク分断中にストアが一部のリクエストを拒否するか、古い読み取りを許容する必要があると述べます。Dynamo は可用性を保ちます。Daniel Abadi の PACELC(2012 年)は、分断がないときでもレイテンシと一貫性のトレードオフがあると補足し、Dynamo、Cassandra、Riak のデフォルト設定を PA/EL に分類しています。

ハッシュリングと仮想ノードによるパーティショニング

Dynamo は各キーを MD5 でリング上の 128 ビットの位置にハッシュし、キーは時計回りで最初のノードに属します。ノードが参加または離脱しても、hash(key) % N のようにほぼ全キーが動くのではなく、隣接する範囲だけが移動します。仕組みは Consistent Hashing の図で確認できます。

ノードごとに位置が 1 つだとデータが偏るため、各ノードは仮想ノード(トークン)と呼ばれる多数の位置を持ちます。Cassandra 5.0 はノードあたり 16 トークンが標準で、Riak のリングはデフォルトで 64 パーティションです。範囲スキャンは使えなくなります。隣り合うキーが別のノードに置かれるためで、データベースシャーディングの図で説明しています。

レプリケーションとプリファレンスリスト

各キーは N 個のノードに置かれます。コーディネーター(時計回りで最初のノード)と、続く N − 1 個の異なる物理ノードです。キーのプリファレンスリストはそれより先まで続き、レプリカが停止したときの代役がいます。レプリカは障害ドメインにまたがって配置します。Dynamo は各リストをデータセンターにまたがって配置し、Cassandra の NetworkTopologyStrategy はラックにまたがって配置します。データベースレプリケーションの図のリーダー型構成と違い、すべてのレプリカが書き込みを受け付けます。

クォーラム:R + W > N

コーディネーターは各書き込みを N 個すべてのレプリカに送り、W 個の確認応答の後で返答します。読み取りは R 個の応答の後で返答します。R + W > N なら、どの読み取り集合と確認済みのどの書き込み集合も、少なくとも 1 つのノードを共有します。

N, R, W R + W > N 得られるもの 支払うもの
3, 2, 2 はい 読み取りが確認済みの最新の書き込みを見られる。レプリカ 1 台の障害に耐える 各リクエストが 2 番目に速い応答を待つ
3, 1, 3 はい どのレプリカからでも高速に読み取れる 書き込みが 3 台すべてを待つ
3, 1, 1 いいえ 最小のレイテンシと最高の可用性 読み取りが古くなる場合がある
5, 3, 3 はい レプリカ 2 台の障害に耐える 各値のコピーが 5 つ必要

Dynamo 論文で一般的だった構成は (3, 2, 2) で、商品カタログのような読み取りが多いサービスは R = 1、W = N を使いました。Cassandra はリクエストごとに ONE から ALL までの整合性レベルを設定します。読み取りと書き込みの両方に QUORUM を使うと R + W > N になります。

重なりがあっても線形化可能性は得られません。1 つのレプリカに届いてから失敗した書き込みは、ある読み取りには現れ、次の読み取りでは消えることがあります。Cassandra のデフォルトのブロッキング read repair は、クォーラム読み取りでこれを防ぎます。Compare-and-set には合意が必要で、Cassandra の軽量トランザクションや Raft ベースのストアがその例です。

競合:Last Write Wins、Vector Clock、CRDT

異なるレプリカを通じた同時書き込みは、2 つのバージョンを残します。解決策は 3 つあります。

戦略 解決方法 更新が失われるか 使用例
Last Write Wins 最も新しいタイムスタンプが勝つ はい、気づかれずに失われる。クロックのずれが勝者を決める Cassandra、DynamoDB グローバルテーブル、設定時の Riak
Vector Clock 同時のバージョンを保持し、クライアントがマージする いいえ。ただしすべてのクライアントがマージする必要がある Dynamo、Riak(dotted version vector)
CRDT マージが必ず収束するデータ型 いいえ(対応する型の場合) Riak のカウンター、セット、マップ

Vector Clock は (ノード, カウンター) のペアのリストです。すべてのカウンターが別のバージョン以下であるバージョンは祖先であり、破棄できます。そうでなければ両方を保持します。カートサービスは競合するカートをマージしたため、追加した商品は失われませんでしたが、削除した商品が復活することはありました。競合はまれで、24 時間のうち 99.94% のカートリクエストが見たバージョンは 1 つだけでした。CRDT はマージをデータ型そのものに任せます。CRDT ベースの共同編集エディターは、同じ考え方を共有テキストに適用しています。

障害処理:hinted handoff、repair、gossip

Sloppy quorum と hinted handoff。 Dynamo は、プリファレンスリストの先頭から健全な N 個のノードを使います。C が停止していれば、D がヒント付きで C のコピーを預かり、C の復旧時に返します。書き込みは動き続けますが、B と復旧した C から読み取ると、A と D だけが確認した書き込みを見逃すことがあります。Cassandra はクォーラムを厳密に保ちます。ヒントが整合性レベルに数えられるのは ANY のときだけで、ノードが 3 時間停止すると打ち切られます(max_hint_window)。

Read repair と anti-entropy。 応答が食い違うと、コーディネーターは最新のバージョンを古いレプリカに書き戻します。コールドデータでは、レプリカがキー範囲ごとに Merkle ツリーを比較し、差のある範囲だけを同期します。Cassandra のドキュメントは、すべてのノードで少なくとも 7 日ごとに nodetool repair を実行するよう推奨しています。tombstone は gc_grace_seconds(デフォルトは 10 日)の後に削除されるため、repair されていないレプリカは削除済みのデータを復活させることがあります。

Gossip と障害検知。 各ノードは毎秒、ランダムなピアとメンバーシップとトークンの状態を交換します。全ノードが知っているシードノードが、リングの分裂を防ぎます。Cassandra の phi accrual 検出器は、疑いの値が phi_convict_threshold(デフォルトは 8)を超えるとピアを停止と判定します。

書き込みパス:commit log、memtable、SSTable

Cassandra のストレージエンジンは、書き込みに最適化された log-structured merge(LSM)ツリーです。

  1. 書き込みを commit log に追記します。デフォルト(periodic)では、Cassandra はすぐに確認応答を返し、10 秒ごとに同期するため、クラッシュするとその間の書き込みが失われることがあります。
  2. メモリ上のソート済み構造である memtable に挿入します。
  3. いっぱいになった memtable を、ディスク上の不変でソート済みの SSTable にフラッシュします。
  4. バックグラウンドで SSTable をコンパクションし、最新のバージョンを残して期限切れの tombstone を破棄します。

読み取りは memtable、次に SSTable を調べ、SSTable ごとの Bloom filter がキーを含み得ないファイルを飛ばします。キーあたり 10 ビット、ハッシュ関数 7 個の場合、偽陽性率は (1 − e^(−0.7))^7 で、約 0.8% です。Size-tiered compaction がデフォルトで、Cassandra 5.0 は新しいワークロードに unified 戦略を推奨しています。

実在のシステムと論文の比較

Dynamo (2007) Amazon DynamoDB Cassandra 5.0 Riak KV
パーティショニング MD5 リング、均等なパーティション サイズやトラフィックで分割される範囲 Murmur3 リング、ノードあたり 16 トークン 160 ビットリング、64 パーティション
レプリケーション リーダーなし、キーあたり N 個 AZ にまたがる 3 レプリカ、Multi-Paxos リーダー リーダーなし、データセンターごと リーダーなし、n_val 3
一貫性 Sloppy quorum デフォルトは結果整合性。強い読み取りはリーダーから リクエストごとの整合性レベル Sloppy quorum、pr と pw
競合 Vector Clock リーダーが書き込みを順序付け。リージョン間は last writer wins Last Write Wins Sibling または CRDT
ストレージ Berkeley DB、MySQL B-tree と write-ahead log LSM ツリー Bitcask、LevelDB

DynamoDB は名前を共有していますが、設計は異なります。2022 年の USENIX 論文によると、パーティションリーダーは 3 レプリカのうち 2 つがログに書き込んだ時点で確認応答を返します。グローバルテーブルはリージョン間でデフォルトが last writer wins ですが、執筆時点(2026 年 11 月)では、ちょうど 3 リージョンでマルチリージョンの強い一貫性も提供しています。

Dynamo 型キーバリューストアの図

A から F までの 6 台のサーバーがリング上にあり、キー k は A の直前にハッシュされます。カートサービスが A に put(k, ctx, v) を送り、A は B(ack)と C(停止中)に複製します。破線の hinted write は D に届き、D が後で C に渡します。パネルには N = 3、W = 2、R = 2 と LSM の書き込みパスを示します。

21 個のコンポーネント · 8 個の接続

Archboard で開く
ダイアグラムの内容
  • Node B
  • Node A
  • Node C
  • Node F
  • Node D
  • Node E
  • Cart service
  • Inside every node: LSM write path
  • Commit log
  • Memtable
  • SSTables
  • put(k, ctx, v)
  • replica 2: ack
  • replica 3: no reply
  • hinted write for C: ack
  • hand off when C recovers
  • then insert
  • flush when full
  • gossip
キー k は 6 ノードのリング上の 1 点にハッシュされます。Node A が put を調整して B と C に複製します。C は停止中のため、D がヒント付きコピーを保持し、後で返します。サイドパネルには N、R、W と各ノード内の書き込みパスを示します。

図の読み方は次のとおりです。

  • リング。 点で示した hash(k) から時計回りにたどると、A から F までのプリファレンスリストになります。
  • 書き込み。 カートサービスが put(k, ctx, v) をコーディネーター A に送り、A が B と C に複製します。
  • 障害。 C が停止しているため、D がヒント付きで C のコピーを預かり(破線の琥珀色)、後で返します。W = 2 なので、A と B に書き込まれた時点で put が返ります。
  • Gossip(点線)は、ランダムなノードのペアの間で行われます。
  • パネルには N、R、W と各ノードの書き込みパスを示します。

キーバリューストアの図を分かりやすく描く

  • 1 つのキーを追う。 そのハッシュに印を付け、プリファレンスリストを書き出し、横に N、R、W を置きます。キーのないリングは何も説明しません。
  • 障害を描く。 赤いノードと破線のフォールバックエッジは、sloppy quorum を文章より速く説明します。
  • 障害ドメインを示す。 レプリカをラックやゾーンで色分けし、同じドメインに 2 つのコピーがないことをレビュアーが確認できるようにします。
  • ノードの内部は 1 つのインセットにまとめる。 クラスターが先です。

よくある間違いは、クライアントから全レプリカへの矢印だけでコーディネーターがないことです。書き込みの成功を誰が判断するのかが隠れてしまいます。レイアウトと数値については、ステップごとのシステム設計の進め方を参照してください。

Archboard で作る

  1. Google または GitHub でサインインし、ダイアグラムを作成します。
  2. トークンリング用に、基本パックから大きなグレーの楕円を追加します。
  3. ネットワークパックのサーバーノード 6 個をリング上に時計回りで Node A から Node F まで配置します。A と B を緑、C を赤、D を琥珀色にし、役割を基本のテキストノートでラベル付けします。
  4. リング上の Node A の直前に、hash(k) 用の小さな楕円を追加し、テキストラベルを付けます。
  5. カートサービス用に、C4 モデルパックのコンテナを追加し、Node A への put(k, ctx, v) エッジを引きます。
  6. エッジを描きます。A から B は緑の実線、A から C は十字の矢じりの赤い破線、A から D と D から C は琥珀色の破線(hinted write、次に handoff)、F と E の間は点線の gossip エッジで、テキストノートを付けます。
  7. 基本パックから、N、R、W とシナリオを書いた Markdown ブロックを追加します。
  8. 基本パックのフレームを追加し、C4 モデルパックのコンポーネントノード 3 個(Commit log、Memtable、SSTables)を上から下へつなぎ、Bloom filter 用のテキストノートを付けます。

この例で使うダイアグラムノードは 14 個で、Free プランの範囲に収まります。

よくある質問

分散キーバリューストアはどう設計しますか? Consistent Hashing でパーティション分割し、各キーを N 個のノードに複製し、R と W を調整し、競合戦略を選び、hinted handoff と anti-entropy repair を加え、ノードごとに LSM ツリーを動かします。

R + W > N とは何を意味しますか? N 個のレプリカのうち、書き込みは W 個を、読み取りは R 個を待ちます。R + W が N を超えると、すべての読み取りが確認済みの最新の書き込みを持つレプリカに少なくとも 1 つ届きます。

DynamoDB は Dynamo 論文に基づいていますか? 一部だけです。各パーティションは 3 レプリカと Multi-Paxos リーダー、B-tree ストレージを持ち、sloppy quorum や Vector Clock は使いません。

Hinted handoff とは何ですか? 到達できないレプリカの書き込みを別のノードがヒント付きで保存し、レプリカが戻ったときに届ける仕組みです。Cassandra はデフォルトで、ノードが 3 時間停止するとそのノードへのヒント保存をやめます。

Last Write Wins と Vector Clock のどちらを使うべきですか? Last Write Wins は、セッションのように同時更新の損失が許容できるデータに向いています。カートやカウンターのようにすべての更新が重要な場合は、Vector Clock か CRDT を使います。

無料で始める — 1 シート、クレジットカード不要。

関連記事

← ブログに戻る

1分でキャンバスを開く

Google または GitHub でサインイン。1シートは無料で、チームが加わったらアップグレード。