feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms #1199

NX-Official · 2023-12-10T09:32:44Z

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.

添加一种使用 Alias Method 的负载均衡方法，来减少权重随机负载均衡算法的时间复杂度

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

en:

Alias Method:

https://en.wikipedia.org/wiki/Alias_method
http://www.keithschwarz.com/darts-dice-coins/

zh(optional):

https://nickxu.me/post/darts-dice-coins-chinese-version

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

#1184

(optional) The PR that updates user documentation:

CLAassistant · 2023-12-10T09:32:50Z

All committers have signed the CLA.

codecov · 2023-12-11T04:55:16Z

Codecov Report

All modified and coverable lines are covered by tests ✅

Comparison is base (a6d5d90) 66.89% compared to head (b2ff131) 66.97%.

Additional details and impacted files

@@             Coverage Diff             @@
##           develop    #1199      +/-   ##
===========================================
+ Coverage    66.89%   66.97%   +0.07%     
===========================================
  Files          256      257       +1     
  Lines        19479    19534      +55     
===========================================
+ Hits         13031    13082      +51     
- Misses        5271     5282      +11     
+ Partials      1177     1170       -7

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

ppzqh · 2023-12-11T06:04:52Z

thanks for the contribution. Please fix the ci issue and add the reference of this algorithm in the pr description

pkg/loadbalance/weighted_random_with_alias_method.go

ppzqh · 2023-12-13T11:01:58Z

Can we add a benchmark for init, which is also used when rebalance.

NX-Official · 2023-12-19T03:19:40Z

BenchmarkAliasMethodPickerInit

goos: darwin
goarch: arm64
pkg: github.com/cloudwego/kitex/pkg/loadbalance
BenchmarkAliasMethodPickerInit
BenchmarkAliasMethodPickerInit/10ins
BenchmarkAliasMethodPickerInit/10ins-8         	 9356866	       136.7 ns/op	     400 B/op	       5 allocs/op
BenchmarkAliasMethodPickerInit/100ins
BenchmarkAliasMethodPickerInit/100ins-8        	 1512398	       848.7 ns/op	    4480 B/op	       5 allocs/op
BenchmarkAliasMethodPickerInit/1000ins
BenchmarkAliasMethodPickerInit/1000ins-8       	  180366	      6993 ns/op	   40960 B/op	       5 allocs/op
BenchmarkAliasMethodPickerInit/10000ins
BenchmarkAliasMethodPickerInit/10000ins-8      	   13801	     92550 ns/op	  409604 B/op	       5 allocs/op
PASS

ppzqh · 2023-12-19T05:02:23Z

LGTM

pkg/loadbalance/weighted_random_with_alias_method_test.go

NX-Official · 2024-01-07T06:38:54Z

我觉得这个 PR 已经可以和进去了（但是貌似会报一些我感觉奇怪的 CI 问题

ppzqh · 2024-01-08T01:36:10Z

我觉得这个 PR 已经可以和进去了（但是貌似会报一些我感觉奇怪的 CI 问题

什么问题？

NX-Official · 2024-01-08T02:57:18Z

我觉得这个 PR 已经可以和进去了（但是貌似会报一些我感觉奇怪的 CI 问题

什么问题？

review 通过一下看看👀

AsterDY · 2024-01-08T06:35:15Z

