Design consistent hashing for cache sharding

Interview explanation:

• Consistent hashing maps both servers and keys onto the same hash ring.
• A key is assigned to the first server clockwise from the key hash.
• When a server joins/leaves, only nearby keys remap, not the full keyspace.

Core design:

1. Hash ring (e.g. 0..2^32-1) with sorted server positions.
2. Virtual nodes per physical server (e.g. 100-500) for better load balance.
3. Lookup: hash(key) -> binary search first vnode >= hash, wrap to start if needed.
4. Replication: choose next N distinct physical servers clockwise.
5. Health-aware routing: skip unhealthy nodes during reads/writes.

Operational concerns:

• Rebalancing rate limits to avoid thundering migrations.
• Warm-up strategy for new nodes (background prefill).
• Observability: per-node hit rate, memory pressure, key distribution skew.
• Failure mode: temporary increase in misses; mitigate with multi-layer cache (L1+L2).

Complexity:

• Lookup is O(log V) with binary search on V virtual nodes.
• Space is O(V).