上級読了 4 分

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 だけです。

論文: リング、N,R,Wは自分で調整DynamoDB: マネージドput(key, value)キーをハッシュどちらのシステム?N 個のノードのうち W個に書き込み読み取り時にベクタークロックで調停リーダーが書き込みをログに記録3 つの AZ レプリカのうち 2つが永続化したら ack

論文が今も 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 を実行できます。

著者: Dmitriy · 更新日