hrw

README

go-hrw

HRW (Highest Random Weight), aka rendezvous hashing, for Go. Maps keys to nodes stably under membership churn. Port of joladev/hrw (Elixir).

// Linear scan, O(n)
owner, _ := hrw.Owner("192.168.0.1", []string{"server1", "server2", "server3"})

// Top-n owners (replicas), O(n log n)
owners, _ := hrw.Owners("192.168.0.1", nodes, 2)

// Skeleton-backed lookup, O(log n); plain data, build once
skel, _ := hrw.Build(nodes)
owner, _ = skel.Owner("192.168.0.1")

// Weighted: weight-10 node gets ~10x share
owner, _ = hrw.OwnerW("192.168.0.1", []hrw.WeightedNode{
    {Node: "server1", Weight: 1}, {Node: "server3", Weight: 10},
})

// Bounded load: no node exceeds ceil(k/n * (1+eps)) keys
m, _ := hrw.Assign(keys, nodes, hrw.WithEpsilon(0))

Notes

• Unlike Elixir, default hash is FNV-1a 64 with a splitmix64 finalizer; plug in your own via WithHash. Assignments are stable within a configuration but intentionally not comparable across hash functions or library versions.
• Build/BuildW accept WithFanout and WithClusterSize; defaults are auto-selected (fanout by cost model, cluster size 16).
• Zero dependencies beyond the standard library.

Development

Requires mise: mise trust, then mise run check (gofmt -> vet -> build -> test -race).

Benchmarks: go test -bench . -benchtime 1s.

Documentation

Index

• Variables
• func Assign(keys, nodes []string, opts ...Option) (map[string]string, error)
• func Owner(key string, nodes []string, opts ...Option) (string, error)
• func OwnerW(key string, nodes []WeightedNode, opts ...Option) (string, error)
• func Owners(key string, nodes []string, n int, opts ...Option) ([]string, error)
• type Option
  • func WithClusterSize(n int) Option
  • func WithEpsilon(e float64) Option
  • func WithFanout(n int) Option
• type Skeleton
  • func Build(nodes []string, opts ...Option) (*Skeleton, error)
  • func BuildW(nodes []WeightedNode, opts ...Option) (*Skeleton, error)
  • func (s *Skeleton) Owner(key string) (string, error)
• type Weighted
• type WeightedNode

Variables

var (
	ErrEmptyNodes = errors.New("hrw: empty node list")
	ErrBadCount   = errors.New("hrw: negative count")
	ErrBadWeights = errors.New("hrw: weights must be positive")
	ErrBadEpsilon = errors.New("hrw: epsilon must be >= 0")
)

Functions

func Assign

func Assign(keys, nodes []string, opts ...Option) (map[string]string, error)

Assign maps every key to a node, bounding each node's load at ceil(len(keys)/len(nodes) * (1+epsilon)). Keys and nodes are deduped; the result is a pure function of the inputs. O(k*n).

func Owner

func Owner(key string, nodes []string, opts ...Option) (string, error)

Owner returns the node owning key. O(n) over nodes.

func OwnerW

func OwnerW(key string, nodes []WeightedNode, opts ...Option) (string, error)

OwnerW returns the weighted owner of key. O(n) over nodes.

func Owners

func Owners(key string, nodes []string, n int, opts ...Option) ([]string, error)

Owners returns the top-n nodes for key, best first. O(n log n).

Types

type Option

type Option func(*config)

Option configures scoring and skeleton construction.

func WithClusterSize

func WithClusterSize(n int) Option

WithClusterSize sets the skeleton cluster size (default 16).

func WithEpsilon

func WithEpsilon(e float64) Option

WithEpsilon sets the load slack factor for Assign (default 0.25).

func WithFanout

func WithFanout(n int) Option

WithFanout sets the skeleton branching factor (default: auto).

type Skeleton

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

Skeleton is a precomputed clustered tree enabling O(log n) lookups. Plain data; build once with Build or BuildW, reuse across calls.

func Build

func Build(nodes []string, opts ...Option) (*Skeleton, error)

Build precomputes a Skeleton for O(log n) lookups.

func BuildW

func BuildW(nodes []WeightedNode, opts ...Option) (*Skeleton, error)

BuildW precomputes a weighted Skeleton. Weights bias both tree routing (via per-branch totals) and in-cluster leaf selection.

func (*Skeleton) Owner

func (s *Skeleton) Owner(key string) (string, error)

Owner routes key through the tree to a cluster, then picks the best-scoring node in it. O(log n).

type Weighted

type Weighted struct{}

Weighted implements weighted rendezvous scoring: score = pow(hash01, 1/weight). Higher weight biases keys toward the node.

type WeightedNode

type WeightedNode struct {
	Node   string
	Weight int
}

WeightedNode pairs a node with a positive weight.