25｜一致性哈希：如何在集群上合理分配流量？

Feb 17, 2022

25｜一致性哈希：如何在集群上合理分配流量？-业务开发算法50讲-极客时间



下载APP





关闭

渠道合作

推荐作者

25｜一致性哈希：如何在集群上合理分配流量？

黄清昊 · 业务开发算法50讲

课程介绍



讲述：代录（老师近期生病）

时长13:40大小12.49M



你好，我是微扰君。
上一讲我们学习了在分布式系统中，生成全局唯一 ID 的两种方式，既可以通过引入独立组件远程调用申请 ID，也可以通过约定的方式让各个节点独立生成唯一 ID。
那对于有多个节点的服务，其他服务或者客户端在访问这个服务的时候，具体应该访问哪一个节点呢？
负载均衡问题大部分情况下，我们都希望集群在分配流量时，能够比较均衡或者按照某种预期的权重比例，这样每个机器都可以得到比较充分的使用，也不容易出现单点服务过载的情况，能够发挥集群的最大价值。
如何分配流量的问题，也通常被称为负载均衡问题，根据不同的业务需要，解决的方式也很多。
比如最直接的，我们可以引入一个中间的负载均衡层，集中记录收到的请求序号；然后按照 Round-Robin 的轮询方式，轮流将外界的请求转发给内部的服务集群，或者直接用随机转发的方式也可以。当然你也可以引入权重，让这两种算法对流量的分配不是均匀的，而是按照一定比重分配在不同的机器上。这两种算法也被称为加权轮询和加权随机。
其实，不止可以通过引入中间层实现，如果整个系统完全可信、可控，你也可以让客户端自己按照随机或轮询的策略，直接调用需要负载均衡的服务，同样可以达到负载均衡的效果。
除了加权轮询、加权随机，负载均衡算法还有许多。这里我们可以看下 Dubbo 官方中文文档中的列出的算法，Dubbo 作为一款知名的 RPC 服务框架，是典型的分布式应用，自然需要支持集群负载均衡，以保证请求可以正确地发送到 Dubbo 实例上。
一共支持了 5 种负载均衡算法，提供的都是客户端负载均衡。这里就不一一讲解了，第三、第四种主要是通过在客户端记录服务集群中不同实例的请求响应情况，以此为依据来判断哪台服务器更适合访问。
这些策略比较简单，但都有比较大的共性问题，无法应对带有状态的请求或服务。这时候就需要我们的一致性哈希算法登场了。
有状态的请求先来了解一下，什么样的请求或者服务是带有状态的呢？
比如一个分布式 KV 缓存系统，为了提高整个系统的容量，我们往往会把数据水平切分到不同的节点来存储，当然为了提供更好的系统可用性，在部分不同节点上存储时，我们会让数据产生一定的冗余。对于这样的系统，某个 key 应该到哪个或者哪些节点上获得，应该是确定的，不是说任意访问一个节点都可以得到缓存结果的。这样的服务，我们就可以认为是有状态的。
再比如，假设某个请求，需要在某个节点上进行一系列连续操作才能完成，也就是构成了一个流程，或者想进行某个操作，会受到在被请求的节点之前请求的影响，在这种的情况下，请求也是有状态的。
在本地，服务器一定会存储和这次请求相关的上下文，这样下次同一个客户端或者会话内发生的请求，就仍然需要打到这台特定的服务器上，才能保证整个服务正常的工作。
这两个例子可能还是有点抽象不太好理解，我们看一个工作中实际的例子。
之前我维护过一个长连接网关，一般主要就是用来做消息推送。某个设备连接到我们的服务器上时，服务器就会去存储里，拉取该设备需要收到的消息进行推送。一个类似场景就是 QQ 登陆时会去服务端拉取消息。所以拉取消息的请求就是一个有状态的请求。
由于需要推送的消息比较多，服务器会以流的形式推送，也会需要随时保留服务器推送消息的位置。一个比较合理的设计就是，
当连接失败，客户端准备重连的时候，一定需要连接到之前连过的服务器，因为只有这台服务器才保留了之前推送消息的位置，可以从之前断连的位置继续推送消息；
如果连接到其他没有保留这样上下文信息的服务器中，唯一能做的就是直接再去存储里拉一下要推送的全部消息，但是这样肯定就包含了之前已推送到一半的消息了。
这个时候我们可以想一想，如果负载均衡采用的是随机或者轮询策略，客户端下次请求的时候，大概率就不会再打到上一次请求的节点了，所以，面对许多有状态的服务和请求，这是有很大问题的。那我们如何解决这种情况下的负载均衡呢？
方案一可能你首先想到的方案是，我们直接在负载均衡服务器上记录一下，每个会话或者客户端上次请求到的服务器是哪一台不就好了，这样如果我们发现这个客户端之前已经有访问记录，那下次还继续打到上一次的机器，不是就可以了？
这个思路当然是理论可行的，但这会对负载均衡系统本身带来巨大的开销。
还记得我们为什么要引入复杂的分布式系统吗？就是因为请求和访问数量太高了，而在负载均衡系统里，如果记录每个请求或者参数对应应该访问哪个机器，这就在负载均衡层引入了状态，本身就是另一个需要负载均衡的应用了。所以即使得以实现，付出的性能开销和代价也是不可接受的。
那怎么做呢？重新思考一下本质想要的目标，我们无非就是希望某些访问的参数或者客户端，在请求的时候，都能指向指定的机器，并且也能起到均衡的效果，那说到这里，不知道你有没有想到我们之前讲过的哈希表也就是散列表呢？我们来看看是否可行。
方案二哈希算法假设一个集群有 20 个可以对外服务的节点，有很多的客户端同时在请求这些服务，我们希望每次从同一个客户端访问的请求，下次再请求集群的时候，也能打到和这次一样的节点上。这不就类似散列表的需求嘛：对任意 key 映射到一段连续数组空间，且同一个 key 每次映射都会映射到数组的同一个位置。
我们就还是用长连网关举例子。
在业务场景中，每个不同的客户端都会有不同的 client-ID 作为唯一客户端标识，有没有想到上一节课学的 UUID，其实差不多就是这样的东西。在有很多同时请求的客户端时，我们可以认为，正在请求的所有客户端 ID，在整个 UUID 的空间里是均匀分布的。
把集群里的 20 个节点连续标号为 0～19，想要让每个节点接受差不多的流量，并保证每个相同的客户端在不同的时候都会请求到同一个节点，我们就只需要把 clientID 哈希到空间为 20 以内的数字，根据这个数字请求对应标号的节点就可以了。最简单的做法就是进行取 MOD 运算。
这样的话，无论采用客户端的负载均衡算法，还是添加一层负载均衡层，我们都只需要告知客户端或者负载均衡服务，现在可用的服务器是哪些，再根据计算而非存储的方式分配流量，既避免了状态的产生，又能完美地解决负载均衡问题。
但是，分布式系统当然没有这么简单了。一旦引入了分布式，我们首先没有办法保证所有节点都能一直正常工作，其次也要考虑可能会经常扩容的情况。还记得哈希表怎么处理扩容的吗，需要申请两倍的空间，然后把原始数据全部重新哈希再次分配。但是如果在分布式的环境中用这个方案，会带来很大的麻烦。
节点数量变化问题我们来看一看，对于负载均衡背后的系统来说，节点数量变化会导致什么样的问题呢？
用一个简化的分布式缓存系统来举例，一共有 3 个节点，每个节点存储一系列 (key, value) 对，假设我们一开始存储了 6 个 KV pair，由于 key 分布均匀，取 MOD 的哈希算法也均匀，它们被均匀地分配在了三个节点上。
此时，如果 2 节点突然异常需要下线，整个系统只剩 1、3 两个节点，我们就需要和 JDK 的 HashMap 一样，做重哈希的工作，这次就需要对所有的 key 进行 MOD2 而不是 MOD3 的操作了。
你会发现，除了需要把 2 节点的数据搬移到 1、3 节点上，为了满足 MOD2 的条件，还需要移动 1 和 3 中本来正常存储可以对外提供服务的两个 KV 对，也就是 (4,emqx) 和 (3,peach)。
更重要的是，分布式应用，数据存储量比单机更大，节点之间的数据拷贝复制需要经过不可靠的网络，不止时延会高，也可能会需要更多次的重传，因此这样大量不必要数据的搬迁，我们是一定要想办法避免的。
而且工业的分布式缓存系统，其实一般不会真的进行数据的搬移，因为需要一直对外提供服务，这个时候一旦大量的请求和存储数据节点失配，会导致同一时间大部分缓存值失效，转而请求源数据，这就会导致被缓存的服务比如数据库，请求激增，出现宕机等情况。这也被称为缓存雪崩。
所以理论上来说，如果某些节点挂了，我们应该尽量保持其他节点上的数据不要移动，这样就不会出现大量缓存数据失效的情况了。有没有办法做到呢？
一致性哈希一致性哈希就很好地解决了这个问题。
最常见的一致性哈希算法同样会采用哈希的思想，但是会把请求，按照标识，比如请求的某些参数、客户端 ID、会话 ID 等等，映射到一个很大的数字空间里，比如 2^32 次方，让它们自然溢出，2^32 在这样的空间里就会被表示为 0，于是整个空间可以看成一个首尾相接的数字环，我们称为项（item）。
而一个个节点，也会按照标识，比如机器 IP 或者编号等等，映射到这个环上，我们称为桶（bucket）。整个环看起来就像这样：
这里的 A、B、C 节点就是三个桶，在负载均衡场景下也就是服务器；而 1、2、3、4、5、6 则是项，可以是一个个不同标识的请求。
看这个环的图，我们如何决定哪个请求应该被分配到哪个服务器上呢？
现在就很简单了，找到每个请求在环上的位置之后，按照某个方向，比如数字增大的方向，找到和当前请求最近的桶，桶所对应的值就是我们一次性哈希的位置，在负载均衡下也就是对应的服务器了。
有可能你有疑问了，这样的策略可以保证负载真的是均衡的吗？ 假设出现这个情况，A、B、C 三个桶集中分布在环的一侧，而请求在环上相对均匀分布，因为我们是按照某个方向寻找最近的，就发现绝大部分请求都被分配到了 C 节点上，而 A 节点一个请求都没有。
一致性哈希的作者当然想到了这个问题，解决办法也非常巧妙。既然负载均衡的节点不是那么多，容易出现分配不均匀的情况，我们给这些 bucket 增加一些副本不就好了，数量比较多的话会更均匀。
一种简单好用的策略就是在某个 bucket 用于哈希的标识之后，拼接上一些字母或者数字，把它们也映射到环上，当作自己的副本，只要 item 在环上顺次找到了副本中的一个，也都认为指向的是对应的 bucket。
这样，桶和副本在环上就不太容易出现集中在一侧的情况了。而且在业务中，请求数量比较大，在用于 Hash 的 key 或者 ID 生成合理的前提下，分布应该天然就是比较均匀的。
实现现在有了思路，动手实现是非常简单的。我之前换工作准备从前端转基础架构的时候，写了一个玩具的分布式缓存，就用到了一致性哈希。这里我简单说明一下相关的代码逻辑，里面耦合了部分和存储相关的逻辑。如果感兴趣，你也可以直接到我的GitHub上了解这个项目，能很好地帮助你练习 LRU。
    package consistent
  
  import (
    "hash/crc32"
    "sort"
  )
  
  // 哈希环 用于存放节点和副本以及需要存储的key
  type HashRing struct {
    nodes      map[uint32]string
    replicates int
    keys       []uint32
  }
  
  // 初始化哈希环 需要传入创建的副本数量
  func New(replicates int) *HashRing {
    hashRing := &HashRing{
      replicates: replicates,
      nodes:      make(map[uint32]string),
    }
  
    return hashRing
  }
  
  // 在哈希环上添加节点 需要传入节点名称
    // 根据副本数，在节点名称后添加数字后缀后进行哈希计算，并放置节点
  func (hashRing *HashRing) Add(key string) {
    for i := 0; i < hashRing.replicates; i++ {
      hash := crc32.ChecksumIEEE([]byte(key + "-" + string(i)))
      hashRing.keys = append(hashRing.keys, hash)
      hashRing.nodes[hash] = key
    }
        // 为了方便查找节点；我们需要将环上节点进行排序
    sort.Slice(hashRing.keys, func(i, j int) bool { return hashRing.keys[i] < hashRing.keys[j] })
  }
  
  // 基于key在环上二分查找最近的节点
  func (hashRing *HashRing) Get(key string) string {
    hash := crc32.ChecksumIEEE([]byte(key))
    idx := sort.Search(len(hashRing.keys), func(i int) bool { return hashRing.keys[i] >= hash })
    if idx == len(hashRing.keys) {
      idx = 0
    }
  
    return hashRing.nodes[hashRing.keys[idx]]
  }
