Talk:Distributed hash table

From Wikipedia, the free encyclopedia

Citation
This page was cited by BBC News

Contents

[edit] Inconsistency

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)

[edit] To do list

  • 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)

[edit] What happens if a node goes offline ?

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)

[edit] DEPOT

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)

[edit] DHT in Tangosol

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)

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

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 Θ(logn) means "about logn", and O(logn) means "about logn 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)

[edit] Confusing

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)

[edit] Info about resilience to attachs

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)

[edit] Formatting for Formula Θ(log n)

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
Θ(logn) The way it is now
Θ(logn) Restricts hyperlink to Θ, but still no space. Requires 2 <math> elements.
Θ(log n) Some space, but not enough. Requires 2 <math> elements.
Θ(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: Θ(log 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)