はじめに：魔法への疑念

「データが100件でも1億件でも、DynamoDBの応答速度（レイテンシ）は変わらない」

AWSのドキュメントやセミナーでよく聞くフレーズですが、RDBMSに慣れ親しんだエンジニアからすると、そんな魔法みたいな話があるかと疑いたくなります。

インデックスを貼ろうが何しようが、データが増えれば遅くなるのがデータベースの常識のはずです。

この記事では、DynamoDBがなぜスケールしても遅くならないのか、その「魔法」のタネ明かしをします。

結論から言うと、そこにあるのは魔法ではなく、Request Router、Paxos、そして徹底的な物理制約（メモリとI/O）の回避という、泥臭くも美しいアーキテクチャでした。

この記事の結論（忙しい人向け）

DynamoDBが遅くならない理由は、魔法ではなく3つの物理的な工夫にあります。

探さない ($O(1)$ Routing): 巨大なインデックスを探索せず、ハッシュ計算一発で担当サーバーを特定する。
溜めない (Partitioning): データが増えても1つの木（B-tree）を10GB以下に保ち、検索計算量を定数に収束させる。
迷わない (Paxos & Lease): 3拠点で合意形成しつつ、リーダー任期制で通信待ちを極限まで減らす。

0. 解剖図：DynamoDBの「物理」構造

本題に入る前に、DynamoDBが物理的にどうなっているのか、その「登場人物」を整理しておきましょう。ここを理解すると、後の話がスッと入ってきます。多いので、逐一見返してみてください！

登場人物の階層構造

🌏 Region (リージョン)
- 🧠 Control Plane (管理層): データの配置や健全性を管理する裏方の司令塔。
  - Auto Admin: パーティション分割（Split）や障害復旧を自動で行う「管理人」。DynamoDBの心臓部。
    - スケーラブルな管理フリート: 単一のサーバーではなく、管理タスク量に応じてスケールする分散システム。
    - Metadataの更新: 分割や移動の結果をPartition Metadata Systemに書き込む。
    - 自己修復: 全ストレージノードを監視し、障害時は自動で代替ノードを作成してデータを復旧（B-treeとログのコピー）させる。
  - Partition Metadata System: 「地図（Partition Map）」の原本管理者。Auto Adminからの更新を受け、Routerに最新の地図を配布する。
- 🚦 Request Router (Router): 玄関口。地図をキャッシュし、リクエストを正しいサーバーへ飛ばす。
- 🏢 Availability Zone (AZ) x 3: 物理的に離れたデータセンター。
  - 💻 Storage Node (物理サーバー): SSDを搭載したサーバー。数千のパーティション（レプリカ）が同居している。
    - 📦 Replica (物理パーティション): テーブル作成時に、サーバー上に作成されるデータを格納する場所。3つのAZのレプリカで**Paxos Group（合意形成チーム）**を組む。
      - 🌳 B-Tree: 実際にデータを格納するデータ構造。
      - 📜 Replication Log: 書き込み操作を記録する台帳。Paxosアルゴリズムを用いて、全レプリカ間で順序と内容の一貫性が保証される。

【図解】3つのAZに跨るデータ配置

DynamoDBのテーブルを作成すると、裏側では自動的に 3つのAZ にレプリカが配置されます。

📚 参考文献・出典

1. 敵を知る：RDBMSはなぜ「遅くなる」のか？

DynamoDBの凄さを理解するには、まず「なぜRDBMS（MySQL, PostgreSQL）はデータが増えると遅くなるのか」を、物理構造（B-Tree） と メモリ管理 のレベルで理解する必要があります。

① B-Treeの正体：PKから「ページID」への旅

データベースのインデックス（B-Tree）とは、一言で言えば 「PK（検索条件）を頼りに、ページID（物理的なデータの住所）を探す旅」 です。

以下の図を見てください。例えば、PKが6500のデータを取得したい場合に、データにたどり着くまでに、複数の「ページ（Page）」を経由しなければなりません。

ページ (Page): DBがデータを管理する最小単位（通常 4KB〜16KB の箱）。この箱単位でメモリとディスクを行き来します。
ページID: 箱につけられた物理的な住所。

データ量 $N$ が増えると、このツリーはどんどん高く（深く）なります。

上記の図では2回ジャンプすればデータに着いたのですが、データが増えると、3回、4回、5回……と増えていきます。これが 計算量 $O(\log N)$ の増加 です。

② 「スラッシング」の恐怖（物理的な死）

もっと致命的なのがこれです。計算回数が増えるだけでなく、物理的にメモリが溢れるのです。

データベースは、頻繁に使うページをメモリ上の「バッファプール（Buffer Pool）」に置きます。しかし、木が巨大化してインデックス自体がメモリに乗り切らなくなるとどうなるでしょうか？

