会社で行っている輪読会でDynamoの論文を読んだので、そのために取ったメモを若干整形してまとめた。

Dynamoの論文は2007年にAmazonから発表されたNoSQLの先駆け的な論文で、現代の分散系システムに関連する色々な技術について触れられているため、とても勉強になった。

自己流の解釈がそこそこ入ってしまっていると思うので、正確な理解のためには元の論文を参考にしていただくと良いと思います。

また、論文を読むに当たっては@imai_factoryさんのまとめをとても参考にさせていただきました、ありがとうございました。

Dynamoの概要

Dynamoとは？

100%書き込み可能でスケーラブルな分散型NoSQL
- NoSQLの先駆け
- Amazonプラットフォームで実際に使われていた内製の技術
可用性を一番の売りにしている
- Amazonのproduction環境での実用に耐えうるパフォーマンス等の条件を満たしながら、可用性を最大限確保した技術

Dynamoが生まれた背景

Amazonが自社のプラットフォームを支えるデータストアに求める厳しい要件を満たすために生まれた
Amazonがデータストアに求める要件
- 信頼性
  - 信頼性を損ねれば経済的損失が大きいため
- スケーラビリティ
  - プラットフォームの成長を支えるため

信頼性（可用性）とは

ここで言う信頼性とは、障害が起きても変わらずサービスを提供できること
- 障害とはサーバの故障やネットワークの不通など
- データストアを構成する各要素の部分的な障害が起きるのは避けられないことで、その上でデータストア全体としては常にサービスを維持したい、ということ
- よって、SPOFは存在してはならない

customers should be able to view and add items to their shopping cart even if disks are failing, network routes are flapping, or data centers are being destroyed by tornados.

RDBでは駄目なのか

RDBが必要ないというわけではないが、伝統的なRDBでは以下の点でAmazonプラットフォームのニーズとマッチしなかった

高価なハードウェアや高い人的運用スキルを必要とすること
- 高度な機能を提供するがゆえのコスト
- 多くのサービスにおいてRDBが提供する高度な機能は必要ない
可用性よりも整合性を重視していること
スケールアウトが難しいこと

Dynamoが設定したゴール

高可用性
- Amazonの厳格なSLAを満たすもの
スケーラビリティ
- システムが大きくなるにつれてスケールアウトできなくなるような事態は避ける
効率性
- コモディティでの動作

SLA(Service Level Agreements)

サービス側とクライアント側で合意しているサービス品質に関する約束

具体例

ピーク時クライアントが毎秒500requestsをするときに、99.9%は300ms以内にレスポンスできるようにする

これを「レスポンスの99.9パーセンタイルが300ms以内である」と言う
一般的にはSLAの指標として平均値や中間値が使われることが多いが、Amazonではパーセンタイルを使用している。その理由として、一部ではなく全てのユーザに対して良い体験を提供することが必要であるから、と書かれている。

Dynamoの設計

先述した「Dynamoが設定したゴール」を満たすために、どのような設計を取り入れたか

設計概要

シンプルなインターフェース(KVS)
- unique keyに対応する単オブジェクトのread, writeのみ
  - オブジェクトは大体１メガバイト以下
ACID特性の放棄
- いわゆるトランザクションは提供しない
- 理由としては、ACID特性、特に強整合性（一貫性）を保つことが可用性を損ねるため
- Dynamoでは代わりに以下の仕様にしている
  - single keyのみでのアップデートを許可
  - 結果整合性のみの提供

整合性について

（メモ）いわゆるCAPの定理のC(整合性、Consistency)とA(可用性、Availability)について。一般的にCAPの定理だと3つのうち2つを選ぶ、という議論がされがちだが、実際には整合性と可用性にはそれぞれ度合いがあり、どちらを諦めるというよりはどちらを優先するか、という方が正しそう（CAP定理を見直す。“CAPの3つから2つを選ぶ”という説明はミスリーディングだった）

整合性と可用性のトレードオフ

一般的なデータストアでは、レプリケーションがデータの耐久性のために必須
レプリケーションを行う場合、データの更新が行われた時に、データの不整合が生じないように一時的にデータをロックしてしまう
- 「データのロック＝不可用」であるため、可用性を損なうことになる
結果整合性を許容することにより、データの更新が行われた時でも、レプリカと更新を完全に同期させる必要がなくなるため、可用性を損なうことが無くなる

