README
¶
go-loadbalancer
Fast and robust load balancers for Go.
Features
- General pourpose load balancers
- Support various algorithms
- Stable and safe
- Fast
Supported algorithms:
- Weight: the algorithm supports weighted targets
- Health: the algorithm consider targets' active/inactive status
- Hash-based: the algorithm is hash-based
| Algorithm | Weight | Health | Hash-based | Consistent hash | Complexity |
|---|---|---|---|---|---|
| Priority | Yes | Yes | No | -- | O(n) |
| Random | No | Yes | No | -- | O(1) |
| WeightedRandom | Yes | Yes | No | -- | O(n) |
| BasicRoundRobin | Yes | Yes | No | -- | O(1) |
| RoundRobin | Yes | Yes | No | -- | O(n) |
| RendezvousHash | Yes | Yes | Yes | Yes | O(n) |
| JumpHash | No | Yes | Yes | Yes | O(1) |
| DirectHash | Yes | Yes | Yes | No | O(1) |
| WeightedDirectHash | Yes | Yes | Yes | No | O(n) |
| RingHash | Yes | Yes | Yes | Yes | O(log(n)) |
| Maglev | Yes | Yes | Yes | Yes | O(1) |
Priority: priority based, or weight based load balancer.Random: random load balancer.RandomW: weighted random load balancer.BasicRoundRobin: basic round robin load balancer.RoundRobin: smooth round robin load balancer.RendezvousHash: rendezvous hash load balancer.JumpHash: jump hash load balancer.DirectHash: direct hash load balancer.DirectHashW: weighted direct hash load balancer.RingHash: ring hash load balancer.Maglev: maglev hash load balancer.
Usages
Basic usage
RoundRobin is used here. Other load balancers can be used in the same way.
See also examples/roundrobin/.
// Create targets.
t1 := examples.NewTarget(1, 1, true) // id:1, weight:1, active:true
t2 := examples.NewTarget(2, 2, true) // id:2, weight:2, active:true
t3 := examples.NewTarget(3, 2, true) // id:3, weight:2, active:true
// Create new RoundRobin loadbalancer with targets.
lb := loadbalancer.NewRoundRobin(t1, t2)
// Add new target.
lb.Add(t3)
// Remove target with id.
lb.Remove(t3.ID())
// Get target.
target, found := lb.Get(0) // Arg 0 is not used in roundrobin.
Loadbalancer for http proxy
We use RoundRobin here. Other load balancers can be used in the same way.
See also examples/roundrobin-proxy/.
t1 := examples.NewProxyTarget(1, 1, true, "http://localhost:8081") // id:1, weight:1, active:true
t2 := examples.NewProxyTarget(2, 2, true, "http://localhost:8082") // id:2, weight:2, active:true
t3 := examples.NewProxyTarget(3, 2, true, "http://localhost:8083") // id:3, weight:2, active:true
t4 := examples.NewProxyTarget(4, 0, true, "http://localhost:8084") // 0 weight
t5 := examples.NewProxyTarget(5, 1, false, "http://localhost:8085") // inactive
// Create new loadbalancer with targets.
lb := loadbalancer.NewRoundRobin(t1, t2, t3, t4, t5)
// Create proxy.
proxy := &httputil.ReverseProxy{
Rewrite: func(r *httputil.ProxyRequest) {
t, found := lb.Get(0) // Get next target.
if !found {
log.Println("proxy target not found")
panic(http.ErrAbortHandler)
}
u := r.In.URL.Clone()
u.Scheme = t.URL().Scheme
u.Host = t.URL().Host
r.SetURL(u)
log.Println("proxy to", t.String(), u.Host)
},
}
// Run the proxy.
err := http.ListenAndServe(":8080", proxy)
if err != nil && err != http.ErrServerClosed {
panic(err)
}
Docs & Examples
- GoDoc: https://pkg.go.dev/github.com/aileron-projects/go-loadbalancer
- Examples:
- example_test.go
- Priority loadbalancer:
- Random loadbalancer:
- Weighted Random loadbalancer:
- Basic RoundRobin loadbalancer:
- RoundRobin loadbalancer:
- RendezvousHash loadbalancer:
- JumpHash loadbalancer:
- DirectHash loadbalancer:
- Weighted DirectHash loadbalancer:
- RingHash loadbalancer:
- Maglev loadbalancer:
Benchmarks
See benchmark_test.go.
100 targets:
BenchmarkPriority-8 2568870 636.20 ns/op 0 B/op 0 allocs/op
BenchmarkRandom-8 49832438 30.25 ns/op 0 B/op 0 allocs/op
BenchmarkRandomW-8 312236 3655.00 ns/op 0 B/op 0 allocs/op
BenchmarkBasicRoundRobin-8 35078384 39.40 ns/op 0 B/op 0 allocs/op
BenchmarkRoundRobin-8 2222901 510.10 ns/op 0 B/op 0 allocs/op
BenchmarkRendezvousHash-8 687146 1901.00 ns/op 0 B/op 0 allocs/op
BenchmarkJumpHash-8 22861758 54.64 ns/op 0 B/op 0 allocs/op
BenchmarkDirectHash-8 72653737 20.35 ns/op 0 B/op 0 allocs/op
BenchmarkDirectHashW-8 722329 1823.00 ns/op 0 B/op 0 allocs/op
BenchmarkRingHash-8 20953122 69.38 ns/op 0 B/op 0 allocs/op
BenchmarkMaglev-8 71862310 18.04 ns/op 0 B/op 0 allocs/op
10,000 targets:
BenchmarkPriority-8 16574 74330.00 ns/op 0 B/op 0 allocs/op
BenchmarkRandom-8 23409380 47.17 ns/op 0 B/op 0 allocs/op
BenchmarkRandomW-8 4220 272044.00 ns/op 0 B/op 0 allocs/op
BenchmarkBasicRoundRobin-8 35659839 34.21 ns/op 0 B/op 0 allocs/op
BenchmarkRoundRobin-8 27069 44584.00 ns/op 0 B/op 0 allocs/op
BenchmarkRendezvousHash-8 7923 183715.00 ns/op 0 B/op 0 allocs/op
BenchmarkJumpHash-8 16162225 84.00 ns/op 0 B/op 0 allocs/op
BenchmarkDirectHash-8 57095277 20.78 ns/op 0 B/op 0 allocs/op
BenchmarkDirectHashW-8 6546 161088.00 ns/op 0 B/op 0 allocs/op
BenchmarkRingHash-8 9070880 133.00 ns/op 0 B/op 0 allocs/op
BenchmarkMaglev-8 56946526 21.97 ns/op 0 B/op 0 allocs/op
References
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BasicRoundRobin ¶
type BasicRoundRobin[T Target] struct { // contains filtered or unexported fields }
BasicRoundRobin is the load balancer that uses basic round-robin algorithm. The load balancer considers both active status and weight. Target weights and their orders are respected. For n targets, computational complexity is O(1).
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
States:
index = Current target index
weight = Remaining weight of the current target
function Get():
for range {T0 ... Tn-1}:
if weight == 0:
index <-- index+1 (Reset to 0 when n)
weight <-- W[index]
weight <-- weight-1
return T[index]
return nil
Visit each targets consuming their weights.
┌-----------------------------------------------------┐
↓ |
-------→ -------→ -------→ -------→ -------→ -------→↑
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewBasicRoundRobin(t0, t1, t2, t3, t4)
count := map[string]int{}
for range 1200 {
target, found := lb.Get(0)
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:200 t2:400 t3:600 total:1200]
func NewBasicRoundRobin ¶
func NewBasicRoundRobin[T Target](targets ...T) *BasicRoundRobin[T]
NewBasicRoundRobin returns a new instance of basic round-robin load balancer with given targets. See BasicRoundRobin.
func (*BasicRoundRobin[T]) Get ¶
func (lb *BasicRoundRobin[T]) Get(_ uint64) (t T, found bool)
Get returns a target.
func (*BasicRoundRobin[T]) Remove ¶
func (lb *BasicRoundRobin[T]) Remove(id uint64)
Remove removes targets with the given id.
func (*BasicRoundRobin[T]) Targets ¶
func (lb *BasicRoundRobin[T]) Targets() []T
Targets returns registered targets.
type DirectHash ¶
type DirectHash[T Target] struct { // contains filtered or unexported fields }
DirectHash is a load balancer that uses a direct-hash algorithm. For n targets, the computational complexity is O(1). However, it attempts up to MaxRetry+1 times to find an active target with non-zero weight. Note that the load balancer may return false even if active targets with non-zero weight exist. A weighted variant of the direct-hash load balancer is available via NewDirectHashW.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get(key):
for range {0 ... MaxRetry}:
key <-- SplitMix64(key)
index <-- key % n
if T[index] is not active:
continue
if W[index] == 0:
continue
return T[index]
return nil
Select SplitMix64(key)%n.
Retry if active=false or weight=0.
↓
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewDirectHash(t0, t1, t2, t3, t4)
lb.WithMaxRetry(1)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1 // Total won't be 1200.
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:329 t2:319 t3:351 total:999]
func NewDirectHash ¶
func NewDirectHash[T Target](targets ...T) *DirectHash[T]
NewDirectHash returns a new instance of direct hash load balancer. Targets can be added or removed after instantiation. See the comments on DirectHash.
func (*DirectHash[T]) Get ¶
func (lb *DirectHash[T]) Get(key uint64) (t T, found bool)
Get returns a target.
func (*DirectHash[T]) Remove ¶
func (lb *DirectHash[T]) Remove(id uint64)
Remove removes targets with the given id.
func (*DirectHash[T]) Targets ¶
func (lb *DirectHash[T]) Targets() []T
Targets returns registered targets.
func (*DirectHash[T]) WithMaxRetry ¶
func (lb *DirectHash[T]) WithMaxRetry(i int)
WithMaxRetry specifies maximum retry count. The load balancer returns first found target with active and non-zero weight. If zero or negative, no retries are applied.
type DirectHashW ¶
type DirectHashW[T Target] struct { // contains filtered or unexported fields }
DirectHashW is a load balancer that uses a weighted direct-hash algorithm. For n targets, computational complexity is O(n). Non-weighted direct-hash load balancer is available with NewDirectHash.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get(key):
maxScore <-- 0
target <-- nil
for i range {T0 ... Tn-1}:
key <-- SplitMix64(key)
score <-- Wi / -log( key/MaxUint64 )
if score > maxScore:
maxScore <-- score
target <-- Ti
return target
Select the target with max score.
↓
Calculate scores -------→ -------→ -------→ -------→ -------→ -------→
Score S[i] │ 1.25 │ 3.92 │ -- │ -- │ 2.04 │ .... │ 1.95 │
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
- https://en.wikipedia.org/wiki/Reservoir_sampling
- https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewDirectHashW(t0, t1, t2, t3, t4)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:199 t2:384 t3:617 total:1200]
func NewDirectHashW ¶
func NewDirectHashW[T Target](targets ...T) *DirectHashW[T]
NewDirectHashW returns a new instance of weighted direct hash load balancer. Targets can be added or removed after instantiation. See the comments on DirectHashW.
func (*DirectHashW[T]) Get ¶
func (lb *DirectHashW[T]) Get(key uint64) (t T, found bool)
Get returns a target.
func (*DirectHashW[T]) Remove ¶
func (lb *DirectHashW[T]) Remove(id uint64)
Remove removes targets with the given id.
func (*DirectHashW[T]) Targets ¶
func (lb *DirectHashW[T]) Targets() []T
Targets returns registered targets.
type JumpHash ¶
type JumpHash[T Target] struct { // contains filtered or unexported fields }
JumpHash is the load balancer that uses jump hash algorithm. For n targets, computational complexity is O(1). However, it attempts up to MaxRetry+1 times to find an active target with non-zero weight. Note that the load balancer may return false even if active targets with non-zero weight exist.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get(key):
for range {0 ... MaxRetry}:
key <-- SplitMix64(key)
index <-- JumpHash(key, n)
if T[index] is not active:
continue
if W[index] == 0:
continue
return T[index]
return nil
Select JumpHash(key, n).
Retry if active=false or weight=0.
↓
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
- https://arxiv.org/abs/1406.2294
- https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf
- https://en.wikipedia.org/wiki/Consistent_hashing
Example ¶
t0 := &MocTarget{name: "t0", id: 123, weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", id: 456, weight: 1, active: true}
t2 := &MocTarget{name: "t2", id: 789, weight: 2, active: true}
t3 := &MocTarget{name: "t3", id: 123, weight: 3, active: true}
t4 := &MocTarget{name: "t4", id: 926, weight: 4, active: false} // Non-active
lb := loadbalancer.NewJumpHash(t0, t1, t2, t3, t4)
lb.WithMaxRetry(1)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1 // Total won't be 1200.
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:324 t2:359 t3:326 total:1009]
func NewJumpHash ¶
NewJumpHash returns a new instance of jump hash load balancer. Targets can be added or removed after instantiation. See the comments on JumpHash.
func (*JumpHash[T]) Targets ¶
func (lb *JumpHash[T]) Targets() []T
Targets returns registered targets.
func (*JumpHash[T]) WithMaxRetry ¶
WithMaxRetry specifies maximum retry count. The load balancer returns first found target with active and non-zero weight. If zero or negative, no retries are applied.
type LoadBalancer ¶
type LoadBalancer[T Target] interface { // Targets returns all registered targets. // Targets is safe for concurrent call. Targets() (targets []T) // Add adds targets to the load balancer. // Add is safe for concurrent call. Add(targets ...T) // Remove removes targets with given id. // Remove is safe for concurrent call. Remove(id uint64) // Get returns a target. // hint should be given if the loadbalancer requires it. // Get is safe to concurrent call. Get(hint uint64) (t T, found bool) }
LoadBalancer is the interface of load balancers.
type Maglev ¶
type Maglev[T Target] struct { // contains filtered or unexported fields }
Maglev is a load balancer that uses the Maglev hashing algorithm. For n targets, lookup complexity is O(1). However, it may try up to MaxRetry+1 times to find an active, non-zero-weight target.
Note: The load balancer may return false even when active and non-zero-weight targets exist.
Target weights are evaluated only when the lookup table is rebuilt, and cannot be updated dynamically. Inactive targets are excluded from the table during reconstruction.
Algorithm:
- See references for the original Maglev hashing design.
References:
- https://research.google/pubs/maglev-a-fast-and-reliable-software-network-load-balancer/
- https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_slides_eisenbud.pdf
Example ¶
t0 := &MocTarget{name: "t0", id: 123, weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", id: 456, weight: 1, active: true}
t2 := &MocTarget{name: "t2", id: 789, weight: 2, active: true}
t3 := &MocTarget{name: "t3", id: 123, weight: 3, active: true}
t4 := &MocTarget{name: "t4", id: 926, weight: 4, active: false} // Non-active
lb := loadbalancer.NewMaglev(t0, t1, t2, t3, t4)
lb.WithMinimumTableSize(111)
lb.WithMaxRetry(1)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:209 t2:410 t3:581 total:1200]
func NewMaglev ¶
NewMaglev returns a new instance of maglev hash load balancer. Targets can be added or removed after instantiation. See the comments on Maglev.
func (*Maglev[T]) Remove ¶
Remove removes targets with the given id. lb.Update is internally called after removing the target.
func (*Maglev[T]) WithMaxRetry ¶
WithMaxRetry specifies maximum retry count. The load balancer returns first found target with active and non-zero weight. If zero or negative, no retries are applied.
func (*Maglev[T]) WithMinimumTableSize ¶
WithMinimumTableSize specifies minimum lookup table size. The actual lookup table size wil be adjusted based on the target weights.
type Priority ¶
type Priority[T Target] struct { // contains filtered or unexported fields }
Priority is a load balancer that uses a priority-based algorithm. It is very simple algorithm that select a target with maximum priority, or maximum weight. The load balancer considers both active status and weight of targets. For n targets, computational complexity is O(n). Note that the actual algorithm is improved to load balance the targets with same weights which is the maximimum among targets using round-robin.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get():
maxWeight <-- 0
index <-- -1
for i range {T0 ... Tn-1}:
if CWi > maxWeight:
maxWeight <-- CWi
index <-- i
return T[index]
Select the target with max weight.
First found one is selected if same weight targets exist.
↓
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewPriority(t0, t1, t2, t3, t4)
count := map[string]int{}
for range 100 {
target, found := lb.Get(0)
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t3:100 total:100]
func NewPriority ¶
NewPriority returns a new instance of priority-based load balancer. Targets can be added or removed after instantiation. See the comments on Priority.
type Random ¶
type Random[T Target] struct { // contains filtered or unexported fields }
Random is the load balancer that uses random algorithm. For n targets, computational complexity is O(1). But it tries MaxRetry+1 times at most until it finds an active and non-zero weight target. Note that the load balancer may return false even active and non-zero weight targets are exist. Weighted random load balancer is available with NewRandomW.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get(_):
for i range {0 ... MaxRetry}:
index <-- random(0, n)
if T[index] is not active:
continue
if W[index] == 0:
continue
return T[index]
return nil
Select random()%n.
Retry if active=false or weight=0.
↓
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewRandom(t0, t1, t2, t3, t4)
lb.WithMaxRetry(1)
count := map[string]int{}
for range 1200 {
target, found := lb.Get(0)
if found {
count["total"] += 1 // Total won't be 1200.
count[target.name] += 1
}
}
fmt.Println(count)
func NewRandom ¶
NewRandom returns a new instance of random load balancer. Targets can be added or removed after instantiation. See the comments on Random.
func (*Random[T]) WithMaxRetry ¶
WithMaxRetry specifies maximum retry count. The load balancer returns first found target with active and non-zero weight. If zero or negative, no retries are applied.
type RandomW ¶
type RandomW[T Target] struct { // contains filtered or unexported fields }
RandomW is the load balancer that uses weighted random algorithm. The load balancer considers both active status and weight of targets. For n targets, computational complexity is O(n). Non-weighted random load balancer is available with NewRandom.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
function Get(_):
maxScore <-- 0
target <-- nil
for i range {T0 ... Tn-1}:
score <-- Wi / -log( random() )
if score > maxScore:
maxScore <-- score
target <-- Ti
return target
Select the target with max score.
↓
Calculate score -------→ -------→ -------→ -------→ -------→ -------→
Score S[i] │ 1.25 │ 3.92 │ -- │ -- │ 2.04 │ .... │ 1.95 │
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
- https://en.wikipedia.org/wiki/Reservoir_sampling
- https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewRandomW(t0, t1, t2, t3, t4)
count := map[string]int{}
for range 1200 {
target, found := lb.Get(0)
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
func NewRandomW ¶
NewRandomW returns a new instance of weighted random load balancer. Targets can be added or removed after instantiation. See the comments on RandomW.
type RendezvousHash ¶
type RendezvousHash[T Target] struct { // contains filtered or unexported fields }
RendezvousHash is a load balancer that use rendezvous-hash algorithm. Rendezvous Hashing also known as Highest Random Weight (HRW). The load balancer considers both active status and weight of targets. For n targets, computational complexity is O(n).
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
IDi = T[i].ID() = identifier of T[i]
function Get(key):
maxScore <-- 0
target <-- nil
for i range {T0 ... Tn-1}:
score <-- Wi / -log( Hash(key*IDi) / MaxUint64 )
if score > maxScore:
maxScore <-- score
target <-- Ti
return target
Select the target with max score.
↓
Calculate score -------→ -------→ -------→ -------→ -------→ -------→
Score S[i] │ 1.25 │ 3.92 │ -- │ -- │ 2.04 │ .... │ 1.95 │
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
- https://en.wikipedia.org/wiki/Rendezvous_hashing
- https://en.wikipedia.org/wiki/Consistent_hashing
- https://en.wikipedia.org/wiki/Reservoir_sampling
- https://www.ietf.org/archive/id/draft-ietf-bess-weighted-hrw-00.html
- https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
- Weighted Random Sampling (2005; Efraimidis, Spirakis)
- Using Name-Based Mappings to Increase Hit Rates
- -> https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/HRW98.pdf
Example ¶
t0 := &MocTarget{name: "t0", id: 123, weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", id: 456, weight: 1, active: true}
t2 := &MocTarget{name: "t2", id: 789, weight: 2, active: true}
t3 := &MocTarget{name: "t3", id: 321, weight: 3, active: true}
t4 := &MocTarget{name: "t4", id: 654, weight: 4, active: false} // Non-active
lb := loadbalancer.NewRendezvousHash(t0, t1, t2, t3, t4)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:201 t2:387 t3:612 total:1200]
func NewRendezvousHash ¶
func NewRendezvousHash[T Target](targets ...T) *RendezvousHash[T]
NewRendezvousHash returns a new instance of rendezvous hash load balancer. Targets can be added or removed after instantiation. See the comments on RendezvousHash.
func (*RendezvousHash[T]) Get ¶
func (lb *RendezvousHash[T]) Get(key uint64) (t T, found bool)
Get returns a target.
func (*RendezvousHash[T]) Remove ¶
func (lb *RendezvousHash[T]) Remove(id uint64)
Remove removes targets with the given id.
func (*RendezvousHash[T]) Targets ¶
func (lb *RendezvousHash[T]) Targets() []T
Targets returns registered targets.
type RingHash ¶
type RingHash[T Target] struct { // contains filtered or unexported fields }
RingHash is a load balancer that uses a ring-hash algorithm. For n targets, computational complexity is O(log(n)). This complexity is derived from the binary search used in the algorithm. Note that the load balancer may return false even active and non-zero weight targets are exist. The internal virtual ring is updated when [RingHash.Update] is called. Target weights are evaluated at the time of updating the virtual ring and cannot be updated dynamically.
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
Ri = R[i] = Ring[i] // Ring[i] maps to Target[j].
function Get(key):
key <-- SplitMix64(key)
index <-- BinarySearch(key, Ring[i])
for range {0 ... MaxTry}:
if R[index] is not active:
index <-- index+1
continue
if R[index] == 0:
index <-- index+1
continue
return R[index]
return nil
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=20 │ W1=30 │ W2=0 │ W3=10 │ W4=10 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
A concept of virtual ring.
Targets are mapped on the ring with size MaxUint64 based on their hash value.
Start index determined by binary search.
↓---→ ---→ ---→ ---→ ---→
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ T1 │ T9 │ T3 │ T0 │ T1 │ T8 │ T7 │ T5 │ T6 │ T4 │....│ T5 │
├────┼────┴────┴────┴────┴────┴────┴────┴────┴────┴────┼────┤
│ T5 │ │ T0 │
├────┤ ├────┤
│ T6 │ │ T8 │
├────┤ ├────┤
│ T9 │ │ T4 │
├────┤ ├────┤
│ T3 │ │ T1 │
├────┼────┬────┬────┬────┬────┬────┬────┬────┬────┬────┼────┤
│ T1 │....│ T0 │ T7 │ T4 │ T8 │ T1 │ T5 │ T8 │ T1 │ T7 │ T9 │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
Example ¶
t0 := &MocTarget{name: "t0", id: 123, weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", id: 456, weight: 10, active: true}
t2 := &MocTarget{name: "t2", id: 789, weight: 20, active: true}
t3 := &MocTarget{name: "t3", id: 123, weight: 30, active: true}
t4 := &MocTarget{name: "t4", id: 926, weight: 40, active: false} // Non-active
lb := loadbalancer.NewRingHash(t0, t1, t2, t3, t4)
count := map[string]int{}
for i := range 1200 {
target, found := lb.Get(uint64(i+1) * 0x9e3779b97f4a7c15) // Give a very simple hash.
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:171 t2:442 t3:587 total:1200]
func NewRingHash ¶
NewRingHash returns a new instance of ring hash load balancer. Targets can be added or removed after instantiation. See the comments on RingHash.
type RoundRobin ¶
type RoundRobin[T Target] struct { // contains filtered or unexported fields }
RoundRobin is the load balancer that uses smooth round-robin algorithm. The load balancer considers both active status and weight. For n targets, computational complexity is O(n).
Algorithm:
Ti = T[i] = Target[i]
Wi = W[i] = Weight[i]
States:
CWi = CW[i] = Current weight of T[i]
function Get():
sumWeight <-- 0
maxWeight <-- 0
index <-- -1
for i range {T0 ... Tn-1}:
sumWeight <-- sumWeight + Wi
CWi <-- CWi + Wi
if CWi > maxWeight:
maxWeight <-- CWi
index <-- i
CW[index] = CW[index] - sumWeight
return T[index]
Select the target with max current weight.
↓
Calculate each -------→ -------→ -------→ -------→ -------→ -------→
CW[i] │ 4 │ 8 │ 0 │ 0 │ 2 │ .... │ 5 │
┌─────────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Target T[i] │ T0 │ T1 │ T2 │ T3 │ T4 │ .... │ Tn-1 │
│ Weight W[i] │ W0=2 │ W1=3 │ W2=0 │ W3=1 │ W4=1 │ .... │ Wn-1=2 │
│ Active │ true │ true │ true │ false │ true │ .... │ true │
└─────────────┴────────┴────────┴───┬────┴───┬────┴────────┴────────┴────────┘
│ │
│ └── Non-active target is ignored.
└─────────── Target with 0 weight is ignored.
References:
- https://en.wikipedia.org/wiki/Weighted_round_robin
- https://github.com/phusion/nginx/commit/27e94984486058d73157038f7950a0a36ecc6e35
- https://dubbo.apache.org/en/overview/what/core-features/load-balance/
Example ¶
t0 := &MocTarget{name: "t0", weight: 0, active: true} // 0 weight
t1 := &MocTarget{name: "t1", weight: 1, active: true}
t2 := &MocTarget{name: "t2", weight: 2, active: true}
t3 := &MocTarget{name: "t3", weight: 3, active: true}
t4 := &MocTarget{name: "t4", weight: 4, active: false} // Non-active
lb := loadbalancer.NewRoundRobin(t0, t1, t2, t3, t4)
count := map[string]int{}
for range 1200 {
target, found := lb.Get(0)
if found {
count["total"] += 1
count[target.name] += 1
}
}
fmt.Println(count)
Output: map[t1:200 t2:400 t3:600 total:1200]
func NewRoundRobin ¶
func NewRoundRobin[T Target](targets ...T) *RoundRobin[T]
NewRoundRobin returns a new instance of round-robin load balancer. Targets can be added or removed after instantiation. See the comments on RoundRobin.
func (*RoundRobin[T]) Get ¶
func (lb *RoundRobin[T]) Get(_ uint64) (t T, found bool)
Get returns a target.
func (*RoundRobin[T]) Targets ¶
func (lb *RoundRobin[T]) Targets() []T
Targets returns registered targets.
type Target ¶
type Target interface {
// ID returns the identifier of the target.
// Hash-based loadbalancers use the IDs.
// ID must be safe for concurrent call.
ID() uint64
// Active returns if the target is active or not.
// It depends on loadbalancers if the returned value is used or not.
// Active must be safe for concurrent call.
Active() bool
// Weight returns the target's weight, or priority.
// It depends on loadbalancers if the returned value is used or not.
// Weight must be safe for concurrent call.
Weight() uint16
}
Target is the interface for load balance targets.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
direct
command
|
|
|
direct-proxy
command
|
|
|
direct-weighted
command
|
|
|
direct-weighted-proxy
command
|
|
|
jump
command
|
|
|
jump-proxy
command
|
|
|
maglev
command
|
|
|
maglev-proxy
command
|
|
|
priority
command
|
|
|
priority-proxy
command
|
|
|
random
command
|
|
|
random-proxy
command
|
|
|
random-weighted
command
|
|
|
random-weighted-proxy
command
|
|
|
rendezvous
command
|
|
|
rendezvous-proxy
command
|
|
|
ring
command
|
|
|
ring-proxy
command
|
|
|
roundrobin
command
|
|
|
roundrobin-basic
command
|
|
|
roundrobin-basic-proxy
command
|
|
|
roundrobin-proxy
command
|