负载均衡原理分析与源码解读 - go-zero开源社区 - SegmentFault 思否

指数加权移动平均法（EWMA）

一 P2C负载均衡算法 & EWMA

在go-zero中默认使用的是P2C的负载均衡算法。
算法的原理：即随机从所有可用节点中选择两个节点，然后计算这两个节点的负载情况，选择负载较低的一个节点来服务本次请求。
为了避免某些节点一直得不到选择导致不平衡，会在超过一定的时间后强制选择一次。

使用EWMA指数移动加权平均，记录每个节点的平均延迟，该算法相对于算数平均来说对于突然的网络抖动没有那么敏感，从而可以让算法更加均衡。

二 源码阅读

2.1EWMA记录节点的平均延迟

buildDoneFunc返回函数会复制给 PickResult.Done， RPC完成调用后会执行PickResult.Done方法。

/*
// Done is called when the RPC is completed.
rpc 完成时将会执行该函数
*/
func (p *p2cPicker) buildDoneFunc(c *subConn) func(info balancer.DoneInfo) {
	//start 记录subConn被选中的时间
	start := int64(timex.Now())
	return func(info balancer.DoneInfo) {
        //......
		now := timex.Now()
		last := atomic.SwapInt64(&c.last, int64(now))
		//本次请求 和 上次请求 请求间隔
		td := int64(now) - last
		if td < 0 {
			td = 0
		}
		//e^x 距离最后一次请求 时间约久，权重约低
		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
		}
		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)))

		//每一分钟记录一次请求日志
	    //......
	}

2.2 选择节点

Pick方法从所有节点随机选择两个节点，交给choose方法计算两个节点中负载。

func (p *p2cPicker) Pick(info balancer.PickInfo) (balancer.PickResult, error) {
	p.lock.Lock()
	defer p.lock.Unlock()

	var chosen *subConn
	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:
		//从所有链接中随机选择两个
		var node1, node2 *subConn
		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)
	}
	
	atomic.AddInt64(&chosen.inflight, 1)
	atomic.AddInt64(&chosen.requests, 1)

	return balancer.PickResult{
		SubConn: chosen.conn,
		Done:    p.buildDoneFunc(chosen),
	}, nil
}

choose 方法计算这两个节点的负载情况，选择负载较低的一个节点来服务本次请求。为了避免某些节点一直得不到选择导致不平衡，会在超过一定的时间后强制选中一次。

/*
从两个链接中 选择一个负载较低的链接
*/
func (p *p2cPicker) choose(c1, c2 *subConn) *subConn {
	start := int64(timex.Now())
	if c2 == nil {
		atomic.StoreInt64(&c1.pick, start)
		return c1
	}

	if c1.load() > c2.load() {
		c1, c2 = c2, c1
	}

	//如果1s没有选中过，被强制选中
	pick := atomic.LoadInt64(&c2.pick)
	if start-pick > forcePick && atomic.CompareAndSwapInt64(&c2.pick, pick, start) {
		return c2
	}

	atomic.StoreInt64(&c1.pick, start)
	return c1
}

三 总结

1.在go-zero中默认使用的是P2C的负载均衡算法

2.使用EWMA算法记录节点的负载情况，EWMA算法对突然的网络抖动没有那么敏感。

3.使用p2c负载均衡算法选择负载节点，为了避免某些节点一直得不到选择导致不平衡，会在超过一定的时间后强制选择一次。