結果整合性を達成するために考慮すべきこと

整合性に常に付きまとう課題がコンフリクトの解決方法である

データストアでは、同じデータに対する異なる更新の衝突が発生することがある
整合性を保つには、衝突の解決をいつ(when)誰が(who)行うか考える必要がある

WHEN

伝統的なdata storeではwrite時に衝突を解決する
Dynamoではread時に解決する
- 常に書き込み可能とするため、現実的にwrite時の衝突解決が不可

WHO

データストア側・クライアント側のどちらでもよい
- データストア側で行う場合、衝突の解決方法は単純化(例: last write wins)するしか無いが、実装が楽
- クライアント側で行う場合、衝突の解決方法を柔軟に選択できるが、クライアント側でロジックを実装する必要がある

その他の設計方針

Symmetry(対称性)
- 各ノードが同じ役割を担う
- これにより、システムのprovisioningとmaintenanceがシンプルになる
Decentralization(分散)
- 対称性と似ているが、中央管理ではなくpeer-to-peerライクな設計にする
- これにより、スケーラビリティと可用性が増す
Heterogeneity（不均一性）
- 各ノードのリソースが均一でなくてもよい設計にする
- これにより、スケールアウトだけでなくスケールアップも容易になる

Dynamoの仕組み

先述した設計をもとにしたDynamoの実際のシステムアーキテクチャについて。コアな部分のみ解説されている（それでも多いが）

システムインターフェース

get(key)

Read処理。通常は単一のオブジェクトを返す
複数バージョンが衝突している場合はcontextと共に複数バージョンのオブジェクトのリストを返す
- おそらく衝突をクライアント側で解決する設定の場合の仕様

put(key, context, object)

Write処理。
contextとはオブジェクト（value）のメタデータであり、バージョン情報などを含むが、呼び出し側からは隠蔽(opaque)されている
Dynamoはオブジェクトとキーについてはopaque array of bytesとして扱う（データの型を考慮しない）
キーはそのまま使うとオブジェクトの配置が偏るので、内部ではMD5ハッシュをかけている

パーティショニングアルゴリズム

データをどのように各ノード（サーバのことだが、DynamoはP2Pライクな設計なので本論文では基本的にノードと書かれている）に割り振るかを決定するアルゴリズム

incrementalなスケールを実現するために、コンシステントハッシュ法を採用している
- 前提条件
  - キーとスロット（ノードの場所）にはそれぞれハッシュ値が存在し比較可能
- キーの追加方法
  - キーのハッシュ値以上のもので最小のハッシュ値を持つスロットに割り当てる
  - 見つからなかった場合は最小のハッシュ値を持つスロットに割り当てる
- メリット
  - スロットの追加や削除（スケールイン・アウト）が「キーの数/スロットの数」のキーの再マップで済む

コンシステントハッシュ法の課題

各スロットへのキーの割り振りがハッシュ関数に依存するため、ハッシュ関数が不均一だったりノード数が少なかったりするとデータ（負荷）が十分に分散しない
この問題はノード数が増えることで解消されるため、Dynamoでは仮想ノードという考え方を導入して仮想的にノード数を増やしている
- 1つの実ノード（サーバ）が1つ以上の仮想ノード（スロット）を保有する
- AというノードがA1とA2という仮想ノードを持っていれば、A1とA2に対応するデータは両方共Aが責任を持って処理する

レプリケーション

可用性と持続性のために、Nノードにレプリケーション
- Dynamoだと大体N=3とかで設定しているよう
各キーに対して、そのキーを保存すべきノードのリストを「preference list」と言う
- preference listのノードにレプリケーションする際にfailure nodeがあるかもしれないので、listにはN以上のノードが登録される
preference list作成時は物理ノードが異なるように選ぶ
- 仮想ノードを適当に順にNノード選ぶと、同じ物理ノードに複数データを配置してしまう可能性があり、レプリケーションの意味が無い

データバージョニング

