参考文章
http://blog.chinaunix.net/uid-20498361-id-4303232.html
http://blog.csdn.net/kongqz/article/details/6695417
https://my.oschina.net/goal/blog/203593?p=1
一直认为一致性hash是个很神奇的东东，技术大牛的想法果然不同凡响。
下列代码并没有作优化处理，仅供参考理解ketama算法，当然也有助于自己理解记忆。如果有错误的地方欢迎指出
function addServer($hostName = array()){
$serverList = array();
foreach($hostName as $val) {
for($i = 0;$i<40;$i++) {
$digest = md5($val.'_'.$i, true);
for ($h = 0; $h < 4; $h++) {
$hash = (ord($digest[3 + $h * 4]) << 24) | (ord($digest[2 + $h * 4]) << 16)
| (ord($digest[1 + $h * 4]) << 8) | ord($digest[$h * 4]);
$serverList[$val][$i*4+$h] = $hash;
}
}
}
return $serverList;
}
//md5的原因是怕用户输入前缀一致 hash一样 分布不均匀？？
function getKeyHash($str){
$digest = md5($str,1);
return (ord($digest[3])<<24) | (ord($digest[2])<<16) | (ord($digest[3])<<8) | (ord($digest[0]));
}
function findKey($str){
$hostName = array(
'10.100.20.1',
'10.100.20.2',
'10.100.20.3',
'10.100.20.4',
'10.100.20.5',
'10.100.20.6',
);
$serverList = addServer($hostName);
$serverHash = array();
foreach($serverList as $server){
$serverHash = array_merge($serverHash,$server);
}
sort($serverHash);
$i = 0;
$len = count($serverHash);
$keyHash = getKeyHash($str);
if($keyHash>$serverHash[$len-1]){
foreach($serverList as $key=>$val){
if(in_array($serverHash[$len-1],$val)){
return $key;
}
}
return 0;
}
while($i<$len){
$curr = $serverHash[$i];
$next = $serverHash[++$i];
if($next>=$keyHash && $keyHash>=$curr){
foreach($serverList as $key=>$val){
if(in_array($serverHash[$i],$val)){
return $key;
}
}
}
}
return false;
}
$result = array();
for($i=1;$i<1000;$i++){
$tmp = findKey('key'.$i);
if(isset($result[$tmp])){
$result[$tmp]++;
}else{
$result[$tmp] = 0;
}
}
print_r($result);
上面输出结果如下，所以说该算法分布还是相当均匀的。
[root@silence suanfa]# php ketama.php
Array
(
[10.100.20.6] => 149
[10.100.20.5] => 162
[10.100.20.4] => 171
[10.100.20.2] => 146
[10.100.20.3] => 196
[10.100.20.1] => 169
)
查找键值所在服务器可以采用下列折半的方式
$rangeArr =
array (
0 => 19,
1 => 99,
2 => 47,
3 => 49,
4 => 74,
5 => 77,
6 => 45,
7 => 95,
8 => 87,
9 => 15,
10 => 14,
11 => 29,
12 => 57,
13 => 3,
14 => 8,
15 => 38,
16 => 28,
17 => 67,
18 => 55,
19 => 43,
20 => 5,
21 => 25,
22 => 48,
23 => 32,
24 => 58,
25 => 90,
26 => 27,
27 => 50,
28 => 6,
29 => 63,
30 => 65,
31 => 81,
32 => 51,
33 => 52,
34 => 66,
35 => 30,
36 => 56,
37 => 54,
38 => 86,
39 => 84,
40 => 83,
41 => 64,
42 => 42,
43 => 26,
44 => 46,
45 => 79,
46 => 69,
47 => 98,
48 => 24,
49 => 37,
);
sort($rangeArr);
function findPoint($num,$rangeArr){
$len = count($rangeArr);
if($num> $rangeArr[$len-1] || $num<$rangeArr[0]){
return $num.'in'.$rangeArr[0];
}
if($len == 2){
return $num.'in'.$rangeArr[1];
}
if($len == 1){
return $num.'in'.$rangeArr[0];
}
$half =(int)floor($len/2);
if($num<$rangeArr[$half]){
$tmp = array_slice($rangeArr,0,$half+1);
return findPoint($num,$tmp);
}else{
$tmp = array_slice($rangeArr,$half,$len-$half);
return findPoint($num,$tmp);
}
}
echo findPoint(4,$rangeArr);exit;