たけまる / Amazon's Dynamo is awesome!

Dynamo というのは，Amazon の膨大なデータを扱う分散 DBM のことで，
毎秒 500 リクエストに対して，99.9% を 300ms 以内にレスポンスするよ
うに設計されている．その化け物のようなシステムの概要を紹介する．

一般的に，RDBMS でクラスタを組むときは master/slave 構成にする．か
の有名な GFS (Google File System) も master/slave を採っている．こ
の構成はすべてのリクエストが master を通過するので，どうしても
master がボトルネックになる．Dynamo が想定しているような膨大なリク
エストを捌くのは難しい．また，master が故障するとシステム全体がダウ
ンしてしまう．

# 補足しておくと，GFS の目標はリクエスト数ではなく IO (スループッ
# ト) の向上なので，master/slave でかまわない．


Dynamo は，master 不在の peer-to-peer アーキテクチャを採用した．
peer-to-peer がうまくいくと，システム規模と耐障害性を格段に高めるこ
とができる．ところが，これまでバックエンドに採用されたことはない．
これには2つの課題があったからだと思う．ひとつは latency (探索遅延)
で，もうひとつはデータの一貫性．

peer-to-peer は，データの在処を各ノードに分散させておき，いくつかの
ノードを経由して目的のデータにたどり着く．このため，latency が問題
にならない分野にしか使われてこなかった．KaZaA や Winny であれば数分
から数時間のうちにデータを見つけられればいいし，Skype にしても10秒
くらいの猶予がある．ところが，Dynamo は 300ms 以内にレスポンスしな
ければならない．

Dynamo のベースになっている Chord という技術は，1億ノードでも動作す
るように設計されている．このため，各ノードがすべてのデータの在処を
記憶するのではなく，分散させておく．しかし，Dynamo の場合はもう少し
規模が小さい (おそらく，数百〜数千ノード)．そこで，データの在処を分
散させたままにするのではなく，ノード同士が教えあって学習するように
した (gossip protocol と呼ばれる)．これによって，latency を大幅に改
善している．

次に2つ目の課題．あらゆるシステムでは，障害対策のためにデータを複数
ノードにコピーする．Dynamo でも，もちろんそうする．ところが，
peer-to-peer には master がいないため，データを lock することができ
ない (GFS では master が lock する)．つまり，ほぼ同時に書き込みが行
われた場合，異なるバージョンのデータが分散して存在することになりう
る．

この問題に対して，eventually consistent というかなり思い切ったモデ
ルを採用することにした．書き込み時点でのバージョンの不一致はほおっ
ておき，読み取るときに修正する．簡単な不一致であれば，vector clocks
という分散アルゴリズムで Dynamo が修正する．それで手に負えないとき
はアプリケーションが修正する (手動マージのイメージ)．これでうまくい
く (実際にはアプリケーションによる修正が必要になることはほとんどな
いらしい)．

# 公平のために補足しておくと，Dynamo が採用した分散アルゴリズムは，
# アカデミアで提案されていたものがほとんどである．Amazon はそれら
# をシステムとして統合し，サービスにまでつなげている点がすごい．


従来の RDBMS と比べて，Dynamo の性能や拡張性はとても高い．ところが，
データモデルがまったく異なるため，サービス開発者はかなり戸惑ったと
思う．読み取ったデータが最新ではないかもしれないシステムなんて，普
通扱ったことがない．ライブラリで完全に隠蔽するのは難しそうだしなぁ．
トランザクションはどうしてるんだろう．もっと知りたいことがたくさん
ある．

論文では，RDBMS から Dynamo への移行は簡単だといっているけど，この
新たなモデルをしっかり理解しないとうまくいかないんじゃないかなぁ．
CTO の Vogels だけでなく，かなり多くの開発者が Dynamo のデータモデ
ルを理解しているということかな．Amazon という企業の先進性に驚く．


ここからは余談．

最近の Google からは腕っぷしの強さを感じるけど，Amazon からは洗練さ
れた美しさを感じる．Google のシステムに比べて，Dynamo の負荷分散ア
プローチは本質的で華麗だ (まぁ，目的が違うので単純な比較はできない
んだけど)．Web API の設計にしても，Google がだんだん場当たり的になっ
ている印象を受けるのに対して，S3 や SimpleDB は RESTful で機能的だ．

Google はアプリケーションに重点が移っていて，基盤的な技術が少しおろ
そかになっているのかなぁ．Cloud Computing (buzz word になりそうな響
きがして好きではない) では，Amazon が先んじているかもしれない．

ところで，後発とはいえ，楽天も Cloud Computing に取り組むことを発表
している．個人的にはかなり面白い挑戦だと思ってる．日本はこのへんの
技術に弱いから，興味を持ってる人は少ないかもしれないけど．