DynamoDB のストレージ内部構造の仕組み

DynamoDB は、値がソートされた木であるハッシュテーブルで、3つの Availability Zone のマシンにまたがって広がっています。ほぼすべての仕事を2つのデータ構造がこなします — パーティションキーへのハッシュがマシンを選び、ソートキーへの B-tree がその中でアイテムを並べます。

DynamoDB はどのようにデータを保存するのか？

DynamoDB は、値がソートされた B-tree である巨大な分散ハッシュテーブルとしてデータを保存します。パーティションキーへのハッシュが1つのストレージノードを選び、B-tree がその中でソートキーによってアイテムを並べます。すべての書き込みは応答する前に、3つのアベイラビリティーゾーンをまたぐ3つのノードへ同期的にレプリケートされます。

• パーティションキーはハッシュされ、検索されない。 DynamoDB は PK にハッシュ関数を走らせて、そのパーティションを保持する1つのストレージノードを見つける — テーブルサイズに関わらず O(1) のジャンプだ。
• ソートキーは B-tree に存在する。 パーティション内で、アイテムは SK で辞書順に並ぶ B-tree に格納される。だから範囲読み取り（begins_with、between）は安く、Scan は安くない。
• すべての書き込みは ack する前に3つのノードに当たる。 書き込みはリーダーに行き、リーダーが別の AZ の2つのピアへ同期的にレプリケートする — 耐久性は PutItem が返る前に支払われる。
• だからアクセスパターンのルールが存在する。 ハッシュしてから木は、キーで読むときだけ速い。キーが無ければ速い経路も無い — 木のスキャンに落ちる。

API ではなくデータ構造から始める

SQL から来ると、テーブルをディスク上の行と、インデックスを選ぶクエリプランナーとして思い描きます。DynamoDB にプランナーはありません。ストレージのレイアウト そのもの が契約です — 何が速く何が地雷かは、どちらも2つの構造から直接落ちてきます。

巨大な分散マップを思い描いてください。キーはパーティションキーのハッシュです。値は単一のアイテムではなく — そのパーティションキーを共有するアイテムの B-tree 全体で、ソートキーで並べられています。

それ以外のすべて — クエリのセマンティクス、10 GB の警告、欠けたキーが Scan を強いる理由 — はその1文の帰結です。

パーティションキーをハッシュしてノードを見つける

リクエストが到着すると、DynamoDB はパーティションキー値に内部ハッシュ関数を適用します。ハッシュは決定論的に1つの ストレージノード — それらのアイテムを所有する物理パーティション — にマップします。AWS は、テーブルサイズに関わらず定数時間のキールックアップの背後にあるメカニズムとしてこれを文書化しています。

それが O(1) のステップです。10 TB のテーブルと 10 KB のテーブルは 場所を特定する コストが同じです — ハッシュ、ジャンプ、完了。ノードを見つけるためのインデックススキャンも、統計も、プランもありません。

落とし穴は裏面です。パーティションキーを供給しなければ、DynamoDB にジャンプ先のノードはありません — すべてのパーティションを歩かなければなりません。それが Scan で、O(1) とテーブル全体を読むことの違いです。

リクエストはちょうど1つのパーティションにハッシュされ、そのパーティションのソートキー B-tree をアイテムまで降りていきます — テーブル走査ではなく、2つの安いステップです。

パーティションごとの B-tree でアイテムを並べる

単一のパーティション内で、アイテムはヒープではありません。ソートキーをキーとする B-tree に、辞書順で並べて保持されます。B-tree 検索は O(log n) で、決定的に重要なことに、その n は 1つの パーティション内のアイテムであって、テーブル全体ではありません。

これがソートキー範囲読み取りが安い理由のすべてです。各デバイスの読み取り値が1つのパーティションキーの下に存在する車両テレメトリのテーブルを考えます。

B-tree がソートされているので、「08:00 から 09:00 の間のすべての読み取り値」は、開始値への木の降下に続く逐次の歩みです — そのデバイスがこれまで送ったすべての読み取り値に対するフィルタではありません。マッチした範囲だけを読みます。

その順序付けはまた、begins_with(SK, "READING#2026-06-23") クエリが速く、非キー属性へのフィルタリングが速くない理由でもあります。木は SK でシークできますが、それ以外ではシークできません。それらのキー条件を安全に組み立てるには、文字列を手で連結するのではなくDynamoDB 式ビルダーで構築しましょう。

KeyConditionExpression  PK = :pk AND begins_with(SK, :day)

すべての書き込みを3つの AZ にレプリケートする

パーティションは1台のマシンではありません。1つ1つが 3つの Availability Zone の3つのノード にまたいでレプリケートされます — 2007 年の Amazon Dynamo 論文のレプリケーションモデルに遡る設計の系譜です。

1つのノードがパーティションの リーダー です。書き込みはリーダーに行き、リーダーはローカルに書き込んで2つのピアへレプリケートします。リーダーは、ノードの耐久性のあるクォーラムがそれを持った時点で書き込みを ack します — なので AZ をまたいだ耐久性は、PutItem が返る 前 に支払われます。

読み取りには選択肢があります。強い整合性のある 読み取りはリーダーに行き、最新のコミット済み書き込みを見ます。結果整合性のある 読み取りは3つのノードのいずれかから提供されえ、そのうち1つは数ミリ秒遅れているかもしれません — それが、より安く、より可用性の高い読み取りと引き換えにするラグです。

同じ非同期伝播の考え方が、GSI の読み取りが古くなりうる理由です — GSI は結果整合性を参照。

ルールを構造から読み取る

ほぼすべての DynamoDB の「ルール」は、ただのストレージの物理です。

• 常にパーティションキーを供給する。 キーが無ければハッシュ先も無い — マップ全体をスキャンしている。これがQuery と Scanの核心だ。
• 一緒に読むものを共置する。 1つのパーティションキーの下に置けば、1回のハッシュ + 木の歩みでアイテムコレクション全体が返る。それがシングルテーブル設計の基盤だ。
• パーティションを有界に保つ。 1つのパーティションは有限のノード集合上の1つの B-tree だ。暴走するホットキーや LSI の 10 GB 上限は、どちらもその物理パーティションの限界だ。

ハッシュしてから B-tree という形が見えれば、アクセスパターンの規律が恣意的に感じられなくなります — あなたはただ、すべての読み取りを速い経路に保っているだけなのです。

次のステップ

ソートキー戦略とシングルテーブル設計で構造に合わせてキーをモデリングし、それからDynamoDB 式ビルダーで実際の式を組み立てましょう。DynoTable を試してこれらの読み取りが自分のテーブルに対して走る様子を見て、キー条件がどのアイテムを引き戻すかを正確に確かめましょう。