article

Free access

A coherent distributed file cache with directory write-behind

Editor: Ken Birman Authors:

Garret SwartAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 12, Issue 2

Pages 123 - 164

https://doi.org/10.1145/176575.176577

Published: 01 May 1994 Publication History

PDF eReader

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.]]

Google Scholar

[2]

BAKER, M., ASAMI, S., DEPRIT, E., OUSTERHOUT, J., AND SELTZER, M., 1992. Non-volatile memory for fast, reliable file systems. In Proceedings 5th International Conference on Architectural Support for Prograramlng Languages and Operatzng Systems (Boston, Mass, Oct. 12-15). ACM, New York, pp 10 22]]

Crossref

Google Scholar

[3]

BAKER, M. G., HARTMAN, J. H., KUPFER, M. D., SHIRRIFF, K. W., AND OUSTERHOUT, J. K. 1991. Measurements of a distributed file system. In Proceedings 13th Symposium on Operating Systems Principles (Pacific Grove, Calif., Oct. 13-16). ACM, New York, pp. 198-212.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[5]

BURROWS, M., 1988. Efficient data sharing. Ph.D. thesis, Computer Laboratory, Univ. of Cambridge, U.K. Sept.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[8]

GRAY, C. G., AND CHERITON, D. R., 1989. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In Proceedings 12th Symposium on Operating Systems Principles (Litchfield Park, Ariz., Dec. 3-6) ACM, New York, pp. 202 210.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[14]

HOWARD, J. H., KAZAR, M. L., MENEES, S. G., NICHOLS, D. A., SATYANARAYNAN, M., SIDEBOTHAM, R. N., AND WEST, M. J. 1988. Scale and performance in a distributed file system. ACM Trans. Comput. Syst. 6, 1 (Feb.), 51-81.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[16]

KISTLER, J. J., AND SATYANARAYNAN, M. 1991. Disconnected operation in the coda file system. In Proceedtngs 13th Symposium on Operating Systems Prtnc~ples (Oct.). ACM, New York, pp. 213-225.]]

Crossref

Google Scholar

[17]

LAMPSON, B., ABADI, M., BURROWS, AND M., AND WOBBER, E. 1991. Authentication in distributed systems: Theory and practice. In Proceedings 13th Symposium on Operating Systems Princples (Oct.). ACM, New York, pp. 165 182.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[20]

NELSON, M. N., WELCH, B. B., AND OUSTERHOUT, J. K. 1988. Caching in the Sprite network file system. ACM Trans. Comput. Syst. 6, i (Feb.), 134-154.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[22]

POPEK G., WALKER, B., CHOW, J., EDWARDS, D., KLINE, C., RUDISIN, G, AND THIEL, G. 1981. LOCUS: A network transparent, high reliability distributed system. In Proceedings 8th Symposzum on Operating Systenzs Prznczples (Pacific Grove, Calif., Dec. 14-16). ACM, New York, pp. 169 177.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[24]

SCHMUCK, F., AND WYLLIE, J. 1991. Experience with transactions in QuickSilver. In Proceedzngs 13th Sympos~ura on Operating Systems Prznc~ples (Pacific Grove, Calif., Oct. 13-16). ACM, New York, pp. 239-253.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[26]

SUN MICROSYSTEMS, INC. 1989. NFS: Network file system protocol specificatmn. RFC 1094, Network Information Center, SRI International, Menlo Park, Calif., Mar.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[29]

WALm~R, B., POPEK, G., ENGLISH, R., KL~NE, C. AND THmL, G 1983. The LOCUS distributed operating system. In Proceedings 9th Symposzum on Operatzng Systems Principles (Bretton Woods, N.H., Oct. 12-13). ACM, New York, pp. 49 70.]]

Crossref

Google Scholar

[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]]

Google Scholar

Cited By

View all

Hatzieleftheriou AAnastasiadis S(2017)Client-Side Journaling for Durable Shared StorageACM Transactions on Storage10.1145/314937213:4(1-34)Online publication date: 17-Nov-2017
https://dl.acm.org/doi/10.1145/3149372
Hatzieleftheriou AAnastasiadis SSchindler JZadok E(2015)Host-side filesystem journaling for durable shared storageProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750487(59-66)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750487
Paz A(2013)Bremen workshop reviewACM SIGACT News10.1145/2556663.255668444:4(91-97)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.1145/2556663.2556684
Show More Cited By

Index Terms

A coherent distributed file cache with directory write-behind
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Distributed memory
    2. Software system structures
      1. Distributed systems organizing principles

Recommendations

Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling

As the performance gap between disks and micropocessors continues to increase, effective utilization of the file cache becomes increasingly immportant. Application-controlled file caching and prefetching can apply application-specific knowledge to ...
PS directory: a scalable multilevel directory cache for CMPs

