論文DynamoDB 2022に関するいくつかのメモ

※このブログは2022年8月12日に公開された英語ブログ「Some Notes on the DynamoDB 2022 Paper」の拙訳です。

著者: Ed Huang (PingCAP共同創設者兼CTO)
編集者: Fendy Feng, Tom Dewan

DynamoDBが論文を発表してから長い時間が経ちました。数日前、私はその新しく出版されたもの「Amazon DynamoDB:スケーラブルで予測可能なパフォーマンスとフルマネージドのNoSQLデータベースサービス」を読みましたが、エンジニアリングの観点から、大規模分散システムに関する近年の最も実用的な論文の1つだと思いました。アーキテクチャについては、その必要がないためあまり詳細に説明されていません。シェアードナッシングシステムは似ており、著者はこの論文の読者がどのような人かを正確に分かっています^_^。さらに、論文は簡単に書かれており、数式はありません！

結局のところ、DynamoDBは何かを「証明」しようとする必要はありません。過去10年間で、規模と安定性の両方の点で完全に証明してきました。論文は比較的新しいにも関わらず、あまり多くのブログでその論文について語られていないことに気がついたので、何か書いてみようと思います。

予測可能なパフォーマンス > 高性能

これはこの投稿における最初のポイントです。最近TiDB Cloudを構築したときに最も深く感動したポイントでもあります。私はいつも、不安定な速さよりも安定した遅さが良いと信じています。99パーセンタイルの遅延時間は平均遅延時間に比べて、よりシステム設計スキルが反映されます。

これが意図的なものかどうかはわかりませんが、DynamoDB 2022の論文の最初のセクションにも掲載されているので、その重要性がわかります。

DynamoDBは、予測可能なパフォーマンスを提供したいと考えています。最初のステップは、読み込みキャパシティーユニット (RCU) と書き込みキャパシティーユニット (WCU) の概念を導入して、ワークロードを抽象化することです。実際、RCUとWCUは従来の意味でのクエリ/秒 (QPS) に非常に近く、ターゲット項目の指標のみが加算されるため、比較的正確なワークロード計画を実行できます。たとえば、1WCU=1KB項目の1QPSです。ユーザーがワークロードをRCUとWCUの観点から記述できれば、予測可能性への最初のステップは完了です。DynamoDBのスケジューラは、さまざまなモデルのハードウェア機能がWCUとRCUの組み合わせに単純に抽象化されているため、事前パーティショニングやリソースの事前割り当てなど、多くのことを実行できます。

各パーティションのクォータがわかったら、おそらくスケジューリングのナップサック問題になります。DynamoDBは、同じマシンのパーティションのクォータの合計を考慮します。その合計は、パーティションのクォータを割り当てるときにマシンが提供できるRCUまたはWCUの合計よりも、論文に記載されている例では約20%〜30%小さくする必要があります。現実の世界では、経験の浅い開発者やシステム管理者は通常、「究極の」パフォーマンスを追求するために、マシンからCPUとI/Oの最後のビットまで絞り出します。CPU使用率が100%になるまで彼らは満足しません。ただし、そのような場合マシンはすでに非常に不健康な状態にあります。スループットが向上する可能性がありますが、リクエストのロングテールレイテンシーがとても増えることになり、この不安定なロングテールのためにユーザーの観点から観察されるパフォーマンスは「予測不可能」になります。運用環境では、同じ理由でマシンの約30%をオーバープロビジョニングすることをお勧めします。

バーストは単純なアイデアです。クォータを割り当てるとき、DynamoDBはパーティションごとにある程度のキャパシティを予約します。トラフィックが短期間に急増すると、予約キャパシティが使用されます。アダプティブキャパシティは、ユーザーのワークロードが変動した後、さまざまなパーティションのクォータを動的に調整します (ただし、合計量がテーブルの合計クォータを超えることはできません) 。

バーストキャパシティとアダプティブキャパシティはユーザーのワークロードがあまり変化しないことを前提としていること、また、フロー制御はパーティションレベル (ほぼストレージノードレベル) 、つまりローカルスケジューリングに重点を置いていることに注意することが重要です。

大規模なストレージシステムでは、フロー制御は実際には全体的な問題です。TiDB を例にとると、TiDBのSQLレイヤーはステートレスです。リクエストは、TiDBのストレージサーバーであるTiKVに転送されます。TiDB SQLレイヤーは一種の「リクエストルーター」 (論文の用語を使用) ですが、複数のTiDB SQLノードが展開されている場合、フロー制御はTiKV (ストレージレイヤー) でのみ実行されます。極端な場合、TiDB SQLノードは、過負荷のTiKVノードにリクエストでヒットし続ける可能性があります。この問題を解決するには、TiDBレイヤーでフロー制御を実行し、TiDBレイヤーのクライアントに直接エラーを返し、過負荷のTiKVノードに侵入しないようにする必要があります。

