Chord-like protocol in Ruby pseudocode

chord.rb

#
# Chord-like network overlay protocol based on the eon (http://github.com/thomaslee/eon)
# source code, which was itself based on the Principles of Distributed Computing paper
# and Pamela Zave's pseudocode from "How to make Chord correct":
#
# http://en.wikipedia.org/wiki/Chord_(peer-to-peer)
#
# (Prefer Zave's proposed changes to anything in the other papers + Wikipedia.)
#
# Haven't bothered with finger tables yet, though they should be a trivial addition.
#
# All operations assume single-threaded operation of the local node.
#
# Node IDs can be derived by e.g. hashing host+port (eon uses SHA-1)
#
# eon's RPC code transparently converts between node IDs and proxies/local nodes:
# we send node IDs over the wire whenever we see a "node" in the API (e.g. in notify_predecessor)
# & deserialize them to either a proxy object or `self`.
#

#
# This is fine for a small & reliable network, but probably not for larger/unreliable networks.
# Also, per Zave's paper this requires a "stable base" of at least 4 nodes.
#
MAX_SUCCESSOR_LIST_SIZE = 3

def between(first, value, last)
  # true if 'value' falls between 'first' and 'last' (exclusive) on the consistent hash ring.
  # details depend on size of ID. see between(...) in eon here for a naive Java impl:
  # https://github.com/thomaslee/eon/blob/master/eon-chord/src/main/java/co/tomlee/eon/chord/local/LocalNode.java#L413-L423
end

class LocalNode
  #
  # RPC method: called to locate the node that immediately follows the given ID
  #
  def find_successor(id)
    if between(self.id, id, self.successor.id)
      self.successor
    else
      closest_preceding = self.closest_preceding_node(id)
      if closest_preceding.id == self.id
        self
      else
        closest_preceding.find_successor(id)
      end
    end
  end

  #
  # RPC method: what's the immediate successor of this node?
  #
  def successor
    if successors.empty?
      self
    else
      # TODO liveness check?
      successor_list.first
    end
  end
  
  #
  # RPC method: what's the immediate predecessor of this node?
  #
  def predecessor
    @predecessor
  end
  
  #
  # RPC method: what are all the nodes that succeed this node (up to MAX_SUCCESSOR_LIST_SIZE successors)
  #
  def successor_list
    @successors
  end
  
  #
  # RPC method, but more or less a no-op on the receiver side.
  #
  # Exists so remote nodes can check we're alive (in practice this could be
  # a simple reachability test, doesn't necessarily warrant an RPC method)
  #
  def ping; end
  
  #
  # RPC method: called by a remote node to tell us that it believes itself to be
  # our immediate predecessor.
  #
  # `sender` is a proxy to a remote Node, or `self`.
  #
  # This is basically Pamela Zave's pseudocode from "How to make Chord correct",
  # plus some tweaks that appeared to be necessary for a network consisting of
  # a single peer. I *think* Zave's model assumes enough peers are present for
  # such edge cases not to matter. This tweak may or may not break correctness
  # per her model, but it makes it possible to play with smaller networks.
  #
  def notify_predecessor(sender)
    return if !@ready

    if self.predecessor.nil?
      #
      # no predecessor yet, so the sender's claim is as good as any
      #
      self.predecessor = sender
    elsif sender.id != self.id
      #
      # FIXME why ping before we've checked on whether the new candidate is
      # closer than our current predecessor?
      #
      begin
        self.predecessor.ping
      rescue DeadPeer
        #
        # sigh, current predecessor is dead.
        # fortunately we can assume the sender is alive given it just made this RPC call
        #
        self.predecessor = sender
        return
      end
  
      predecessor_is_self = self.id == self.predecessor.id
      sender_is_self = self.id == sender.id
      sender_is_closer_than_predecessor = between(self.predecessor.id, sender.id, self.id)
      
      if (predecessor_is_self && !sender_is_self) || sender_is_closer_than_predecessor
        #
        # always prefer to confer local predecessorship to a node other than the local node,
        # or to the sender if the sender is closer to us on the ring than our current predecessor.
        #
        self.predecessor = sender
      end
    else
      # everything stays the same
    end
  end
  
  #
  # Called for a stand-alone peer (i.e. we're creating a new network)
  #
  def start
    @successors = []
    @predecessor = nil
    @ready = true
  end
  
  #
  # This join method is also inspired by Zave's paper, but with tweaks for small networks
  # (against her requirements RE: a stable base for correctness)
  #
  def join(peer)
    successor = peer.find_successor(self.id)
    successors = successor.successor_list
    self.successors = [successor] + successors
    @predecessor = nil
    @ready = true
  end
  
  #
  # Another Zave-inspired method. Called periodically to check surrounding peers & fix up
  # our successor list.
  #
  def stabilize
    return if !@ready
    
    #
    # keep trying while we have a non-empty successor list
    #
    while self.successor.id != self.id
      successor = self.successor
      begin
        new_successor = successor.predecessor
      rescue DeadPeer
        #
        # current successor is dead -- move on to the next peer in the successor list
        #
        @successors.shift
        next
      end
      
      new_successors = nil
      if !new_successor.nil? && between(self.id, new_successor.id, successor.id)
        #
        # our current successor's predecessor appears before the local node in the ring.
        # that means the successor's predecessor should be our new successor.
        #
        begin
          new_successors = [new_successor] + new_successor.successor_list
        rescue DeadPeer
          #
          # a peer appeared between this node and its successor, but is now dead ...
          # let's assume `successor` is legit for now.
          #
        end
      end
      
      if new_successors.nil?
        #
        # no new successor, or potential new successor appears to be dead.
        # pull the successor list from the current successor
        #
        begin
          new_successors = [successor] + successor.successor_list
        rescue DeadPeer
          #
          # successor has died since our last RPC call -- move to the next peer in the successor list
          #
          @successors.shift
          next
        end
      end
      
      self.successors = new_successors
      begin
        self.successor.notify_predeccessor(self)
        break
      rescue DeadPeer
        #
        # our successor died before we could notify it of our existence.
        #
        @successors.shift
      end
    end
  end
  
  #
  # Only ever called directly & locally (i.e. not an RPC method)
  #
  # Pseudocode implementation from the paper never returns `self`
  #
  def closest_preceding_node(id)
    candidate = nil
    successors.each do |successor|
      if between(self.id, successor.id, id)
        candidate = successor
      end
    end
    candidate.nil? ? self : candidate
  end
  
  #
  # Set the predecessor to nil when RPC calls to the predecessor fail
  #
  def fix_predecessor
    return if !@ready

    @predecessor = nil
  end
  
  #
  # Called for e.g. `self.successors = [...]`
  #
  def successors=(successors)
    @successors = successors
    while @successors.size > MAX_SUCCESSOR_LIST_SIZE
      @successors.pop
    end
  end
end