Appears in Proceedings of the USENIX Annual Technical Conference, June 2004.Handling Churn in a DHTSean Rhea, Dennis Geels, Timothy Roscoe, and John KubiatowiczUniversity of California, Berkeley and Intel Research, Berkeley{srhea,geels,kubitron}@cs.berkeley.edu, [email protected] paper addresses the problem of churn—the continu-ous process of node arrival and departure—in distributedhash tables (DHTs). We argue that DHTs should performlookups quickly and consistently under churn rates at leastas high as those observed in deployed P2P systems suchas Kazaa. We then show through experiments on an em-ulated network that current DHT implementations cannothandle such churn rates. Next, we identify and explorethree factors affecting DHT performance under churn: re-active versus periodic failure recovery, message timeoutcalculation, and proximity neighbor selection. We workin the context of a mature DHT implementation calledBamboo, using the ModelNet network emulator, whichmodels in-network queuing, cross-traffic, and packet loss.These factors are typically missing in earlier simulation-based DHT studies, and we show that careful attentionto them in Bamboo’s design allows it to function effec-tively at churn rates at or higher than that observed in P2Pfile-sharing applications, while using lower maintenancebandwidth than other DHT implementations.1 IntroductionThe popularity of widely-deployed file-sharing serviceshas recently motivated considerable research into peer-to-peer systems. Along one line, this research has focusedon the design of better peer-to-peer algorithms, especiallyin the area of structured peer-to-peer overlay networks ordistributed hash tables (e.g. [20, 22, 24, 27, 30]), which wewill simply call DHTs. These systems map a large iden-tifier space onto the set of nodes in the system in a deter-ministic and distributed fashion, a function we alternatelycall routing or lookup. DHTs generally perform theselookups using only O(log N) overlay hops in a networkof N nodes where every node maintains only O(log N )neighbor links, although recent research has explored thetradeoffs in storing more or less state.A second line of research into P2P systems has focusedon observing deployed networks (e.g. [5, 9, 13, 25]). Asignificant result of this research is that such networks arecharacterized by a high degree of churn. One metric ofchurn is node session time: the time between when a nodejoins the network until the next time it leaves. Mediansession times observed in deployed networks range fromas long as an hour to as short as a few minutes.In this paper we explore the performance of DHTs insuch dynamic environments. DHTs may be better ableto locate rare files than existing unstructured peer-to-peernetworks [18]. Moreover, it is not hard to imagine thatother proposed uses for DHTs will show similar churnrates to file-sharing networks—application-level multicastof a low-budget radio stream, for example. In spite of thispromise, we show that short session times cause a vari-ety of negative effects on two mature DHT implementa-tions we tested. Both systems exhibit dramatic latencygrowth when subjected to increasing churn, and in oneimplementation the network eventually partitions, causingsubsequent lookups to return inconsistent results. The re-mainder of this paper is dedicated to determining whethera DHT can be built such that it continues to perform wellas churn rates increase.We demonstrate that DHTs can in fact handle highchurn rates, and we identify and explore several factorsthat affect the behavior of DHTs under churn. The threemost important factors we identify are:• reactive versus periodic recovery from failures• calculation of message timeouts during lookups• choice of nearby over distant neighborsBy reactive recovery, we mean the strategy whereby aDHT node tries to find a replacement neighbor immedi-ately upon noticing that an existing neighbor has failed.We show that under bandwidth-limited conditions, reac-tive recovery can lead to a positive feedback cycle thatoverloads the network, causing lookups to have high la-tency or to return inconsistent results. In contrast, a DHTnode may recover from neighbor failure at a fixed, pe-riodic rate. We show that this strategy improves perfor-mance under churn by allowing the system to avoid posi-tive feedback cycles.The manner in which a DHT chooses timeout valuesduring lookups can also greatly affect its performance un-der churn. If a node performing a lookup sends a message1Appears in Proceedings of the USENIX Annual Technical Conference, June 2004.to a node that has left the network, it must eventually time-out the request and try another neighbor. We demonstratethat such timeouts are a significant component of lookuplatency under churn, and we explore several methods ofcomputing good timeout values, including virtual coordi-nate schemes as used in the Chord DHT.Finally, we consider proximity neighbor selection(PNS), where a DHT node with a choice of neighborstries to select those that are most nearby itself in net-work latency. We compare several algorithms for discov-ering nearby neighbors—including algorithms similar tothose used in the Chord, Pastry, and Tapestry DHTs—toshow the tradeoffs they offer between latency reductionand added bandwidth.We have augmented the Bamboo DHT [23] such thatit can be configured to use any of the design choicesdescribed above. As such, we can examine each de-sign decision independently of the others. Moreover, weexamine the performance of each configuration by run-ning it on a large cluster with an emulated wide-area net-work. This methodology is particularly important withregard to the choice of reactive versus periodic recoveryas described above. Existing studies of churn in DHTs(e.g. [7, 8, 16, 19]) have used simulations that—unlikeour emulated network—did not model the effects of net-work queuing, cross traffic, or message loss. In our ex-perience, these effects are primary factors contributing toDHTs’ inability to handle churn. Moreover, our measure-ments are conducted on an isolated network, where theonly sources of queuing, cross traffic, and loss are theDHTs themselves; in the presence of heavy backgroundtraffic, we expect that such network realities will exacer-bate the ability of DHTs to handle even lower levels ofchurn.Of course, this study has limitations. Building and test-ing a complete DHT implementation on an emulated net-work is
View Full Document
Unlocking...