Kademlia: A Peer-to-Peer Information System Based on the XOR Metric

Petar Maymounkov and David Mazières

Abstract

We describe Kademlia, a distributed system for storing and finding information without a central server.

Kademlia is designed for a network in which computers often join, leave, stop responding, or lose packets. Every participating computer has a large numerical identifier. Stored items also have large numerical keys. The system places each item on the computers whose identifiers are closest to the item's key.

Kademlia measures closeness with exclusive OR, usually called XOR. This distance rule gives the network a simple and useful shape. It lets us use the same routing method from the beginning of a search to the end. It also means that normal network traffic teaches computers about useful contacts.

A computer can send several search requests at the same time. It can continue as soon as useful replies arrive, without waiting for failed or slow computers. This gives the system good performance and strong fault tolerance.

1. Introduction

Kademlia is a peer-to-peer distributed hash table. It stores key and value pairs across many independent computers. There is no single directory that must know where everything is stored.

Kademlia has several important properties.

First, computers learn about one another during ordinary searches. They do not need a separate and expensive process for constantly rebuilding the network map.

Second, a computer usually knows several possible next steps for a search. It can choose a contact that responds quickly, or it can ask several contacts at once.

Third, searches are asynchronous. A failed computer does not force the user to wait through a long timeout before the search can continue.

Fourth, Kademlia prefers old, proven contacts over unknown new contacts. This makes routing tables more stable and makes it harder for an attacker to erase useful routing information simply by introducing many new identities.

Finally, the main performance and reliability properties of the system can be explained and proven under fairly weak assumptions about how long computers remain online.

Each stored item has a key. In the system described here, keys are one hundred sixty bit numbers. A key may be the SHA-1 hash of a larger piece of data, but Kademlia does not need to understand what the key means.

Each participating computer also has a one hundred sixty bit node identifier. We call a participating computer a node. A value is stored on a small group of nodes whose identifiers are close to the value's key. To find the value, a node searches for other nodes that are progressively closer to that key.

The meaning of close is very important. Kademlia uses XOR distance. This choice gives the routing system several benefits.

XOR distance is symmetric. If node A is a certain distance from node B, then node B is the same distance from node A. Because of this, the nodes that contact a participant during searches come from the same kinds of distance ranges that the participant needs in its own routing table. Incoming traffic is therefore useful for maintaining routing information.

This is different from a system such as Chord, whose distance rule is directional. A Chord routing entry often needs a very specific node in a particular position. Kademlia can usually use any healthy node from an appropriate distance range. This gives it more freedom to choose a low-latency route or to send parallel requests.

Kademlia also uses one distance rule for the complete search. Some earlier systems use one routing method to approach the target and another method for the final steps. Pastry, for example, first moves toward a matching prefix and later changes to ordinary numerical distance. A node that is close under one rule may be far away under the other. That change can create awkward boundaries and makes worst-case behavior harder to study. Kademlia avoids that problem by using XOR throughout the process.

2. System Description

A useful way to understand Kademlia is to picture all node identifiers as leaves in a binary tree.

The first bit divides the tree into two halves. Identifiers beginning with zero are in one half, and identifiers beginning with one are in the other. The second bit divides each half again. Every later bit continues the same process.

A node does not need a complete list of every other node. Instead, it needs contacts in a series of regions around its own identifier.

Consider a node whose identifier begins with zero, zero, one, one. The largest region it needs to know about is the opposite half of the tree, containing identifiers that begin with one. The next region contains identifiers that begin with zero, one. The next contains identifiers that begin with zero, zero, zero. The next contains identifiers that begin with zero, zero, one, zero. Each region is closer to the node than the region before it.

Kademlia tries to ensure that a node knows at least one contact in every such region that actually contains a node. With that property, a search can repeatedly move into a smaller and more relevant part of the tree. Each contacted node supplies contacts that are closer to the target, and the search eventually reaches the closest existing nodes.

2.1 XOR Distance

Every node has a one hundred sixty bit identifier. In the basic design, we can treat these identifiers as randomly chosen. Every message includes the sender's node identifier, so the receiver can learn that the sender exists.

