Golang之 go实现基于离散概率分布算法负载均衡策略
背景
实现O(1) 加权随机算法, 基于离散概率分布中进行采样的有效算法，根据某个任意概率分布p i返回整数值1 ≤ i ≤ n。该算法通常使用O(nlogn)或O(n)预处理时间，之后可以在O(1)时间内从分布中抽取随机值。
算法说明
- 根据实例权重
weight除以 总的权重之和weightSum， 让其概率分布计算累积分布，映射到[0,1]的线段上； - 通过一个
[0,1]之间均匀分布的随机生成器，生成一个[0,1]之间的随机数； - 判断这个数落在
[0,1]线段上的哪个分段，平输出最接近这个值的实例
实现算法
// Package aliasmethod implements alias-method algorithm load balance strategy.
package aliasmethod // weighted random with alias-method algorithm
import (
"math/rand"
"dubbo.apache.org/dubbo-go/v3/cluster/loadbalance"
"dubbo.apache.org/dubbo-go/v3/protocol"
)
type aliasMethodPicker struct {
invokers []protocol.Invoker // Instance
weightSum int64
alias []int
prob []float64
}
func NewAliasMethodPicker(invokers []protocol.Invoker, invocation protocol.Invocation) *aliasMethodPicker {
am := &aliasMethodPicker{
invokers: invokers,
}
am.init(invocation)
return am
}
// Alias Method: https://en.wikipedia.org/wiki/Alias_method
func (am *aliasMethodPicker) init(invocation protocol.Invocation) {
n := len(am.invokers)
weights := make([]int64, n)
am.alias = make([]int, n)
am.prob = make([]float64, n)
totalWeight := int64(0)
scaledProb := make([]float64, n)
small := make([]int, 0, n)
large := make([]int, 0, n)
for i, invoker := range am.invokers {
weight := loadbalance.GetWeight(invoker, invocation)
weights[i] = weight
totalWeight += weight
}
am.weightSum = totalWeight
for i, weight := range weights {
scaledProb[i] = float64(weight) * float64(n) / float64(totalWeight)
if scaledProb[i] < 1.0 {
small = append(small, i)
} else {
large = append(large, i)
}
}
for len(small) > 0 && len(large) > 0 {
l := small[len(small)-1]
small = small[:len(small)-1]
g := large[len(large)-1]
large = large[:len(large)-1]
am.prob[l] = scaledProb[l]
am.alias[l] = g
scaledProb[g] -= 1.0 - scaledProb[l]
if scaledProb[g] < 1.0 {
small = append(small, g)
} else {
large = append(large, g)
}
}
for len(large) > 0 {
g := large[len(large)-1]
large = large[:len(large)-1]
am.prob[g] = 1.0
}
for len(small) > 0 {
l := small[len(small)-1]
small = small[:len(small)-1]
am.prob[l] = 1.0
}
}
func (am *aliasMethodPicker) Pick() protocol.Invoker {
i := rand.Intn(len(am.invokers))
if rand.Float64() < am.prob[i] {
return am.invokers[i]
}
return am.invokers[am.alias[i]]
}
性能
goos: darwin
goarch: amd64
pkg: dubbo.apache.org/dubbo-go/v3/cluster/loadbalance
cpu: VirtualApple @ 2.50GHz
BenchmarkRoudrobinLoadbalance-8 3814 284544 ns/op 88099 B/op 2555 allocs/op
BenchmarkLeastativeLoadbalance-8 4214 274662 ns/op 81884 B/op 2043 allocs/op
BenchmarkConsistenthashingLoadbalance-8 30619 39091 ns/op 3440 B/op 267 allocs/op
BenchmarkP2CLoadbalance-8 1508785 792.5 ns/op 472 B/op 10 allocs/op
BenchmarkInterleavedWeightedRoundRobinLoadbalance-8 10000 102737 ns/op 45312 B/op 1027 allocs/op
BenchmarkRandomLoadbalance-8 13738 87314 ns/op 38992 B/op 767 allocs/op
BenchmarkAliasMethodLoadbalance-8 13190 90566 ns/op 49232 B/op 772 allocs/op
PASS
ok dubbo.apache.org/dubbo-go/v3/cluster/loadbalance 12.402s
其他
「如果这篇文章对你有用,请随意打赏」
如果这篇文章对你有用,请随意打赏
使用微信扫描二维码完成支付
