mirror of
https://github.com/hanzokv/go.git
synced 2026-09-24 00:31:51 +00:00
BigskandGitHub
cd984fae99
* ring: remove external rendezvous dependency by inlining implementation Replace usage of github.com/dgryski/go-rendezvous with an internal implementation to eliminate the external dependency and avoid licence propagation concerns. The implementation preserves the exact hashing algorithm and behaviour: - same hash combination: khash ^ nhash - same mixing function (xorshift* variant) - same node ordering semantics No functional changes intended. * Refactor TestRendezvous to remove randomString function Replaced function with inline string generation for test cases. * test: refactor RendezvousHash tests to use Ginkgo and Gomega * test: improve RendezvousHash test for per-instance determinism and distribution balance * test: enhance distribution verification in RendezvousHash tests
55 lines
1.0 KiB
Go
55 lines
1.0 KiB
Go
package hashtag
|
|
|
|
import "github.com/cespare/xxhash/v2"
|
|
|
|
// RendezvousHash implements HRW (Highest Random Weight) hashing.
|
|
type RendezvousHash struct {
|
|
nodes []node
|
|
}
|
|
|
|
type node struct {
|
|
name string
|
|
hash uint64
|
|
}
|
|
|
|
// NewRendezvousHash builds a hash from shard names.
|
|
func NewRendezvousHash(shards []string) *RendezvousHash {
|
|
n := make([]node, len(shards))
|
|
for i, s := range shards {
|
|
n[i] = node{
|
|
name: s,
|
|
hash: xxhash.Sum64String(s),
|
|
}
|
|
}
|
|
return &RendezvousHash{nodes: n}
|
|
}
|
|
|
|
// Get returns the shard name for the given key.
|
|
func (r *RendezvousHash) Get(key string) string {
|
|
if len(r.nodes) == 0 {
|
|
return ""
|
|
}
|
|
|
|
kh := xxhash.Sum64String(key)
|
|
|
|
bestIdx := 0
|
|
bestScore := mix64(kh ^ r.nodes[0].hash)
|
|
|
|
for i := 1; i < len(r.nodes); i++ {
|
|
if score := mix64(kh ^ r.nodes[i].hash); score > bestScore {
|
|
bestScore = score
|
|
bestIdx = i
|
|
}
|
|
}
|
|
|
|
return r.nodes[bestIdx].name
|
|
}
|
|
|
|
// mix64 is a xorshift-based mixing function.
|
|
func mix64(x uint64) uint64 {
|
|
x ^= x >> 12
|
|
x ^= x << 25
|
|
x ^= x >> 27
|
|
return x * 2685821657736338717
|
|
}
|