一致哈希算法介绍参考文章《一致哈希算法理解(一致哈希学习笔记一)》
回顾一致哈希算法步骤:
0、将每一个服务器节点按照ip或者server_name, 通过hash函数(eg: crc32)得到对应的一组hash整数值,这里称做hash_servers,并对得到的整数值按由小到大进行排序。
1、将key也通过上面同一个hash函数计算得到对应hash整数值, 这里称为hash_key。
2、遍历hash_servers,用hash_key与hash_servers中的数逐个比较,当hash_key最后小于hash_servers中的那个数存在时,这个数对应的节点就是这个key所存储的节点,否则存在第一个节点。
一致哈希算法PHP的一种实现
/** * 一致哈希PHP的一种实现 * * @link * @author salmonl * @date 2018-08-24 */ class ConsistentHashing { // 每个节点对应虚拟节点数 const VIRTUAL_NODES = 32; protected $nodes = []; protected $position = []; /** * 添加节点 */ public function add_node($node) { if (isset($this->nodes[$node])) { return; } // 添加节点和虚拟节点 for ($i = 0; $i < self::VIRTUAL_NODES; $i++) { $pos = $this->my_hash($node . '-' . $i); $this->position[$pos] = $node; $this->nodes[$node][] = $pos; } // 重新排序 $this->sort_position(); } /** * 删除节点 */ public function del_node($node) { if (!isset($this->nodes[$node])) return; // 循环删除虚拟节点 foreach ($this->nodes[$node] as $val) { unset($this->position[$val]); } // 删除节点 unset($this->nodes[$node]); } /** * 定位key所属节点 */ public function lookup($key) { $point = $this->my_hash($key); // 先取圆环上最小的一个节点,当成结果 $node = current($this->position); // 循环获取相近的节点 foreach ($this->position as $key => $val) { if ($point <= $key) { $node = $val; break; } } // 指向第一个单元 reset($this->position); return $node; } /** * 按键名排序 */ private function sort_position() { ksort($this->position); } /** * 自定义哈希函数,把key转为32位符号整数 */ private function my_hash($key) { return sprintf('%u', crc32($key)); } } // 测试 $ch = new ConsistentHashing(); $ch->add_node('N1'); $ch->add_node('N2'); $ch->add_node('N3'); $k1 = 'niliu_k1'; $k2 = 'niliu_k2'; echo 'key ' . $k1 . '落在' . $ch->lookup($k1) . '节点上' . PHP_EOL; echo 'key ' . $k2 . '落在' . $ch->lookup($k2) . '节点上' . PHP_EOL; $ch->del_node('N1'); $k1 = 'niliu_k1'; $k2 = 'niliu_k2'; echo 'after delete node' . PHP_EOL; echo 'key ' . $k1 . '落在' . $ch->lookup($k1) . '节点上' . PHP_EOL; echo 'key ' . $k2 . '落在' . $ch->lookup($k2) . '节点上' . PHP_EOL; // output key niliu_k1落在N1节点上 key niliu_k2落在N3节点上 after delete node key niliu_k1落在N3节点上 key niliu_k2落在N3节点上
更多语言实现可参考:Implementations in various languages