Performance and Fault-Tolerance in a Cache for Distributed File Service.

Caching data on client workstations can improve the performance of file service in a distributed system. Distributed systems, though, are subject to host crashes and communication failures, and techniques that are commonly used to improve the performance of file caching do not tolerate these failures. This dissertation describes how high performance can be obtained from caching while still tolerating failures and providing at least the same level of coherence, availability, and reliability that the file service would have without caching. Leasing is a time-based mechanism that guarantees that access to cached data is coherent with respect to arbitrary communication. The requirements for leasing to function correctly are stated, and it is shown how those requirements can be efficiently satisfied in a practical system that has both host crashes and lost messages. Leasings performance is evaluated using both closed-form estimates and trace-driven simulation. For the pattern of access to files in V and similar systems, performance is very good for lease terms of just a few seconds terms of this duration also give acceptable bounds on delays added due to failures. Several previous mechanisms for cache coherence are included as special cases of leasing, and leasing also allows a range of policies that can accommodate different access patterns. In addition, leasing can be extended to work with multilevel caching, with replicated data, ancf in conjunction with transactions. A prototype file service cache has been implemented for the V distributed operating system the caches design is described, and its performance is evaluated based on traces of file system access.