分布式有利于提高网站的可用性、伸缩性和安全性。分布式缓存，顾名思义，就是将缓存服务器作分布式配置，提高集群性能和可伸缩性。然而对分布式缓存集群而言，不能像应用服务器一样使用简单的负载均衡手段来实现，因为分布式缓存服务器集群中不同服务器中缓存的数据各不相同，缓存访问请求不可以在缓存服务器集群中的任意一台处理，必须先找到缓存有需要数据的服务器，然后才能访问。这个特点会严重制约分布式缓存集群的伸缩性设计，因为新上线的缓存服务器没有缓存任何数据，而已下线的缓存服务器还缓存着网站的许多热点数据。
分布式缓存算法的主要设计目标，就是在保证负载均衡的同时，尽可能让新上线的缓存服务器对整个分布式缓存集群影响最小，也就是说新加入缓存服务器后应使整个缓存服务器集群中已经缓存的数据尽可能还被访问到，同时新增服务器对原有服务器的影响要尽可能均衡。
余数 hash 算法
分布式缓存的算法要保证对于一个确定数据，它所在的服务器也必须是确定的。比如对于键值对 <’BEIJING’,DATA>，每一次查找 ‘BEIJING’ 这个关键词，系统总是访问相同的服务器去读取数据。这样，只要服务器还缓存着该数据，就能保证命中。
余数 hash 是一个不错的办法:用服务器数目除缓存数据 KEY 的 hash 值，余数为服务器列表下标编号。假设我们有三台服务器，要存键值对 <’BEIJING’,DATA> 到缓存。则先计算 ‘BEIJING’的 hash 值是 490806430（Java 中的 HashCode() 返回值），用服务器数目 3 除该值，得到余数 1，将其保存到 NODE1 上，以后想要读取数据 ‘BEIJING’ 的时候，只要服务器数量不变，一定会定位 NODE1 上。同时，由于 HashCode 具有随机性，使用余数 hash 算法可保证缓存数据在整个缓存服务器集群中比较均匀地分布。
对余数 Hash 算法稍加改进，还能满足对不同硬件性能的服务器集群作负载均衡的需求。比如 3 台服务器中，第 2 台服务器的性能是另外 2 台的 2 倍，这时我们可以调整算法，把除数设置为 4，当余数为 1、2 的时候，将数据存入 NODE2，实现加权负载均衡。
事实上，如果不需要考虑缓存服务器集群伸缩性，余数 hash 几乎可以满足绝大多数的缓存路由需求。
余数 hash 算法的不足
然而，当考虑到缓存服务器集群伸缩性的时候，余数 hash 算法的不足就暴露出来了。假设由于业务发展，网站需要将 3 台缓存服务器扩容至 4 台。这时用户再次访问 ‘BEIJING’ 这个数据的时候，除数变成了 4，用 4 除‘BEIJING’的 Hash 值 490806430，余数为 2，对应 NODE2。由于数据 <’BEIJING’,DATA> 缓存在 NODE1，对 NODE2 的读缓存操作失败，缓存没有命中。
很容易就可以计算出，3 台服务器扩容至 4 台的时候，大约只能命中 25%的缓存（3/4），随着服务器集群规模的增大，这个比例线性上升。当 100 台服务器的集群加入一台新服务器，不能命中的概率是 99%（N/(N+1)）。
这个结果显然是无法接受的，因此我们需要改进这种算法，提高增加新机器后的缓存命中率。
一致性 hash 算法
一致性 hash 算法通过一个叫作一致性 hash 环的数据结构提高了新增机器后的缓存命中率，如下图：
具体算法过程为：先构造一个长度为 2^32 的整数环（这个环被称作一致性 hash 环），根据节点名称的 hash 值（其分布范围为[0,2^32-1]）将缓存服务器节点放置在这个 hash 环上。然后根据需要缓存的数据的 KEY 值计算得到其 hash 值（其分布范围也同样为[0,2^32-1]），然后在 hash 环上顺时针查找距离这个 KEY 的 hash 值最近的缓存服务器节点，完成 KEY 到服务器的 hash 映射查找。
在上图中，假设 NODE1 的 hash 值为 3594963423，NODE2 的 hash 值为 1845328979，而 KEY0 的 hash 值为 2534256785，那么 KEY0 在环上顺时针查找，找到的最近的节点就是 NODE1。
当缓存服务器集群需要扩容的时候，只需要将新加入的节点名称（NODE3）的 hash 值放入一致性 hash 环中，由于 KEY 是顺时针查找距离其最近的节点，因此新加入的节点只影响整个环中的一小段，如下图中加粗的一段：
假设 NODE3 的 hash 值是 2790324235，那么加入 NODE3 后，KEY0（hash 值 2534256785）顺时针查找得到的节点就是 NODE3。
如上图所示，加入新节点 NODE3 后，原来的 KEY 大部分还能继续计算到原来的节点，只有 KEY3、KEY0 从原来的 NODE1 重新计算到 NODE3。这样就能保证大部分被缓存的数据还可以继续命中。3 台服务器扩容至 4 台，命中率可以达到 75%，远高于余数 hash 的 25%，而且随着集群规模增大，继续命中原有缓存数据的概率也逐渐增大，100 台服务器扩容增加 1 台，继续命中的概率是 99%。虽然仍有小部分数据缓存在服务器中不能被读到，但这个比例在可接受范围之内。
一致性 hash 算法的不足
虽然上述的算法使缓存服务器集群在增加新服务器后的命中率有了大幅提高，但还存在一个小小的问题。
新加入的节点 NODE3 只影响了原来的节点 NODE1，也就是说一部分原来需要访问 NODE1 的缓存数据现在需要访问 NODE3（概率上是 50%）。但是原来的节点 NODE0 和 NODE2 不受影响，这也就意味着，新引入的 NODE3 这个节点只减轻了 NODE1 的压力，假设原先三个节点的压力是一样大的，那么在引入 NODE3 这个节点后，NODE0 和 NODE2 的缓存数据量和负载压力是 NODE1 与 NODE3 的两倍。这个是有违我们负载均衡的初衷的。
怎么办？
改！
改进后的一致性 hash 算法
我们可以通过增加一层虚拟层的方式解决这个问题：将每台物理缓存服务器虚拟为一组虚拟缓存服务器，将虚拟缓存服务器的 hash 值放置在 hash 环上，KEY 在环上先找到虚拟服务器节点，再得到物理服务器的信息。
这样新加入物理服务器节点时，是将一组虚拟节点加入环中，如果虚拟节点的数目足够多，这组虚拟节点将会影响同样多数目的已经在环上存在的虚拟节点，这些已经存在的虚拟节点又对应不同的物理节点。最终的结果是：新加入一台缓存服务器，将会较为均匀地影响原来集群中已经存在的所有服务器，也就是说分摊原有缓存服务器集群中所有服务器的一小部分负载，其总的影响范围和上面讨论过的相同。如下图所示：
显然每个物理节点对应的虚拟节点越多，各个物理节点之间的负载越均衡，新加入物理服务器对原有的物理服务器的影响越保持一致（这就是一致性 hash 这个名称的由来）。那么在实践中，一台物理服务器虚拟为多少个虚拟服务器节点合适呢？太多会影响性能，太少又会导致负载不均衡，一般说来，经验值是 150，当然根据集群规模和负载均衡的精度需求，这个值应该根据具体情况具体对待。