kitex/pkg/loadbalance/weighted_balancer_test.go at 834c15a5e6c7def209f257246122803ed1e77b92 · cloudw 发现这个 BenchmarkWeightedPicker_Next 测试结果有点奇怪：“weitghted_random” 的性能并没有随着n增大而裂化（明明是O(N))，导致新算法的收益看起来不是很明显。初步debug看了下传到weightedRandomPicker.Next(）里面的instances一直都是10估计是有bug，cc @ppzqh 。同学如果有兴趣也帮忙看看问题在哪吧 @NX-Official

ppzqh · 2024-01-08T10:08:01Z

这个单测问题我修了，辛苦rebase一下，再跑个测试

jizhuozhi

LGTM

ppzqh · 2024-03-11T07:43:07Z

@NX-Official Hi, 这个alis method的功能要辛苦你帮忙补充一个介绍文档。可以参考官网文档进行添加，包括中英文两个文件。感谢你的支持！
官网：https://www.cloudwego.io/zh/docs/kitex/tutorials/service-governance/loadbalance/

NX-Official requested review from a team as code owners December 10, 2023 09:32

NX-Official changed the title ~~feat(lb): add loadbalancer using alias method (#1184)~~ feat(lb): add loadbalancer using Alias Method (#1184) Dec 10, 2023

jizhuozhi reviewed Dec 11, 2023

View reviewed changes

pkg/loadbalance/weighted_random_with_alias_method.go Outdated Show resolved Hide resolved

ppzqh reviewed Dec 13, 2023

View reviewed changes

pkg/loadbalance/weighted_random_with_alias_method.go Outdated Show resolved Hide resolved

ppzqh previously approved these changes Dec 19, 2023

View reviewed changes

NX-Official dismissed ppzqh’s stale review via a557280 December 19, 2023 06:49

AsterDY reviewed Dec 20, 2023

View reviewed changes

pkg/loadbalance/weighted_random_with_alias_method_test.go Outdated Show resolved Hide resolved

ppzqh previously approved these changes Jan 8, 2024

View reviewed changes

NX-Official added 9 commits January 9, 2024 13:49

feat(lb): add loadbalancer using alias method (cloudwego#1184)

b15d1c7

feat(lb): add loadbalancer using alias method (cloudwego#1184)

073b2ca

feat(lb): add loadbalancer using alias method (cloudwego#1184)

00c11e2

feat(lb): add loadbalancer using alias method (cloudwego#1184)

6f8a815

feat(lb): add loadbalancer using alias method (cloudwego#1184)

19a2ca7

feat(lb): add loadbalancer using alias method (cloudwego#1184)

8a6bd2d

feat(lb): add loadbalancer using alias method (cloudwego#1184)

f4eceb9

feat(lb): add loadbalancer using alias method (cloudwego#1184)

983f786

feat(lb): add loadbalancer using alias method (cloudwego#1184)

037d37e

NX-Official force-pushed the feat/loadblance branch from 834c15a to 037d37e Compare January 9, 2024 05:49

chore: remove redundant test file

b2ff131

NX-Official dismissed ppzqh’s stale review via b2ff131 January 9, 2024 06:06

ppzqh approved these changes Jan 18, 2024

View reviewed changes

NX-Official requested a review from jizhuozhi January 20, 2024 07:25

jizhuozhi approved these changes Jan 22, 2024

View reviewed changes

AsterDY approved these changes Jan 23, 2024

View reviewed changes

ppzqh merged commit 37fc52b into cloudwego:develop Jan 23, 2024

jizhuozhi mentioned this pull request Jan 29, 2024

Provides an O(1) weighted random algorithm implementation #1184

Closed

YangruiEmma changed the title ~~feat(lb): add loadbalancer using Alias Method (#1184)~~ feat(loadbalance): add loadbalancer using Alias Method (#1184) Mar 4, 2024

YangruiEmma changed the title ~~feat(loadbalance): add loadbalancer using Alias Method (#1184)~~ feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms Mar 4, 2024

This was referenced Mar 4, 2024

Add interleaved weighted round-robin and alias-method loadbalancer apache/dubbo-go#2606

Merged

fix: change runtime.fastrand to runtime.cheaprand in go 1.22 bytedance/gopkg#206

Merged

NX-Official mentioned this pull request Mar 14, 2024

docs(lb): Add description of Alias Method cloudwego/cloudwego.github.io#1034

Merged

2 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms #1199

feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms #1199

Uh oh!

NX-Official commented Dec 10, 2023 •

edited by YangruiEmma

Loading

Uh oh!

CLAassistant commented Dec 10, 2023 •

edited

Loading

Uh oh!

codecov bot commented Dec 11, 2023 •

edited

Loading

Uh oh!

ppzqh commented Dec 11, 2023

Uh oh!

Uh oh!

Uh oh!

ppzqh commented Dec 13, 2023

Uh oh!

NX-Official commented Dec 19, 2023

Uh oh!

ppzqh commented Dec 19, 2023

Uh oh!

Uh oh!

NX-Official commented Jan 7, 2024

Uh oh!

ppzqh commented Jan 8, 2024

Uh oh!

NX-Official commented Jan 8, 2024

Uh oh!

AsterDY commented Jan 8, 2024

Uh oh!

ppzqh commented Jan 8, 2024

Uh oh!

jizhuozhi left a comment

Uh oh!

ppzqh commented Mar 11, 2024

Uh oh!

Uh oh!

feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms #1199

feat(loadbalance): add loadbalancer using Alias Method to reduce the time complexity of weighted random load balancing algorithms #1199

Uh oh!

Conversation

NX-Official commented Dec 10, 2023 • edited by YangruiEmma Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What type of PR is this?

Check the PR title.

(Optional) Translate the PR title into Chinese.

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

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

(optional) The PR that updates user documentation:

Uh oh!

CLAassistant commented Dec 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov bot commented Dec 11, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

ppzqh commented Dec 11, 2023

Uh oh!

Uh oh!

Uh oh!

ppzqh commented Dec 13, 2023

Uh oh!

NX-Official commented Dec 19, 2023

Uh oh!

ppzqh commented Dec 19, 2023

Uh oh!

Uh oh!

NX-Official commented Jan 7, 2024

Uh oh!

ppzqh commented Jan 8, 2024

Uh oh!

NX-Official commented Jan 8, 2024

Uh oh!

AsterDY commented Jan 8, 2024

Uh oh!

ppzqh commented Jan 8, 2024

Uh oh!

jizhuozhi left a comment

Choose a reason for hiding this comment

Uh oh!

ppzqh commented Mar 11, 2024

Uh oh!

Uh oh!

NX-Official commented Dec 10, 2023 •

edited by YangruiEmma

Loading

CLAassistant commented Dec 10, 2023 •

edited

Loading

codecov bot commented Dec 11, 2023 •

edited

Loading