As the number of cores increases in current and future chip-multiprocessor (CMP) generations, coherence protocols must rely on novel hardware structures to scale in terms of performance, power, and area. Systems that use directory information for ...
Coordinating Simultaneous Caching of File Bundles from Tertiary Storage
SSDBM '00: Proceedings of the 12th International Conference on Scientific and Statistical Database Management

In a previous paper, we described a system called STACS (Storage Access Coordination System) for High Energy and Nuclear Physics (HENP) experiments. These experiments generate very large volumes of event data at a very high rate. The volumes of data may ...

Reviews

Reviewer: Caroline Merriam Eastman

Echo is a distributed file system based on a client-server architecture. This paper describes its design, implementation, and performance, and addresses security and fault-tolerance issues. Most of the paper is devoted to a description of Echo's contributions and novel features; there is some discussion of its limitations, and it is compared to similar systems. Echo is no longer in use and is not being developed any further. Key features of Echo include the use of large client caches and ordered write-behind for both files and directories. Concurrency control is handled through tokens issued to clients. Leases specify the maximum time a client is allowed to hold a token, thus allowing tokens to be reclaimed and preventing a failed client from tying up a resource. The procedures used to maintain transaction order are discussed in exhaustive detail. Performance results for different implementations on a network of DEC Fireflies are presented. For three benchmarks, full write-behind gave the lowest elapsed time, and write-back on close gave the highest; directory write-through was intermediate. The results were much more dramatic for the tasks involving compilation of many small C programs and the creation of a new version of a software package using the Vesta configuration management system than for the task involving the make phase of the Andrew benchmark. The results indicate that full write-behind might give modest performance improvements on many realistic workloads. Echo was also compared to a UNIX implementation on similar hardware. As is usual in such comparisons, it is hard to isolate the reasons for performance differences. No statistical tests are presented. Comprehensive descriptions of complete implemented systems are an important contribution and serve to advance the field of computer systems development. This paper provides such a description for Echo; it should interest researchers and developers of file systems, operating systems, and distributed systems.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 12, Issue 2

May 1994

74 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/176575

Editor:
Ken Birman
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1994

Published in TOCS Volume 12, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
928
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)9

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hatzieleftheriou AAnastasiadis S(2017)Client-Side Journaling for Durable Shared StorageACM Transactions on Storage10.1145/314937213:4(1-34)Online publication date: 17-Nov-2017
https://dl.acm.org/doi/10.1145/3149372
Hatzieleftheriou AAnastasiadis SSchindler JZadok E(2015)Host-side filesystem journaling for durable shared storageProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750487(59-66)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750487
Paz A(2013)Bremen workshop reviewACM SIGACT News10.1145/2556663.255668444:4(91-97)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.1145/2556663.2556684
Braud-Santoni N(2013)PODC 2013 reviewACM SIGACT News10.1145/2556663.255668244:4(83-86)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.1145/2556663.2556682
Bhattacharyya A(2013)Guest columnACM SIGACT News10.1145/2556663.255667844:4(53-72)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.1145/2556663.2556678
Criminisi ASharp TRother CP'erez P(2010)Geodesic image and video editingACM Transactions on Graphics10.1145/1857907.185791029:5(1-15)Online publication date: 5-Nov-2010
https://dl.acm.org/doi/10.1145/1857907.1857910
Halli ASaaidi ASatori KTairi H(2010)Extrusion and revolution mappingACM Transactions on Graphics10.1145/1857907.185790829:5(1-14)Online publication date: 5-Nov-2010
https://dl.acm.org/doi/10.1145/1857907.1857908
Sears RBrewer E(2009)Segment-based recoveryProceedings of the VLDB Endowment10.14778/1687627.16876832:1(490-501)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.14778/1687627.1687683
Frost CMammarella MKohler Ede los Reyes AHovsepian SMatsuoka AZhang L(2007)Generalized file system dependenciesACM SIGOPS Operating Systems Review10.1145/1323293.129429141:6(307-320)Online publication date: 14-Oct-2007
https://dl.acm.org/doi/10.1145/1323293.1294291
Gunawi HPrabhakaran VKrishnan SArpaci-Dusseau AArpaci-Dusseau R(2007)Improving file system reliability with I/O shepherdingACM SIGOPS Operating Systems Review10.1145/1323293.129429041:6(293-306)Online publication date: 14-Oct-2007
https://dl.acm.org/doi/10.1145/1323293.1294290
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling

PS directory: a scalable multilevel directory cache for CMPs

Coordinating Simultaneous Caching of File Bundles from Tertiary Storage

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations