TASK
Implementation
Rendezvous hashing (Highest Random Weight) is an alternative to consistent hashing. For each key, compute a score for every node, and the highest score wins.
Algorithm:
- For each key K and each node N:
score = hash(K + N) - Assign K to the node with the highest score
- When a node is added/removed, re-evaluate only affected keys
Advantages over consistent hashing:
- Simpler implementation (no ring data structure)
- Perfect distribution without virtual nodes
- Easy to support weighted nodes:
score = hash(K + N) * weight(N)
Disadvantages:
- O(N) per lookup (must compute score for all nodes) vs. O(log N) for ring
- For small clusters (<100 nodes), the O(N) cost is negligible
Request: {"type": "hrw_lookup", "msg_id": 1, "key": "user:42", "nodes": ["n1", "n2", "n3"]}
Response: {"type": "hrw_lookup_ok", "in_reply_to": 1, "key": "user:42", "winner": "n2", "scores": {"n1": 12345, "n2": 99999, "n3": 45678}}Sample Test Cases
HRW returns node with highest scoreTimeout: 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":"hrw_lookup","msg_id":2,"key":"test","nodes":["n1","n2","n3"]}}
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":"hrw_lookup","msg_id":2,"key":"k","nodes":["n1","n2"]}}
{"src":"c1","dest":"n1","body":{"type":"hrw_lookup","msg_id":3,"key":"k","nodes":["n1","n2"]}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
For each key, compute weight(key, node) = hash(key + node_id) for ALL nodes
Hint 2▾
The node with the highest weight owns the key
Hint 3▾
When a node is added/removed, only keys where that node had the highest weight are affected
Hint 4▾
Simpler than consistent hashing: no ring, no virtual nodes
Hint 5▾
Naturally supports weighted nodes: multiply the hash by the node weight
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
rendezvous hashinghighest random weightHRWconsistent hashing alternativeweighted nodes
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()