aether/cluster/hashring_test.go

package cluster

import (
	"fmt"
	"math"
	"sort"
	"testing"
)

func TestNewConsistentHashRing(t *testing.T) {
	ring := NewConsistentHashRing()

	if ring == nil {
		t.Fatal("NewConsistentHashRing returned nil")
	}
	if ring.ring == nil {
		t.Error("ring map is nil")
	}
	if ring.nodes == nil {
		t.Error("nodes map is nil")
	}
	if !ring.IsEmpty() {
		t.Error("new ring should be empty")
	}
}

func TestAddNode(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")

	if ring.IsEmpty() {
		t.Error("ring should not be empty after AddNode")
	}

	nodes := ring.GetNodes()
	if len(nodes) != 1 {
		t.Errorf("expected 1 node, got %d", len(nodes))
	}
	if nodes[0] != "node-1" {
		t.Errorf("expected node-1, got %s", nodes[0])
	}

	// Verify virtual nodes were added
	expectedVirtualNodes := DefaultVirtualNodes
	if len(ring.sortedHashes) != expectedVirtualNodes {
		t.Errorf("expected %d virtual nodes, got %d", expectedVirtualNodes, len(ring.sortedHashes))
	}

	// Verify all virtual nodes point to the same physical node
	for _, hash := range ring.sortedHashes {
		if ring.ring[hash] != "node-1" {
			t.Errorf("virtual node hash %d points to %s, expected node-1", hash, ring.ring[hash])
		}
	}
}

func TestAddNode_Idempotent(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	initialHashCount := len(ring.sortedHashes)

	// Adding the same node again should be idempotent
	ring.AddNode("node-1")

	if len(ring.sortedHashes) != initialHashCount {
		t.Errorf("adding same node twice changed hash count: got %d, want %d", len(ring.sortedHashes), initialHashCount)
	}

	nodes := ring.GetNodes()
	if len(nodes) != 1 {
		t.Errorf("expected 1 node after duplicate add, got %d", len(nodes))
	}
}

func TestAddNode_MultipleNodes(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	ring.AddNode("node-2")
	ring.AddNode("node-3")

	nodes := ring.GetNodes()
	if len(nodes) != 3 {
		t.Errorf("expected 3 nodes, got %d", len(nodes))
	}

	expectedHashes := DefaultVirtualNodes * 3
	if len(ring.sortedHashes) != expectedHashes {
		t.Errorf("expected %d virtual nodes, got %d", expectedHashes, len(ring.sortedHashes))
	}

	// Verify hashes are sorted
	for i := 1; i < len(ring.sortedHashes); i++ {
		if ring.sortedHashes[i] < ring.sortedHashes[i-1] {
			t.Error("sortedHashes is not sorted")
			break
		}
	}
}

func TestRemoveNode(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	ring.AddNode("node-2")

	ring.RemoveNode("node-1")

	nodes := ring.GetNodes()
	if len(nodes) != 1 {
		t.Errorf("expected 1 node after removal, got %d", len(nodes))
	}

	if nodes[0] != "node-2" {
		t.Errorf("remaining node should be node-2, got %s", nodes[0])
	}

	// Verify virtual nodes were removed
	expectedHashes := DefaultVirtualNodes
	if len(ring.sortedHashes) != expectedHashes {
		t.Errorf("expected %d virtual nodes, got %d", expectedHashes, len(ring.sortedHashes))
	}

	// Verify no hashes point to removed node
	for _, hash := range ring.sortedHashes {
		if ring.ring[hash] == "node-1" {
			t.Error("found virtual node still pointing to removed node")
		}
	}
}

func TestRemoveNode_NonExistent(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	initialHashCount := len(ring.sortedHashes)

	// Removing non-existent node should be a no-op
	ring.RemoveNode("node-2")

	if len(ring.sortedHashes) != initialHashCount {
		t.Error("removing non-existent node changed ring state")
	}

	nodes := ring.GetNodes()
	if len(nodes) != 1 {
		t.Errorf("expected 1 node, got %d", len(nodes))
	}
}

