go 53 lines · 8 steps

How consistent hashing works in Go

A hash ring maps keys to nodes so that adding or removing a node reshuffles only a small fraction of keys.

Explained by highlit
Intermediate consistent-hashing load-balancing concurrency binary-search data-structures
1package hashring
2 
3import (
4 "hash/crc32"
5 "sort"
6 "strconv"
7 "sync"
8)
9 
10type Ring struct {
11 mu sync.RWMutex
12 replicas int
13 keys []uint32
14 hashMap map[uint32]string
15}
16 
17func New(replicas int) *Ring {
18 return &Ring{
19 replicas: replicas,
20 hashMap: make(map[uint32]string),
21 }
22}
23 
24func (r *Ring) hash(key string) uint32 {
25 return crc32.ChecksumIEEE([]byte(key))
26}
27 
28func (r *Ring) Add(nodes ...string) {
29 r.mu.Lock()
30 defer r.mu.Unlock()
31 for _, node := range nodes {
32 for i := 0; i < r.replicas; i++ {
33 h := r.hash(strconv.Itoa(i) + node)
34 r.keys = append(r.keys, h)
35 r.hashMap[h] = node
36 }
37 }
38 sort.Slice(r.keys, func(i, j int) bool { return r.keys[i] < r.keys[j] })
39}
40 
41func (r *Ring) Get(key string) string {
42 r.mu.RLock()
43 defer r.mu.RUnlock()
44 if len(r.keys) == 0 {
45 return ""
46 }
47 h := r.hash(key)
48 idx := sort.Search(len(r.keys), func(i int) bool { return r.keys[i] >= h })
49 if idx == len(r.keys) {
50 idx = 0
51 }
52 return r.hashMap[r.keys[idx]]
53}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Consistent hashing places both nodes and keys on the same circular space so a key walks clockwise to the nearest node.
  2. 2Virtual replicas spread each physical node across the ring, smoothing out uneven key distribution.
  3. 3Keeping the hash points sorted lets lookups use binary search instead of scanning every node.

Related explainers

go 
package middleware
 
import (
	"net/http"

Wrapping Gin requests in a DB transaction

middleware transactions error-handling
Intermediate 8 steps
go 
package handlers
 
import (
	"encoding/base64"

Cursor pagination in a Gin handler

pagination cursor rest-api
Intermediate 8 steps
go 
package metrics
 
import (
	"sync"

A thread-safe sliding-window average in Go

concurrency sliding-window running-average
Intermediate 8 steps
go 
package logging
 
import (
	"fmt"

Redacting secrets with Go reflection

reflection recursion struct-tags
Advanced 10 steps
java 
public class RequestThrottler {
 
    private final Semaphore permits;
    private final long acquireTimeoutMillis;

Bounding concurrency with a Semaphore in Java

concurrency semaphore rate-limiting
Intermediate 6 steps
python 
import time
import threading
from flask import Flask, request, jsonify, g
 

A token-bucket rate limiter in Flask

rate-limiting token-bucket middleware
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

How consistent hashing works in Go — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code