2023-11-30 ML勉強会

Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service

Introduction

• Amazon DynamoDBについて
• Amazon DynamoDBは、あらゆる規模で迅速かつ予測可能なパフォーマンスをサポートするNoSQLクラウドデータベースサービス
• 2021年のAmazonプライムデーでは、秒間最大8920万リクエストを処理し、高い可用性とパフォーマンスを実現
• DynamoDBは、世界中のデータセンターにある大量のサーバーを使用して何十万もの顧客にサービスを提供するAWSの基盤サービスで、Alexa、Amazon.comサイト、すべてのAmazon配送センターなどの多くの高トラフィックのAmazonプロパティやシステムを動かしている
• さらに、AWS Lambda、AWS Lake Formation、Amazon SageMakerなどの多くのAWSサービスや顧客アプリケーションもDynamoDB上に構築されている
 

• DynamoDBの要件
• DynamoDBが使われているアプリケーションやサービスは、パフォーマンス、信頼性、耐久性、効率性、スケーラビリティの面で要求の厳しい運用要件を持っている
• 特に一貫して低遅延であることは極めて重要であり、中央値的なパフォーマンスよりもすべてのリクエストに対するパフォーマンスが顧客体験を向上させる上で重要
• DynamoDBの設計目標は、すべてのリクエストを一桁ミリ秒の低遅延で完了させること。さらに図1で示すように断続的な機能追加が求められる。
• ここ10年の進化において、オペレーション面での要件に影響を与えることなく、いかにして機能を追加していくかがいちばんの課題

• DynamoDBの6つの基本的なシステム特性
• フルマネージドなクラウドサービス
• ソフトウェアのパッチ適用、ハードウェアの管理、分散データベースクラスターの設定、クラスター運用の管理などは不要
• リソースのプロビジョニング、障害からの自動回復、データの暗号化、ソフトウェアのアップグレード、バックアップの実行などもフルマネージド
• マルチテナントなアーキテクチャ
• 異なる顧客のデータを同じ物理マシンに格納し、リソースの高い利用率を確保
• これにより、コスト削減を顧客に還元することが可能
• リソースの予約、厳密なプロビジョニング、使用量の監により、リソースを共有するテーブルの負荷の分離を行っている
• 強力なスケーラビリティ
• 各テーブルが格納できるデータ量には予め定義された制限はなく、顧客のアプリケーションの需要に応じてテーブルは弾力的に拡大可能
• DynamoDBは必要に応じて、数千ものサーバーにテーブルのリソースを分散させスケールさせることが可能
• DynamoDBは、データストレージ量とスループット要件が増加するにつれて、アプリケーションのデータをより多くのサーバーに分散させる
• 予測可能なパフォーマンス
• GetItemとPutItemによるシンプルな操作で、一貫し低遅延でリクエストに応答することが可能
• 同じAWSリージョンで動作するアプリケーションは、1KBのアイテムに対して、サービス側の遅延は基本的に平均一桁ミリ秒の範囲に収まる
• 最も重要なことは、DynamoDBの遅延が予測可能であることで、テーブルが数メガバイトから数百テラバイトに拡大しても、データの配置とリクエストルーティングアルゴリズムの分散性により、遅延は安定している
• 水平スケーリングを通じて任意のレベルのトラフィックを処理し、アプリケーションのI/Oパフォーマンス要件を満たすためにデータを自動的に分割および再分割する
• 高可用性
• Availability Zoneと呼ばれる複数のデータセンターにデータをレプリケートし、ディスクやノードの障害が発生した場合には自動的に再レプリケーションを行い、厳格な可用性と耐久性の要件を満たす
• 顧客は災害対策として指定したリージョン間でレプリケートされたグローバルテーブルを作成でき、どこからのアクセスでも低遅延を提供できる
• 柔軟なユースケース
• 開発者を特定のデータモデルに制限しない
• DynamoDBのテーブルには固定されたスキーマがなく、各データアイテムが任意の数の属性を異なるタイプで含むことができ、複数値の属性も持たせることができる
• テーブルはキーバリューまたはドキュメントデータモデルを使用し、開発者はテーブルからアイテムをgetする際に強力な一貫性またはeventualな一貫性をリクエストできる

History

