distributed hash table dht

**Distributed Hash Tables (DHT)** are **decentralized lookup systems that distribute key-value storage across multiple nodes using consistent hashing — providing O(log N) route-to-key lookup in a self-organizing overlay network without any centralized directory or coordinator**. **Consistent Hashing:** - **Hash Ring**: keys and node IDs mapped to positions on a circular hash space (0 to 2^m - 1) — each key assigned to the nearest clockwise node (successor), distributing keys roughly evenly across N nodes - **Node Addition/Removal**: when a node joins or leaves, only keys in the affected arc of the hash ring need redistribution — O(K/N) keys moved on average compared to O(K) for traditional hashing - **Virtual Nodes**: each physical node assigned multiple positions on the ring (100-200 virtual nodes typical) — reduces variance in key distribution from O(K/N ± √(K/N)) to near-uniform across heterogeneous machines - **Replication**: keys replicated to R successor nodes clockwise from primary — provides fault tolerance (R-1 node failures tolerable) and read load distribution **DHT Protocols:** - **Chord**: each node maintains finger table pointing to nodes at exponentially increasing distances — lookup resolved in O(log N) hops by routing to the finger closest to the key without overshooting - **Kademlia**: XOR-based distance metric (distance = ID₁ XOR ID₂) with k-buckets storing contacts at each distance range — iterative lookup queries α nodes in parallel, converging in O(log N) rounds; used in BitTorrent - **Pastry**: nodes organized by proximity of node ID prefixes — routing table resolves one prefix digit per hop (O(log₂ᵇN) hops for base-2^b IDs); locality-aware routing minimizes physical network latency - **CAN (Content-Addressable Network)**: maps nodes to a d-dimensional coordinate space — routing follows coordinate space neighbors in O(d × N^(1/d)) hops; higher dimensions reduce path length at cost of larger routing tables **Performance and Reliability:** - **Lookup Latency**: O(log N) overlay hops, each potentially crossing the physical network — optimizations: caching popular keys, proximity-aware routing (prefer physically nearby nodes), and iterative-parallel lookups reduce practical latency to 2-4 network round trips - **Churn Handling**: frequent node joins/leaves require routing table maintenance — stabilization protocols periodically verify successor/predecessor links; aggressive churn (>50% node turnover per hour) degrades lookup reliability - **Load Balancing**: hot keys (popular content) overload their responsible node — solutions include key replication to multiple nodes, caching at intermediate routing nodes, and hash space power-of-two-choices - **Consistency**: eventual consistency under concurrent updates — applications requiring strong consistency must layer consensus protocols (Paxos, Raft) over the DHT substrate **Distributed hash tables represent the foundational building block for decentralized distributed systems — enabling scalable key-value storage, peer-to-peer file sharing, and distributed databases without single points of failure or centralized coordination bottlenecks.**