[Seeks-users] How many threads ?

[Loic D. <lo...@da...>]

Hi,

I'm still strugling and unsure if the implementation of the chord
algorithm should be done using event based I/O instead of the sequential
approach described in the papers and currently implemented in
DHTVirtualNode.

While thinking about it, I realize that in the current implementation
there needs to be a thread for each lookup of the host responsible for a
given key. In a million node DHT, such a lookup will take up to 10
seconds (see below for the reasoning). Even in a much smaller DHT it
takes a lot longer than is acceptable for a blocking operation.

As a result, the number of threads required by the current implementation is

1) for stabilisation
2) for handling incoming requests
N) for N simultaneous requests

That is 2 + N threads total.

Cheers

* Execution time of the routing and access algorithms

  The finger table is refreshed one entry after the other independantly.
     Updating is done by looking up the host responsible for a given key.
  The successor list is refreshed by asking the successor.
  The successor and the predecessor is refreshed by a simple decision based
     on an incoming message.

  Finding the host responsible for a give key is the longest operation
  as it requires to contact log(N) nodes. Let say a DHT contains 1
  million nodes, ~13 nodes will be contacted to figure out which host
  needs to be contacted for a given finger table entry. A contact is
  made of a) asking for the closest predecessor, b) asking its
  successor to the predecessor retrieved in step a).  How long will
  these 13 * 2 = 26 contacts take ? Assuming each connection timesout
  when not receiving an answer within 300ms, the total time to
  complete the operation is 26 * 300 = 7800ms, 7.8ms.