• 起源となるDynamo
• DynamoDBの設計は、Amazonで開発された最初のNoSQLデータベースシステムであるDynamoの経験から生まれている（がアーキテクチャは全然違う）
• Dynamoは、ショッピングカートのデータのための高スケーラビリティ、高可用性、高耐久性を備えたkey-valueデータベースのニーズによって作られた
• 創業の初期はAmazonは伝統的なエンタープライズデータベースインスタンスへの直接アクセスを提供していたが、これは接続管理、同時実行ワークロード間の干渉、スキーマアップグレードといった運用に関する問題などに問題があり、スケールのボトルネックになることを学んだ
• そのため、Dynamoではサービス指向アーキテクチャが採用され、アプリケーションのデータをサービスレベルのAPIの背後にカプセル化し、クライアントのリクエストを中断させることなく構成の見直し等を可能にした
• さらに、Dynamoの重要な要件として、アプリケーションがユーザーに一貫した体験を提供できるようにするための予測可能なパフォーマンスがあった。

• Dynamoの限界
• Dynamoの採用はAmazon内のいくつかのユースケースに広がりましたが、Dynamoは依然として自己管理された大規模データベースシステムの運用の複雑さを抱えていた。
• Dynamoはシングルテナントシステムであり、開発チームは自身のDynamoインストールを管理する責任があった
• また、開発チームはデータベースサービスのさまざまな部分について専門家になる必要があり、その結果生じる運用の複雑さは採用の障害となった

• マネージドサービスの開発
• AmazonはDynamoの運用負担を取り除くために新しいサービス（特にAmazon S3とAmazon SimpleDB）を立ち上げ、マネージドで弾力性のある体験を提供するサービスの開発に取り組んだ
• Amazonのエンジニアは、アプリケーションのニーズとより密接に一致していたとしても、Dynamoのような自己管理システムではなく、マネージドで弾力性のあるサービスを好んだ

• SimpleDB
• Amazonからの最初のデータベース・アズ・ア・サービスはSimpleDBで、フルマネージドで弾力性のあるNoSQLデータベースサービスだった
• SimpleDBは、顧客がデータベースを設定、構成、またはパッチを適用する必要なく、マルチデータセンターレプリケーション、高可用性、高耐久性を提供した
• SimpleDBは成功し、多くのアプリケーションを支えましたが、いくつかの制限があった
• テーブルの容量が小さく（ストレージは10GB）、リクエストスループットに制限があったこと
• クエリと書き込みの遅延が予測できなかったこと（すべてのテーブル属性がインデックス化され、書き込みのたびにインデックスを更新する必要があったため）
• これらの制限により、アプリケーションのストレージおよびスループット要件を満たすためにデータを複数のテーブルに分割する必要が発生し、新しい種類の運用負担を開発者にもたらした
• SimpleDBの制限を取り除き、予測可能なパフォーマンスを備えたスケーラブルなNoSQLデータベースサービスを提供するという目標は、SimpleDBの延長的な開発では達成できないと認識した

• DynamoDBの登場
• SimpleDBの課題のより良い解決策は、オリジナルのDynamo設計（インクリメンタルスケーラビリティと予測可能な高パフォーマンス）とSimpleDBの長所（クラウドサービスの管理のしやすさ、一貫性、純粋なキーバリューストアよりも豊かなテーブルベースのデータモデル）を組み合わせること
• これらのアーキテクチャに関する議論は、2012年に公開されたAmazon DynamoDBという新しいサービスに結実した
• Amazon DynamoDBは、Amazon.comで大規模な非リレーショナルデータベースを構築し、AWSで高スケーラビリティと信頼性のあるクラウドコンピューティングサービスを構築する経験から得られたすべての知見の結晶である

Architecture

• キーについて
• DynamoDBのテーブルはアイテムのコレクションであり、各アイテムは属性のコレクションである。
• それぞれのアイテムはprimary keyによってユニークに識別され、テーブル作成時にprimary keyのスキーマを定義する。
• primary keyのスキーマはpartition keyのみの場合とpartition keyとsort key（複合primary key）を持つ場合がある
• partition keyの値はハッシュ関数の入力として使われ、ハッシュ関数の出力とsort keyによってitemがストアされている場所が決定される
• 複合primary keyによって、複数のアイテムが同じpartition keyを持つことができるが、それらは異なるsort keyを持っていなければならない

