Interview Notes Search

Hello InterviewQuick Reference

Full Article

Consistent Hashing

Interview Use

Use managed systems

Most modern distributed systems handle sharding and data distribution for you.

Go deep for infrastructure

Distributed databases, caches, and message brokers are the common from-scratch prompts.

Avoid custom implementation

Most interviews only need to acknowledge that existing solutions handle this complexity.

Distribution Choice

Modulo Hashing uses hash(key) % node count and redistributes most data on membership changes; Consistent Hashing maps keys and nodes to a ring and walks clockwise to minimize redistribution.

  • Modulo Hashing : Use hash(key) % node count; adding or removing a node redistributes most data.
  • Consistent Hashing : Hash keys and nodes onto a ring; walk clockwise to the next node to minimize redistribution.

Hash Ring

Lookup Flow

1

Create the hash ring

Use a fixed circular hash space for both data and servers.

2

Place server nodes

Map each database, cache, broker, or app server to positions on the ring.

3

Route each key

Hash the key, find its point, then move clockwise until a node is found.

Membership Changes

Adding a Node moves only the range claimed by the new node; Removing a Node moves only keys mapped to that node to the next clockwise node.

  • Adding a Node : Only the new node's claimed range moves; all other keys stay put.
  • Removing a Node : Only keys mapped to the removed node move; they remap to the next clockwise node.

Load Balance

Virtual Node Effects

Virtual Nodes place each database at many ring positions; Failure Spread sends failed ranges to multiple remaining databases; New Node Spread absorbs small chunks from multiple existing nodes.

  • Virtual Nodes : Hash multiple variations of each database name to place it at many ring positions.
  • Failure Spread : A failed node's ranges redistribute across multiple remaining databases, not one neighbor.
  • New Node Spread : A new database absorbs small chunks from multiple existing nodes from the start.

Hot Spot Fixes

Read Replicas are the most common hot spot fix and load-balance reads across replicas; Key-Space Salting scatters hot keys with suffixes; Adaptive Rebalancing moves key ranges using traffic monitoring.

  • Read Replicas : Most common approach; replicate hot keys and load-balance reads across nodes.
  • Key-Space Salting : Append random suffixes to hot keys so reads scatter across nodes and aggregate.
  • Adaptive Rebalancing : Operationally complex; monitor traffic and move specific key ranges off overloaded nodes.

Real World

Apache Cassandra uses consistent hashing to distribute data across the ring; Amazon DynamoDB uses it for partition placement; Content Delivery Networks use it to choose an edge cache server.

  • Apache Cassandra : Uses consistent hashing to distribute data across the ring.
  • Amazon DynamoDB : Uses consistent hashing under the hood for partition placement.
  • Content Delivery Networks (CDNs) : Use consistent hashing to choose which edge server should cache content.