Consistent Hashing (C)
Topics: consistent hashing, virtual nodes, hash ring
Problem
Distribute keys across a changing set of nodes (cache shards, storage replicas) so that adding or
removing a node moves only ~1/N of the keys, not the whole keyspace. The trick is a hash ring
with virtual nodes, built here over caller-provided storage (no allocation).
#define RING_NAME_MAX 32
typedef struct { unsigned int hash; char node[RING_NAME_MAX]; } RingPoint;
typedef struct {
int replicas;
RingPoint *points; size_t points_cap, points_count;
char (*nodes)[RING_NAME_MAX]; size_t nodes_cap, nodes_count;
} Ring;
void ring_init(Ring *r, int replicas, RingPoint *points, size_t points_cap,
char nodes[][RING_NAME_MAX], size_t nodes_cap);
void ring_add(Ring *r, const char *node);
void ring_remove(Ring *r, const char *node);
bool ring_get(Ring *r, const char *key, char *out); // out: >= RING_NAME_MAX bytes
size_t ring_len(const Ring *r);
ring_add: place replicas virtual points for node on the ring (hash("node#i") for
i in 0..replicas), keeping points sorted by hash. Idempotent.ring_get: hash the key and return the node owning the first point clockwise (the
smallest point hash >= hash(key)), wrapping to index 0 if the key's hash is past every point.
Returns false if the ring is empty.ring_remove: drop a node and all of its virtual points.
Key concepts
- The ring:
points is a sorted array of (hash, node). ring_get is a linear scan for the
first point with hash >= hash(key) (a sorted array would also support binary search), wrapping
to index 0 past the end.
- Virtual nodes: each real node gets
replicas points spread around the ring, so its share of
the keyspace is roughly even — more replicas means smoother distribution.
- Minimal disruption: because a key only depends on the next point clockwise, adding a node
steals keys only from the arcs its new points land on; everything else is untouched.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/ring && /tmp/ring
Sign in to submit your solution.