• セカンダリーインデックス
• DynamoDBはセカンダリーインデックスをサポートしており、高度なクエリをサポートする
• セカンダリーインデックスによって、テーブルのデータをalternate keyを使って検索可能になる

• CRUD操作



• DynamoDBのテーブルでアイテムを読み書きするためにクライアントが利用できる主要な操作には、PutItem, UpdateItem, DeleteItem, GetItemがあり、挿入、更新、または削除する際に、操作が成功するために満たされなければならない条件を指定することも可能
条件式 - Amazon DynamoDB
Amazon DynamoDB は高速なフルマネージド NoSQL データベースをサービスとして提供しており、任意の量のデータの保存と取得、および任意のレベルのリクエストトラフィックの処理を高いコスト効率で簡単に実現できます。
https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/Expressions.ConditionExpressions.html
• DynamoDBはACIDなトランザクションをサポートしており、アプリケーションが複数のアイテムを更新する際に、アトミック性、一貫性、分離性、耐久性（ACID）をアイテム間で確保しながらも、DynamoDBテーブルのスケーラビリティ、可用性、パフォーマンスの特性を担保する

• パーティションとコンセンサス



• DynamoDBはスループットとストレージ要件を満たすために、テーブルを複数のパーティションに分割させる
• 各パーティションは、高い可用性と耐久性のために、いくつかのAvailability Zoneに複数のレプリカを分散させて保持している
• これらのレプリカはレプリケーショングループを形成し、リーダーの選出とコンセンサス形成にはMulti-Paxosを採用しており、リーダーレプリカのみが書き込みと強い一貫性のある読み取りリクエストを処理できる。レプリケーショングループの任意のレプリカは最終的に一貫性のある読み取りを提供する
• 書き込みリクエストを受け取ると、対象キーのレプリケーショングループのリーダーはwrite-ahead logのレコードを生成し、ピア（レプリカ）にそれを送信する
• 書き込みのリクエストは、ピアの定足数がログレコードをローカルのwrite-ahead logに持続させたのち、アプリケーションに対して適用される





• レプリケーショングループは、write-ahead logsとkey-valueデータを格納するBツリーを含むストレージレプリカで構成されている（図2）。可用性と耐久性を向上させるために、レプリケーショングループには、Bツリーを持たず、直近のwrite-ahead logsのエントリのみを持続させるレプリカも存在（図3）し、ログレプリカと呼ばれる。
• DynamoDBの構成



• DynamoDBは数十のマイクロサービスで構成され、メタデータサービス、リクエストルーティングサービス、ストレージノード、オートアドミンサービスなどが主要なサービスとなっている（図4）
• メタデータサービス
• 特定のテーブルやインデックスに対するテーブル、インデックス、およびレプリケーショングループのルーティング情報を保存する
• リクエストルーティングサービス
• 各リクエストの認証、認可、および適切なサーバーへのルーティングを担当する。例えば、すべての読み取りおよび更新リクエストは、顧客データをホストするストレージノードにルーティングされる。リクエストルーターはメタデータサービスのルーティング情報を参照する。すべてのリソース作成、更新、データ定義のリクエストはオートアドミンサービスにルーティングされます。
• ストレージサービス
• ストレージノードのフリートに顧客データを保存する責任を持つ。各ストレージノードは、異なるパーティションの多くのレプリカをホストする。
• オートアドミンサービス
• DynamoDBの中枢神経系として構築されており、フリートのヘルチェック、パーティションのヘルチェック、テーブルのスケーリング、すべてのコントロールプレーンリクエスト(APIリクエスト)の実行を担当する。このサービスは、すべてのパーティションの健康状態を継続的に監視し、不健全と判断されたレプリカ（反応が遅い、応答しない、不良なハードウェア上でホストされているなど）を交換する。また、DynamoDBのす
• すべてのコアコンポーネントのヘルスチェックを行い、故障しているまたは故障したハードウェアを交換する。
• 例えば、オートアドミンサービスがストレージノードが不健全であると検出した場合、そのノード上でホストされているレプリカを交換してシステムを安定した状態に戻す回復プロセスを開始する

Journey from provisioned to on-demand

