Consistent Hashing

1 / The Distribution Problem

Consistent Hashing was not an abstract concept I read about — I implemented it from scratch in both Java and Python. The problem it solves is fundamental to distributed systems: when you have N cache nodes and you add or remove one, a naive hash function (`key % N`) would remap almost every key to a different node, causing a cascade of cache misses. Consistent hashing limits that disruption to approximately K/N keys.

2 / Implementation in Cairn and Shard

In Cairn (Java 21) and Shard (Python), I implemented hash rings with Murmur3 hash functions. The critical insight was virtual nodes: mapping each physical node to 100-250 virtual positions on the ring to prevent the uneven key distribution that occurs with too few hash points. Without virtual nodes, key distribution hotspots caused some nodes to handle disproportionate load while others sat nearly idle.

3 / Data Structures

Java's TreeMap (NavigableMap) provided O(log N) ring lookup for successor node identification — given a key's hash, finding the next node on the ring was a ceiling-key operation. In Python, the bisect module served the same purpose over a sorted list of ring positions.

4 / Concurrency Challenges

Handling concurrent ring mutations during node join/leave events without blocking active read traffic required careful lock management. The solution was read-write locks (ReentrantReadWriteLock in Java) — read routing operations ran in parallel while ring topology updates acquired exclusive write locks. This prevented a node departure from corrupting routing decisions mid-request.