Implement a consistent hashing ring

Q: Implement a consistent hashing ring

This question evaluates understanding of consistent hashing, virtual nodes, deterministic hash functions, and data structure design for efficient key-to-server mapping and dynamic membership changes.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement a class ConsistentHashRing that distributes keys across servers using a hash ring with virtual nodes.

Required API:

ConsistentHashRing(replicas_per_server: int)
add_server(server_id: str) -> None
remove_server(server_id: str) -> None
get_server(key: str) -> Optional[str]

Behavior:

Use any deterministic hash function that maps a string to a 32-bit integer.
When a server is added, create replicas_per_server virtual nodes at positions hash(server_id + "#" + i) for i = 0..replicas_per_server-1 .
get_server(key) computes hash(key) and returns the server owning the first virtual node found when moving clockwise around the ring.
If there is no virtual node with position greater than or equal to hash(key) , wrap around and return the server at the smallest position.
If the ring is empty, return None .
Removing a server removes all of its virtual nodes.

Target complexity:

add_server / remove_server : O(R log N) where R is the number of replicas added or removed
get_server : O(log N)

Implement a consistent hashing ring

Quick Overview

Comments (0)