状態	机（メモリ）と倉庫（ディスク）のたとえ	速度イメージ
正常時 (In-Memory)	机の上で書類（ページ）を広げて辿る。	100ナノ秒 (爆速)
メモリ不足 (Swap)	机が一杯。一旦、ページを遠くの倉庫（ディスク）に運び出す。次のページを見るために、また倉庫まで走って取りに行く。	10ミリ秒 (10万倍遅い)

さらにRDBMSでは、複雑なJOINや集計処理を行うと、計算用の作業メモリ（Working Memory）も大量に消費します。これらが競合してメモリが溢れると、DBはこの「倉庫往復」を頻繁に繰り返します（スラッシング）。

これが、データ量が増えた途端にRDBMSが指数関数的に遅くなる真の原因です。

📚 参考文献・出典

B-Treeの計算量: PostgreSQL Documentation - Internals: B-Tree Structure
ディスクI/Oとバッファプール: MySQL 8.0 Reference Manual - The InnoDB Buffer Pool
スラッシング: Wikipedia - Thrashing (Computer Science)

2. 解決策①：「旅をしない」 ($O(1)$ ルーティング)

ここからが本題です。DynamoDBはこの「RDBMSの弱点」をどう克服したのでしょうか？

最初のアプローチは、「そもそも巨大なB-Treeを探索しない（旅をスキップする）」 ことです。

Request Router と Cached Map

DynamoDBへのリクエストは、まず冒頭で紹介した Request Router が受け取ります。

通常、案内係は「データはどこ？」とデータベースに問い合わせたくなりますが、DynamoDBのRouterは違います。

Routerは、Partition Map（パーティションの地図） を自分自身のメモリ上に キャッシュ（暗記） しています。

地図（Partition Map）の中身

Partition Mapは、すべてのPKを覚えているわけではありません（それではメモリが溢れます）。

「ハッシュ値の範囲（Range）」と「ノードグループID」の対応表 です。

ハッシュ範囲 (Start - End)	担当パーティション (Group ID)
0x0000 - 0x4FFF	Partition A (Node 1, 2, 3)
0x5000 - 0x9FFF	Partition B (Node 4, 5, 6)
...	...

Hash計算: 送られてきた Partition Key (PK) のみ をハッシュ関数にかける。
- 重要: Sort Key (SK) はここでは無視されます。
Map参照: 地図の範囲を見て、「ハッシュ値が 0x1234 だから、Partition A だな」と即座に特定する。

B-Treeを何段も降りる必要はありません。計算一発で「正解のサーバー」へワープします。

📝 理論的根拠

ハッシュマップを用いたルックアップ操作であるため、理論上の計算量は $O(1)$ となります。(Source: USENIX ATC '22)

📚 参考文献・出典

$O(1)$ ルーティング: USENIX ATC '22 Paper (Section 2.2: Request Routing)

3. 解決策②：「木を大きくしない」 (物理パーティショニング)

ルーティングで特定のサーバー（ストレージノード）に着いた後はどうなるのでしょうか？

ここで 「10GBの壁」 が効いてきます。

検索空間を強制的に小さく保つ

実は、DynamoDBのストレージノード内部でも B-Tree が使われています。

「えっ、それじゃ結局遅くなるのでは？」と思うかもしれませんが、決定的な違いがあります。

RDBMS: データが増えると、1つの巨大な木（高さ5段、6段...）に成長し、メモリに乗り切らなくなる。
DynamoDB: 木が大きくなる前に、新しい「パーティション」に分割（Split） し、負荷が均等になるようクラスタ内のサーバー群に分散配置する。

よくある誤解ですが、DynamoDBにおいて「1台のサーバー＝1つのパーティション」ではありません。1台の物理サーバー（ストレージノード）の中には、何千ものパーティション（のレプリカ）が同居しています。

1つのパーティション（＝1つのB-Tree）のデータ量が約10GBを超えると、自動的に「2つのパーティション」に分割（Split）されます。分割されたパーティションは、AWSのコントロールプレーン（Auto Admin）によって、空き容量のある適切なサーバーへと再配置（移動）されます。

つまり、どんなにデータが増えても、検索対象の「木」の大きさは常に一定（10GB以下）に保たれる のです。

厳密な計算量： O(1)

$N_{partition}$ = 1つのパーティション内のデータ数（上限10GBによりキャップされる）

全データ $N$ が100TBになっても、検索対象の $N_{partition}$ は常に小さいままです。したがって、探索コスト $O(\log N_{partition})$ は 定数（一定の最大値） に収束します。

【コラム1】分割された「地図」はどうなる？

「パーティションが勝手に分割されたら、Routerが持っている地図と食い違ってしまうのでは？」

ご安心ください。ここで Control Plane が活躍します。

Auto Admin が分割（Split）と移動を実行。
その結果（新しい配置）を Partition Metadata System に書き込む。
最新の地図情報が Request Router に伝播される。

この連携により、Routerは常に「正しい宛先」を知ることができるのです。

【図解】パーティション分割のイメージ

【コラム2】偏りへの耐性 (Adaptive Capacity)

「パーティションを分割しても、特定の1つのパーティションだけにアクセスが集中（ホットパーティション) したら遅くなるのでは？」

