# Dynamo: Amazon's Highly Available Key-value Store > [!abstract] > 大規模な信頼性の確保は Amazon.com が直面する最大の課題のひとつであり、わずかな停止でも重大な財務的影響と顧客信頼の毀損を招く。Amazon.com のプラットフォームは世界中の多数のデータセンタに配置された数万台のサーバとネットワーク構成要素の上に構築されている。この規模では大小の構成要素が絶えず故障し、永続的状態の管理方法がソフトウェアシステムの信頼性とスケーラビリティを左右する。本論文は、Amazon のコアサービスの一部が「常時稼働」体験を提供するために使用する高可用キーバリューストレージシステム Dynamo の設計と実装を提示する。この水準の可用性を達成するため、Dynamo は特定の障害シナリオにおいて整合性を犠牲にする。オブジェクトバージョニングとアプリケーション支援の競合解決を広範に活用し、開発者に新たなインタフェースを提供する。 ## 論文情報 - **著者**: [[Giuseppe DeCandia]], Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, [[Werner Vogels]] - **所属**: [[Amazon|Amazon.com]] - **会議**: SOSP 2007（ACM Symposium on Operating Systems Principles）、2007 年 10 月 14〜17 日、Stevenson, Washington, USA - **URL**: https://dl.acm.org/doi/10.1145/1323293.1294281 ## 概要 Dynamo は Amazon 内部の高可用キーバリューストアである。数百のサービスから構成される Amazon の分散サービス指向アーキテクチャにおいて、ショッピングカート・セッション管理・ベストセラーリスト・顧客設定などのサービスが、ディスク障害・ネットワーク経路の不安定・データセンタの壊滅的障害の最中でも読み書き可能なストレージを必要としている。Dynamo はこの要求に対し、既知の分散システム技術を合成して応える。 主要技術の組み合わせ: - **一貫性ハッシュ法**（consistent hashing）によるデータのパーティショニングとレプリケーション - **ベクタクロック**（vector clocks）によるバージョン管理と因果関係の追跡 - **スロッピークォーラム**（sloppy quorum）と**ヒンテッドハンドオフ**（hinted handoff）による一時障害の処理 - **マークル木**（Merkle trees）を用いたアンチエントロピーによるレプリカ同期 - **ゴシッププロトコル**（gossip protocol）によるメンバーシップ管理と障害検知 ## 問題設定 Amazon の e コマースプラットフォームは数万台のサーバで動作し、ページリクエスト 1 件あたり 150 以上のサービスに問い合わせる。SLA は 99.9 パーセンタイルで評価され（平均・中央値ではなく）、300 ミリ秒以内の応答が要求される。 従来のリレーショナルデータベースでは以下の問題がある: - Amazon のサービスの多くはプライマリキーのみのアクセスであり、リレーショナルスキーマの複雑さは不要 - 商用データベースの ACID 保証は可用性を犠牲にする - スケールアウトが困難であり、レプリケーション技術は整合性を可用性より優先する 設計上の核心的判断: 1. **「常に書き込み可能」**（always writeable）とし、書き込みを決して拒否しない 2. **競合解決は読み取り時**に行い、書き込みの複雑さを低減する 3. 競合解決の主体は**アプリケーション**（データストアではなく）に委ねる 4. 漸進的スケーラビリティ・対称性・分散化・異種環境対応を設計原則とする ## 提案手法 ### システムインタフェース `get(key)` と `put(key, context, object)` の 2 操作のみを公開する。キーに MD5 ハッシュを適用して 128 ビット識別子を生成し、担当ノードを決定する。コンテキストにはベクタクロック情報が含まれ、バージョンの妥当性検証に使われる。 ### 一貫性ハッシュ法によるパーティショニング ハッシュ空間をリング状に扱い、各ノードをリング上の位置に配置する。データ項目はキーのハッシュ値の位置から時計回りに最初のノードに割り当てられる。**仮想ノード**（virtual nodes）の導入により、物理ノードがリング上の複数位置を担当し、以下を実現する: - ノード離脱時の負荷の均等分散 - ノード復帰・追加時の均等な負荷引き受け - ノード性能の異種性への対応（高性能ノードに多くの仮想ノードを割り当て） ### ベクタクロックによるデータバージョニング 結果整合性（eventual consistency）を前提に、更新の非同期伝播を許容する。ベクタクロック（`(ノード, カウンタ)` 対のリスト）により、2 つのバージョンが因果関係にあるか並行分岐しているかを判定する。因果的先祖は破棄でき、並行分岐はクライアントに返して意味的調整（semantic reconciliation）を委ねる。ベクタクロックのサイズが閾値（例: 10）を超えた場合は最古のエントリを切り捨てる。 ### スロッピークォーラムとヒンテッドハンドオフ 厳密なクォーラムの代わりに、プリファレンスリストの先頭 N 個の**到達可能な**ノードで読み書きを行う。障害ノードの代わりに別のノードが一時的にレプリカを保持し（ヒンテッドハンドオフ）、元のノードの復帰時に返却する。データセンタ障害に対しては、プリファレンスリストを複数データセンタにまたがるよう構成する。 ### マークル木によるレプリカ同期 永続障害からの回復には、マークル木（ハッシュ木）を用いたアンチエントロピープロトコルを使う。各仮想ノードのキー範囲ごとに独立のマークル木を維持し、ルートハッシュの比較から効率的に不一致キーを特定してバックグラウンドで同期する。 ### ゴシッププロトコルによるメンバーシップ管理 ノードの追加・離脱は明示的な管理操作として行い、ゴシッププロトコルでメンバーシップ変更を伝播する。各ノードは毎秒ランダムなピアと通信し、メンバーシップ変更履歴を調整する。シードノードの仕組みにより論理パーティションを防ぐ。障害検知はローカルな通信失敗に基づく局所的判断で行い、グローバルな障害状態の一致は不要とする。 ## 新規性 1. **既知技術の合成と本番検証**: 個々の技術（一貫性ハッシュ法、ベクタクロック、クォーラム等）は既知だが、それらを単一の高可用システムに統合し、Amazon の厳しい本番環境で検証した初の報告 2. **SLA を 99.9 パーセンタイルで定義・評価**: 平均でなくテイルレイテンシを設計目標とする実践 3. **パラメータ公開設計**: `(N, R, W)` の設定をサービスオーナーに委ね、整合性・可用性・耐久性のトレードオフをアプリケーション単位で制御可能にした 4. **クライアント駆動コーディネーション**: 状態機械をクライアント側に移すことで 99.9 パーセンタイルレイテンシを約 50% 削減 5. **パーティショニング戦略の進化**: 3 つの戦略（ランダムトークン、ランダムトークン+等サイズパーティション、固定トークン+等サイズパーティション）を本番で比較し、戦略 3 が最良と実証 ## 実験設定 - **構成**: (N, R, W) = (3, 2, 2)、数百ノード、均質ハードウェア - **配置**: 複数データセンタに分散、高速ネットワークで接続 - **評価期間**: 2006 年 12 月のピークシーズン（ホリデーショッピング）を含む 30 日間 - **ワークロード**: ショッピングカートサービス（1 日あたり数千万リクエスト、300 万以上のチェックアウト）、セッション管理サービス（数十万の同時アクティブセッション） - **ストレージエンジン**: BDB Transactional Data Store が本番の主流。MySQL、BDB Java Edition、インメモリバッファも利用可能 ## 実験結果 ### レイテンシ性能 - 平均レイテンシは読み書きとも数ミリ秒（クライアント駆動で読み 1.55ms、書き 1.9ms） - 99.9 パーセンタイルは平均の約 1 桁上（サーバ駆動で読み 68.9ms、書き 68.5ms） - クライアント駆動コーディネーションにより 99.9 パーセンタイルを 30ms 以上削減 - 書き込みバッファリングにより 99.9 パーセンタイルを 5 分の 1 に削減（耐久性とのトレードオフ） ### 負荷分散 - 高負荷時の不均衡率は約 10%、低負荷時は約 20% - 戦略 3（Q/S トークン/ノード、等サイズパーティション）が最良の負荷分散効率を達成し、メンバーシップメタデータを戦略 1 の 3 桁削減 ### バージョン分岐 - 99.94% のリクエストが単一バージョンのみを返す - 2 バージョン: 0.00057%、3 バージョン: 0.00047%、4 バージョン: 0.00009% - 分岐の主因は障害ではなく並行書き込み（主に自動化クライアント） ### 全体可用性 - 成功応答率（タイムアウトなし）: 99.9995% - データ損失イベント: 運用期間中ゼロ ## 考察 Dynamo の設計は「**障害は常態であり、障害下でも書き込みを拒否しない**」という Amazon の運用哲学を体現している。結果整合性という一見弱い保証が、実際にはショッピングカートのような重要サービスで 99.94% のリクエストが単一バージョンしか返さないほど、現実の不整合発生率は低い。 `(N, R, W)` パラメータの公開は、データストアの設計を「ひとつの万能解」から「アプリケーション固有の最適化問題」に転換した。これは後年の NoSQL 運動の設計哲学に大きな影響を与えた。 パーティショニング戦略の進化（戦略 1→3）は、本番運用で初めて明らかになる課題（ブートストラップの遅さ、マークル木の再計算コスト、アーカイブの困難さ）から段階的に学んだ過程を示しており、分散システムの実運用知見として価値がある。 フルメンバーシップモデルの限界として、数百ノード規模では動作するが、数万ノードへのスケーリングにはルーティングテーブルの肥大化が課題であり、階層的拡張が必要と認識されている。 ## 強み - Amazon の本番環境での大規模検証データに基づく説得力のある評価 - 設計判断の根拠（なぜ整合性を犠牲にするか、なぜアプリケーション主導の競合解決か）が明確 - パーティショニング戦略の段階的進化を本番データで比較し、実践的な設計指針を提示 - テイルレイテンシ（99.9 パーセンタイル）への注力と、それを実現する具体的最適化手法 ## 弱点・課題 - セキュリティ・認証は対象外（内部の信頼できる環境を前提） - Amazon の事業上の制約から、レイテンシの絶対値やワークロードの詳細が集約値のみの開示 - ベクタクロックの切り捨てスキームが調整効率に与える影響は本番で「問題にならなかった」とされるが、理論的な正確性の分析は不十分 - リレーショナルクエリ・結合・範囲クエリなど複雑な操作は対象外（プライマリキーのみ） - フルメンバーシップモデルは数百ノードまでの設計であり、万ノード規模への拡張は未解決