Keys use the same one hundred sixty bit format. We therefore need one distance rule that works between two node identifiers and also between a node identifier and a key.

XOR compares two numbers one bit at a time. If the two bits are the same, the result at that position is zero. If the bits differ, the result is one. We then read the complete result as an ordinary nonnegative number. A smaller result means a shorter distance.

This is a proper distance rule. An identifier has zero distance from itself. Different identifiers have a positive distance. The distance is the same in both directions. It also obeys the ordinary triangle rule: taking a detour through a third point cannot produce a distance smaller than the direct relationship requires.

XOR matches the binary-tree view of the system. The first bit where two identifiers differ has the greatest effect on their distance. Two identifiers with a long shared prefix are usually close. Two identifiers that differ near the beginning are far apart.

In a completely full binary tree, the size of the smallest subtree containing two identifiers tells us the most important part of their XOR distance. In a real network, many possible identifiers have no node. The closest existing node to a target is then the node that follows the target's prefix as far as possible before taking an occupied branch.

XOR has another useful property that we call unidirectionality. Starting from one identifier, there is exactly one identifier at any exact XOR distance. As a result, searches for the same key tend to converge through the same parts of the network, even when they begin at different nodes. This makes caching effective because later searches are likely to pass through earlier cache locations.

At the same time, XOR is symmetric. This combination is unusual and valuable. Searches move consistently toward a target, while communication in either direction still provides useful routing information.

2.2 Node State

Each node stores a limited set of contacts. A contact contains an IP address, a UDP port, and a node identifier.

The contacts are divided into distance bands. We call each list a K bucket. The first possible band covers very close identifiers. Each later band is twice as wide as the one before it. Together, the bands describe all possible XOR distances from the local node.

Most very close bands are empty because the identifier space is enormous and only a small fraction of possible identifiers are in use. Wider and more distant bands are more likely to contain nodes.

Each K bucket can hold up to K contacts. K is a system-wide replication and reliability setting. It should be large enough that all K contacts are very unlikely to fail during the period between routing-table refreshes. A value such as twenty is reasonable for the assumptions in this design.

Contacts inside a bucket are ordered by the time they were last seen. The least recently seen contact is at the front. The most recently seen contact is at the end.

Whenever a node receives either a request or a reply, it updates the bucket for the sender.

If the sender is already in the bucket, the node moves that contact to the end because it has just proved that it is alive.

If the sender is new and the bucket has space, the node adds it at the end.

If the bucket is full, the node checks the least recently seen contact. If that old contact does not answer a ping, it is removed and the new contact takes its place. If the old contact answers, the old contact is kept, moved to the end, and the new contact is discarded.

This resembles a least-recently-used policy, but with an important difference: a contact is not removed merely because it is old. A live old contact is preferred over an unproven new contact.

Measurements of Gnutella peers showed why this is useful. A peer that has already remained online for a long time is more likely to remain online for another hour than a peer that has only recently appeared. Keeping old live contacts therefore improves the expected stability of the routing table.

This rule also provides some resistance to denial-of-service attacks. An attacker cannot easily erase a routing table by flooding a node with fresh identities. New contacts enter a full bucket only when old contacts stop responding.

2.3 The Kademlia Protocol

Kademlia uses four basic remote procedure calls. In ordinary language, these are four kinds of network request.

A ping asks whether a node is online.

A store request tells a node to save a key and value pair.

A find-node request contains a target identifier. The receiver returns the K contacts it knows that are closest to that target. If it knows fewer than K contacts in total, it returns all of them.

A find-value request works like find-node unless the receiver has the requested value. If it has the value, it returns the value instead of more contacts.

Each request carries a large random request identifier. The reply must repeat it. This makes forged replies more difficult. A node may also combine address checks with normal replies to gain more confidence that the sender is reachable at the claimed network address.

Finding the Closest Nodes

The central operation in Kademlia is finding the K nodes closest to a target identifier.

The searching node begins with the closest contacts it already knows. It keeps a working list of the best K candidates seen so far.

It chooses a small number of the closest unqueried candidates and sends find-node requests to them at the same time. We call the number of parallel requests alpha. A typical value is three.

