A coherent distributed file cache with directory write-behind

ABSTRACT

Extensive caching is a key feature of the Echo distributed file system. Echo client machines maintain coherent caches of file and directory data and properties, with write-behind (delayed write-back) of all cached information. Echo specifies ordering constraints on this write-behind, enabling applications to store and maintain consistent data structures in the file system even when crashes or network faults prevent some writes from being completed. In this paper we describe the Echo cache's coherence and ordering semantics, show how they can improve the performance and consistency of applications, explain how they are implemented. We also discuss the general problem of reliably notifying applications and users when write-behind is lost; we addressed this problem as part of the Echo design, but did not find a fully satisfactory solution.

REFERENCES

• 1: BAKER, M., AND SULLIVAN, M. 1992. The recovery box. Using fast recovery to provide h~gh availabfilty in the UNIX environment. In Proceedings Summer 1992 USENIX Conference (June) USENIX Association, Berkeley, Calif., pp. 31 43.
• 2: Mary Baker , Satoshi Asami , Etienne Deprit , John Ouseterhout , Margo Seltzer, Non-volatile memory for fast, reliable file systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.10-22, October 12-15, 1992, Boston, Massachusetts, United States
• 3: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 4: BIRRELL, A. D., HISGEN, A., JERIAN, C., MANN, T., AND SWART, G. 1993. The Echo distributed file system. Res. Rep. Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif, Sept.
• 5: BURROWS, M., 1988. Efficient data sharing. Ph.D. thesis, Computer Laboratory, Univ. of Cambridge, U.K. Sept.
• 6: CHIU S.-Y., AND LEVIN, R. 1993. The Vesta repository: A file system extension for software development. Res. Rep. 106, Systems Research Center, Digital Equipment Corporation, Pa}o Alto, Calif.
• 7: GLASSMAN, L., GRINBERG, D., HIBBARD, C., REID, L. G., AND VAN LEUNEN, M. C. 1992. Hector: Connecting words with definitions. Res. Rep. 92A, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif., Oct.
• 8: C. Gray , D. Cheriton, Leases: an efficient fault-tolerant mechanism for distributed file cache consistency, Proceedings of the twelfth ACM symposium on Operating systems principles, p.202-210, November 1989
• 9: GuY, R. G., AND POPEK, G. J. 1991. Algorithms for consistency in optimistically replicated file systems. Tech. Rep. CSD-910006, UCLA Computer Science Dept. UCLA, Los Angeles, Calif., Mar.
• 10: HISGEN, A., BIRRELL, A., JERIAN, C., MANN, T., AND SWART, G. 1992. Some consequences of excess load on the Echo replicated file system. In Proceedings 2rid Workshop on the Management of Replicated Data (Monterey, Calif., Nov. 12-13). IEEE, New York, pp. 92-95.
• 11: HISGEN, A., BIRRELL, A., JERIAN, C., MANN, T., AND SWART, G., 1993. New-value logging in the Echo replicated file system. Res. Rep. 104, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif., June.
• 12: HISGEN, A., BmRELL, A., MANN, T., SCnROEDER, M., AND SWART, G. 1989. Availability and consistency tradeoffs in the Echo distributed file system. In Proceedings 2nd Workshop on Workstation Operating Systems (Pacific Grove, Calif., Sept. 27 29). IEEE, New York, pp. 49-54.
• 13: HISGEN, A., BIRRELL, A., JERIAN, C., MAN~, T., SCHROEDER, M., AND SWART, G., 1990. Granularity and semantic level of replication in the Echo distributed file system. In Proceedzngs Workshop on the Management of Replicated Data (Houston, Tex., Nov. 8 9). IEEE, New York, pp. 2-4.
• 14: 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]
• 15: KAZAR, M. L., 1988. Synchronization and caching issues in the Andrew file system. In Proceedings Winter 1988 USENIX Conference (Dallas, Tex., Feb. 9 12). USENIX Association, Berkeley, Calif., pp. 27-36.
• 16: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.213-225, October 13-16, 1991, Pacific Grove, California, United States
• 17: Butler Lampson , Martín Abadi , Michael Burrows , Edward Wobber, Authentication in distributed systems: theory and practice, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.165-182, October 13-16, 1991, Pacific Grove, California, United States
• 18: LEVIN, R., AND MCJONES, P. 1993. The Vesta approach to precise configuration of large software systems. Res. Rep. 105, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif.
• 19: MANN, T., HISGEN, A., AND SWART, G. 1989. An algorithm for data replication. Res. Rep. 46, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif. June.
• 20: 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]
• 21: PAGE, T. W. JR., GUY. R. G., POPEK, G. J_, ANn HEIDEMANN, J. S. 1991. Architecture of the Ficus scalable replicated file system. Tech. Rep. CSD-910005, UCLA Computer Science Dept., UCLA, Los Angeles, Calif., Mar.
• 22: G. Popek , B. Walker , J. Chow , D. Edwards , C. Kline , G. Rudisin , G. Thiel, LOCUS a network transparent, high reliability distributed system, Proceedings of the eighth ACM symposium on Operating systems principles, p.169-177, December 14-16, 1981, Pacific Grove, California, United States
• 23: SANDBERG, R., GOLDBERG, D., KLEIMAN, S., WALSH, D., AND LYON, B. 1985. Design and implementation of the Sun network filesystem. In Proceedzngs Summer 1985 USENIX Conference (Portland, Ore., June. 11-14). USENIX Association, Berkeley, Calif., pp. 119-130.
• 24: 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
• 25: SCHROEDER, M. D., BIRRELL, A. D., BURROWS, M., MURRAY, H., NEEDHAM, R. M., RODEHEFFER, T L., SATrERHWAITE, E. H., A~D T~ACXER, C. P. 1990 Autonet: A high-speed, self-configuring local area network using point-to-point links. Res. Rep. 59, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif., Apr.
• 26: SUN MICROSYSTEMS, INC. 1989. NFS: Network file system protocol specificatmn. RFC 1094, Network Information Center, SRI International, Menlo Park, Calif., Mar.
• 27: SWART, G., BIRRELL, A., HISGEN, A., JERIAN, C., AND MANN, T 1993. Availability in the Echo file system. Res. Rep. 112, Systems Research Center, Digital Equipment Corporation, Palo Alto, Calif., Sept.
• 28: THACKER, C. P., STEWART, L. C., AND SATrERTHWAITE, E. H, JR. 1987. Firefly: A multiprocessor workstation. Res. Rep. 23, Systems Research Center, Digital Eqmpment Corporation, Palo Alto, Calif., Dec.
• 29: Bruce Walker , Gerald Popek , Robert English , Charles Kline , Greg Thiel, The LOCUS distributed operating system, Proceedings of the ninth ACM symposium on Operating systems principles, p.49-70, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 30: WELC}~, B., AND OUST~RHOUT, J. 1986. Prefix tables' A simple mechanism for locating files m a distributed filesystem. In Procee&ngs 6th International Conference on Distributed Computing Systems (Cambridge, Mass., May 19-23). IEEE, New York, pp. 184-189

INDEX TERMS

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

General Terms:
Design, Experimentation, Measurement, Performance, Reliability, Security

Keywords:
coherence, file caching, write-behind