はじめに
USENIX カンファレンスで公開された Amazon DynamoDB に関する論文を読んでみたので主にアーキテクチャ周りの内容のメモ書きです。
https://www.usenix.org/system/files/atc22-elhemali.pdf
メモ
- DynamoDB は複数のマイクロサービスから構成される
- 他のAWSサービス(主に認証周り)も使っている
- IAM, KMS など... これらに問題があった場合も DynamoDB 自体が動作できるように工夫されている
- データの分散管理の仕組みでは、DynamoDBテーブルは内部的にはパーティションという論理的な領域に保持されており、それらは各 AZ のストレージノードへ分散して配置され、データは PK をベースに各パーティションへ分散して保存されるので、フルスキャンみたいなことをするといろんなAZのデータを拾ってくる必要がある、と思うとなんとなくコストがかかるというのがイメージはできた
- DynamoDB はサービスに影響を与えないような(ユーザー側からはDynamoDBの更新に伴うメンテナンス対応などはない)デプロイとなるよう仕組みの工夫が行われている。
- Read-Write Deploy と書かれており、最初にメッセージの読み取りをできるようにして、全てのノードでそれが完了したら送信をできるようにするといった感じのようで、ローリングアップデートっぽい感じのように思われた。またデプロイを一気にやるのではなく、一部に適用して徐々に全体に適用したり、テストについてもアップグレードおよびダウングレードのテストを行なっている
## アーキテクチャ * ストレージの構成 * 高可用性と耐久性を実現するために、異なるアベイラビリティー ゾーンにレプリカを作成する。 * レプリカは、レプリケーショングループという単位を形成し、Multi-Paxosのアルゴリズムで、レプリカの中から Leader を選出する。 * レプリケーショングループは、先行書き込みログ(WAL)と、データを格納する B ツリーの両方を含むストレージレプリカで構成される。 * 可用性と耐久性を向上させるために、レプリケーショングループには最近のWALのみを保持するレプリカも存在する。 * Leader となったレプリカのみが、書き込み要求と強整合性読み取り要求を処理できる。 * 書き込み要求を受信した場合、Leader はWALを生成し、それをレプリカに送信する。各レプリカでクォーラムが形成されるとWALを永続保存され、書き込みが成功したことをアプリケーションに知らせる * 読み取りの場合は結果整合性。 * レプリケーショングループの Leader は、リース(Amazon で採用されているリーダー選挙メカニズム)メカニズムを使用している。 レプリケーショングループの Leader がそのピアのいずれかによって障害が検出された (異常または使用不可と見なされた) 場合、ピアは新しい Leader として自分自身を選択するための新しいラウンドの選択を提案できる。 新しいLeaderは、前のLeaderのリースが期限切れになるまで、書き込みまたは一貫した読み取りを提供しない * DynamoDB 自体の構成 * 下記のような複数のマイクロサービスで構成される。 * メタデータ サービス * 特定のテーブルのキーのテーブル、インデックス、およびレプリケーション グループに関するルーティング情報を格納する。 * リクエストルーティング サービス * リクエスト ルーティング サービスは、各リクエストの承認、認証、および適切なサーバーへのルーティングを担当する。たとえば、すべての読み取りおよび更新要求は、顧客データをホストするストレージ ノードにルーティングされる。メタデータ サービスからルーティング情報を検索します。 すべてのリソースの作成、更新、およびデータ定義の要求は、autoadmin サービスにルーティングされます * ストレージノード * ストレージノードにデータを格納する役割。 各ストレージノードは、DynamoDB テーブルの多数のパーティション、多数のレプリカをホストする。 * autoadmin サービス * DynamoDB のコアとなるサービス。 フリートの正常性、パーティションの正常性、テーブルのスケーリング、およびすべてのコントロール プレーン リクエストの実行を担当します。 このサービスは、すべてのパーティションの正常性を継続的に監視し、異常 (遅い、応答がない、または不良なハードウェアでホストされている) と見なされたレプリカを置き換えます。 このサービスは、DynamoDB のすべてのコア コンポーネントのヘルス チェックも実行し、故障している、または故障したハードウェアを交換します。 たとえば、autoadmin サービスは、ストレージ ノードが異常であることを検出すると、そのノードでホストされているレプリカを置き換える回復プロセスを開始して、システムを安定した状態に戻します。 * その他 * ポイントインタイムリストア、オンデマンドバックアップ、更新ストリーム、グローバルアドミッションコントロール、グローバル テーブル、グローバルセカンダリインデックス、トランザクションなどの機能をサポート ## プロビジョニングからオンデマンドへの変遷 * パーティション * DynamoDB の初期の段階ではテーブルが必要とするスループット(読み取りキャパシティーユニット (RCU) と書き込みキャパシティーユニット (WCU) ) をユーザーが明示的に指定していた。 * その頃は、テーブル作成時にパーティションが割り当てられ、パーティションは複数のストレージノードで分散して管理され、各ストレージノードで、使用可能なストレージ領域とパフォーマンスの両方を管理できるようにする、といった形だったらしい。 * テーブルに対する要求が変化した場合 (サイズが大きくなった、または負荷が増加した、等)、パーティションをさらに分割・移行し、テーブルを柔軟にスケーリングできるようになっていた * admission control * ユーザーが必要とするスループットを担保するために、ストレージノードの負荷状況や、ストレージノード内の各テーブルのパーティションを管理するもの * パーティション間のスループットの均一な分散は、アプリケーションがテーブル内のキーに均一にアクセスし、パーティションをテーブルサイズで分割することでパフォーマンスも均等に分割される、という前提に基づいていたが、実際にはさまざまなアクセスパターンがあり、十分なパフォーマンスが出ない状態も発生した * このような性能問題が起きた場合、RCU, WCU のプロビジョニング値を増やしてその値内で収まるようにする必要があった。 * admission controlの改善 * ストレージノードにホストされている全てのパーティションが、割り当てられたスループットを同時に使用している訳ではなかった。そのため、パーティションごとのワークロードの一時的なスパイクを吸収するために、バーストの概念を導入した。 * これにより、ストレージノード内での未使用の容量をベストエフォートで利用して短期的なスパイクを捌けるようにした * つづいて、パーティション間でアクセス パターンが大きく偏っているワークロードに対応できる Adaptive capacity という概念が導入された * テーブル全体のスループットを超えていない場合、比例制御アルゴリズムを使用して、特定のパーティションに割り当てられたスループットが自動的に増加 (ブースト) される * Global admission control * admission controlの改善を図ったが限界があった * バーストは、トラフィックの一時的なスパイクにのみ役立ち、バーストをサポートするノードに依存していた。 * Adaptive capacity スロットリングが発生した後にのみ開始される形であり、短い時間ではあるものの性能問題は起こりえた * admission controlを削除して、global admission control に置き換えた * テーブル容量の総消費量をトークンで一元的に追跡する * 各リクエストルーターはローカル トークン バケットを維持してアドミッションの決定を行い、GAC と通信して定期的な間隔 (数秒程度) でトークンを補充する * GAC はトークンの消費状況から、アクセスを均等に分散されるようにトークンを管理・発行するらしい * GAC は、クライアントの要求からオンザフライで計算された一時的な状態を維持する * サービスの全体的な運用に影響を与えることなく、各 GAC サーバーを停止および再起動する * リクエスト ルーターは、複数の期限付きトークンをローカルで管理する * アプリケーションからのリクエストが到着すると、リクエスト ルーターはトークンを消費するので、枯渇したら、リクエストルーターは GAC に追加のトークンをリクエストする * GAC インスタンスは、クライアントから提供された情報を使用して、グローバルトークンの消費量を推定し、次回の時間単位で利用可能なトークンを、トークン全体のクライアントのシェアする * 消費容量のバランス調整 * DynamoDB は、さまざまなハードウェアインスタンスタイプで実行される。 * EC2 を指しているのか単純に言葉通り専用のハードウェアなのか不明 * 最新世代のストレージノードは、数千のパーティションレプリカをホストしている。 * 単一のストレージノードでホストされているパーティションは、まったく関連性がなく、異なるテーブルに属している可能性があります。 * ストレージノード上の複数のテーブルからのレプリカをホストする * 各テーブルは異なるユーザーからのものであり、さまざまなトラフィックパターンを持つ * これには、可用性、予測可能なパフォーマンス、セキュリティ、弾力性などの重要なプロパティに違反することなく安全に共存できるレプリカを決定する割り当てスキームを定義することが含まれます。 * スループットの消費とストレージに基づいてストレージノード全体に割り当てられたパーティションのバランスを事前に調整するシステムを実装し、密集したレプリカによって引き起こされる可用性のリスクを軽減した。 * 各ストレージ ノードは、ホストされているすべてのレプリカの全体的なスループットとデータ サイズを個別に監視します。 * スループットがノードの最大容量のしきい値パーセンテージを超えている場合、現在のノードから移動する候補パーティションレプリカのリストが autoadmin サービスに報告されます。 * autoadmin は、このパーティションのレプリカを持たない同じまたは別のアベイラビリティーゾーンで、パーティションの新しいストレージ ノードを見つけます。 ## 耐久性と正確性 * コミット後にデータが失われることはないが、実際には、ハードウェア障害、ソフトウェア バグ、またはハードウェア バグが原因でデータ損失が発生する可能性はある * DynamoDB は、潜在的なデータ損失を防止、検出、および修正するメカニズムを備えているため、高い耐久性を実現するように設計されている * ハードウェア障害 * DynamoDB も RDBMS と同じく、先行書き込みログ(WAL)があり、耐久性とクラッシュ リカバリを提供するための重要な役割となる * WAL はS3 にも定期的にアーカイブされており、最新のものは各レプリカの中に持っている * ノード障害が発生すると、そのノードでホストされているすべてのレプリケーショングループが 2 つコピーされる。 * 修復プロセスには B ツリーと先行書き込みログのコピーが含まれるため、ストレージ レプリカの修復プロセスには数分かかることがある * 異常なストレージ レプリカが検出されると、レプリケーション グループのリーダーはログ レプリカを追加して、耐久性に影響を与えないようにします。 * ログ レプリカの追加には数秒しかかかりません。これは、システムが正常なレプリカから B ツリーを使用せずに新しいレプリカに最近の先行書き込みログのみをコピーする必要があるためです。 * したがって、ログ レプリカを使用して影響を受けたレプリケーション グループを迅速に修復することで、最新の WR の高い耐久性が保証されます。 * データの誤り * 一部のハードウェア障害により、誤ったデータが保存されることがあり、検知が難しい。 * DynamoDB はチェックサムを多用してこれらのエラーを検出する * DynamoDB は、すべてのログ エントリ、メッセージ、およびログ ファイル内でチェックサムを維持することにより、2 つのノード間のすべてのデータ転送のデータ整合性を検証する * これらのチェックサムは、エラーがシステムの残りの部分に広がるのを防ぐためのガードレールとして機能する * たとえば、ノードまたはコンポーネント間のすべてのメッセージに対してチェックサムが計算され、検証される * これは、これらのメッセージが宛先に到達する前にさまざまな変換レイヤーを通過する可能性があるため * このようなチェックがないと、レイヤーのいずれかでサイレント エラーが発生する可能性がある * 継続的な検証 * DynamoDB は、保管中のデータも継続的に検証します。 * 私たちの目標は、システム内のサイレント データ エラーやビット腐敗を検出することです。 * このような継続的な検証システムの例は、スクラブ プロセスです。 スクラブの目的は、ビットの腐敗など、予期していなかったエラーを検出することです。 * スクラブ プロセスが実行され、次の 2 つのことが検証されます。 * レプリケーション グループ内のレプリカの 3 つのコピーすべてが同じデータを持ち、ライブ レプリカのデータが、 アーカイブされた先行書き込みログ エントリを使用してオフラインで構築されたレプリカのコピーと一致することです。 * アーカイブされたログを使用してレプリカを構築するプロセスは、以下のセクション 5.5 で説明されています。 * 検証は、ライブ レプリカのチェックサムを計算し、それを S3 でアーカイブされたログ エントリから生成されたスナップショットと照合することによって行われます。 * スクラブ メカニズムは、ライブ ストレージ レプリカと、テーブルの開始からのログの履歴を使用して構築されたレプリカとの間の相違を検出するための多層防御として機能します。 * これらの包括的なチェックは、実行中のシステムに信頼を与える上で非常に有益です。 * グローバル テーブルのレプリカを検証するために、同様の継続的検証手法が使用されます。 * 何年にもわたって、保存データの継続的な検証が、ハードウェア障害、サイレント データ破損、さらにはソフトウェア バグから保護するための最も信頼できる方法であることを学びました。 * ソフトウェアのバグ * DynamoDB は、複雑なサブストレート上に構築された分散キー値ストアです。 * 複雑さが増すと、設計、コード、および操作における人的エラーの可能性が高くなります。 * システムのエラーは、データの損失や破損を引き起こしたり、お客様が依存する他のインターフェース契約に違反したりする可能性があります. * 形式的な方法 [16] を広く使用して、レプリケーション プロトコルの正確性を保証します。 * コア レプリケーション プロトコルは、TLA+ [12、13] を使用して指定されました。 * レプリケーション プロトコルに影響を与える新しい機能が追加されると、仕様に組み込まれ、モデルがチェックされます。 * モデル チェックにより、コードが本番環境に入る前に、耐久性と正確性の問題につながる可能性のある微妙なバグを発見することができました。 * S3 [6] などの他のサービスでも、同様のシナリオでモデル チェックが役立つことがわかっています。 * また、展開されたすべてのソフトウェアの正確性を確保するために、広範な障害挿入テストとストレス テストを採用しています。 * データ プレーンのレプリケーション プロトコルのテストと検証に加えて、正式な方法を使用して、コントロール プレーンと分散トランザクションなどの機能の正確性を検証しています。 * バックアップと復元 * DynamoDB は、物理メディアの破損から保護するだけでなく、お客様のアプリケーションのバグによる論理的な破損から保護するためのバックアップと復元もサポートしています。 * バックアップまたは復元は、S3 にアーカイブされた先行書き込みログを使用して構築されるため、テーブルのパフォーマンスや可用性に影響しません。 * バックアップは、最も近い秒まで複数のパーティション間で一貫しています。 * バックアップは DynamoDB テーブルの完全なコピーであり、Amazon S3 バケットに保存されます。 * バックアップからのデータは、いつでも新しい DynamoDB テーブルに復元できます。 * DynamoDB はポイントインタイム リストアもサポートしています。 * ポイントインタイム リストアを使用すると、過去 35 日間に存在したテーブルの内容を、同じリージョン内の別の DynamoDB テーブルにリストアできます。 * ポイントインタイム リストアが有効になっているテーブルの場合、DynamoDB はテーブルに属するパーティションの定期的なスナップショットを作成し、S3 にアップロードします。 * パーティションのスナップショットが作成される周期は、そのパーティションに蓄積された先行書き込みログの量に基づいて決定されます。 * スナップショットは、先行書き込みログと組み合わせて、ポイントインタイム リストアを行うために使用されます。 * テーブルのポイントインタイム リストアが要求されると、DynamoDB はテーブルのすべてのパーティションについて、要求された時刻に最も近いスナップショットを特定し、 * ログをリストア要求のタイムスタンプまで適用し、テーブルのスナップショットを作成します。 そしてそれを復元します ## 可用性 * 高可用性のために、DynamoDB テーブルはリージョン内の複数のAZに分散・複製される * ノード、ラック、ZA障害の回復力に対する定期的なテストを実施する * DynamoDB は、ノード、ラック、および AZ の障害に対する回復力を定期的にテストします。 * たとえば、サービス全体の可用性と耐久性をテストするために、電源オフ テストが実行されます。 * 現実的にシミュレートされたトラフィックを使用し、ジョブ スケジューラを使用してランダム ノードの電源をオフにします。 * すべての電源オフ テストの最後に、テスト ツールは、データベースに保存されているデータが論理的に有効であり、破損していないことを確認します * 書き込みと一貫した読み取りの可用性 * 書き込み可用性は、健全な Leader と健全な書き込みクォーラムで成り立つ * 書き込みクォーラムは、異なる AZ にある 3 つのレプリカのうちの 2 つから構成されるらしい * 書き込みクォーラムと Leader に十分な正常なレプリカがある限り、パーティションは引き続き使用可能 * 最小クォーラムを達成するために必要な数のレプリカが使用できない場合、パーティションは書き込みには使用できなくなる * レプリカの 1 つが応答しない場合、Leader はログレプリカをグループに追加する * ログレプリカを追加することがグループの書き込みクォーラムが常に満たされるようにする最速の方法らしい * これにより、異常な書き込みクォーラムによる書き込みの可用性の中断が最小限に抑えられる * Leader レプリカは一貫した読み取りを提供する * ログ レプリカの導入はシステムに大きな変化をもたらした * 正式に証明された Paxos の実装により、システムを安全に調整して実験し、より高い可用性を実現する自信が持てた。 * ログレプリカを使用して、1 つのリージョンで何百万もの Paxos グループを実行することができた * 結果整合性のある読み取りは、どのレプリカでも処理できる * Leader レプリカに障害が発生した場合、他のレプリカがその障害を検出し、新しい Leader を選択して、一貫した読み取りの可用性の中断を最小限に抑えられる * 障害検出 * 高可用性システムの重要なコンポーネントの 1 つは、Leader の障害検出 * グループのすべてのレプリカがリーダーへの接続を失う障害ではうまく機能する * ただし、定義が曖昧なネットワーク的な要害だと問題が発生する * このため、フェイルオーバーを発生させるような異常が検出された場合、他のレプリカに、Leader と通信できるかどうかを確認する処理を行う * そのレプリカが、Leader から正常なメッセージの応答ができた場合、フェイルオーバーを発生させないようにする。 * DynamoDB で使用される障害検出アルゴリズムのこの変更により、システム内の誤検知の数が大幅に最小限に抑えられたため、誤ったリーダー選出の数が減少された * 可用性の測定 * DynamoDB は、グローバル テーブルで 99.999% の可用性、地域テーブルで 99.99% の可用性を実現するように設計されている * 可用性は、成功した DynamoDB によって処理されたリクエストの割合をもとに 5 分間隔ごとに計算される * デプロイ * メンテナンス ウィンドウを必要とせずに裏側でサイレントにデプロイされる * DynamoDB は定期的にソフトウェアの更新が行われているらしい * 何年にわたる複数のデプロイを経験してさまざまな改善がおこわれたらしい。 * DynamoDB は、すべてのデプロイの前にコンポーネント レベルで一連のアップグレードおよびダウングレード テストを実行している * 次に、ソフトウェアは意図的にロールバックされ、機能テストを実行してテストされる * 分散システムであるため、デプロイ時には新旧のバージョンが並行稼働する状態になる * この場合、新しいバージョンのもので処理可能なリクエストが古いバージョンの方にいった場合に問題が起こりうる * DynamoDB は、Read/Write デプロイという形でこの種の変更を処理する * Read/Write デプロイは、複数のステップからなるプロセスとして完了します。 * 最初のステップは、ソフトウェアを展開して、新しいメッセージ形式またはプロトコルを読み取る * すべてのノードが新しいメッセージを処理できるようになると、ソフトウェアが更新されて新しいメッセージが送信される * 新しいメッセージは、ソフトウェアの展開でも有効になる。 * Read/Write デプロイにより、両方のタイプのメッセージがシステム内で共存できることが保証される * ロールバックの場合でも、システムは古いメッセージと新しいメッセージの両方を処理できる * すべてのデプロイは、ノードのフリート全体にプッシュする前に、少数のノード セットで行われる * この戦略により、デプロイの失敗による潜在的な影響が軽減される * DynamoDB は、可用性メトリクスにアラームしきい値を設定する * 展開中にエラー率または遅延がしきい値を超えると、システムは自動ロールバックをトリガーする。 * ストレージ ノードにソフトウェアを展開すると、可用性への影響を回避するように設計されたリーダー フェイルオーバーがトリガーされる * リーダーのレプリカはリーダーシップを放棄するため、グループの新しいリーダーは古いリーダーのリースが期限切れになるのを待つ必要がない * 外部サービスへの依存 * 高可用性を確保するには、リクエストパスで DynamoDB が依存するすべてのサービスを DynamoDB よりも高可用性にする必要がある。 * DynamoDB が依存しているサービスに障害が発生した場合でも、DynamoDB は動作を継続できる必要がある * DynamoDB がリクエストパスに依存するサービスの例には、AWS Identity and Access Management Services (IAM) や、 顧客キーを使用して暗号化されたテーブルの AWS Key Management Service (AWS KMS)などがあるとのこと。 * DynamoDB は、IAM と AWS KMS を使用して、すべての顧客のリクエストを認証する * これらのサービスは高可用性ですが、DynamoDB は、これらのサービスが利用できない場合でも動作するように設計されている * IAM と AWS KMS の場合、DynamoDB は静的に安定した設計を採用しており、依存関係が損なわれてもシステム全体が動作し続ける。 おそらくその依存関係が配信したはずの更新された情報を認識していないだろうとのこと。 * ただし、依存関係が損なわれる前のすべての機能は、依存関係が損なわれても引き続き機能する。 * 多分下位互換が保たれるようになっているのだと思われる * DynamoDB キャッシュは、すべてのリクエストの認証を実行するリクエストルーターの IAM および AWS KMS からの結果をキャッシュする * DynamoDB は、キャッシュされた結果を定期的に非同期で更新する * IAM または KMS が利用できなくなった場合、リクエストルーターはキャッシュされた結果を事前に決められた期間使用し続ける * キャッシュされた結果を持たないリクエストルーターに操作を送信するクライアントは、影響を受けるが、AWS KMS または IAM が損なわれた場合の実際の影響は最小限とのこと * キャッシュによる応答時間も改善される。システムの負荷が高い場合に特に有効。 * メタデータの可用性 * リクエストルーターが必要とする最も重要なメタデータの 1 つは、テーブルの主キーとストレージノード間のマッピング * DynamoDB は DynamoDB 自体にメタデータを保存する * このルーティング情報は、テーブルのすべてのパーティション、各パーティションのキー範囲、およびパーティションをホストするストレージ ノードで構成されている * ルーターは、これまで見たことのないテーブルに対する要求を受信すると、テーブル全体のルーティング情報をダウンロードして、ローカルにキャッシュ * パーティションのレプリカに関する構成情報はめったに変更されないため、キャッシュヒット率は約 99.75% * 欠点はキャッシングによってな動作が導入されることです。 * リクエストルーターのキャッシュが空のコールドスタートの場合、すべての DynamoDB リクエストはメタデータルックアップになるため、サービスは DynamoDB と同じレートでリクエストを処理するようにスケーリングする必要がある * この効果は、リクエスト ルーター フリートに新しい容量が追加されたときに実際に観察されている * 場合によっては、メタデータ サービスのトラフィックが最大 75% まで急増することがある * そのため、新しいリクエスト ルーターを導入すると、パフォーマンスが低下し、システムが不安定になる可能性がある * さらに、効果のないキャッシュは、データのソースが過度の直接負荷からフォールオーバーするため、システムの他の部分にカスケード障害を引き起こす可能性がある * DynamoDB は、顧客のリクエストのレイテンシーに影響を与えることなく、リクエスト ルーターやその他のメタデータ クライアントのローカル キャッシュへの依存を取り除き、大幅に削減したいと考えていました。 * 要求を処理するとき、ルーターは要求のキーをホストするパーティションに関する情報のみを必要とする * そのため、テーブル全体のルーティング情報を取得するのは無駄でした。特に多くのパーティションを持つ大きなテーブルの場合 * メタデータのスケーリングと可用性のリスクを費用対効果の高い方法で軽減するために、DynamoDB は MemDS と呼ばれるインメモリ分散データストアを構築した * MemDS はすべてのメタデータをメモリに保存し、MemDS フリート全体に複製する * 水平方向にスケーリングして、DynamoDB の受信リクエスト レート全体を処理する * データは高度に圧縮されている : (云々)
参考
- USENIX ATC '22 | USENIX
- Amazon DynamoDB Under the Hood: How We Built a Hyper-Scale Database (DAT321) - AWS re:Invent 2018 | PPT
- AWS re:Invent 2018: Amazon DynamoDB Under the Hood: How We Built a Hyper-Scale Database (DAT321) - YouTube
- アベイラビリティーゾーンを使用した静的安定性
- パーティションとデータ分散 - Amazon DynamoDB
- 10歳の誕生日おめでとう – DynamoDB | Amazon Web Services ブログ
- Amazon Prime Day 2022 – AWS for the Win! | AWS News Blog
- https://assets.amazon.science/ac/1d/eb50c4064c538c8ac440ce6a1d91/dynamo-amazons-highly-available-key-value-store.pdf
- 分散システムのリーダー選挙