一致性Hash算法在分布式缓存系统中的应用与历史解析
一致性hash的历史
Consistent Hashing 算法在 1997 年被提出于论文 Consistent hashing and random trees 中。如今，它在 cache 系统中的应用越来越广泛。
一致性hash的目的
一致性哈希算法在分布式系统中较为常用。普通余数 Hash 算法存在伸缩性差的问题，而一致性哈希算法对此进行了有效解决。它能够确保在服务器上线或下线时，尽量让更多的请求命中原本路由到的服务器。
问题背景
在业务开发过程中，我们通常会将数据持久化到数据库里。当需要读取这些数据时，除了直接从数据库中进行读取之外，为了能够减轻数据库的访问压力并且提高访问速度，我们更多地会引入缓存来对数据进行存取操作。
分布式缓存
分布式缓存中，不同机器分别存储不同对象的数据。为达成这些缓存机器的负载均衡，通常会有两种 Hash 算法来进行数据节点存储的均匀分配，其中一种是普通 Hash 算法。
普通的Hash算法的 Hash取模做法的缺陷
在一个 Redis 集群中，若将一条数据进行 Hash 操作，接着依据集群节点数取模来确定该数据应放置在哪个节点。这种方式存在的缺陷为：在进行扩容（即增加一个节点）之后，会有大量的缓存失效。
普通Hash的案例分析
如果你有 N 个 cache 服务器（以下简称 cache ），那么怎样把一个对象 object 映射到 N 个 cache 上呢？你很有可能会运用类似如下的通用方法来计算 object 的 hash 值，接着将其均匀地映射到 N 个 cache 上。
hash(object)%N
一切都运行正常，再考虑如下的两种情况；
一致性Hash算法
一致性 hash 算法是为了解决此类问题的方法。它能够保证，在机器增加或者减少的时候，对缓存访问命中的概率所产生的影响能够减至很小。接下来我们详细说一说一致性 hash 算法的具体过程。
改良版一致性Hash算法 一致性Hash算法 + 虚拟节点
为解决数据分布不均的问题，我们引入了虚拟节点的概念。我们针对每一个服务节点进行多个哈希的计算，将每个计算结果所对应的位置都放置一个此服务节点，此服务节点被称为虚拟节点。当定位到虚拟节点时，其数据就会被存放到该虚拟节点所对应的真实节点上。通过这种方式，数据分布就变得相对均匀了。并且，虚拟节点的数量越多，数据分布就越均匀。
引入“虚拟节点”之后，映射关系由 { 对象 -> 节点 } 转变为了 { 对象 -> 虚拟节点 } 。在查询物体所在 cache 时的映射关系
一般虚拟节点数32个以上，dubbo是160个。
处理机器增减的情况
对于线上的业务，增加或者减少一台机器的部署是常有的事情。
部署机器 c4 并将其加入到 hash 环中机器 c3 与 c2 之间。此时，仅机器 c3 与 c4 之间的对象需重新分配至新机器。就我们的例子而言，仅有对象 o4 被重新分配到了 c4，其余对象仍在原机器上。
一致性Hash算法的实现原理
在业务开发时，我们经常把数据保存在数据库里。要是需要读取这些数据，除了直接从数据库读取之外，为了降低数据库的访问压力并且提升访问速度，我们更多地采用引入缓存的方式来对数据进行存取。读取数据的过程通常是这样的：
Java代码实现Hash算法的实现
使用一个 TreeMap 当作环，其 key 是虚拟节点的下标，value 是真实节点的 hash。我个人觉得可以添加一个 Map 去对真实节点与虚拟节点的关系进行维护。
/**
* 一致性Hash算法
算法的详细解释为：http://blog.csdn.net/sparkliang/article/details/5279393
算法的实现地址为：https://weblogs.java.net/blog/2007/11/27/consistent-hashing
* @author xiaoleilu
*
* @param 节点类型
*/
public class ConsistentHash<T> implements Serializable{
private static final long serialVersionUID = 1L;
/** Hash计算对象，用于自定义hash算法 */
Hash32<Object> hashFunc;
/** 复制的节点个数 */
private final int numberOfReplicas;
/** 一致性Hash环 */
private final SortedMap<Integer, T> circle = new TreeMap<>();
/**
* 构造，使用Java默认的Hash算法
参数 numberOfReplicas 表示复制的节点个数，增加每个节点的复制节点有助于实现负载均衡。
* @param nodes 节点对象
*/
public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
this.hashFunc = key -> {
//默认使用FNV1hash算法
return HashUtil.fnvHash(key.toString());
};
//初始化节点
for (T node : nodes) {
add(node);
}
}
/**
* 构造
* @param hashFunc hash算法对象
* @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡
* @param nodes 节点对象
*/
public ConsistentHash(Hash32<Object> hashFunc, int numberOfReplicas, Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
this.hashFunc = hashFunc;
//初始化节点
for (T node : nodes) {
add(node);
}
}
/**
* 增加节点
* 每增加一个节点，就会在闭环上增加给定复制节点数
如果复制节点数为 2，那么每调用此方法一次，就会增加两个虚拟节点，且这两个节点指向同一个 Node
因为 hash 算法会调用 node 的 toString 方法，所以依据 toString 来进行去重。
* @param node 节点对象
*/
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunc.hash32(node.toString() + i), node);
}
}
/**
* 移除节点的同时移除相应的虚拟节点
* @param node 节点对象
*/
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunc.hash32(node.toString() + i));
}
}
/**
* 获得一个最近的顺时针节点
给定键取 Hash 后，取得顺时针方向上最近的一个虚拟节点，该虚拟节点对应的是实际节点。
* @return 节点对象
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunc.hash32(key);
if (false == circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash); //返回此映射的部分视图，其键大于等于 hash
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
//正好命中
return circle.get(hash);
}
}
phper