Hash Ring Implementation

The heart of our distributed system is the consistent hashing algorithm. Let's examine how it works.

How Consistent Hashing Works

1. Each node is assigned a position on a virtual ring using SHA1 hashing
2. Keys are also hashed to find their position on the ring
3. A key is assigned to the first node clockwise from its position
4. This ensures even distribution and minimal data movement when nodes change

Implementation

// hash_ring/hashring.go
package hash_ring

import (
    "crypto/sha1"
    "sort"
    "sync"
)

type Node struct {
    ID      string
    Address string
}

type HashRing struct {
    nodes  []Node
    hashes []uint32
    lock   sync.RWMutex
}

func NewHashRing() *HashRing {
    return &HashRing{}
}

func (h *HashRing) AddNode(node Node) {
    h.lock.Lock()
    defer h.lock.Unlock()
    hash := h.hash(node.ID)
    h.nodes = append(h.nodes, node)
    h.hashes = append(h.hashes, hash)
    sort.Slice(h.hashes, func(i, j int) bool {
        return h.hashes[i] < h.hashes[j]
    })
}

func (h *HashRing) GetNode(key string) Node {
    if len(h.nodes) == 0 {
        return Node{}
    }

    h.lock.RLock()
    defer h.lock.RUnlock()

    hash := h.hash(key)
    index := sort.Search(len(h.hashes), func(i int) bool {
        return h.hashes[i] >= hash
    })

    if index == len(h.hashes) {
        index = 0
    }

    targetHash := h.hashes[index]
    for _, node := range h.nodes {
        if h.hash(node.ID) == targetHash {
            return node
        }
    }

    return h.nodes[0]
}

Key Benefits

• Even Distribution: Keys are distributed evenly across nodes
• Minimal Redistribution: When nodes join or leave, only a fraction of keys need to move
• Scalability: Easy to add or remove nodes from the cluster