ブログ  前の記事  次の記事  2008-05-13 

たけまる / Kai - Amazon's Dynamo communicating with memcache protocol


2008-05-13

_ Kai - Amazon's Dynamo communicating with memcache protocol [kai][dynamo][erlang]

だいぶ前 [2008-02-25-1] に,Perl (POE) で Amazon Dynamo っぽいもの
を作りかけて放置していました.

Erlang で書き直して,それなりに動くことを確認したので公開します.名
前は Kai といいます.今回は,memcache プロトコルでデータをやり取り
できるようにしました.

Dynamo とは,Amazon で使われているスケーラブルなハッシュテーブルで
す.詳しくは [2008-01-31-1] に書きましたが,次のような特徴を持って
おり,Amazon の巨大なサービスを支えています.

- 簡単にスケールアウトできる
- 障害に強い (マシン障害どころかラック障害にも耐える)
- レスポンスタイム (Latency) が安定している
- いつでも読み書きできる (Lock によるストールがない)
- 小さなデータをたくさん格納するのに向いている (GFS と違って)

Dynamo のすべてを実装することは難しいので,Kai では重要な機能を順に
実装し,Lightweight なDynamo として仕上げていきます.まだ手の回って
ない部分もたくさんありますが,Dynamo の特徴を体験できる程度にはなっ
ています.オープンソースの Dynamo としては唯一の実装だと思います.

8 台で動くことは確認しました.毎秒数百リクエストの状況下でノードを
追加・除去しても,安定したレスポンスが得られます.

継続的に開発をしていきますので,よろしくお願いします.技術的な詳細
も追々紹介していきたいと思います.

# memcache プロトコルの実装では以下のページを参考にさせていただき
# ました.ありがとうございます.
# DSAS開発者の部屋:Erlang で memcached を作ってみました。

■ インストール

(2008-05-23 追記) sourceforge.net にプロジェクトを立ち上げましたの
で,最新情報はそちらを参考にしてください [2008-05-23-1]

Erlang v5.6 (OTP R12B) 以降をインストールしておいてください.Mac
ports を使えば簡単にインストールできます.それ以外の方はソースをダ
ウンロードして ./configure; make; make install してください.なお,
Debian stable は v5.5.2 なのでダメです (byte_size を size に置換す
ればいけるかも).

Eralng の準備ができたら,Kai のソースをダウンロードして make してく
ださい.

kai-20080513.tar.gz

% tar zxvf kai-20080513.tar.gz
% cd kai/
% make

■ 使い方 (スタンドアローン)

まずは単体で動作させてみます.以下のようにすると,通常の memcached
のように動作します.memache クライアントから set/get/delete してみ
てください.

% erl -pa src -config kai -kai n 1 -kai r 1 -kai w 1
> application:load(kai).
> application:start(kai).

■ 使い方 (クラスタ)

Kai はクラスタで使ってこそ意味があります.多くのマシンを用意するの
は難しい人が多いと思うので,ひとつのマシンで 3 つのインスタン
ス (daemon) を実行する方法を紹介します.

まずは,それぞれのインスタンスを起動します.それぞれに異なるポート
番号を指定してください.

ターミナル1
% erl -pa src -config kai -kai hostname '"localhost"' -kai port 11210 -kai memcache_port 11211
> application:load(kai).
> application:start(kai).

ターミナル2
% erl -pa src -config kai -kai hostname '"localhost"' -kai port 11212 -kai memcache_port 11213
> application:load(kai).
> application:start(kai).

ターミナル3
% erl -pa src -config kai -kai hostname '"localhost"' -kai port 11214 -kai memcache_port 11215
> application:load(kai).
> application:start(kai).

次に,インスタンスをクラスタ化します.次のようにして隣のノードを教
えてあげてください.IP アドレスの区切りが "." ではなく "," になっ
ているので注意してください (Erlang の流儀です).

ターミナル1
> kai_monitor:call_check({{127,0,0,1},11212}).

ターミナル2
> kai_monitor:call_check({{127,0,0,1},11214}).

