没有一致的哈希算法。我劝你不要在简历里写，搞过负载均衡。有小伙伴在讨论一致性哈希算法的问题，担心写不出来，下面简单介绍一下它的原理。下面以分布式缓存中的经典场景为例，采访中经常提到的一些话题，看看什么是一致性哈希算法及其优势。搭建一个场景如果我们有三台缓存服务器，编号分别为node0、node1、node2，现在有3000万个key，我们希望这些key可以平均缓存在三台机器上，你会想到什么方案呢？我们可能首先想到的方案是取模算法hash(key)%N，对key进行hash运算，然后取模，N为机器数。key哈希后的结果取模3，结果必须是0、1或2，分别对应服务器node0、node1、node2。可以直接找到对应的服务器访问数据。简单粗暴，完全可以解决上面的问题question。hash问题的取模算法虽然简单易用，但是机器数量的取模在集群扩容和缩容时有一定的局限性，因为在生产环境中，常见的是根据机器数量的大小来调整服务器数量业务量；服务器数量N发生变化后，hash(key)%N的计算结果也会随之变化。比如某个服务器节点宕机，计算公式由hash(key)%3变为hash(key)%2，结果也会发生变化。这时候如果要访问一个key，这个key的缓存位置很可能会发生变化，那么之前缓存的key数据也会失去作用和意义。大量缓存同时失效，造成缓存雪崩，进而导致整个缓存系统不可用。这基本上是不能接受的。为了解决和优化上述情况，一致性哈希算法应运而生。那么，一致性哈希算法又是如何解决上述问题的呢？Consistencyhash一致性哈希算法本质上也是一种取模算法，但是不同于上面根据服务器数量取模，一致性哈希是一个固定值2^32的取模。IPv4地址由4组8位二进制数组成，所以使用2^32可以保证每个IP地址都会有一个唯一的映射哈希环。我们可以把这2^32个值抽象成一个环??（不开心的Round，自己想个形状，好理解），环正上方的点代表0，顺时针排列，依此类推，1,2,3,4,5,6...直到2^32-1，而这个由2到32次幂组成的环统称为哈希环。那么这个哈希环和一致性哈希算法有什么关系呢？我们以上面的场景为例，三台缓存服务器，编号为node0，node1，node2，3000万个key。服务器映射到hash环时，计算公式由hash(key)%N变为hash(serverip)%2^32，使用服务器IP地址进行hash计算，使用hash后的结果取模的2^32，结果必须是0到2^32-1之间的整数，这个整数映射在哈希环上的位置代表一个服务器，三个缓存服务器node0、node1、node2映射到哈希环依次。对象key映射到哈希环，然后需要缓存的key对象也映射到hash环，hash(key)%2^32，服务器节点和要缓存的key对象映射到哈希环和对象键应该缓存到哪个服务器？对象键映射到服务器。从缓存对象键的位置开始，顺时针第一个遇到的服务器就是当前对象将被缓存的服务器。因为缓存对象的值和服务器的hash是固定的，所以在服务器不变的情况下，对象key必须缓存在固定的服务器上。根据以上规则，下图中的映射关系：key-1->node-1key-3->node-2key-4->node-2key-5->node-2key-2->node-0如果你想访问某个key，只要用同样的计算方法就可以知道这个key缓存在哪个服务器上。consistenthash的优点我们简单了解了consistenthash的原理，那么它是如何优化集群中节点的增减、普通取模算法带来的缓存服务、大规模不可用的问题呢？我们先来看看扩展场景。如果业务量激增，系统需要扩容，增加一台服务器node-4。正好node-4映射在node-1和node-2之间，对象按顺时针方向映射到节点。发现原来缓存在node-2上的对象key-4和key-5被重新映射到node-4上，整个扩容过程中只有node-4和node-1之间的一小部分数据受到影响。反之，如果node-1节点宕机，则对象映射节点为顺时针方向，将node-1上缓存的对象key-1重新映射到node-4。此时受影响的数据只是node-0和node-1之间数据的一小部分。从以上两种情况发现，当集群中的服务器数量发生变化时，一致性哈希计算只会影响一小部分数据，保证缓存系统作为一个整体仍然可以对外提供服务。数据倾斜问题为了便于理解原理，图中的节点在理想情况下是相对均匀分布的，但理想场景和实际场景往往有很大差异。比如我有健身年卡，只去过健身房。两次，这只是淋浴。当服务器节点数量过少时，很容易因为节点分布不均造成数据倾斜。如下图所示，大部分缓存对象缓存在node-4服务器上，导致其他节点资源浪费，大部分系统压力集中。在node-4节点上，这样的集群是很不健康的。数据倾斜的解决方案也很简单。我们需要想办法让节点在映射到哈希环上的时候分布相对均匀。一致性哈希算法引入了虚拟节点机制，即为每个服务器节点计算多个哈希值，并将它们映射到哈希环中，映射到这些虚拟节点的对象键最终缓存在真实节点。虚拟节点的哈希计算通常可以通过将对应节点的IP地址加上数字后缀哈希（10.24.23.227#1）来完成。例如node-1的节点IP为10.24.23.227，正常计算node-1的hash值。hash(10.24.23.227#1)%2^32假设我们设置三个虚拟节点分别为node-1，node-1#1，node-1#2，node-1#3，散列后取模。hash(10.24.23.227#1)%2^32hash(10.24.23.227#2)%2^32hash(10.24.23.227#3)%2^32下图添加虚拟节点后，原来的节点分布在hashring比较统一，分担了剩余节点的压力。但需要注意的是，分配的虚拟节点越多，哈希环上的映射就越均匀。如果节点太少，则很难看到效果。虚拟节点的引入也增加了新的问题。做虚拟节点与真实节点的映射，objectkey->virtualnode->realnode之间的转换。ConsistentHash的应用场景ConsistentHash应该是分布式系统中负载均衡的首选算法。它的实现比较灵活，可以在客户端实现，也可以在中间件上实现。例如缓存中间件memcached和redis集群使用的。memcached集群比较特殊。严格来说，它只能算是一个伪集群，因为它的服务器不能互相通信。请求的分发路由完全取决于客户端计算缓存对象应该落在哪个服务器上，其路由算法使用一致性哈希。Redis集群中也有哈希槽的概念。虽然实现方式不同，但思路是一样的。看完本文的consistencyhash，你对redisslots的理解就会容易很多。还有很多其他的应用场景：RPC框架Dubbo用于选择服务提供者分布式关系数据库分库分表：数据与节点的映射关系LVS负载均衡调度器……………….总结并简要说明一致性哈希。如果有不对的地方可以留言指正。没有技术是完美的。一致性Hash算法也存在一些潜在的隐患。如果Hash环的节点数非常多或者更新频繁，那么检索性能会比较低，整个分布式缓存需要一个路由服务来做负载均衡。一旦路由服务宕机，整个缓存将不可用，还要考虑高可用。不过话说回来，只要能解决问题就是好技术，有些副作用还是可以忍受的。
