zlb

package
v0.0.0-alpha.17 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 16, 2025 License: Apache-2.0 Imports: 5 Imported by: 1

Documentation

Overview

Package zlb provides load balancers.

Provided algorithms: 

|                    | Consider | Consider | Hash-base | Consistent | Computation |
| Algorithm          |  weight  |  health  | algorithm |    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)     |

See the comments:

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 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.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]

BasicRoundRobin returns a new instance of basic round robin load balancer. Targets can be added or removed after instantiation. See the comments on BasicRoundRobin.

func (*BasicRoundRobin[T]) Add 

func (lb *BasicRoundRobin[T]) Add(targets ...T)

Add adds targets.

func (*BasicRoundRobin[T]) Get 

func (lb *BasicRoundRobin[T]) Get(_ uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (*BasicRoundRobin[T]) Remove 

func (lb *BasicRoundRobin[T]) Remove(id uint64)

Remove removes targets.

func (*BasicRoundRobin[T]) Targets 

func (lb *BasicRoundRobin[T]) Targets() []T

Targets returns registered targets.

type DirectHash 

type DirectHash[T Target] struct {

	// MaxRetry is the maximum retry count.
	// If zero, no retries are applied.
	// The load balancer returns first found target
	// with active and non-zero weight.
	MaxRetry int
	// 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 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.NewDirectHash(t0, t1, t2, t3, t4)
	lb.MaxRetry = 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) Add 

func (lb DirectHash) Add(targets ...T)

Add adds targets.

func (*DirectHash[T]) Get 

func (lb *DirectHash[T]) Get(key uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (DirectHash) Remove 

func (lb DirectHash) Remove(id uint64)

Remove removes targets.

func (DirectHash) Targets 

func (lb DirectHash) Targets() []T

Targets returns registered targets.

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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.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) Add 

func (lb DirectHashW) Add(targets ...T)

Add adds targets.

func (*DirectHashW[T]) Get 

func (lb *DirectHashW[T]) Get(key uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (DirectHashW) Remove 

func (lb DirectHashW) Remove(id uint64)

Remove removes targets.

func (DirectHashW) Targets 

func (lb DirectHashW) Targets() []T

Targets returns registered targets.

type JumpHash 

type JumpHash[T Target] struct {

	// MaxRetry is the maximum retry count.
	// If zero, no retries are applied.
	// The load balancer returns first found target
	// with active and non-zero weight.
	MaxRetry int
	// 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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", id: 123, weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", id: 456, weight: 1, active: true}
	t2 := &Target{name: "t2", id: 789, weight: 2, active: true}
	t3 := &Target{name: "t3", id: 123, weight: 3, active: true}
	t4 := &Target{name: "t4", id: 926, weight: 4, active: false} // Non-active
	lb := zlb.NewJumpHash(t0, t1, t2, t3, t4)
	lb.MaxRetry = 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 

func NewJumpHash[T Target](targets ...T) *JumpHash[T]

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) Add 

func (lb JumpHash) Add(targets ...T)

Add adds targets.

func (*JumpHash[T]) Get 

func (lb *JumpHash[T]) Get(key uint64) (t T, found bool)

func (JumpHash) Remove 

func (lb JumpHash) Remove(id uint64)

Remove removes targets.

func (JumpHash) Targets 

func (lb JumpHash) Targets() []T

Targets returns registered targets.

type LoadBalancer 

type LoadBalancer[T Target] interface {
	// Targets returns all registered targets.
	// It is safe for concurrent call.
	Targets() (targets []T)
	// Add adds targets to the load balancer.
	// It may change the internal state.
	// It is safe for concurrent call.
	Add(targets ...T)
	// Remove removes targets with the given id.
	// It may change the internal state.
	// It is safe for concurrent call.
	Remove(id uint64)
	// Get returns a next target.
	// Get is safe to concurrent call.
	Get(hint uint64) (t T, found bool)
}

LoadBalancer is the load balancer interface.

type Maglev 

type Maglev[T Target] struct {

	// MaxRetry is the maximum retry count.
	// If zero, no retries are applied.
	// The load balancer returns first found target
	// with active and non-zero weight.
	MaxRetry int
	// Size is the lookup table size.
	// The actual lookup table size wil be adjusted
	// based on the target weights.
	Size int
	// 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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", id: 123, weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", id: 456, weight: 1, active: true}
	t2 := &Target{name: "t2", id: 789, weight: 2, active: true}
	t3 := &Target{name: "t3", id: 123, weight: 3, active: true}
	t4 := &Target{name: "t4", id: 926, weight: 4, active: false} // Non-active
	lb := zlb.NewMaglev(t0, t1, t2, t3, t4)
	lb.MaxRetry = 1
	lb.Size = 111 // Prime number grater than sum(weight). It's good to choose near N*sum(weight).
	lb.Update()   // Update table.

	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 

func NewMaglev[T Target](targets ...T) *Maglev[T]

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) Add 

func (lb Maglev) Add(targets ...T)

Add adds targets.

func (*Maglev[T]) Get 

func (lb *Maglev[T]) Get(key uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (*Maglev[T]) Remove 

func (lb *Maglev[T]) Remove(id uint64)

Remove removes target. lb.Update is internally called after removing the target.

func (Maglev) Targets 

func (lb Maglev) Targets() []T

Targets returns registered targets.

func (*Maglev[T]) Update 

func (lb *Maglev[T]) Update()

Update update lookup table.

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).

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 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.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 

func NewPriority[T Target](targets ...T) *Priority[T]

NewPriority returns a new instance of priority-based load balancer. Targets can be added or removed after instantiation. See the comments on Priority.

func (Priority) Add 

func (lb Priority) Add(targets ...T)

Add adds targets.

func (*Priority[T]) Get 

func (lb *Priority[T]) Get(_ uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (Priority) Remove 

func (lb Priority) Remove(id uint64)

Remove removes targets.

func (Priority) Targets 

func (lb Priority) Targets() []T

Targets returns registered targets.

type Random 

type Random[T Target] struct {
	MaxRetry int
	// 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 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.NewRandom(t0, t1, t2, t3, t4)
	lb.MaxRetry = 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 

func NewRandom[T Target](targets ...T) *Random[T]

NewRandom returns a new instance of random load balancer. Targets can be added or removed after instantiation. See the comments on Random.

func (Random) Add 

func (lb Random) Add(targets ...T)

Add adds targets.

func (*Random[T]) Get 

func (lb *Random[T]) Get(_ uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (Random) Remove 

func (lb Random) Remove(id uint64)

Remove removes targets.

func (Random) Targets 

func (lb Random) Targets() []T

Targets returns registered targets.

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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.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 

func NewRandomW[T Target](targets ...T) *RandomW[T]

NewRandomW returns a new instance of weighted random load balancer. Targets can be added or removed after instantiation. See the comments on RandomW.

func (RandomW) Add 

func (lb RandomW) Add(targets ...T)

Add adds targets.

func (*RandomW[T]) Get 

func (lb *RandomW[T]) Get(_ uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (RandomW) Remove 

func (lb RandomW) Remove(id uint64)

Remove removes targets.

func (RandomW) Targets 

func (lb RandomW) Targets() []T

Targets returns registered targets.

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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", id: 123, weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", id: 456, weight: 1, active: true}
	t2 := &Target{name: "t2", id: 789, weight: 2, active: true}
	t3 := &Target{name: "t3", id: 321, weight: 3, active: true}
	t4 := &Target{name: "t4", id: 654, weight: 4, active: false} // Non-active
	lb := zlb.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) Add 

func (lb RendezvousHash) Add(targets ...T)

Add adds targets.

func (*RendezvousHash[T]) Get 

func (lb *RendezvousHash[T]) Get(key uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (RendezvousHash) Remove 

func (lb RendezvousHash) Remove(id uint64)

Remove removes targets.

func (RendezvousHash) Targets 

func (lb RendezvousHash) 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 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", id: 123, weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", id: 456, weight: 10, active: true}
	t2 := &Target{name: "t2", id: 789, weight: 20, active: true}
	t3 := &Target{name: "t3", id: 123, weight: 30, active: true}
	t4 := &Target{name: "t4", id: 926, weight: 40, active: false} // Non-active
	lb := zlb.NewRingHash(t0, t1, t2, t3, t4)
	lb.Update()

	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 

func NewRingHash[T Target](targets ...T) *RingHash[T]

NewRingHash returns a new instance of ring hash load balancer. Targets can be added or removed after instantiation. See the comments on RingHash.

func (RingHash) Add 

func (lb RingHash) Add(targets ...T)

Add adds targets.

func (*RingHash[T]) Get 

func (lb *RingHash[T]) Get(key uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (*RingHash[T]) Remove 

func (lb *RingHash[T]) Remove(id uint64)

Remove removes target. lb.Update is internally called after removing the target.

func (RingHash) Targets 

func (lb RingHash) Targets() []T

Targets returns registered targets.

func (*RingHash[T]) Update 

func (lb *RingHash[T]) Update()

Update update lookup table.

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:

Example 
package main

import (
	"fmt"

	"github.com/aileron-projects/go/zx/zlb"
)

type Target struct {
	name   string
	id     uint64
	weight uint16
	active bool
}

func (t *Target) ID() uint64 {
	return t.id
}

func (t *Target) Weight() uint16 {
	return t.weight
}

func (t *Target) Active() bool {
	return t.active
}

func main() {
	t0 := &Target{name: "t0", weight: 0, active: true} // 0 weight
	t1 := &Target{name: "t1", weight: 1, active: true}
	t2 := &Target{name: "t2", weight: 2, active: true}
	t3 := &Target{name: "t3", weight: 3, active: true}
	t4 := &Target{name: "t4", weight: 4, active: false} // Non-active
	lb := zlb.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]) Add 

func (lb *RoundRobin[T]) Add(targets ...T)

Add adds targets.

func (*RoundRobin[T]) Get 

func (lb *RoundRobin[T]) Get(_ uint64) (t T, found bool)

Get returns a target. Returned value found is true when an active target was found.

func (*RoundRobin[T]) Remove 

func (lb *RoundRobin[T]) Remove(id uint64)

Remove removes targets.

func (*RoundRobin[T]) Targets 

func (lb *RoundRobin[T]) Targets() []T

Targets returns registered targets.

type Target 

type Target interface {
	// ID returns the identifier of this target.
	// It depends on implementation how the ID is used.
	// In some load balancers, IDs are used for calculating
	// hash value in their load balancing algorithms.
	// Therefore, IDs should be globally unique.
	// ID must be safe for concurrent call.
	ID() uint64
	// Active returns if this target is active or not.
	// It depends on implementation if the active status is used.
	// Some load balancing algorithms ignores the status.
	// Active must be safe for concurrent call.
	Active() bool
	// Weight returns the target weight, or priority.
	// It depends on implementation how the weight is used.
	// Some load balancing algorithms ignores the weight.
	// Weight must be safe for concurrent call.
	Weight() uint16
}

Target is the load balance target interface.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.