// Package placement selects which cluster nodes should hold a given pin. // // anchorage uses Rendezvous (Highest Random Weight, HRW) hashing over the // tuple (orgID, cid, nodeID): every (node, pin) pair gets a deterministic // score, and the top min(replicas, liveNodes) nodes are chosen. // // Properties: // // - Deterministic: any node can compute "where does this pin belong" // without coordination, given the same live-node set. // - Minimal disruption: when a node joins or leaves, only pins whose top // replica set actually changes get moved; on average a fraction of // 1/N pins migrate, not all of them. // - No coordination: unlike consistent hashing with ring state, HRW is // pure function of the inputs, so there's no "ring" to synchronize. package placement import ( "sort" "github.com/zeebo/xxh3" ) // Node is the minimal view of a cluster node that placement needs. type Node struct { ID string // Status is used only by callers to pre-filter; placement treats // every node it's given as eligible. Status string } // Compute returns up to wantReplicas distinct node IDs chosen via HRW // over (orgID, cid, nodeID). The returned slice is sorted by score // descending; callers can take the first N for the replica set. // // If len(nodes) < wantReplicas, all nodes are returned (caller decides // whether to accept under-replication). func Compute(orgID, cid string, wantReplicas int, nodes []Node) []string { if wantReplicas <= 0 || len(nodes) == 0 { return nil } scored := make([]scoredNode, 0, len(nodes)) for _, n := range nodes { scored = append(scored, scoredNode{id: n.ID, score: score(orgID, cid, n.ID)}) } sort.Slice(scored, func(i, j int) bool { if scored[i].score == scored[j].score { return scored[i].id < scored[j].id } return scored[i].score > scored[j].score }) n := wantReplicas if n > len(scored) { n = len(scored) } out := make([]string, n) for i := 0; i < n; i++ { out[i] = scored[i].id } return out } type scoredNode struct { id string score uint64 } // score computes the HRW weight for a (org, cid, node) triple using // xxh3, which is fast, 64-bit, and well-distributed. The scalar weight // is the hash itself; higher = closer to the top. func score(orgID, cid, nodeID string) uint64 { h := xxh3.New() _, _ = h.WriteString(orgID) _, _ = h.WriteString("\x00") _, _ = h.WriteString(cid) _, _ = h.WriteString("\x00") _, _ = h.WriteString(nodeID) return h.Sum64() }