Chord vs Kademlia

Jingyi Liu, Pachara Sawettamalya

We explore two approaches to peer-to-peer distributed hash tables with provable guarantees: Chord and Kademlia. Chord and Kademlia are both popular peer-to-peer distributed hash table (DHT) protocols that form the foundation of distributed systems, yet they work in very distinct ways. We first provide a brief summary of both systems.

Chord was first proposed in the paper: “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications.” The idea of Chord is simple yet powerful: hash nodes and keys into a circular ring, and each node will be responsible for its adjacent interval. Despite its simplicity, there are many subtleties hidden underneath Chord’s abstraction. Each chord node maintains its own: 1) successor pointer to its closest node in the clockwise direction, 2) predecessor pointers to its closest node in the clockwise direction, and 3) a finger table that routes a key look-up request to a peer node. To handle node failures, Chord suggests storing multiple successors for each finger of the look-up table.

Kademlia was first proposed in the paper “Kademlia: A Peer-to-Peer Information System Based on the XOR Metric.” Like Chord, Kademlia also uses consistent hashing, so the node IDs and hashed keys share the same key space. Instead of using the clockwise distance on a ring to determine how (key, value) pairs are stored and where fingers should point, Kademlia uses the XOR metric to determine the distance between nodes and stores (key, value) pairs on the k nearest nodes. Each node also stores pointers to nodes in exponentially increasing distances: it stores k nodes that are distance 2^I to 2^{I+1} from it for each I in [0, m-1] where m is the number of bits for the key space. These sets of k nodes are called k-buckets. Intuitively if we view the key space as a binary tree, then this is equivalent to storing k nodes for each subtree that diverges from the subtree that contains the node ID, and these k-buckets form the routing table for key or node lookup. The k nodes in the k-buckets provide tolerance for node failures since having one node in each of its k-buckets already allows for a successful lookup.

In this project, we run experiments on the performance of Chord and Kademlia under no failure. Both Chord and Kademlia must be able to handle three types of operations: client’s put and get requests, and nodejoins. We note that under no failure, it suffices for Chord to store only one successor pointer for each of its fingers and for Kademlia to store one node in each of its k-buckets.

How do Chord and Kademlia handle operations?

Let’s first discuss how Chord and Kademlia handle each operation: client’s put and get, and nodejoins.

1. put requests: a client can insert a (key, value) pair via its local node.
   Chord: to handle a put request (k,v) to a local node n, n decides if it should keep (k,v) by hashing the key k and sees if it lies on the portion of the ring n is responsible for. If it does, n stores (k,v). If not, n relays put(k,v) to the next node (via a successor, a finger, etc.) In short, the key-value pair (k,v) will eventually be stored at the successor of k on the the size of the ring.
   Kademlia: to handle a put request (k,v) to a local node n, n looks up k closest nodes to the key in the network by doing an iterative lookup process, and then it sends a store RPC to all these nodes. We now describe the lookup process in more detail: when a node is trying to look up k closest nodes to a key or a node ID (recall that the keys and the node IDs lie in the same key space), it first picks P closest nodes from its routing table and sends parallel Find_Node requests, which asks each node which k nodes they know of in their routing table closest to the key. After it hears back from these nodes and collects the set of k nodes, it resends requests to a new set of P closest nodes that it hasn’t queried before. This process is repeated until the distance to the key does not get smaller, in which case it returns the k closest nodes it has heard of. This is the core lookup process that Kademlia uses for many of its operations. Intuitively, during each round of the lookup process, the distance of the current closest node to the key should decrease by ½, so the lookup process should complete in O(log N) time where N is the total number of nodes in the network.
2. get requests: a client can contact its local node, and query for a value of any key k.
   Chord: upon node n receiving a get request for key k from its client, n hashes the keys and sees if it lies on the portion of the ring n is responsible for. If it does, n should be holding key k; thus is able to answer the client’s request right away. On the other hand, if n does not hold key k, it searches for its furthest peer (in its finger table) in the clockwise direction which does not surpass k, and forwards the client’s request to the corresponding peer who recursively looks up for k. This design choice of Chord can be interpreted as searching for a key through a binary lookup tree via fingers; thus, Chord can satisfy clients’ requests via at most O(log N) hops.
   Kademlia: node n first checks if it stores the <k,v> pair in its cache. If so, it returns to the client immediately. If not, it uses the same iterative process as described previously, but this time, it sends Find_Value requests to each of the nodes it wants to query, which asks each node to return the value if they store the <k,v> pair and if not, return k closest nodes they know of just like the Find_Node request. Node n returns to the client immediately once a node it queries has the <k,v> pair.
