Distributed hash table: Difference between revisions

Revision as of 03:10, 12 April 2025

Revision as of 01:23, 10 June 2025

Line 36:

The structure of a DHT can be decomposed into several main components.<ref>Moni Naor and Udi Wieder. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/dh.pdf Novel Architectures for P2P Applications: the Continuous-Discrete Approach] {{Webarchive|url=https://web.archive.org/web/20191209032152/http://www.wisdom.weizmann.ac.il/~naor/PAPERS/dh.pdf |date=2019-12-09 }}. Proc. SPAA, 2003.</ref><ref>Gurmeet Singh Manku. [http://www-db.stanford.edu/~manku/phd/index.html Dipsea: A Modular Distributed Hash Table] {{webarchive|url=https://web.archive.org/web/20040910154927/http://www-db.stanford.edu/~manku/phd/index.html |date=2004-09-10 }}. Ph. D. Thesis (Stanford University), August 2004.</ref> The foundation is an abstract [[Keyspace (distributed data store)|keyspace]], such as the set of 160-bit [[string (computer science)|string]]s. A keyspace [[Partition (database)|partitioning]] scheme splits ownership of this keyspace among the participating nodes. An [[overlay network]] then connects the nodes, allowing them to find the owner of any given key in the keyspace.

Once these components are in place, a typical use of the DHT for storage and retrieval might proceed as follows. Suppose the keyspace is the set of 160-bit strings. To index a file with given {{Var serifmvar|filename}} and {{mvar|data}} in the DHT, the [[SHA-1]] hash of {{mvar|filename}} is generated, producing a 160-bit key {{mvar|k}}, and a message {{math|''put''(''k, data'')}} is sent to any node participating in the DHT. The message is forwarded from node to node through the overlay network until it reaches the single node responsible for key {{mvar|k}} as specified by the keyspace partitioning. That node then stores the key and the data. Any other client can then retrieve the contents of the file by again hashing {{mvar|filename}} to produce {{mvar|k}} and asking any DHT node to find the data associated with {{mvar|k}} with a message {{math|''get''(''k'')}}. The message will again be routed through the overlay to the node responsible for {{mvar|k}}, which will reply with the stored {{mvar|data}}.

The keyspace partitioning and overlay network components are described below with the goal of capturing the principal ideas common to most DHTs; many designs differ in the details.