func TestRemoveNode_AllNodes(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	ring.AddNode("node-2")

	ring.RemoveNode("node-1")
	ring.RemoveNode("node-2")

	if !ring.IsEmpty() {
		t.Error("ring should be empty after removing all nodes")
	}

	if len(ring.sortedHashes) != 0 {
		t.Errorf("expected 0 virtual nodes, got %d", len(ring.sortedHashes))
	}
}

func TestGetNode_EmptyRing(t *testing.T) {
	ring := NewConsistentHashRing()

	result := ring.GetNode("any-key")

	if result != "" {
		t.Errorf("expected empty string for empty ring, got %q", result)
	}
}

func TestGetNode_Consistent(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	ring.AddNode("node-2")
	ring.AddNode("node-3")

	testKeys := []string{
		"actor-123",
		"actor-456",
		"user:john@example.com",
		"order-789",
		"session-abc-def",
	}

	// Get initial assignments
	assignments := make(map[string]string)
	for _, key := range testKeys {
		assignments[key] = ring.GetNode(key)
	}

	// Verify consistency: same key should always return same node
	for i := 0; i < 100; i++ {
		for _, key := range testKeys {
			result := ring.GetNode(key)
			if result != assignments[key] {
				t.Errorf("inconsistent result for key %q: got %q, expected %q", key, result, assignments[key])
			}
		}
	}
}

func TestGetNode_SingleNode(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("only-node")

	// All keys should map to the only node
	testKeys := []string{"key1", "key2", "key3", "actor-123", "completely-different-key"}

	for _, key := range testKeys {
		result := ring.GetNode(key)
		if result != "only-node" {
			t.Errorf("key %q mapped to %q, expected only-node", key, result)
		}
	}
}

func TestGetNode_AfterNodeRemoval(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")
	ring.AddNode("node-2")
	ring.AddNode("node-3")

	// Get initial assignments for many keys
	numKeys := 1000
	initialAssignments := make(map[string]string)
	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		initialAssignments[key] = ring.GetNode(key)
	}

	// Remove one node
	ring.RemoveNode("node-2")

	// Count how many keys moved
	keysMoved := 0
	for key, initialNode := range initialAssignments {
		newNode := ring.GetNode(key)
		if initialNode == "node-2" {
			// Keys on removed node must move
			if newNode == "node-2" {
				t.Errorf("key %q still assigned to removed node", key)
			}
			keysMoved++
		} else if newNode != initialNode {
			// Keys not on removed node should ideally stay put
			keysMoved++
		}
	}

	// Verify remaining nodes get the traffic
	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		if node != "node-1" && node != "node-3" {
			t.Errorf("key %q assigned to unexpected node %q", key, node)
		}
	}
}

func TestKeyDistribution_Balanced(t *testing.T) {
	ring := NewConsistentHashRing()

	numNodes := 5
	for i := 0; i < numNodes; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	// Distribute many keys
	numKeys := 10000
	distribution := make(map[string]int)

	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		distribution[node]++
	}

	// Calculate expected keys per node and acceptable deviation
	expectedPerNode := float64(numKeys) / float64(numNodes)
	maxDeviation := 0.25 // Allow 25% deviation for reasonable balance

	for node, count := range distribution {
		deviation := math.Abs(float64(count)-expectedPerNode) / expectedPerNode
		if deviation > maxDeviation {
			t.Errorf("node %s has %d keys (%.1f%% deviation from expected %.0f)",
				node, count, deviation*100, expectedPerNode)
		}
	}

	// Verify all nodes got some keys
	if len(distribution) != numNodes {
		t.Errorf("expected %d nodes in distribution, got %d", numNodes, len(distribution))
	}
}