Replies do not need to arrive together. As soon as a reply supplies new contacts, the searching node merges those contacts into its working list, keeps the best candidates, and sends new requests to the closest promising nodes it has not yet queried.

A slow or failed node is temporarily ignored. The search does not need to stop while waiting for it. If the node eventually replies, its answer can still be used.

As long as replies reveal nodes closer to the target, the process continues with the small alpha-sized group of parallel requests. When a round produces no closer candidate, the searching node asks every remaining unqueried node among its current best K candidates. The search ends after it has queried and received replies from the K closest responsive nodes it has discovered.

With alpha equal to one, the process is mostly serial. It sends fewer requests at once, but a failed node can delay progress. A larger alpha uses somewhat more bandwidth, but usually lowers delay and hides failures. The node may also use measured round-trip times when choosing which candidates to ask first.

Storing Values

To store a key and value pair, a node first performs a node lookup for the key. It then sends store requests to the K closest nodes it found.

Copies must be renewed because nodes leave the network and because new nodes may later join with identifiers closer to the key. Kademlia therefore republishes stored values as needed.

In the file-sharing application for which we built the original system, the original publisher republishes a value every twenty-four hours. A value that is not republished expires after twenty-four hours. This removes stale index entries. Other applications may choose a longer lifetime. A mapping used for a certificate or another long-lived object may need different rules.

When a node learns about a new node that is closer to one of its stored keys, it copies the relevant key and value pair to the new node. It does not immediately delete its own copy.

Finding Values and Caching Them

A value lookup follows the same general process as a node lookup, but it sends find-value requests.

The lookup stops as soon as any contacted node returns the value. The requester then caches the value at the closest node it encountered that did not already have it.

Because searches for the same key tend to follow similar paths, later searches are likely to encounter that cached copy before reaching the nodes closest to the key. A popular value may naturally spread to many useful cache locations.

We do not want unlimited caching. A cache far from the key should usually expire sooner than a cache near the key. Kademlia estimates how many nodes lie between the cache and the closest node to the key. The more intervening nodes there are, the shorter the cache lifetime becomes. This produces many short-lived copies for a popular value and fewer long-lived copies near its proper storage location, without requiring a fixed cache size.

Refreshing Buckets

Normal search traffic usually keeps K buckets current. Requests and replies continually confirm old contacts and introduce new ones.

A quiet part of the identifier space may receive no traffic. If a node has not performed a lookup in a bucket's range for an hour, it refreshes that bucket. It chooses a random identifier inside the range and performs a node lookup for that identifier.

Joining the Network

A new node must begin with the address of at least one node already in the network. This first contact may come from saved state, a friend, a program distributor, or another bootstrap method.

The new node inserts the known contact into the correct K bucket. It then performs a lookup for its own node identifier. This introduces the new node to nearby participants and fills the most relevant parts of its own routing table.

Finally, the new node refreshes the buckets that represent regions farther away than its nearest known neighbor. These refreshes help it discover the rest of the network and allow other nodes to learn about it.

2.4 Routing Table

The routing table can be represented as a binary tree whose leaves are K buckets. Each bucket covers one non-overlapping range of identifiers. Together, the buckets cover the entire identifier space.

The tree is created only as needed.

At first, a node has one bucket covering every possible identifier. When a new contact arrives, the node tries to place it in the matching bucket.

If the bucket has space, the contact is added.

If the bucket is full and its range contains the local node's own identifier, the bucket is divided into two smaller buckets. Existing contacts are separated according to their identifiers, and the insertion is tried again. The process may repeat several times.

If a full bucket covers a range that does not contain the local node's identifier, the basic rule does not split it. The new contact is normally discarded.

This produces a routing table with fine detail near the local node and less detail far away. That is the right tradeoff because a node needs complete knowledge of its immediate neighborhood, while a few contacts are enough to cross distant parts of the identifier space.

A special case appears when identifiers are distributed unevenly.

Suppose one node is the only participant whose identifier begins with zero, zero, zero, while many nodes have identifiers beginning with zero, zero, one. The many nodes in the second group should learn about the single nearby node. A normal refresh by the single node might notify only K members of that larger group, leaving the others unaware of it.

