論文メモ Dynamo: Amazon's Highly Available Key-value Store

November 6, 2020

Amazonで社内運用されている高可用性のKVS, Dynamoのアーキテクチャを解説している。 まぎらわしいが、Dynamoは、AWSサービスのDynamo DBとは違う*。 Dynamoは、リーダーレスレプリケーションモデルで、Dynamo DBはシングルリーダレプリケーションモデルを採用している。 Dynamoは、高信頼性が必要なシステムの状態管理に使用される。 その用途から、トランザクション分離レベルのサポートは不要で、可用性を優先するために結果整合性を許容する。

整合性を維持するには、いつ、何が、不整合を解消するか決めなくてはならない。 Dynamoは、書込みの高可用性を重視し、障害時でも書込みを受理する。 論文では、ショッピングカートにいつでも商品を追加できることがUXの質につながることを引き合いに、高可用性のある書込みの需要を説得している。 ノードやクライアントは、読み込み時に、書込みで生じた不整合の解決をはかる。 書き込まれるオブジェクトを版管理し、不整合時はクライアントに履歴を返し、クライアント-側のドメイン知識をかりて不整合を解決する。 以下の表は、解決すべき諸問題に対するDynamoの技術や、その利点をまとめている。

techniques

Partitioning

オブジェクトを格納するノードは、コンシステントハッシュ法で決め、ノードの増減時のキーの再配置に必要な計算を抑える。 はじめに、無作為に比較可能なハッシュ値をノードに割りあてる。 ハッシュ値の昇順にノードを並べ、最大のハッシュ値のノードと最小のノードを隣接させるとノードを円環上に配置できる。 オブジェクトは、そのキーのハッシュ値から円環を時計回りにたどり、最初にみつかるノード、キーのハッシュ値よりも大きくノードのハッシュ値で最小値もつノードに格納される。 ただし、Dynamoは、ノードのスペックで負荷分散するために、1つのノードに対して性能にあわせて複数のハッシュ値を与える。 これにより所持するハッシュ値の数で管理するオブジェクトの数を制御する。

High Availability for writes

Dynamoは版管理にベクトルクロックをもちいる。 ここでのベクトルクロックは、ノードとカウンタのペアのリストである。 次の図は、オブジェクトに生じた半順序の書込みイベントをベクトルクロックで管理した様子である。 オブジェクトの最新の状態をノードが解決できないときは、変更履歴がクライントに提示される。 クライアントは、履歴の中から更新したい状態を選び、整合性を回復する。

version

Handling temporary failures

ノードの障害に備えて、複数のノードにオブジェクトを保存する。 オブジェクトを格納したノードは、時計周りの方向に近い順に複数のノードにオブジェクトを複製する。 複製を渡す対象のノードが一時的な障害で応答できなければ、時計回りをすすめて、応答を返すノードにオブジェクトを複製する。 障害から復帰したら複製されたオブジェクトを復帰したノードに転送する。

Recovering from permanent failures

複製の不整合を効率よく解消するために、ノードが管理するオブジェクトをMerkle木で管理する。 Merkle木では、キーのハッシュ値を葉、子ノードのハッシュ値を連結後ハッシュ化した値を親ノードをする。 これにより、木の一部だけを比べれば、ノード間のオブジェクトの不整合を検知できるようになり、不整合検知のためのノード間のデータの転送量を抑えられる。

Membership and failure detection

あるノードが同じクラスタに存在するか、また、クラスタに存在するが障害により通信できない状態にあるかを判断しなければならず、その解決にゴシッププロトコルがもちいられる。