自适应负载均衡算法原理和实现

简介: 自适应负载均衡算法原理和实现

背景

在选择负载均衡算法时,我们希望满足以下要求:

  1. 具备分区和机房调度亲和性
  • 每次选择的节点尽量是负载最低的
  • 每次尽可能选择响应最快的节点
  1. 无需人工干预故障节点
  • 当一个节点有故障时,负载均衡算法可以自动隔离该节点
  • 当故障节点恢复时,能够自动恢复对该节点的流量分发

基于这些考虑,go-zero 选择了 p2c+EWMA 算法来实现。

算法的核心思想

p2c

p2c (Pick Of 2 Choices) 二选一: 在多个节点中随机选择两个节点。

go-zero 中的会随机的选择3次,如果其中一次选择的节点的健康条件满足要求,就中断选择,采用这两个节点。

EWMA

EWMA (Exponentially Weighted Moving-Average) 指数移动加权平均法: 是指各数值的加权系数随时间呈指数递减,越靠近当前时刻的数值加权系数就越大,体现了最近一段时间内的平均值。

  • 公式:
    EWMA公式
  • 变量解释:
  • Vt: 代表的是第 t 次请求的 EWMA值
  • Vt-1: 代表的是第 t-1 次请求的 EWMA值
  • β: 是一个常量

EWMA 算法的优势

  1. 相较于普通的计算平均值算法,EWMA 不需要保存过去所有的数值,计算量显著减少,同时也减小了存储资源。
  2. 传统的计算平均值算法对网络耗时不敏感, 而 EWMA 可以通过请求频繁来调节 β,进而迅速监控到网络毛刺或更多的体现整体平均值。
  • 当请求较为频繁时, 说明节点网络负载升高了, 我们想监测到此时节点处理请求的耗时(侧面反映了节点的负载情况), 我们就相应的调小ββ越小,EWMA值 就越接近本次耗时,进而迅速监测到网络毛刺;
  • 当请求较为不频繁时, 我们就相对的调大β值。这样计算出来的 EWMA值 越接近平均值

β计算

go-zero 采用的是牛顿冷却定律中的衰减函数模型计算 EWMA 算法中的 β 值:

牛顿冷却定律中的衰减函数

其中 Δt 为两次请求的间隔,ek 为常数

gRPC 中实现自定义负载均衡器

  1. 首先我们需要实现 google.golang.org/grpc/balancer/base/base.go/PickerBuilder 接口, 这个接口是有服务节点更新的时候会调用接口里的Build方法
type PickerBuilder interface {
    // Build returns a picker that will be used by gRPC to pick a SubConn.
    Build(info PickerBuildInfo) balancer.Picker
}
  1. 还要实现 google.golang.org/grpc/balancer/balancer.go/Picker 接口。这个接口主要实现负载均衡,挑选一个节点供请求使用
type Picker interface {
  Pick(info PickInfo) (PickResult, error)
}
  1. 最后向负载均衡 map 中注册我们实现的负载均衡器

go-zero 实现负载均衡的主要逻辑

  1. 在每次节点更新,gRPC 会调用 Build 方法,此时在 Build 里实现保存所有的节点信息。
  2. gRPC 在获取节点处理请求时,会调用 Pick 方法以获取节点。go-zeroPick 方法里实现了 p2c 算法,挑选节点,并通过节点的 EWMA值 计算负载情况,返回负载低的节点供 gRPC 使用。
  3. 在请求结束的时候 gRPC 会调用 PickResult.Done 方法,go-zero 在这个方法里实现了本次请求耗时等信息的存储,并计算出了 EWMA值 保存了起来,供下次请求时计算负载等情况的使用。

负载均衡代码分析

  1. 保存服务的所有节点信息
    我们需要保存节点处理本次请求的耗时、EWMA 等信息,go-zero 给每个节点设计了如下结构:
