负载均衡

Kitex 提供的负载均衡器实现原理和使用指南。

Kitex 默认提供了以下几种 LoadBalancer:

  • WeightedRoundRobin
  • InterleavedWeightedRoundRobin(kitex >= v0.7.0)
  • WeightedRandom
  • Alias Method(kitex >= v0.9.0)
  • ConsistentHash
  • Tagging Based

Kitex 默认使用的是 WeightedRoundRobin。

WeightedRoundRobin

该 LoadBalancer 使用的是基于权重的轮询策略,也是 Kitex 的默认策略。

该 LoadBalancer 能让所有下游实例拥有最小的同时 inflight 请求数,以减少下游过载情况的发生。

如果所有的实例的权重都一样,会使用一个纯轮询的实现,来避免加权计算的一些额外开销。

使用方式:

cli, err := echo.NewClient("echo", client.WithLoadBalancer(loadbalance.NewWeightedRoundRobinBalancer()))

InterleavedWeightedRoundRobin

WeightedRoundRobin 相同, 该 LoadBalancer 使用的也是基于权重的轮询策略。

区别在于 WeightedRoundRobin 的空间复杂度是将所有实例按权重选择一遍的最小正周期(所有实例权重的和除以所有实例权重的最大公约数), 而该 LoadBalancer 的空间复杂度是下游实例数,在下游实例数权重总和非常大时更节省空间。

使用方式:

cli, err := echo.NewClient("echo", client.WithLoadBalancer(loadbalance.NewInterleavedWeightedRoundRobinBalancer()))

WeightedRandom

顾名思义,这个 LoadBalancer 使用的是基于权重的随机策略。

这个 LoadBalancer 会依据实例的权重进行加权随机,并保证每个实例分配到的负载和自己的权重成比例。

如果所有的实例的权重都一样,会使用一个纯随机的实现,来避免加权计算的一些额外开销。

使用方式:

cli, err := echo.NewClient("echo", client.WithLoadBalancer(loadbalance.NewWeightedRandomBalancer()))

Alias Method

使用别名方法的 LoadBalancer ,具体来说实现的是 Darts, Dice, and Coins 中的 Vose’s Alias Method

使用 O(n) 时间生成别名表,之后在 O(1) 时间内选取实例,选取效率比 WeightedRandom 更高

cli, err := echo.NewClient("echo", client.WithLoadBalancer(loadbalance.NewWeightedRandomWithAliasMethodBalancer()))

ConsistentHash

简介

一致性哈希主要适用于对上下文(如实例本地缓存)依赖程度高的场景,如希望同一个类型的请求打到同一台机器,则可使用该负载均衡方法。

如果你不了解什么是一致性哈希,或者不知道带来的副作用,请勿使用一致性哈希。

使用

创建 client 的时候初始化一致性哈希策略:

cli, err := echo.NewClient(
    "echo",
    client.WithLoadBalancer(loadbalance.NewConsistBalancer(loadbalance.NewConsistentHashOption(func(ctx context.Context, request interface{}) string {
		// 根据请求上下文信息设置 key
        return "key"
    }))),
)

ConsistentHashOption 定义如下:

type ConsistentHashOption struct {
    GetKey KeyFunc

    // 是否使用 replica
    // 如果使用,当请求失败(连接失败)后会依次尝试 replica
    // 会带来额外内存和计算开销
    // 如果不设置,那么请求失败(连接失败)后直接返回
    Replica uint32

    // 虚拟节点数
    // 每个真实节点对应的虚拟节点的数量
    // 这个数值越大,内存和计算代价越大,负载越均衡
    // 当节点数多时,可以适当设小一些;反之可以适当设大一些
    // 推荐 VirtualFactor * Weight(如果 Weighted 为 true)的中位数在 1000 左右,负载应当已经很均衡了
    // 推荐 总虚拟节点数 在 2000W 以内(1000W 情况之下 build 一次需要 250ms,不过为后台 build 理论上 3s 内均无问题)
    VirtualFactor    uint32

    // 是否要遵循 Weight 进行负载均衡
    // 如果为 false,对于每个 instance 都会忽略 Weight,均生成 VirtualFactor 个虚拟节点,进行无差别负载均衡
    // 如果为 true,对于每个 instance 会生成 instance.Weight() * VirtualFactor 个虚拟节点
    // 需要注意,对于 weight 为 0 的 instance,无论 VirtualFactor 为多少,均不会生成虚拟节点
    // 建议设为 true,不过要注意适当调小 VirtualFactor
    Weighted bool

    // 是否进行过期处理
    // 实现会缓存所有的 Key
    // 如果永不过期会导致内存一直增长
    // 设置过期会导致额外性能开销
    // 目前的实现是每分钟扫描删除一次,以及实例发生变动 rebuild 时删除一次
    // 建议一定要设置,值不要小于一分钟
    ExpireDuration time.Duration
}