• 初期のパーティション
• DynamoDBのローンチ時には、テーブルの容量とパフォーマンスを動的にスケールする方法として、パーティションを導入
• 初期のDynamoDBリリースでは、顧客はテーブルが必要とするスループットを読み取り容量ユニット（RCU）と書き込み容量ユニット（WCU）という形で明示的に指定するようにした
• 例えば、4KBまでのアイテムに対して、1RCUは1秒に1回の強い一貫性のある読み取りリクエストを実行でき、1KBまでのアイテムに対して、1WCUは1秒に1回の標準的な書き込みリクエストを実行できます。
• RCUとWCUは合わせてプロビジョンドスループットと呼ばれた
• 当初のシステムは、テーブルを複数のストレージノードにまたがって分割し、それらのノード上で利用可能なスペースとパフォーマンスを管理した
• そして、テーブルの需要が変化する（サイズが増大するか負荷が増加するなど）につれて、パーティションを再分割させることで、テーブルを弾力的にスケールさせた
• パーティションによる抽象化は非常に有用であり、DynamoDBの設計において中心的な役割を続けているが、この初期バージョンでは、個々のパーティションの容量とパフォーマンスの割り当てに課題が生じた
• アドミッションコントロール（入場制限）





• DynamoDBは、特定のストレージノードに負荷が集中することを防ぐために、顧客にのリクエストのスループットに制限を設け、ノード内に共存する別テーブルのパーティションとの干渉を防いでいる
• ストレージノードは、ローカルに格納されたパーティションの割り当てに基づいて、独立してアドミッションコントロールを行なっている。ストレージノードは複数のテーブルからパーティションをホストするため、各パーティションに割り当てられたスループットは、ワークロードを分離するために使用された。
• DynamoDBは、単一のパーティションに割り当てることができる最大スループットに上限を設け、ストレージノードがホストするすべてのパーティションの合計スループットが、そのストレージドライブの物理的特性によって決定されるノード上で許可される最大スループット以下であることを保証した
• パーティションに割り当てられたスループットは、テーブル全体のスループットが変更されたり、パーティションが子パーティションに分割されたりした際に調整される
• サイズのためにパーティションが分割されると、親パーティションに割り当てられたスループットは子パーティション間で均等に分割される。
• スループットのためにパーティションが分割されると、新しいパーティションはテーブルのプロビジョンドスループットに基づいてスループットが割り当てられる。
• 例
• パーティションが最大1000 WCUのプロビジョンドスループットを受け入れると仮定
• 3200 WCUでテーブルが作成された場合、DynamoDBはそれぞれ800 WCUが割り当てられる4つのパーティションを作成する
• その後、テーブルのプロビジョンドスループットが3600 WCUに増加した場合、各パーティションの容量は900 WCUに増加する
• また、テーブルのプロビジョンドスループットが6000 WCUに増加した場合、パーティションは分割され、8つの子パーティションが作成され、各パーティションに750 WCUsが割り当てられる
• そして、テーブルの容量が5000 WCUに減少した場合、各パーティションの容量は675 WCUに減少する
• キーレンジでの非一様なアクセスパターン
• テーブル内のパーティション間でスループットが均等に分配されるのは、アプリケーションがテーブル内のキーに一様にアクセスし、パーティションのサイズのために分割することがパフォーマンスを均等に分割するという仮定に基づく
• しかし、実際はアプリケーションのワークロードはしばしば時間やキーレンジにわたって非一様なアクセスパターンを持つことがわかった
• テーブル内のリクエストレートが非一様の場合、パーティションを分割し、パフォーマンス割り当てを比例的に分配しても、パーティションのホットな部分の利用可能なパフォーマンスが分割前よりも少なくなる可能性もある
• スループットは静的に割り当てられ、パーティションレベルで実施されていたため、これらの非一様なワークロードは、テーブルの総プロビジョンドスループットが十分であっても、アプリケーションの読み書きが拒否される（スロットリングと呼ばれる）ことが時々発生した


