PHP一致性哈希

浏览数：23 / 时间：2015年06月09日

什么是一致性哈希参考这里：

http://zh.wikipedia.org/zh/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C#.E5.BA.94.E7.94.A8.E5.AE.9E.E4.BE.8B

和这里：

http://baike.baidu.com/view/1588037.htm

classes/Consistenthashing.php

  1 <?php
  2 /**
  3  * 一致性哈希
  4  * @author Sundj
  5  * 
  6  * demo:
  7  *         $servers = array(
  8  *             ‘rm11950.eos.com.cn‘,
  9  *             ‘rm11951.eos.com.cn‘,
 10  *             ‘rm11952.eos.com.cn‘,
 11  *             ‘rm11953.eos.com.cn‘,
 12  *             ‘rs11950.hebe.com.cn‘,
 13  *             ‘rs11951.hebe.com.cn‘,
 14  *             ‘rs11952.hebe.com.cn‘,
 15  *             ‘rs11953.hebe.com.cn‘,
 16  *             ‘rs11950.atlas.com.cn‘,
 17  *             ‘rs11951.atlas.com.cn‘,
 18  *             ‘rs11952.atlas.com.cn‘,
 19  *             ‘rs11953.atlas.com.cn‘
 20  *         );
 21  *         
 22  *         $consistentHashing = Consistenthashing::instance()->addNodes($servers);
 23  *         
 24  *         for($i = 0; $i < 10; $i++) {
 25  *             echo $consistentHashing->getNode(chr(mt_rand(33, 126)))."\r\n";
 26  *         }
 27  */
 28 final class Consistenthashing {
 29     
 30     static protected $_instance = NULL;
 31     
 32     static public function instance($name = ‘‘) {
 33         
 34         if(self::$_instance === NULL) {
 35             if($name == ‘‘) {
 36                 $name = ‘md5‘;
 37             }
 38             
 39             $hasher = Consistenthashing_Hasher::factory($name);
 40             $config = Kohana::$config->load(‘consistenthashing.md5‘);
 41             
 42             self::$_instance = new self($hasher, $config);
 43         }
 44         
 45         return self::$_instance;
 46     }
 47     
 48     protected $_replicas = 1;
 49     
 50     protected $_hasher = NULL;
 51 
 52     protected $_nodes = array();
 53     
 54     protected $_virtualNodes = array();
 55     
 56     public function __construct(Consistenthashing_Hasher $hasher, array $config) {
 57         
 58         if(!$config) {
 59             throw new Consistenthashing_Exception(‘$config is needed.‘);
 60         }
 61         
 62         $this->_hasher = $hasher;
 63         
 64         if(isset($config[‘replicas‘])) {
 65             $this->_replicas = $config[‘replicas‘];
 66         }
 67     }
 68     
 69     /**
 70      * 增加节点
 71      * @param string $node
 72      * @return Consistenthashing
 73      */
 74     public function addNode($node = NULL) {
 75         if(!$node) {
 76             throw new Consistenthashing_Exception(‘node: $node can\‘t be NULL‘);
 77         }
 78         
 79         $hash = $this->_hasher->hash($node);
 80         if(isset($this->_nodes[$hash])) {
 81             return $this;
 82         }
 83         $this->_nodes[$hash] = $node;
 84         
 85         for($i = 0; $i < $this->_replicas; $i++) {
 86             $virtualNode = $node .‘#‘. $i;
 87             $hash = $this->_hasher->hash($virtualNode);
 88             
 89             $this->_virtualNodes[$hash] = $node;
 90         }
 91         
 92         ksort($this->_virtualNodes);
 93         
 94         return $this;
 95     }
 96     
 97     /**
 98      * 批量增加节点
 99      * @param array $nodes
100      * @return Consistenthashing
101      */
102     public function addNodes(array $nodes = array()) {
103         foreach($nodes as $node) {
104             $this->addNode($node);
105         }
106         return $this;
107     }
108     
109     /**
110      * 删除一个节点
111      * @param object $node
112      */
113     public function removeNode($node = NULL) {
114         $hash = $this->_hasher->hash($node);
115         if(!isset($this->_nodes[$hash])) {
116             return $this;
117         }
118         unset($this->_nodes[$hash]);
119         
120         for($i = 0; $i < $this->_replicas; $i++) {
121             $virtualNode = $node .‘#‘. $i;
122             
123             $hash = $this->_hasher->hash($virtualNode);
124             unset($this->_virtualNodes[$hash]);
125         }
126         return $this;
127     }
128     
129     /**
130      * 批量删除节点
131      * @param array $nodes
132      * @return Consistenthashing
133      */
134     public function removeNodes(array $nodes = array()) {
135         foreach($nodes as $node) {
136             $this->removeNode($node);
137         }
138         return $this;
139     }
140     
141     /**
142      * 全部节点(虚拟)
143      * @return array
144      */
145     public function all() {
146         return $this->_virtualNodes;
147     }
148     
149     /**
150      * 获得节点
151      * @param string $key
152      * @return string
153      */
154     public function getNode($key) {
155         $hashKey = $this->_hasher->hash($key);
156         
157         $nodeFound = NULL;
158         $counter = 0;
159         foreach($this->_virtualNodes as $hash => $node) {
160             if($counter == 0) {
161                 $nodeFound = $node;
162             }
163             if($hash > $hashKey) {
164                 $nodeFound = $node;
165                 break;
166             }
167         }
168         
169         return $nodeFound;
170     }
171 }

classes/Consistenthashing/Hasher.php

 1 <?php
 2 abstract class Consistenthashing_Hasher {
 3 
 4     static public function factory($name) {
 5         if($name == ‘md5‘) {
 6             return new Consistenthashing_Hasher_Md5();
 7         }
 8         if($name == ‘sha1‘) {
 9             return new Consistenthashing_Hasher_Sha1();
10         }
11         if($name == ‘crc32‘) {
12             return new Consistenthashing_Hasher_Crc32();
13         }
14         throw new Consistenthashing_Exception("Undefined hashing method: {$name}. md5, sha1 and crc32 are supported.");
15     }
16     
17     abstract public function hash($object);
18     
19 }

classes/Consistenthashing/Hasher/Md5.php

<?php
class Consistenthashing_Hasher_Md5 extends Consistenthashing_Hasher {
    
    public function hash($object) {
        return md5($object);
    }
    
}

config/consistenthashing.php

 1 <?php
 2 return array(
 3     ‘md5‘ => array(
 4         ‘replicas‘ => 64,
 5     ),
 6         
 7     ‘crc32‘ => array(
 8         ‘replicas‘ => 64,
 9     ),
10         
11     ‘sha1‘ => array(
12         ‘replicas‘ => 64,
13     ),
14 );