在大型 WEB 应用中，缓存可算是当今的一个标准开发配置了，比如常见的 Redis、Memcached。在大规模的缓存应用中，应运而生了分布式缓存系统。分布式缓存系统的基本原理，大家也有所耳闻。将 Key 均匀的分布在缓存集群中。最常规的方式莫过于 Hash 取模的方式。比如集群中可用机器适量为 N，那么 Key 值为 K 的的数据请求很简单的应该路由到 hash(K) mod N 对应的机器。这种方式简单实用。
但是在一些高速发展的 WEB 系统中，这样的解决方案有比较大的缺陷。随着系统访问压力的增长，缓存系统不得不通过增加缓存节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照 hash 取模的方式，在增加机器节点的这一时刻，大量的缓存命不中，缓存数据需要重新建立，甚至是进行整体的缓存数据迁移，瞬间会给 DB 带来极高的系统负载，设置导致 DB 服务器宕机。
一致性哈希
算法简述
一致性哈希算法 (Consistent Hashing Algorithm) 是一种分布式算法，常用于负载均衡。解决将 key-value 均匀分配到众多 cache server 上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删 cache server 的问题。
简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数 H 的值空间为 0 - (2^32)-1（即哈希值是一个 32 位无符号整形）：
然后将各个服务器使用 H 进行一个哈希，具体可以选择服务器的 ip 或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设有三台服务器使用 ip 地址哈希后在环空间的位置如下：
将数据 key 使用相同的函数 H 计算出哈希值 h，通根据 h 确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。例如我们有 A、B、C、D 四个数据对象，经过哈希计算后，数据 A 会被定为到 Server 1 上，D 被定为到 Server 3 上，而 B、C 分别被定为到 Server 2 上。在环空间上的位置如下：
容错性与可扩展性分析
下面分析一致性哈希算法的容错性和可扩展性。现假设 Server 3 宕机了：
可以看到此时 A、C、B 不会受到影响，只有 D 节点被重定位到 Server 2。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
再考虑另外一种情况，如果我们在系统中增加一台服务器 Memcached Server 4：
此时 A、D、C 不受影响，只有 B 需要重定位到新的 Server 4。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
虚拟节点
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台服务器，其环分布如下：
此时必然造成大量数据集中到 Server 1 上，而只有极少量会定位到 Server 2 上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器 ip 或主机名的后面增加编号来实现。例如上面的情况，我们决定为每台服务器计算三个虚拟节点，于是可以分别计算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六个虚拟节点：
总结
一致性最大限度地抑制了 Hash 键的重新分布。另外要取得比较好的负载均衡的效果，往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能均匀的分布在圆环上。因为使用一般的 Hash 方法，服务器的映射地点的分布非常不均匀。使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配 100～200 个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。
閱讀更多 振偉學長 的文章
