数据结构与算法 - Power of Two Choices

两次随机选择法（Power of Two Choices，简称 P2C）是一种高效的负载均衡算法。

背景

实现连接池负载均衡

实现思路

连接池

type ConnPool struct {
	conns []*conn
	i     uint32
}

type conn struct {
	clientConn *grpc.ClientConn
	streams    int32
}

1. 轮询

顺序地从连接池中轮流取出连接。

func (cp *ConnPool) GetConn() (conn *conn) {
	n := uint32(len(cp.conns))
	if n == 0 {
		return nil
	}
	idx := atomic.AddUint32(&cp.i, 1)
	return cp.conns[idx%n]
}

2. 最小连接数

遍历连接池，选中当前连接数最少的连接。

func (cp *ConnPool) GetLeastConn() (conn *conn) {
	if n := len(cp.conns); n == 0 {
		return nil
	}
	var minStreams int32 = math.MaxInt32
	for _, c := range cp.conns {
		streams := atomic.LoadInt32(&c.streams)
		if streams >= minStreams {
			continue
		}
		minStreams = streams
		conn = c
	}
	return
}

3. 其他

Hash、随机、加权轮询 等

最小连接数优化方式

除了遍历连接池的方式外，还有另一种两种随机选择的优化方式，即：从连接池中随机选两个连接，对比它们的负载，选其中活跃连接数更少的那个。

• 较明显的优势：时间复杂度低 O(1)、支持更高规模的连接池。

• 对比遍历方式的不足：选中最少连接数的准确度差、整体负载均衡不是最优。

func (cp *ConnPool) GetLeastConn() (conn *conn) {
	n := len(cp.conns)
	if n == 0 {
		return nil
	} else if n == 1 {
		return cp.conns[0]
	}

	i := rand.Intn(n)
	j := rand.Intn(n)
	for j == i {
		j = rand.Intn(n)
	}

	c1 := cp.conns[i]
	c2 := cp.conns[j]

	if atomic.LoadInt32(&c1.streams) <= atomic.LoadInt32(&c2.streams) {
		return c1
	}
	return c2
}