Speculative execution in a distributed file system

ABSTRACT

Speculator provides Linux kernel support for speculative execution. It allows multiple processes to share speculative state by tracking causal dependencies propagated through inter-process communication. It guarantees correct execution by preventing speculative processes from externalizing output, e.g., sending a network message or writing to the screen, until the speculations on which that output depends have proven to be correct. Speculator improves the performance of distributed file systems by masking I/O latency and increasing I/O throughput. Rather than block during a remote operation, a file system predicts the operation's result, then uses Speculator to checkpoint the state of the calling process and speculatively continue its execution based on the predicted result. If the prediction is correct, the checkpoint is discarded; if it is incorrect, the calling process is restored to the checkpoint, and the operation is retried. We have modified the client, server, and network protocol of two distributed file systems to use Speculator. For PostMark and Andrew-style benchmarks, speculative execution results in a factor of 2 performance improvement for NFS over local-area networks and an order of magnitude improvement over wide-area networks. For the same benchmarks, Speculator enables the Blue File System to provide the consistency of single-copy file semantics and the safety of synchronous I/O, yet still outperform current distributed file systems with weaker consistency and safety.

REFERENCES

• 1: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: Birrell, A. D., Hisgen, A., Jerian, C., Mann, T., and Swart, G. The Echo distributed file system. Tech. Rep. 111, Digital Equipment Corporation, Palo Alto, CA, USA, October 1993.
• 3: Callaghan, B., Pavlowski, B., and Staubach, P. NFS Version 3 Protocol Specification. Tech. Rep. RFC 1813, IETF, June 1995.
• 4: Carson, M. Adaptation and Protocol Testing thorugh Network Emulation. NIST, http://snad.ncsl.nist.gov/itg/nistnet/slides/index.htm.
• 5: Castro, M., and Liskov, B. Proactive recovery in a byzantine-fault-tolerant system. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (San Diego, CA, October 2000).
• 6: Fay Chang , Garth A. Gibson, Automatic I/O hint generation through speculative execution, Proceedings of the third symposium on Operating systems design and implementation, p.1-14, February 1999, New Orleans, Louisiana, United States
• 7: D. R. Cheriton , K. J. Duda, Logged virtual memory, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.26-38, December 03-06, 1995, Copper Mountain, Colorado, United States
• 8: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 9: Manoj Franklin , Gurindar S. Sohi, ARB: A Hardware Mechanism for Dynamic Reordering of Memory References, IEEE Transactions on Computers, v.45 n.5, p.552-571, May 1996 [doi>10.1109/12.509907]
• 10: Fraser, K., and Chang, F. Operating system I/O speculation: How two invocations are faster than one. In Proceedings of the 2003 USENIX Technical Conference (San Antonio, TX, June 2003), pp. 325--338.
• 11: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 12: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 13: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 14: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 15: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States
• 16: Katcher, J. PostMark: A new file system benchmark. Tech. Rep. TR3022, Network Appliance, 1997.
• 17: Samuel T. King , Peter M. Chen, Backtracking intrusions, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 18: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 19: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 20: Li, J., Krohn, M., Mazières, D., and Shasha, D. Secure untrusted data repository (SUNDR). In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (San Francisco, CA, December 2004), pp. 121--136.
• 21: Liskov, B., and Rodrigues, R. Transactional file systems can be fast. In Proceedings of the 11th SIGOPS European Workshop (Leuven, Belgium, September 2004).
• 22: David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
• 23: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 24: Nightingale, E. B., and Flinn, J. Energy-efficiency and storage flexibility in the Blue File System. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (San Francisco, CA, December 2004), pp. 363--378.
• 25: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 26: Frank Schmuck , Jim Wylie, Experience with transactions in QuickSilver, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.239-253, October 13-16, 1991, Pacific Grove, California, United States
• 27: Shepler, S., Callaghan, B., Robinson, D., Thurlow, R., Beame, C., Eisler, M., and Noveck, D. Network File System (NFS) version 4 Protocol. Tech. Rep. RFC 3530, IETF, April 2003.
• 28: Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, Proceedings of the tenth ACM symposium on Operating systems principles, p.127-146, December 1985, Orcas Island, Washington, United States
• 29: Srinivasan, S., Andrews, C., Kandula, S., and Zhou, Y. Flashback: A light-weight extension for rollback and deterministic replay for software debugging. In Proceedings of the 2004 USENIX Technical Conference (Boston, MA, June 2004).
• 30: V. Srinivasan , J. Mogul, Spritely NFS: experiments with cache-consistency protocols, Proceedings of the twelfth ACM symposium on Operating systems principles, p.44-57, November 1989
• 31: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 32: Matthew J. Weinstein , Thomas W. Page, Jr. , Brian K. Livezey , Gerald J. Popek, Transactions and synchronization in a distributed operating system, Proceedings of the tenth ACM symposium on Operating systems principles, p.115-126, December 1985, Orcas Island, Washington, United States
• 33: Y. Zhang , L. Rauchwerger , J. Torrellas, Hardware for Speculative Parallelization of Partially-Parallel Loops in DSM Multiprocessors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.135, January 09-12, 1999
• 34: Zhu, N., and Chiueh, T. Design, implementation and evaluation of the Repairable File Service. In Proceedings of the International Conference on Dependable Systems and Networks (San Francisco, CA, June 2003).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
      D.4.8 Performance

Keywords:
causality, distributed file systems, speculative execution