hash.go

package hash

import (
	"crypto/md5"
	"encoding/binary"
	"errors"
)

type NodeId int

type NodeManager interface {
	RemoveNode(NodeId) error
	AddNode(NodeId) error
	NodeResolver
}

type nodeManager struct {
	NodeResolver
	nodes map[NodeId]bool
}

func NewNodeManager() (NodeManager, error) {
	resolver, err := NewStaticNodeResolver(0)
	if err != nil {
		return nil, err
	}
	return nodeManager{
		resolver,
		make(map[NodeId]bool),
	}, nil
}

func (m nodeManager) AddNode(nodeId NodeId) error {
	_, ok := m.nodes[nodeId]
	if ok {
		return errors.New("node to be added already present")
	}
	resolver, err := NewStaticNodeResolver(len(m.nodes) + 1)
	if err != nil {
		return err
	}
	m.nodes[nodeId] = true
	m.NodeResolver = resolver
	return nil
}

func (m nodeManager) RemoveNode(nodeId NodeId) error {
	_, ok := m.nodes[nodeId]
	if !ok {
		return errors.New("node to be deleted not present")
	}

	resolver, err := NewStaticNodeResolver(len(m.nodes) - 1)
	if err != nil {
		return err
	}
	delete(m.nodes, nodeId)
	m.NodeResolver = resolver
	return nil
}

func (m nodeManager) Get(actor string) (NodeId, error) {
	id, err := m.NodeResolver.Get(actor)
	if err != nil {
		return 0, err
	}

	// TODO: also hold keys in slice to make this O(1)
	keys := make([]NodeId, 0, len(m.nodes))
	for k := range m.nodes {
		keys = append(keys, k)
	}
	return keys[id], nil
}

type NodeResolver interface {
	Get(actor string) (NodeId, error)
}

type staticNodeResolver struct {
	numberOfNodes int
}

func NewStaticNodeResolver(n int) (NodeResolver, error) {
	if n < 1 {
		return staticNodeResolver{}, errors.New("Node count invalid")
	}
	return staticNodeResolver{n}, nil
}

func (r staticNodeResolver) Get(actor string) (NodeId, error) {
	md5sum := md5.Sum([]byte(actor))
	u := binary.BigEndian.Uint64(md5sum[:8])
	nodeId := NodeId(u % uint64(r.numberOfNodes))
	return nodeId, nil
}

hash_test.go

package hash

import (
	"fmt"
	"math"
	"math/rand"
	"testing"
)

func TestStaticHashWithOneNode(t *testing.T) {
	nodeResolver := generateStaticResolver(1, t)
	actor := "actor1"
	nodeId, resolveErr := nodeResolver.Get(actor)
	if resolveErr != nil {
		t.Fatalf(fmt.Sprintf("%v", resolveErr))
	}

	expectedNodeId := NodeId(0)
	if nodeId != expectedNodeId {
		t.Errorf("Get(%s) returned %d, expected %d", actor, nodeId, expectedNodeId)
	}
}

func TestStaticHashShouldHaveUniformDistribution(t *testing.T) {
	rand.Seed(1345)

	nodeResolver := generateStaticResolver(2, t)
	actors := 10000
	counts := make(map[NodeId]int)
	for i := 0; i < actors; i++ {
		b := make([]byte, 10)
		_, err := rand.Read(b)
		if err != nil {
			t.Fatalf("Random array generation failed")
		}
		actor := string(b)
		node, fetchError := nodeResolver.Get(actor)
		if fetchError != nil {
			t.Fatalf("Lookup of %s failed", b)
		}

		counts[node] = counts[node] + 1
	}

	// results should be uniform with 1% error
	uniformityThreshold := 0.01
	uniformity := math.Abs(float64(counts[0]-counts[1]) / float64(counts[0]+counts[1]))

	if uniformity > uniformityThreshold {
		t.Errorf("Node distribution not uniform: actual %f, expected <%f", uniformity, uniformityThreshold)
	}
}

func generateStaticResolver(n int, t *testing.T) NodeResolver {
	nodeResolver, createErr := NewStaticNodeResolver(n)
	if createErr != nil {
		t.Fatalf(fmt.Sprintf("%v", createErr))
	}
	return nodeResolver
}

func TestNodeManagerWithSingleNode(t *testing.T) {
	manager, _ := NewNodeManager()
	addedNodeId := NodeId(5)
	manager.AddNode(addedNodeId)
	n, _ := manager.Get("foobar")
	if n != addedNodeId {
		t.Errorf("returned node id not correct: %d, expected %d", n, addedNodeId)
	}
}