TASK
Implementation
Build Chord DHT: nodes on ring, finger tables for routing. Achieve O(log n) lookups in P2P network.
Sample Test Cases
Hash key to ringTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"chord_hash","msg_id":2,"key":"mykey","m":6}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"chord_hash_ok","in_reply_to":2,"msg_id":1,"hash":7}}Hints
Hint 1▾
Each node has ID on hash ring
Hint 2▾
Finger table for O(log n) lookup
Hint 3▾
Handle node join/leave
OVERVIEW
Theoretical Hub
Chord DHT
Chord arranges nodes on hash ring. Finger tables point to nodes 2^i ahead for O(log n) hops. Used in P2P systems and some databases.
Key Concepts
DHTChordfinger table
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/env python3
import hashlib
class ChordNode:
def __init__(self, node_id, m=6):
self.id = node_id
self.m = m # Ring size = 2^m
self.finger = [None] * m
self.predecessor = None
self.data = {}
def _hash(self, key):
return int(hashlib.sha256(key.encode()).hexdigest(), 16) % (2 **
self.m)
def find_successor(self, key_id):
# TODO: Use finger table to find responsible node
pass
def join(self, existing_node):
# TODO: Join ring via existing node
pass
def put(self, key, value):
# TODO: Store at responsible node
pass
def get(self, key):
# TODO: Retrieve from responsible node
pass