Do You PHP はてブロ

Do You PHPはてなからはてブロに移動しました

Consistent Hashingな拡張モジュール

Consistent Hashingについては以下を参照。要は「キャッシュを分散させた場合で分散させる数が変わったときに、「orz」とならないようにするための仕組みの1つ」な感じです(多分)。

で、それを実現するためのCライブラリとしてlibketamaがあります。

このlibketamaのソースにはPythonJavaPHPの各バインディングが含まれているようなので、ちょっと使ってみました。
まずは、ソースを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と組み合わせて動かしてみたいな。。。