3. nodejoins: a new node can join the network to which Chord/Kademlia must gracefully adapt.
   Chord: when a new node n joins, it is possible to trigger various types of mishaps. First and foremost, n must have the correct successor/predecessor pointers, as well as a correct finger table. To this end, n asks for its successor from the node it makes the first contact with. Upon receiving information about its successor s, n asks s about its predecessor and asks s to fill out the finger table.
   More importantly, n joining can cause instability to the Chord ring in multiple ways: (1) it can corrupt successor/predecessor pointers of surrounding nodes, and (2) it can assert itself in some nodes’ finger table. It is worth noting that (1) can cause further instability if left unfixed; as pointers will simply skip n, and (2) can hurt the lookup latency, as in the number of hops, as some lookups will overshoot n. To fix the said issue, Chord introduces periodic stabilization to address issue (1) and finger fixing to address issue (2). It is worth noting that in the event of node failure (which is not within the scope of our project), Chord ring shall become unstable by which nodes’ successor/predecessor pointers and fingers are pointed towards dead nodes. In these events, periodic stabilization and finger fixing, as well as maintaining multiple successor pointers per finger come to the rescue and help circumvent those instabilities. These features are to ensure that in the long run, the Chord ring will be in a stable state again.
   Kademlia: when node n joins, it must have information about one existing node in the network, call it node c. Node n puts c in its routing table and vice versa. Then node n looks up k closest nodes in the network to its own node ID using the iterative lookup process. Note that during the first round of the lookup, the only node that node n can query is node c, which returns k closest nodes to node n’s ID. Node n then puts the k closest nodes it learns from this iterative process in its routing table. Then because node n still has many empty k-buckets to fill, it needs to refresh each k-bucket by looking up a random key in the range of the k-buckets, which fills each of its k-buckets with at least one node if a node exists in that range. Each node that is queried in this process will also put node n in their routing table. It is crucial that each node in the network has at least one node in each of its k-buckets if such a node exists since this invariant is what allows for successful lookups/insertions.

Framework

To facilitate our evaluations, we implemented the evaluation framework from scratch with the following design choices.

1. DHTs: Chord and Kademlia
2. Nodes: we simulate the environment of distributed systems by putting each node in its own thread — with channels between nodes managed by a main thread. To mimic real-world communication models, each node n can send a package to another node n’ via the channel connecting two nodes. Once a package is put into a channel on one end, it suffers a latency (according to some distributions), and arrives at an in-queue of the receiving node. Each node constantly processes a package from its in-queue.
3. Clients: each node is also equipped with a client whose task is to send a put and get requests to the node. All clients reside in the main thread.

For the purpose of evaluation, we establish a controller who reads a sequence of randomly-generated operations from a txt file, and feeds those operations to proper objects (clients, new nodes, etc.). Each object then carries out the designated operations. In particular, a controller reads a txt file consisting of a sequence of operations — one for each line. For each operation the controller reads,

• If it is a put by client c, it tells c to send a put request of (k,v) to its local node.
• If it is a get operation by client c, it tells c to send a get request of key k to its local node, then wait for responses from such node. Upon receiving an output, c writes it to an output file. For the purpose of evaluation, we attach to the output information about the number of hops needed to reach key k.
• If it is a nodejoins operation of a new node n, it creates a new node/thread and have it make contact to the network. In turn, each DHT should gracefully handle the new node joining depending on its own specifications.

Hypotheses

Our project focuses on clients’ lookup latencies, as in the number of hops, in Chord vs Kademlia. By its nature, Chord looks up a key by propagating requests via its fingers. Though some propagations can induce high savings (one Chord’s hop can go very far), it is essential to highlight that those propagations are only in the clockwise direction. Kademlia, on the other hand, propagates client’s put requests in both clockwise and counterclockwise directions; while preserving high savings (one Kademlia’s hop can also go very far.) For these reasons, we propose the following hypotheses.

Hypothesis 1: In the scenario where Chord and Kademlia process the same sequence of operations, we expect to see Kademlia outperform Chord in latencies measured by the number of hops.

