1、Memcached分布式缓存集群的访问模型
以Memcached为代表的分布式缓存，访问模型如下图所示：
应用程序通过Memcached客户端访问Memcached服务器集群，Memcached客户端主要由一组API、Memcached服务器集群路由算法、Memcached服务器集群列表及通信模块构成。
其中路由算法负载根据应用程序输入的缓存数据KEY计算得到应该将数据写入到Memcached的哪台服务器或者应该从哪台服务器读取数据。
一个典型的缓存写操作如上图所示。应用程序输入需要写缓存的数据<'BEIJING',DATA>，API将KEY（'BEIJING'）输入路由算法模块，路由算法根据KEY和Memcached集群服务器列表计算得到一台服务编号（NODE1），进而得到该机器的IP地址和端口（10.0.0.0:91000）。API调用通信模块和编号为NODE1的服务器通信，将数据<'BEIJING',DATA>写入该服务器。完成一次分布式缓存的写操作。
读缓存的过程和写缓存一样，由于使用同样的路由算法和服务器列表，只要应用程序提供相同的KEY（'BEIJING'），Memcached客户端总是访问相同的服务器（NODE1）去读取数据。只要服务器还缓存着该数据，就能保证缓存命中。
2、Memcached分布式缓存集群的伸缩性挑战
由上述讨论可得知，在Memcached分布式缓存系统中，对于服务器集群的管理，路由算法至关重要，和负载均衡算法一样，决定着究竟该访问集群中的哪台服务器。
简单的路由算法可以使用余数Hash：用服务器数目初一缓存数据KEY的Hash值，余数为服务器列表下标编号。假设上图中'BEIJING'的Hash值是490806430（JAVA中的HashCode()返回值），用服务器数目3除以该值，得到余数1，对应节点NODE1。由于HashCode具有随机性，因此使用余数Hash路由算法可保证缓存数据在整个Memcached服务器集群中比较均衡的分布。
对余数Hash路由算法稍加改进，就可以实现和负载均衡算法中加权负载均衡一样的加权路由。事实上，如果不需要考虑缓存服务器集群伸缩性，余数Hash几乎可以满足绝大多数的缓存路由需求。
但是，当分布式缓存集群需要扩容的时候，事情就变得棘手了。
假设由于业务发展，网站需要将3台缓存服务器扩容至4台。更改服务器列表，仍旧使用余数Hash，用4除以'BEIJING'的Hash值49080643，余数为2，对应服务器NODE2。由于数据<'BEIJING',DATA>缓存在NODE1，对NODE2的读缓存操作失败，缓存没有命中。
很容易就可以计算出，3台服务器扩容至4台服务器，大约有75%被缓存了的数据不能正确命中，随着服务器集群规模的增大，这个比例线性上升。当100台服务器的集群中加入一台新服务器，不能命中的概率是99%。
这个结果显然是不能接受的，在网站业务中，大部分的业务数据读操作请求事实上是通过缓存获取的，只有少量读操作请求会访问数据库，因此数据库的负载能力是以有缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时，这些数据访问的压力就落到了数据库的身上，这将大大超过数据库的复杂你能力，严重的可能会导致数据库宕机。
一种解决办法是在网站访问量最少的时候扩容缓存服务器集群，这时候对数据库的负载冲击最小。然后通过模拟请求的方法逐渐预热缓存，使缓存服务器中的数据重新分布。但是这种方案对业务场景有要求，还需要技术团队通宵加班（网站访问低谷通常是在半夜）。
能不能通过改进路由算法，使得新加入的服务器不影响大部分缓存数据的正确命中呢？目前比较流行的算法是一致性Hash算法。
3、分布式缓存的一致性Hash算法
具体内容请看：https://www.jianshu.com/p/6ad87a1f070e 里面的一致性Hash算法。
