What is consistent hashing?

Consistent hashing is a special kind of hashing such that when a hash table is resized and the number of buckets changes, only a small fraction of keys need to be remapped on average. It's particularly useful in distributed systems and caches where nodes can be added or removed.

Why is consistent hashing important for load balancing?

In load balancing, if a server is added or removed, standard hashing would require remapping almost all keys. Consistent hashing minimizes this disruption by only remapping the keys that were assigned to the removed server or should be assigned to the new server, leading to better cache hit rates and less data migration.

System Design Interview

Consistent Hashing

A key technique for building scalable distributed systems. Learn how consistent hashing works and why it's superior to traditional hashing in dynamic environments.

Example: Consistent Hashing Ring in Python

A simplified implementation of a consistent hashing ring. This demonstrates how nodes and keys are placed on a ring and how to find the correct node for a given key.


                                import hashlib
                                import bisect
                                
                                class ConsistentHashing:
                                    def __init__(self):
                                        self.ring = {}
                                        self.sorted_keys = []
                                
                                    def _hash(self, key):
                                        return int(hashlib.md5(key.encode()).hexdigest(), 16)
                                
                                    def add_node(self, node):
                                        key = self._hash(node)
                                        self.ring[key] = node
                                        bisect.insort(self.sorted_keys, key)
                                
                                    def get_node(self, string_key):
                                        key = self._hash(string_key)
                                        idx = bisect.bisect_left(self.sorted_keys, key)
                                        if idx == len(self.sorted_keys):
                                            idx = 0
                                        return self.ring[self.sorted_keys[idx]]

Our AI Coach can help you explore advanced concepts like virtual nodes (replicas) to ensure a more even distribution of keys and load across your servers.