发现维基百科上只有”一致哈希“这个概念，不知道”一致性哈希”是从哪来的，查看介绍一致性哈希的文章也都说”一致性哈希”是MIT的David Karger及合作者在1997年的学术论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》(论文要付费阅读和下载😓)上提出了的，由此可以推理”一致性哈希”和”一致哈希”是同一个算法。这里按照维基百科的说法称为一致哈希。

一致哈希算法要解决的问题

一致哈希是一种算法，特殊的哈希算法。特殊在什么地方，是为了解决什么问题呢？

考虑这样一个场景，在一个Web系统中，有N台缓存服务器(一般称Cache集群或Cache服务器池)，缓存从后端DB拿到的数据，我们就要思考把一个key存到N台服务器中的那一台呢（其实是一个路由选择的问题）？传统的做法是通过负载均衡的方式，把key经一个普通哈希算法（比如余数哈希算法）计算出服务器的节点，然后进行存取操作。

余数哈希算法核心思想：
服务器节点编号 = hash(key) mod N

1、用Z对N取模(Z % N)得到的数就是服务器节点编号。

上面这种方式的问题在于，当新增或删除一台服务器的时候，原来计算的服务器节点编号大部分会发生变化，也就是说大部分缓存都会失效，导致缓存服务器大量集中的从DB读取数据更新缓存，即缓存被穿透了，俗称”雪崩”。一致哈希算法可以有效解决这个问题。

一致哈希算法及实现

一致哈希算法步骤：
0、将每一个服务器节点按照ip或者server_name, 通过hash函数(eg: crc32)得到对应的一组hash整数值，这里称做hash_servers，并对得到的整数值按由小到大进行排序。
1、将key也通过上面同一个hash函数计算得到对应hash整数值, 这里称为hash_key。

2、遍历hash_servers，用hash_key与hash_servers中的数逐个比较，当hash_key最后小于hash_servers中的那个数存在时，这个数对应的节点就是这个key所存储的节点，否则存在第一个节点。

明白了算法，在参考实现，理解起来就相对容易。一致哈希算法的实现：
PHP的第一种实现: flexihash
PHP的第二种实现：《一致哈希PHP实现及应用(一致哈希学习笔记二)》。

Golang的实现：Github地址。
更多语言实现可见Implementations in various languages

一致哈希环

比较直观的理解方式是通过构建一个虚拟的圆环(Hash环)
0、构造一个长度为2^32的整数环

1、根据服务器节点的hash值将节点放在环上对应位置(下图中N1、N2、N3)。

2、根据key的hash值将key放在环上对应位置(下图中k1、k2)。

3、按顺时针方向，在环上查找离key最近的服务器节点，就是目标节点(下图中k1存在N1中，k2存N2中)。

4、新增服务器节点N4(下图中k2将存到N4中)。

5、删除服务器节点N1(下图中k1将存到N4中)。

6、数据倾斜性问题(服务器N2意外宕机，则存在N2上都全部瞬间转移到N3)

7、引入虚拟节点，解决平衡性(数据倾斜)问题(定位到多台虚拟节点上的key实际指向一台，可以做到相对均匀的分布，实际上做了两次key到节点的映射)。

一致哈希特点

冗余少／负载均衡／过渡平滑／存储均衡／关键词单调
具体含义参考：一致性Hash算法背景

应用实例

CouchBase
Memcached客户端实现分布式缓存

一致哈希算法在PHP Memcached扩展中的应用可以查看PHP Memcached扩展源码。源码分析可以参考：https://github.com/bingbo/blog/wiki/PHP的Memcached扩展源码分析

总结

一致哈希算法我们可能觉得很熟悉，但又不能很清楚的理解。我想的原因主要有两个：一是我们经常有意无意听到这个”一致哈希”这个词，比如我们经常听到Memcached客户端用的是一致哈希算法，我们很熟悉，但是并没有真正去学习、深入理解过；二是，很多介绍一致哈希的文章站在很高的起点，作者没有交代一些细节，导致我们理解很费劲。当然这篇文章也有很多没有说清楚，或者表述有误的地方，欢迎留言指正。一旦我们花点时间搞明白了，发现确实不难理解。

思考

有读者提到机器节点hash冲突的情况，应该顺位到下一个槽点(位置)？你怎么考虑，欢迎留言?

参考资料：
https://zh.wikipedia.org/wiki/一致哈希
https://en.wikipedia.org/wiki/Consistent_hashing
https://blog.csdn.net/jeffleo/article/details/68060506
http://afghl.github.io/2016/07/04/consistent-hashing.html
http://imhuchao.com/687.html