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 streaming
 
import (
	"bufio"

Streaming NDJSON logs over HTTP in Go

http-streaming channels select
Advanced 10 steps
go 
package api
 
import (
	"crypto/sha256"

ETag conditional requests in Gin

http-caching etag conditional-requests
Intermediate 6 steps
go 
func (w *Watcher) resetDebounce(d time.Duration) {
	if !w.timer.Stop() {
		select {
		case <-w.timer.C:

Debouncing a stream of events in Go

debounce timers channels
Advanced 7 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 steps
go 
package middleware
 
import (
	"net/http"

Per-plan export limits in Gin middleware

middleware rate-limiting authorization
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