The Chubby lock service for loosely-coupled distributed systems

ABSTRACT

We describe our experiences with the Chubby lock service, which is intended to provide coarse-grained locking as well as reliable (though low-volume) storage for a loosely-coupled distributed system. Chubby provides an interface much like a distributed file system with advisory locks, but the design emphasis is on availability and reliability, as opposed to high performance. Many instances of the service have been used for over a year, with several of them each handling a few tens of thousands of clients concurrently. The paper describes the initial design and expected use, compares it with actual use, and explains how the design had to be modified to accommodate the differences.

References

1. Birman, K. P., and Joseph, T. A. Exploiting virtual synchrony in distributed systems. In 11th SOSP (1987), pp. 123--138.
2. Birrell, A., Jones, M. B., and Wobber, E. A simple and efficient implementation for small databases. In 11th SOSP (1987), pp. 149--154.
3. Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R. Bigtable: A distributed structured data storage system. In 7th OSDI (2006).
4. Dean, J., and Ghemawat, S. MapReduce: Simplified data processing on large clusters. In 6th OSDI (2004), pp. 137--150.
5. Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374--382.
6. French, R. S., and Kohl, J. T. The Zephyr Programmer's Manual. MIT Project Athena, Apr. 1989.
7. Ghemawat, S., Gobioff, H., and Leung, S.-T. The Google file system. In 19th SOSP (Dec. 2003), pp. 29--43.
8. Gosling, J., Joy, B., Steele, G., and Bracha, G. Java Language Spec. (2nd Ed.). Addison-Wesley, 2000.
9. Gray, C. G., and Cheriton, D. R. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In 12th SOSP (1989), pp. 202--210.
10. Howard, J., Kazar, M., Menees, S., Nichols, D., Satyanarayanan, M., Sidebotham, R., and West, M. Scale and performance in a distributed file system. ACM TOCS 6, 1 (Feb. 1988), 51--81.
11. Jefferson, D. Virtual time. ACM TOPLAS, 3 (1985), 404--425.
12. Lamport, L. The part-time parliament. ACM TOCS 16, 2 (1998), 133--169.
13. Lamport, L. Paxos made simple. ACM SIGACT News 32, 4 (2001), 18--25.
14. Lampson, B. W. How to build a highly available system using consensus. In Distributed Algorithms, vol. 1151 of LNCS. Springer-Verlag, 1996, pp. 1--17.
15. Liang, S. Java Native Interface: Programmer's Guide and Reference. Addison-Wesley, 1999.
16. MacCormick, J., Murphy, N., Najork, M., Thekkath, C. A., and Zhou, L. Boxwood: Abstractions as the foundation for storage infrastructure. In 6th OSDI (2004), pp. 105--120.
17. Mann, T., Birrell, A., Hisgen, A., Jerian, C., and Swart, G. A coherent distributed file cache with directory write-behind. TOCS 12, 2 (1994), 123--164.
18. McJones, P., and Swart, G. Evolving the UNIX system interface to support multithreaded programs. Tech. Rep. 21, DEC SRC, 1987.
19. Oki, B., and Liskov, B. Viewstamped replication: A general primary copy method to support highly-available distributed systems. In ACM PODC (1988).
20. Olson, M. A., Bostic, K., and Seltzer, M. Berkeley DB. In USENIX (June 1999), pp. 183--192.
21. Pike, R., Presotto, D. L., Dorward, S., Flandrena, B., Thompson, K., Trickey, H., and Winterbottom, P. Plan 9 from Bell Labs. Computing Systems 8, 2 (1995), 221--254.
22. Ritchie, D. M., and Thompson, K. The UNIX timesharing system. CACM 17, 7 (1974), 365--375.
23. Snaman, Jr., W. E., and Thiel, D. W. The VAX/VMS distributed lock manager. Digital Technical Journal 1, 5 (Sept. 1987), 29--44.
24. Yin, J., Martin, J.-P., Venkataramani, A., Alvisi, L., and Dahlin, M. Separating agreement from execution for byzantine fault tolerant services. In 19th SOSP (2003), pp. 253--267.

• General and reference

  • Cross-computing tools and techniques

• Social and professional topics

  • Professional topics

    • Computing profession

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

    • Software system structures