maglev

Documentation

Index

• Constants
• Variables
• type BackendInfo
• type Config
  • func (def Config) Flags(flags *pflag.FlagSet)
• type Maglev
  • func New(cfg Config, lc cell.Lifecycle) (*Maglev, error)
  • func (ml *Maglev) GetLookupTable(backends iter.Seq[BackendInfo]) []loadbalancer.BackendID
  • func (ml *Maglev) Start(cell.HookContext) error
  • func (ml *Maglev) Stop(cell.HookContext) error

Constants

const (
	DefaultTableSize = 16381

	// seed=$(head -c12 /dev/urandom | base64 -w0)
	DefaultHashSeed = "JLfvgnHc2kaSUFaI"

	MaglevTableSizeName = "bpf-lb-maglev-table-size"
	MaglevHashSeedName  = "bpf-lb-maglev-hash-seed"
)

Variables

var Cell = cell.Module(
	"maglev",
	"Maglev table computations",

	cell.Config(DefaultConfig),
	cell.Provide(New),
)

var DefaultConfig = Config{
	MaglevTableSize: DefaultTableSize,
	MaglevHashSeed:  DefaultHashSeed,
}

Types

type BackendInfo

type BackendInfo struct {
	ID     loadbalancer.BackendID
	Addr   loadbalancer.L3n4Addr
	Weight uint16
	// contains filtered or unexported fields
}

BackendInfo describes the backend information relevant for the maglev computation.

type Config

type Config struct {
	// Maglev backend table size (M) per service. Must be prime number.
	// "Let N be the size of a VIP's backend pool." [...] "In practice, we choose M to be
	// larger than 100 x N to ensure at most a 1% difference in hash space assigned to
	// backends." (from Maglev paper, page 6)
	MaglevTableSize uint `mapstructure:"bpf-lb-maglev-table-size"`

	// MaglevHashSeed contains the cluster-wide seed for the hash(es).
	MaglevHashSeed string `mapstructure:"bpf-lb-maglev-hash-seed"`
}

func (Config) Flags

func (def Config) Flags(flags *pflag.FlagSet)

type Maglev

type Maglev struct {
	Config
	SeedJhash0 uint32
	SeedJhash1 uint32
	// contains filtered or unexported fields
}

func New

func New(cfg Config, lc cell.Lifecycle) (*Maglev, error)

New constructs a new Maglev computation object.

func (*Maglev) GetLookupTable

func (ml *Maglev) GetLookupTable(backends iter.Seq[BackendInfo]) []loadbalancer.BackendID

GetLookupTable returns the Maglev lookup table for the given backends. The lookup table contains the IDs of the given backends.

Maglev algorithm might produce different lookup table for the same set of backends listed in a different order. To avoid that sort backends by the hash, as these are the same on all nodes (in opposite to backend IDs which are node-local).

The weights implementation is inspired by https://github.com/envoyproxy/envoy/pull/2982.

A backend weight is honored by altering the frequency how often a backend's turn is selected. A backend weight is multiplied in each turn by (n + 1) and compared to weightCntr[index] value which is an incrementation of weightSum (but starts at backend's weight / number of backends, so that each backend is selected at least once). If this is lower than weightCntr[index], another backend has a turn (and weightCntr[index] is incremented). This way we honor the weights.

func (*Maglev) Start

func (ml *Maglev) Start(cell.HookContext) error

func (*Maglev) Stop

func (ml *Maglev) Stop(cell.HookContext) error