Skip to main content
PreparationZone Logo
PrepZone

Consistent Hashing with Virtual Nodes

Add or remove nodes without remapping the entire key space — ShardPay's shard ring.

Pass checkpoint below

Why this matters

  • Naive modulo hashing remaps almost every key when N changes — unacceptable during cluster resize.
  • Consistent hashing is standard for caches, shard routers, and load balancers.
  • Virtual nodes prevent uneven ring segments when physical machines differ in capacity.
  • ShardPay's shard router uses consistent hashing with 150 vnodes per physical shard.
Hash ring
Node Avn1, vn2
Node Bvn3, vn4
Node Cvn5, vn6

Keys hash onto the ring; walk clockwise to find owner

Virtual nodes spread keys evenly. Adding a node moves only adjacent key ranges.

Ring mechanics

ShardPay places 150 virtual nodes (vnodes) per physical shard on a hash ring from 0 to 2^64−1. An accountId hashes to a point on the ring; the router walks clockwise to the first vnode ≥ that hash — that vnode's physical shard owns the account. Adding shard 257 inserts 150 new vnodes; only keys between adjacent new and old vnodes migrate — not the entire keyspace.

Ring concepts

  • Hash ring — Logical circle where both keys and nodes map via the same hash function (e.g., Murmur3). ShardPay's ring state is versioned; routers cache ring v42 until the control plane publishes v43.
  • Clockwise walk (successor) — First node at or after the key's hash owns the key. ShardPay's ShardRouter.locate(accountId) performs binary search on sorted vnode positions — O(log vnodes) per lookup.
  • Virtual node (vnode) — Multiple ring positions per physical machine. ShardPay uses 150 vnodes per shard so a 16-shard cluster has 2,400 ring points — smooth load distribution even when physical nodes differ in CPU.
  • Rebalance / migration — When vnodes move between physical shards, only key ranges between old and new successor boundaries copy. ShardPay's resharding job migrates ~1/16 of keys when growing 16→17 shards, not 15/16 as with hash % 16.
  • Bounded loads — Extensions like Google's Jump Consistent Hash minimize migration further. ShardPay evaluated Jump Hash for even distribution; stayed with vnode ring for fine-grained hot-shard evacuation.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 2 sections

  • Modulo vs consistent hash
  • Virtual nodes and hot-shard evacuation

Test yourself

Answer these before moving on — recall is what makes it stick.