Implement a Consistent Hash Ring

Question

The candidate is asked to implement a consistent hash ring, a data structure that allows for efficient distribution of data across a dynamic set of nodes.

Codemia · Accepted Answer

To implement a consistent hash ring, we need to ensure that data can be evenly distributed across a variable number of nodes. The main requirements include:
- Efficiently adding and removing nodes without significant data movement.
- Ensuring that the distribution of keys remains balanced.
- Providing a mechanism to retrieve the node responsible for a given key.

The consistent hash ring can be visualized as a circular structure where nodes are placed at various points based on their hash values. Keys are also hashed to determine their position on the ring. The node responsible for a key is the first node encountered when moving clockwise from the key's position. This design allows for minimal disruption when nodes are added or removed, as only a subset of keys will need to be reassigned.

Here is a basic implementation in Python:

```python
import hashlib
from bisect import bisect_right

class ConsistentHash:
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)

def _hash(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

def add_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f'{node}:{i}')
            self.ring[key] = node
            self.sorted_keys.append(key)
        self.sorted_keys.sort()

def remove_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f'{node}:{i}')
            del self.ring[key]
            self.sorted_keys.remove(key)

def get_node(self, key):
        if not self.ring:
            return None
        key_hash = self._hash(key)
        idx = bisect_right(self.sorted_keys, key_hash)
        return self.ring[self.sorted_keys[0]] if idx == len(self.sorted_keys) else self.ring[self.sorted_keys[idx]]
```
This code defines a `ConsistentHash` class that allows adding and removing nodes while maintaining the hash ring.

Using consistent hashing has several benefits, such as reduced data movement when nodes are added or removed. However, it can lead to uneven data distribution if the number of replicas is not chosen correctly. A higher number of replicas can improve balance but at the cost of increased memory usage. Additionally, the choice of hash function can impact the performance and distribution of keys, so it is crucial to select a robust hashing algorithm.

Implement a Consistent Hash Ring

DoorDash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

DoorDash Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline