10 Memcached 一致性哈希分布式算法原理与实现[PHP实现]

 1 <?php  
 2 
 3 header("Content-type:text/html;charset=utf-8");
 4 
 5 interface  hash{
 6 
 7     public function _hash($str);
 8 }
 9 interface distribution{
10 
11     public function lookup($key);
12 }
13 /****
14 一致性哈希分布式算法原理与实现[PHP实现]
15 **/
16 class Consistent  implements hash,distribution{
17     #存放实际节点
18     protected $_nodes=array();
19     #定义虚拟节点的个数
20     protected $mul=64;
21     #定义一个位置数组 记录节点所在位置
22     protected $_position=array();
23     #算出节点
24     public function _hash($str){
25         return sprintf('%u',crc32($str));//把字符串转成32位符号的整数
26     }
27     #核心功能
28     public function lookup($key){
29         #算出当前节点
30         $point=$this->_hash($key);
31         $node=current($this->_position);//先取圆环上最小的一个节点
32         #循环所以节点
33         foreach($this->_nodes as $k=>$v){
34             #找到当前节点所在在的节点数,如果没找到说明大于所以节点 既在最小的节点上
35             if($point<=$k){
36                $node=$v;
37                break;
38             }
39         }
40         return $node;
41     }
42     #增加一个节点
43     public function addNode($node){
44         #存储到数组中去  arrar([key=>val])
45         //$this->_nodes[$this->_hash($node)]=$node;
46         for ($i=0; $i < $this->mul; $i++) { 
47             $this->_position[$this->_hash($node.'-'.$i)]=$node;
48         }
49         $this->_sortNode();
50 
51     }
52     #删除一个节点
53     public function delNode($node){
54         foreach ($this->_position as $k => $v) {
55             if($v==$node){
56                 unset($this->_position[$k]);
57             }
58         }
59     }
60     #排序
61     protected function _sortNode(){
62         #SORT_REGULAR 根据key的大小进行排序
63         ksort($this->_position,SORT_REGULAR);
64     }
65     #打印出所有的虚拟节点
66     public function getNodes(){
67         var_dump($this->_position);
68     }
69 }
70 $con=new Consistent();
71 $con->addNode('a');
72 $con->addNode('b');
73 $con->addNode('c');
74 
75 
76 echo '当前所以服务器如下：<br/>';
77  $con->getNodes();
78 echo '<br/>当前的建计算的hsas落点是'.$con->_hash('name').'<br/>';
79 echo  'name'.'在'.$con->lookup('name').'节点上';