発明のための再発明

内部動作のような、プログラムを書くときの参考になることを書きます

Dynamo: Amazon’s Highly Available Key-value Store

はじめに

AmazonがDynamodbを紹介した論文を読んだ。
2007年のもので、NoSQLブームの走りとなったものだったと思う。
コンピュータ・サイエンス関係の「おすすめの論文」のようなもので、よくおすすめされるので読んでみたが、意外と面白かったので、面白かった場所に焦点を当てて書く。
ただし、現在は、AWSのサービスとして提供されていて機能追加も多いのでこの論文とは大きく異なると思われるので注意が必要。

Dynamodbとは

Amazonが開発したNoSQLで、高可用性KVS。
論文上では99.9995%のリクエスト返答成功率と、データロス無しという、数字を出している。

https://aws.amazon.com/jp/dynamodb/
を読むと、概要がわかりやすいだろう。

Dynamo で使われている技術 (4章)

4章では、主要技術を5つ挙げている。

  1. Consistent hasing
    データ分割のアルゴリズムとして、Consistent hashingを採用している。
    また、キーが偏らないように Virtual node を使い単一ホストに対する複数キーの設定を設定している。
    ただ、単純には行かなかったようで、後半で試行錯誤を書いている。

  2. Versioning
    Vector clockを採用し、順序が確定する場合には最新の情報を返す。
    更新要求が成功したからと言って、dynamoが更新された情報を返すわけではなく、古いデータを取得することが有りえる。
    そのため、同一データに対して同時に更新する可能性があり、不整合が発生しうる。その場合は復元を行う(後半に詳細が有る)
    さらに、vectorが大きくなるのを抑えるために、古い情報は捨てている。

  3. Sloppy quorum and hinted handoff
    (W: Writeが成功する時の最低ノード数) + (R: Read時のデータ取得対象ノード数) > (N: レプリケーションノード数)
    になるようにして、Quorumのようになっている。
    書き込み対象が落ちている場合は、別ノードにデータが書き込まれる。復旧したら、データを戻した後にデータを消す(hinted hand off)。
    ちなみに、W, Rのノード数を変えることで、個々のサービスの要求を満たすことが出来るようになっている。
    例えば6章に、商品情報や宣伝のサービスではW=N,R=1にして高速で動作するようにしているとしている。(更新が圧倒的に少ないのでこういう設定が可能)

  4. Anti-entropy using merkle tree
    Merkle tree を使うことによって差分を高速に発見し、そこだけデータ同期を行う

  5. Gossip based membership protocol and failure detection
    GossipでノードやConsistent hashのリング情報などを共有している
    Seedsというリング上の全てのノードを知っているノードがいて、全ノードがそれらに合わせるので、分断は起きない。

バージョン差異が見つかった場合の修復方法 (6章冒頭)

Versioningでバージョンの不整合があるので、それをどのように治すかという問題を解説している。
不整合に対する対応では、サービスの性質に応じて3種類の方法を用いている。

  1. クライアント(アプリ側)が独自のビジネスロジックで治す (例: カート情報)
  2. 最新の更新日付を持つバージョンを使用する (例: セッション情報)
  3. R=1,W=Nにして、そもそもバージョン差異に気づかないようにする。(例: 商品情報や宣伝のサービス)

ちなみに、全リクエスト中に複数バージョンが見つかった割合は

  • 0.00057%で2つのバージョン
  • 0.00047%で3つ
  • 0.00009%で4つ

と、少ない(6.3章)

Consistent hasingのキーの割当に用いた戦略について (6.2章)

Consistent hashは工夫が合ったようで、3種類の戦略を取ったらしい。
下に論文にある図を置く
f:id:mrasu:20180910002502j:plain

戦略1. ノードに対してランダムなtokenを割り当てて、token間のデータを各ノードが持つデータとする

Consistent hasingを素直に実装した初期の戦略。
ただ、この戦略には、以下の問題があった

  1. ノードが増えたときには必ずデータ移動が発生し、移動対象データの全スキャンが走るので重い
    それに対応するために、データ移動を優先度最低のバックグラウンドタスクとして、移動完了後にノードを追加するようにした。そのために、ノード追加の時間が長かった
  2. Merkle tree の再計算が必要
  3. データの存在するノードが変動する可能性が有るので、全体バックアップを取るのに苦労した

これら問題の本質は、

  1. データの分割箇所(partition)(上図の網掛け部分)の決定
  2. データを配置する配置ノード(上図のA,B,C)の決定

という選択を同時に変更してるところから発生している。
例えば、「リクエストが多いからノードを追加しよう」と思ってもデータの分割箇所の変更が発生していた。

戦略2. 事前にpartionを均等なQ個に分割し、partitionを配置するノードは後から割り当てる

バックアップやMerkle treeの問題は、ノードが保持するデータが変わるために発生する問題だったので、保持データが変わらないようにしている。
partition内のデータを保持するノードを決定する際には、リングの位置を表すtokenを各ノードに割り当てて、partitionに最も近いtokenを持つN個のノードへpartitionのデータが配置される。
これによって、

  • (戦略1で問題だった)partitionと配置ノードが同時に変わる問題を解決
  • partitionを動的に変えられる

という利点が有る。

戦略3. Q個の均等なpartionに分割し、各ノードに割り当てるpartitionも確定する

2番めの戦略を進めて、割り当てるpartitionのノードを固定している。
そのために、

  • ノードが無くなる場合には、消えたノードのpartitionを別のノードへ割り当てる
  • ノードを追加する場合には、既存のノードに割り当てられたpartitionを新規ノードに移動させる

となり、2で発生していた、ノードが保持するpartitionが変わる問題が解消された。
ちなみに、3つの戦略における負荷の偏りを測ると、3が最良で2が最悪となった。(2が遅い理由はみつからなかった)

3番目の戦略の良いところはデプロイが簡単になったところ。
簡単になった理由は、

  • partitionの範囲が固定されていてノードが保持するpartitionも固定されるおかげで、ノードのbootstrapや復元が早くなる (partitionの範囲が動的だとランダムアクセスになる)
  • アーカイブが簡単 (partitionの範囲が固定されるので)

ただし、ノード管理の手間は増えるという欠点が有る。

まとめ

以上、Dynamoの古い論文を読んだ。