To handle this case, Kademlia slightly relaxes the ordinary splitting rule. A node keeps complete contact information for the smallest surrounding subtree that contains at least K nodes. It may split a nearby bucket even when that bucket does not directly contain its own identifier. These extra splits are expected to be small in number.

After the node refreshes these more detailed buckets, all relevant nearby nodes can learn about it. This also gives the node enough local knowledge to perform efficient value maintenance.

2.5 Efficient Key Republishing

Values must be republished for two reasons.

First, some of the K nodes holding a value may leave.

Second, new nodes may join with identifiers closer to the key than the current holders.

Without republishing, a valid value could remain somewhere in the network but no longer be found among the K closest nodes, which is where searches expect it to be.

Kademlia republishes each key and value pair about once an hour. A direct implementation would be expensive. Every one of the K holders might perform a fresh lookup and send the value to the other K minus one holders. That would create many duplicate messages.

We use two main optimizations.

First, when a node receives a store request for a value, it assumes that the sender also sent the value to the other closest nodes. The receiver therefore postpones its own republication of that value for the next hour. If node schedules are not exactly synchronized, this usually causes only one holder to perform the hourly republication.

Second, a node does not need a separate lookup for every value it republishes. The relaxed routing table gives the node complete knowledge of a nearby subtree containing at least K participants. Before republishing a group of values, the node refreshes the buckets in that subtree. It can then determine the closest holders for many different keys from the routing information it already has.

There are two reasons this works.

A key may fall inside the well-known nearby subtree. In that case, the node knows every participant in the relevant area and can directly choose the K closest nodes.

A key may fall outside that subtree even though the local node is one of the K closest holders. In that case, all identifier ranges between the local node's neighborhood and the key must contain fewer than K known nodes. The node has complete knowledge of those partly filled buckets. Combining those contacts with the complete nearby subtree still reveals the K closest nodes.

When a new node joins, it should receive every value for which it has become one of the K closest nodes. Existing nearby nodes can determine which values qualify and send them to the newcomer. To avoid duplicate transfers, responsibility is given to the existing holder that is closest to the key among the relevant known holders.

3. Sketch of the Proof

We now explain why lookups are fast and why stored values usually survive failures.

The complete mathematical proof uses formal definitions for bucket depth and tree height. The main ideas can be stated more simply.

Node identifiers are chosen at random from a huge space. Random identifiers are unlikely to form an extremely unbalanced tree. For a network with N nodes, the useful depth of the tree grows roughly with the logarithm of N. This means that making the network much larger adds only a small number of routing steps.

The key routing condition is this: if a distance range contains a node, the corresponding bucket should contain at least one contact from that range.

Assume this condition holds. During a lookup, the current best contact can usually point to a node whose identifier agrees with the target for one more important bit. In the tree view, each step enters a smaller subtree containing the target. In the distance view, each step reduces the important part of the remaining distance by about half.

After a logarithmic number of steps, the search reaches the closest existing node. Finding the rest of the K closest nodes requires only a small additional number of steps because those nodes lie in the same nearby part of the tree.

An empty bucket does not normally make the result incorrect. It means that one expected region contains no known node. The search behaves as though it followed the nearest occupied branch instead. It may need an extra step, but it still reaches the closest existing node.

We next consider whether the routing condition remains true over time.

When a bucket is refreshed, the lookup either fills it with K live contacts or discovers every node in that range when fewer than K exist. New nodes are inserted into buckets that have room. Therefore, a populated range becomes unknown only if all K contacts representing that range fail before any relevant search or refresh repairs the bucket.

K is chosen to make this event very unlikely during the one-hour refresh period.

The real probability is lower still because every incoming and outgoing request updates routing information. XOR symmetry is important here. The nodes encountered in normal communication are distributed across exactly the distance ranges that the local routing table needs.

Even if one bucket in one node temporarily loses all useful contacts, the usual effect is an extra hop rather than an incorrect lookup. A complete lookup failure would require a sequence of nodes along the search path to lose all K useful contacts in corresponding ranges before traffic or refreshes repair them. That combined event is far less likely.

Stored values receive similar protection.