As a terminology, we say a lookup is left-biased if the client requests a key that is being stored at a node residing to the left side (i.e. counter-clockwise) of its local node in the Chord ring. In what follows, we generate left-biased lookups specify by a parameter b, where each lookup has probability b to be on the left of the client’s local node. Note that the case of no bias (i.e. each lookup is sampled uniformly) corresponds to b = 1/2.

Hypothesis 2: In the scenario lookups are left-biased, we expect to see a significant increase in Chord’s latencies measured by a number of hops. On the other hand, we expect no statistically significant increase nor decrease in Kademlia’s latencies measured by the number of hops.

We remark that the reason we expect to see no significant changes in Kademlia’s latency is that Kademlia executes lookups in both clockwise and counter-clockwise directions since it is using the XOR distance metric, which is symmetric. As a result, with or without biases, Kademlia’s nodes already load-balance its search to its left and right. This is unlike Chord whose nodes only execute lookups to its right — meaning that when there are left-lookup biases, Chord’s lookup must traverse very far in the ring’s clockwise direction; thus high lookup latencies as in the number of hops.

For the same reasoning, we also pose our third hypothesis.

Hypothesis 3: In the scenario where Chord and Kademlia process the same sequence of operations and lookups are left-biased, we expect to see Kademlia significantly outperform Chord in latencies measured by the number of hops.

Experiment Designs

We investigated the latencies of Chord and Kademlia, as the number of hops in lookups, in various environments. In all of our experiments, we set key length to 12 (the number of bits representing a key or a node ID). To our interest, the evaluation should be conducted when DHTs are at stable states — meaning that every node’s attributes are correct; e.g. in Chord, each node should have the correct successor/predecessor pointers as well as its fingers. Crucially, we propose that each experiment consists of two stages.

• The first stage is an initialization where the controller (1) reads a sequence of nodejoins and insert_keys operations (no look-ups) from an initialization file (usually named init.txt), and then (2) inserts those said nodes and keys, and stabilizes the DHTs. Afterwards, the DHTs should be in stable states. Note that this stage is not a part of the evaluation, but rather is towards building the environment towards an actual evaluation.
• The second stage is an actual evaluation where a controller (1) reads a much longer and complicated sequence of interleaving operations (varied by experiments) from an operation file (usually named normal_ops.txt), and then (2) distributes those operations, one by one, to proper objects which then carry out each operation. For each client’s put request, we record the number of hops for further post-processing.

Each of our experiments is run on 250 key-value pairs in the initialization stage and 200-500 normal operations in the evaluation stage; each is independently sampled to be client’s put, client’s get, and nodejoins with probability p_insertkey, p_lookup, and p_nodejoins respectively. Importantly, to clearly observe performance comparison, we run Chord and Kademlia on the same sequences of operations.

To test our Hypothesis 1, we evaluate Chord and Kademlia in three settings without left-lookup biases.

1. get only: we set (p_insertkey, p_lookup, p_nodejoins) = (0, 1, 0) where the number of nodes in the initialization stage number varies from {20, 50, 100}.
2. get and put only: we set (p_insertkey, p_lookup, p_nodejoins) = (p, 1–p, 0) where there are 50 nodes in the initialization stage, and p varies from {0.05, 0.10, 0.25, 0.50}.
3. get, put and a small rate of nodejoins: we set (p_insertkey, p_lookup, p_nodejoins) = (0.25, 0.75–p, p) where there are 50 nodes in the initialization stage, and p varies from{0.002, 0.01, 0.02}. This should represent 1,5, and 10 nodejoins in expectation.

To test our Hypothesis 2 and Hypothesis 3, we evaluate Chord and Kademlia in three settings with left-lookup biases b.

1. get only: we set (p_insertkey, p_lookup, p_nodejoins) = (0, 1, 0) where there are 50 nodes in the initialization stage, and the left-lookup biases b varies from {0.80, 0.90, 0.95, 0.99}. We also compare the results with that in the same setting with no biases run in evaluation #1.
2. get and put only: we set (p_insertkey, p_lookup, p_nodejoins) = (0.5, 0.5, 0) where there are 50 nodes in the initialization stage, and the left-lookup biases b varies from {0.80, 0.90, 0.95, 0.99}. We also compare the results with that in the same setting with no biases run in evaluation #2.
3. get, put and a small rate of nodejoins: we set (p_insertkey, p_lookup, p_nodejoins) = (0.25, 0.74, 0.01) where there are 50 nodes in the initialization stage, and the left-lookup biases b varies from {0.80, 0.90, 0.95, 0.99}. We also compare the results with that in the same setting with no biases run in evaluation #3.

