Amazon’s Dynamo is awesome!

たけまる

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

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

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

なるほど。