type subConn struct {
    addr     resolver.Address
    conn     balancer.SubConn
    lag      uint64 // 用来保存 ewma 值
    inflight int64  // 用在保存当前节点正在处理的请求总数
    success  uint64 // 用来标识一段时间内此连接的健康状态
    requests int64  // 用来保存请求总数
    last     int64  // 用来保存上一次请求耗时, 用于计算 ewma 值
    pick     int64  // 保存上一次被选中的时间点
}
  1. p2cPicker 实现了 balancer.Picker 接口,conns 保存了服务的所有节点信息
type p2cPicker struct {
  conns []*subConn  // 保存所有节点的信息 
  r     *rand.Rand
  stamp *syncx.AtomicDuration
  lock  sync.Mutex
}
  1. gRPC 在节点有更新的时候会调用 Build 方法,传入所有节点信息,我们在这里把每个节点信息用 subConn 结构保存起来。并归并到一起用 p2cPicker 结构保存起来
func (b *p2cPickerBuilder) Build(info base.PickerBuildInfo) balancer.Picker {
  ......
  var conns []*subConn
  for conn, connInfo := range readySCs {
    conns = append(conns, &subConn{
      addr:    connInfo.Address,
      conn:    conn,
      success: initSuccess,
    })
  }
  return &p2cPicker{
    conns: conns,
    r:     rand.New(rand.NewSource(time.Now().UnixNano())),
    stamp: syncx.NewAtomicDuration(),
  }
}
  1. 随机挑选节点信息,在这里分了三种情况:
    主要实现代码如下:
switch len(p.conns) {
  case 0: // 没有节点,返回错误
    return emptyPickResult, balancer.ErrNoSubConnAvailable
  case 1: // 有一个节点,直接返回这个节点
    chosen = p.choose(p.conns[0], nil)
  case 2: // 有两个节点,计算负载,返回负载低的节点
    chosen = p.choose(p.conns[0], p.conns[1])
  default: // 有多个节点,p2c 挑选两个节点,比较这两个节点的负载,返回负载低的节点
    var node1, node2 *subConn
    // 3次随机选择两个节点
    for i := 0; i < pickTimes; i++ {
      a := p.r.Intn(len(p.conns))
      b := p.r.Intn(len(p.conns) - 1)
      if b >= a {
        b++
      }
      node1 = p.conns[a]
      node2 = p.conns[b]
      // 如果这次选择的节点达到了健康要求, 就中断选择
      if node1.healthy() && node2.healthy() {
        break
      }
    }
    // 比较两个节点的负载情况,选择负载低的
    chosen = p.choose(node1, node2)
  }
  1. 只有一个服务节点,此时直接返回供 gRPC 使用即可
  2. 有两个服务节点,通过 EWMA值 计算负载,并返回负载低的节点返回供 gRPC 使用
  3. 有多个服务节点,此时通过 p2c 算法选出两个节点,比较负载情况,返回负载低的节点供 gRPC 使用
  1. load计算节点的负载情况
    上面的 choose 方法会调用 load 方法来计算节点负载。
    计算负载的公式是: load = ewma * inflight
    在这里简单解释下:ewma 相当于平均请求耗时,inflight 是当前节点正在处理请求的数量,相乘大致计算出了当前节点的网络负载。
func (c *subConn) load() int64 {
  // 通过 EWMA 计算节点的负载情况; 加 1 是为了避免为 0 的情况
  lag := int64(math.Sqrt(float64(atomic.LoadUint64(&c.lag) + 1)))
  load := lag * (atomic.LoadInt64(&c.inflight) + 1)
  if load == 0 {
    return penalty
  }
  return load
}
  1. 请求结束,更新节点的 EWMA 等信息
