Dynamo 論文から DynamoDB へ
2007 年の論文 "Dynamo: Amazon's Highly Available Key-value Store" は、Amazon のチームが自分たちのために運用していたストアを記述したものです。DynamoDB は、AWS がのちに似た名前で構築したマネージドサービスです。
DynamoDB は Dynamo 論文に基づいている?
ゆるやかにしか基づいていません。今日のサービスを記述した 2022 年の USENIX ATC 論文は、DynamoDB が "shared most of the name of the previous Dynamo system but little of its architecture." と述べています。今でも パーティションキー はハッシュされます。
リング、sloppy クォーラム、ベクタークロック、ゴシップは消えました。
- 論文は決して失敗しない書き込みに最適化しました。 その仕事は、障害中でもショッピングカートの書き込みを受け付けることでした。たとえ後の読み込みが古いバージョンや競合するバージョンを返すとしてもです。
- DynamoDB はハッシュを残し、仕組みを置き換えました。 パーティションは連続したキー範囲を所有し、それぞれが選出されたリーダーを持つ 3 レプリカのグループで、書き込みには 3 つのうち 2 つが必要です。
- もうツマミを調整しません。 論文の
N、R、Wは、読み込みごとの 1 つの選択になりました。ConsistentReadを true にするか false にするかです。 - 系譜は文脈であって、原因ではありません。 設計を読み解く助けにはなりますが、
Scanのコストと GSI の遅延を説明しているのは AWS 自身のドキュメントです。
論文が解いていたもの
Amazon のショッピングカートはダウンできませんでした。2007 年の論文は "always writeable" なストアを記述しています。書き込みを受け付け、不一致はあとで調整するのです。
負荷下で書き込みを拒否する、あるいは失敗したレプリカでブロックするデータベースこそ、それが避けるために作られたものでした。
単一のマスターなしに動くために、Dynamo は 2 つの問いに自ら答えなければなりませんでした。キーはどこに住むのか、そして読み込みや書き込みが成立するまでに何個のコピーが一致しなければならないのか。
一貫性ハッシュ:Dynamo でキーはどこに住んでいたか
論文はすべてのノードをハッシュリング上のランダムな位置に配置しました。キーの位置はそのキーのハッシュで、時計回りで次のノードがそれを所有し、続く N-1 個のノードがレプリカを保持します。
ノードの追加や削除は、隣接するノードのキーだけを動かします。それが一貫性ハッシュです。
DynamoDB は最初のステップ、つまりキーのハッシュを残し、リングを置き換えました。ATC '22 論文によれば、各パーティションは "hosts a disjoint and contiguous part of the table's key-range" であり、DynamoDB はパーティションが育ったりホットになったりすると分割します。
配置はパーティションキーの仕組みで順に説明し、分割は物理パーティションで扱っています。
ハッシュがあるからこそ、キーの選択は今も重要です。カーディナリティの低いパーティションキー、例えば 2 つの値しか持たない STATUS を選ぶと、同じ値を持つすべての項目が 1 つのアイテムコレクションを共有します。それがホットパーティションの落とし穴です。
抜け道は、ユーザー ID やテナント ID のようなカーディナリティの高いパーティションキーです。カーディナリティの低い値は GSI のソートキーとして、あるいは ACTIVE#customer123 のような複合キーの中に残します。ホットのままでなければならないキーのシャーディングはホットパーティションで扱っています。
クォーラム:何個のコピーが一致しなければならなかったか
論文の 2 つ目のツマミはクォーラムでした。N 個のレプリカがあるとき、書き込みはそのうち W 個が ack すると成功し、読み込みはそのうち R 個に問い合わせます。論文は R + W > N が "yields a quorum-like system" と述べています。メンバーシップが厳密なら、どの読み込みも最新の書き込みと重なります。
Dynamo はそれを緩めました。その "sloppy" なクォーラムは最初の N 個の健全なノードを使ったので、ダウンしたノード宛ての書き込みは代役に行き、あとで返されました(ヒンテッドハンドオフ)。
競合するバージョンはベクタークロックでタグ付けされ、読み込み時にアプリケーションが調整しました。
DynamoDB が残したもの、変えたもの
DynamoDB は、規模における予測可能なパフォーマンスという目標と、キーのハッシュを残しました。ATC '22 論文は、それ以外を新しい仕組みとして記述しています。
| 関心事 | 2007 年の Dynamo 論文 | 今日の DynamoDB(ATC '22 論文、AWS ドキュメント) |
|---|---|---|
| キーの配置 | 一貫性ハッシュリング | パーティションキーのハッシュ(コレクションが分割されたらソートキーも)→ そのキー範囲を所有するパーティション |
| レプリケーション | N ノード、あなたが選ぶ | 1 つのリーダーを持つ Multi-Paxos グループで、AZ をまたぐ 3 レプリカ |
| 整合性のツマミ | R、W クォーラムの調整 | 書き込みには 3 レプリカのうち 2 つが必要。読み込みごとに ConsistentRead |
| 競合解決 | ベクタークロック、読み込み時のアプリ側マージ | リージョン内ではなし(書き込みはリーダーを通る)。リージョン間では、MREC グローバルテーブルではラストライターウィンズ、MRSC では拒否 |
| メンバーシップ | ピア間のゴシッププロトコル | フルマネージド、あなたには見えない |
| マルチキー操作 | なし、純粋なキーバリュー | Query、GSI、トランザクション |
マルチリージョン強整合性(MRSC)のグローバルテーブルでは、別のリージョンで変更中の項目への同時書き込みは ReplicatedWriteConflictException で失敗し、それを再試行します。(AWS, How global tables work。)
論文の API は 2 つの呼び出しでした。get(key) と put(key, value) です。DynamoDB は論文のものに似たキーバリューモデルを提供し、ソートキー、インデックス、クエリを加えています。
Query は 1 つのアイテムコレクションをソートキー順に読み、Scan はテーブルのすべてのパーティションを読みます。
書き込みはどう進むのか、当時と今
以下のフローは、論文のクォーラム書き込みと DynamoDB のリーダーベースの書き込みを対比します。論文ではあなたのコードが数値を調整し、競合をマージしていました。DynamoDB では AWS がその両方を所有し、あなたが選ぶのは読み込みごとの ConsistentRead だけです。
論文が今も DynamoDB を読み解く助けになるところ
結果整合性のデフォルトは、論文の「あとで調整する」という取引と韻を踏みます。それは類推として読んでください。実際の理由は AWS 自身の資料が示しています。
ATC '22 論文によれば、結果整合性の読み込みはどのレプリカでも提供でき、AWS は GSI が "asynchronously, using an eventually consistent model" で更新されると述べています。
そのため、新しい項目が一瞬 GSI から欠けることがあります。その遅延が問題になるときについては GSI vs LSI を参照してください。
強い整合性は 2 つの方法で買い戻せます。ベーステーブルの読み込みで ConsistentRead: true を使う(リーダーレプリカに送られます)か、書き込みを ConditionExpression でガードして、項目の現在の状態が一致するときにだけ着地するようにします。
DynamoDB Expression Builder で 1 つスケッチしてみてください。attribute_not_exists(PK) は PutItem を挿入専用にします。これが論文の競合検出に最も近い現代の代役です。
DynamoDB が代わりに選んだトレード
論文は書き込みに決してノーと言いませんでした。DynamoDB は言えます。健全な書き込みクォーラムのないパーティションは書き込みを拒否し、リーダーの障害後、新しいリーダーは古いリースが切れるまで数秒待ってから書き込みを受け付けます(ATC '22)。
AWS SDK はこうした失敗したリクエストをバックオフ付きで再試行します(エラー処理)が、デフォルトの予算(standard リトライモードで 3 回の試行)は新しいリーダーが引き継ぐ前に尽きることがあります。フェイルオーバーを乗り切らなければならない書き込み経路では、SDK の最大試行回数を引き上げてください。リージョン全体の障害には グローバルテーブル を使います。
その見返りとして、リージョン内では項目ごとに 1 つの現在のバージョンが得られ、マージのコードは要りません。
シングルテーブル設計のように単一コレクションの Query のためにキーをモデリングし、Scan はエクスポートと一回限りのジョブのために取っておきましょう。リーダーとそのレプリカはストレージの内部構造で、その前にあるルーターはリクエストルーティングで扱っています。
DynoTable を試すと、テーブルとその GSI を参照し、それから自分のデータに対して SQL Workbench で JOIN と GROUP BY を実行できます。