103 A Coherent Distributed File Cache With Directory Write behind Timothy Mann Andrew Birrell Andy Hisgen Charles Jerian and Garret Swart June 10 1993 digi tal Systems Research Center 130 Lytton Avenue Palo Alto California 94301 Systems Research Center The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems From our establishment in 1984 we have performed basic and applied research to support Digital s business objectives Our current work includes exploring distributed personal computing on multiple platforms networking programming technology system modelling and management techniques and selected applications Our strategy is to test the technical and practical value of our ideas by building hardware and software prototypes and using them as daily tools Interesting systems are too complex to be evaluated solely in the abstract extended use allows us to investigate their properties in depth This experience is useful in the short term in refining our designs and invaluable in the long term in advancing our knowledge Most of the major advances in information systems have come through this strategy including personal computing distributed systems and the Internet We also perform complementary work of a more mathematical flavor Some of it is in established fields of theoretical computer science such as the analysis of algorithms computational geometry and logics of programming Other work explores new ground motivated by problems that arise in our systems research We have a strong commitment to communicating our results exposing and testing our ideas in the research and development communities leads to improved understanding Our research report series supplements publication in professional journals and conferences We seek users for our prototype systems among those with whom we have common interests and we encourage collaboration with university researchers Robert W Taylor Director A Coherent Distributed File Cache With Directory Write behind Timothy Mann Andrew Birrell Andy Hisgen Charles Jerian and Garret Swart June 10 1993 c Digital Equipment Corporation 1993 This work may not be copied or reproduced in whole or in part for any commercial purpose Permission to copy in whole or in part without payment of fee is granted for nonprofit educational and research purposes provided that all such whole or partial copies include the following a notice that such copying is by permission of the Systems Research Center of Digital Equipment Corporation in Palo Alto California an acknowledgment of the authors and individual contributors to the work and all applicable portions of the copyright notice Copying reproducing or republishing for any other purpose shall require a license with payment of fee to the Systems Research Center All rights reserved 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 and 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 Contents 1 Introduction 1 2 Design motivation 2 3 Coherence and ordering semantics 4 3 1 Ordering constraints 5 3 2 Reporting lost write behind 10 4 Using the semantics 13 5 Performance 19 6 Implementation 6 1 Coherence 6 2 Fault tolerance 6 3 Security 6 4 Resource reservations 6 5 Ordering constraints 6 6 Reporting lost write behind 6 7 Advisory lock tokens 23 23 27 29 32 33 33 34 7 Related work 35 8 Conclusions 39 1 Introduction Echo is a distributed file system that incorporates replication caching global naming and distributed security Figure 1 gives a block diagram of the Echo system 1 Replication Echo replicates servers for availability and disks for data integrity allowing a wide range of configurations and tolerating both server crashes and network faults The interconnections between disks servers and client machines can be replicated as well Caching Echo client machines keep coherent write back caches of data and properties for both files and directories in volatile memory thereby reducing the latency seen by applications on file system operations and reducing the read load and peak write load on servers The caches use ordered writebehind that is updates buffered in the cache are automatically flushed after a time delay and are written to server disks in a well defined partial order thus limiting the damage that can occur when a client machine crashes and its volatile memory is erased We use the term clerk for the module in the client operating system that performs these functions Global naming Echo supports a globally scalable hierarchical name space The upper levels of the hierarchy are implemented using a replicated name service that achieves very high availability with loose consistency semantics while the lower levels are implemented by the file system with tight consistency but somewhat lower availability Distributed security Echo has adopted a security model in which servers do not trust client machines instead client machines use a cryptographic protocol to authenticate themselves as acting on behalf of the users who have logged in to them 16 This paper concentrates on Echo s client cache Separate papers give a complete overview of Echo 4 and discuss various other aspects in detail 9 10 11 12 18 25 In the next section we discuss the motivation for Echo s cache design then in Section 3 we present the cache s coherence and ordering semantics and the facilities for reporting lost write behind We show how these semantics are useful 1 Although Echo is no longer under development or in use to avoid awkwardness we speak of it in the present tense throughout this paper 1 Applications OS Echo Clerk Applications OS Echo Clerk Client machines Network Echo Server Echo Server primary secondary Server machines Disks Figure 1 Block diagram of the Echo system to some