要注意,如果 GetKey 是 nil 或者 VirtualFactor 是 0,会 panic。

性能

经过测试,在 weight 为 10、VirtualFactor 为 100 的情况之下,不同 instance 数量的 build 性能如下:

BenchmarkNewConsistPicker_NoCache/10ins-16                 6565        160670 ns/op      164750 B/op          5 allocs/op
BenchmarkNewConsistPicker_NoCache/100ins-16                 571       1914666 ns/op     1611803 B/op          6 allocs/op
BenchmarkNewConsistPicker_NoCache/1000ins-16                 45      23485916 ns/op    16067720 B/op         10 allocs/op
BenchmarkNewConsistPicker_NoCache/10000ins-16                 4     251160920 ns/op    160405632 B/op        41 allocs/op

所以当有 10000 个 instance,每个 instance weight 为 10,VirtualFactor 为 100 的情况之下(总虚拟节点数 1000W),build 一次需要 251 ms。

build 和 请求 信息都会被缓存,所以一次正常请求(不需要 build)的时延和节点多少无关,如下:

BenchmarkNewConsistPicker/10ins-16             12557137            81.1 ns/op         0 B/op          0 allocs/op
BenchmarkNewConsistPicker/100ins-16            13704381            82.3 ns/op         0 B/op          0 allocs/op
BenchmarkNewConsistPicker/1000ins-16           14418103            81.3 ns/op         0 B/op          0 allocs/op
BenchmarkNewConsistPicker/10000ins-16          13942186            81.0 ns/op         0 B/op          0 allocs/op

注意事项

  1. 下游节点发生变动时,一致性哈希结果可能会改变,某些 key 可能会发生变化;
  2. 如果下游节点非常多,第一次冷启动时 build 时间可能会较长,如果 rpc 超时短的话可能会导致超时;
  3. 如果第一次请求失败,并且 Replica 不为 0,那么会请求到 Replica 上;而第二次及以后仍然会请求 第一个 实例。

负载的均衡度

经过测试,当下游实例为 10 个时,如果 VirtualFactor 设置为 1 并且不开启 Weighted 时,负载非常不均衡,如下:

addr2: 28629
addr7: 13489
addr3: 10469
addr9: 4554
addr0: 21550
addr6: 6516
addr8: 2354
addr4: 9413
addr5: 1793
addr1: 1233

当 VirtualFactor 设置为 10 时,负载如下:

addr7: 14426
addr8: 12469
addr3: 8115
addr4: 8165
addr0: 8587
addr1: 7193
addr6: 10512
addr9: 14054
addr2: 9307
addr5: 7172

可以看出比 VirtualFactor 为 1 时要好很多。

当 VirtualFactor 为 1000 时,负载如下:

addr7: 9697
addr5: 9933
addr6: 9955
addr4: 10361
addr8: 9828
addr0: 9729
addr9: 10528
addr2: 10121
addr3: 9888
addr1: 9960

可以看出此时负载基本均衡。

再来看看带 Weight 的情况,我们设置 addr0 的 weight 为 0,addr1 的 weight 为 1,addr2 的 weight 为 2……以此类推。

设置 VirtualFactor 为 1000,得到负载结果如下:

addr4: 8839
addr3: 6624
addr6: 13250
addr1: 2318
addr8: 17769
addr2: 4321
addr5: 11099
addr9: 20065
addr7: 15715

可以看到基本是和 weight 的分布一致。在这里没有 addr0 是因为 weight 为 0 是不会被调度到的。

综上,提高 VirtualFactor,可以使得负载更加均衡,但是也要注意会增加性能开销,需要找个平衡点。

Tagging Based

拓展 loadbalance-tagging 提供了一个基于标签的负载均衡策略,允许根据客户端上的标签将集群划分为不同的子集。

这适用于有状态服务或多租户服务的场景,使得可以对服务实例进行更细粒度的控制和路由。

特性

  • 基于标签的子集划分: 便于特定请求定向到相应的服务实例;

  • 适用于多态服务: 支持有状态服务的特定需求,在多租户环境中实现请求路由;

  • 自定义标签函数: 允许通过自定义函数使用标签,以实现更复杂的负载均衡策略。

使用

cli, err := echo.NewClient("echo",
    client.WithLoadBalancer(tagging.New(
        "tag",
        func(ctx context.Context, req interface{}) string {
            return "value"
        },
		// 可以自行选择负载均衡策略,如果需要基于多标签,可以再次传入 tagging.new() 来使用新的 tag
        loadbalance.NewWeightedRoundRobinBalancer(),
    )))