Dynamoでは結果整合性を保つために、書き込み時は過去のオブジェクトを上書きするのではなく、新しいバージョン情報を付与することで新しいバージョンと古いバージョンのそれぞれを管理しておき、読み込み時にバージョンを統合するという方式をとっている

reconciliation(調停)

複数バージョンのオブジェクトの統合のこと。結果整合性の項で述べた「同じデータに対する更新の衝突の解決」をこの用語で呼んでいるっぽい

syntactic reconciliation
- 分裂していない1つのブランチ上にある2つのバージョン（親子関係にある2つのバージョン）については、（殆どの場合）新しいバージョンに統合する
semantic reconciliation
- 分岐した2つのブランチに存在する2つのバージョンはクライアントに統合してもらう必要がある
  - 例: merge
  - last write wins等の単純なアルゴリズムであればデータストア側でも自動で統合可能

ベクタークロック

ある2つのバージョンが親子関係であるかどうかを判別するためにDynamoが使っている情報のスキーマ
具体的には、write時にオブジェクトとともにputされる以下のバージョン情報をベクタークロックと言う
- (writeを処理したノード,シーケンス番号(何回writeを処理したか))ペアのArray
- put時に、writeを受け付けたノードのシーケンス番号がインクリメントされる
問題点として、ベクタークロックのArrayは一方的に肥大化するということがある。Dynamoではたとえばペアの数が10を超えたら最も古いペアを削除するなどで対処しているらしい。

get()とput()の実行について

クライアントがget(read)/put(write) requestを渡すノードを選択する方法は2つ
1. ロードバランサを介する方法
  1. Dynamoシステムの外部にあるロードバランサ（nginxなど）がDynamoのノードにランダムにリクエストを割り振る
  2. リクエストを受けたDynamoのノードは自分がそのキーの担当かどうかを確認
  3. 担当であればそのノードはコーディネータとしてそのリクエストを処理し、担当でなければ適切なノードにリクエストをリダイレクトする
2. クライアントライブラリ側で適切にルーティングする方法
  1. 定期的に各ノードとキーの対応関係表（後述）をダウンロードし、その情報を元に適切なノードに直接リクエストを送る
  2. リクエストを送られたノードはコーディネータとしてリクエストを処理
コーディネーター
- read/writeを処理するノードのこと
- preference listの先頭Nノードのうち、最初にリクエストを受け取ったノードがコーディネータに昇格する
read, writeの成功・失敗の基準
- quorum systemを使用
  - quorum systemはZooKeeperとかで利用されている多数決的な概念
- R + W > N となるR,Wを設定し、R(W)以上のノードがread(write)処理に参加すると、処理が初めて成功する
  - R + W > Nという式によって、ReadとWriteのどちらのパフォーマンスを優先するか、ある程度自由に設定できるようになっている

Handling Failures: Hinted Handoff

厳格なquorumであれば、read, writeを送るノード（多数決に参加できるメンバー）は厳格に決まっているため、障害に弱い
sloppy quorum
- sloppyではquorumのメンバーは厳格である必要はない
  - write時にレプリカをA,B,Cに送る予定で、Aがdownしていた場合、Dに代わりにレプリカを送ることが出来る
  - ただし、本来の所有者はAなので、DはAが復活したらAにレプリカを返す
  - その時本来の所有者を現す情報をレプリカに付与するが、その情報をhintと呼んでいるっぽい

Handling permanent failures: Replica synchronization

レプリカの一貫性を確保するための方法
- hintによるレプリカの復帰だけでは耐障害性が不十分なので、共通のキー担当範囲をもつノード群は、定期的に互いのレプリカの状態を比較し合うことで、足りないレプリカを同期している
レプリカの比較方法
- 各ノードはローカルにマークル木を持ち、それをノード同士で比較することで、一貫性を検証する
  - 例: rootが一緒であれば完全にsyncされている。rootが違えば、レプリカが足りないか、足りているとしてもオブジェクトが正常にコピーできていない（壊れている）
  - マークル木を使うメリットは、比較が効率的に行えることである
- マークル木はkey rangeごとに1つ作成される

メンバーシップ