• 課題
• アプリケーションが最も一般的に直面する課題の2つは、ホットパーティションとスループットの希薄化
• ホットパーティションは、トラフィックがテーブルの一部のアイテムに一貫して集中するアプリケーションにて発生。
• スループットの希薄化は、サイズが原因でパーティションが分割されたテーブルで一般的に発生し、パーティションのスループットが新しく作成された子パーティション間で均等に分割されるので、パーティションごとのスループットが減少する
• スロットリングを経験した顧客は、テーブルのプロビジョンドスループットを増やして対処するが、すべての容量を使用しないため、テーブルは過剰にプロビジョンされることになる
• テーブルに対する適切なパフォーマンスプロビジョニングレベルを見積もることが難しいため、顧客体験は決して良くはなかった
• アドミッションコントロールの最初の改善
• Bursting



• パーティションが非一様なアクセスを受けているという発見から、さらにすべてのパーティションが同時に割り当てられたスループットを使用しているわけではないこともわかった
• DynamoDBはパーティションレベルでの一時的なワークロードの急増を吸収するためにBurstingの概念を導入。
• Burstingの背後にある考え方は、短期間のスパイクを吸収するために、アプリケーションがパーティションレベルで未使用の容量を最大限に活用可能にすること
• DynamoDBは、パーティションの未使用容量の一部を後のスループットの急増に備えて最大300秒間保持し、消費された容量がパーティションのプロビジョンド容量を超えたときにそれを活用できるようにした（burst capacity）
• この容量はストレージノード上で複数のトークンバケットを使用して管理
• 各パーティションに対して2つ（割り当てられたものとバースト用）とノード全体に対して1つ
• リクエストがストレージノードに到着した場合、パーティションの割り当てられたトークンバケットにトークンがあれば、リクエストは許可され、パーティションおよびノードレベルのバケットからトークンが差し引かれる
• パーティションがプロビジョンドトークンを使い果たした後、バーストトークンバケットとノードレベルのトークンバケットの両方にトークンがある場合にのみ、リクエストがバーストを許可
• また、読み取りリクエストはローカルのトークンバケットに基づいて受け入れられ、バースト容量を使用する書き込みリクエストには、パーティションの他のメンバーレプリカのノードレベルのトークンバケットに対する追加のチェックが必要
• パーティションのリーダーレプリカは定期的に各メンバーのノードレベル容量に関する情報を収集する
• アダプティブキャパシティの導入
• DynamoDBは、パーティション間でアクセスパターンが大きく偏っているワークロードなど、バースト容量で吸収できない長期にわたるスパイクをより効果的に吸収するために、アダプティブキャパシティを導入
• アダプティブキャパシティは、すべてのテーブルのプロビジョンド容量と消費容量を監視
• スロットリング発生時にテーブルレベルのスループットまでは超過していない場合、比例制御アルゴリズムを使用してテーブルのパーティションに割り当てられたスループットを自動的に増加（ブースト）させる
• スロットリング発生時にテーブルレベルのスループットを超過している場合、ブーストを受けたパーティションの容量は減少される
• これにより、偏ったアクセスパターンによるスロットリングの99.99%以上を排除した
 
• グローバルアドミッションコントロール（GAC）の導入
• バースティングとアダプティブキャパシティの課題
• バースティングとアダプティブキャパシティを用いて非一様アクセスのスループット問題を大幅に軽減できたが、これらのソリューションには限界があった
• バースティングは短期間のトラフィックスパイクにのみ有効であり、ノードがバーストをサポートするスループットを持っている場合に依存する
• アダプティブキャパシティはスロットリングが観察された後にのみ機能するため、テーブルを使用するアプリケーションが既に短期間の非利用状態に陥っていることになる
• アドミッションコントロールは分散され、パーティションレベルで実行されていたが、アドミッションコントロールをパーティションから取り除き、パーティションが常にバーストできるようにしながらワークロードの分離を提供することが有益であると認識した。
• グローバルアドミッションコントロール（GAC）