A newly published value is copied to the K nodes closest to its key and is republished every hour. Even if a new node has only an even chance of remaining online for the next hour, the chance that all K independent holders disappear in that hour becomes extremely small as K grows.

New nodes that join near the key contact their neighbors to fill their routing tables. During that process, they receive nearby values they should now store. This keeps replication aligned with the current set of closest nodes.

Kademlia cannot prevent every possible loss. If all K closest holders fail and no useful cached copy exists elsewhere, the value is lost. The purpose of replication, caching, refreshes, and republishing is to make that event rare.

4. Implementation Notes

We used two additional techniques to reduce network traffic and lookup delay.

4.1 Optimized Contact Accounting

The basic bucket rule says that when a full bucket receives a message from an unknown node, the oldest contact should be pinged immediately. If unknown nodes appear often, this creates too many pings.

Instead, we keep a replacement cache for each full bucket.

When a new contact appears and the bucket is full, the node places the newcomer in the replacement cache instead of immediately probing the oldest active contact. The replacement cache is ordered by recent activity, with recently seen candidates preferred.

Later, when the node has a useful reason to contact members of that bucket, failed active contacts are discovered naturally. An unresponsive entry can then be removed and replaced by a candidate from the cache. This avoids many standalone pings.

UDP introduces another problem. A healthy node may fail to answer because a packet was lost. Packet loss may also mean that the network is congested. Kademlia therefore avoids treating one missed reply as proof that a contact is dead.

After a failed request, the contact is temporarily locked and is not queried again for a backoff period. Repeated failures make the waiting period longer. A lookup usually needs a reply from only one of several candidates, so it normally continues through another node rather than retransmitting immediately to the same one.

After five consecutive unanswered requests, a contact is considered stale. Even then, it is not always deleted at once. If the bucket is not full, or if there is no replacement candidate, the contact may remain marked as stale. This matters when the local node itself temporarily loses network access. Otherwise, its own outage could cause it to discard most of its routing table at once.

4.2 Accelerated Lookups

The simplest routing table treats one identifier bit as one level of progress. This gives a logarithmic number of hops.

We can reduce the number of hops by grouping several bits together. Let B be the number of bits considered at once. A larger B creates more routing buckets, but each successful hop can move through a larger part of the tree.

The basic routing table splits full buckets mainly along the branch containing the local node's identifier. The accelerated version also splits selected ranges outside that branch. It adds enough detail that a search can choose among the possible values of the next B bits rather than learning only one bit at a time.

For example, grouping two bits requires some distant ranges to be divided once. Grouping three bits may divide them through two additional levels. Our implementation groups five bits at a time.

The cost is a larger routing table and more maintenance work. The benefit is fewer network hops per lookup.

Pastry, Tapestry, and Plaxton's routing method can also try to advance several bits at once. However, without Kademlia's XOR structure, they need extra mechanisms to finish a search among nodes that share one prefix but differ in the next group of bits. Those secondary structures increase bootstrap and maintenance costs and make the protocols and their proofs more complicated.

With XOR, Kademlia can use the same basic idea at either one bit or several bits per step. The routing method remains uniform from the beginning of the lookup to the end.

5. Summary

Kademlia combines a simple XOR distance rule with a practical peer-to-peer routing system.

Its topology is symmetric, so communication in either direction teaches nodes useful routing information. It is also unidirectional in the sense that searches for the same target tend to converge through the same areas. This supports effective caching.

K buckets preserve several old and reliable contacts for each important distance range. Parallel requests let a lookup continue through the fastest useful replies instead of waiting for failed nodes. The alpha setting lets an implementation trade some bandwidth for lower delay and faster recovery from failures.

Values are copied to the K nodes closest to their keys. Caching, refreshes, hourly republishing, and transfers to newly joined closer nodes keep those copies available as the network changes.

The routing table grows dynamically and keeps its greatest detail near the local node. A small relaxation handles uneven identifier distributions. Replacement caches and backoff rules reduce maintenance traffic, while wider routing steps can reduce lookup hops.

The result is a distributed hash table with logarithmic lookup growth, strong tolerance of ordinary node failures, flexible low-latency routing, and a design simple enough to analyze.