この部分はDynamoDBの論文では少し曖昧です。私の理解では、リクエストルーターは定期的に要求クォータをグローバルアドミッションコントロール (GAC) に適用します。GACはグローバル割り当てポリシーを管理しており、パーティションが過負荷になっている場合、応答するリクエストルーターは顧客へのサービスを直接拒否して、システムの残りの部分を保護することができます。パーティションレベルでのフロー制御は、ノードレベルでの最後の防衛線としても保持されます。

シェアードナッシングストレージシステムの場合、スケールアウトの鍵はシャーディング戦略です。DynamoDBは、TiKVと同様に動的シャーディング戦略を選択しています。範囲分割も使用しますが、違いは、TiKVのリージョン (DynamoDBのパーティションの概念と同様) がデフォルトの分割しきい値としてサイズを使用することです。TiDB 6.0ではロードベーススプリット戦略が導入され、DynamoDBはロードベーススプリットを直接採用しています。パーティションには既定のスループットしきい値があり、この値を超えると分割されます。キー範囲にわたる負荷分散の状態の監視を開始することで、最適な分割ポイント (必ずしも中間点であるとは限りません) を簡単に取得できます。

もう一つの重要な分割概念は、いつそれを避けるべきかということです。論文は次のように述べています。

• 既知の単一行ホットスポット
• アクセスパターンがキーの順番 (Keyの反復に似ています) 。この場合、DynamoDBは分割を回避します。

要約すると、DynamoDBの予測可能なパフォーマンスの中核は次のとおりです。

• 単純なトランザクション/秒 (TPS) 、QPS、およびデータサイズではなく、ワークロード (WCUおよびRCU) のより正確な抽象化を使用
• クォータをパーティションに事前に割り当て、フローを厳密に制限
• 予期しないシナリオ (バースト) の一時的なリソースプールとしてノードレベルでの余裕を持たせる
• トラフィックのスケジューリングにグローバル情報を使用し、すべてのレベルでフローを制御

観測可能な影響が最小なフェイルオーバー

まず、先行書き込みロギング (WAL) について説明します。DynamoDBは、TiKVと同様に、分散コンセンサスアルゴリズム (DynamoDBの場合はMulti-Paxos、TiKVの場合はRaft) を介して、ログを複数のレプリカに複製します (論文によるとデフォルトは3です) 。ただしDynamoDBは、耐久性を高めるために、WAL (DBスナップショットではない) をS3に定期的に同期します。これは耐久性を高めるためだけでなく、ポイントインタイムリカバリ (PITR) のためでもあると理解しています。

フェイルオーバーに関するもう1つの興味深い詳細は、DynamoDBのレプリケーショングループ内のノードに障害が発生した場合、たとえば3つのコピーのうちの1つに障害が発生した場合、グループリーダーがただちにログレプリカをレプリケーショングループに追加することです。ログレプリカは、実際には私たちがしばしば立会人と呼ぶものです。以下、ログレプリカは立会人とします。立会人は、ログのみを保存し、サービスを提供しないノードです。実際、これは非常に賢いアプローチです。なぜなら、上記のケースでは過半数を満たしているにもかかわらず、現時点ではシステムが非常に脆弱であるためです。

新しいメンバーを完全に復元するには、パーティションスナップショットが比較的大きい場合は特に時間がかかります (最初にDBスナップショットをコピーしてから、最近のログを適用します) 。スナップショットをコピーするプロセスでは、既存のピアに余分な負荷がかかる可能性があります。

立会人の追加は低コストです。論文に記載されている時間は秒単位です。少なくとも、データ復旧中のログのセキュリティを確保できます。さらに、クロスアベイラビリティーゾーン (AZ) デプロイシナリオでは、この最適化により、フェールオーバーフェーズでの書き込みレイテンシーも削減できます。たとえば2つのAZがあり、そのうちの1つがプライマリとします。これをAZ-Aと呼び、メインの書き込みトラフィックを伝送します。別のAZであるAZ-Bは、ディザスタリカバリのスタンバイです (またはローカル読み取りトラフィックを処理します) 。AZ-Aのノードがハングしても、このノードのデータのRaftグループは書き込みを停止しません (リーダーの再選択後) 。しかし従来のRaftによると、過半数の要件を満たすにはAZ-Bのピアに要求し、ログが正常に保持されることを確認する必要があります。その後、成功をクライアントに返すことができ、パフォーマンスの揺らぎがクライアントから観察されます (AZ-Aの新しいピアが追加されるまで) 。ノードの障害を検出し、AZ-A内の正常なノードを立会人としてすぐに見つけて、この障害グループに追加すると、AZ-Aへの書き込みが引き続き過半数を達成できるため、AZ-Bへのログの同期の待ち時間が節約されます。クライアントの観点から見ると、システムには重大な揺らぎは見られません。

