ConsistentHashの動きをPHPでもやってみた
via - http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing
こんな感じで実装
interface HashFunction {
public function hash($key);
}
interface Circle {
public function put($key, $value);
}
interface Node {
public function put($key, $value);
public function get($key);
public function has($key);
public function keys();
public function getName();
}
class TreeMap implements Circle {
private $values;
public function __construct(array $values = array()){
$this->values = new ArrayObject($values);
}
public function put($key, $value){
$this->values->offsetSet($key, $value);
}
public function get($key){
return $this->values->offsetGet($key);
}
public function remove($key){
$this->values->offsetUnset($key);
}
public function has($key){
return $this->values->offsetExists($key);
}
public function isEmpty(){
return $this->values->count() < 1;
}
public function firstKey(){
$map = clone $this->values;
$map->ksort();
$arrayKeys = array_keys($map->getArrayCopy());
return $arrayKeys[0];
}
public function tailMap($key){
$map = clone $this->values;
$map->ksort();
$array = $map->getArrayCopy();
$arrayKeys = array_keys($array);
$results = array();
foreach($arrayKeys as $arrayKey){
if($key <= $arrayKey){
$results[$arrayKey] = $array[$arrayKey];
}
}
return new self($results);
}
}
class ConsistentHash {
private $hashFunction;
private $numberOfReplicas;
private $circle;
private $nodes = array();
public function __construct(HashFunction $hashFunction, $numberOfReplicas){
$this->hashFunction = $hashFunction;
$this->numberOfReplicas = $numberOfReplicas;
$this->circle = new TreeMap;
}
public function getNodes(){
return $this->nodes;
}
public function add(Node $node){
for($i = 0; $i < $this->numberOfReplicas; ++$i){
$nodeKey = $this->hashFunction->hash($node->getName() . $i);
$this->circle->put($nodeKey, $node);
}
$this->nodes[] = $node;
}
public function get($key){
if($this->circle->isEmpty()){
return null;
}
$hash = $this->hashFunction->hash($key);
if(!$this->circle->has($hash)){
$tailMap = $this->circle->tailMap($hash);
if($tailMap->isEmpty()){
$hash = $this->circle->firstKey();
} else {
$hash = $tailMap->firstKey();
}
}
return $this->circle->get($hash);
}
public function remove(Node $node){
for($i = 0; $i < $this->numberOfReplicas; ++$i){
$nodeKey = $this->hashFunction->hash($node->getName() . $i);
$this->circle->remove($nodeKey);
}
}
}
class ConsistentHashNode implements Node {
private $hash;
private $keys = array();
public function __construct(ConsistentHash $hash){
$this->hash = $hash;
}
public function put($key, $value){
$this->hash->get($key)->put($key, $value);
$this->keys[] = $key;
}
public function get($key){
return $this->hash->get($key)->get($key);
}
public function has($key){
return $this->hash->get($key)->has($key);
}
public function keys(){
return $this->keys;
}
public function getName(){
return __CLASS__;
}
}
class IdentNode implements Node {
private $name;
private $values = array();
public function __construct($name){
$this->name = $name;
}
public function put($key, $value){
$this->values[$key] = $value;
}
public function get($key){
return $this->values[$key];
}
public function has($key){
return isset($this->values);
}
public function keys(){
return array_keys($this->values);
}
public function getName(){
return $this->name;
}
}
PHPでTreeMapみたいな実装(keyを並び替えながら挿入、指定key以降のmap取得)が思いつかなかったので、ksortとかつかって、なんちゃって実装
んで、ハッシュアルゴリズムとかは、こんな感じで実装して、必要に応じて切り替える
class HashMD5Integer implements HashFunction {
public function hash($key){
$values = unpack('H*', md5($key));
return $values[1];
}
}
class HashSha1Integer implements HashFunction {
public function hash($key){
$values = unpack('H*', sha1($key));
return $values[1];
}
}
class HashCRC32Integer implements HashFunction {
public function hash($key){
$values = unpack('H*', crc32($key));
return $values[1];
}
}
これについても、ハッシュ値を並び替えるため、数値にしたくて、ハッシュ文字列(md5)を数値(digit)にする方法が思いつかなかったので、unpack(H*)。もっといい方法があると思う。
こんな風に動かす
$hash = new ConsistentHash(new HashMD5Integer, 8);
$hash->add(new IdentNode('hoge1'));
$hash->add(new IdentNode('hoge2'));
$hash->add(new IdentNode('hoge3'));
$map = new ConsistentHashNode($hash);
for($i = 0; $i < 10; ++$i){
$map->put('key' . $i, 'value' . $i);
}
foreach($hash->getNodes() as $node){
echo $node->getName(), ':', join(',', $node->keys()), PHP_EOL;
}
実行結果としては、こんな感じで出た。まあそこそこバラけてる(?)
hoge1:key1,key4,key6
hoge2:key3,key5,key7
hoge3:key0,key2,key8,key9
試しに他のアルゴリズムでも実行して比較してみた
$hashAlgos = array(
new HashMD5Integer,
new HashSha1Integer,
new HashCRC32Integer
);
foreach($hashAlgos as $algo){
echo get_class($algo), PHP_EOL;
$hash = new ConsistentHash($algo, 32);
for($i = 0; $i < 10; $i++){
$hash->add(new IdentNode('hoge' . $i));
}
$map = new ConsistentHashNode($hash);
for($i = 0; $i < 100; $i++){
$map->put('*' . $i, $i);
}
$allKeys = $map->keys();
foreach($hash->getNodes() as $node){
$keys = $node->keys();
echo 'node(', (count($keys) / count($allKeys)) * 100, '%):', $node->getName(), ', keys:', join(',', $keys), PHP_EOL;
}
}
HashMD5Integer
node(12%):hoge0, keys:*2,*9,*21,*27,*30,*47,*49,*52,*53,*70,*77,*89
node(12%):hoge1, keys:*0,*8,*10,*20,*23,*33,*40,*41,*69,*86,*90,*98
node(11%):hoge2, keys:*16,*22,*31,*38,*39,*63,*64,*72,*75,*79,*88
node(10%):hoge3, keys:*12,*48,*56,*58,*62,*65,*67,*73,*83,*84
node(4%):hoge4, keys:*6,*61,*91,*95
node(11%):hoge5, keys:*1,*4,*7,*13,*17,*28,*42,*44,*54,*55,*94
node(13%):hoge6, keys:*5,*11,*26,*35,*37,*43,*50,*51,*57,*74,*87,*92,*97
node(8%):hoge7, keys:*18,*32,*36,*45,*46,*60,*82,*85
node(8%):hoge8, keys:*15,*19,*25,*59,*68,*78,*81,*96
node(11%):hoge9, keys:*3,*14,*24,*29,*34,*66,*71,*76,*80,*93,*99
HashSha1Integer
node(11%):hoge0, keys:*29,*33,*36,*38,*46,*55,*67,*74,*81,*86,*92
node(8%):hoge1, keys:*1,*2,*18,*48,*69,*89,*93,*99
node(8%):hoge2, keys:*6,*57,*58,*62,*66,*68,*71,*78
node(12%):hoge3, keys:*8,*14,*32,*39,*42,*51,*56,*75,*79,*88,*95,*97
node(14%):hoge4, keys:*3,*9,*12,*13,*34,*40,*43,*45,*53,*59,*64,*65,*77,*94
node(10%):hoge5, keys:*7,*23,*24,*41,*49,*61,*72,*76,*80,*91
node(10%):hoge6, keys:*0,*10,*11,*15,*17,*25,*28,*35,*87,*98
node(8%):hoge7, keys:*4,*20,*21,*27,*31,*50,*63,*85
node(12%):hoge8, keys:*5,*16,*22,*26,*30,*37,*44,*47,*52,*70,*90,*96
node(7%):hoge9, keys:*19,*54,*60,*73,*82,*83,*84
HashCRC32Integer
node(13%):hoge0, keys:*11,*12,*13,*14,*16,*17,*40,*42,*44,*45,*47,*49,*98
node(9%):hoge1, keys:*58,*62,*63,*64,*65,*74,*75,*81,*96
node(3%):hoge2, keys:*29,*30,*36
node(14%):hoge3, keys:*4,*5,*9,*21,*25,*27,*32,*38,*39,*51,*78,*87,*92,*99
node(7%):hoge4, keys:*43,*50,*56,*59,*80,*86,*97
node(22%):hoge5, keys:*10,*15,*18,*19,*34,*41,*48,*52,*53,*54,*55,*57,*60,*61,*66,*67,*68,*69,*70,*71,*85,*93
node(5%):hoge6, keys:*8,*24,*28,*31,*79
node(5%):hoge7, keys:*0,*1,*35,*46,*82
node(16%):hoge8, keys:*2,*3,*6,*22,*23,*26,*37,*72,*73,*76,*77,*83,*88,*90,*94,*95
node(6%):hoge9, keys:*7,*20,*33,*84,*89,*91
crc32とかだと、似たようなキー(52-55,66-71とか)は一部集中してる感じ。逆に md5, sha1 あたりは一様にバラけてるので、バラ撒くなら後者の2つを使う方が良さそう。
というか、crc32は一部に偏りすぎな気もする（実装の問題?)
ノードを増やしてみたりした結果はこれ
$hash = new ConsistentHash(new HashMD5Integer, 32);
$hash->add(new IdentNode('hoge1'));
$hash->add(new IdentNode('hoge2'));
$hash->add(new IdentNode('hoge3'));
$map = new ConsistentHashNode($hash);
for($i = 0; $i < 10; ++$i){
$map->put('key' . $i, 'value' . $i);
}
$hash->add(new IdentNode('hoge4'));
for($i = 10; $i < 20; ++$i){
$map->put('key' . $i, 'value' . $i);
}
$hash->add(new IdentNode('hoge5'));
for($i = 30; $i < 40; ++$i){
$map->put('key' . $i, 'value' . $i);
}
$allKeys = $map->keys();
foreach($hash->getNodes() as $node){
$keys = $node->keys();
echo 'node(', (count($keys) / count($allKeys)) * 100, '%):', $node->getName(), ', keys:', join(',', $keys), PHP_EOL;
}
node(30%):hoge1, keys:key0,key4,key6,key7,key16,key17,key30,key31,key34
node(16.6666666667%):hoge2, keys:key2,key3,key5,key9,key19
node(23.3333333333%):hoge3, keys:key1,key8,key10,key11,key12,key14,key15
node(20%):hoge4, keys:key13,key18,key32,key35,key37,key39
node(10%):hoge5, keys:key33,key36,key38
これはこういう動きが正しいのかわからない。。。(先に存在していたノードはキーが増えるよなぁ）
んで、結論。
ConsistentHashは面白い
]]>
