Documentation
¶
Overview ¶
Package ring implements rendezvous (highest-random-weight, HRW) hashing — the L0 sharding primitive (DESIGN.md §11). Each key is placed on the nodes that score highest for it, where a node's score for a key is a hash of the key seeded by the node's identity. This gives:
- Deterministic placement: every node computes the same owners for a key with no shared state beyond the membership list, so routing needs no coordinator on the hot path.
- Minimal movement (~1/N) on membership change: adding a node only ever steals keys *to itself*, and removing a node only redistributes *its* keys — existing assignments between other nodes never reshuffle. This is the property that makes rebalancing move the minimal set of parts.
The ring is immutable; membership changes (Ring.With / Ring.Without) return a new ring.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
Node is a cluster member. ID is its stable, unique identity (the only thing that affects a node's HRW score).
Failure domains are hierarchical, coarsest first: Domains holds the node's location as a path such as {"rack1", "hostA"} — rack, then server — with the node itself the finest domain (a disk). Ring.LookupBalanced spreads a key's shards to minimize how many land in any one domain at each level (fewest per rack, then per server, then one per node/disk), so a whole rack, server, or disk failure loses as few shards as the topology allows. Zone is the single-level shorthand — equivalent to Domains == {Zone} — kept for the replica path (Ring.Lookup, which spreads across the coarsest domain only). When Domains is set it supersedes Zone; when both are empty placement is pure HRW.
type Ring ¶
type Ring struct {
// contains filtered or unexported fields
}
Ring is an immutable set of nodes over which keys are placed by HRW hashing. The zero value is an empty ring; construct one with New. Safe for concurrent use (read-only).
func New ¶
New returns a ring over nodes. Nodes with an empty or duplicate ID are dropped (ID is the identity), so membership is a well-formed set.
func (*Ring) Lookup ¶
Lookup returns up to rf nodes responsible for key — the first is the primary, the rest are replicas. It returns fewer than rf nodes only when the ring has fewer than rf members, and nil for an empty ring or rf ≤ 0. Selection is **zone-aware**: among nodes sorted by descending HRW score (ties broken by ID), it greedily picks the highest-scoring node from each not-yet-used zone first, so a key's replicas spread across as many distinct failure domains as possible; once distinct zones are exhausted (fewer zones than rf) it fills the remaining slots in score order. The primary is always the single highest-scoring node, and when every zone is empty the result is exactly the score-ordered top-rf (pure HRW). The result is fully deterministic.
func (*Ring) LookupBalanced ¶ added in v0.32.0
LookupBalanced returns up to rf nodes for key, spread across the failure-domain hierarchy **as evenly as possible** — it minimizes the maximum number of returned nodes in any one domain at each level (fewest per rack, then per server, then one per node/disk), rather than only guaranteeing distinct coarse domains up front like Ring.Lookup. This is the placement erasure coding needs: an ec(k,m) part must not lose more than m of its k+m shards to a single failure at any level, so the shards have to be balanced across the whole topology. With enough racks the maximum per rack is `ceil(rf / racks)`, and within a rack the shards balance across its servers the same way.
out[0] is always the primary (the single highest-scoring node), so the compaction owner is always among the returned set. When every node's domains are empty (the default), the result is exactly score order — identical to Ring.Lookup / pure HRW. Fully deterministic; returns fewer than rf nodes only when the ring is smaller, and nil for an empty ring or rf ≤ 0.
func (*Ring) Primary ¶
Primary returns the single owner of key (the highest-scoring node) and true, or a zero Node and false for an empty ring.
Source Files