DynamoDBのフェイルオーバー処理

フェイルオーバー中に観察可能な影響を軽減するために、DynamoDBではレプリケーショングループのリーダー選択も改善されています。大規模なシステムでは、ネットワークの揺らぎまたはネットワーク分断は特別なことではありません。たとえば、レプリケーショングループにピアXというピアがあるとします。Xがグループリーダーに接続できなくなると、従来のリーダー選出プロトコルに従って、Xはより大きな期間で新しい選出を急いで開始します。他のピアはそれに投票するのをやめます。ユーザー側から見ると、一部のデータは利用できませんが (データの整合性のために選出中はサービスが停止します) 、古いリーダーはまだ生きている可能性があります。

これはよくある問題ですが、解決策は非常に簡単です。TiKV 2.1では、Prevoteと呼ばれる最適化が導入されました。ピアがリーダー選出を開始したい場合、最初に他のピアに投票するかどうかを尋ね、以前のリーダーが生きているか利用可能であるかを確認します。そうでない場合、ピアは新しいリーダー選出を開始できます。DynamoDBの論文でも、同様のメカニズムについて言及しています。ピアが新しいリーダー選出を開始する前に、他のピアに古いリーダーが切断されていると思うかどうかを尋ね、そうでない場合は、候補者自身の問題であり、通常のノードに影響を与えないことを意味します。

DynamoDBのリーダー選出プロセス

大規模システムの最悪の障害は、連鎖障害です。2015年のDynamoDBの障害は典型的なものです。この論文で言及されたメタデータサービスの改善は、このケースを思い出させます。 (おそらくこのケースのせいで、それらの改善が行われたと思います) 解決策は非常にインテリジェントなので、少し言い換えます。

DynamoDBは、連鎖障害の根本原因の1つが短期間でのトラフィックの突然変異であることを観察しました。トラフィックの突然変異を引き起こす一般的な要因の1つは、キャッシュの障害です。私たちはキャッシュヒット率が高いほど良いと考えていますが (論文ではパーティションルーターテーブルのキャッシュヒット率は約99.75%であると述べています) 、このような高いキャッシュヒット率は、キャッシュ障害(またはキャッシュエラーが発生した場合に多数の新しいノードが参加するときのキャッシュ暖気フェーズ)発生時、メタデータサービスは400倍のトラフィック量 (最悪の場合0.25%→100%) を処理できなければなりません。DynamoDBは、次の方法でこの問題を解決します。

1. DynamoDBは、リクエストルーターとメタデータサービスの間に、分散メモリキャッシュMemDSのレベルを追加します。リクエストルーターのローカルキャッシュが失われた後、メタサービスに直接アクセスせず、最初にMemDSにアクセスします。次に、MemDSはバックグラウンドでメタデータサービスにアクセスし、データを入力します。ピークシェービングのためにキャッシュの層を追加することは、一般的な方法である保険の層を追加することと同じです。
2. 2番目の方法は非常に賢い方法です。先ほどリクエストがMemDSのキャッシュにヒットしなかった場合、リクエストルーターはMemDSを通じてメタデータを取得すると述べました。これはわかりやすいですね。しかし、本当に賢いのはキャッシュがヒットした場合でも、MemDSはメタデータサービスにも非同期でアクセスすることです。理由は次のとおりです。

• MemDS内の既存のキャッシュができるだけ早く更新されるようになります
• メタデータサービスに”安定した”トラフィックがもたらされます (ただし、トラフィックは大きくなる可能性があります) 。

“安定した”トラフィックが多いということは、たとえるならば、洪水が来たときに自信を持てるように、水で遊んでいるのと同じです。🙂

　3. 限られたトークン (容量) に基づくGACは、連鎖障害の影響を軽減します。

さらに、クラウド上のサービスの大きな利点の1つは、従来のエンタープライズソフトウェアよりも早くアップデートがリリースされることです。ただし、新しいリリースのデプロイメントは通常、システムの最も脆弱な時期であり、DynamoDBは大規模システムとしてオフライン更新を行う可能性は低いです。ローリングアップデートの場合、アップデートプロセス中にノードの古いバージョンと新しいバージョンが共存します。したがって、新しいバージョンは古いバージョンで実行されているノードと通信し、すべてのノードが新しいバージョンをデプロイした後に新しいプロトコルに切り替える必要があります。

