theory - Simple basic explanation of a Distributed Hash Table (DHT) -

could 1 give explanation on how dht works?

nothing heavy, basics.

ok, they're fundamentally pretty simple idea. dht gives dictionary-like interface, nodes distributed across network. trick dhts node gets store particular key found hashing key, in effect hash-table buckets independent nodes in network.

this gives lot of fault-tolerance , reliability, , possibly performance benefit, throws lot of headaches. example, happens when node leaves network, failing or otherwise? , how redistribute keys when node joins load balanced. come think of it, how evenly distribute keys anyhow? , when node joins, how avoid rehashing everything? (remember you'd have in normal hash table if increase number of buckets).

one example dht tackles of these problems logical ring of n nodes, each taking responsibility 1/n of keyspace. once add node network, finds place on ring sit between 2 other nodes, , takes responsibility of keys in sibling nodes. beauty of approach none of other nodes in ring affected; 2 sibling nodes have redistribute keys.

for example, in 3 node ring first node has keys 0-10, second 11-20 , third 21-30. if fourth node comes along , inserts between nodes 3 , 0 (remember, they're in ring), can take responsibility half of 3's keyspace, deals 26-30 , node 3 deals 21-25.

there many other overlay structures such use content-based routing find right node on store key. locating key in ring requires searching round ring 1 node @ time (unless keep local look-up table, problematic in dht of thousands of nodes), o(n)-hop routing. other structures - including augmented rings - guarantee o(log n)-hop routing, , claim o(1)-hop routing @ cost of more maintenance.

read wikipedia page, , if want know in bit of depth, check out coursepage @ harvard has pretty comprehensive reading list.