分布式缓存中三种负载均衡的方法
2016-06-25 19:46:20 
阿炯
本文主要比较三种分布缓存负载均衡的方法，它们存在于高可用的缓存集群的开源解决方案中。第一种是最简单的将 key的hash值对机器数取模算法，第二种是一致性哈希算法，第三种是淘宝开源的缓存解决方案tair的均衡算法。下面来分析下这三种算法的优缺点。
第一种：传统的数据分布方法,将key的hash值对机器数取模
这个算法的实现非常简单，计算hash(key)/n，n为机器数，得到的值就是该key需要路由到的服务器编号了。
优点：实现简单
缺点：在服务器数量发生变化的时候，缓存会大量失效。
使用哈希算法有什么问题
哈希算法因为对同一个关键字进行哈希计算，每次计算都是相同的值，这样就可以将某个 key 确定到一个节点了，可以满足分布式系统的负载均衡需求。哈希算法最简单的做法就是进行取模运算，比如分布式系统中有 3 个节点，基于 hash(key) % 3 公式对数据进行了映射。
如果客户端要获取指定 key 的数据，通过下面的公式可以定位节点：
hash(key)%3
如果经过上面这个公式计算后得到的值是 0，就说明该 key 需要去第一个节点获取。
但是有一个很致命的问题，如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。举个例子，假设我们有一个由 A、B、C 三个节点组成分布式 KV 缓存系统，基于计算公式 hash(key) % 3 将数据进行了映射，每个节点存储了不同的数据：
现在有 3 个查询 key 的请求，分别查询 key-01，key-02，key-03 的数据，这三个 key 分别经过 hash() 函数计算后的值为 hash( key-01) = 6、hash( key-02) = 7、hash(key-03) = 8，然后再对这些值进行取模运算。通过这样的哈希算法，每个 key 都可以定位到对应的节点。
当 3 个节点不能满足业务需求了，这时我们增加了一个节点，节点的数量从 3 变化为 4，意味取模哈希函数中基数的变化，这样会导致大部分映射关系改变，如下图：
比如，之前的 hash(key-01) % 3 = 0，就变成了 hash(key-01) % 4 = 2，查询 key-01 数据时，寻址到了节点 C，而 key-01 的数据是存储在节点 A 上的，不是在节点 C，所以会查询不到数据。同理，如果我们对分布式系统进行缩容，比如移除一个节点，也会因为取模哈希函数中基数的变化，可能出现查询不到数据的问题。要解决这个问题的办法，就需要我们进行迁移数据，比如节点的数量从 3 变化为 4 时，要基于新的计算公式 hash(key) % 4 ，重新对数据和节点做映射。
假设总数据条数为 M，哈希算法在面对节点数量变化时，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是 O(M)，这样数据的迁移成本太高了。所以应该要重新想一个新的算法，来避免分布式系统在扩容或者缩容时，发生过多的数据迁移。
第二种：一致性hash
试想下如果使用传统取模算法。如果有一个key要存到缓存中，根据hash(key)/n (n表示有n台缓存服务器)，可以计算出缓存所在的服务器id。这个时候有一台服务器挂掉了，剩下n-1台服务器。这时候，同样一个key，根据hash(key)/(n-1) ，这个时候就命中不了缓存了，基本所有的缓存都会失效，这个情况在线上可能是灾难性的。 一致性hash可以解决部分问题。
通常可以考虑[0,(2^32-1)]为hash值的取值范围。我们可以把取值范围想象成一个闭环，2^32-1 和 0 相连接。如下图所示。
这个时候假设我们有4个缓存服务器节点。（node1~node4） 首先计算这四个值的hash值，并且这四个点占据了闭环的四个位置，如上图所示，这个时候需要根据key来路由缓存服务器，首先计算hash(key)值（这个hash算法需要保证hash(key)的值落在在区间[0,2^32-1]中）。然后我们可以想象这个hash（key）值位于闭环的其中一个点，然后用这个hash(key)依次加一，直到命中其中一个node为止，命中的node就是key需要路由的服务器，如上图，需要找到key2的缓存值所在的服务器，首先计算hash(key2)，落在如图的闭环中，然后顺时针找到离这个hash值最近的node，可以看到是node1。key2对应的缓存值就存在node1中。
如果这个时候如果增加了节点node5如下图：
看下缓存失效的情况，如上图，只有hash(key)落在node4~node5之间的key才会有影响，在未增加node5之前落在这个范围的key最终路由到node1,增加node5之后路由到node5了，缓存失效了。除此之外，落在其他范围的hash值就不受影响。如上图，增加node5之后key6原来会路由到node1的，现在路由到node5。而key1不受影响，还是路由到node1。
同理，如果少掉一个节点，还是上图为例，假如这个时候node5失效了，node5失效之前落在node4~node5之间的hash值，会路由到node5，失效之后会路由到node1,也就是原本落在node4~node5之间的hash值失效了。由此可见一致性hash能在节点变动的时候减少缓存失效的比例。
还有一种情况，当cache的数量很少的或者缓存服务器很少的时候，会导致缓存分布不均衡。如下图所示：
当只有很少节点的时候，例如上图的两个，这个时候就会分配得很不均衡。上图中node1明显承受了较多的压力。这个时候引入一个叫虚拟节点的概念，原理就是增加更多的虚拟节点，让每个节点承受的压力尽量均衡。这些增加的节点并不是真正新增的服务器节点，而是由原来的节点”复制“出来的。例如下图，”复制“了两个新节点，node3,node4。实际上，落到node3,node4的key最终访问的服务器是node2,node1。
这样就可以把压力尽量分配到各个机器上。另外需要维护一张表格，用来记录虚拟节点指向的真正节点。
优点：相比简单的对机器数取模算法，当节点变动的时候只有相对较少的key失效，实现也相对简单。不需要进行数据迁移，每个服务器是独立的。
缺点：还是会有部分的key失效，如果访问量非常大的时候，如果访问到失效的key的时候，就会直接访问到数据源上面去了，可能会导致数据源承受重压。
第三种：tair负载均衡算法,构造一张对照表
首先看下如何构建一张对照表。
tair中数据的存储是以bucket为单位的，一个bucket对应一个dateServer,一个dateServer中会有多个bucket。bucket的数目是固定的，这里假设bucket的数量为1024个，并且每个bucket有属于自己的id，依次从0到1023。如下图：
可以看到对key进行hash之后首先会路由到某个bucket然后根据对应关系，再路由到对应的dataServer。
在tair中，你可以设置同一个bucket的备份数目，我们称其中一个bucket为master,其他的备份称为slave。configServer启动的时候会构造三张bucket和dataServer的对照表，分别是hash_table,m_hash_table,d_hash_table，这三张对照表在初始构建的时候都是一样的，但是在dataServer发生增加的时候会暂时不一样，但是最终会趋向一致，三张表分别有什么用处下面会讲到。configServer在构建对照表的时候有两种模式，一种是均衡模式，这种模式会尽量保证每个节点的bucket数目差不多。一种是安全模式，这种模式会尽量保证一份数据以及它的备份分配在不同的区域的服务器上。client通过configServer获取对照表(hash_table)之后，根据（hash(key)%bucket的总数）算出bucket的id并且参照对照表,就能知道这个key对应的dataServer了。对照表的结构大概如下（这里为了简化，一共只有5个bucket，4个dataServer(ds1,ds2,ds3,ds4),这个是初始时的对照表，hash_table, m_hash_table, d_hash_table的内容都是一样的）。
当服务器变化之后configserver是如何重构对照表的？重构对照表的时候，数据是怎么迁移的？
configServer会定时发送心跳包给dataServer，用来检测dataServer是否还存活，如果没有存活的话就会重新构造对照表。或者如果有新加dataServer的话也会重新构造对照表。
当有一个dataServer当机之后，这个机器 上的存储的bucket数据都会丢失，如果是master bucket丢失之后其中一个slave bucket会补上成为master bucket。至于选择哪个slave bucket成为master bucket的是根据slave 上负载的master bucket有没有超标，并且总bucket数有没有超标等标准。举个例子，上图中当ds2失效之后，hash_table, m_hash_table, d_hash_table三个表分别是这样子的。
hash_table ：
m_hash_table：
d_hash_table：
hash_table发送给client，client不至于不能工作，m_hash_table和d_hash_table发送到dataServer，dataServer根据这两张表就可以知道自己是否需要迁移数据和迁移到哪里了。例如这里第一列，第三排，对比两表，可以知道，ds1需要把数据迁移到ds4。
如果是要增加新的dataServer，原理就差不多了，configServer新建对照表，然后把对照表发送到dateServer，然后dataServer再根据新对照表来做数据迁移，完成之后，client就可以使用新的对照表了。
优点：当需要增加机器的时候，不会有key失效。
缺点：实现比较复杂，需要进行数据的迁移。
本文源自：分布式缓存中三种负载均衡的方法
使用一致性哈希算法有什么问题
一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。它也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。
可以把一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，就像钟表一样，钟表的圆可以理解成由 60 个点组成的圆，而此处我们把这个圆想象成由 2^32 个点组成的圆，这个圆环被称为哈希环，如下图：
一致性哈希要进行两步哈希：
1：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
2：当对数据进行存储或访问时，对数据进行哈希映射；
所以一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。问题来了，对「数据」进行哈希映射得到一个结果要怎么找到存储该数据的节点呢？
答案是，映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。
举个例子，有 3 个节点经过哈希计算，映射到了如下图的位置：
接着对要查询的 key-01 进行哈希计算，确定此 key-01 映射在哈希环的位置，然后从这个位置往顺时针的方向找到第一个节点，就是存储该 key-01 数据的节点。比如下图中的 key-01 映射的位置，往顺时针的方向找到第一个节点就是节点 A。
所以当需要对指定 key 的值进行读写的时候，要通过下面 2 步进行寻址：
1：对 key 进行哈希计算，确定此 key 在环上的位置；
2：从这个位置沿着顺时针方向走，遇到的第一节点就是存储 key 的节点。
知道了一致哈希寻址的方式，我们来看看，如果增加一个节点或者减少一个节点会发生大量的数据迁移吗？
假设节点数量从 3 增加到了 4，新的节点 D 经过哈希计算后映射到了下图中的位置：
可以看到，key-01、key-03 都不受影响，只有 key-02 需要被迁移节点 D。假设节点数量从 3 减少到了 2，比如将节点 A 移除：
可以看到，key-02 和 key-03 不会受到影响，只有 key-01 需要被迁移节点 B。
因此在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。
上面这些图中 3 个节点映射在哈希环还是比较分散的，所以看起来请求都会「均衡」到每个节点。但是一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。比如，下图中 3 个节点的映射位置都在哈希环的右半边：
这时候有一半以上的数据的寻址都会找节点 A，也就是访问请求主要集中的节点 A 上，这肯定不行的，说好的负载均衡呢，这种情况一点都不均衡。
另外在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。比如上图中如果节点 A 被移除了，当节点 A 宕机后，根据一致性哈希算法的规则，其上数据应该全部迁移到相邻的节点 B 上，这样节点 B 的数据量、访问量都会迅速增加很多倍，一旦新增的压力超过了节点 B 的处理能力上限，就会导致节点 B 崩溃，进而形成雪崩式的连锁反应。所以一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。
如何通过虚拟节点提高均衡度
要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。比如对每个节点分别设置 3 个虚拟节点：
对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03
引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。
可以看到，节点数量多了后，节点在哈希环上的分布就相对均匀了。这时候，如果有访问请求寻址到「A-01」这个虚拟节点，接着再通过「A-01」虚拟节点找到真实节点 A，这样请求就能访问到真实节点 A 了。
上面为了方便理解，每个真实节点仅包含 3 个虚拟节点，这样能起到的均衡效果其实很有限。而在实际的工程中，虚拟节点的数量会大很多，比如 Nginx 的一致性哈希算法，每个权重为 1 的真实节点就含有160个虚拟节点。
另外，虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。比如当某个节点被移除时，对应该节点的多个虚拟节点均会移除，而这些虚拟节点按顺时针方向的下一个虚拟节点，可能会对应不同的真实节点，即这些不同的真实节点共同分担了节点变化导致的压力。
且有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可。因此带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。
第一种：传统的数据分布方法,将key的hash值对机器数取模
这个算法的实现非常简单，计算hash(key)/n，n为机器数，得到的值就是该key需要路由到的服务器编号了。
优点：实现简单
缺点：在服务器数量发生变化的时候，缓存会大量失效。
使用哈希算法有什么问题
哈希算法因为对同一个关键字进行哈希计算，每次计算都是相同的值，这样就可以将某个 key 确定到一个节点了，可以满足分布式系统的负载均衡需求。哈希算法最简单的做法就是进行取模运算，比如分布式系统中有 3 个节点，基于 hash(key) % 3 公式对数据进行了映射。
如果客户端要获取指定 key 的数据，通过下面的公式可以定位节点：
hash(key)%3
如果经过上面这个公式计算后得到的值是 0，就说明该 key 需要去第一个节点获取。
但是有一个很致命的问题，如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。举个例子，假设我们有一个由 A、B、C 三个节点组成分布式 KV 缓存系统，基于计算公式 hash(key) % 3 将数据进行了映射，每个节点存储了不同的数据：
现在有 3 个查询 key 的请求，分别查询 key-01，key-02，key-03 的数据，这三个 key 分别经过 hash() 函数计算后的值为 hash( key-01) = 6、hash( key-02) = 7、hash(key-03) = 8，然后再对这些值进行取模运算。通过这样的哈希算法，每个 key 都可以定位到对应的节点。
当 3 个节点不能满足业务需求了，这时我们增加了一个节点，节点的数量从 3 变化为 4，意味取模哈希函数中基数的变化，这样会导致大部分映射关系改变，如下图：
比如，之前的 hash(key-01) % 3 = 0，就变成了 hash(key-01) % 4 = 2，查询 key-01 数据时，寻址到了节点 C，而 key-01 的数据是存储在节点 A 上的，不是在节点 C，所以会查询不到数据。同理，如果我们对分布式系统进行缩容，比如移除一个节点，也会因为取模哈希函数中基数的变化，可能出现查询不到数据的问题。要解决这个问题的办法，就需要我们进行迁移数据，比如节点的数量从 3 变化为 4 时，要基于新的计算公式 hash(key) % 4 ，重新对数据和节点做映射。
假设总数据条数为 M，哈希算法在面对节点数量变化时，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是 O(M)，这样数据的迁移成本太高了。所以应该要重新想一个新的算法，来避免分布式系统在扩容或者缩容时，发生过多的数据迁移。
第二种：一致性hash
试想下如果使用传统取模算法。如果有一个key要存到缓存中，根据hash(key)/n (n表示有n台缓存服务器)，可以计算出缓存所在的服务器id。这个时候有一台服务器挂掉了，剩下n-1台服务器。这时候，同样一个key，根据hash(key)/(n-1) ，这个时候就命中不了缓存了，基本所有的缓存都会失效，这个情况在线上可能是灾难性的。 一致性hash可以解决部分问题。
通常可以考虑[0,(2^32-1)]为hash值的取值范围。我们可以把取值范围想象成一个闭环，2^32-1 和 0 相连接。如下图所示。
这个时候假设我们有4个缓存服务器节点。（node1~node4） 首先计算这四个值的hash值，并且这四个点占据了闭环的四个位置，如上图所示，这个时候需要根据key来路由缓存服务器，首先计算hash(key)值（这个hash算法需要保证hash(key)的值落在在区间[0,2^32-1]中）。然后我们可以想象这个hash（key）值位于闭环的其中一个点，然后用这个hash(key)依次加一，直到命中其中一个node为止，命中的node就是key需要路由的服务器，如上图，需要找到key2的缓存值所在的服务器，首先计算hash(key2)，落在如图的闭环中，然后顺时针找到离这个hash值最近的node，可以看到是node1。key2对应的缓存值就存在node1中。
如果这个时候如果增加了节点node5如下图：
看下缓存失效的情况，如上图，只有hash(key)落在node4~node5之间的key才会有影响，在未增加node5之前落在这个范围的key最终路由到node1,增加node5之后路由到node5了，缓存失效了。除此之外，落在其他范围的hash值就不受影响。如上图，增加node5之后key6原来会路由到node1的，现在路由到node5。而key1不受影响，还是路由到node1。
同理，如果少掉一个节点，还是上图为例，假如这个时候node5失效了，node5失效之前落在node4~node5之间的hash值，会路由到node5，失效之后会路由到node1,也就是原本落在node4~node5之间的hash值失效了。由此可见一致性hash能在节点变动的时候减少缓存失效的比例。
还有一种情况，当cache的数量很少的或者缓存服务器很少的时候，会导致缓存分布不均衡。如下图所示：
当只有很少节点的时候，例如上图的两个，这个时候就会分配得很不均衡。上图中node1明显承受了较多的压力。这个时候引入一个叫虚拟节点的概念，原理就是增加更多的虚拟节点，让每个节点承受的压力尽量均衡。这些增加的节点并不是真正新增的服务器节点，而是由原来的节点”复制“出来的。例如下图，”复制“了两个新节点，node3,node4。实际上，落到node3,node4的key最终访问的服务器是node2,node1。
这样就可以把压力尽量分配到各个机器上。另外需要维护一张表格，用来记录虚拟节点指向的真正节点。
优点：相比简单的对机器数取模算法，当节点变动的时候只有相对较少的key失效，实现也相对简单。不需要进行数据迁移，每个服务器是独立的。
缺点：还是会有部分的key失效，如果访问量非常大的时候，如果访问到失效的key的时候，就会直接访问到数据源上面去了，可能会导致数据源承受重压。
第三种：tair负载均衡算法,构造一张对照表
首先看下如何构建一张对照表。
tair中数据的存储是以bucket为单位的，一个bucket对应一个dateServer,一个dateServer中会有多个bucket。bucket的数目是固定的，这里假设bucket的数量为1024个，并且每个bucket有属于自己的id，依次从0到1023。如下图：
可以看到对key进行hash之后首先会路由到某个bucket然后根据对应关系，再路由到对应的dataServer。
在tair中，你可以设置同一个bucket的备份数目，我们称其中一个bucket为master,其他的备份称为slave。configServer启动的时候会构造三张bucket和dataServer的对照表，分别是hash_table,m_hash_table,d_hash_table，这三张对照表在初始构建的时候都是一样的，但是在dataServer发生增加的时候会暂时不一样，但是最终会趋向一致，三张表分别有什么用处下面会讲到。configServer在构建对照表的时候有两种模式，一种是均衡模式，这种模式会尽量保证每个节点的bucket数目差不多。一种是安全模式，这种模式会尽量保证一份数据以及它的备份分配在不同的区域的服务器上。client通过configServer获取对照表(hash_table)之后，根据（hash(key)%bucket的总数）算出bucket的id并且参照对照表,就能知道这个key对应的dataServer了。对照表的结构大概如下（这里为了简化，一共只有5个bucket，4个dataServer(ds1,ds2,ds3,ds4),这个是初始时的对照表，hash_table, m_hash_table, d_hash_table的内容都是一样的）。
当服务器变化之后configserver是如何重构对照表的？重构对照表的时候，数据是怎么迁移的？
configServer会定时发送心跳包给dataServer，用来检测dataServer是否还存活，如果没有存活的话就会重新构造对照表。或者如果有新加dataServer的话也会重新构造对照表。
当有一个dataServer当机之后，这个机器 上的存储的bucket数据都会丢失，如果是master bucket丢失之后其中一个slave bucket会补上成为master bucket。至于选择哪个slave bucket成为master bucket的是根据slave 上负载的master bucket有没有超标，并且总bucket数有没有超标等标准。举个例子，上图中当ds2失效之后，hash_table, m_hash_table, d_hash_table三个表分别是这样子的。
hash_table ：
m_hash_table：
d_hash_table：
hash_table发送给client，client不至于不能工作，m_hash_table和d_hash_table发送到dataServer，dataServer根据这两张表就可以知道自己是否需要迁移数据和迁移到哪里了。例如这里第一列，第三排，对比两表，可以知道，ds1需要把数据迁移到ds4。
如果是要增加新的dataServer，原理就差不多了，configServer新建对照表，然后把对照表发送到dateServer，然后dataServer再根据新对照表来做数据迁移，完成之后，client就可以使用新的对照表了。
优点：当需要增加机器的时候，不会有key失效。
缺点：实现比较复杂，需要进行数据的迁移。
本文源自：分布式缓存中三种负载均衡的方法
使用一致性哈希算法有什么问题
一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。它也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。
可以把一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，就像钟表一样，钟表的圆可以理解成由 60 个点组成的圆，而此处我们把这个圆想象成由 2^32 个点组成的圆，这个圆环被称为哈希环，如下图：
一致性哈希要进行两步哈希：
1：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
2：当对数据进行存储或访问时，对数据进行哈希映射；
所以一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。问题来了，对「数据」进行哈希映射得到一个结果要怎么找到存储该数据的节点呢？
答案是，映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。
举个例子，有 3 个节点经过哈希计算，映射到了如下图的位置：
接着对要查询的 key-01 进行哈希计算，确定此 key-01 映射在哈希环的位置，然后从这个位置往顺时针的方向找到第一个节点，就是存储该 key-01 数据的节点。比如下图中的 key-01 映射的位置，往顺时针的方向找到第一个节点就是节点 A。
所以当需要对指定 key 的值进行读写的时候，要通过下面 2 步进行寻址：
1：对 key 进行哈希计算，确定此 key 在环上的位置；
2：从这个位置沿着顺时针方向走，遇到的第一节点就是存储 key 的节点。
知道了一致哈希寻址的方式，我们来看看，如果增加一个节点或者减少一个节点会发生大量的数据迁移吗？
假设节点数量从 3 增加到了 4，新的节点 D 经过哈希计算后映射到了下图中的位置：
可以看到，key-01、key-03 都不受影响，只有 key-02 需要被迁移节点 D。假设节点数量从 3 减少到了 2，比如将节点 A 移除：
可以看到，key-02 和 key-03 不会受到影响，只有 key-01 需要被迁移节点 B。
因此在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。
上面这些图中 3 个节点映射在哈希环还是比较分散的，所以看起来请求都会「均衡」到每个节点。但是一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。比如，下图中 3 个节点的映射位置都在哈希环的右半边：
这时候有一半以上的数据的寻址都会找节点 A，也就是访问请求主要集中的节点 A 上，这肯定不行的，说好的负载均衡呢，这种情况一点都不均衡。
另外在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。比如上图中如果节点 A 被移除了，当节点 A 宕机后，根据一致性哈希算法的规则，其上数据应该全部迁移到相邻的节点 B 上，这样节点 B 的数据量、访问量都会迅速增加很多倍，一旦新增的压力超过了节点 B 的处理能力上限，就会导致节点 B 崩溃，进而形成雪崩式的连锁反应。所以一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。
如何通过虚拟节点提高均衡度
要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。比如对每个节点分别设置 3 个虚拟节点：
对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03
引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。
可以看到，节点数量多了后，节点在哈希环上的分布就相对均匀了。这时候，如果有访问请求寻址到「A-01」这个虚拟节点，接着再通过「A-01」虚拟节点找到真实节点 A，这样请求就能访问到真实节点 A 了。
上面为了方便理解，每个真实节点仅包含 3 个虚拟节点，这样能起到的均衡效果其实很有限。而在实际的工程中，虚拟节点的数量会大很多，比如 Nginx 的一致性哈希算法，每个权重为 1 的真实节点就含有160个虚拟节点。
另外，虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。比如当某个节点被移除时，对应该节点的多个虚拟节点均会移除，而这些虚拟节点按顺时针方向的下一个虚拟节点，可能会对应不同的真实节点，即这些不同的真实节点共同分担了节点变化导致的压力。
且有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可。因此带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。