一致性哈希算法的理解
作者: 何忠利 • 发表于 2018-09-22
阅读文章前需要您对一致性哈希算法基本概念有一定了解认识（哈希环，虚拟节点）。
开始正文
很早之前就有听说过这个算法，把各个服务器落在2的32次方-1的一个哈希环上，把存储的key通过算法把它存储在对应的下一个服务器上。但是，当我们发现当服务器节点特别少的时候这个哈希环可能分布的不是特别均匀，可能出现最坏的情况（大部分都存储在一台服务器节点中），这时候就抛出了虚拟节点的概念，当我们虚拟节点越多这个哈希环就分布越均匀便可解决该问题。
代码如下
<?php
$vmNodeList = []; // 初始化
$config = array(
array('ip' => '10.211.55.1','start' => 1,'end' => 100), // 配置服务器并且创造虚拟节点（可实现权重）
array('ip' => '10.211.55.2','start' => 101,'end' => 200),
array('ip' => '10.211.55.3','start' => 201,'end' => 300),
array('ip' => '10.211.55.4','start' => 301,'end' => 400),
array('ip' => '10.211.55.5','start' => 401,'end' => 800), // 权重后约1/2的key会落在该节点上
);
// 创造配置文件对应的虚拟节点
foreach ($config as $node) {
for ($i = $node['start'];$i <= $node['end']; $i++) {
$vmNodeList[crc32($i)] = $node['ip'];
}
}
// 函数：返回key经过crc32过后,下一个节点的ip地址
function foundNext($vmNodeList, $crckey){
$isFound = false;
foreach ($vmNodeList as $key => $val) {
if ($isFound == true) {
return $val;
}
if ($key == $crckey) {
$isFound = true;
}
}
return current($arr); // 没有下一个默认第一个。
}
// 开始实验
$key = 'order_1';
$crckey = crc32($key); // 注意在32位系统可能出现负数情况，请使用sprintf。
if(isset($vmNodeListvmNodeList[$crckey])){
$ip = $vmNodeList[$crckey]; // 找到服务器地址
}else{
$vmNodeList[$crckey] = null;
ksort($vmNodeList);
$ip = foundNext($vmNodeList,$crckey);
unset($vmNodeList[$crckey]);
}
die($ip); // $key的存储与获取都落在这个ip上总结：
一致性哈希算法的PHP大致伪代码就是这样子，不得不感慨计算机神奇美妙之处。
一致性哈希算法已经应用在比较著名的缓存系统Memcached中，如有比较大型分布式缓存系统建议优先实现用Memcached缓存。Redis的话不建议使用，后期的话我们也会介绍下Redis的关键核心技术。
如有理解不到位的地方，欢迎邮箱指出。转发注明出处！
文章关键词：
# 一致性哈希
# Memcached缓存
阅读量：
999
返回主页
