Implementing Distributed Hash Tables
1. Understanding DHT Architecture
| Property | Detail |
|---|---|
| Decentralized | No central directory |
| Scalable | O(log N) routing |
| Self-organizing | Auto-handles joins/leaves |
| Examples | Chord, Kademlia, Pastry, CAN, Tapestry |
| Real systems | BitTorrent (Mainline DHT), IPFS, Cassandra (variant) |
2. Implementing Chord Protocol
| Property | Value |
|---|---|
| Identifier space | m-bit ring (e.g., SHA-1 = 160-bit) |
| Successor | Next node clockwise on ring |
| Finger table | m entries; finger[i] = successor(n + 2^i) |
| Lookup | O(log N) hops |
| Stabilization | Periodic to maintain successor pointers |
3. Implementing Kademlia Protocol
| Property | Value |
|---|---|
| Distance metric | XOR — symmetric, simple |
| k-buckets | k nodes per distance bucket (k ≈ 20) |
| Lookup | Iterative; α parallel queries (α ≈ 3) |
| Used by | BitTorrent DHT, IPFS, Ethereum discovery |
4. Understanding Key Space Partitioning
| Approach | Detail |
|---|---|
| Ring (Chord, Cassandra) | Each node owns arc of ring |
| XOR tree (Kademlia) | Closest node by XOR distance |
| Cartesian (CAN) | d-dimensional torus |
| Prefix routing (Pastry) | Numeric prefix matching |
5. Implementing Finger Tables
| Index i | Entry | Use |
|---|---|---|
| 0 | successor(n+1) | Direct neighbor |
| 1 | successor(n+2) | Skip 2 |
| k | successor(n+2^k) | Exponential reach |
| m-1 | successor(n+2^(m-1)) | Half-ring |
6. Handling Node Joins and Departures
| Event | Action |
|---|---|
| Join | Bootstrap via known node; populate finger table; notify successor |
| Graceful leave | Transfer keys to successor; update predecessors |
| Failure | Detected by heartbeat; successor list provides redundancy |
| Stabilize | Periodic: ask successor for predecessor; fix fingers |
7. Implementing Routing in DHTs
| Algorithm | Steps |
|---|---|
| Recursive (Chord) | Forward query through nodes; reply propagates back |
| Iterative (Kademlia) | Originator queries directly; receives next hop hints |
| Greedy | Always forward to closest known to target |
8. Understanding DHT Replication
| Strategy | Detail |
|---|---|
| Successor list | Replicate to next k nodes (Chord) |
| k closest (Kademlia) | Store at k nodes nearest to key |
| Periodic re-publish | Refresh keys to handle churn |
| Erasure coding | Split + parity for storage efficiency |
9. Implementing DHT Lookups
| Cost | Value |
|---|---|
| Hops | O(log N) |
| Routing table size | O(log N) |
| Latency | ~log N × RTT |
| Redundancy | Parallel queries (α) tolerate slow/failed nodes |
10. Understanding DHT Trade-offs
| Pro | Con |
|---|---|
| Decentralized, scalable | Higher lookup latency than centralized |
| Fault tolerant | Churn requires constant maintenance |
| No SPOF | Hard to query "all values" |
| Self-balancing | Eventual consistency only |