func TestRingBehavior_ManyNodes(t *testing.T) {
	ring := NewConsistentHashRing()

	numNodes := 100
	for i := 0; i < numNodes; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	// Verify all nodes are present
	nodes := ring.GetNodes()
	if len(nodes) != numNodes {
		t.Errorf("expected %d nodes, got %d", numNodes, len(nodes))
	}

	// Verify virtual nodes count
	expectedHashes := numNodes * DefaultVirtualNodes
	if len(ring.sortedHashes) != expectedHashes {
		t.Errorf("expected %d virtual nodes, got %d", expectedHashes, len(ring.sortedHashes))
	}

	// Verify hashes remain sorted
	for i := 1; i < len(ring.sortedHashes); i++ {
		if ring.sortedHashes[i] < ring.sortedHashes[i-1] {
			t.Error("sortedHashes is not sorted with many nodes")
			break
		}
	}

	// Verify GetNode still works correctly
	numKeys := 10000
	distribution := make(map[string]int)

	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		if node == "" {
			t.Errorf("GetNode returned empty string for key %q", key)
		}
		distribution[node]++
	}

	// All nodes should get at least some keys with 10000 keys across 100 nodes
	// (with virtual nodes, distribution should be reasonable)
	nodesWithKeys := len(distribution)
	if nodesWithKeys < numNodes/2 {
		t.Errorf("only %d nodes received keys, expected at least %d", nodesWithKeys, numNodes/2)
	}
}

func TestDefaultVirtualNodes_ImproveDistribution(t *testing.T) {
	// Test that virtual nodes actually improve distribution
	// by comparing with a theoretical single-hash-per-node scenario

	ring := NewConsistentHashRing()

	numNodes := 10
	for i := 0; i < numNodes; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	// Distribute keys
	numKeys := 10000
	distribution := make(map[string]int)

	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		distribution[node]++
	}

	// Calculate standard deviation of distribution
	expectedPerNode := float64(numKeys) / float64(numNodes)
	var sumSquaredDiff float64
	for _, count := range distribution {
		diff := float64(count) - expectedPerNode
		sumSquaredDiff += diff * diff
	}
	stdDev := math.Sqrt(sumSquaredDiff / float64(numNodes))
	coefficientOfVariation := stdDev / expectedPerNode

	// With DefaultVirtualNodes=150, we expect good distribution
	// Coefficient of variation should be low (< 15%)
	if coefficientOfVariation > 0.15 {
		t.Errorf("distribution has high coefficient of variation: %.2f%% (expected < 15%%)",
			coefficientOfVariation*100)
	}

	// Verify that the actual number of virtual nodes matches expected
	if len(ring.sortedHashes) != numNodes*DefaultVirtualNodes {
		t.Errorf("expected %d virtual node hashes, got %d", numNodes*DefaultVirtualNodes, len(ring.sortedHashes))
	}
}

func TestGetNodes(t *testing.T) {
	ring := NewConsistentHashRing()

	// Empty ring
	nodes := ring.GetNodes()
	if len(nodes) != 0 {
		t.Errorf("empty ring should return empty nodes slice, got %d nodes", len(nodes))
	}

	// Add nodes
	ring.AddNode("node-a")
	ring.AddNode("node-b")
	ring.AddNode("node-c")

	nodes = ring.GetNodes()
	if len(nodes) != 3 {
		t.Errorf("expected 3 nodes, got %d", len(nodes))
	}

	// Verify all added nodes are present
	nodeSet := make(map[string]bool)
	for _, n := range nodes {
		nodeSet[n] = true
	}

	for _, expected := range []string{"node-a", "node-b", "node-c"} {
		if !nodeSet[expected] {
			t.Errorf("expected node %q not found in GetNodes result", expected)
		}
	}
}

