= DHT =

A DHT or Distributed Hash Table is a distributed system that provides a look up
service, similar to that of a [[hash_table]]. The difference however, is the
distributed, self organizing nature of such a datastructure. The keys are
distributed in such a manner that any disruption of nodes causes minimal
disruption to the availability of the data.

DHTs are used in cooperative web caching, distributed file systems, domain name
services, instant messaging, and peer-to-peer file sharing. DHTs are used by
BitTorrent, Freenet, and [[IPFS]].

== Structure ==

A DHT is made up of several components

* Abstract keyspace
  * IE all 160bit strings
  * Partitioned across all participating nodes
* Overlay network
  * TCP/IP protocol to allow nodes to find each other
  * Allows node to query network for any vlaue

=== Insertion ===

Some _filename_ and _data_ exist. A SHA-1 hash is taken of _filename_ and
produces a key, _k_, in the specified keyspace. The message `put(k,data)` is
sent to any node in the network, and is forwarded till the node responsible for
key _k_ is found, and then that node stores the _data_ and _key_.

=== Retrieval ===

A node wants to find some _filename_. They take the SHA-1 hash of _filename_
and produce some key, _k_. `get(k)` is sent to any other node, and the message
is propogated through the network till the node responsible for _k_ is found,
and replies with _data_.

=== Keyspace Partitioning ===