Documentation
¶
Overview ¶
Package hrw implements Rendezvous (Highest-Random-Weight) hashing for Gantry's per-digest puller selection (the step 3).
Score function (deterministic across all agents):
score(node, digest) = SHA256( node_id_utf8 || digest_canonical_utf8 )
Concatenation is a byte-level append, no separator. node_id is the stable string identity from ifaces.NodeID; digest_canonical is digest.Digest.String (e.g. "sha256:abc..."). Both forms are stable and identical across agents per the design doc / the design doc / the design doc.
The top-K selection uses a min-heap of capacity K rather than a full sort: with 10k cluster members the algorithmic gain (O(N·log K) vs O(N·log N)) is meaningful, and the heap also bounds the temporary allocation. The final returned slice is ordered by score *descending* - rank 0 is the highest-scoring node, rank K-1 is the lowest of the top-K.
Topology-aware mode (the design doc): callers may filter candidates to a single availability zone before scoring. The package itself is topology- agnostic - TopK takes whatever node slice it is given. Callers constructing zone-scoped sets must produce a strictly local view (any node with matching zone label, regardless of address state).
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Candidates ¶
Candidates filters cluster by scope: - ScopeCluster: returns cluster unchanged (caller may share the backing array - TopK never mutates it). - ScopeZone: returns the subset whose Zone equals requesterZone. If requesterZone == "" the returned slice is empty; the caller is responsible for handling that case (typically by falling back to ScopeCluster behavior at the config layer).
The returned slice is freshly allocated only when filtering is necessary.
func RankOf ¶
RankOf returns the 0-based rank of nodeID inside cluster for digest d, or -1 if nodeID is not in cluster. Used by `pull_intent_query` responders to report their own rank back to the requester so the requester can detect informer-divergence (the design doc) and emit `p2p_hrw_rank_mismatch_total` (the design doc).
Note this scores every member; for large clusters this is intentionally O(N) - there is no faster way to learn one's own rank without scoring every candidate.
Types ¶
type Scope ¶
type Scope int
Scope is the topology mode HRW operates in.
const ( // ScopeCluster considers every node in the membership view. ScopeCluster Scope = 0 // ScopeZone restricts the candidate set to nodes that share a zone // label with the requester. Nodes without a Zone label (Zone == "") // are excluded entirely in ScopeZone - they cannot be matched. ScopeZone Scope = 1 )
func ParseScope ¶
ParseScope returns the Scope value for a config string. "zone" and "cluster" are accepted; everything else is treated as ScopeCluster (the safe default per the config layer's Validate step).
type Scored ¶
Scored pairs a node with its computed HRW score. The score is the 32-byte SHA-256 output; lexicographic byte-order comparison defines "higher" so all implementations agree on tie-breaking.
func TopK ¶
TopK returns up to k nodes from candidates ranked by descending HRW score for d. If len(candidates) <= k, every candidate is returned (still in score order). A nil or empty candidates slice returns nil.
The candidate filter - e.g., zone-scoping per the design doc - is the caller's responsibility. This function preserves no order from the input.
Source Files