func TestIsEmpty(t *testing.T) {
	ring := NewConsistentHashRing()

	if !ring.IsEmpty() {
		t.Error("new ring should be empty")
	}

	ring.AddNode("node-1")
	if ring.IsEmpty() {
		t.Error("ring with node should not be empty")
	}

	ring.RemoveNode("node-1")
	if !ring.IsEmpty() {
		t.Error("ring should be empty after removing last node")
	}
}

func TestHash_Deterministic(t *testing.T) {
	ring := NewConsistentHashRing()

	testKeys := []string{
		"simple",
		"with-dashes",
		"with.dots",
		"with:colons",
		"unicode-\u4e16\u754c",
		"",
	}

	for _, key := range testKeys {
		hash1 := ring.hash(key)
		hash2 := ring.hash(key)
		if hash1 != hash2 {
			t.Errorf("hash not deterministic for key %q: got %d and %d", key, hash1, hash2)
		}
	}
}

func TestHash_DifferentKeys(t *testing.T) {
	ring := NewConsistentHashRing()

	keys := make([]string, 1000)
	hashes := make(map[uint32]string)

	for i := 0; i < 1000; i++ {
		keys[i] = fmt.Sprintf("key-%d", i)
		hash := ring.hash(keys[i])
		if existing, ok := hashes[hash]; ok {
			t.Errorf("hash collision: %q and %q both hash to %d", existing, keys[i], hash)
		}
		hashes[hash] = keys[i]
	}
}

func TestMinimalKeyMovement(t *testing.T) {
	ring := NewConsistentHashRing()

	// Start with 3 nodes
	ring.AddNode("node-1")
	ring.AddNode("node-2")
	ring.AddNode("node-3")

	// Record initial assignments
	numKeys := 10000
	initialAssignments := make(map[string]string)
	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		initialAssignments[key] = ring.GetNode(key)
	}

	// Add a new node
	ring.AddNode("node-4")

	// Count keys that moved
	keysMoved := 0
	for key, initialNode := range initialAssignments {
		if ring.GetNode(key) != initialNode {
			keysMoved++
		}
	}

	// With consistent hashing, only ~1/N keys should move (where N is new number of nodes)
	// Allow some tolerance: at most 35% should move
	maxExpectedMoved := int(float64(numKeys) * 0.35)
	if keysMoved > maxExpectedMoved {
		t.Errorf("too many keys moved: %d (%.1f%%), expected at most %d (35%%)",
			keysMoved, float64(keysMoved)/float64(numKeys)*100, maxExpectedMoved)
	}

	// At least some keys should move to the new node
	keysOnNewNode := 0
	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		if ring.GetNode(key) == "node-4" {
			keysOnNewNode++
		}
	}

	if keysOnNewNode == 0 {
		t.Error("no keys moved to new node")
	}
}

func TestWrapAround(t *testing.T) {
	ring := NewConsistentHashRing()

	ring.AddNode("node-1")

	// Test many keys to ensure wrap-around logic works
	// (keys with hash > max virtual node hash should wrap to first)
	for i := 0; i < 1000; i++ {
		key := fmt.Sprintf("wrap-test-%d", i)
		result := ring.GetNode(key)
		if result != "node-1" {
			t.Errorf("key %q should map to node-1, got %q", key, result)
		}
	}
}

func TestNodeIDFormats(t *testing.T) {
	ring := NewConsistentHashRing()

	// Test various node ID formats
	nodeIDs := []string{
		"simple",
		"with-dashes",
		"with_underscores",
		"with.dots",
		"192.168.1.1:8080",
		"node-1-replica-0",
		"verylongnodeidthatmightbeused",
		"",
	}

	for _, nodeID := range nodeIDs {
		ring.AddNode(nodeID)
	}

	if len(ring.GetNodes()) != len(nodeIDs) {
		t.Errorf("expected %d nodes, got %d", len(nodeIDs), len(ring.GetNodes()))
	}

	// Verify each node can be found
	for _, nodeID := range nodeIDs {
		found := false
		for _, n := range ring.GetNodes() {
			if n == nodeID {
				found = true
				break
			}
		}
		if !found {
			t.Errorf("node %q not found in ring", nodeID)
		}
	}
}

func TestSortedHashesOrder(t *testing.T) {
	ring := NewConsistentHashRing()

	// Add nodes in various orders
	nodeIDs := []string{"node-z", "node-a", "node-m", "node-1", "node-9"}

	for _, nodeID := range nodeIDs {
		ring.AddNode(nodeID)

		// Verify sorted after each addition
		for i := 1; i < len(ring.sortedHashes); i++ {
			if ring.sortedHashes[i] <= ring.sortedHashes[i-1] {
				t.Errorf("sortedHashes not properly sorted after adding %s", nodeID)
				break
			}
		}
	}
}

func TestConcurrentReadSafety(t *testing.T) {
	// Note: This test verifies that reads don't panic, but the implementation
	// may need mutex protection for concurrent read/write safety
	ring := NewConsistentHashRing()

	for i := 0; i < 10; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	// Multiple reads should be safe
	for i := 0; i < 1000; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		if node == "" {
			t.Errorf("GetNode returned empty for key %q", key)
		}
	}
}

func BenchmarkGetNode(b *testing.B) {
	ring := NewConsistentHashRing()

	for i := 0; i < 100; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	keys := make([]string, 1000)
	for i := range keys {
		keys[i] = fmt.Sprintf("key-%d", i)
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		ring.GetNode(keys[i%len(keys)])
	}
}

func BenchmarkAddNode(b *testing.B) {
	for i := 0; i < b.N; i++ {
		ring := NewConsistentHashRing()
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}
}

func BenchmarkDistribution(b *testing.B) {
	ring := NewConsistentHashRing()

	for i := 0; i < 10; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		ring.GetNode(fmt.Sprintf("key-%d", i))
	}
}

// Helper function to get min value from a slice (not using generics for Go 1.x compatibility)
func minInt(values []int) int {
	if len(values) == 0 {
		return 0
	}
	result := values[0]
	for _, v := range values[1:] {
		if v < result {
			result = v
		}
	}
	return result
}

// Helper function to get max value from a slice
func maxInt(values []int) int {
	if len(values) == 0 {
		return 0
	}
	result := values[0]
	for _, v := range values[1:] {
		if v > result {
			result = v
		}
	}
	return result
}

func TestDistributionStatistics(t *testing.T) {
	ring := NewConsistentHashRing()

	numNodes := 10
	for i := 0; i < numNodes; i++ {
		ring.AddNode(fmt.Sprintf("node-%d", i))
	}

	numKeys := 10000
	distribution := make(map[string]int)

	for i := 0; i < numKeys; i++ {
		key := fmt.Sprintf("key-%d", i)
		node := ring.GetNode(key)
		distribution[node]++
	}

	counts := make([]int, 0, len(distribution))
	for _, count := range distribution {
		counts = append(counts, count)
	}
	sort.Ints(counts)

	minCount := minInt(counts)
	maxCount := maxInt(counts)
	expectedPerNode := numKeys / numNodes

	// Log distribution statistics (these help understand the ring behavior)
	t.Logf("Distribution statistics:")
	t.Logf("  Min: %d (%.1f%% of expected)", minCount, float64(minCount)/float64(expectedPerNode)*100)
	t.Logf("  Max: %d (%.1f%% of expected)", maxCount, float64(maxCount)/float64(expectedPerNode)*100)
	t.Logf("  Expected: %d", expectedPerNode)

	// Verify min node has at least 50% of expected
	if minCount < expectedPerNode/2 {
		t.Errorf("minimum distribution too low: %d (expected at least %d)", minCount, expectedPerNode/2)
	}

	// Verify max node has at most 200% of expected
	if maxCount > expectedPerNode*2 {
		t.Errorf("maximum distribution too high: %d (expected at most %d)", maxCount, expectedPerNode*2)
	}
}