[php]对服务器进行一致性hash分布算法

1. <?php
   
2. /**
   
3.  * 对服务器进行一致性hash分布算法
   
4.  */
   
5. class HashRing
   
6. {
   
7.     private $servers = array();
   
8.     private $nodeList = array();
   
9.     private $nodeHashList = array();
   
10.     private $nodeTotalNum = 0;
    
11.     private $virtualNodeNum = 32;
    
12.     private $keyHash = '';
    
13. 
    
14.     public function __construct($servers)
    
15.     {
    
16.         $this->servers = $servers;
    
17.         foreach ($servers as $server) {
    
18.             for ($i = 0; $i < $this->virtualNodeNum; $i++) {
    
19.                 $this->nodeList[sprintf("%u", crc32($server.'-'.$i))] = array($server, $i);
    
20.             }
    
21.         }
    
22.         ksort($this->nodeList);
    
23.         $this->nodeHashList = array_keys($this->nodeList);
    
24.     }
    
25. 
    
26.     private function getNodeIndex($key)
    
27.     {
    
28.         $this->keyHash = sprintf("%u", crc32($key));
    
29.         if ($this->keyHash > end($this->nodeHashList)) {
    
30.             $this->keyHash = $this->keyHash % end($this->nodeHashList);
    
31.         }
    
32.         if ($this->keyHash <= reset($this->nodeHashList)) {
    
33.             return 0;
    
34.         }
    
35.         $this->nodeTotalNum = count($this->nodeHashList);
    
36.         return $this->binaryChopIndex(0, $this->nodeTotalNum);
    
37.     }
    
38. 
    
39.     private function binaryChopIndex($l=0, $r=0)
    
40.     {
    
41.         if ($l < $r) {
    
42.             $avg = intval(($l+$r) / 2);
    
43.             if ($this->nodeHashList[$avg] == $this->keyHash) {
    
44.                 return $avg;
    
45.             } elseif ($this->keyHash < $this->nodeHashList[$avg] && ($avg > 0)) {
    
46.                 return $this->binaryChopIndex($l, $avg-1);
    
47.             } else {
    
48.                 return $this->binaryChopIndex($avg+1, $r);
    
49.             }
    
50.         } else {
    
51.             return $l;
    
52.         }
    
53.     }
    
54. 
    
55.     public function getServersByKey($key, $num=1)
    
56.     {
    
57.         $index = $this->getNodeIndex($key);
    
58.         $server = $this->nodeList[$this->nodeHashList[$index]];
    
59.         if ($num == 1) {
    
60.             return $server[0];
    
61.         }
    
62.         if ($num >= count($this->servers)) {
    
63.             $num = count($this->servers);
    
64.         }
    
65.         $result = array($server[0]);
    
66.         for ($i=$index+1; true; $i++) {
    
67.             if ($i >= $this->nodeTotalNum) {
    
68.                 $i = 0;
    
69.             }
    
70.             $nextServer = $this->nodeList[$this->nodeHashList[$i]];
    
71.             if (!in_array($nextServer[0], $result)) {
    
72.                 $result[] = $nextServer[0];
    
73.             }
    
74.             if (count($result) == $num) {
    
75.                 break;
    
76.             }
    
77.         }
    
78.         return $result;
    
79.     }
    
80. }
    
81. 
    
82. 
    
83. 
    
84. //示例
    
85. $servers = array(
    
86.     '127.0.0.1:11211',
    
87.     '127.0.0.1:11212',
    
88.     '127.0.0.1:11213',
    
89.     '127.0.0.1:11214',
    
90.     '127.0.0.1:11215'
    
91. );
    
92. $obj = new HashRing($servers);
    
93. $servers = $obj->getServersByKey('testkey', 2);
    
94. print_r($servers);
    
95. echo "\n";