ターミナル3
> kai_monitor:call_check({{127,0,0,1},11210}).

クラスタの状態を確認します.次のように 3 つのインスタンスが表示され
ればうまくいっています.

> kai_hash:node_list().
{node_list,[{{127,0,0,1},11214},
            {{127,0,0,1},11210},
            {{127,0,0,1},11212}]}

お好きな memache クライアントを使って,set/get/delete してみてくだ
さい.どのインスタンスに話しかけても同じように結果が返ってきます.

ここで,インスタンスを 1 つ止めてみます.

> application:stop(kai).

データが失われることもなく,変わらずに使い続けることができると思い
ます (障害が発生したらぜひバグレポートを).

なお,デフォルトの設定では 2 つ以上のインスタンスが動作していない
と書き込めません.

■ ノード管理 (クラスタ構成の管理) について

論文によれば,Dynamo は Chord という DHT 技術によってノードを管理
しているとことになっています.ただし,多くの制約により,個人的には
Chord はほとんど役に立っていないと思います.また,100 ノード以下で
あれば DHT をつかうまでもないので,現在は Gossip based protocol と
いう簡易な方法でノード管理を行っています.DHT の採用は必要になって
から考えます (採用するにしても Chord ではなく Kademlia かなぁ).

Erlang はクラスタ管理の機能を備えていますが,なんとなく重そうなの
で (テストもしてませんが),使っていません.

ところで,Kai では新たにノードを追加するときに,すでにクラスタに属
しているノードを 1 つ以上教える必要があります.cagra のようにマルチ
キャストでクラスタの状態を報知することもできますが,Kai ではそのよ
うなアプローチは採りません.ひとつは,クラスタをサブネットに限定し
ないためです.もうひとつは,クラスタへの参加タイミングを管理者が制
御できたほうが,実運用では扱いやすいからです.

■ サポートしている memcache プロトコル

現在は 4 つのコマンドをサポートしています.Kai は "キャッシュ" で
はないので,期限切れ (exptime) はサポートしません.

コマンド名 コメント
get データの取得.key は 1 つのみ
set データの追加・更新.期限切れは "なし (0)" でなければならない
delete データの削除.データがなくても成功 (DELETED) が返ってくる (バグ)
quit

今後は,stats や cas のサポートを検討しています.

Kai では,1 つの key に対して複数のデータが返ってくることがありま
す.これは次のような Kai (というか Dynamo) の特徴によります.

"安定したレスポンスタイム" や "いつでも書き込める" ことを実現するた
めに,Kai はレプリカを作成するときでも Lock をかけません.このため,
ほぼ同時に書き込みが行われたときには,異なるバージョンのレプリカが
存在する可能性があります.

バージョンの不一致を発見すると,Kai はすべてのバージョンをクライア
ントに返します.複数のデータを受信したクライアントは,必要に応じて
不一致を解消し,書き戻してください.

■ なぜ Erlang なのか

マルチコアを有効に使いたかったのと,リソースの排他制御を実装したく
なかったためです.

Erlang にしたことで,設計がとても簡単になりました.Erlang で
Hello, World! を書いてからまだ 1ヶ月も経ってないのに,ここまででき
ました.Erlang すごいです.

ちなみに,Amazon は Java で実装しているようです.

■ 主な TODO

コミッター募集中です.

- コーディング規約の統一,小さなリファクタリング,細かなバグ修正
- 簡単なドキュメント整備
- どこかのコードリポジトリに移動 (英語圏の人でも気楽に使えるのがいいかなぁ)
- MySQL など persistent storage の利用 (現在は ets というメモリ DB のみ)
- Vector Clocks によるバージョン不整合の解消
- memcache stas, cas のサポート
- プロセスプールによる負荷制御
- ラック障害対策

# 細かいのを含めると 40 項目くらいある…

一言メッセージをこっそり送信できます (非公開)
 今年の西暦→
Referrer (Inside): [2008-05-23-1] [2008-05-14-1]