feat(lb): interleaved weighted round-robin load balancer #1019

jizhuozhi · 2023-07-06T15:22:46Z

An O(1) time and O(n) memory weighted load balancing implementation

What type of PR is this?

Check the PR title.

This PR title match the format: <type>(optional scope): <description>
The description of this PR title is user-oriented and clear enough for others to understand.
Attach the PR updating the user documentation if the current PR requires user awareness at the usage level. User docs repo

(Optional) Translate the PR title into Chinese.

交错式加权轮询负载均衡算法，时间复杂度O(1)，空间复杂度O(n)，相比于VNSWRR的O(sigma(W))更省空间且可控

(Optional) More detailed description for this PR(en: English/zh: Chinese).

https://en.wikipedia.org/wiki/Weighted_round_robin#Interleaved_WRR

与Linux O(1)调度器思路相同，维护两个队列，分别是当前队列和下一次队列。队列中的每个元素都维护remainder表示在当前队列中剩余可选中次数，初始时remainder与权重相同，每次被选中后都会减少remainder（使用GCD来缩短周期）。当remainder为0时表示当前周期内不可调度，将其放到下一次队列中。当当前队列为空时表示当前周期所有元素都被按权重选择过了，此时对换当前队列和下一次队列开始新一轮周期。由于始终复用链表节点，因此该负载均衡算法实现在初始化后可以保证是零分配的。

(Optional) Which issue(s) this PR fixes:

(optional) The PR that updates user documentation:

An O(1) time and O(n) memory weighted load balancing implementation

jizhuozhi · 2023-07-06T15:25:12Z

Compared with NGINX SWRR, it abandons the smooth feature, but in a large traffic scenario, the benefits brought by load balancing smoothing are very low, because a cycle will be selected in a short time.

Here is the benchmark

goos: darwin
goarch: amd64
pkg: github.com/cloudwego/kitex/pkg/loadbalance
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkWeightedPicker_Next
BenchmarkWeightedPicker_Next/weight_round_robin
BenchmarkWeightedPicker_Next/weight_round_robin/10ins
BenchmarkWeightedPicker_Next/weight_round_robin/10ins-16   	35996655	        29.68 ns/op
BenchmarkWeightedPicker_Next/weight_round_robin/100ins
BenchmarkWeightedPicker_Next/weight_round_robin/100ins-16  	43196908	        28.20 ns/op
BenchmarkWeightedPicker_Next/weight_round_robin/1000ins
BenchmarkWeightedPicker_Next/weight_round_robin/1000ins-16 	44490229	        28.01 ns/op
BenchmarkWeightedPicker_Next/weight_round_robin/10000ins
BenchmarkWeightedPicker_Next/weight_round_robin/10000ins-16         	43913323	        27.36 ns/op
BenchmarkWeightedPicker_Next/weight_random
BenchmarkWeightedPicker_Next/weight_random/10ins
BenchmarkWeightedPicker_Next/weight_random/10ins-16                 	48869401	        25.84 ns/op
BenchmarkWeightedPicker_Next/weight_random/100ins
BenchmarkWeightedPicker_Next/weight_random/100ins-16                	48376174	        24.28 ns/op
BenchmarkWeightedPicker_Next/weight_random/1000ins
BenchmarkWeightedPicker_Next/weight_random/1000ins-16               	48595500	        25.93 ns/op
BenchmarkWeightedPicker_Next/weight_random/10000ins
BenchmarkWeightedPicker_Next/weight_random/10000ins-16              	43551429	        26.65 ns/op
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/10ins
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/10ins-16         	61868748	        18.20 ns/op
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/100ins
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/100ins-16        	62682951	        17.69 ns/op
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/1000ins
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/1000ins-16       	67905054	        17.31 ns/op
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/10000ins
BenchmarkWeightedPicker_Next/interleaved_weighted_round_robin/10000ins-16      	62474013	        17.14 ns/op
PASS

pkg/loadbalance/interleaved_weighted_round_robin.go

An O(1) time and O(n) memory weighted load balancing implementation

pkg/loadbalance/interleaved_weighted_round_robin.go

codecov · 2023-07-07T05:17:10Z

Codecov Report

Patch coverage: 100.00% and project coverage change: +0.11 🎉

Comparison is base (ab3c244) 68.01% compared to head (bcbcb90) 68.13%.

❗ Current head bcbcb90 differs from pull request most recent head a9c25ff. Consider uploading reports for the commit a9c25ff to get more accurate results

Additional details and impacted files

@@             Coverage Diff             @@
##           develop    #1019      +/-   ##
===========================================
+ Coverage    68.01%   68.13%   +0.11%     
===========================================
  Files          248      249       +1     
  Lines        18802    18867      +65     
===========================================
+ Hits         12789    12855      +66     
- Misses        4845     4850       +5     
+ Partials      1168     1162       -6

Impacted Files	Coverage Δ
...kg/loadbalance/interleaved_weighted_round_robin.go	`100.00% <100.00%> (ø)`
pkg/loadbalance/weighted_balancer.go	`89.18% <100.00%> (+1.68%)`	⬆️
pkg/loadbalance/weighted_round_robin.go	`94.28% <100.00%> (+0.53%)`	⬆️

... and 7 files with indirect coverage changes

☔ View full report in Codecov by Sentry.
📢 Do you have feedback about the report comment? Let us know in this issue.

joway · 2023-07-14T08:02:54Z

@jizhuozhi Hi，Last thing you need to do is updating the docs in : https://github.com/cloudwego/cloudwego.github.io/blob/main/content/zh/docs/kitex/Tutorials/service-governance/loadbalance.md

Both chinese and english.

jizhuozhi · 2023-07-16T15:58:44Z

@jizhuozhi Hi，Last thing you need to do is updating the docs in : https://github.com/cloudwego/cloudwego.github.io/blob/main/content/zh/docs/kitex/Tutorials/service-governance/loadbalance.md

Both chinese and english.

Hello, @joway . The docs is updated, PTAL.

feat(lb): interleaved weighted round-robin load balancer

160d76d

An O(1) time and O(n) memory weighted load balancing implementation

jizhuozhi requested review from a team as code owners July 6, 2023 15:22

Merge branch 'develop' into iwrr

c754eee