🔗Consistent Hashing

NEW

Distributing keys across nodes to minimize remapping when nodes change.

DESCRIPTION

Consistent hashing maps keys and nodes onto a ring so that node additions or removals only remap a small fraction of keys. It underlies scalable caches, sharded databases, and distributed hash tables. Virtual nodes smooth load imbalance across heterogeneous clusters. Replication is achieved by walking the ring to successive nodes. It reduces reconfiguration overhead compared to modulo-based partitioning.

ALTERNATIVE DEFINITIONS

Wikipedia

Consistent hashing is a special kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average.

Quantifies minimal key remapping upon resizing.

Source

Cloudflare

Consistent hashing is a technique that allows requests to be distributed across a changing set of servers with minimal reorganization.

Focuses on dynamic server sets and minimal reshuffling.

Source

RELATED TERMS

Distributed Hash Table Sharding Partitioning Ring Topology Load Balancing Virtual Nodes Replication CAP Theorem Key Space

COMPETING TERMS

Rendezvous Hashing Range Partitioning

RELATIONS

• Broader: Hashing

KNOWLEDGE AREAS

Infrastructure Data Storage & Operations Software Engineering Data Engineering

TARGET AUDIENCE

Software Developer Data Engineer Cloud Architect DevOps Engineer Software Architect

EXTERNAL SOURCES

• Wikipedia - Consistent hashing
• Amazon (Dynamo paper) - Dynamo uses consistent hashing ring
• Cloudflare - CDN-focused explanation
• Apache Cassandra - Partitioning and token ring

TOP QUESTIONS

Why use Consistent Hashing over modulo hashing?

Consistent hashing remaps only a small fraction of keys when nodes change, reducing rebalancing and cache invalidation costs.

Category: Comparison

What are virtual nodes in Consistent Hashing?

Virtual nodes assign multiple positions per physical node on the ring to smooth load and handle heterogeneity.

Category: Concept

How does replication work with Consistent Hashing?

Replicas are placed on subsequent positions around the ring to achieve durability and availability.

Category: Application

What are common pitfalls of Consistent Hashing?

Poor hash functions, too few virtual nodes, or skewed key distributions cause hotspots and imbalance.

Category: Mistakes

Is Rendezvous Hashing a competitor to Consistent Hashing?

Yes, rendezvous hashing also minimizes remapping and can simplify implementation without a ring structure.

Category: Alternatives

How does Consistent Hashing impact scalability?

It supports near-linear scalability by enabling incremental node changes with limited data movement.

Category: Performance

Where is Consistent Hashing used in practice?

It powers distributed caches (CDNs, memcached), key-value stores, and service sharding in microservices.

Category: Application

How do you test a Consistent Hashing implementation?

Validate uniformity, movement fraction on node changes, and replica placement under randomized workloads.

Category: Testing

What is a hot topic around Consistent Hashing?

Weighted and locality-aware hashing to optimize for heterogeneous or multi-region clusters.

Category: Topic