Dynamo：常に書き込めることを選んだ分散KVS

この論文が解いた問題

横にスクロール

2000年代半ばのAmazonは、世界規模のECサイトを支えるために極端な要求と向き合っていた。数千台規模のサーバーを常時動かせば、どこかのノードは必ず壊れ、ネットワークは分断し、ディスクは故障する。障害は例外ではなく日常だ。それでも、ユーザーが商品をカートに入れる操作や注文の確定は、一瞬たりとも失敗させたくない。カートに入れられない数分は、そのまま売り上げの損失になるからだ。

従来の分散データベースは、複数のレプリカ間で強い一貫性を保とうとする。全レプリカが同じ値に揃うまで書き込みを確定しない方式では、一部のノードが落ちたりネットワークが割れたりした瞬間に、書き込みそのものが止まってしまう。整合性を守るために可用性を犠牲にする。この割り切りは、Amazonの求める体験と真っ向からぶつかっていた。

DeCandiaらが2007年に発表したDynamoは、この対立に対して明確な立場を取った。「常に書き込めること」を最優先し、そのために一貫性の側を緩める。ネットワークが分断されても、各ノードは手元で書き込みを受け付け、整合性はあとから揃えればよい。この考え方が結果整合性（eventual consistency）だ。

分散システムでは、一貫性（Consistency）と可用性（Availability）は、ネットワーク分断（Partition）のもとで同時には満たせない。これを整理したのがCAP定理であり、Dynamoは迷わず可用性の側を選んだ設計の代表例として知られる。強整合を捨てる代わりに、いつでも応答する巨大なキーバリューストアを作る。それがDynamoの出発点だった。

核心アイデア

Dynamoの設計は、いくつかの独立した技術を組み合わせて成り立っている。それぞれが「可用性を落とさない」という一点に向けて選ばれている。

結果整合性という割り切り

Dynamoは、書き込みを受け付けた時点では全レプリカの一致を保証しない。ある瞬間には、レプリカごとに違う値が見えることを許す。しかし更新が伝播すれば、いずれ全レプリカは同じ値へ収束する。この「いずれ揃う」という約束が結果整合性だ。強整合のように常に最新を返す保証はないが、その代わりに、障害のもとでも書き込みと読み取りを止めない。

コンシステントハッシュによる分散

データをどのノードに置くかは、コンシステントハッシュで決める。キーをハッシュして巨大な円環（リング）上の一点に対応させ、その点から時計回りに最初に現れるノードが担当になる。単純なハッシュ剰余と違い、ノードが1台増減しても、影響を受けるのは隣接する範囲だけだ。全データの再配置は起きず、増設や故障の波及を局所に抑えられる。実際にはリング上に仮想ノードを多数配置し、負荷の偏りをならす工夫も取り入れている。

N/R/Wクォーラム

各データはN台のノードに複製される。読み取りはR台、書き込みはW台からの応答が揃えば成功とみなす。このN・R・Wを調整することで、可用性と整合性のバランスを運用側が選べる。RとWの和がNを上回るように設定すれば、読みの集合と書きの集合が必ず重なり、最新の書き込みを読める可能性が高まる。逆にWを小さくすれば書き込みは落ちにくくなり、Rを小さくすれば読み取りが速くなる。

ベクタークロックによる衝突管理

書き込みを止めないと決めた以上、同じキーへの更新が複数のレプリカで並行して起きうる。どちらが新しいのかを機械的に決められない衝突が発生する。Dynamoはこれをベクタークロックで扱う。各更新にノードごとのカウンタの組を付け、バージョン間の前後関係を判定する。片方がもう片方を包含していれば古い方を捨てられるが、包含関係がなければ「並行して起きた衝突」として両方を保持する。

論理的な前後関係を時計で表す発想は、ランポートの論理時計を拡張したものだ。そしてDynamoの割り切りは、衝突の最終的な解決をストア側で決めきらず、アプリケーション側に委ねてよいとした点にある。

障害からの復旧

ノードの一時的な不調には、ヒンテッドハンドオフで対応する。本来の担当ノードが落ちている間、別のノードが「本来は誰宛てか」のヒント付きでデータを預かり、担当が復帰したら渡し直す。書き込みはその間も止まらない。

一方、ノードが恒久的に失われ、レプリカ間に食い違いが積み重なった場合は、Merkleツリーで差分を検出する。データ範囲をハッシュの木構造にまとめ、木の頂点から突き合わせれば、食い違う枝だけをたどって差分を絞り込める。全データを比較せずにレプリカを同期でき、修復のコストを小さく抑えられる。

単一障害点のないP2P

Dynamoには特別な親ノードや調停役が存在しない。すべてのノードが対等で、同じ責務を持つ完全対称なP2P構成だ。ノードは互いの生死をゴシップ（gossip）で伝え合い、メンバー構成を共有する。中心となる管理ノードがないため、そこが落ちれば全体が止まるという単一障害点を持たない。運用面でも、ノードを足せばそのぶん容量とスループットが伸びる素直なスケールを実現した。

その後の影響

Dynamoが示した設計思想は、論文の枠を超えて分散データベースの一時代を作った。Apache Cassandra、Riak、Voldemortはいずれも、コンシステントハッシュやクォーラム、結果整合性といったDynamoの発想を色濃く受け継いでいる。特にCassandraは、Dynamoの分散モデルとBigtableのデータモデルを組み合わせたものとして広く使われるようになった。

そしてAmazon自身は、この経験をマネージドサービスへと結実させる。名前を受け継いだAmazon DynamoDBは、Dynamo論文の運用知見を土台に、フルマネージドなキーバリュー／ドキュメントストアとして提供された。論文が扱った可用性やスケールの難しさを、利用者が意識せず使えるサービスへ昇華させたといえる。

より大きな影響は、語彙と考え方そのものの普及にある。「結果整合性」「コンシステントハッシュ」「クォーラム」「ベクタークロック」といった用語は、Dynamo以後、分散システムを語るうえでの共通語になった。強い一貫性だけが正解ではなく、用途によっては可用性を優先し、整合性はあとから揃えるという選択肢が、実務のエンジニアにとって現実的な設計判断として定着したのだ。CAP定理を机上の理論から日々の設計へ引き下ろした一本として、Dynamoの位置づけは大きい。

まとめ

Dynamoは、「常に書き込めること」を設計の中心に据え、そのために一貫性を緩めるという明快な立場を取った分散キーバリューストアだ。コンシステントハッシュで分散し、N/R/Wクォーラムで可用性と整合性を調整し、衝突はベクタークロックで管理してアプリ側に解決を委ねる。一時故障はヒンテッドハンドオフ、恒久故障はMerkleツリーで癒やし、完全対称なP2Pで単一障害点をなくす。これらの選択はすべて、可用性を落とさないという一点でつながっている。結果整合性を選ぶという判断の原典として、いまも読む価値のある論文だ。ほかの分散システムの古典は論文で辿るから辿れる。