このページの目次
ストレージシステムの具体例
Dynamo(リーダーレス + ゴシップ + クォーラム)と Spanner(リーダーベース + TrueTime + Paxos + 2PC)は、分散ストレージの両極を表しています。前五章で学んだコンセンサス、レプリケーション、パーティショニング、メンバー発見を組み合わせて、2つの完全なシステムアーキテクチャを構築します。
概要
前五章ではそれぞれコンセンサス、レプリケーション、パーティショニング、メンバー発見、読み書きパスと修復について解説しました。これらは孤立した概念ではなく、実際の分散ストレージシステムでは同時に稼働し、互いに噛み合っています。ここでは2つの古典的なシステムを取り上げ、これまでの部品を組み立てて完成品を作ります。Dynamo(リーダーレス + ゴシップ + クォーラムの路線)と Spanner(リーダーベース + TrueTime + 外部一貫性の路線)です。これら2つのシステムは分散ストレージの両極を表しており、これらを理解すれば、前五章の各章でなぜそのように解説したのかが理解できます。
Dynamo: 可用性を優先するパズル
Amazonの2007年のDynamo論文は、リーダーレス + 最終一貫性という一連の路線(Riak、Cassandra、DynamoDBなど)の基礎を築きました。そのアーキテクチャは、いくつかの独立したメカニズムの組み合わせであり、各メカニズムはすでに個別に解説済みです。これらを組み合わせることで、Dynamoが完成します。
| 層 | Dynamoの手法 | 対応する前章 |
|---|---|---|
| パーティショニング | 一貫性ハッシュ。各ノードが特定のトークン範囲を担当。負荷をより均一にするため仮想ノード(物理ノードあたり約100個のvnode)を導入 | 一貫性ハッシュ |
| レプリケーション | 各データはコーディネーターに書き込まれ、時計回りにN個の successor(vnodeが存在する物理ノード)に書き込まれ、レプリカが異なる物理ノードに分散されることを保証 | レプリケーション戦略 リーダーレス |
| 書き込み | コーディネーターがN個のレプリカに並列書き込みを行い、W個のACKを待てば返答。W < Nの場合、一部のレプリカは一時的に不整合になる | 分散読み書きパス |
| 読み取り | コーディネーターがN個のレプリカに並列読み込みを行い、R個の応答を待ち、最も新しいバージョン(タイムスタンプではなくベクトルクロックで比較)を取得。read repairをトリガーして、非同期で最新バージョンを遅れたレプリカにプッシュ | 同上 |
| メンバー発見 | ゴシッププロトコルでノードの参加/離脱/ハートビート情報を伝播し、最終的に各ノードが完全なルーティングテーブルを持つ | Gossipプロトコル |
| 整合性修復 | バックグラウンドでMerkle treeによる比較、ゴシップ駆動での修復 | 整合性修復とデータ修復 |
| 競合解決 | ベクトルクロック(vector clock)で因果関係を追跡。アプリケーション側で読み取り時に競合をマージ(ショッピングカート: 異なるレプリカの項目をマージし、消失させない) | 競合解決 |
| hinted handoff | 対象ノードに到達できない場合、コーディネーターがその分のデータを自機のhints領域に一時的に保存し、対象ノードが復旧後に再生する | 分散読み書きパス hintセクション |
これらの層が噛み合う際には、スタック全体を通じて2つのグローバルな制約が貫かれています。
- 常に書き込み可能(always writeable)——一部のノードに到達できなくても、コーディネーターは書き込みを受け付けます(hinted handoff + sloppy quorumによりWを確保)。その代償として、競合がより頻繁に発生する可能性があります。
- 最終一貫性——データは最終的に収束しますが、収束前のウィンドウ内では、異なる読み取りで異なるバージョンが見えることがあります。アプリケーション層でこれを処理する必要があります(Dynamoは競合をアプリケーション側に委ねて解決します。これが設計思想の中核です: ストレージ層はアプリケーションのために競合の決定を行いません)。
Dynamoでの書き込みの完全な旅路(全層を繋ぐ)
Spanner: 外部一貫性のパズル
Google Spanner(2012)は別の路線を選びました。強力なリーダー + 外部一貫性です。Googleの広告やF1データベースを支えています。これもまた一連のメカニズムの組み合わせですが、追求する目標は正反対です——可用性を犠牲にしても、「単一マシンのように」振る舞うトランザクションセマンティクスを保証します。
| 層 | Spannerの手法 | 対応する前章 |
|---|---|---|
| パーティショニング | レンジシャーディング(range sharding)。キーを辞書順に分割してタブレットにし、各タブレットは1つのPaxosグループ | シャーディング戦略 |
| コンセンサス | 各タブレット内部はPaxosグループ(複数レプリカ、Paxosでリーダーを選出およびログをレプリケート) | Paxos |
| レプリケーション | Paxosログをグループ内の過半数にレプリケート。すべての書き込みはリーダーを経由する必要がある。読み取りはフォロワーから可能(ただし読み取りトランザクションのタイムスタンプが必要) | レプリケーション戦略 single-leader |
| トランザクション | タブレットを跨ぐ書き込みは2PC(2フェーズコミット)を使用。コーディネーターはPaxosリーダーの1つ。コミットタイムスタンプはTrueTimeによって割り当てられる | 分散トランザクション |
| 時間 | TrueTime: 各データセンターにGPSと原子時計による同期があり、グローバルなクロックのオフセットを ≤ ε(約7ms)に保証。各トランザクションに「すべてのコミット済みトランザクションより遅い」タイムスタンプを割り当て、外部一貫性を実現 | 時間とクロック |
Spannerの中核的な革新は、TrueTime + 2PC + Paxosの組み合わせにより、外部一貫性(external consistency)を実現した点です——トランザクションはコミットタイムスタンプでグローバルに順序付けられ、どの読み取りでも、それより前の書き込みをすべて見ることができます。これはDynamoの「最終的に収束し、読み取りで古いデータが見える可能性がある」とは正反対です。
Spannerでの跨テーブルトランザクション(全層を繋ぐ)
BEGIN
UPDATE users SET balance = balance - 100 WHERE id = 42 -- タブレットA (PaxosグループG1)
UPDATE orders SET status = 'paid' WHERE id = 789 -- タブレットB (PaxosグループG2)
COMMIT
フロー:
1. クライアント → G1のPaxosリーダー (2PCコーディネーターとなる)
2. コーディネーター: G1とG2のリーダーにprepareを送信
3. 各グループのPaxosリーダー: prepareレコードをPaxosログに書き込み → 過半数にレプリケート
4. 全参加者がACK → コーディネーターがコミットタイムスタンプを選択:
- ts = max(各参加者のローカル時間) + バックオフ > TrueTime.now() + ε
- これにより、tsがすでにコミットされたトランザクションのタイムスタンプより遅いことが保証される (外部一貫性)
5. コーディネーター: commit record + tsを自機のPaxosログに書き込み → レプリケート → committed
6. 各参加者にコミットを通知 (ts付きPaxosログエントリ)
注意: 4番目のステップでTrueTimeの now() + ε を保証するのは、εがクロックのずれの上限であるため、すべてのデータセンターの「今」の実際の時間は now() + ε を超えることがないからです。したがって、ts > now() + ε を選択することで、tsが将来の時間であることが保証され、ts以降の読み取りではこのトランザクションが見えるようになります。これこそが、SpannerがSQLに対して「単一マシンのように」直列化分離を提供できる理由です——タイムスタンプは真の物理的な制約に基づくグローバル順序だからです。
両極の比較
| Dynamo | Spanner | |
|---|---|---|
| 一貫性 | 最終一貫性 | 外部一貫性(強力) |
| 書き込み可用性 | 常に(リーダーレス、任意のノードが受け付け可能) | リーダーが必要(リーダーがダウンすると選挙待ち) |
| 競合解決 | アプリケーション側 (ベクトルクロック) | ストレージ層 (タイムスタンプのグローバル順序) |
| トランザクション | キーを跨ぐトランザクションはサポートしない | 完全なACID (2PC + TrueTime) |
| レイテンシ | 低い (複数ラウンドの調整なし) | 高い (Paxos + 2PC + コミット待機) |
| クロック依存 | 緩い (バージョン比較にのみ使用され、同期は要求されない) | 厳しい (TrueTimeが正しさの前提) |
| 運用複雑さ | 低い (リーダーなし、ノードは自由にダウン可能) | 高い (GPS/原子時計による同期、リーダー選挙) |
この2つのシステムの選択は、分散ストレージシステムの根本的なトレードオフです——ストレージの選定を行う際には、常にこの表の2つの列の間で位置を見つけることになります。
参考文献
- Dynamo論文: "Dynamo: Amazon's Highly Available Key-value Store"(DeCandia 2007)——すべてのリーダーレスシステムの源流
- Spanner論文: "Spanner: Google's Globally-Distributed Database"(Corbett 2012)——TrueTime + 外部一貫性
Keywords: Dynamo, Spanner, leaderless, leader-based, consistent hashing, virtual nodes, gossip, quorum, Merkle tree, vector clock, eventual consistency, TrueTime, external consistency, Paxos, 2PC, GPS + atomic clock, commit wait, ε, always writeable, timestamp ordering