OpenDHT: a public DHT service and its uses

Abstract

Large-scale distributed systems are hard to deploy, and distributed hash tables (DHTs) are no exception. To lower the barriers facing DHT-based applications, we have created a public DHT service called OpenDHT. Designing a DHT that can be widely shared, both among mutually untrusting clients and among a variety of applications, poses two distinct challenges. First, there must be adequate control over storage allocation so that greedy or malicious clients do not use more than their fair share. Second, the interface to the DHT should make it easy to write simple clients, yet be sufficiently general to meet a broad spectrum of application requirements. In this paper we describe our solutions to these design challenges. We also report our early deployment experience with OpenDHT and describe the variety of applications already using the system.

References

1. Bamboo. http://bamboo-dht.org/.]]
2. Chord. http://www.pdos.lcs.mit.edu/chord/.]]
3. Pastry. http://freepastry.rice.edu/.]]
4. H. Balakrishnan, S. Shenker, and M. Walfish. Peering peer-to-peer providers. In IPTPS, Feb. 2005.]]
5. A. Bavier et al. Operating system support for planetary-scale network services. In NSDI, Mar. 2004.]]
6. M. Beck, T. Moore, and J. S. Plank. An end-to-end approach to globally scalable programmable networking. In FDNA, 2003.]]
7. M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. SplitStream: High-bandwidth multicast in a cooperative environment. In SOSP, 2003.]]
8. J. Cates. Robust and efficient data management for a distributed hash table. Master's thesis, MIT, May 2003.]]
9. F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In SOSP, Oct. 2001.]]
10. F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for low latency and high throughput. In NSDI, 2004.]]
11. F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica. Towards a common API for structured P2P overlays. In IPTPS, 2003.]]
12. A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queuing algorithm. In SIGCOMM, 1989.]]
13. J. Douceur. The Sybil attack. In IPTPS, 2002.]]
14. P. Druschel and A. Rowstron. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In SOSP, 2001.]]
15. M. J. Freedman, E. Freudenthal, and D. Mazières. Democratizing content publication with Coral. In NSDI, Mar. 2004.]]
16. P. Goyal, H. Vin, and H. Cheng. Start-time fair queuing: A scheduling algorithm for integrated services packet switching networks. In SIGCOMM, Aug. 1996.]]
17. R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, and I. Stoica. Querying the Internet with PIER. In VLDB, 2003.]]
18. D. R. Karger and M. Ruhl. Diminished Chord: A protocol for heterogeneous subgroup formation in peer-to-peer networks. In IPTPS, 2004.]]
19. B. Karp, S. Ratnasamy, S. Rhea, and S. Shenker. Spurring adoption of DHTs with OpenHash, a public DHT service. In IPTPS, 2004.]]
20. A. Mislove et al. POST: a secure, resilient, cooperative messaging system. In HotOS, 2003.]]
21. R. Moskowitz, P. Nikander, P. Jokela, and T. Henderson. Host identity protocol (work in progress). IETF Internet Draft, 2004.]]
22. A. Muthitacharoen, S. Gilbert, and R. Morris. Etna: A fault-tolerant algorithm for atomic mutable DHT data. Technical Report MIT-LCS-TR-993, MIT-LCS, June 2005.]]
23. A. Muthitacharoen, R. Morris, T. Gil, and B. Chen. Ivy: A read/write peer-to-peer file system. In OSDI, 2002.]]
24. K. Petersen, M. Spreitzer, D. Terry, M. Theimer, and A. Demers. Flexible update propagation for weakly consistent replication. In SOSP, 1997.]]
25. S. Ramabhadran, S. Ratnasamy, J. Hellerstein, and S. Shenker. Brief announcement: Prefix hash tree (extended abstract). In PODC, 2004.]]
26. V. Ramasubramanian and E. G. Sirer. The design and implementation of a next generation name service for the Internet. In SIGCOMM, Aug. 2004.]]
27. S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Application-level multicast using content-addressable networks. Lecture Notes in Computer Science, 2233:14--29, 2001.]]
28. S. Rhea, P. Eaton, D. Geels, H. Weatherspoon, B. Zhao, and J. Kubiatowicz. Pond: the OceanStore prototype. In USENIX FAST, Mar. 2003.]]
29. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. In USENIX Annual Tech. Conf., June 2004.]]
30. T. Roscoe and S. Hand. Palimpsest: Soft-capacity storage for planetary-scale services. In HotOS, May 2003.]]
31. I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana. Internet indirection infrastructure. In SIGCOMM, Aug. 2002.]]
32. J. Stribling. Planetlab all-pairs ping. http://www.pdos.lcs.mit.edu/~strib/pl_app/APP_README.txt.]]
33. M. Walfish, H. Balakrishnan, and S. Shenker. Untangling the Web from DNS. In NSDI, Mar. 2004.]]
34. B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE JSAC, 22(1):41--53, Jan. 2004.]]
35. S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. H. Katz, and J. Kubiatowicz. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In NOSSDAV, 2001.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles