Kelips*: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead
📜 Abstract
A peer-to-peer (p2p) distributed hash table (DHT) system allows hosts to join and fail silently (or leave), as well as to insert and retrieve files (objects). This paper explores a new point in design space in which increased memory usage and constant background communication overheads are tolerated to reduce file lookup times and increase stability to failures and churn. Our system, called Kelips, uses peer-to-peer gossip to partially replicate file index information. In Kelips, (a) under normal conditions, file lookups are resolved with O(1) time and complexity (i.e., independent of system size), and (b) membership changes (e.g., even when a large number of nodes fail) are detected and disseminated to the system quickly. Per-node memory requirements are small in medium-sized systems. When there are failures, lookup success is ensured through query rerouting. Kelips achieves load balancing comparable to existing systems. Locality is supported by using topologically aware gossip mechanisms. Initial results of an ongoing experimental study are also discussed.
✨ Summary
Summary
Kelips investigates a deliberate tradeoff of increased per-node memory and continuous background communication for faster and more stable distributed-hash-table lookups. Nodes are assigned to virtual affinity groups using consistent hashing. Each node maintains partial membership information for its own group, a small set of contacts for every other group, and replicated file-index records, called filetuples. Gossip disseminates membership and file-index updates, while heartbeat expiration removes stale state.
With approximately √n affinity groups, the system requires O(√n) soft state per node while providing O(1) lookup time and message complexity under normal conditions. Multi-hop, multi-try query routing compensates for incomplete or stale state and node failures. File insertion uses a similar routing mechanism to improve load distribution, with normal-case insertion cost growing as O(log(√n)). Round-trip-time-aware gossip and contact selection provide a degree of network locality.
The prototype experiments, conducted in emulated environments of up to a few thousand nodes, reported reasonably balanced filetuple distributions. In one 1,000-node experiment, 66.2% of insertions succeeded on the first try, 33% on the second, and 0.8% on the third. In a test where 500 of 1,000 nodes failed simultaneously, lookups failed only when the file’s homenode had also failed; membership and filetuple state stabilized shortly afterward. The evaluation was preliminary, did not address replication of the files themselves, and explicitly omitted privacy and security considerations.
Influence
Subsequent research applied Kelips directly to peer-to-peer web caching. The churn-resistant peer-to-peer web caching system was built on the Kelips routing substrate, and Kache was implemented over Kelips to provide one-hop, locality-aware cache lookup under churn. (dprg.cs.uiuc.edu) Later DHT research and surveys cited Kelips as a representative constant-hop design that achieves low lookup latency through O(√N)-scale replication or routing state, including comparative discussions of CoDoNS, Beehive, and related systems. (cs.cornell.edu) The sources reviewed provide evidence of influence on subsequent P2P caching and DHT research, but no specific production-industry deployment of Kelips itself was identified. The publication metadata is corroborated by the Springer proceedings record, which lists the paper on pages 160–169 with the five authors above. (link.springer.com)