Dynamoでは、ノードの追加と削除を「各ノードが持つメンバーシップ情報の変更」という手段で行う
Amazonではメンバーシップの変更はコマンドラインなどで明示的に発行している（自動ではない）
メンバーシップの変更は履歴として保存され、gossip-based protocolで全体に共有される
- 実際にはシードという、全ノードが認識しているノードと同期することで共有されるらしい
  - シードを全ノードに認識させるために、config fileにipを直書きしておいても良いし、外部にシード用のdns serverを建てても良い
  - （メモ）この仕様は、論文で主張している可用性や対称性と食い違う気がするので疑問。例えば、シードが1つであればSPOFになるので可用性が失われる。よっておそらくだが、実際にはシードは複数設定されており、シードのメンバーシップを更新する際は同期的に行うのだと思う。
メンバーシップの履歴の共有と同じタイミングで、ノードとtokens(仮想ノードの位置)の対応関係表もgossip-based protocolで共有される
- 対応表を共有する際に、ノード間で内容が異なる場合はマージ？する
- 対応表を全員がローカルに持つことで、全員が互いのノードをキーの責任範囲とともに認識できるようになるため、あるキーに対応するread/write命令を直接（1ホップで）ノードに送ることが出来る

Dynamoの実装

3つのソフトウェアコンポーネント

request coordination
membership and failure detection
local persistence engine

local persistence engine(data store)

ローカルのdata storeには何を選んでも良い
- Berkeley DatabaseをAmazonでは使ってたっぽい
  - Berkeley Databaseはアプリケーション組み込み型のデータベースのため、RDBとくらべて管理が楽で性能も良い

request coordination(coordinator)

クライアントのリクエストからstate machineを作成し、そのstate machineのロジックに従って種々のプロセスが処理される
- state machine: いわゆる状態遷移図。オートマトン
read repair
- Read operationの終わり時に、残りのまだ来ていないresponseについて少し待機し、それが古いバージョンであれば、そのノードのオブジェクトを最新のバージョンに更新してあげること。
write requestを処理するコーディネータの選び方
- 理想的にはpreference listの先頭Nノードのうちの1つに処理を集中させることでデータの衝突が起きないようにしたいが、この方法だとノードへの負荷が偏ってしまう。特に、普通はすべてのオブジェクトが均等に参照されないので、オブジェクトごとにもリクエスト数が偏り、結果一部のノードにリクエストが集中してしまう。
- そこで、直前のread operationを最も早く返したノードがwriteを処理するようにすることで、writeするノードが偏らないようにしている。また、こうすることで、一連の読み書きを同じノードが行うので、データの整合性が担保されやすくなる

実験

Dynamoは調停のロジック、レプリケーション（N）の数、read/write quorumのR, Wの数等をチューニングすることで、アプリケーションに最適な性質のパフォーマンスを提供できる。

Read/Writeのレイテンシーについて
- 平均は十分に速いが、99.9パーセンタイルだとWriteが特に遅くなってしまっている
- 原因はDisk IOのせい。Disk IOのボトルネックを極力減らすために、Write処理は一旦バッファにストアし、あとで定期的にストレージに書き込むことで、パフォーマンスを上げることができる
負荷の均等分散について
- Figure6の通り、負荷が多いときほど負荷は均等に分散する
バージョンが分岐するケースについて
- 障害が起きている時か、同じキーに対する書き込みが多数並列に走っている時に、分岐することが多い
- 実験の結果、99.94%のリクエストはバージョンが分岐しなかったようなので、基本的には問題にならないと考えて良い

感想

可用性を最大化するために様々な技術やロジックが使われていて、非常にためになった。
システムアーキテクチャは簡単ではないが、設計でゴールをはっきりと定義しているので、一貫性をもった仕様になっていると思った。
この手の論文について、細かい挙動についても精読しようとするとかなり時間がかかってしまうため普段は多少読み飛ばしてしまうが、輪読だったので一応一通り（特に4章のシステムアーキテクチャの部分）理解することに努めた。結果としては、曖昧な理解では得られなかった知識の定着に繋がったと思う。
P2Pライクなシステムは実装が大変そうだなと思う。開発をどのように行っていくのか若干興味が湧いた。

AmazonのDynamo論文を読んだ