Consistent hashing

What is consistent hashing?

A technique to distribute data across nodes so that minimal remapping is needed when nodes are added or removed.

Why is consistent hashing used?

To improve scalability and fault tolerance in distributed systems.

How does consistent hashing work?

It maps both data and nodes to a circular hash space and assigns data to the nearest clockwise node.

What is the main advantage of consistent hashing?

Only a small portion of data needs to be redistributed when the system changes.

What is a hash ring?

A circular space where both keys and nodes are placed based on their hash values.

What happens when a new node is added in consistent hashing?

Only a fraction of the keys are reassigned to the new node.

What happens when a node is removed in consistent hashing?

Its keys are transferred to its next clockwise neighbor on the hash ring.

What is a virtual node in consistent hashing?

A logical subdivision of a physical node to improve data distribution and load balancing.

Why are virtual nodes used?

To evenly distribute keys and reduce load imbalance between physical nodes.

What is a drawback of basic consistent hashing?

Uneven distribution if there are few nodes and no virtual nodes.

What types of systems commonly use consistent hashing?

Distributed caches (e.g., Memcached), databases, and load balancers.

What is the time complexity for key lookup in consistent hashing?

Typically O(1) with appropriate data structures like sorted maps.

How is a key assigned to a node in consistent hashing?

By hashing the key and finding the nearest node in the clockwise direction on the ring.

What is a good hash function for consistent hashing?

A uniform, deterministic function like MD5 or SHA-1.

What is the primary goal of consistent hashing in distributed systems?

To maintain data availability and performance during system changes.