可以看到，利用 Golang 内置的数据结构和方法，代码不超过 50 行，就非常好地解决了这个问题。而且在工作中我也实际用到过这个算法，很值得你手写练习一下。
总结我们今天学习了负载均衡的问题和常用的策略。
对于有多个节点的服务，其他服务或者客户端在访问这个服务的时候，我们希望能够比较均衡地分配流量，发挥集群的最大价值，也不容易出现单点服务过载。最直接的思路就是轮询和随机分配。
但在请求和服务有状态的时候，简单基于轮询和随机的策略就失效了，这个时候我们就需要想办法把有状态的请求稳定的指向同一台机器，保证上下文的连续性，当然，同时也需要能起到均衡的效果。
这个时候，我们可以采用一致性哈希算法，利用请求标识，比如请求的参数或者客户端 ID 等等，把请求稳定的分配到同一台节点，保持上下文的连续性；而相比于直接进行哈希的方式，把请求和节点都映射到同一个哈希环，并顺次寻找最近的节点，可以让我们尽可能少的减少不必要的重哈希，只是把失效节点所负责的请求，较为平均地分配到其他节点之上。
课后作业实现一致性哈希的代码并不困难，你可以自己动手实践一下，有什么问题，欢迎你在评论区留言和我一起讨论。
如果你觉得这篇文章对你有帮助的话，也欢迎转发给你的朋友一起学习。我们下节课见～

一致性哈希算法是解决分布式系统中负载均衡问题的有效方案。传统的负载均衡算法无法满足有状态请求或服务的需求，而一致性哈希算法通过哈希映射客户端ID到服务器节点，实现了对有状态请求的负载均衡，同时避免了引入额外的状态记录。该算法能够有效解决分布式系统中的负载均衡问题，保证请求能够正确地发送到指定的服务器节点，并且能够应对系统扩容等情况。文章通过实际案例和技术原理深入浅出地介绍了一致性哈希算法的应用和优势，对于理解分布式系统中负载均衡问题的读者具有很高的参考价值。文章还提到了一致性哈希算法的实现，通过Golang内置的数据结构和方法，简洁地解决了负载均衡问题。总之，一致性哈希算法是一种高效且可靠的负载均衡解决方案，对于分布式系统的设计和实现具有重要意义。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

2022-02-17

赞 3

提建议

24｜UUID：如何高效生成全局的唯一ID？

26｜B+ Tree：PostgreSQL 的索引是如何建立的？

 写留言

全部留言(3)

最新
精选

peter
2022-02-17
请教老师两个问题： Q1：长连接网关的问题 A 长连接网关有开源框架吗？ B 长连接是双向还是单向的？比如客户端连接到长连接网关，网关到客户端一直有数据流量，需要一直处于连接状态，但是，客户端到网关数据量小，需要一直处于连接状态吗？（不过好像连接不可能是一个方向通而一个方向不通啊，哈） Q2：节点2移除后为什么需要移动4和3？在“节点数量变化问题”部分，节点2下线后，为什么要移动4和3？ Q3：实现部分，例子是练习LRU吗？ “能很好地帮助你练习 LRU”，这句话是说此例子可以用来练习LRU。应该是练习一致性Hash吧。
展开
作者回复: Q1 网上有一些开源的推送组件不过个人觉得和业务耦合比较紧密；开源的不多。我们的长连是双工的。 Q2: 因为采用传统hash取模的方式，如果模数如果变化了，相应的节点数据肯定要搬迁的。 Q3: 我的项目里也实现了LRU。
2
Geek_3xnq17
2022-10-19 来自湖南
没有讲扩容或者缩容时，本来请求路由的问题
Geek_3xnq17
2022-10-19 来自湖南
讲的真好

