Dynamo 論文から DynamoDB へ

2007 年の "Dynamo: Amazon's Highly Available Key-value Store" 論文と、今日あなたが呼び出す DynamoDB は、名前と目標 — どんなスケールでも予測可能なパフォーマンス — を共有しますが、同じシステムではありません。論文は、自分で運用する内部の結果整合性ストアを記述しました。DynamoDB は、教訓を保ち、機構のほとんどを捨てたマネージドサービスです。

DynamoDB は Dynamo 論文に基づいているのか？

部分的にはそうです。DynamoDB はその名前と中核的な目標 — どんなスケールでも予測可能なパフォーマンスと高可用性 — を 2007 年の Amazon Dynamo 論文から受け継ぎ、パーティションキーのハッシュという考え方はほぼそのまま保ちました。しかし、それは別物のマネージドシステムです。論文のベクタークロック、ゴシップによるメンバーシップ、調整可能な読み取り/書き込みクォーラムは姿を消し、AWS が所有する内部構造に置き換えられました。

• 論文は可用性を解いたのであって、使い勝手ではない。 その仕事は、休日のトラフィックスパイク中に、たとえ古い読み取りを返す代償を払っても、決して書き込みを拒否しないことだった。
• DynamoDB は形を保ち、内部を置き換えた。 キーのハッシュで分割し、AZ をまたいでレプリケートし、水平にスケールする — が、競合解決の中身（ベクタークロック、ゴシップ、read-repair）は無い。
• もうつまみを回さない。 論文の N、R、W は1つの選択になった — ConsistentRead を true か false か。残りは AWS が所有する。
• メンタルモデルは依然として報われる。 系譜を知ることが、Scan がなぜ高いか、GSI の読み取りがなぜ遅れうるかを説明する — どちらも元の設計から落ちてくる。

論文が実際に解いていたもの

Amazon のショッピングカートはダウンできませんでした。負荷下で書き込みを拒否する — あるいは失敗したレプリカでブロックする — リレーショナルデータベースは許容できませんでした。2007 年の Dynamo 論文は 整合性より可用性 を選びました — 常に書き込みを受け入れ、不一致は後で調停する。そのトレードが以下すべての根です。

単一のマスターなしにそれを行うため、Dynamo は2つの問いに自力で答えなければなりませんでした — キーはどこに存在するか、そして読み取りや書き込みが成立する前に何個のコピーが一致しなければならないか。

コンシステントハッシング: キーはどこに存在するか

論文はすべてのノードをハッシュリングに置きました。キーの位置はそのキーのハッシュで、時計回りに次のノードが所有し、続く N-1 個のノードへレプリケートされます。ノードの追加や削除は、その隣のキーを再シャッフルするだけ — データセット全体ではありません。それが コンシステントハッシング で、DynamoDB がほぼそのまま保った1つの考え方です。

DynamoDB は今もパーティションキーをハッシュして、どの物理パーティションがアイテムを格納するかを決めます。低カーディナリティのパーティションキー — たとえば2つの値を持つ STATUS — を選ぶと、同じ値のすべてのアイテムが同じパーティションに着地します。それが ホットパーティション の地雷で、リングの直接の帰結です — ハッシュは同一のキーを同一の住まいへ送ります。

クォーラム: 何個のコピーが一致しなければならないか

論文の2つ目のつまみは クォーラム でした。N 個のレプリカで、書き込みは W 個が ack すれば成功し、読み取りは R 個に問い合わせます。R + W > N にセットすると、どの読み取りも最新の書き込みを保持する少なくとも1つのノードと重なります — 強い整合性です。それらを低くセットすると、鮮度を速度と稼働時間と引き換えにします。

Dynamo は「ずさんな」クォーラムを走らせました — 対象ノードがダウンしていれば、書き込みは代役へ行き、後で引き渡されました（hinted handoff）。競合するバージョンは ベクタークロック でタグ付けされ、読み取り時にアプリケーションが調停しました。

DynamoDB が保ったものと変えたもの

DynamoDB は目標と分割を受け継ぎ、それから元のシステムを運用しにくくしていた部分を削除しました。

論文の API は2つの呼び出しでした — get(key) と put(key, value)。DynamoDB は同じキーバリューのコアの上にソートキー、インデックス、クエリを追加しました — だから Query は安く（1パーティション）、Scan は安くない（リングがこれまで作ったすべてのパーティションを歩く)のです。

書き込みはどう旅するか、当時と今

下の流れは、論文のクォーラム書き込みと DynamoDB のマネージドな書き込みを対比します。形は韻を踏みますが、責任があなたのコードから AWS へ移りました。

論文では、クォーラムの計算とマージをあなたが所有しました。DynamoDB では、その下半分全体がマネージドで、あなたはリクエストごとに ConsistentRead を選ぶだけです。

系譜があなたのコードに漏れ出るところ

結果整合性のデフォルトは、論文が透けて見えているのです。global secondary index は非同期にレプリケートされるので、書き込んだばかりのアイテムが一瞬インデックスから欠けることがあります — 同じ「後で調停する」取引が、ただインデックス層で起きているだけです。そのラグが効くのはいつかはGSI と LSIを参照。

強い整合性は2つの方法で買い戻せます。ベーステーブルの読み取りで ConsistentRead: true を使う（リーダーのコピーへルーティングされる）、または書き込みを ConditionExpression でガードして、アイテムの現在の状態が一致するときだけ着地させる。1つをDynamoDB 式ビルダーでスケッチしましょう — たとえば attribute_not_exists(PK) で PutItem を挿入専用の操作にする、論文の競合検出の現代的な代役です。

1つだけ覚えておくこと

論文は、書き込みに決してノーと言わないことを最適化しました。DynamoDB はそのバイアスを受け継ぎ、だからそのデフォルトは可用性を優先し、強い読み取りはより高くつきます。シングルテーブル設計のように単一パーティションの Query のためにキーをモデリングし、本当に必要なときだけ Scan に手を伸ばしましょう — リングは、フルテーブルの歩みを、聞こえるとおりに高くします。

DynoTable を試してパーティションを調べ、必要に応じて整合性のある読み取りを実行し、自分のテーブルに対して GSI が追いつく様子を見ましょう。