maglev_hash

Documentation

Overview

Package maglevhash implements Maglev Hash algorithm from the paper [Maglev: A Fast and Reliable Software Network Load Balancer](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf) Maglev hash break down the key space to slots and assign slots to nodes. Each node is a logic entity that can handle the key. It could be a server, a service, a VIP, etc. Maglev hash guarantees the following two properties.

1. Load Balance. Let N be the number of nodes and M be the number of slots. The difference between any node's assigned slots is less than N/M. For example, if M = 100*N, then the node with most slots has no more than 1% slots than the node with the least slots.
2. Minimal disruption. On average, add a new node causes reassigns M/N slots.

Example mh, _ := NewMaglev([]string{"B0", "B1"}) node := mh.Node([]byte("key1"))

Index

• Constants
• type KeyHashFnType
• type MaglevHash
  • func NewMaglev(nodes []string) (*MaglevHash, error)
  • func NewMaglevWithTableSize(slotCnt int, nodes []string, keyHashFn KeyHashFnType) (*MaglevHash, error)
  • func (m *MaglevHash) Node(key []byte) string

Constants

const (
	// The default number of slots is the smallest prime number larger than 10,000.
	// It should be OK for less than 100 nodes.
	DefaultSlotCnt = 10007
)

Types

type KeyHashFnType

type KeyHashFnType func([]byte) uint32

KeyHashFnType

type MaglevHash

type MaglevHash struct {
	// contains filtered or unexported fields
}

MaglevHash assigns fixed number of slots to a collection of nodes. 1. Nodes are identified by string. 2. The default hash function hashing key to slot is CRC32.

func NewMaglev

func NewMaglev(nodes []string) (*MaglevHash, error)

NewMaglev creates a Maglev hash for the given nodes, using default number of slots and the CRC32 key hash function.

func NewMaglevWithTableSize

func NewMaglevWithTableSize(slotCnt int, nodes []string, keyHashFn KeyHashFnType) (*MaglevHash, error)

NewMaglevWithTableSize creates a Maglev hash. Nodes are identified by strings. In order to make lookup table stable, the given list of nodes are sorted and deduplicated.

func (*MaglevHash) Node

func (m *MaglevHash) Node(key []byte) string

Node returns the assigned node for the given key.