FaTLease: scalable fault-tolerant lease negotiation with paxos

ABSTRACT

A lease is a token which grants its owner exclusive access to a resource for a defined span of time. In order to be able to tolerate failures, leases need to be coordinated by distributed processes. We present FaTLease, an algorithm for fault-tolerant lease negotiation in distributed systems. It is built on the Paxos algorithm for distributed consensus, but avoids Paxos' main performance bottleneck of requiring persistent state. This property makes our algorithm particularly useful for applications that can not dispense any disk bandwidth. Our experiments show that FaTLease scales up to tens of thousands of concurrent leases and can negotiate thousands of leases per second in both LAN and WAN environments.

REFERENCES

• 1: R. Boichat, P. Dutta, S. Frolund, and R. Guerraoui. Deconstructing paxos. SIGACT News, 34(1):47--67, 2003.
• 2: M. Burrows. Chubby distributed lock service. In Proceedings of the 7th Symposium on Operating System Design and Implementation, OSDI'06, Seattle, WA, November 2006.
• 3: T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: an engineering perspective. In PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 398--407, New York, NY, USA, 2007. ACM Press.
• 4: T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, 1996.
• 5: S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google file system. In SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29--43, New York, NY, USA, 2003. ACM Press.
• 6: C. Gray and D. Cheriton. Leases: an efficient fault-tolerant mechanism for distributed file cache consistency. In SOSP '89: Proceedings of the twelfth ACM symposium on Operating systems principles, pages 202--210, New York, NY, USA, 1989. ACM Press.
• 7: F. Hupfeld, T. Cortes, B. Kolbeck, J. Stender, E. Focht, M. Hess, J. Malo, J. Marti, and E. Cesario. XtreemFS: a case for object-based storage in Grid data management. In 3rd VLDB Workshop on Data Management in Grids, co-located with VLDB 2007, 2007.
• 8: R. Jiménez-Peris, M. Patiño-Martínez, G. Alonso, and B. Kemme. Are quorums an alternative for data replication? ACM Trans. Database Syst., 28(3):257--294, 2003.
• 9: L. Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133--169, 1998.
• 10: L. Lamport. Paxos made simple. SIGACT News, 32(4):18--25, 2001.
• 11: B. W. Lampson. How to build a highly available system using consensus. In WDAG '96: Proceedings of the 10th International Workshop on Distributed Algorithms, pages 1--17, London, UK, 1996. Springer-Verlag.
• 12: J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In OSDI, pages 105--120, 2004.
• 13: R. D. Prisco, B. Lampson, and N. Lynch. Revisiting the Paxos algorithm. Theor. Comput. Sci., 243(1-2):35--91, 2000.
• 14: C. A. Thekkath, T. Mann, and E. K. Lee. Frangipani: a scalable distributed file system. SIGOPS Oper. Syst. Rev., 31(5):224--237, 1997.
• 15: R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In OSDI, pages 91--104, 2004.
• 16: M. Welsh, D. Culler, and E. Brewer. Seda: an architecture for well-conditioned, scalable internet services. SIGOPS Oper. Syst. Rev., 35(5):230--243, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Theory

Keywords:
high-availability, leases, locks, paxos, replication