CANChord: Reimplementing Chord in Python and adding CAN Realities to improve performance
This blog post was written by Jordan Holland and Elena Lucherini for the final project in COS518.
Introduction
There was a boon of peer-to-peer (P2P) networking research in 2001 resulting in multiple new peer-to-peer protocols. Two of the most influential papers introducing peer to peer protocols were published at this time: Chord, a distributed lookup protocol used to efficiently locate items in peer to peer networks, and CAN, a distributed infrastructure for addressing content.[1][2] In this blog post, we describe the Chord and CAN protocols, examine our experience of re-implementing the basic Chord protocol from scratch, and finally look at the performance improvement of combining the idea of realities from the can distributed infrastructure with the routing simplicity of Chord.
What exactly are CAN, Chord, and realities? Why develop peer to peer systems in the first place? We will explain these concepts in the following sections.
Background
Let’s start by introducing the unique properties and goals of peer to peer systems. Many classic distributed systems take the from of a central authority which manages, replicates, and distributes content. While simple, this design has a few clear drawbacks: namely the trust put in a single authority, exposing a single point of failure, and difficulty scaling. P2P protocols attempt to mitigate many of the issues that arise from the single central authority, instead creating a system where each node in the system has equivalent functionality and runs the same software.
These designs distribute trust across each node in the system instead of a single point, exploiting parallelism to scale services. For each added node in the system we have additional CPU, network, and disk resources which in theory makes the system more resilient to failures. P2P network architectures do have drawbacks. While many centralized architectures rely on specialized, reliable hardware, nodes in a P2P network have to be assumed to be unreliable, running on commodity hardware that can fail at any point. Furthermore, nodes are free to join or leave the network at any point.
P2P systems have been successfully used in some popular areas including popular (and sometimes illegal) file sharing systems. Today we’ll examine and implement one of the most influential P2P protocols, Chord, and then test if we can improve it by merging the protocol with another P2P protocol developed and released around the same time, CAN.
Chord
One critical function of a P2P network is being able to efficiently find an item on an ever-changing network. The Chord protocol attempts to solve this problem with just one operation: given a key, it maps that key onto a node. To better understand Chord, we need to examine exactly how it works. Chord uses consistent hashing to evenly distribute nodes and keys that need to be looked up across a given identifier space. We leave the specific details of consistent hashing out of this post, as there is an entire line of research specifically on the subject. For simplicity, know that consistent hashing takes an input of arbitrary length and outputs a random string of a fixed length. This randomness allows for an even distribution over a given space. Below is a simple sample of how both a node and a key would be mapped to the same identifier space in Chord.
We’ve mentioned an “identifier space” a few times now, but not fully defined what this means. In Chord, nodes and keys are organized in an “identifier space”, which is simply just a range of numbers that keys and nodes can be assigned to. This range can vary based on the size of the system. In Chord, the identifier space is organized as a ring, rather than a line, allowing for the identifier space to wrap around itself. An example of a Chord ring with the identifier space [0,7] is seen below. For now, pay attention only to the Chord identifiers, shown in blue.
Now that we understand how Chord evenly distributes arbitrary keys and nodes to an identifier space and understand exactly what a Chord identifier space looks like, we can piece together the puzzle of how Chord organizes nodes and keys across a given Chord ring. Above, the same Chord identifier space is populated with the node identifier and key identifier we hashed earlier, as well as a few more nodes and keys introduced, all shown in red. Here we note that both keys and nodes can map to the same identifier.
A few questions arise now that we have nodes and keys mapped to the same space. What nodes own which keys? How do we lookup a key in the system? Let’s start with which nodes own which keys, which is actually pretty simple. Each key is stored at the closest node at or after (clockwise) it on the Chord ring. For example, in the above Chord ring, node 1 stores key 1, node 3 stores key 2, and node 0 stores key 7. How do we correctly lookup a key in the system? Each node keeps track of its successor (the node after it on the ring), and forwards the request for any key it does not have to its successor. An example of a query fulfilled this way is shown above, this time in green.
The above lookup in green is slow (O(n)), as it is just traversing a linked list. The authors realize this and speed up queries by introducing a finger table (read: routing table) for each node that halves the distance between the current location in the ring and the key at each hop, working as a binary search and finding keys in O(log n) time. Each entry i in a node’s finger table points to the successor of identifier n + 2ᶦ on the identifier space. Again, this finger table has two benefits; it allows a node to forward a request for a key reducing the distance by roughly half, and each node knows more about the area near it than farther away. Below is an example of a Chord network with finger tables shown. By keeping more state Chord is able to reduce the number of total hops to O(log n).
CAN
Now that we know the basic concepts behind Chord, let’s take a brief look at Content-Addressable Networks, or CAN. The protocol provides a scalable indexing system similar to a hash table that can be used to retrieve nodes in a P2P network. In CAN, nodes see the network as a d-dimensional torus where each node owns a portion, or zone of the available area. Keys are mapped to this virtual coordinate space by using a hash function. The node that owns the zone where the hashed key falls owns the key.
Let’s take a look at an example. For simplicity, we refer to a 2-dimensional [0,1] x [0, 1] coordinate space divided among 5 nodes, denoted by letters A to E.
Each node manages all the keys that fall into its zone, specified by the coordinates in blue. For example, node B manages the [0.5, 1] interval on the first dimension and [0, 0.5] on the second dimension. A key that is hashed to (0.7, 0.2), as in the example above, is owned by node B.
What about routing? Nodes maintain a routing table with virtual coordinates of their neighbors, which are identified by looking at their coordinates in the space: in a d-dimensional space, two nodes are neighbors if their coordinate zones overlap in d-1 dimensions. Each node therefore maintains a total of 2d neighbors. Routing is achieved by simple greedy forwarding: each node chooses to forward a message to its neighbor with coordinates closest to the message destination.
Let’s introduce one more example. Suppose node F receives a lookup request for a key owned by node D. The figure below shows a possible path taken by the message. First, F forwards the request to its neighbor B, which in turns forwards it to A. Finally, A sends the request to its neighbor D.
This routing protocol is simple, but not very efficient. What CAN really excels at is keeping the number of neighbors constant as the size of the network increases, as per node state only depends on the dimensions of the coordinate space. What we found most interesting about CAN is the idea of realities. With multiple realities, the system is mapped to more than one coordinate space, all independent from each other. Nodes are assigned a zone in each of the spaces, as we see in the image below.
This also implies that nodes maintain a different neighbor coordinate set for each reality. Additionally, each key is stored in a different node for each reality. While this increases per node state for each reality added in the system, it can decrease latency and improve fault-tolerance and availability. The greatest advantage of realities is that nodes can route messages in any reality. In the example above, communication between nodes A and D has a shorter path in reality 2 than in reality 1, reducing the number of total hops in the taken.
System Overview
We start by implementing basic Chord as described above, replicating the results found in the original Chord paper. We then implement and test our idea of adding “realities” to Chord for both replication and to reduce the average number of hops taken for a lookup in our system.
Simulation
Ultimately, we chose to implement our project in Python. Although there are multiple peer to peer simulators built, almost all of them have the Chord protocol built in. Furthermore, we could not find any peer to peer simulator in Python, so we wanted to fill that gap. The lack of a specific peer to peer simulator in Python forced us to implement and simulate Chord using a basic discrete event simulator framework, SimPy. [3]
While this idea seemed good at first, it proved to be more work than we thought, which was in some ways painful but did teach us about how to build a larger system in a generic event simulator. We ultimately had to implement the nodes, messaging, latency, and remote procedure calls as events in our simulator. We are able to run networks of up to 500 nodes in size locally, though increases in network size significantly blow up the run time of our code due to messages being processed as events between the nodes.
One of the biggest challenges of implementing a peer-to-peer network simulator from scratch was coming up with a good distribution that could simulate real latencies. Latency varies widely across applications and is influenced by an array of factors, such as geographical location and medium of communication. In our evaluations, we ultimately decide to simulate latency values according to the prototype implementation of Chord presented in the original paper deployed across different sites in the United States. Specifically, we consider an an average round-trip time between nodes of 60 ms. Latencies are generated with a normal distribution of mean equal to 60 ms and scale equal to 5 ms.
Evaluation
Having built a Chord simulator, we first want to replicate the load balancing and path length results from the paper. We run all simulations locally.
First, we examine the load balancing capabilities of Chord in our system. Below we see a comparison of the original results (above) and our results (below) for the number of keys per node in a system. Both graphs show the 1st, 50th, and 99th percentile of the number of keys per node when varying the number of keys in the system. The only real difference in the two figures are the number of nodes, where the original system considers a 10,000 node network, we only consider a 100 node network. Our simulator exhibits the same general trend of all networks having nodes without any keys, the 50th percentile increasing, and the 99th percentile having an increasingly larger amount of keys.
Next, we look at the PDF of the number of keys per node for a 100 node network with 1000 keys. This experiment was run 10 times for verification of results. Once again we see that the results in the original paper (above) largely match the ones in our simulated networks (below).
We also compare our path length experiments to the paper’s path length results. First, we examine the path length of a given lookup in the system as the size of the system (number of nodes) increases. Although we use a smaller range of values, we see that our results directly match the results in the paper.
Below we see the PDF of the path length of a network of size 2⁶. This graph was most helpful in determining if our network was performing lookup correctly, as we could make sure the peak of the path length matched the expected value of .5 log(n) (log base 2), where n is the number of nodes in the network. For reference, the Chord PDF (above) shows the path length in the case of a 2¹² node network. We see that our PDF (below) directly matches the original results!
Next, we look at the simulated values of lookup latency with networks of 10, 30, 60, 70, and 100 nodes. Below, we compare our simulated latency results with the real-world experimental results found in the Chord paper. We see that our simulated results differ numerically from those in the paper for smaller networks. This is an expected result: despite simulating the average round-trip times specified in the paper, our simulator does not take into account the proper message processing times and other possible delays in the network. However, both behaviors and median values match in networks with 60 or more nodes.
Finally, for completeness we compare the lookup failure rate of our simulated system with the one in the original Chord paper. We run the simulation on a 128-node network varying the node failure rate. Once again, the results match our expectations as the median lookup failure rate seems to have a linear behavior. Note that the authors wait for the network to stabilize after the node failures before starting to count failed lookup messages. Because of the limitations of our simulator we include all failed lookups, hence the numerical difference.
CANChord: Improving Chord
After ensuring our base chord simulation was correct (which took much longer than expected), we moved on to implementing realities in Chord. Specifically, we look to implement realities as a form of replication that can also shorten the path length. For N realities, there are N Chord rings where each node has a unique PID. In a production environment, this could be implemented by hashing the IP of the node n times for the nth reality. For purposes of our simulation environment, we simply randomly choose the ids from available ones. Each node contains the keys for its PID at each reality. Ultimately, this means that 3 realities does not guarantee that each key is replicated 3 times, as the same node could be responsible for a key in reality 1 and 3 in a 3 reality CANChord network. All clients forward requests to the 1st reality, and the others are hidden (only known by the nodes). When a CANChord node receives a request, it checks each of its realities to see if it owns the key for the request in any of them. If it does not own the key for the request, it forwards the request to the node nearest to the key on a reality by checking all realities.
We are particularly interested in the effect that realities have on path length. Below, we reproduce the path length graphs we used to validate our Chord implementation, with the exception that each of the graphs uses 3 realities instead of vanilla Chord (1 reality). We see promising results, that in the PDF the path length is generally 1 less hop than before. Furthermore, we see that as the network size increases, the median path length increases at a slower rate!
Conclusions
Implementing Chord in a generic discrete event simulator was a useful exercise that taught us more than we would have learned had we leaned on a well-established P2P simulator. However, this choice led us to take much longer on the initial part of the project than expected, as we had to implement more moving parts than we would have if we had chosen a P2P simulator. Ultimately, we were able to reproduce the Chord paper’s original results, which was the base goal of the project. Furthermore, we were able to show that implementing CAN realities in Chord is a novel way to provide replication in Chord while decreasing the overall path length. It was exciting to see our improvements on Chord actually have some overall impact on path length without changing the simplistic Chord protocol that made it so popular.
Our code is available at: https://github.com/JordanHolland/cos518_project
References:
[1]: https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf
[2]: http://conferences.sigcomm.org/sigcomm/2001/p13-ratnasamy.pdf
