Data currency in replicated DHTs

ABSTRACT

Distributed Hash Tables (DHTs) provide a scalable solution for data sharing in P2P systems. To ensure high data availability, DHTs typically rely on data replication, yet without data currency guarantees. Supporting data currency in replicated DHTs is difficult as it requires the ability to return a current replica despite peers leaving the network or concurrent updates. In this paper, we give a complete solution to this problem. We propose an Update Management Service (UMS) to deal with data availability and efficient retrieval of current replicas based on timestamping. For generating timestamps, we propose a Key-based Timestamping Service (KTS) which performs distributed timestamp generation using local counters. Through probabilistic analysis, we compute the expected number of replicas which UMS must retrieve for finding a current replica. Except for the cases where the availability of current replicas is very low, the expected number of retrieved replicas is typically small, e.g. if at least 35% of available replicas are current then the expected number of retrieved replicas is less than 3. We validated our solution through implementation and experimentation over a 64-node cluster and evaluated its scalability through simulation up to 10,000 peers using SimJava. The results show the effectiveness of our solution. They also show that our algorithm used in UMS achieves major performance gains, in terms of response time and communication cost, compared with a baseline algorithm.

REFERENCES

• 1: Philip A. Bernstein , Alan Fekete , Hongfei Guo , Raghu Ramakrishnan , Pradeep Tamma, Relaxed-currency serializability for middle-tier caching and replication, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142540]
• 2: Bromwich, T. J. I. An Introduction to the Theory of Infinite Series. 3rd edition, Chelsea Pub. Co., 1991.
• 3: Ian Clarke , Scott G. Miller , Theodore W. Hong , Oskar Sandberg , Brandon Wiley, Protecting Free Expression Online with Freenet, IEEE Internet Computing, v.6 n.1, p.40-49, January 2002 [doi>10.1109/4236.978368]
• 4: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: Dabek, F., Zhao, B. Y., Druschel, P., Kubiatowicz, J., and Stoica, I. Towards a Common API for Structured Peer-to-Peer Overlays. Proc. of Int. Workshop on Peer-to-Peer Systems (IPTPS), 2003.
• 6: Daswani, N., Garcia-Molina, H., and Yang, B. Open Problems in Data-Sharing Peer-to-Peer Systems. Proc. of ICDT, 2003.
• 7: Datta A., Hauswirth M., and Aberer, K. Updates in Highly Unreliable, Replicated Peer-to-Peer Systems. Proc. of IEEE Int. Conf. on Distributed Computing Systems (ICDCS), 2003.
• 8: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 9: Gnutella. http://www.gnutelliums.com/.
• 10: Hongfei Guo , Per-Åke Larson , Raghu Ramakrishnan , Jonathan Goldstein, Relaxed currency and consistency: how to say "good enough" in SQL, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007661]
• 11: Hongfei Guo , Per-Åke Larson , Raghu Ramakrishnan, Caching with "good enough" currency, consistency, and completeness, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Kazaa. http://www.kazaa.com/.
• 13: Knezevic, P., Wombacher, A., and Risse, T. Enabling High Data Availability in a DHT. Proc. of Int. Workshop on Grid and P2P Computing Impacts on Large Scale Heterogeneous Distributed Database Systems (GLOBE), 2005.
• 14: Lindstrom, G., and Hunt, F. Consistency and Currency in Functional Databases. Proc. of INFOCOM, 1983.
• 15: Luby, M. Pseudorandomness and Cryptographic Applications. Princeton University Press, 1996.
• 16: Mills., D. L. Internet Time Synchronization: The Network Time Protocol. IEEE Transactions on Communications, 39(10), 1991.
• 17: Özsu, T., and Valduriez, P. Principles of Distributed Database Systems. 2nd Edition, Prentice Hall, 1999.
• 18: Santashil PalChaudhuri , Amit Kumar Saha , David B. Johnson, Adaptive clock synchronization in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984672]
• 19: Ratnasamy, S., Francis, P., Handley, M., Karp, R. M., and Shenker, S. A. Scalable Content-Addressable Network. Proc. of SIGCOMM, 2001.
• 20: Rhea, S. C., Eaton, P. R., Geels, D., Zhao, B., Weatherspoon, H., and Kubiatowicz, J. Pond: the OceanStore Prototype. Proc. of USENIX Conf. on File and Storage Technologies (FAST), 2003.
• 21: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 22: Röhm, U., Böhm, K., Schek, H., and Schuldt, H. FAS: a Freshness-Sensitive Coordination Middleware for a Cluster of OLAP Components. Proc. of VLDB, 2002.
• 23: Rowstron, A. I. T., and Druschel, P. Pastry: Scalable, Decentralized Object Location, and Routing for large-scale Peer-to-Peer Systems. Proc. of Middleware, 2001.
• 24: Rowstron, A., and Druschel, P. Storage Management and Caching in PAST, a large-scale, Persistent Peer-to-Peer Storage Utility. Proc. of ACM Symp. on Operating Systems Principles, 2001.
• 25: Rowstron, A., and Druschel, P. Storage Management and Caching in PAST, a large-scale, Persistent Peer-to-Peer Storage Utility. Proc. of ACM Symp. on Operating Systems Principles, 2001.
• 26: Segev, A., and Fang, W. Currency-based Updates To Distributed Materialized Views. Proc. of ICDE, 1990.
• 27: Simjava. http://www.dcs.ed.ac.uk/home/hase/simjava/
• 28: Spivak, M. Calculus. 3rd edition, Cambridge University Press, 1994.
• 29: Stoica I., Morris, R., Karger, D. R., Kaashoek, M. F., and Balakrishnan, H. Chord: a Scalable Peer-to-Peer Lookup Service for Internet Applications. Proc. of SIGCOMM, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Query processing

General Terms:
Algorithms, Performance, Reliability

Keywords:
data currency, data dvailability, data replication, distributed hash table (DHT), peer-to-peer