Consistent Hashingな拡張モジュール
Consistent Hashingについては以下を参照。要は「キャッシュを分散させた場合で分散させる数が変わったときに、「orz」とならないようにするための仕組みの1つ」な感じです(多分)。
で、それを実現するためのCライブラリとしてlibketamaがあります。
このlibketamaのソースにはPython、Java、PHPの各バインディングが含まれているようなので、ちょっと使ってみました。
まずは、ソースをcheckout。使用リビジョンは398です。
$ svn co svn://svn.audioscrobbler.net/misc/ketama $
build手順は以下の通り。Makefileを置換しているのは、make testを実行するためです。
$ cd ketama/libketama/ $ make $ make test $ sudo make install $ cd ../php_ketama/ $ phpize $ ./configure $ perl -i -p -s -e "s/run-tests\.php/run-tests\.php -n/g" Makefile $ make test $ sudo echo "extension=ketama.so" >> /usr/local/lib/php5/ini/5.2.5/php.ini $ sudo /usr/local/apache2/bin/apachectl graceful $
動作確認には、付属するketama_test.phpをちょっとだけ変えた以下のようなサンプル(ketama_sample.php)を用意しました。
<?php $continuum = ketama_roll("ketama.servers"); if (!$continuum) { die("Continuum doesn't exist!\n"); } for ($i = 0; $i < 25; $i++) { $key = sprintf('key%02d', $i); $server = ketama_get_server($key, $continuum); echo "Key " .$key. " is mapped to server " . $server[ "ip" ] . " ". "at point: " . sprintf('%u', $server[ "point" ]) . "\n"; } ketama_destroy( $continuum );
2行目で読み込んでいるのは、キャッシュサーバの一覧を記述したファイルです。
$ cat ketama.servers #------ Server ------- -Mem-# #255.255.255.255:65535 66666# 10.0.1.1:11211 600 10.0.1.2:11211 300 10.0.1.3:11211 200 10.0.1.4:11211 350 10.0.1.5:11211 1000 10.0.1.6:11211 800 10.0.1.7:11211 950 10.0.1.8:11211 100
フォーマットは
[サーバのIPアドレス]:[ポート]\t[メモリ量(MB)]
で、改行コードは\nとのこと。
で、実行結果は以下の通り。
$ php ./ketama_sample.php Key key00 is mapped to server 10.0.1.8:11211 at point: 1800320459 Key key01 is mapped to server 10.0.1.6:11211 at point: 3193899226 Key key02 is mapped to server 10.0.1.6:11211 at point: 2976219962 Key key03 is mapped to server 10.0.1.5:11211 at point: 376189836 Key key04 is mapped to server 10.0.1.1:11211 at point: 3137020707 Key key05 is mapped to server 10.0.1.5:11211 at point: 1725056963 Key key06 is mapped to server 10.0.1.5:11211 at point: 1224552229 Key key07 is mapped to server 10.0.1.6:11211 at point: 2357367355 Key key08 is mapped to server 10.0.1.6:11211 at point: 4079696097 Key key09 is mapped to server 10.0.1.6:11211 at point: 2004225177 Key key10 is mapped to server 10.0.1.7:11211 at point: 416637376 Key key11 is mapped to server 10.0.1.2:11211 at point: 2520092206 Key key12 is mapped to server 10.0.1.5:11211 at point: 3604351698 Key key13 is mapped to server 10.0.1.5:11211 at point: 1684213248 Key key14 is mapped to server 10.0.1.5:11211 at point: 4115738439 Key key15 is mapped to server 10.0.1.2:11211 at point: 1266589709 Key key16 is mapped to server 10.0.1.5:11211 at point: 1335097278 Key key17 is mapped to server 10.0.1.2:11211 at point: 2969767984 Key key18 is mapped to server 10.0.1.2:11211 at point: 3300786288 Key key19 is mapped to server 10.0.1.3:11211 at point: 1481603467 Key key20 is mapped to server 10.0.1.7:11211 at point: 3257186564 Key key21 is mapped to server 10.0.1.5:11211 at point: 250943416 Key key22 is mapped to server 10.0.1.7:11211 at point: 4012085095 Key key23 is mapped to server 10.0.1.5:11211 at point: 444090199 Key key24 is mapped to server 10.0.1.6:11211 at point: 3726532859
メモリ量が多いところに多く割り振られている感じで、「重み付け」的な意味を持っているようです。
ここで、
$ vi ketama.servers $ cat ketama.servers #------ Server ------- -Mem-# #255.255.255.255:65535 66666# 10.0.1.1:11211 600 10.0.1.2:11211 300 10.0.1.3:11211 200 10.0.1.4:11211 350 #10.0.1.5:11211 1000 10.0.1.6:11211 800 10.0.1.7:11211 950 10.0.1.8:11211 100 $
と10.0.1.5を切り離して再度実行してみると、
$ php ./ketama_sample.php Key key00 is mapped to server 10.0.1.8:11211 at point: 1800320459 Key key01 is mapped to server 10.0.1.6:11211 at point: 3193899226 Key key02 is mapped to server 10.0.1.6:11211 at point: 2976219962 Key key03 is mapped to server 10.0.1.6:11211 at point: 381397883 Key key04 is mapped to server 10.0.1.8:11211 at point: 3135768551 Key key05 is mapped to server 10.0.1.6:11211 at point: 1725712187 Key key06 is mapped to server 10.0.1.6:11211 at point: 1227015366 Key key07 is mapped to server 10.0.1.6:11211 at point: 2357367355 Key key08 is mapped to server 10.0.1.6:11211 at point: 4079696097 Key key09 is mapped to server 10.0.1.6:11211 at point: 2004225177 Key key10 is mapped to server 10.0.1.7:11211 at point: 416637376 Key key11 is mapped to server 10.0.1.2:11211 at point: 2520092206 Key key12 is mapped to server 10.0.1.1:11211 at point: 3604652217 Key key13 is mapped to server 10.0.1.2:11211 at point: 1685388071 Key key14 is mapped to server 10.0.1.7:11211 at point: 4112879081 Key key15 is mapped to server 10.0.1.3:11211 at point: 1259973668 Key key16 is mapped to server 10.0.1.6:11211 at point: 1338271903 Key key17 is mapped to server 10.0.1.2:11211 at point: 2969767984 Key key18 is mapped to server 10.0.1.2:11211 at point: 3300786288 Key key19 is mapped to server 10.0.1.3:11211 at point: 1481603467 Key key20 is mapped to server 10.0.1.7:11211 at point: 3257186564 Key key21 is mapped to server 10.0.1.1:11211 at point: 252679968 Key key22 is mapped to server 10.0.1.7:11211 at point: 4012085095 Key key23 is mapped to server 10.0.1.4:11211 at point: 445175540 Key key24 is mapped to server 10.0.1.7:11211 at point: 3725544024
となりました。diffを採ってみると
$ diff before.log after.log 4,7c4,7 < Key key03 is mapped to server 10.0.1.5:11211 at point: 376189836 < Key key04 is mapped to server 10.0.1.1:11211 at point: 3137020707 < Key key05 is mapped to server 10.0.1.5:11211 at point: 1725056963 < Key key06 is mapped to server 10.0.1.5:11211 at point: 1224552229 --- > Key key03 is mapped to server 10.0.1.6:11211 at point: 381397883 > Key key04 is mapped to server 10.0.1.8:11211 at point: 3135768551 > Key key05 is mapped to server 10.0.1.6:11211 at point: 1725712187 > Key key06 is mapped to server 10.0.1.6:11211 at point: 1227015366 13,17c13,17 < Key key12 is mapped to server 10.0.1.5:11211 at point: 3604351698 < Key key13 is mapped to server 10.0.1.5:11211 at point: 1684213248 < Key key14 is mapped to server 10.0.1.5:11211 at point: 4115738439 < Key key15 is mapped to server 10.0.1.2:11211 at point: 1266589709 < Key key16 is mapped to server 10.0.1.5:11211 at point: 1335097278 --- > Key key12 is mapped to server 10.0.1.1:11211 at point: 3604652217 > Key key13 is mapped to server 10.0.1.2:11211 at point: 1685388071 > Key key14 is mapped to server 10.0.1.7:11211 at point: 4112879081 > Key key15 is mapped to server 10.0.1.3:11211 at point: 1259973668 > Key key16 is mapped to server 10.0.1.6:11211 at point: 1338271903 22c22 < Key key21 is mapped to server 10.0.1.5:11211 at point: 250943416 --- > Key key21 is mapped to server 10.0.1.1:11211 at point: 252679968 24,25c24,25 < Key key23 is mapped to server 10.0.1.5:11211 at point: 444090199 < Key key24 is mapped to server 10.0.1.6:11211 at point: 3726532859 --- > Key key23 is mapped to server 10.0.1.4:11211 at point: 445175540 > Key key24 is mapped to server 10.0.1.7:11211 at point: 3725544024 $
と10.0.1.5以外のところも変わってしまっていますが、メモリ量を全て同じにすると良いようです。たとえば、メモリ量を全て「100」にして同様の手順でdiffを採ってみると確認できます。
$ diff before.log after.log 4c4 < Key key03 is mapped to server 10.0.1.5:11211 at point: 376189836 --- > Key key03 is mapped to server 10.0.1.3:11211 at point: 376597854 $
ちなみに、円周上のノードですが、ketama_print_continuum関数で一覧を表示できます。
<?php $continuum = ketama_roll("ketama.servers"); if (!$continuum) { die("Continuum doesn't exist!\n"); } var_dump(ketama_print_continuum($continuum));
これを実行すると以下のように出力されます。
$ php ./ketama_print_continuum.php Numpoints in continuum: 1264 10.0.1.5:11211 (762113) 10.0.1.5:11211 (2322555) 10.0.1.6:11211 (3967256) 10.0.1.4:11211 (4398564) 10.0.1.1:11211 (10171922) 10.0.1.7:11211 (13311690) 10.0.1.7:11211 (17290842) 10.0.1.6:11211 (20429789) 10.0.1.2:11211 (24991403) :
実際にmemcached・Repcachedと組み合わせて動かしてみたいな。。。