在微服务的架构模式下服务间通过长连接进行通信，通常情况下每个客户端实例都会与每个服务实例建立连接，如果服务实例数达到几千几万个那么相互之间建立的连接数将指数级上升，这样带来的坏处是：

  1. 客户端的连接池里的连接数变多，消耗的资源增加
  2. 对应的服务端维护的长连接增多，尤其在一个连接一个线程的模式下消耗的资源很可观
  3. 长连接定期的健康检查消耗一定的CPU

为了避免过多的资源消耗客户端可以选择服务集群实例的某个子集来建立连接，这样可有效的减少资源消耗。这个子集的选择方案必须满足以下几个条件：

  1. 子集的大小要足够客户端使用
  2. 后端服务的连接数要负载均衡
  3. 能够在服务重启、滚动升级、客户端和服务端进行集群大小调整时持续均衡，避免大量连接的重建、迁移或者各服务实例的连接数产生较大的波动

接下来看看Google是如何解决这个问题的

随机选择

在确定好子集的大小后采用完全随机的方式为每个客户端选择固定大小的子集，但经过实验这种方式负载的效果非常差，要想达到比较均匀的负载则子集大小至少要在75%，这对于大规模部署的集群来说是不可接受的。

个人认为之所以完全随机表现的不够好是因为连接的建立次数是有限的，只在服务初始化时建立。这就好比抛硬币正反面出现的概率各占50%，但是如果我们只抛四次有可能出现三次正面一次反面，只有抛的次数足够多才能无限接近概率。而每次连接的建立就好比一次抛硬币，如果连接建立的次数足够多那负载会比较均衡，扩大子集的规模一定程度上增加了抛硬币的次数，如果每次请求都新建连接那么负载的效果会比较好但每次新建连接的成本太高，所以该方法不可靠。

确定性算法

随后Google抛弃了完全随机的算法，采用了一种相对确定的算法：

1
2
3
4
5
6
7
8
9
10
11
12
func Subset(backends []string, clientID, subsetSize int) []string {
	// 计算一轮可满足几个客户端
	subsetCount := len(backends)/subsetSize
	// 计算本次客户端属于哪一轮，每一轮使用相同的随机列表
	round := clientID/subsetCount
	 r := rand.New(rand.NewSource(int64(round)))
 r.Shuffle(len(backends), func(i, j int) { backends[i], backends[j] = backends[j], backends[i] })
 	// 计算客户端在本轮中的位置
 	subsetID := clientID % subsetCount
 	start := subsetID * subsetSize
 	return backends[start: start+subsetSize]
}

假设我们有13个后端实例，有10个客户端，子集的大小为3。那么每轮我们最多可以给4个客户端分配后端实例：subsetCount = 12/3，每一轮里一个后端实例只会被分配给一个且仅一个客户端，当客户端数量不够时有些实例没有被分配，但没有被分配的实例在每一轮中是随机的。总共有10个实例所以我们要分配三轮，每次产生的随机列表可能如下：

1
2
3
4
5
Round 0: [0, 6, 3, 5, 12, 1, 7, 11, 9, 2, 4, 8, 10]

Round 1: [8, 11, 4, 12, 0, 5, 6, 10, 3, 2, 7, 9, 1]

Round 2: [8, 3, 7, 2, 1, 4, 12, 9, 10, 6, 5, 0, 11]

例如clientID为2每个client需要3个连接则roud=2/4=0，subsetID= 2%4 = 2，那分配给该客户端的实例为[7, 11, 9]。注意，在最后一轮中只有2个客户端需要分配，所以剩下的两组后端实例是没有被分配连接的。

只要clientID是连续的则分配到每个后端的连接数也是均匀的

滚动更新及扩容

Client

某个client的下线不会影响其他client的连接分布，所以当某个client下线时只会导致某些backend实例连接数比其他实例少1

client集群扩容时clientID从后面依次递增按照上述算法的描述连接依然是均匀的

Server

与client情况类似，当某个server实例下线时会导致跟这台实例有连接的部分client连接发生变化，但因每个server随机分配给不同的client从整体来看计算结果不会有大变化

server集群扩容时相当于每一轮能满足的client数变多，round变小连接依然是均匀的

最后

确定性算法为什么比完全随机要负载更均匀呢？确定性算法将客户端划分为多轮，在同一轮之中使用相同的随机序列使一轮之中连接的分配是均匀的，而每轮序列的不同又增加了一定的随机性

要使用该算法还需要考虑以下几个问题：

  1. clientID是需要连续的，这将增加外部依赖
  2. 如果clientID并非滚动升级那么极端情况下会挑选出一批client使得某台服务实例连接数为0
  3. 如果一次滚动升级的服务实例数较多囊括了某个client所选择的全部实例则会导致该client无连接可用

参考

[1] https://sre.google/sre-book/load-balancing-datacenter/