Kinesis: A new approach to replica placement in distributed storage systems

ABSTRACT

Kinesis is a novel data placement model for distributed storage systems. It exemplifies three design principles: structure (division of servers into a few failure-isolated segments), freedom of choice (freedom to allocate the best servers to store and retrieve data based on current resource availability), and scattered distribution (independent, pseudo-random spread of replicas in the system). These design principles enable storage systems to achieve balanced utilization of storage and network resources in the presence of incremental system expansions, failures of single and shared components, and skewed distributions of data size and popularity. In turn, this ability leads to significantly reduced resource provisioning costs, good user-perceived response times, and fast, parallelized recovery from independent and correlated failures.

This article validates Kinesis through theoretical analysis, simulations, and experiments on a prototype implementation. Evaluations driven by real-world traces show that Kinesis can significantly outperform the widely used Chain replica-placement strategy in terms of resource requirements, end-to-end delay, and failure recovery.

REFERENCES

• 1: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
• 2: Petra Berenbrink , Artur Czumaj , Angelika Steger , Berthold Vöcking, Balanced allocations: the heavily loaded case, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.745-754, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335411]
• 3: Byers, J., Considine, J., and Mitzenmacher, M. 2003. Simple load balancing for distributed hash tables. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS).
• 4: Czumaj, A., Riley, C., and Scheideler, C. 2003. Perfectly balanced allocation.
• 5: 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
• 6: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: Godfrey, B., Lakshminarayanan, K., Surana, S., Karp, R., and Stoica, I. 2004. Load balancing in dynamic structured p2p systems. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 8: Hui-I Hsiao , David J. DeWitt, Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines, Proceedings of the Sixth International Conference on Data Engineering, p.456-465, February 05-09, 1990
• 9: Minwen Ji , Edward W. Felten , Randolph Wang , Jaswinder Pal Singh, Archipelago: an Island-based file system for highly available and scalable internet services, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.1-1, August 03-04, 2000, Seattle, Washington
• 10: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 11: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 12: Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.84-92, October 01-04, 1996, Cambridge, Massachusetts, United States
• 13: Witold Litwin, Linear hashing: a new tool for file and table addressing, Proceedings of the sixth international conference on Very Large Data Bases, p.212-223, October 01-03, 1980, Montreal, Quebec, Canada
• 14: Christopher R. Lumb , Richard Golding, D-SPTF: decentralized request distribution in brick-based storage systems, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 15: John MacCormick , Nick Murphy , Marc Najork , Chandramohan A. Thekkath , Lidong Zhou, Boxwood: abstractions as the foundation for storage infrastructure, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.8-8, December 06-08, 2004, San Francisco, CA
• 16: Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004 [doi>10.1016/j.jalgor.2003.12.002]
• 17: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.205-216, October 02-07, 1998, San Jose, California, United States
• 18: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 19: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: Sanders, P., Egner, S., and Korst, J. H. M. 2003. Fast concurrent access to parallel disks. Algorithmica 35, 1, 21--55.
• 21: Kunal Talwar , Udi Wieder, Balanced allocations: the weighted case, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250829]
• 22: Robbert van Renesse , Fred B. Schneider, Chain replication for supporting high throughput and availability, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.7-7, December 06-08, 2004, San Francisco, CA
• 23: Berthold Vöcking, How Asymmetry Helps Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.131, October 17-18, 1999
• 24: Sage A. Weil , Scott A. Brandt , Ethan L. Miller , Darrell D. E. Long , Carlos Maltzahn, Ceph: a scalable, high-performance distributed file system, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.22-22, November 06-08, 2006, Seattle, WA
• 25: Sage A. Weil , Scott A. Brandt , Ethan L. Miller , Carlos Maltzahn, CRUSH: controlled, scalable, decentralized placement of replicated data, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188582]
• 26: Udi Wieder, Balanced allocations with heterogenous bins, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248407]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
Storage system, load balancing, multiple-choice paradigm