Files

63 lines
1.6 KiB
Go

// Package hashring implements immutable consistent hashing with virtual nodes.
package hashring
import (
"cmp"
"crypto/sha256"
"encoding/binary"
"fmt"
"slices"
"sort"
"strconv"
)
type point struct {
hash uint64
node string
}
// Ring maps arbitrary keys to stable node identifiers.
type Ring struct {
points []point
}
// New creates an order-independent ring and rejects ambiguous node identities.
func New(nodes []string, replicas int) (*Ring, error) {
if len(nodes) == 0 || replicas < 1 {
return nil, fmt.Errorf("nodes and positive virtual node count are required")
}
ring := &Ring{}
seen := make(map[string]bool)
for _, node := range nodes {
if node == "" || seen[node] {
return nil, fmt.Errorf("node identifiers must be unique and nonempty")
}
seen[node] = true
for index := range replicas {
ring.points = append(ring.points, point{hash: hash(node + ":" + strconv.Itoa(index)), node: node})
}
}
slices.SortFunc(ring.points, func(a, b point) int {
if order := cmp.Compare(a.hash, b.hash); order != 0 {
return order
}
return cmp.Compare(a.node, b.node)
})
return ring, nil
}
// Owner selects the first virtual node clockwise from the key hash.
func (r *Ring) Owner(key string) string {
value := hash(key)
index := sort.Search(len(r.points), func(index int) bool {
return r.points[index].hash >= value
})
return r.points[index%len(r.points)].node
}
// hash maps a stable string into the ring's 64-bit coordinate space.
func hash(value string) uint64 {
sum := sha256.Sum256([]byte(value))
return binary.BigEndian.Uint64(sum[:8])
}