Talk:Distributed hash table

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Internet (Rated B-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Internet, a collaborative effort to improve the coverage of the internet on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Inconsistency[edit]

Second sentence of the article says: Each node is analogous to a bucket in a hash table.

There is no expression "bucket" in the hash table article.

It now reads 'array slot', but would 'record' be more appropriate? Nazlfrag 07:46, 1 March 2007 (UTC)
The hash table article uses array index and (now) bucket as well as array slot. Between these I don't much care; maybe we should look up with Knuth uses. Record is probably not appropriate -- to me this implies an instance of a structure like a (key,value) pair rather than a position in the hash table's array. --Nethgirb 08:29, 1 March 2007 (UTC)
Array index seems best, but I'll leave it for someone else to change. I agree with your rejection of record.Nazlfrag 11:54, 15 July 2007 (UTC)
Bucket was the right term to use — it is a chain of records that share a common digest, as produced by the hash function. Array index merely refers to the fact that digests are used as indexes to the array of buckets (bucket pointers.) — 213.141.154.11 (talk) 14:46, 13 October 2008 (UTC)
You are correct, damnit, I knew bucket was correct but I was thinking of making the page more accesible to those who didn't know. Luckily the page is much better now, but thanks for reminding me that bucket should have stayed as the proper description. Nazlfrag (talk) 15:42, 18 January 2010 (UTC)

To do list[edit]

  • Give example topology
  • Give example of typical use -- associate object with key, store object at owner of key, retrieve later by looking up owner.
  • Discuss need to maintain O(log n) of the "right" neighbors for fault tolerance
  • Reference all 4 original DHT papers

Nethgirb 01:53, 16 August 2005 (UTC)

I get very very sleepy reading these k index i O(log n) mathematics, even though I'm soon a MSc. Could someone replace these parts with normal words? The articles doesn't have to be technical scientific papers in how to express facts. "... which is fundamental in graph theory", well I could've sweared the author was in that field. And the Background part is written in past tempus. Why? I never really used any of these programs, once existed they will always exist. Gnutella for instance wasn't. It is. Used or not. Interesting background though, but tempus "must" be changed. I swear DHT's aren't more complicated than Hash tables, so why make the article much more complicated and mathematic? After reading the article I still don't know how it works, I know the background and k index i and O(log n). Not good. The preceding unsigned comment was added by 130.158.78.7 (talk • contribs) 14:46, 8 December 2005 (UTC).

I disagree. True mathematics might confuse most people, but this article desperately needs a section detailing how the results in the overlay networks section were achieved, or at least a reference.


It is in past tense due to the fact it is discussing origins of the concept, which happened in the past. The background section is fine as it is. On your other point, I don't see how to simplify this. To describe O(log n) is an article in itself, and the description of the keyspace as a circle couldn't be more clear. The article describes the process accurately, if in a somewhat complex manner. It's a complex subject. Nazlfrag 07:57, 1 March 2007 (UTC)

What happens if a node goes offline ?[edit]

Hi everyone,

in the Structure section of this article it is said that the (k,data) tuple is moved to a node which is responsible for k according to the keyspace partitioning. Now, P2P systems are very dynamic systems. What happens if this node, where (k,data) is stored goes offline? Are there any replication mechanisms in place? And if so, how can duplicates and inconsistence or unavailability then be avoided?

Thanks for your answers.

Manfred

Hi Manfred: Most DHTs that store files use replication. There are several methods and it would be a good addition to this article to have them described. The most common method is to store replicas on nodes that are nearby in the keyspace to the owner of the key k. So for example you can visualize the Chord DHT's keyspace as a circle, and each node is located at some point on the circle. The replicas of a node v's data are stored at the r nodes clockwise around the circle starting at v, where r is the number of replicas, often 4 or 8.
Maintaining consistency when data is mutable is trickier. One technique is to have all writes handled by a single node, the owner of k. If you want really strong guarantees (which as far as I know most DHT implementations don't provide), these are basically classical distributed systems problems not specific to DHTs; see two phase commit.
Nethgirb 00:49, 9 February 2006 (UTC)

DEPOT[edit]

Can we please have a link to DEPOT?

To keep the number of links manageable, I think we should only include links to projects which are notable, which probably means that the project has a significant number of users (either other researchers or regular people). Does DEPOT fall into that category? Also, if you were thinking that it should go in the "Applications employing DHTs" section, can you provide a reference showing that DEPOT uses a DHT? Thanks. --Nethgirb 20:12, 19 September 2006 (UTC)

DHT in Tangosol[edit]

The Tangosol product has a DHT called "partitioned cache service" [[1]] that meets the definition of a "decentralized distributed systems that partition ownership of a set of keys among participating nodes", and "route[s] messages to the unique owner of any given key." Channelsurfer 00:03, 7 November 2006 (UTC)

Thanks for the link. It does seem Tangosol splits up the data among nodes, but the partitioning of an abstract keyspace is one of the, er, key features of a DHT. Another important DHT feature is that the information about who owns what keys is itself distributed: no one node knows everything. It may be that Tangosol Coherence does these things, but they are not described on the page you gave or on the others I looked at. In the absence of further documentation, I'd say we should leave it off the list; otherwise the list tends to become cluttered and less useful. --Nethgirb 09:46, 7 November 2006 (UTC)
My name is Cameron Purdy, and I work at Tangosol. Sorry about the apparent previous link spam; I'll try to make sure that never happens again. Regarding DHT in our software, we dynamically partition the key space in a manner that can guarantee non-ambiguous ownership (and line of ascension), even during and after node failure. That is how the data are partitioned (since with key / value pairs, the value naturally goes with the key, therefore if the key domain is partitioned, the value domain follows respectively ;-). There is no global (or replicated) directory of keys; only the owner (and ordered backups) of a key knows that that key exists and what its value is. We had customers in production in June of 2002 on our DHT implementation, and at the time, I hadn't even heard of the term "Distributed Hash Table"; for lack of a better term, we just called it dynamic partitioning. As the explanation in the article of DHT is a bit cryptic (or I am simply not technical enough to understand it), I cannot say for certain that the algorithm that we use is the same as the one (or ones) suggested in this article; I would love to learn more about this particular part of the field and you can contact me at my first name at tangosol dot com and I will send you my contact info, etc. Having looked over the DHT article, the DHT implementation in Tangosol Coherence pre-dates (by at least a year) all of the articles and most of the implementations that you have referenced, and so I am quite surprised that you were not aware of Coherence. As for the academic initiatives in this space, I heard of one funded (a multi-million dollar grant) by the US government in 2003 to a professor who was going to "invent" such technology; I repeatedly emailed him to tell him about what our customers were already using in production, but he never responded. (8 Nov '06)

Hi Cameron, Looks like Tangosol deserves a mention in the article at least as related work. I'm curious about how the process of discovering who owns a key works. I could imagine a design like this: one coordinator knows how the keyspace is partitioned among participating nodes, e.g., node 128.2.1.4 handles keys 0-100, node 68.4.35.30 handles keys 200-307, etc. Then, to get a key's value -- or even just decide whether the key K has an associated value -- you ask the coordinator which node owns K, and then you ask that node directly about K. Alternately, the coordinator's info could be replicated at all nodes. Either way, there is no global directory of keys or their contents; but at least one node knows something about all the nodes in the system, in particular, who handles which keys. This general scheme is used in a system called LH*, a 1996 paper from HP Labs [2] (see Sec. 3.5). Is this how Coherence works?

DHTs are even more distributed. Not only is no one aware of all keys; in addition, no node is aware of all nodes. Usually a DHT node knows only O(log N) of the N other participants. So most queries end up being routed through a series of participants before they find the node that has the data (if any) associated with the target key. Those O(log N) neighbors have to be chosen with care in order to ensure that queries do not involve too many nodes. Since there is so little state at each node, DHTs can be very scalable, to a virtually unlimited number of nodes and high rates of node joins and leaves (e.g., each node participates for just a few minutes). It is debatable how many applications actually need such extreme scalability, but there has been some specialized adoption as discussed in the article.

I would be interested to talk/email with you to learn more about how DHTs and Tangosol relate (certainly, the description in the article does need some improvement!) -- perhaps I'll drop you a note... --Nethgirb 00:47, 10 November 2006 (UTC)

Θ(log n) : What's 'theta'?[edit]

Under 'Properties' it says:

most commonly, Θ(log n) of the n participants (see below)

...which defines n as the number of participants, but what's the Θ signify? Is it the name of some function, or a magic number to multiplied with log n.

And what base is the log?

Also later in the article, under 'Overlay network', there's a bunch of Degrees, that begin with 0.

Degree O(1), route length O(log n) ...

Should those 'ohs' be 'thetas' or vice-versa?

What I'd like to see is that any function is named as such (or linked to a relevant article), as soon as it's used, instead of being taken for granted. Example:

"the number of nosehairs on a goat may be approximately determined by Blackguard's function B(p), where p is how much money, in pennies, the goat cost."

And the boldface Blackguard's function would link to a wiki that defines the function, but if the function has no article, it should be defined on the spot:

"the number of nosehairs on a goat may be approximately determined by Blackguard's function, which is defined B(p) = (9999+p^2)/p + pi/p, where p is how much money, in pennies, the goat cost."

--AC 09:13, 7 February 2007 (UTC)

See Big O notation. "Big O" and "Big Theta" notation both tell you about the growth rate of a function, within constant factors, in this case as a function of n. At the high level \Theta(\log n) means "about \log n", and O(\log n) means "about \log n or smaller" . "Constant" here means "independent of n". Since constant factors are hidden, the base of the log doesn't matter: whatever constant base you put there, the resulting value will only change by a constant factor. You're right, it should be linked to the big O article at the first use. --Nethgirb 16:43, 7 February 2007 (UTC)


these notations o(log n) and theta log(n) are usually used to denote time and space complexity of the algorithmsGayatri.capricorn (talk) 17:05, 25 April 2011 (UTC)Gayatri

Confusing[edit]

This article needs a serious cleanup, I have no idea what the author is trying to say. The concept of DHT should be explained in a more simpler manner. —The preceding unsigned comment was added by 68.146.236.11 (talk) 11:23, 12 February 2007 (UTC).

Can you say more specifically which parts you found confusing? Thanks! --Nethgirb 18:15, 12 February 2007 (UTC)

Hi Nethgirb. I am a user of Bit Torrent. I see DHT in all of the BT Clients. I never knew what it meant. I searched Wikipedia, it looks like this page written for engineers by engineers a normal person wouldn't understand what DHT is. —The preceding unsigned comment was added by 71.198.210.123 (talk)

Thanks, that helps --Nethgirb 22:11, 20 February 2007 (UTC)

As a layman, this page doesn't tell me any of the benefits of DHT when used in a BitTorrent client. It's all features and no benefits. I suggest there needs to be a plain Engliah introduction saying what DHT is *for*? R. sparts (talk) 22:04, 5 December 2007 (UTC)

That's because "DHT" is the generic term for the concept, as used in hundreds of different protocols/programs; it's not a functional/tangible protocol, it's just a building block for other systems. What BitTorrent in particular uses DHTs for is covered on BitTorrent protocol#Distributed trackers, not here. -- intgr [talk] 23:48, 6 December 2007 (UTC)

I think a diagram of the keyspace and overlay from one node would help immensely. I get the keyspace (i think!) but then the method by which the nodes route for specific keys isn't clear - the algorithm as described *sounds* linear, but i'm assuming that's my misunderstanding from the big-O notation. 64.154.223.249 (talk) 00:46, 28 October 2008 (UTC)

Sorry if I am saying something stupid, but as far as I am concerned, the keywords 'key' and 'value' meaning doesn't match the original value for hash tables. Using the example at the article (and the draw), according to the original meaning, the 'filename' would be the key, and the 'key' (160-bit string) would be the hash. The file content would be the 'value'. If the terms have different meaning for DTH as is seems, it would be nice to give a brief introduction explaining the concepts. Thanks. —Preceding unsigned comment added by 201.58.210.181 (talk) 04:37, 8 January 2010 (UTC)

Info about resilience to attachs[edit]

I'm interested in info/references discussing DHT resilience against an hostile attack. That is, a powerful attacker joining malicious nodes and giving away false data or routing info. Jcea 16:43, 12 April 2007 (UTC)

Try googling byzantine DHT. Also: Awerbuch and Scheideler, "Towards a scalable and robust DHT", SPAA 2006. This [3] is also related, though I don't think it was ever published; you might contact the authors directly. --Nethgirb 20:53, 12 April 2007 (UTC)
Just happened to notice this as well. Not DHT-specific but I would guess the techniques might transfer... --Nethgirb 13:34, 13 April 2007 (UTC)

Formatting for Formula Θ(log n)[edit]

Formatting for formula Θ(log n) is bad. The article uses a single <math> element to code the formula. This method is straightforward, and MediaWiki TeX should render the formula well. Unfortunately MediaWiki TeX does not render the formula well. MediaWiki TeX puts no space between 'log' and 'n'.

There is also a problem with the hyperlink for the formula. The link to Big_O_notation should apply just to the 'Θ' character.

I played around with the formatting. I came up with 2 ways to restrict the hyperlink text and extend the space. The 1st way uses 2 <math> elements. The 2nd way uses 3 <math> elements.

Formatting Description
\Theta(\log n) The way it is now
\Theta(\log n) Restricts hyperlink to Θ, but still no space. Requires 2 <math> elements.
\Theta(\log \mbox{ } n) Some space, but not enough. Requires 2 <math> elements.
\Theta(\log  n) Looks best. Requires 3 <math> elements.


I favor the 3-<math>-element method. It is the most complex, but I do not think it will matter. The formula is semantically correct. I do not think that anyone will want to edit the formula. And the 3-<math>-element method looks the best.

Preferences? Is there a simpler way to achieve extended spacing in the formula?


TT    23:00, 23 May 2008 (UTC)

Maybe no one will edit it soon, but people still have to read the wiki markup, and people may create other formulas so it would add complexity there. Also, I think it's OK to have the Big O link for the whole formula. After all, the whole formula is written in Big O notation. So I would suggest a variant on your third option: \Theta(\log \mbox{ } n) One math element, and I think it's plenty of space before the n. --Nethgirb (talk) 22:19, 25 May 2008 (UTC)
Don't use math tags if you don't need them. What's wrong with the simplest form? Θ(log n) -- intgr [talk] 00:32, 26 May 2008 (UTC)
Nothing as far as I'm concerned, though to me Θ(log n) is just as good --Nethgirb (talk) 10:05, 26 May 2008 (UTC)
Agreed; I was just making a point with regards to the overuse of <math></math>. -- intgr [talk] 15:30, 27 May 2008 (UTC)

Some content[edit]

Resource discovery activity involve searching for the appropriate resource types that match the user’s application requirements. Recent advances in the domain of decentralized resource discovery have been based on extending the existing DHTs with the capability of multi-dimensional data organization and query routing. Majority of the efforts have looked at embedding spatial database indices such as the Space Filling Curves (SFCs) including the Hilbert curves, Z-curves, k-d tree, MX-CIF Quad tree and R*-tree for managing, routing, and indexing of complex Grid resource query objects over DHT networks. Spatial indices are well suited for handling the complexity of Grid resource queries. Although some spatial indices can have issues as regards to routing load-balance in case of a skewed data set, all the spatial indices are more scalable in terms of the number of hops traversed and messages generated while searching and routing Grid resource queries.

-- moved in from peer-to-peer.   M   19:12, 14 June 2009 (UTC)

BitTorrent Clients[edit]

There is a request for not posting the names of bittorrent clients in the "Applications employing DHTs" section, still the names of utorrent and transmission have been mentioned. This may create a confusion that only these two(and vuze) support DHT and others don't. So I am going to remove these references if there are no objections. —Preceding unsigned comment added by 117.194.196.91 (talk) 05:00, 4 July 2009 (UTC)

I totally agree, but won't touch the page myself. Please feel free to clean up the list. -- Cghost (talk) 22:19, 21 November 2009 (UTC)
Another user has recently deleted all BT clients except Deluge from that list. In the interest of neutrality, I have also deleted Deluge.
Strangely, an outdated editor's comment at the top of that section mentions a link to Comparison of BitTorrent software, the link to which did not exist anywhere in the article at the time of the deletion of the other clients. Deleting the client list without the existence of that link seemed counter-productive, so I have re-linked to the current location and version of that wiki (Comparison of BitTorrent clients) and updated the comment.
Personally, I am not against the inclusion of a very short list of notable clients, consisting solely of Vuze/Azureus (first client to implement DHT, natively compatible with Azureus DHT and also compatible via plugin with "mainline" DHT) and the "mainline" client (second, using only its own different and normally incompatible implementation). Arguments for and against are welcome.
69.181.227.133 (talk) 08:56, 29 December 2009 (UTC)

DHT History[edit]

The current discussion of history is misleading. It could be read as implying that Cord, CAN, Pastry, and Tapestry invented DHTs in 2001, but there were earlier systems. I propose revising the "history" paragraph as follows:

Old text:

The first four DHTs—CAN, Chord,[1] Pastry, and Tapestry—were introduced about the same time in 2001. Since then this area of research has been quite active. Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network.

Proposed new text:

The first DHT implementation—the Beyond Browsers system[2]—was introduced in 1998 and was based on Plaxton, Rajaraman, and Richa's algorithm.[3] In 2001, four systems—CAN, Chord,[4] Pastry, and Tapestry—ignited DHTs as a popular research topic, and this area of research remains active. Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network.

Md4567 (talk) 14:42, 2 February 2010 (UTC)

Looks good; Be bold in updating pages. If someone disagrees, they will create a discussion themselves and revert (WP:BRD) -- intgr [talk] 18:40, 2 February 2010 (UTC)
I disagree that Beyond Browsers was the first DHT, because its architecture is fundamentally hierarchical (as is clear from the referenced paper) and thus it is not decentralized, and fails to meet the first of the three DHT properties outlined in the article. Javalangstring (talk) 22:05, 6 July 2010 (UTC)


Errors in this article[edit]

I just read this article and it seems to be incorrect or misleading on several aspects.

1. It confuses peer-to-peer system with DHT. A DHT is a distributed datastructure, peer-to-peer systems often implement such a DHT, but have additional properties like skaling to larger number of nodes and and and... most things in the article said about DHT are in fact just properties of peer-to-peer systems.


2. It should be made clear that neither Napster nor Gnutella implement a DHT structure. Also Freenet did not do soin the beginning.


3. DHT was invented in 1997 before peer-to-peer for content distribution. [5]

-> DHT was not motivated by peer-to-peer in the beginning!

Sadly this error of mixing up DHT and peer-to-peer system is something that was already done in scientific papers (or at least authors not being very clear, the paper for Kelips is just one example in that direction).

Quicksilver 132.230.150.44 (talk) 08:56, 30 November 2010 (UTC)

You're right about what you're saying: the article does not differentiate enough between P2P and DHT systems. As for gnutella, it does implement a DHT system - or at least, the mojito DHT is very closely bound to gnutella and makes searches by hash possible, which the original network does not in its current form. (As the search by hash feature is not supported by most clients.)
mfg, OldDeath - 18:25, 30 November 2010 (UTC)

Mojito DHT is not Gnutella, but a Kademlia p2p network implemented by Limewire. This seems to be independent of Gnutella. Gnutella as in original just floods searches out, so there is no guarantee for a hit if the file is there -> Gnutella itself is not DHT. Quicksilver 132.230.150.44 (talk) 16:04, 6 December 2010 (UTC)

It might not be gnutella and be able to operate separately, however, it has been designed as an extension for gnutella to replace the flooding based search for hashes (that hasn't even been implemented in most of the major clients). So in fact, it is only a solution for one single flaw of gnutella, not a solution to be used for itself.
mfg, OldDeath - 03:16, 12 December 2010 (UTC)

So how does it work exactly?[edit]

Okay so all I'm hearing is that golden word "decentralization" every sentence but I still don't understand how I can connect to the swarm without a central node telling me what IPs to connect to.

I understand this system is decentralized, that is fine, but how a completely decentralized system can be organized is my question. If I run, lets say a P2P program that uses DHT, and I search for the word "london", which IP will my computer first connect to and why? How will my computer know which IP out of the 4 billion to first connect to and request the hashes of that keyword I searched for? I really don't get it.142.59.42.197 (talk) 04:34, 11 April 2011 (UTC)

Typically you need one peer to start off the search. You can get it multiple ways; as far as I know, the most common way is just for the torrent program you're downloading to have a list of 'superpeers' or people who volunteer to act as a node. It isn't completely decentralized, but it's a decent solution. It would also be 'possible' to brute force every IP out there, though I can't think of why anyone would do this. Google is your friend! 140.193.135.22 (talk)

  1. ^ Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.
  2. ^ Renu Tewari, Mike Dahlin, Harrick Vin, and John Kay.Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet. University of Texas at Austin Computer Sciences Department Technical Report number TR98-04, February 1998.
  3. ^ C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, Newport, Rhode Island, pages 311-320, June 1997.
  4. ^ Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.
  5. ^ C. Plaxton, R. Rajaram, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1997.