背景

在抉择负载平衡算法时，咱们心愿满足以下要求：

  1. 具备分区和机房调度亲和性

    • 每次抉择的节点尽量是负载最低的
    • 每次尽可能选择响应最快的节点

  2. 无需人工干预故障节点

    • 当一个节点有故障时，负载平衡算法能够主动隔离该节点
    • 当故障节点复原时，可能主动复原对该节点的流量散发

基于这些思考，go-zero 抉择了 p2c+EWMA 算法来实现。

算法的核心思想

p2c

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

go-zero 中的会随机的抉择3次，如果其中一次抉择的节点的衰弱条件满足要求，就中断抉择，采纳这两个节点。

EWMA

EWMA (Exponentially Weighted Moving-Average) 指数挪动加权平均法: 是指各数值的加权系数随工夫呈指数递加，越凑近以后时刻的数值加权系数就越大，体现了最近一段时间内的平均值。

  • 公式:

  • 变量解释:

    • Vt: 代表的是第 t 次申请的 EWMA值
    • Vt-1: 代表的是第 t-1 次申请的 EWMA值
    • : 是一个常量

EWMA 算法的劣势

  1. 相较于一般的计算平均值算法，EWMA 不须要保留过来所有的数值，计算量显著缩小，同时也减小了存储资源。

  2. 传统的计算平均值算法对网络耗时不敏感, 而 EWMA 能够通过申请频繁来调节 ，进而迅速监控到网络毛刺或更多的体现整体平均值。

    • 当申请较为频繁时, 阐明节点网络负载升高了, 咱们想监测到此时节点解决申请的耗时(侧面反映了节点的负载状况), 咱们就相应的调小。越小，EWMA值 就越靠近本次耗时，进而迅速监测到网络毛刺;
    • 当申请较为不频繁时, 咱们就绝对的调大值。这样计算出来的 EWMA值 越靠近平均值

计算

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

其中 t 为两次申请的距离，e，k 为常数

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}

  2. 还要实现 google.golang.org/grpc/balancer/balancer.go/Picker 接口。这个接口次要实现负载平衡，筛选一个节点供申请应用

    type Picker interface {  Pick(info PickInfo) (PickResult, error)}
  3. 最初向负载平衡 map 中注册咱们实现的负载均衡器

go-zero 实现负载平衡的次要逻辑

  1. 在每次节点更新，gRPC 会调用 Build 办法，此时在 Build 里实现保留所有的节点信息。
  2. gRPC 在获取节点解决申请时，会调用 Pick 办法以获取节点。go-zero 在 Pick 办法里实现了 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  // 保留上一次被选中的工夫点}

  2. p2cPicker 实现了 balancer.Picker 接口，conns 保留了服务的所有节点信息

    type p2cPicker struct {  conns []*subConn  // 保留所有节点的信息   r     *rand.Rand  stamp *syncx.AtomicDuration  lock  sync.Mutex}

  3. 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(),  }}

  4. 随机筛选节点信息，在这里分了三种状况:

    1. 只有一个服务节点，此时间接返回供 gRPC 应用即可
    2. 有两个服务节点，通过 EWMA值 计算负载，并返回负载低的节点返回供 gRPC 应用
    3. 有多个服务节点，此时通过 p2c 算法选出两个节点，比拟负载状况，返回负载低的节点供 gRPC 应用

    次要实现代码如下：

    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)  }

  5. 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}

  6. 申请完结，更新节点的 EWMA 等信息

    1. 把节点正在解决申请的总数减1
    2. 保留解决申请完结的工夫点，用于计算间隔上次节点解决申请的差值，并算出 EWMA 中的 值
    3. 计算本次申请耗时，并计算出 EWMA值 保留到节点的 lag 属性里

    4. 计算节点的衰弱状态保留到节点的 success 属性中

      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()   } }}}

我的项目地址

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

欢送应用 go-zero 并 star 反对咱们！

微信交换群

关注『微服务实际』公众号并点击 交换群 获取社区群二维码。