libmemcached一致hashアルゴリズム詳細解(1)----php-memcachedクライアントの一致性ハッシュとcrcアルゴリズムの共用によって生成されたbug分析

author:selfimpr
ブログ:http://blog.csdn.net/lgg201
メール:[email protected]
事の起源は、同僚が以下のコードを使って、妖しい結果を得たことであり、しかも安定的に私達が望まない結果を生み出したことである.

<?php
$mem = new Memcached;
$mem->addServers(array(array('10.8.8.32',11300,100),array('10.8.8.32',11301,0)));
$mem->setOption(Memcached::OPT_DISTRIBUTION, Memcached::DISTRIBUTION_CONSISTENT);
$mem->setOption(Memcached::OPT_HASH, Memcached::HASH_CRC);
for ($i=0;$i<10;$i++){
    $key = "item_$i";
    $arr = $mem->getServerByKey($key);
    echo ($key.":\t".$arr['port']."
");
}
print_r($mem->getServerList());

コードは簡単です.つまり、phpのMemcachedクライアントを作成し、2つのサーバを追加し、分散アルゴリズムが一致するハッシュを設定しました.HashアルゴリズムはCRCです.
このテストケースを何回も実行しましたが、入力は以下の通りです.

item_1:	11301
item_2:	11301
item_3:	11301
item_4:	11301
item_5:	11301
item_6:	11301
item_7:	11301
item_8:	11301
item_9:	11301
Array
(
    [0] => Array
        (
            [host] => 10.8.8.32
            [port] => 11300
            [weight] => 100
        )

    [1] => Array
        (
            [host] => 10.8.8.32
            [port] => 11301
            [weight] => 0
        )

)

は上の出力から見れば、2台のサーバーは全部OKです.しかし、全てのkeyは1台のサーバーに分布されています.
その後、テスト用例に対して以下の修正を試みました.
1.Hashアルゴリズムを他のサポートのアルゴリズムに切り替える
2.分散アルゴリズムを普通のアルゴリズムに変換する
以上の試みを行いましたが、出力の結果はすべて私達が期待しています.keyは異なるサーバーに分布されています.
そして苦痛な問題は追跡して、最終的に問題がphpのmemcachedクライアントのlibmemcachedに対する実現の上で発見します.
libmemcachedでは、サーバのセット(同じクライアントサービスに対する)を表すための構造(libmemcached/memcached.hで定義されている)は、struct memcachedである.st{}その部分的な定義を以下に要約します.

struct memcached_st {
  uint8_t purging;
  bool is_allocated;
  uint8_t distribution;
  uint8_t hash;
...
  memcached_hash hash_continuum;
...
};

hashとshuを覚えてください.continuumという二つのフィールドです.
そして関数を見ます.
libmemcached/memcached_hash.c中のmemcached_ゲナート_hash関数は、この関数に入る流れは以下の通りです.
「php-memcached拡張phpumemcached.cでget ServeredByKey関数」  呼び出し  「libmemcachedのlibmemcached/memcachemuserver.cnのmemcacheduserverubyuukey関数」では、「libmemcached/memcachedcached.ccのmemcachedcachedcachedcy.cy.cd中のmemcacheduhash関数」を呼び出します.
この関数で重要なことを3つ作りました.
1.探しているkeyのhash値を生成する
2.必要であれば、サーバーの整合性hashポイントセットを更新します.
3.keyをサーバに分布する
私たちはそれぞれこの3つのことを見に来ました.
1.keyのhash値を生成する:
引き続きコードを追跡して、私達はgenerate_で発見します.hash関数には次のようなコードがあります.
hash=memcached_ゲナート_hashvalue(key,keymulength,ptr->hash);
memcached_を見るゲナート_hashvalue関数のソースは、この関数が3番目のパラメータで指定されたhashアルゴリズムを使用してkeyのhash値を生成することを知っています.ここではptr->hashを使用しています.
注:ptrは前述のmemcached_です.リスト構造
2.サーバの整合性を更新するhashポイントセット
ここで、必要でなくても、コードの中のaddServer呼び出しをテストする時には、この関数を実行します.だから、私達はその中でやったことに注目したいです.
私達はudateに追跡します.continuum関数では、ソースコードを分析し、この関数が行うことをまとめ、phpコードで以下のように説明します.

<?php
$servers	= array(
	array('10.8.8.32', 11301), 
	array('10.8.8.32', 11300), 
);
$points		= array();
$index		= 0;
foreach ( $servers as $server ) {
	$i	= 0;
	while ( $i ++ < 100 ) { //libmemcached 100         
		$points[]	= array(
			'index'	=> $index, 
			'value'	=> hash_value, 
		);
	}
	$index ++;
}
//    $servers     'value'  

、つまり、keyとして100 hash値を生成し、すべてのサーバで生成されたこれらhash値を並べ替える.
ここはlibmemcachedのudate_です.continuumでは、次のコードを見つけます.

value= memcached_generate_hash_value(sort_host, sort_host_length, ptr->hash_continuum);

つまり、各点のhash値を求めて、ここでptrのhash_を使っています.continuumフィールドによって与えられたhashアルゴリズム計算.
3.keyをサーバに分布する
ここでの分布過程とは、上で発生したポイントセットを二分割検索し、keyのhash値から一番近い点を見つけて、その対応サーバーをkeyのサーバとして、phpコードで下記のように説明します.

<?php
$points	= array();	//             
$hash	= 1;		//    key hash 
$begin = $left = 0;
$end = $right = floor(count($points) / 2);
while ( $left < $right ) {
	$middle	= $left + floor(($left + $right) / 2);
	if ( $points[$middle]['value'] < $hash ) $left = $middle + 1;
	else $right = $middle;
}
//      
if ( $right = $end ) $right = $begin;
//      key                $index 
$index	= $servers[$right]['index'];

主な過程の分析が終わりました.この問題を引き起こした肝心な点に対して赤い字で表示しました.keyとサーバに対してhash値を求めるアルゴリズムはmemcached_にあります.st構造は異なるフィールドで指定されています.
それでは、問題は明らかになりました.私達はphp-memcachedのsetOption方法の実現を見てみます.ptr->hashフィールドを修正しただけです.
したがって、テストケースの動作状況は:
keyに対してcrcアルゴリズムを使ってhashを求めます.
サーバのポイントセットにデフォルトのアルゴリズムを使ってhash値を求めます.
二つのアルゴリズムを比較した結果、デフォルトのアルゴリズムではsh値が大きく、crcで発生するsh値は最大で数万円のようです.(具体的な上限は計算されていません)
したがって、サーバーポイントセットのhash値はkeyによって生成されたhash値よりも大きいので、検索する時は常に点セットの最初の点に落ちます.
これで問題の原因が明らかになり、解決方法も明らかになった.phpのmemcached拡張を修正し、setOptionに修正ptr->hash_を追加する.continuumフィールドの操作は、テストケースに応答して修正すれば良いです.
次の文章はlibmemcachedソースコードから抽出された簡略版一致hashアルゴリズムを示します.簡単明瞭で、libmemcachedの一致性hashアルゴリズムの実現を簡単に説明できます.
libmemcached一致性hashアルゴリズム詳細解(2)----簡略化版のlibmemcached一致性hashアルゴリズムを実装します.