鋭い疑問です。かつてのDynamoDBではそれが課題でしたが、現在は Adaptive Capacity (適応型キャパシティ) によって克服されています。

仕組み: あるパーティションが忙しくなると、システムが自動的に、暇な他のパーティション」のキャパシティを融通して割り当てます。
効果: これにより、データ分布が不均一でも、物理的な限界（1パーティションあたり最大3,000RCU/1,000WCU程度）まではスループットを維持できます。

この記事のテーマである「レイテンシ（速さ）」とは少し異なりますが、この「トラフィックの偏りを吸収する力（強さ）」もまた、DynamoDBが大規模サービスで選ばれる理由の一つです。

📚 参考文献・出典

Partitioning: AWS Developer Guide - Partitions and Data Distribution
Adaptive Capacity: AWS Database Blog - Accommodate uneven data access patterns with DynamoDB Adaptive Capacity

4. 深掘り：SK（ソートキー）検索もなぜ速い？

「PKで絞り込むのは分かった。でも begins_with（範囲検索）をしたら、結局スキャンで遅くなるのでは？」

答えは No です。ここにもB-Treeの物理構造が生きています。

連結キーとページ構造

物理的には、PKとSKは 「PKとSKをバイナリ結合した値 (Concatenated Key)」 としてB-Treeに格納されています。

論理イメージ: PK=UserA, SK=2023-01
物理キー: UserA:::2023-01

これにより、PKが同じデータは物理的に隣接し、さらにSK順にソートされて 「リーフページ（数KBのブロック）」 に詰め込まれます。

計算量の内訳：

$O(log N_{part} + K)$
- $O(\log N_{part})$ Seek (頭出し): 目次を見て、該当データの 最初のページID を特定。
- $O(K)$ Fetch (順次読み出し): そのページを開き、隣り合うデータを吸い出すだけ。

辞書で「apple」を引くとき、「A」のページを一発で開き（Seek）、そこから「apple」の項目だけを読む（Fetch） のと同じです。

他のページ（zebraやbanana）は一切読み込まないため、データ総量がどれだけ増えても速度には影響しません。

5. 比較：なぜDynamoDBは「死なない」のか

ここまでの仕組みを、RDBMSと比較して整理します。

DynamoDBが「不便だ（Joinできない）」と言われる理由は、裏を返せば 「物理的に死なないための安全装置」 なのです。

この違いは、メモリがどのように圧迫されるか（静的 vs 動的）で見るとより鮮明になります。

特徴	RDBMS (PostgreSQL / MySQL / Aurora)	DynamoDB
静的な圧迫 (構造の問題)	インデックス肥大化木が巨大化し、バッファプール（データ置き場）を圧迫する。 📉 地図を見るだけでディスクI/Oが発生。	パーティショニング 10GBで分割されるため、個々の木は常に小さいまま。 📈 メモリ効率が良い。
動的な圧迫 (操作の問題)	複雑なクエリ (JOIN/Sort) 計算のために大量の「作業台（Sort/Join Buffer）」を消費する。 💥 一発のクエリでメモリが溢れるリスク。	機能制限 (No JOIN) JOINや集計を禁止し、データを「置いて読むだけ (Fetch)」に特化。 🛡️ 作業メモリが溢れる事態を物理的に防ぐ。
結果	メモリ不足で Disk Swap (スラッシング) が発生し、死ぬ。	1リクエストの取得上限(1MB)もあり、物理的にメモリが溢れない。

DynamoDBは、「メモリを圧迫して自滅するような処理を、物理的に実行させない」 という仕組み（ガードレール）によって、Predictable Performance（予測可能な性能） を維持しているのです。

6. 裏側の正義：PaxosとConsistent Hashing

最後に、この爆速アーキテクチャを支える「裏方」を紹介します。

Paxos：正しさを守る裁判官（と、そのスピード）

「Routerがキャッシュ（地図）を持ってるなら、古い地図を見て間違った場所に書き込んだらどうする？」「3つのAZにコピーするなら遅くならない？」

そこで Paxos の出番です。

