Marcos K. Aguilera
ABSTRACT
We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols -- a major complication in existing distributed systems. Instead, developers just design and manipulate data structures within our service called Sinfonia. Sinfonia keeps data for applications on a set of memory nodes, each exporting a linear address space. At the core of Sinfonia is a novel minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures. Using Sinfonia, we implemented two very different and complex applications in a few months: a cluster file system and a group communication service. Our implementations perform well and scale to hundreds of machines.
Supplemental Material
Available for Download
other
Slides from the presentation
zip
p159-slides.zip (9.2 MB)
Supplemental material for Sinfonia: a new paradigm for building scalable distributed systems
- Y. Amir and J. Stanton. The Spread wide area group communication system. Technical Report CNDS-98-4, The Johns Hopkins University, July 1998.Google Scholar
Digital Library
- K. P. Birman and T. A. Joseph. Exploiting virtual synchrony in distributed systems. In Symposium on Operating Systhem Principles, pages 123--138, Nov. 1987. Google ScholarDigital Library
- N. Budhiraja, K. Marzullo, F. B. Schneider, and S. Toueg. The primary-backup approach. In SJ. Mullender, editor, Distributed Systems, chapter 8. Addison-Wesley, 1993. Google ScholarDigital Library
- M. Burrows. The Chubby lock service for loosely-coupled distributed systems. In Symposium on Operating Systems Design and Implementation, pages 335--350, Nov. 2006. Google ScholarDigital Library
- T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, March 1996. Google ScholarDigital Library
- F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. BigTable: A distributed storage system for structured data. In Symposium on Operating Systems Design and Implementation, pages 205--218, Nov. 2006. Google ScholarDigital Library
- C. Chao, R. English, D. Jacobson, A. Stepanov, and J. Wilkes. Mime: a high performance storage device with strong recovery guarantees. Technical Report HPL-CSP-92-9, HP Laboratories, Nov. 1992.Google Scholar
- G. V. Chockler, I. Keidar, and R. Vitenberg. Group communication specifications: A comprehensive study. ACM Computing Surveys, 33(4):1--43, December 2001. Google ScholarDigital Library
- J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In Symposium on Operating Systems Design and Implementation, pages 137--150, Dec. 2004. Google ScholarDigital Library
- X. Défago, A. Schiper, and P. Urbàn. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Computing Surveys, 36(4):372--421, Dec. 2004. Google ScholarDigital Library
- M. Fakler, S. Frenz, R. Goeckelmann, M. Schoettner, and P. Schulthess. Project Tetropolis-application of grid computing to interactive virtual 3D worlds. In International Conference on Hypermedia and Grid Systems, May 2005.Google Scholar
- P. Ferreira et al. Perdis: design, implementation, and use of a persistent distributed store. In Recent Advances in Distributed Systems, volume 1752 of LNCS, chapter 18. Springer-Verlag, Feb. 2000. Google ScholarDigital Library
- S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google file system. In Symposium on Operating Systems Principles, pages 29--43, Oct. 2003. Google ScholarDigital Library
- S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler. Scalable, distributed data structures for Internet service construction. In Symposium on Operating Systems Design and Implementation, pages 319--332, Oct. 2000. Google ScholarDigital Library
- T. Harris and K. Fraser. Language support for lightweight transactions. In Conference on Object-Oriented Programming Systems, Languages and Applications, pages 388--402, Oct. 2003. Google ScholarDigital Library
- M. Herlihy, V. Luchangco, M. Moir, and W. Scherer. Software transactional memory for dynamic--sized data structures. In Symposium on Principles of Distributed Computing, pages 92--101, July 2003. Google ScholarDigital Library
- M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In International Symposium on Computer Architecture, pages 289--300, May 1993. Google ScholarDigital Library
- H.-I. Hsiao and D. DeWitt. Chained declustering: a new availability strategy for multiprocessor database machines. In International Data Engineering Conference, pages 456--465, Feb. 1990. Google ScholarDigital Library
- L. Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133--169, May 1998. Google ScholarDigital Library
- B. Liskov. Distributed programming in Argus. Commununications of the ACM, 31(3):300--312, 1988. Google ScholarDigital Library
- B. Liskov, M. Castro, L. Shrira, and A. Adya. Providing persistent objects in distributed systems. In European Conference on Object--Oriented Programming, pages 230--257, June 1999. Google ScholarDigital Library
- J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In Symposium on Operating Systems Design and Implementation, pages 105--120, Dec. 2004. Google ScholarDigital Library
- P. Mehra and S. Fineberg. Fast and flexible persistence: the magic potion for fault-tolerance, scalability and performance in online data stores. In International Parallel and Distributed Processing Symposium -- Workshop 11, page 206a, Apr. 2004.Google Scholar
- M. A. Olson. The design and implementation of the Inversion File System. In USENIX Winter Conference, pages 205--218, Jan. 1993.Google Scholar
- RDMA Consortium. http://www.rdmaconsortium.org.Google Scholar
- M. Satyanarayanan, J. J. Kistler, P. Kumar, M. E. Okasaki, E. H. Siegel, and D. C. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE Transactions on Computers, 39(4):447--459, Apr. 1990. Google ScholarDigital Library
- M. Satyanarayanan, H. H. Mashburn, P. Kumar, D. C. Steere, and J. J. Kistler. Lightweight recoverable virtual memory. ACM Transactions on Computer Systems, 12(1):33--57, Feb. 1994. Google ScholarDigital Library
- A. Schiper and S. Toueg. From set membership to group membership: A separation of concerns. IEEE Transactions on Dependable and Secure Computing, 3(1):2--12, Feb. 2006. Google ScholarDigital Library
- F. B. Schmuck and J. C. Wyllie. Experience with transactions in QuickSilver. In Symposium on Operating Systems Principles, pages 239--253, Oct. 1991. Google ScholarDigital Library
- R. Sears and E. Brewer. Stasis: Flexible transactional storage. In Symposium on Operating Systems Design and Implementation, pages 29--44, Oct. 2006. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software transactional memory. In Symposium on Principles of Distributed Computing, pages 204--213, Aug. 1995. Google ScholarDigital Library
- D. Skeen and M. Stonebraker. A formal model of crash recovery in a distributed system. IEEE Transactions on Software Engineering, 9(3):219--228, May 1983. Google ScholarDigital Library
- A. Z. Spector et al. Camelot: a distributed transaction facility for Mach and the Internet -- an interim report. Research paper CMU--CS--87--129, Carnegie Mellon University, Computer Science Dept., June 1987.Google Scholar
Index Terms
- Sinfonia: a new paradigm for building scalable distributed systems
Recommendations
Sinfonia: A new paradigm for building scalable distributed systems
We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols, a major complication in existing distributed systems. Instead, developers just design and manipulate data ...
Sinfonia: a new paradigm for building scalable distributed systems
SOSP '07We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols -- a major complication in existing distributed systems. Instead, developers just design and manipulate data ...
An approach to efficient distributed transactions
Most distributed systems proposed on the basis of the concept of atomic action or transaction strongly limit parallelism, thus reducing their level of efficiency. In this paper, features of efficiency in a distributed transaction system are ...
Comments