• アドミッションコントロールの問題を解決するために、DynamoDBはアダプティブキャパシティをグローバルアドミッションコントロール（GAC）に置き換えた
• GACサービスは、トークンという形でテーブル容量の総消費量をグローバルに管理し、各リクエストルーターはアドミッション決定を行うためのローカルトークンバケットを持ち、定期的に（数秒単位で）GACと通信して時間制限付きトークンを補充する
• アプリケーションからのリクエストが到着すると、リクエストルーターはトークンを差し引き、最終的に消費または有効期限によりリクエストルーターのトークンがなくなると、リクエストルーターはGACからトークンを補充する
• GACインスタンスは、クライアントが提供した情報を使用してグローバルトークン消費量を推定し、残っているトークン量を加味して次の時間単位に利用可能なトークンを配布する
• これにより、アイテムの一部分にのみトラフィックを送信する非一様ワークロードでも、最大パーティション容量まで実行することが可能になる
• グローバルアドミッションコントロール方式に加えてパーティションレベルのトークンバケットも防御的な役割として設置されており、1つのアプリケーションがストレージノード上の多くのリソースを消費しないように制限されている
• レプリカ間で費された容量のバランス
• バーストしまくったらノードのキャパ超える可能性がある
• パーティションが常にバーストできるようにするために、DynamoDBはバースト容量を効果的に管理する必要が出てきた
• DynamoDBはさまざまなハードウェアインスタンスタイプで実行され、これらのインスタンスタイプはスループットとストレージ能力によって異なる
• また、同じノード内のparition同士は全く関連がなく、異なる顧客の異なるトラフィックのpartioionが共存している
• よって、可用性、予測可能なパフォーマンス、セキュリティ、弾力性などの重要な特性を侵害しないようにpartitionが共存できるレプリカをインスタンスに割り当てる仕組みが必要（コロケーション）
• partitionごとに割り当てられた容量を超えなければ管理はラクだが、バースティングによりストレージノードは所定の容量を超える可能性があり、テナントのコロケーションは複雑化した
• ゆえに、ノードの全体的なプロビジョンド容量より大きな容量でレプリカは作成する
• さらに、DynamoDBは、容量が逼迫したレプリカによって引き起こされる可用性リスクを軽減するために、スループット消費とストレージに基づいてストレージノード全体で割り当てられたパーティションを事前にバランスさせるシステムを実装
• 各ストレージノードは、独立してそのホストするすべてのレプリカの全体的なスループットとデータサイズを監視
• スループットがノードの最大容量の閾値パーセンテージを超えた場合、現在のノードから移動する候補パーティションレプリカのリストをオートアドミンサービスに報告
• オートアドミンは、そのパーティションのレプリカを持っていない同じまたは別のAvailability Zoneにある新しいストレージノードを見つける
• Splitting for consumption
• グローバルアドミッションコントロール（GAC）とパーティションが常にバーストできる能力があっても、特定のアイテムセットにトラフィックが偏っている場合、テーブルはスロットリングを経験する可能性がある
• DynamoDBは消費されたスループットに基づいて自動的にパーティションをスケールアウトさせる
• パーティションの消費スループットが一定の閾値を超えるとパーティションが分割
• キーレンジ内の分割点は、パーティションが観測したキーの分布に基づいて選択
• キーの分布はアプリケーションのアクセスパターンの代理として機能し、キーレンジを中央で分割するよりも効果的
• パーティションの分割は通常数分のオーダーで完了するが消費のための分割から利益を得られないワークロードのクラスも存在する
• たとえば、単一のアイテムに高いトラフィックを受けているパーティションや、キーレンジが順次アクセスされるパーティションは、分割から利益を得ることはできない
• このようなケースもDynamoDBは検出し、パーティションの分割を避ける
• オンデマンドプロビジョニング
• 急激なワークロードの顧客体験を向上させるために、オンデマンドテーブルを導入
• オンデマンドテーブルは、顧客がテーブルの適切なプロビジョニングを見極める負担を取り除く
• DynamoDBは、読み取りと書き込みのシグナルを収集することによってオンデマンドテーブルをプロビジョニングし、テーブルの前回のピークトラフィックの最大2倍までを即座に対応できる
• アプリケーションがテーブルの前回のピーク以上の容量を必要とする場合、DynamoDBはトラフィック量が増加するにつれて自動的により多くの容量を割り当て、ワークロードがスロットリングを経験しないようにする
• オンデマンドは消費のためにパーティションを分割することでテーブルをスケールします。分割決定アルゴリズムはトラフィックに基づいてる
• GACによって1つのアプリケーションがすべてのリソースを消費しないかを監視・保護することを可能にするが、消費された容量に基づいてバランスをとる能力は、オンデマンドテーブルのパーティションがノードレベルの制限に直面することなく、知的に配置されることを意味する