Experimental Findings

In all of our evaluations, we plot the average number of hops of Chord (blue) versus Kademlia (red) as each experiment’s parameter varies.

Let’s first address an elephant in the room. In all the evaluations/plots that we will provide shortly, we clearly notice a phenomena where the average number of hops are low — usually less than 3.5. First of all, it is worth noting that these numbers are measured as an “average” number of hops. In the actual distributions of the number of Chord’s hops, it is prevalent to see 4 and 5 hops, and 6 hops are not unheard off (5 and 6 hops are indeed significant given that our key length is 12.)

More importantly, the low average number of hops can crucially be explained in theory by the choices of parameters we set. We shall argue for the case of Chord, but Kademlia’s can be reasoned in a similar fashion. In almost every experiment, Chord runs on ~50 nodes in a ring of size 2¹² = 4096. This means each Chord node is responsible for an interval of size roughly 80. As each Chord node’s finger points towards a successor of the finger location, one hop can gain up to ~80 positions more further than the actual finger location. Another interpretation is that each hop can gain extra “savings” of up to ~80 steps which is non-trivial as the ring size is just 2¹² = 4096. To see this, if the lookup takes 5 hops, there is already a 400-stepped savings which accounts for 10% of the ring already. As a result, we can expect a smaller average number of hops when the number of nodes is low, and a higher average number of hops when the number of nodes is high. In fact, this is evident by Experiment 1 — where the growth in the number of hops increases rapidly as of 20, 50, and 100 nodes.

Experiment 1: lookups only; Kademlia outperforms Chord by 0.85 hops on average.

Despite the low number of hops, it is absolutely critical to emphasize that our project solely focuses on the relative performance comparison between Chord and Kademlia rather than the performances of Chord and Kademlia in isolation. As long as such phenomena is explainable (which it is as we did above), it should not cause any worries.

Experiments 2 (left): lookups and insertions only; Kademlia outperforms Chord by 0.76 hops on average. Experiment 3 (right): lookups, insertions, with a small fraction of nodejoins; Kamdelia outperforms Chord by 1.61 hops on average.

Hypothesis 1: In the scenario where Chord and Kademlia process the same sequence of operations, we expect to see Kademlia outperforms Chord in latencies measured by a number of hops.

The first three experiments (1,2, and 3) verify our first hypothesis: Kademlia outperforms Chord in latencies measured by the number of hops. In every test we performed, we saw Kademlia beating Chord in the average number of hops. For instance, in Experiment 1, Chord averages 2.07, 2.52, and 3.11 hops for n=20, 50, and 100 nodes respectively, while Kademlia averages 1.25, 1.72, and 2.19 hops — beating Chord by 0.85 hops in average across the experiment. The trend of Kademlia outperforming Chord by a statistically significant amount persists in the second and third experiments, consistently outperforming Chord on average by 0.76 and 1.61 hops respectively.

Experiments 4: lookups only with left-lookup biases; Kamdelia outperforms Chord by 0.82, 0.93, 1.43, 1.43, and 1.15 hops on average.

Experiment 5 (left): lookups and insertions only with left-lookup biases; Kademlia outperforms Chord by 0.81, 1.26, 1.27, 0.99, and 1.32 hops on average. Experiment 6 (right): lookups, insertions, and nodejoins with left-lookup biases; Kademlia outperforms Chord by 1.60, 1.96, 1.94, 2.02, and 1.86 hops on average.

The next three experiments (4,5, and 6) verifies our remaining hypotheses.

Hypothesis 2: In the scenario lookups are left-biased, we expect to see a significant increase in Chord’s latencies measured by a number of hops. On the other hand, we expect to no statistically significant increase nor decrease in Kademlia’s latencies measured by a number of hops.