1. 鉄壁の書き込みフロー (Durability)

DynamoDBの書き込みは、必ず 「過半数（Quorum）」 の合意を得てから完了します。

Routerからリクエストが リーダー (Leader) に届く。
リーダーは自分に書き込み、同時に2台のフォロワーにログを送る。
リーダー + フォロワー1台（合計2台） が書き込み完了した時点で、クライアントに HTTP 200 OK を返す。
【ここがポイント】 残りの1台のフォロワーへは、バックグラウンドで非同期にログが送られ、最終的に追いつく（キャッチアップ）。

これにより、万が一リーダーが直後に爆発しても、フォロワーにデータが残っているため 「データ消失（ロスト）」や「先祖返り（スプリットブレイン）」は絶対に起きません。

2. リーダーは「任期制」で高速化 (Lease Mechanism)

「毎回リーダーを決める選挙をしていたら遅いのでは？」

その通りです。だからDynamoDBは 「リース（任期）」 という仕組みを使っています。

選挙: 最初の一回だけ行う（数秒かかる）。
維持: 選ばれたリーダーは、定期的に「俺はまだ生きてるぞ（Heartbeat）」と宣言し、任期を延長し続ける。
結果: 書き込みのたびに選挙をする必要がないため、通常時のオーバーヘッドはほぼゼロ です。

これこそが、「強力な整合性（Strong Consistency）」と「低レイテンシ」を両立できる秘密 です。

3. 読み込みの整合性：なぜ「結果整合性」は速いのか？

この「2台でOK、残りは後で」という書き込みフローが、読み込みの挙動に直結します。

強力な整合性 (Strongly Consistent Read):
- 必ず 「リーダー」 に問い合わせます。
- リーダーは最新の書き込みを知っているため、「保存後、即取得」でも絶対に最新データ が返ってきます。
- デメリット: リーダーへの通信が必要なため、レイテンシがわずかに増える場合がある。
結果整合性 (Eventually Consistent Read):
- 3つのレプリカのうち、「一番近くにいるどれか（ランダム）」 から読みます。
- もし、まだログが届いていない「残りの1台（遅れているフォロワー）」から読んでしまうと、古いデータが返る可能性 があります。
- メリット: どのノードでも良いため、レイテンシが低く、スループットが出やすい（料金も半額）。

Consistent Hashing：無限のスケーリング

ハッシュ空間をリング状に管理することで、パーティションが増減しても、影響範囲を「隣のノード」だけに限定します。

これにより、サービスを止めることなく、裏側で勝手にサーバーを1万台でも10万台でも増やしていけるのです。

📚 参考文献・出典

Paxos & Write Quorum: USENIX ATC '22 Paper (Section 2.3 Replication)
Read Consistency: AWS Developer Guide - Read Consistency
Distributed Transactions: Amazon Science - Distributed transactions at scale in Amazon DynamoDB

まとめ：DynamoDBの速さの方程式

DynamoDBの速さは魔法ではありません。以下の「物理的な工夫」の積み重ねです。

Map Cache: $O(1)$ で行き先を特定（巨大な木の探索を回避）。
Partitioning: 10GBで分割し、ローカル検索範囲を常に一定（浅い木）に保つ。
SK Optimization: 物理配置を最適化し、必要なデータだけをピンポイントで吸い出す ($O(K)$)。
No Thrashing: Joinを禁止し、メモリ溢れによるI/O爆発を構造的に防ぐ。
Paxos: 整合性は裏側で厳密に担保しつつ、リース機構でオーバーヘッドを消す。

もし次に「DynamoDBはなぜ速いのか」と聞かれたら、こう答えてください。

「検索空間を物理的に小さく切り刻み続け、その地図（Map）を高速に配っているから」 と。

📚 総合参考文献 & 公式ソース

この記事は、以下の一次情報および技術標準に基づいています。

AWS公式 / 論文
- [USENIX ATC '22] Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service
  - 論文PDF / 概要ページ
  - ※Paxos, Leader Leases, Request Router, Control Planeのアーキテクチャ詳細
- AWS Developer Guide
  - Partitions and Data Distribution
  - Read Consistency
- AWS re:Invent 2018: Amazon DynamoDB Under the Hood (DAT321)
  - YouTube Video
  - ※Auto Admin, Partitioning, Paxosの解説動画
- Amazon Science
  - Distributed transactions at scale in Amazon DynamoDB
RDBMS理論 / コンピュータサイエンス基礎
- MySQL 8.0 Reference Manual
  - Optimization / InnoDB Buffer Pool
- PostgreSQL Documentation
  - Internals / B-Tree Indexes
- Operating System Concepts
  - Wikipedia: Thrashing (computer science)