Concept
Consistent hashing
Definition
A hash ring that moves about K/N keys when membership changes, instead of remapping the whole keyspace.
Studies
- Consistent Hashing: Rings, Virtual Nodes & Replica PlacementModulo remaps ~all keys on membership change; consistent hashing remaps ~K/N via a clockwise hash ring. Vnodes fix skew and fan out failures; RF walks collect distinct physical nodes (topology-aware).
- Rendezvous Hashing (HRW): Highest Random WeightHRW scores hash(key, node) and picks the max. No ring to maintain; membership change remaps about 1/N; lookup is O(N) unless approximated. Weights fold into the score.
- Jump Consistent Hash: Dense Buckets, Almost No MemoryJump hash maps a key onto 0..N-1 with almost no memory and ~K/N movement. Buckets must be a dense integer range — no arbitrary node ids, weights, or AZ walks.
- Vnode Rebalancing & Membership: Stream ~K/N Without Split-BrainAdding a node only steals ~1/N of keys, but streaming those keys still needs throttling, versioned membership, and hinted handoff so clients and replicas do not split-brain.
- Topology-Aware Replica Placement: Racks, AZs, and Honest QuorumsRF walks must skip the same host and prefer different racks/AZs. Quorum R+W>RF is not enough if all copies share a failure domain.
- Hot Keys & Bounded Loads: When Consistent Hashing Is Not EnoughConsistent hashing balances key cardinality, not QPS. Salt hot partitions, coalesce, or use bounded-load / power-of-two-choices so one viral key does not melt a shard.