Transcript [Title: Wow them with a great pun here]

Merging separate Chord
structures into a single
harmonious whole
An integral part of the quest to
add more musical puns to The
ConCert Project
The problem:
• Bob: Sridhar, I’m afraid I have some bad news…
We’re shutting down the ConCert Project. As a
result, we’re going to have to let you go.
• Me: What? Why?
• Bob: As you know, we’ve tried as much as possible
to ensure that the various components of the
ConCert Project were named after musical terms.
Indeed, creating suchly-named software was the
true reason for its conception, “certified code” and
“grid computing” merely being the phrases we used
to get funding. Conductor, Lightharp, and Tempo
were great successes in terms of this true goal-• Me: And don’t forget Iktara!
• Bob: --yes, and even Iktara. However, we’ve
recently run into some problems.
Backstory, cont.:
• Bob: Specifically, the Chord protocol, which we’d been
using to implement our distributed hash tables… well, it
works alright in most cases, but we just can’t see any
way to efficiently merge two isolated Chord networks
together. Now, Karl and I have been searching and
searching, but it turns out there aren’t any other
distributed hashtable systems with musical names. It
seems there’s no hope.
• *Bob reaches, sobbing, for a red button, located under a
sign which reads “To terminate the ConCert Project,
press here”*
• Me: Ah, that’s too bad. Guess I’ll have to switch to
spending my summer waking up whenever I want,
working on projects of my own choosing, and generally
wallowing in copious amounts of free time… Well, see ya!
• *I head towards the door*
• Bob: Oh, to see my life’s work come to naught like this!
Approaching the point…
• Me: Your… your life’s work? What about all that stuff with
ML?
• Bob: Oh, that was all just a precursor for the planned
ConCert subproject, ML-Ody. With ML-Ody, I’d finally do
ML right.
• Me: ML-Ody? Tell me, in what ways would ML-Ody
improve on Standard ML?
• Bob: Basically, it would be Haskell, but with a musical
name. Also, we’d probably convert a good portion of the
SML userbase over to ML-Ody.
• Me, excitedly: Replace SML with Haskell? Oh man! That’d
be… That’d be great! Ok, I’ll tell you what… I’ll do some
research and see what I can do about salvaging this
Chord protocol, looking for ways to, uh, to efficiently
merge the… the whatnot… and the… Replace SML with
Haskell? Whoohoo!
• *I run out of the room giddy, and, I must admit, drooling*
The problem, sans
ridiculous lies:
• The Chord protocol gives us a nice way of
implementing distributed hash tables
• However, Chord gives us no easy way of
merging separate such DHTs (as we would
like to do in the case of, for example, a
temporary network partition)
• Therefore, we seek a way to do such
merging both efficiently and with minimal
modifications to the basic Chord protocol
Just what is the Chord
protocol?
• The Chord protocol allows us to do a single
task: For a given key, identify the node
responsible for that key’s data
• This is done in such a way that
responsibility is evenly distributed, lookups
are efficient, and nodes can join and leave
the network with minimal disruption
• There is no direct support for many
features which might be desirable in a DHT
(e.g., redundancy of responsibility). Chord
merely provides a simple layer on top of
which distributed hash tables, among other
things, can be implemented
Details about the Chord
protocol
• High-level overview of the Chord protocol:
• Every node on a network has an identifier derived by
hashing its IP address using SHA-1; These identifiers
are ordered in a circle
• Based on these identifiers, the nodes are ordered in a
ring structure, each maintaining links to its successor
and predecessor on the ring (a link consists of both an
identifier and an IP address)
• Keys are also given identifiers by hashing them (we
will often use the word “key” to refer to this generated
ID, and similarly for “node”, as determined by the
context)
• The node responsible for some key K is the one whose
identifier first follows or is equal to K’s on the
identifier circle; this node is denoted successor(K)
More details about the
Chord protocol
• By chasing successor links around the
ring, we can look up the node responsible
for a particular key in linear time (in the
size of the network)
• Meh. Can’t we do better?
• Yes. By having each node N maintain links
(known as “fingers”) to successor(N+1),
successor(N+2), successor(N+4), etc., we
can arrange for logarithmic time lookup,
sending messages bouncing across the
identifier circle from node to node till
eventually the right one is found
A constructive proof of the
Chord protocol’s
existence, cont.:
• By having each node run a stabilization
function periodically, the ring structure is
maintained after nodes join or leave (or
fail) with accurate successor and
predecessor links
• Basically, stabilization looks for cases where
x.successor.predecessor != x, and then fixes
successor and predecessor links as appropriate
• Finger links are also occasionally recalculated,
but we don’t try to ensure perfect accuracy of
fingers at all time. As long as successor links
are accurate, lookups will succeed, and as long
as finger links are “reasonably” accurate,
lookups will be “reasonably” efficient
The problem, redux:
• The Chord protocol gives us a nice way of
implementing distributed hash tables
• However, Chord gives us no easy way of
merging separate such DHTs (as we would
like to do in the case of, for example, a
temporary network partition)
• Therefore, we seek a way to do such
merging both efficiently and with minimal
modifications to the basic Chord protocol
My proposed solution
• Ghosts:
• Every node can now contain multiple instances of
(Successor, Predecessor, Fingerlist), instead of just
one. Each instance will be associated with unique tag
bits, and one instance will be designated as the “live”
one, the others being considered “ghosts”. The
network in which a node’s live instance lives is its
“primary” network.
• A node still contains only one set of (Key, Data) pairs.
These will consist only of those pairs for which its live
instance is responsible (in its primary network).
• When an external source tells an instance of node N
in network A about the existence of network B, node
N checks to see if it has an instance in network B. If
it does not, N may choose (more details on this later)
to make B its primary network.
A thing of genius, or at
least of good-enough
• Jumping ship:
• To switch primary networks from A to B,
node N creates a new instance with new
tag bits, and designates it as its live
instance. This instance then joins
network B.
• Once in network B, node N checks to
see which of its (Key, Data) pairs it is
still responsible for. These it keeps; the
rest it “injects” into network B, passing
them along to the appropriate nodes to
take care of
Why it works
• Lookups:
• Links will now consist of (Identifier, IP addr, Tag),
instead of just (Identifier, IP addr)
• Messages sent across links always include the tag
bits of the link
• When a node receives a request to lookup data, it
checks to see if it has the wanted (Key, Data) pair. If it
does, it returns the Data, of course. If it doesn’t, it
forwards the request, as before
• Only now, in order to decide to whom to forward the
request, it uses the tag bits sent to it with this message.
The request is forwarded through the fingerlist of the
corresponding instance. Thus, a message which arrives
at N from network X will be forwarded by N back into
network X, even while N maintains pseudo-membership in
multiple networks.
I can practically smell that
Haskell of New Jersey…
• Spreading the revolution:
• When node N jumps ship from network A to network B, it
should tell some of its comrades in A to do the same
• When N’s ghost instance in A receives a request from a node
to newly join A, it should reply saying “No, join B (my primary
network) instead”
• Eventually, A will become a “ghost network”, with no live
nodes
• Once a node thinks it has an instance living in a ghost
network, it would be appropriate to delete that instance
• If a node receives a message with tag bits which do not
correspond to any of its current instances, it must assume
the message was intended for an old, erroneously deleted
instance. In this case, it should contact the sender, explain
the situation, and politely ask the sender to join the
receiver’s new primary network and try again.
• “politely”? I’ve gone over the anthropomorphizing edge. I better
hurry up and finish this presentation…
Issues to flesh out:
•
When does a node decide to jump ship?
•
Idea: Give nodes some way of estimating the size of their network. Have nodes
jump ship only if this would result in moving from a smaller primary network to a
larger one.
•
•
What is the exact protocol for telling other nodes to jump ship?
•
Idea: After jumping ship, contact every node on the old fingerlist with a command
to follow suit. Just as messages bouncing around the fingerlist reach their
destination in logarithmic time with high probability, merging can be expected to
take about logarithmic time with this method.
•
•
Caution: Any individual node is going to receive a lot of redundant commands to jump ship
with this method. We have to ensure that we deal with these appropriately, instead of
creating new instances for each (causing the “jump ship” command to loop around the old
network forever)
When does a node decide it is on a ghost network/it is appropriate to
delete an old instance?
•
•
Caution: Have to make sure to appropriately handle edge cases of merging two
approximately equally-sized networks
This depends on the answer to the above question. With the above solution, a
node jumping ship from a K-sized network could wait log(K) rounds before
deciding to delete its old instance
How many tag bits are necessary?
•
1 could very well be good enough, handling a single jump at a time. 2 bits could
maybe handle several different concurrent jumps (e.g., network A begins to
merge into network B, but before this finishes network B decides to merge into
network C). It’s not clear, though, that this would actually work.
Why it works, cont.
(aka, Does it work?):
• Currently searching for proofs of “correctness”, for
some value of “correctness”
• Proofs that lookups continue to succeed at all points
during merging
• Proofs that ghost instances are always eventually
deleted appropriately
• Proofs that the snake never tries to eat its tail (i.e.,
network A doesn’t try to merge into network B while B
simultaneously tries to merge into A)
• Or perhaps just a proof that temporary snake
autocannibalism is tolerable, with lookups continuing to
succeed and a stable network eventually reached
• Proofs that multiple simultaneous network merges
work smoothly
• Though perhaps this won’t be much of an issue in
practice
Conclusion
•
•
•
•
•
•
•
•
•
•
*Bob, sitting alone in office, grows curious. Finally, he is overcome. He
reaches for, and presses, the red ConCert Project termination button*
*Nothing happens*
Bob: I suppose it’s a good thing the system requires simultaneous
synchronized presses from Karl and me, for authentication.
*I run panting into the room*
Me: I did it! I did it! I’ve fixed the protocol! Start the true referential
transparency! Cue the type classes! Begin the—
Bob: You have concrete results proving the correctness of your fix, right?
Me: Er, well, not quite yet, no…
Bob: Well, I would like to see some of those. Still, did you find anything
interesting about Chord in your research?
Me: Why, yes, actually. It turns out the name is based on the geometrical
concept of a chord; you know, a line connecting any two points on a
circle. That connects with its system of redirecting lookup requests using
“fingerlists”. So I guess it wasn’t really a musical name after all.
Bob: No one must ever know!
• FIN