一致性哈希算法的应用及其优化
一．简单哈希算法
哈希（Hash）就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，使得散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
哈希算法是一种消息摘要算法，虽然哈希算法不是一种加密算法，但由于其单向运算，具有一定的不可逆性使其成为加密算法中的一个重要构成部分。
二．分布式缓存问题
哈希算法除了在数据加密中的运用外，也可以用在常见的数据分布式技术中。
哈希计算是通过求模运算来计算哈希值的，然后根据哈希值将数据映射到存储空间中。
设有由N 个存储节点组成的存储空间，采用简单哈希计算将一个数据对象object 映射到存储空间上的公式为：Hash（object）% N。
现在假设有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式已经不能满足用户的访问，于是想引入Memcached作为缓存机制。
现在一共有三台机器可以作为Memcached服务器，如下图1所示。
图1.三台memcached服务器
可以用简单哈希计算：h = Hash(key) % 3 ，其中Hash是一个从字符串到正整数的哈希映射函数，这样能够保证对相同key的访问会被发送到相同的服务器。
现在如果我们将Memcached Server分别编号为0、1、2，那么就可以根据上式和key计算出服务器编号h，然后去访问。
但是，由于这样做只是采用了简单的求模运算，使得简单哈希计算存在很多不足：
1）增删节点时，更新效率低。
当系统中存储节点数量发生增加或减少时，映射公式将发生变化为Hash(object)%(N±1)，这将使得所有object 的映射位置发生变化，整个系统数据对象的映射位置都需要重新进行计算，系统无法对外界访问进行正常响应，将导致系统处于崩溃状态。
2）平衡性差，未考虑节点性能差异。
由于硬件性能的提升，新添加的节点具有更好的承载能力，如何对算法进行改进，使节点性能可以得到较好利用，也是亟待解决的一个问题。
3）单调性不足。
衡量数据分布技术的一项重要指标是单调性，单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中，当又有新的缓冲加入到系统中时，哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
由上述分析可知，简单地采用模运算来计算object 的Hash值的算法显得过于简单，存在节点冲突，且难以满足单调性要求。
三．一致性哈希算法
一致性哈希算法（Consistent Hashing）最早在David Karger，Eric Lehman等人的论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出，是当前较主流的分布式哈希表协议之一，它对简单哈希算法进行了修正，解决了热点（Hot Pot）问题。
一致性哈希的原理：首先，对存储节点的哈希值进行计算，其将存储空间抽象为一个环，将存储节点配置到环上。
环上所有的节点都有一个值。
其次，对数据进行哈希计算，按顺时针方向将其映射到离其最近的节点上去。
现在根据一致性哈希算法原理，重新解决上面分布式缓存问题。
1.一致性哈希将整个哈希值空间组织成一个虚拟的圆环，现在假设某哈希函数H的值空间为0 – 232-1（即哈希值是一个32位无符号整形），那么整个哈希空间环如下图2：
图2.哈希空间环
2.将各个服务器使用哈希函数进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三台服务器使用ip地址哈希后在环空间的位置如下图3所示。
图3.将memchaed server 分布在哈希环上
3.把数据对象映射到哈希空间，对应访问到相应的服务器：对数据对象进行哈希值计算，将数据对应带到环上。
这里考虑四个数据对象 object1、 object2、 object3、 object4 ，通过 Hash 函数计算出Hash 值的Key ：Hash(object1) = Key1；
Hash(object2) = Key2； Hash(object3) = Key3； Hash(object4) =Key4；
将其对应在哈希空间环上，其分布如图4所示。
对象对应的服务器
Memchahed server2
Memchahed server3Memchahed server2Memchahed server3
根据一致性哈希算法，object1会被定为到Server2上，object2被定为到Server 3上，而object3和object4分别被定为到Server 1上。
一致性哈希算法与简单哈希算法相比有了明显的改善：
1.容错性得到了提升。
例如，假设server2宕机了，那么此时object2 ，object3， object4，不会受到影响，只有object1被重定位到Server 3。
即在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即顺着逆时针方向
宕的情况
2的时候受影响的也只是局部范围。
如下图
Memchahed server3Memchahed server2Memchahed server3Key3
Memchahed server4
图6.增加一个server的情况
四．一致性哈希算法的优化
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。
如果只有两个server，如下图7所示。
时必然造成大量数据集中到Server 2
Memchahed server2
图7.两个服务器的情况
为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。
具体做法可以在服务器ip或主机名的后面增加编号来实现。
例如图7的情况，可以为每台服务器计算三个虚拟节点，分别计算“Memcached Server 1-1”、“Memcached Server 1-2”、“Memcached Server 1-3”、“Memcached Server 2-1”、“Memcached Server 2-2”、“Memcached Server 2-3”的哈希值，于是形成六个虚拟节点，其环分布如下图8所示：
图8.增加虚拟节点的情况
此时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Memcached Server 1-1”、“Memcached Server 1-2”、“Memcached Server 1-3”三个虚拟节点的数据均定位到Server 1上。
这样就解决了服务节点少时数据倾斜的问题。
Memchahed server1-3
Memchahed server2-1
Memchahed server1-1
Memchahed server1-2Memchahed server2-2Memchahed server2-3。