forked from mtusi2026/mtusi2026lab6
63 lines
1.6 KiB
Go
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])
|
|
}
|