架构师训练营 - 第五章 - 一致性 hash 算法
发布于: 2020 年 07 月 08 日
在分布式系统当中，一般都会有 N 台机器组成服务集群。我们可能会将数据分布到很多台机器上，每次有请求到来的时候，将请求分配到对应的机器上执行。
这里，我们如果不知道数据被存储到了哪台机器，那么每次有请求来的时候，我们都需要遍历一遍集群内的机器去查询数据，这样的性能是不能容忍的。
对于数据该存储在哪台机器的问题，可以有不同的处理策略。
除了上面提到的随机分配，还有 hashcode 取模和一致性 hash、带虚拟节点的一致性 hash 算法。
一·hashcode 取模
hashcode 取模是一个比较简单的 hash 算法。我们计算存储的 key 的 hashcode，用 hashcode 对集群内机器数量取模，得到的数就是机器的 id。将数据存储到对应 id 的机器上，有请求来的时候，也根据这个算法，到对应的机器上取数据。
网上找来的，redis集群取数逻辑。
这个只是为了表示简单hash策略，redis集群并一定是这样的。
简单 hash 取模算法有个很大的弊端。如果集群中有机器新增或者删除时，剩余的机器数量就会变化。
那么每个 key 的 hash 取模得到的结果大部分都会变化，那么会导致大量的缓存请求不到，进而导致请求落入后端的数据库，导致缓存雪崩，严重时，可能会导致服务整体崩溃。
二·一致性 hash 算法
一致性 hash 算法解决了上述的弊端，尽可能的减少了服务器增减时，缓存的变更。
一致性 hash 算法是将集群想象成一个环状，每个服务器都是落在环上的一个。
不用想，也是从网上找来的，感谢原博主。
上图是一个例子。实现设定一个足够大的空间（一般为 2^32-1），集群中四个服务器，使用服务器的标识取 hashcode 针对空间取模 ,四个服务器分布在空间内的四个位置。
这个时候如果有请求过来，比如要查询 user1 的信息，那么使用 user1 的 key 取 hashcode 针对空间取模，得到一个位置，从当前位置顺时针查找可用的机器，找到的第一台机器就是当前 key 所在的机器。
简单一致性 hash 解决了有机器增减时，数据位置全都改变的尴尬局面。在上述例子中，如果 ip2 服务器被剔除，那么只有 user1 和 user2 的数据会落到 ip3 服务器上，其余的数据则不变。
简单一致性 hash 虽然解决了增加机器的问题，但是本身也有不小的缺陷。就是如果服务器本身 hashcode 分布不均匀，那么就可能导致数据分布严重倾斜。
这就是服务器分布不均的样子
上图就是服务器分布不均的样子，可想而知，上图中的例子，大量的 key 会落到 ip2、ip1、ip3 上，ip4 和 ip5 则少的多。
三、带虚拟节点的一致性 hash 算法
为了解决服务器分布不均的问题，一致性 hash 算法又演变出带虚拟节点的一致性 hash 算法。
带虚拟节点的一致性hash算法。
带虚拟节点的一致性 hash 算法，我比较喜欢上面这张图。
先是维护一个足够大的虚拟节点结合。每一个请求进来的时候，根据 key 的 hashcode 分布到虚拟节点上，我们需要重视解决的问题就变成了维护虚拟节点和实体节点之间的关系，维持实体节点关联尽可能平均的虚拟节点。
代码实现
代码实现的类图
<?phpnamespace consistenthashVirtualNode;
/** * 缓存接口 * * 缓存接口提供get和set方法 * * Interface CacheInterface * @package consistenthashVirtualNode */interface CacheInterface{ /** * 根据hash key获取值 * @param string $hashKey * @return mixed */ public function get(string $hashKey);
/** * 添加一个值 * @param string $hashKey * @param $value * @return mixed */ public function set(string $hashKey, $value);
}复制代码
<?php
namespace consistenthashVirtualNode;
require_once __DIR__ . '/CacheInterface.php';
interface CacheManager extends CacheInterface{ public function addNode(NodeInterface $node);
public function removeNode(NodeInterface $node);
}复制代码
<?php
namespace consistenthashVirtualNode;require_once __DIR__ . '/CacheInterface.php';
interface NodeInterface extends CacheInterface{ public function getName();
public function equal(NodeInterface $node);
public function getLinkedVirtualNode();
public function linkVirtualNode(VirtualNodeInterface $virtualNode);
public function removeVirtualNode(VirtualNodeInterface $virtualNode);
public function countCacheKey();}
复制代码
<?php
namespace consistenthashVirtualNode;require_once __DIR__ . '/CacheInterface.php';
/** * 虚拟节点 * * 一个虚拟节点只关联一个实体节点 * * Interface VirtualNodeInterface * @package consistenthashVirtualNode */interface VirtualNodeInterface extends CacheInterface{ public function getLinkedNode();
public function linkNode(NodeInterface $oneNode);
public function equal(VirtualNodeInterface $virtualNode): bool;
public function getName();}复制代码
<?php
namespace consistenthashVirtualNode;require_once __DIR__ . '/CacheManager.php';require_once __DIR__ . '/VirtualNode.php';
use consistenthashVirtualNode\VirtualNode;
class Cache implements CacheManager{ private $hashCode = 150; /** * 实际节点list * @var array */ private $nodeList = []; /** * 虚拟节点list * @var array */ private $virtualNodeList = [];
public function __construct(int $hashCode = 50) { $this->hashCode = $hashCode; //初始化虚拟节点 for ($step = 0; $step < $this->hashCode; $step++) { $this->virtualNodeList[] = new VirtualNode("vnode_" . $step); } }
private function sortNodeListByVirtualNodeDesc(NodeInterface $node1, NodeInterface $node2) { $countVirtualNodeNode1 = count($node1->getLinkedVirtualNode()); $countVirtualNodeNode2 = count($node2->getLinkedVirtualNode()); //如果node1的虚拟节点比node2的虚拟节点多, 则排前面 if ($countVirtualNodeNode1 > $countVirtualNodeNode2) { return -1; } else if($countVirtualNodeNode2 == $countVirtualNodeNode1) { return 0; } return 1; }
/** * 添加一个实体节点 * @param NodeInterface $node */ public function addNode(NodeInterface $node) { if (empty($this->nodeList)) { //所有虚拟节点都指向该节点 foreach ($this->virtualNodeList as $oneVirtualNode) { $oneVirtualNode->linkNode($node); $node->linkVirtualNode($oneVirtualNode); } $this->nodeList[] = $node;
return true; } //添加一个实体节点 //获取 添加一个节点后，虚拟节点与实体节点的比例 = 一个实体节点应该关联的虚拟节点的数量 $proportionNew = ceil(count($this->virtualNodeList) / (count($this->nodeList) + 1));
//针对实体节点进行排序，关联虚拟节点较多的排前面 usort($this->nodeList, [$this, 'sortNodeListByVirtualNodeDesc']); //从每个实体节点关联的虚拟节点去除（x-y）个虚拟节点，用来关联新的实体节点
for ($step = 0; $step < count($this->nodeList); $step++) { if (count($node->getLinkedVirtualNode()) > $proportionNew) { //新实体节点关联的虚拟节点达到均值，则不再执行 break; } $virtualList = $this->nodeList[$step]->getLinkedVirtualNode(); $needSub = count($virtualList) - $proportionNew;//当前实体节点应该均给新节点的虚拟节点 if ($needSub <= 0) { continue; }
$virtualList = array_slice($virtualList, 0, $needSub); foreach ($virtualList as $oneVirtaulNode) { //从实体关联节点中移除 $this->nodeList[$step]->removeVirtualNode($oneVirtaulNode); $oneVirtaulNode->linkNode($node); $node->linkVirtualNode($oneVirtaulNode); } } $this->nodeList[] = $node; return true; }
/** * 移除一个实体节点 * @param NodeInterface $node */ public function removeNode(NodeInterface $node) { if (1 == count($this->nodeList) && $this->nodeList[0]->equal($node)) { $this->nodeList = []; return true; } //移除一个实体节点 $virtualNodeList = $node->getLinkedVirtualNode();//待关联的虚拟节点 $needAdd = floor(count($virtualNodeList) / (count($this->nodeList) - 1)); //将被移除的实体节点所关联的虚拟节点， 按照每个实体节点分（y-x）个关联
for ($step = 0; $step < count($this->nodeList); $step++) { //从当前实体节点中移除 if ($this->nodeList[$step]->equal($node)) { array_splice($this->nodeList, $step, 1); break; } if (empty($virtualNodeList)) { break; } $tmpVirtualNodeList = array_slice($virtualNodeList, 0, $needAdd); $virtualNodeList = array_slice($virtualNodeList, $needAdd - 1); //将虚拟节点分配给对应的实体节点 foreach ($tmpVirtualNodeList as $oneVirtualNode) { $oneVirtualNode->linkNode($this->nodeList[$step]); $this->nodeList[$step]->linkVirtualNode($oneVirtualNode); } } //如果剩余虚拟节点不为空， 则随机赋给一台机器 if (!empty($virtualNodeList)) { foreach ($virtualNodeList as $oneVirtualNode) { $oneVirtualNode->linkNode($this->nodeList[0]); $this->nodeList[mt_rand(0, $this->hashCode)]->linkVirtualNode($oneVirtualNode); } }
return true; }
/** * 根据hash key获取值 * @param string $hashKey * @return mixed */ public function get(string $hashKey) { if (empty($this->nodeList)) { return null; } $key = $this->gethashCode($hashKey); return $this->virtualNodeList[$key]->get($hashKey); }
/** * 添加一个值 * @param string $hashKey * @param $value * @return mixed */ public function set(string $hashKey, $value) { if (empty($this->nodeList)) { return false; } $key = $this->gethashCode($hashKey); return $this->virtualNodeList[$key]->set($hashKey, $value); }
/** * key hash取模 * @param string $hashKey * @return int */ private function gethashCode(string $hashKey) { $num = 0; //var_dump($hashKey); for ($step = 0; $step < strlen($hashKey); $step++) { //var_dump($hashKey[$step], (int)$hashKey[$step], ord($hashKey[$step])); $num += $num * 31 + (int)$hashKey[$step]; } return $num % $this->hashCode; }
public function dumpVirtualNode() { for ($step = 0; $step < count($this->virtualNodeList); $step++) { echo $this->virtualNodeList[$step] . "\n"; } }}复制代码
<?php
namespace consistenthashVirtualNode;
require_once __DIR__ . '/NodeInterface.php';
/** * 实体节点 * * 一个实体节点可以关联多个虚拟节点 * * Class Node * @package consistenthashVirtualNode */class Node implements NodeInterface{ public $nodeIp; private $v = []; private $virtualNode = [];
public function __construct(string $nodeIp) { $this->nodeIp = $nodeIp; }
/** * 根据hash key获取值 * @param string $hashKey * @return mixed */ public function get(string $hashKey) { return isset($this->cache[$hashKey]) ? $this->cache[$hashKey] : null; }
/** * 添加一个值 * @param string $hashKey * @param $value * @return mixed */ public function set(string $hashKey, $value) { $this->cache[$hashKey] = $value; return true; }
public function getName() { return $this->nodeIp; }
public function equal(NodeInterface $node) { if ($node->getName() === $this->nodeIp) { return true; } return false; }
/** * 获取当前虚拟节点 * @return |null */ public function getLinkedVirtualNode() { return $this->virtualNode; }
/** * 关联虚拟节点 * @param VirtualNodeInterface $virtualNode */ public function linkVirtualNode(VirtualNodeInterface $virtualNode) { $this->virtualNode[] = $virtualNode; }
public function removeVirtualNode(VirtualNodeInterface $virtualNode) { for ($step = 0; $step < count($this->virtualNode); $step++) { if ($this->virtualNode[$step]->equal($virtualNode)) { array_splice($this->virtualNode, $step, 1); break; } } }
public function __toString() { $virtualNode = ''; foreach ($this->virtualNode as $oneNode) { $virtualNode .= $oneNode->getName() . ", "; } //return 'node : ' . $this->nodeIp . ' count(virtualNode)'. count($this->virtualNode).',linked virtual node: ' . $virtualNode. "\n"; return 'node : ' . $this->nodeIp . ' count(virtualNode)'. count($this->virtualNode). "\n"; }
public function countCacheKey() { return count($this->cache); }}复制代码
<?php
namespace consistenthashVirtualNode;require_once __DIR__ . '/VirtualNodeInterface.php';/** * 虚拟节点 * Class VirtualNode */class VirtualNode implements VirtualNodeInterface{ public $nodeName; private $linkNode;
public function __construct(string $nodeName) { $this->nodeName = $nodeName; }
/** * 根据hash key获取值 * @param string $hashKey * @return mixed */ public function get(string $hashKey) { return $this->linkNode->get($hashKey); }
/** * 添加一个值 * @param string $hashKey * @param $value * @return mixed */ public function set(string $hashKey, $value) { return $this->linkNode->set($hashKey, $value); }
/** * 获取当前关联节点 */ public function getLinkedNode() { return $this->linkNode; }
/** * 添加虚拟节点 * @param Node $oneNode */ public function linkNode(NodeInterface $oneNode) { $this->linkNode = $oneNode; }
public function equal(VirtualNodeInterface $virtualNode): bool { if ($virtualNode->getName() === $this->nodeName) { return true; } else { return false; } }
public function getName() { return $this->nodeName; }
public function __toString() { return 'virtual node : '. $this->nodeName. ',linked node: '. $this->linkNode->getName(); }}
复制代码
这里最核心的代码是 Cache 类的 addNode 和 removeNode 方法。
在添加节点的时候，计算添加后每个实体节点应该关联多少虚拟节点，然后从当前实体节点所关联的虚拟节点均匀的拿出一部分来关联新的实体节点。
目前得到的结果是：
10 个物理节点。
100 个虚拟节点时，标准差为：20410
150 个虚拟节点时，标准差为：3140
200 个虚拟节点时，标准差为：7047
虚拟节点的增多有时候会带来结果的不确定，主要原因还是增加节点和移除节点时的再分配，分配的越均衡，标准差也越小。
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 59
而立
关注
还未添加个人签名 2018.01.25 加入
还未添加个人简介
评论