Chord

Summary

Chord functions as a protocol and algorithm for a peer-to-peer distributed hash table. It enables efficient key/value storage and retrieval by assigning keys to nodes in a network, ensuring data can be found quickly even as nodes join or leave. Chord is particularly useful in decentralized applications such as file-sharing systems, distributed file systems, and in implementing resilient, scalable distributed systems. Its time complexity for lookup operations is O(logn), where n is the number of nodes in the system. Chord distinguishes itself from other systems with its simplicity, provable correctness, and scalability, mainly due to its consistent hashing mechanism that minimizes key reassignment when nodes change.

Implementation

Form a ring

The simple ring-forming algorithm in Chord, as depicted, is designed to facilitate the location of the successor node responsible for a given key. The process is straightforward: a node�� n queries the next node in the ring, referred to as its “successor,” to find the appropriate successor of an identifier�� id. �� id is within the range of no� n and its successor, node� n responds with its successor. Otherwise, the query is forwarded along the ring to the successor of� n, and the process repeats until the correct node is found. This basic algorithm underpins Chord’s distributed data location strategy, ensuring efficient data retrieval in a scalable peer-to-peer network.

Scalable key lookup

The image depicts a Chord protocol’s finger table for node 8 and illustrates how a query traverses the Chord ring. Each entry in the finger table points to the first node that succeeds the start of the finger’s interval on the identifier circle. For instance, finger k corresponds to the node that succeeds the identifier (n + 2^(k-1)) modulo 2^m. The successor is the node’s immediate successor on the identifier circle, while the predecessor is the immediate predecessor on this circle. When a node receives a query for an identifier, it uses the finger table to find the closest preceding node to the identifier and forwards the query to it. This process continues until the node responsible for the identifier is reached. This efficient lookup method greatly reduces the number of hops needed to find a successor, especially in large networks.

Create, join, stablization, fix finger, and check predecessor

Creating the Chord Ring (n.create()): A node initializes the Chord ring by setting its predecessor as nil and its successor as itself. It effectively creates a new network where it is the only node in the ring.

Joining the Chord Ring (n.join(n’)): When a node wants to join an existing network, it invokes the join function. It sets its predecessor as nil and finds its successor by using find_successor on a known node in the Chord network. This process is called join stabilization, where the node integrates itself into the network and updates the relevant successor and predecessor pointers of neighboring nodes.

Stabilization (n.stabilize()): Each node runs stabilize periodically to learn about new nodes and to ensure the network correctly reflects the set of nodes. During stabilization, each node checks with its successor for the successor’s predecessor p and decides if p should be its successor. It also informs the successor about its presence so the successor can update its predecessor if necessary.

Fixing Fingers (n.fix_fingers()): Each node periodically updates its finger table, which is a set of shortcuts to facilitate faster lookups. The fix_fingers function incrementally updates these entries to point to the correct nodes, improving the efficiency of lookups.

Checking Predecessor (n.check_predecessor()): This function is called periodically to check if the predecessor has failed. If the predecessor has failed, it sets the predecessor to nil. This is a cleanup process to maintain the correctness of the ring in case of node failures.

Callback

I implemented Chord using ns3, which only provides an asynchronous API for sending and receiving messages across the network. This asynchronous approach, while not standard, significantly accelerates the simulation. However, it complicates handling any Remote Procedure Call (RPC) that expects a return value. For instance, the find_successor function, which returns the successor of a given key ‘id’, poses a challenge:

successor = n.find_successor(id);

This function triggers a send_packet operation to send a message to another node. However, since this function does not block, the return value isn’t immediately available. Instead, the return value is received through another message from the node that finds the successor to key ‘id’. Due to this asynchronous call and the delay in receiving return values, any function issuing a send_packet operation must be split into two distinct functions: one for initiating the send operation and another for handling the return value. This division disrupts the flow of logic and complicates code readability.

To address this, I designed a callback mechanism to streamline the logic. I utilized a hashmap to associate each transaction_id with a function object capable of processing the return value of the sent packet. When the response to the sent packet is received, the corresponding function in the hashmap is invoked directly, eliminating the need to manually manage the return value handling in the code.

An example of this process is illustrated below, where the callback is registered and stored in a hashmap.

// Each node also runs check predecessor periodically,
// to clear the node’s predecessor pointer if n.predecessor has failed;
// this allows it to accept a new predecessor in notify.
void PennChord::checkPredecessor()
{
  // std::cout << ReverseLookup(GetLocalAddress()) << " checkes predecessor " << "\n";

  // check the last time the node receive the pingRsp from its predecessor
  // if the currentTime - lastTime > threshold, the node think its predecessor failed and set its predecessor to itself
  if(Simulator::Now() - lastTimePredecessorRsp > this->DEAD_TIMEOUT) {
    SetPredecessor(GetLocalAddress(), ReverseLookup(GetLocalAddress()), PennKeyHelper::CreateShaKey(GetLocalAddress()));
  }  

  // register a callback to update the lastTimePredecessorRsp
  uint32_t transactionId = GetNextTransactionId();
  transactionIdToCallbackMapSync.put(
    transactionId,
    [this](PennChordMessage message, Ipv4Address sourceAddress, uint16_t sourcePort) -> void {
      this->lastTimePredecessorRsp = Simulator::Now();
    }
  );

  // ping predecessor
  std::string pingMessage = "I'm your successor. Reply if you are alive.";
  Ptr<PingRequest> pingRequest = Create<PingRequest>(transactionId, Simulator::Now(), m_predecessor->nodeIp, pingMessage);
  m_pingTracker.insert(std::make_pair(transactionId, pingRequest));
  Ptr<Packet> packet = Create<Packet>();
  PennChordMessage message = PennChordMessage(PennChordMessage::PING_REQ, transactionId);
  message.SetPingReq(pingMessage);
  packet->AddHeader(message);
  m_socket->SendTo(packet, 0, InetSocketAddress(m_predecessor->nodeIp, m_appPort));

  checkPredecessorTimer.Schedule(checkPredecessorTimeout);
}

The callback is called when the returned value is sent back with a message.

void PennChord::ProcessPingRsp(PennChordMessage message, Ipv4Address sourceAddress, uint16_t sourcePort)
{
    // do something
    try{
      transactionIdToCallbackMapSync.get(message.GetTransactionId())(message, sourceAddress, sourcePort);
      transactionIdToCallbackMapSync.erase(message.GetTransactionId());
    }catch(std::out_of_range & e) {
      std::cout << e.what() << std::endl;
    }
    // do something else
}

Reference

Chord paper: https://pdos.csail.mit.edu/papers/ton:chord/paper-ton.pdf