算法：一致性哈希算法HASH原理及实践
前言
互联网公司中，绝大部分都没有马爸爸系列的公司那样财大气粗，他们即没有强劲的服务器、也没有钱去购买昂贵的海量数据库。那他们是怎么应对大数据量高并发的业务场景的呢？ 这个和当前的开源技术、海量数据架构都有着不可分割的关系。比如通过mysql、nginx等开源软件，通过架构和低成本的服务器搭建千万级别的用户访问系统。 怎么样搭建一个好的系统架构，这个话题我们能聊上个七天七夜。这里我主要结合Redis集群来讲一下一致性Hash的相关问题。
一、Redis案例
1.Redis集群的使用
我们在使用Redis的过程中，为了保证Redis的高可用，我们一般会对Redis做主从复制，组成Master-Master或者Master-Slave的形式，进行数据的读写分离，如下图1-1所示：
图1-1：Master-Slave模式
当缓存数据量超过一定的数量时，我们就要对Redis集群做分库分表的操作。
来个栗子，我们有一个电商平台，需要使用Redis存储商品的图片资源，存储的格式为键值对，key值为图片名称，Value为该图片所在的文件服务器的路径，我们需要根据文件名，查找到文件所在的文件服务器上的路径，我们的图片数量大概在3000w左右，按照我们的规则进行分库，规则就是随机分配的，我们以每台服务器存500w的数量，部署12台缓存服务器，并且进行主从复制，架构图如下图1-2所示：
图1-2：Redis分库分表
由于我们定义的规则是随机的，所以我们的数据有可能存储在任何一组Redis中，比如我们需要查询"product.png"的图片，由于规则的随机性，我们需要遍历所有Redis服务器，才能查询得到。这样的结果显然不是我们所需要的。所以我们会想到按某一个字段值进行Hash值、取模。所以我们就看看使用Hash的方式是怎么进行的。
2.使用Hash的Redis集群
如果我们使用Hash的方式，每一张图片在进行分库的时候都可以定位到特定的服务器，示意图如图1-3所示：
图1-3：使用Hash方式的命中缓存
从上图中，我们需要查询的是图product.png，由于我们有6台主服务器，所以计算的公式为：hash(product.png) % 6 = 5, 我们就可以定位到是5号主从，这们就省去了遍历所有服务器的时间，从而大大提升了性能。
3.使用Hash时遇到的问题
Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。容易看到，上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。
在上述hash取模的过程中，我们虽然不需要对所有Redis服务器进行遍历而提升了性能。但是，使用Hash算法缓存时会出现一些问题，Redis服务器变动时，所有缓存的位置都会发生改变。
比如，现在我们的Redis缓存服务器增加到了8台，我们计算的公式从hash(product.png) % 6 = 5变成了hash(product.png) % 8 = ? 结果肯定不是原来的5了。
再者，6台的服务器集群中，当某个主从群出现故障时，无法进行缓存，那我们需要把故障机器移除，所以取模数又会从6变成了5。我们计算的公式也会变化。
由于上面hash算法是使用取模来进行缓存的，为了规避上述情况，Hash一致性算法就诞生了~~
二、一致性Hash算法
0.一致性Hash算法简介
一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系；一致性哈希解决了简单哈希算法在分布式[哈希表]（Distributed Hash Table，DHT）中存在的动态伸缩等问题；
一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。
传统Hash算法存在的问题
假定N为后台服务节点数，当前台携带关键字key发起请求时，我们通常将key进行hash后采用模运算（hash(key)%N）来将请求分发到不同的节点上。 对前台请求于后台无状态服务节点不敏感的场景而言，只要请求key具有一定的随机性，哪怕节点动态增删，该算法于后台而言已可以达到很好的负载均衡效果。 但对于分布式缓存，或者分布式数据库等场景而言，上述方式就不合适了。因后台节点的增删会引起几乎所有key的重新映射。这样，于分布式缓存而言，均发生cache miss；于分布式数据库而言发生数据错乱，其影响是灾难性的。
一致性哈希算法的目标是，当K个请求key发起请求时。后台增减节点，只会引起K/N的key发生重新映射。即一致性哈希算法，在后台节点稳定时，同一key的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将K个key映射到与之前相同的节点上。
哈希算法好坏的四个定义
- 1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
- 2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
- 3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
- 4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则（数据库的分库分表也有类似问题）。
1.一致性Hash算法原理
一致性Hash算法简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。
一致性Hash算法也是使用取模的方法，不过，上述的取模方法是对服务器的数量进行取模，而一致性的Hash算法是对2的32方取模。即，一致性Hash算法将整个Hash空间组织成一个虚拟的圆环，Hash函数的值空间为0 ~ 2^32 - 1(一个32位无符号整型)，整个哈希环如下：
图1-4：Hash圆环
整个圆环以顺时针方向组织，圆环正上方的点代表0，0点右侧的第一个点代表1，以此类推。
第二步，我们将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台服务器就确定在了哈希环的一个位置上，比如我们有三台机器，使用IP地址哈希后在环空间的位置如图1-4所示：
图1-4：服务器在哈希环上的位置
现在，我们使用以下算法定位数据访问到相应的服务器：
将数据Key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针查找，遇到的服务器就是其应该定位到的服务器。
例如，现在有ObjectA，ObjectB，ObjectC三个数据对象，经过哈希计算后，在环空间上的位置如下：
图1-5：数据对象在环上的位置
根据一致性算法，Object -> NodeA，ObjectB -> NodeB, ObjectC -> NodeC
2.一致性Hash算法的容错性和可扩展性
服务器扩缩容场景
现在，假设我们的Node C宕机了，我们从图中可以看到，A、B不会受到影响，只有Object C对象被重新定位到Node A。所以我们发现，在一致性Hash算法中，如果一台服务器不可用，受影响的数据仅仅是此服务器到其环空间前一台服务器之间的数据（这里为Node C到Node B之间的数据），其他不会受到影响。如图1-6所示：
图1-6：C节点宕机情况，数据移到节点A上
服务器增加
另外一种情况，现在我们系统增加了一台服务器Node X，如图1-7所示：
图1-7：增加新的服务器节点X
此时对象ObjectA、ObjectB没有受到影响，只有Object C重新定位到了新的节点X上。 如上所述：
一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，有很好的容错性和可扩展性。
3.一致性Hash算法的数据倾斜和虚拟节点
考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，
在一致性Hash算法服务节点太少的情况下，容易因为节点分布不均匀面造成数据倾斜（被缓存的对象大部分缓存在某一台服务器上）问题，如图1-8特例：
图1-8：数据倾斜
缓存雪崩如果每个节点在环上只有一个节点，那么可以想象，当某一集群从环中消失时，它原本所负责的任务将全部交由顺时针方向的下一个集群处理。例如，当group0退出时，它原本所负责的缓存将全部交给group1处理。这就意味着group1的访问压力会瞬间增大。设想一下，如果group1因为压力过大而崩溃，那么更大的压力又会向group2压过去，最终服务压力就像滚雪球一样越滚越大，最终导致雪崩。
这时我们发现有大量数据集中在节点A上，而节点B只有少量数据。为了解决数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务器节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。
“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。
“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为 202.168.14.241 。
引入“虚拟节点”前，计算 cache A 的 hash 值： Hash(“202.168.14.241”);
引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2
具体操作可以为服务器IP或主机名后加入编号来实现，实现如图1-9所示：
图1-9：增加虚拟节点情况
数据定位算法不变，只需要增加一步：虚拟节点到实际点的映射。所以加入虚拟节点之后，即使在服务节点很少的情况下，也能做到数据的均匀分布。
4.一致性Hash性质
分布式系统每个节点都有可能失效，并且很可能会有新的节点增加进来，那么如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是分布式系统需要考虑的一个重点问题。在分布式系统的设计时，我们就必须要考虑动态性扩展的问题，这样才不至于某一台服务宕机会影响整个系统。如果不采用合适的算法来保证一致性，那么系统中的所有数据都可能会失效，因此一致性hash算法就显得尤为重要。一般情况下一致性Hash要满足以下几个性质。这里可以参考https://brpc.apache.org/docs/rpc-in-depth/consistent-hashing/
- 平衡性 (Balance) : 每个节点被选到的概率是O(1/n)。
- 单调性 (Monotonicity) : 当新节点加入时， 不会有请求在老节点间移动， 只会从老节点移动到新节点。当有节点被删除时，也不会影响落在别的节点上的请求。
- 分散性 (Spread) : 当上游的机器看到不同的下游列表时(在上线时及不稳定的网络中比较常见), 同一个请求尽量映射到少量的节点中。
- 负载 (Load) : 当上游的机器看到不同的下游列表的时候， 保证每台下游分到的请求数量尽量一致。
三、代码实现
1.算法接口类
public interface IHashService {
Long hash(String key);
}2.算法接口实现类
public class HashService implements IHashService {
/**
* MurMurHash算法,性能高,碰撞率低
*
* @param key String
* @return Long
*/
public Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}3.模拟机器节点
public class Node<T> {
private String ip;
private String name;
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
/**
* 使用IP当做hash的Key
*
* @return String
*/
@Override
public String toString() {
return ip;
}
}4.一致性Hash操作
public class ConsistentHash<T> {
// Hash函数接口
private final IHashService iHashService;
// 每个机器节点关联的虚拟节点数量
private final int numberOfReplicas;
// 环形虚拟节点
private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
public ConsistentHash(IHashService iHashService, int numberOfReplicas, Collection<T> nodes) {
this.iHashService = iHashService;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
/**
* 增加真实机器节点
*
* @param node T
*/
public void add(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.put(this.iHashService.hash(node.toString() + i), node);
}
}
/**
* 删除真实机器节点
*
* @param node T
*/
public void remove(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.iHashService.hash(node.toString() + i));
}
}
public T get(String key) {
if (circle.isEmpty()) return null;
long hash = iHashService.hash(key);
// 沿环的顺时针找到一个虚拟节点
if (!circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}5.测试类
public class TestHashCircle {
// 机器节点IP前缀
private static final String IP_PREFIX = "192.168.0.";
public static void main(String[] args) {
// 每台真实机器节点上保存的记录条数
Map<String, Integer> map = new HashMap<String, Integer>();
// 真实机器节点, 模拟10台
List<Node<String>> nodes = new ArrayList<Node<String>>();
for (int i = 1; i <= 10; i++) {
map.put(IP_PREFIX + i, 0); // 初始化记录
Node<String> node = new Node<String>(IP_PREFIX + i, "node" + i);
nodes.add(node);
}
IHashService iHashService = new HashService();
// 每台真实机器引入100个虚拟节点
ConsistentHash<Node<String>> consistentHash = new ConsistentHash<Node<String>>(iHashService, 500, nodes);
// 将5000条记录尽可能均匀的存储到10台机器节点上
for (int i = 0; i < 5000; i++) {
// 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
String data = UUID.randomUUID().toString() + i;
// 通过记录找到真实机器节点
Node<String> node = consistentHash.get(data);
// 再这里可以能过其它工具将记录存储真实机器节点上，比如MemoryCache等
// ...
// 每台真实机器节点上保存的记录条数加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
// 打印每台真实机器节点保存的记录条数
for (int i = 1; i <= 10; i++) {
System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get(IP_PREFIX + i));
}
}
}运行结果如下：
每台机器映射的虚拟节点越多，则分布的越均匀~~~ 感兴趣的同学可以拷贝上面的代码运行尝试一下。
四、优雅缩扩容
缓存服务器对于性能有着较高的要求，因此我们希望在扩容时新的集群能够较快的填充好数据并工作。但是从一个集群启动，到真正加入并可以提供服务之间还存在着不小的时间延迟，要实现更优雅的扩容，我们可以从两个方面出发：
1.高频Key预热
负载均衡器作为路由层，是可以收集并统计每个缓存Key的访问频率的，如果能够维护一份高频访问Key的列表，新的集群在启动时根据这个列表提前拉取对应Key的缓存值进行预热，便可以大大减少因为新增集群而导致的Key失效。
具体的设计可以通过缓存来实现，如下：
不过这个方案在实际使用时有一个很大的限制，那就是高频Key本身的缓存失效时间可能很短，预热时储存的Value在实际被访问到时可能已经被更新或者失效，处理不当会导致出现脏数据，因此实现难度还是有一些大的。
2.历史Hash环保留
回顾一致性Hash的扩容，不难发现新增节点后，它所对应的Key在原来的节点还会保留一段时间。因此在扩容的延迟时间段，如果对应的Key缓存在新节点上还没有被加载，可以去原有的节点上尝试读取。
举例，假设我们原有3个集群，现在要扩展到6个集群，这就意味着原有50%的Key都会失效（被转移到新节点上），如果我们维护扩容前和扩容后的两个Hash环，在扩容后的Hash环上找不到Key的储存时，先转向扩容前的Hash环寻找一波，如果能够找到就返回对应的值并将该缓存写入新的节点上，找不到时再透过缓存，如下图：
这样做的缺点是增加了缓存读取的时间，但相比于直接击穿缓存而言还是要好很多的。优点则是可以随意扩容多台机器，而不会产生大面积的缓存失效。
谈完了扩容，再谈谈缩容。
3.熔断机制
缩容后，剩余各个节点上的访问压力都会有所增加，此时如果某个节点因为压力过大而宕机，就可能会引发连锁反应。因此作为兜底方案，应当给每个集群设立对应熔断机制来保护服务的稳定性。
4.多集群LB的更新延迟
这个问题在缩容时比较严重，如果你使用一个集群来作为负载均衡，并使用一个配置服务器比如ConfigServer来推送集群状态以构建Hash环，那么在某个集群退出时这个状态并不一定会被立刻同步到所有的LB上，这就可能会导致一个暂时的调度不一致，如下图：
如果某台LB错误地将请求打到了已经退出的集群上，就会导致缓存击穿。解决这个问题主要有以下几种思路：
- 缓慢缩容，等到Hash环完全同步后再操作。可以通过监听退出集群的访问QPS来实现这一点，等到该集群几乎没有QPS时再将其撤下。
- 手动删除，如果Hash环上对应的节点找不到了，就手动将其从Hash环上删除，然后重新进行调度，这个方式有一定的风险，对于网络抖动等异常情况兼容的不是很好。
- 主动拉取和重试，当Hash环上节点失效时，主动从ZK上重新拉取集群状态来构建新Hash环，在一定次数内可以进行多次重试。
五、对比：HashSlot+P2P
了解了一致性Hash算法的特点后，我们也不难发现一些不尽人意的地方：
- 整个分布式缓存需要一个路由服务来做负载均衡，存在单点问题（如果路由服务挂了，整个缓存也就凉了）
- Hash环上的节点非常多或者更新频繁时，查找性能会比较低下
- 针对这些问题，Redis在实现自己的分布式集群方案时，设计了全新的思路：基于P2P结构的HashSlot算法，下面简单介绍一下：
1.使用HashSlot
类似于Hash环，Redis Cluster采用HashSlot来实现Key值的均匀分布和实例的增删管理。
首先默认分配了16384个Slot（这个大小正好可以使用2kb的空间保存），每个Slot相当于一致性Hash环上的一个节点。接入集群的所有实例将均匀地占有这些Slot，而最终当我们Set一个Key时，使用CRC16(Key) % 16384来计算出这个Key属于哪个Slot，并最终映射到对应的实例上去。
那么当增删实例时，Slot和实例间的对应要如何进行对应的改动呢？
举个例子，原本有3个节点A,B,C，那么一开始创建集群时Slot的覆盖情况是：
节点A 0－5460
节点B 5461－10922
节点C 10923－16383现在假设要增加一个节点D，RedisCluster的做法是将之前每台机器上的一部分Slot移动到D上（注意这个过程也意味着要对节点D写入的KV储存），成功接入后Slot的覆盖情况将变为如下情况：
节点A 1365-5460
节点B 6827-10922
节点C 12288-16383
节点D 0-1364,5461-6826,10923-12287同理删除一个节点，就是将其原来占有的Slot以及对应的KV储存均匀地归还给其他节点。
2.P2P节点寻找
现在我们考虑如何实现去中心化的访问，也就是说无论访问集群中的哪个节点，你都能够拿到想要的数据。其实这有点类似于路由器的路由表，具体说来就是：
- 每个节点都保存有完整的HashSlot - 节点映射表，也就是说，每个节点都知道自己拥有哪些Slot，以及某个确定的Slot究竟对应着哪个节点。
- 无论向哪个节点发出寻找Key的请求，该节点都会通过CRC(Key) % 16384计算该Key究竟存在于哪个Slot，并将请求转发至该Slot所在的节点。
总结一下就是两个要点：映射表和内部转发，这是通过著名的Gossip协议来实现的。
最后我们可以给出Redis Cluster的系统结构图，和一致性Hash环还是有着很明显的区别的：
对比一下，HashSlot + P2P的方案解决了去中心化的问题，同时也提供了更好的动态扩展性。但相比于一致性Hash而言，其结构更加复杂，实现上也更加困难。
而在之前的分析中我们也能看出，一致性Hash方案整体上还是有着不错的表现的，因此在实际的系统应用中，可以根据开发成本和性能要求合理地选择最适合的方案。总之，两者都非常优秀，至于用哪个、怎么用，就是仁者见仁智者见智的问题了。