Distributed hash table: Difference between revisions

Revision as of 15:05, 2 October 2023

Revision as of 04:17, 6 November 2023

Line 1:

{{Short description|Decentralized distributed system with lookup service}}

{{Citations needed|date=September 2020}}

A '''distributed hash table''' ('''DHT''') is a [[Distributed computing|distributed system]] that provides a lookup service similar to a [[hash table]]. [[Key–value pair]]s are stored in a DHT, and any participating [[node (networking)|node]] can efficiently retrieve the value associated with a given [[Key (computing)|key]]. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. ''Keys'' are unique identifiers which map to particular ''values'', which in turn can be anything from addresses, to [[Electronic document|documents]], to arbitrary [[Data (computing)|data]].<ref name=StoicaEtAl2001>{{Cite journal | last1 = Stoica | first1 = I. | author-link1 = Ion Stoica| last2 = Morris | first2 = R. | last3 = Karger | first3 = D. | author-link3 = David Karger| last4 = Kaashoek | first4 = M. F. | last5 = Balakrishnan | first5 = H. | author-link5 = Hari Balakrishnan| title = Chord: A scalable peer-to-peer lookup service for internet applications| doi = 10.1145/964723.383071 | journal = ACM SIGCOMM Computer Communication Review | volume = 31 | issue = 4 | pages = 149 | year = 2001 | url = http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf |quote=A value can be an address, a documentdocumentfggf, or an arbitrary data item. }}</ref> Responsibility for maintaining the mapping from keyske to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to [[scale (computing)|scale]] to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

DHTs form an infrastructure that can be used to build more complex services, such as [[anycast]], cooperative [[Web cache|web caching]], [[distributed file system]]s, [[Domain name system|___domain name services]], [[instant messaging]], [[multicast]], and also [[peer-to-peer file sharing]] and [[content distribution]] systems. Notable distributed networks that use DHTs include [[BitTorrent (protocol)|BitTorrent]]'s distributed tracker, the [[Kad network]], the [[Storm botnet]], the [[Tox (protocol)|Tox instant messenger]], [[Freenet]], the [[YaCy]] search engine, and the [[InterPlanetary File System]].

Line 8:

== History ==

DHT research was originally motivated, in f

DHT research was originally motivated, in part, by [[peer-to-peer]] (P2P) systems such as [[Freenet]], [[Gnutella]], [[BitTorrent]] and [[Napster]], which took advantage of resources distributed across the Internet to provide a single useful application. In particular, they took advantage of increased [[Bandwidth (computing)|bandwidth]] and [[hard disk]] capacity to provide a file-sharing service.<ref>{{cite journal |last1=Liz, Crowcroft|display-authors=et al |title=A survey and comparison of peer-to-peer overlay network schemes |journal=IEEE Communications Surveys & Tutorials |date=2005 |volume=7 |issue=2 |pages=72–93|doi=10.1109/COMST.2005.1610546 |citeseerx=10.1.1.109.6124 |s2cid=7971188 |url=http://www.cl.cam.ac.uk/teaching/2005/AdvSysTop/survey.pdf }}</ref>

DHT research was originally motivated, in part, by [[peer-to-peer]] (P2P) systems such as [[Freenet]], [[Gnutella]], [[BitTorrent]] and [[Napster]], which took advantage of resources distributed across the Internet to provide a single useful application. In particular, they took advantage of increased [[Bandwidth (computing)|bandwidth]] and [[hard disk]] capacity to provide a file-sharing service.<ref>{{cite journal |last1=Liz, Crowcroft|display-authors=et al |title=A survey and comparison of peer-to-peer overlay network schemes |journal=IEEE Communications Surveys & Tutorials |date=2005 |volume=7 |issue=2 |pages=72–93|doi=10.1109/COMST.2005.1610546 |citeseerx=10.1.1.109.6124 |s2cid=7971188 |url=http://www.cl.cam.ac.uk/teaching/2005/AdvSysTop/survey.pdf }}</ref>

These systems differed in how they located the data offered by their peers. Napster, the first large-scale P2P content delivery system, required a central index server: each node, upon joining, would send a list of locally held files to the server, which would perform searches and refer the queries to the nodes that held the results. This central component left the system vulnerable to attacks and lawsuits.