安定性とフェイルオーバーに関するDynamoDBの取り組みは、一言で要約できます。それは、目に見えるクライアント側の影響を最小限に抑えることです。これは、”予測可能”なパフォーマンスの一部であると私は考えています。

データベース≠サービスとしてのデータベース

10年前の論文に記載されていたDynamoのほうがDBに近いと思います (笑) 。現在のDynamoDBは、実際にはサービスとしてのデータベース (DBaaS) です。何が違うのかと疑問に思うかもしれません。DBaaSの構築とは、単に複数のデータベースインスタンスをクラウドにデプロイしてホストすることではないと思います。ユーザーの観点から見ると、DBaaSによって提供されるエンドポイントはデータベースインスタンスのように機能しますが、内部では実装はそれほど単純ではない場合があります。極端な例を挙げてみましょう。DBaaSがSQLiteをサービスとして提供するとします。実際にすべてのユーザーに対して新しいコンテナを作成し、環境をプロビジョニングし、SQLiteプロセスを開始して公開するということは考えにくいと思います。これは共有サービスである可能性が高く、リソースをより有効に活用するために外部ではSQLiteと同じように動作するだけです。

したがって、DBaaSを構築するには、まずマルチテナンシーを考慮する必要があります。DynamoDBを再設計する必要がある理由は、古いDynamoがマルチテナントをサポートしていないためです。これはクラウドサービスでは受け入れられません。TiDBがクラウドに移行していたとき、クラウドネイティブとは単にデータベースをクラウドに移動し、それをさまざまなユーザー向けに展開することではないことを学びました。クラウドによって提供される機能と環境のカーネルから制御プラットフォームまでの大幅な変革が必要です。

DBaaSとデータベースのもう1つの大きな違いは、DBaaSはローカルにデプロイするのが難しいことが多いことです。実際、最新のDBaaSは多くのマイクロサービスで構築されているか、クラウドベンダーが提供する機能 (特にストレージとセキュリティ関連のサービス) に大きく依存しています。DynamoDBの論文では、リクエストルーターがサービスであり、さまざまなテナントからの接続を担当することもわかります。GACはサービスです。認証システムはサービスです。メタデータはサービスです。そしてストレージはサービスです。S3/IAMなどの他のサービスへの依存関係については言うまでもありません。興味深いのは、この論文ではEC2やEBSについてまったく言及されていないことです。これによりDynamoDBのハードウェアインフラストラクチャはおそらく独自に維持されているのではないかと推測できます。つまり、ベアメタルマシン上で実行されているということです。

学んだこと

TiDBの場合、DynamoDBよりも少し複雑な問題を抱えています。結局のところ、TiDB CloudはSQLサービスを提供します。たとえば、ユーザーがSELECT * FROMを入力した場合、RCUを計算するのは困難です (特にTiDBが処理をプッシュダウンするため) 。ただし、この計算は不可能ではありません。もしかしたら、将来このトピックについて書くことができるかもしれません。TiDB Cloudは最近、制御プラットフォームを独立したサービスとして分離し、セッション管理サービス (DynamoDBのリクエストルーターと同様) をTiDBのカーネルコードベースから分離しました。したがってDynamoDBの論文は、クラウドデータベースを構築するためのアンバンドリングとマイクロサービス変革の道の重要性についての私たちの判断を裏付けるものです。

最後に、この論文からの私の要点を以下に示します。

• ワークロードの抽象化を理解すればするほど、より適切に予測可能なシステムを構築することができます。ワークロードの測定が細かくなるほど、収益を得る (またはコストを節約する) 余地が大きくなります。
• システムのマルチテナンシーを最初からグローバルな観点から検討してください。
• クラウドでは、アクセス層が非常に重要です。フロー制御、高可用性、テナントの分離、無停止アップデートなど、システムの予測可能性を向上させるためにアクセス層でできることはたくさんあります。
• スケジューリングの抽象化のために、異なる層でフロー制御を行います。
• マルチテナンシーを実現するプラットフォームを構築するために、マイクロサービスを使用します。
• クラウドインフラストラクチャを使用すると、S3などの作業が大幅に節約されます。

この論文を読んだ後、サーバーレスアーキテクチャ、GC戦略、分散トランザクション (ACID) など、取り上げていないことがたくさんあると感じましたが、だからといってこの論文が古典であることを止めるものではありません。この論文から多くのことを学びました。このブログの読者の中にDynamoDBチームのメンバーがいたら、ぜひお知らせください。喜んでビールをおごります。 (ベイエリアにいる場合😉)

こちらもお読みください
実世界のHTAP：TiDBとSingleStore、そのアーキテクチャを考察
コードを変更せずにSaaSプラットフォームを1日で5倍高速化
より良いGitHubインサイトツールを1週間で作る？実話