TASK
Implementation
With few physical nodes, a consistent hash ring has uneven key distribution. Virtual nodes fix this by giving each physical node V positions on the ring.
Problem: with 3 physical nodes, one node might own 50% of the ring, another 35%, and the last 15%. This is because hash positions are pseudo-random.
Solution: create V virtual nodes for each physical node at positions hash(node_id + "-" + i) for i in 0..V.
Distribution quality (V = virtual nodes per physical node):
- V=1: high variance (~40% standard deviation)
- V=10: moderate (~15% standard deviation)
- V=150: low (~5.5% standard deviation)
- V=500: very low (~3% standard deviation)
Request: {"type": "ring_create", "msg_id": 1, "nodes": ["n1", "n2", "n3"], "vnodes_per_node": 150}
Response: {"type": "ring_create_ok", "in_reply_to": 1, "total_vnodes": 450, "distribution": {"n1": 0.34, "n2": 0.33, "n3": 0.33}}Sample Test Cases
Virtual nodes improve distributionTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"ring_create","msg_id":2,"nodes":["n1","n2","n3"],"vnodes_per_node":150}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Total vnodes equals nodes * vnodes_per_nodeTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2"]}}
{"src":"c1","dest":"n1","body":{"type":"ring_create","msg_id":2,"nodes":["n1","n2"],"vnodes_per_node":100}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
With only 3 physical nodes, distribution is uneven (one node may own 60% of keys)
Hint 2▾
Virtual nodes: each physical node has V positions: hash(node_id + "-" + i) for i in 0..V
Hint 3▾
V=150 gives a standard deviation of ~5.5% around the ideal 1/N per node
Hint 4▾
Key lookup: find the nearest vnode clockwise, then map vnode -> physical node
Hint 5▾
More vnodes = better distribution, but more memory for the ring data structure
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
virtual nodesvnodeseven distributionload balancinghash collision
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3
import sys
import json
def main():
# Your implementation here
for line in sys.stdin:
msg = json.loads(line)
print(json.dumps(msg), flush=True)
if __name__ == "__main__":
main()