func (p *p2cPicker) buildDoneFunc(c *subConn) func(info balancer.DoneInfo) {
  start := int64(timex.Now())
  return func(info balancer.DoneInfo) {
    // 正在处理的请求数减 1
    atomic.AddInt64(&c.inflight, -1)
    now := timex.Now()
    // 保存本次请求结束时的时间点,并取出上次请求时的时间点
    last := atomic.SwapInt64(&c.last, int64(now))
    td := int64(now) - last
    if td < 0 {
      td = 0
    }
    // 用牛顿冷却定律中的衰减函数模型计算EWMA算法中的β值
    w := math.Exp(float64(-td) / float64(decayTime))
    // 保存本次请求的耗时
    lag := int64(now) - start
    if lag < 0 {
      lag = 0
    }
    olag := atomic.LoadUint64(&c.lag)
    if olag == 0 {
      w = 0
    }
    // 计算 EWMA 值
    atomic.StoreUint64(&c.lag, uint64(float64(olag)*w+float64(lag)*(1-w)))
    success := initSuccess
    if info.Err != nil && !codes.Acceptable(info.Err) {
      success = 0
    }
    osucc := atomic.LoadUint64(&c.success)
    atomic.StoreUint64(&c.success, uint64(float64(osucc)*w+float64(success)*(1-w)))
    stamp := p.stamp.Load()
    if now-stamp >= logInterval {
      if p.stamp.CompareAndSwap(stamp, now) {
        p.logStats()
      }
    }
  }
}
  1. 把节点正在处理请求的总数减1
  2. 保存处理请求结束的时间点,用于计算距离上次节点处理请求的差值,并算出 EWMA 中的 β值
  3. 计算本次请求耗时,并计算出 EWMA值 保存到节点的 lag 属性里
  4. 计算节点的健康状态保存到节点的 success 属性中

项目地址

https://github.com/tal-tech/go-zero

相关文章
|
28天前
|
负载均衡 算法 Java
Spring Cloud全解析:负载均衡算法
本文介绍了负载均衡的两种方式:集中式负载均衡和进程内负载均衡,以及常见的负载均衡算法,包括轮询、随机、源地址哈希、加权轮询、加权随机和最小连接数等方法,帮助读者更好地理解和应用负载均衡技术。
|
2月前
|
数据采集 机器学习/深度学习 算法
|
28天前
|
机器学习/深度学习 算法 Python
群智能算法:深入解读人工水母算法:原理、实现与应用
近年来,受自然界生物行为启发的优化算法备受关注。人工水母算法(AJSA)模拟水母在海洋中寻找食物的行为,是一种新颖的优化技术。本文详细解读其原理及实现步骤,并提供代码示例,帮助读者理解这一算法。在多模态、非线性优化问题中,AJSA表现出色,具有广泛应用前景。
|
2月前
|
前端开发 算法 JavaScript
React原理之Diff算法
【8月更文挑战第24天】
|
2月前
|
负载均衡 监控 算法
揭秘负载均衡的五大算法秘籍:让你的服务器轻松应对亿万流量,不再崩溃!
【8月更文挑战第31天】在互联网快速发展的今天,高可用性和可扩展性成为企业关注的重点。负载均衡作为关键技术,通过高效分配网络流量提升系统处理能力。本文介绍了轮询、加权轮询、最少连接及IP哈希等常见负载均衡算法及其应用场景,并提供Nginx配置示例。此外,还探讨了如何根据业务需求选择合适算法、配置服务器权重、实现高可用方案、监控性能及定期维护等最佳实践,助力系统优化与用户体验提升。
58 2
|
2月前
|
负载均衡 算法 调度
负载均衡原理分析与源码解读
负载均衡原理分析与源码解读
|
2月前
|
负载均衡 算法 微服务
基于gRPC的注册发现与负载均衡的原理和实战
基于gRPC的注册发现与负载均衡的原理和实战
|
2月前
|
存储 监控 算法
自适应微服务治理背后的算法
自适应微服务治理背后的算法
|
2月前
|
算法 安全 网络安全
Diffie-Hellman (DH) 算法的工作原理
【8月更文挑战第23天】
126 0
|
2月前
|
负载均衡 网络协议 Linux
在Linux中,负载均衡的原理是什么?
在Linux中,负载均衡的原理是什么?
下一篇
无影云桌面