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*/ 28finalclass Consistenthashing {
 29 30staticprotected$_instance = NULL;
 31 32staticpublicfunction instance($name = ‘‘) {
 33 34if(self::$_instance === NULL) {
 35if($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 45return self::$_instance;
 46    }
 47 48protected$_replicas = 1;
 49 50protected$_hasher = NULL;
 51 52protected$_nodes = array();
 53 54protected$_virtualNodes = array();
 55 56publicfunction __construct(Consistenthashing_Hasher $hasher, array$config) {
 57 58if(!$config) {
 59thrownew Consistenthashing_Exception(‘$config is needed.‘);
 60        }
 61 62$this->_hasher = $hasher;
 63 64if(isset($config[‘replicas‘])) {
 65$this->_replicas = $config[‘replicas‘];
 66        }
 67    }
 68 69/**
 70     * 增加节点
 71     * @param string $node
 72     * @return Consistenthashing
 73*/ 74publicfunction addNode($node = NULL) {
 75if(!$node) {
 76thrownew Consistenthashing_Exception(‘node: $node can\‘t be NULL‘);
 77        }
 78 79$hash = $this->_hasher->hash($node);
 80if(isset($this->_nodes[$hash])) {
 81return$this;
 82        }
 83$this->_nodes[$hash] = $node;
 84 85for($i = 0; $i < $this->_replicas; $i++) {
 86$virtualNode = $node .‘#‘. $i;
 87$hash = $this->_hasher->hash($virtualNode);
 88 89$this->_virtualNodes[$hash] = $node;
 90        }
 91 92ksort($this->_virtualNodes);
 93 94return$this;
 95    }
 96 97/**
 98     * 批量增加节点
 99     * @param array $nodes
100     * @return Consistenthashing
101*/102publicfunction addNodes(array$nodes = array()) {
103foreach($nodesas$node) {
104$this->addNode($node);
105        }
106return$this;
107    }
108109/**
110     * 删除一个节点
111     * @param object $node
112*/113publicfunction removeNode($node = NULL) {
114$hash = $this->_hasher->hash($node);
115if(!isset($this->_nodes[$hash])) {
116return$this;
117        }
118unset($this->_nodes[$hash]);
119120for($i = 0; $i < $this->_replicas; $i++) {
121$virtualNode = $node .‘#‘. $i;
122123$hash = $this->_hasher->hash($virtualNode);
124unset($this->_virtualNodes[$hash]);
125        }
126return$this;
127    }
128129/**
130     * 批量删除节点
131     * @param array $nodes
132     * @return Consistenthashing
133*/134publicfunction removeNodes(array$nodes = array()) {
135foreach($nodesas$node) {
136$this->removeNode($node);
137        }
138return$this;
139    }
140141/**
142     * 全部节点(虚拟)
143     * @return array
144*/145publicfunction all() {
146return$this->_virtualNodes;
147    }
148149/**
150     * 获得节点
151     * @param string $key
152     * @return string
153*/154publicfunction getNode($key) {
155$hashKey = $this->_hasher->hash($key);
156157$nodeFound = NULL;
158$counter = 0;
159foreach($this->_virtualNodes as$hash => $node) {
160if($counter == 0) {
161$nodeFound = $node;
162            }
163if($hash > $hashKey) {
164$nodeFound = $node;
165break;
166            }
167        }
168169return$nodeFound;
170    }
171 }

             1 <?php
 2abstractclass Consistenthashing_Hasher {
 3 4staticpublicfunction factory($name) {
 5if($name == ‘md5‘) {
 6returnnew Consistenthashing_Hasher_Md5();
 7        }
 8if($name == ‘sha1‘) {
 9returnnew Consistenthashing_Hasher_Sha1();
10        }
11if($name == ‘crc32‘) {
12returnnew Consistenthashing_Hasher_Crc32();
13        }
14thrownew Consistenthashing_Exception("Undefined hashing method: {$name}. md5, sha1 and crc32 are supported.");
15    }
1617abstractpublicfunction hash($object);
1819 }

<?php
class Consistenthashing_Hasher_Md5 extends Consistenthashing_Hasher {
    
    publicfunction hash($object) {
        returnmd5($object);
    }
    
}

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