Looking up Data in P2P Systems

This article provides a simple, high-level overview of how DHTs work and why one might be interested in them. Three types of routing are covered: Chord, which is a ring with "fingers" pointing to O(log n) neigbors from each node, Pastry, which uses trees based on ID prefixes, and CAN, which splits up a multi-dimensional data identifier space dynamically into regions and moves between neighboring regions. The general idea in all of the systems is the same - keep a small number of pointers from each node, but have some kind of distance metric that lets you get closer to the destination with each hop. Some redundancy in the neighbors also lets you tolerate node departures.

Apart from the easy to read summary, the paper is interesting because it lists some of the reasons why people though P2P systems would be interesting. Basically the idea was that providing a service as a P2P system gives you extremely small expenses (just enough for some tracker service) for a large amount of storage capacity and computation capacity that scales with your number of users. The downside is of course that you have to implement a lot of redundancy and fault-tolerance. In the end, however, the challenge to DHT research was that none of the applications had so much data to index that you couldn't have a centralized index. In other words, people already knew how to build systems for content distribution (BitTorrent, etc), and people knew how to build highly available web applications (torrent sharing sites, etc), so they just put the two together. While a purely distributed index is a nice concept, any real business pretty much had enough resources to build a centralized trackers. Nonetheless, some DHT ideas are being used to provide high availability in data center applications such as memached and Dynamo.