TASK
Implementation
Consistent hashing places nodes and keys on a circular ring, minimizing key redistribution when nodes join or leave. Unlike modulo hashing (hash(key) % N), adding a node only moves ~1/N of keys.
Hash ring construction:
- For each node, compute
position = hash(node_id) % 2^32 - Place nodes on a circle of size 2^32
Key lookup:
- Compute
position = hash(key) % 2^32 - Walk clockwise from that position until you find a node
- That node owns the key
Key redistribution on node join: only keys between the new node and its counter-clockwise neighbor need to move. All other keys stay in place.
Request: {"type": "ring_lookup", "msg_id": 1, "key": "user:42"}
Response: {"type": "ring_lookup_ok", "in_reply_to": 1, "key": "user:42", "node": "n2", "position": 1048576}Sample Test Cases
Key maps to nearest clockwise nodeTimeout: 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_lookup","msg_id":2,"key":"user:42"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Same key always maps to same 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_lookup","msg_id":2,"key":"k1"}}
{"src":"c1","dest":"n1","body":{"type":"ring_lookup","msg_id":3,"key":"k1"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
Place nodes at positions hash(node_id) % 2^32 on a circular ring
Hint 2▾
A key is owned by the first node clockwise from hash(key) % 2^32
Hint 3▾
When a node joins, only keys between the new node and its predecessor migrate
Hint 4▾
When a node leaves, only its keys move to its successor
Hint 5▾
Compare with modulo hashing: adding a node remaps ~1/N keys vs. nearly all keys
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
consistent hashinghash ringkey ownershipclockwise lookupminimal disruption
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()