[chord] DHASHCLIENT_SUCCLIST_OPT

[Benjie Chen]

in case you didn't pay attention to the commit e-mail, here is a
change i made... let me know if you have a problem with this. right
now this is just something that gets turned on by a flag.

one more comment at the end that was not in the original commit e-mail.

------------

3. added another client option DHASHCLIENT_SUCCLIST_OPT

   this option lets the dhashcli code in client.C to check if the
   successor list contains the entire world (i.e. pred = last succ).
   if this is the case, it actually skips lookups and find successor
   lists of other nodes from clntnode->succlist.

   this optimization really only works for small ring, where number
   of nodes equals to the number of successors. for a larger ring, you
   can't cheat.

   this is a hack. probably the better thing to do would be to cache
   all the nodes we know and optimisitcally use this table. on insert
   we'd need to include a condition, something like "only insert this
   block if your predecessor is XXX". if the conditional insert fails,
   we would need to do a real successor list lookup. 

   i know we discussed implementing this in the app level. right now
   this is a bit harder to do, because we would need to pass more than
   just a vec<chordID> back to user on retrieve. to be effective, we'd
   need to notify app if a node died as well, and also add this
   conditional insert. furthermore, short-lived apps would not be able
   to maintain a very good table.

-------------

if we want to implement such as location cache later so it works
when number of nodes is larger than nsucc, i think it should be in the
chord code base, because of the fact that the server would be able to
keep a much better table than any app would, especially short-lived
apps.

you then enter a different world in terms of performance: i can now
pipeline large amounts of data (at least compared w/ before) to each
node in my app. it used to be that each insert would be latency dominated.

also, it makes vivaldi look better, because i can skip routing and 
immediately pick a good successor to use in dhash. it used to be 
that vivaldi wouldn't give you as much benefit because the get 
successor call sometimes would go to a far away node.

benjie


-- 
benjie chen
benjie at lcs.mit.edu