TASK
Implementation
When a node joins, it takes over a portion of the key space from its clockwise neighbor. Only the keys that now fall in the new node's range need to migrate.
Join process:
- New node N4 calculates its position on the ring
- N4 finds its clockwise neighbor (successor) N2
- Keys between N4's counter-clockwise neighbor and N4 are transferred from N2 to N4
- Only ~1/N of total keys are affected (minimal disruption)
With virtual nodes: the new node takes V positions on the ring, taking small ranges from multiple existing nodes. This distributes the migration load evenly.
Request: {"type": "ring_add_node", "msg_id": 1, "new_node": "n4"}
Response: {"type": "ring_add_node_ok", "in_reply_to": 1, "keys_migrated": 250, "total_keys": 1000, "migration_pct": 25.0, "source_nodes": ["n1", "n2", "n3"]}Sample Test Cases
Node join migrates roughly 1/N keysTimeout: 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_add_node","msg_id":2,"new_node":"n4"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Keys are still accessible after migrationTimeout: 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_add_node","msg_id":2,"new_node":"n3"}}
{"src":"c1","dest":"n1","body":{"type":"ring_lookup","msg_id":3,"key":"migrated-key"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
When a new node joins, it takes keys from its clockwise neighbor
Hint 2▾
Only keys between the new node and its counter-clockwise neighbor migrate
Hint 3▾
This is ~1/N of total keys (vs. nearly 100% with modulo hashing)
Hint 4▾
During migration, the old owner continues serving reads for migrating keys
Hint 5▾
After migration completes, redirect new requests to the new owner
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
node additionkey migrationminimal disruptionpredecessor takeoverdata transfer
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()