Hypothesis 2 is evident by an observation that by introducing left-biases in lookups, Chord’s average number of hops increases by a non-trivial number. Numerically, the average number of Chord’s hops on unbiased lookups vs bias lookups are 2.52 vs {2.82, 3.16, 2.87, 2.95} in Experiment 4; 2.61 vs {3.17, 3.07, 2.94, 2.99} in Experiment 5; and 2.63 vs {3.07, 2.97, 3.08, 3.01} in Experiment 6. Kademlia, on the other hand, sees noisy increases/decreases in latencies that is not statistically meaningful. Specifically, the average number of Kademlia’s hops on unbiased lookups vs bias lookups are 1.72 vs {1.88, 1.73, 1.46, 1.80} in Experiment 4; 1.80 vs {1.90, 1.81, 1.95, 1.68} in Experiment 5; and 2.63 vs {3.07, 2.97, 3.08, 3.01} in Experiment 6. These experimental results truly reflect Hypothesis 2.

Hypothesis 3: In the scenario where Chord and Kademlia process the same sequence of operations and lookups are left-biased, we expect to see Kademlia significantly outperforms Chord in latencies measured by a number of hops.

Hypothesis 3 is also evident by the plots. In particular, experiment 4 sees Kademlia outperforming Chord by 0.82, 0.93, 1.43, 1.43, and 1.15 hops on average where lookups are unbiased, and biased with b = 0.8, 0.9, 0.95, and 0.99 respectively. Experiment 5 and 6 also faces similar trends: Kademlia outperforming Chord by (0.81, 1.26, 1.27, 0.99, 1.32) and (1.60, 1.96, 1.94, 2.02, 1.86) hops respectively. In short, the more left-lookup biases introduced, the wider the performance gap Kademlia’s is to Chord’s.

As a final remark, one might wonder why Chord’s hops does not experience a consistently increasing trend as the biases gets higher. This, again, can be explained in theory by our biased sampling models. The bias only indicates the probability that client’s lookups are to the left of its local node n, meaning that the key’s position is still sampled uniformly among those keys to the left of n. In other words, biases, high or low, is not representative of the proximity (to the left of n) of the keys. As a result, by introducing high biases to the lookups, one can hope to observe increase in the number of hops compared with no biases; yet the magnitude of such increase cannot be directly inferred from the magnitude of b. Hence, it is not a complete anomaly to see a mix of ups and downs of hops as the bias increases.

Conclusion

In this project, we study, implement, and tests two DHTs: Chord and Kademlia. We identify the key distinction of Chord’s and Kademlia’s designs: a uni-directional lookups versus bi-directional lookups, in which we expect to see Kademlia’s latencies, as in the number of hops, to outperform those of Chord’s. For these reasons, we posit three hypotheses in which we tested both distributed systems against.

Hypothesis 1: In the scenario where Chord and Kademlia process the same sequence of operations, we expect to see Kademlia outperforms Chord in latencies measured by a number of hops.

Hypothesis 2: In the scenario lookups are left-biased, we expect to see a significant increase in Chord’s latencies measured by a number of hops. On the other hand, we expect to no statistically significant increase nor decrease in Kademlia’s latencies measured by a number of hops.

Hypothesis 3: In the scenario where Chord and Kademlia process the same sequence of operations and lookups are left-biased, we expect to see Kademlia significantly outperforms Chord in latencies measured by a number of hops.

Our contribution to this project is three-fold.

1. We implement from scratch both Chord and Kademlia according to their specification. Both systems gracefully handle three types of operations: client’s put and get, and nodejoins.
2. We implement from scratch a framework which simulates the environment of distributed systems, and is suitable to our evaluation purpose.
3. We carefully craft the experiments that truly target the differences in Chord’s and Kademlia’s design choices. In particular, we evaluate both system’s latencies as the number of hops. This reflects Kademlia’s advantage of bi-directional lookups to Chord’s uni-directional lookups. To further expose Chord’s disadvantages, we generate a biased dataset where client’s lookup keys are very likely to be to the left of client’s local nodes — in which Chord should take multiple hops to find while Kademlia, searching in both directions, should find the key with fewer hops.

We test our hypotheses by running Chord and Kademlia through a series of experiments. Our findings are conclusive: Kademlia outperforms Chord by a non-trivial number of hops. Furthermore, the performance gaps widen as the left-lookup biases increase.

The implementation of our testing framework, Chord, Kademlia, as well as datasets and experimental results can be found at https://github.com/JingyiRose/DHTs/tree/main