Consistent Hashing Implementation
adityakrverma
740
Career

CONSISTENT HASHING IMPLEMENTATION :

Overview:

  • The public key is converted into a hash.
  • The function looks for the closest node hash greater than or equal to the key's hash (using binary search).
  • The system ensures the ring-like behavior by wrapping the search back to the start if necessary.
  • Finally, the node corresponding to that hash is returned, which is where the public key is mapped.
  • This ensures a balanced and efficient distribution of keys (or data) across nodes.

import (
	"crypto/md5"
	"fmt"
	"github.com/spaolacci/murmur3"
)


/ A ConsistentHash is a ring hash implementation.
type ConsistentHash struct {
	// node hash list
	keys []uint64
	// <node hash,name> pair
	ring map[uint64]string
	lock sync.RWMutex
}

// NewConsistentHash returns a ConsistentHash.
func NewConsistentHash() *ConsistentHash {
	return &ConsistentHash{
		ring: make(map[uint64]string),
	}
}

// AddNode add bid services domain
func (h *ConsistentHash) AddNode(node string) {
	h.lock.Lock()
	defer h.lock.Unlock()
	hash := Hash([]byte(node))
	h.keys = append(h.keys, hash)
	h.ring[hash] = node
	sort.Slice(h.keys, func(i, j int) bool {
		return h.keys[i] < h.keys[j]
	})
}

// DelNode delete bid services domain from hash ring
func (h *ConsistentHash) DelNode(node string) {
	h.lock.Lock()
	defer h.lock.Unlock()
	hash := Hash([]byte(node))
	//binary search index
	index := sort.Search(len(h.keys), func(i int) bool {
		return h.keys[i] >= hash
	})
	if index < len(h.keys) && h.keys[index] == hash {
		// delete it
		h.keys = append(h.keys[:index], h.keys[index+1:]...)
	}
	delete(h.ring, hash)
}

func (h *ConsistentHash) GetNode(publicKey string) (string, error) {
	if len(h.keys) == 0 {
		return "", constant.ErrEmptyBidServices
	}
	hash := Hash([]byte(publicKey))
	//binary search index
	index := sort.Search(len(h.keys), func(i int) bool {
		return h.keys[i] >= hash
	})
	index = index % len(h.keys)
	nodeHash := h.keys[index]
	if val, ok := h.ring[nodeHash]; !ok {
		return "", constant.ErrInternal
	} else {
		return val, nil
	}
}


// reference : https://github.com/zeromicro/go-zero/blob/master/core/hash/hash.go

// Hash returns the hash value of data.
func Hash(data []byte) uint64 {
	return murmur3.Sum64(data)
}

// Md5 returns the md5 bytes of data.
func Md5(data []byte) []byte {
	digest := md5.New()
	digest.Write(data)
	return digest.Sum(nil)
}

// Md5Hex returns the md5 hex string of data.
func Md5Hex(data []byte) string {
	return fmt.Sprintf("%x", Md5(data))
}

FYI : Consistent Hash Implmentation :
Here the client's public key (which is likely a unique identifier) is hashed to generate a number. This hash number will be used to locate a node on the ring.

We performs a binary search on the sorted list of node hashes (h.keys). The search finds the first node whose hash is greater than or equal to the hash of the public key. This ensures that the key is mapped to the correct node. [ So hash table has server-name as key and its hash as value ]

Since the consistent hash ring is circular, the index is wrapped around using the modulo operation. Finally, the node corresponding to that hash is returned, which is where the public key is mapped. This ensures a balanced and efficient distribution of keys (or data) across nodes.

Comments (0)