Consitent Hashing

楽天テクノロジーカンファレンスの記事で amazon の Dynamo というのが紹介されていた. そんなのがあるのかとぐぐってみつけた Dynamo の話を読む. その中で consistent hashing が使われており. シンプルでよくできたアルゴリズムだと感心, 紹介しようと思った次第. WWW8 に出たオリジナルの記事も読んでみたけれど, もともと単純なアイデアなので大した詳細はない. Chord や Dynamo の記事に含まれる紹介で十分ことたりている. でも Chord が consitent hashing だというのは件の記事を読むまで気付かなかったなあ. わっかの上をぐるぐる周るやつ, くらいの記憶しかなかった...

Dynamo

consistent hashing にはじまり, Dynamo は分散アルゴリズムがてんこもり. vector clock, gossip-based protocol, merkle tree (使いどころがわからん), eventual consistency (これは技法じゃないか) ... 様々な技法を一つのシステムに集約しているのはすごい. 個人的にはタネン本の知識が役に立って嬉しかったけれど, 現実にこんなシステムがあるとは思わなかった. 複雑さに眩暈がする. しかし複雑さにも関わらず service level agreement に関する議論も絵空事になっていない. 毎秒 500 要求の負荷の下で 300ms の反応速度を 99.9% のクライアントに保証するという目標を達成しているという.

個人的に面白いと思ったのは, 分散ストレージの抱えるバージョン付けの問題に対するアプローチ. Dynamo は partitioning と replication の両方を行っており, かつ ACID の C にいくらか妥協をしている. (eventually consistent ... 一時的に矛盾はあるけど, そのうち矛盾はなおるはずというモデル.) この妥協のおかげで性能を保てるかわりに異なるバージョンのデータが混在することがある.

普通のデータベースは書込みのタイミングで一貫性を保証しようとし, 衝突があった場合はその書込み要求を拒否する. 一方の Dynamo は "always writable" という目標を持っており, 書き込みの失敗は許されない. だから衝突のあるデータも一度ストレージに保存する.

衝突を解決するのは, そのデータを読み出したクライアントの仕事になる. クライアントが衝突のあるキーを読み出すと, 一つの値が返ってくるかわりに衝突を解決すべき値のリストが返ってくる. クライアントはアプリケーションに応じた方法でその二つをマージし, 解決済みデータとしてキーに書き込む. こうしてようやく (eventually) 一貫性が回復する. write の面倒を read に転嫁するわけね.

イメージとしては subversion なんかでブランチをしていて, そのブランチをトランクに戻す際に自力でマージをする感じだろうか. 普通の SCM は行レベルで diff/patch 式マージをしてくれるけれど, Dynamo のデータは opaque なバイト列. マージはアプリケーションの責任になる.

ACID でかっちり固めたデータベースに慣れていると, こうしたルーズなモデルは新鮮に見える. でも Mercurial や git はある種の分散データベースだと言える. そう考えると eventual consistency は案外身近な物に思えてくる. 誰がいつマージするかは悩ましいけれど...

Amazon は AWS やら S3 やらとウェブのプラットホーム化をがんばっている. ただ Google ほど社内のあれこれをアピールしないので, 野次馬的には食い足りない. 去年の ACMQ に載っていた Werner Vogels CTO のインタビューは Amazon の内情をいくらか伝えている. Dynamo のホワイトペーパーも, こうした inside amazon 話のひとつとして読むことができる.

2007-12-01

Dynamo