One file, many caches

On one computer, sharing a file is a solved problem that nobody notices. Two programs open the same file, one writes, the other reads, and the reader sees the write. Put the two programs on different computers, and every part of that sentence needs a decision: where the bytes live, who keeps a copy, when a copy goes out of date, and who may write next.

This page builds those decisions up one at a time, starting from a single machine. Each step is a problem that some system’s designers had to solve, and the examples are their systems: AFS at Carnegie Mellon, NFS at Sun, Amazon S3, and Google’s Chubby lock service.

One copy, then many§

On one machine, every process that reads a file goes through the kernel’s page cache, so there’s exactly one cached copy of each page. A write lands in that copy, and the next read, from any process, finds it there. POSIX writes this down as a rule: “If a read() of file data can be proven (by any means) to occur after a write() of the data, it must reflect that write(), even if the calls are made by different threads.” The same rationale adds that the rule “is particularly significant for networked file systems, where some caching schemes violate these semantics.”From the rationale of write() in POSIX.1-2024, The Open Group Base Specifications Issue 8.

Give a second machine its own cache, and that rule stops coming for free. Each machine now holds a copy, and a copy can be wrong. Cary Gray and David Cheriton, writing about distributed file caches in 1989, defined what “consistent” should mean: “the behavior is equivalent to there being only a single (uncached) copy of the data except for the performance benefit of the cache.”Gray and Cheriton, “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency”, SOSP 1989, section 1. Everything that follows is either a way to get close to that single copy, or a decision to settle for less in exchange for fewer round trips to a server.

Writes are bytes at offsets§

Before asking when a write becomes visible, be precise about what a write is. In object storage, a PUT replaces a whole object. Two clients that PUT the same key leave one complete version or the other. A file system has no such operation. write() puts some bytes at some offset, and a program saving a large file makes many of those calls.

POSIX promises that each call is atomic, and nothing more about writers who overlap: it “does not specify the behavior of concurrent writes to a regular file from multiple threads, except that each write is atomic”, and “applications should use some form of concurrency control.” So when two programs save the same file at the same moment, the last writer wins each range of bytes separately.

Appending doesn’t escape this across machines. Linux’s open(2) man page warns that O_APPEND “may lead to corrupted files on NFS filesystems if more than one process appends data to a file at once”, because NFS has no append operation, so the client has to simulate one, “which can’t be done without a race condition.”From the description of O_APPEND in the open(2) man page.

Keep this in mind through the next section. A consistency model decides when other machines see a write. None of them decides which of two conflicting writes should survive. That takes coordination: leases, ownership, and locks, later on this page.

Three promises on one timeline§

Storage systems describe their consistency with a handful of named promises. They differ in one thing: how long after a write a reader on another machine may still see the old data.

Linearizability is the strongest. Maurice Herlihy and Jeannette Wing defined it in 1990 as “the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response.”Herlihy and Wing, “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Transactions on Programming Languages and Systems 12(3), July 1990, abstract. For a file, it means that once A’s write() returns, any read that starts afterward, on any machine, returns the new bytes. That is the POSIX rule stretched across a network. Its price is that before A’s write returns, every cached copy must be updated or thrown away, or every read must ask the server.

Close-to-open consistency comes from the Andrew File System (AFS). Its designers at Carnegie Mellon wrote down their rules in 1988: “Writes to an open file by a process on a workstation are visible to all other processes on the workstation immediately but are invisible elsewhere in the network.” And: “Once a file is closed, the changes made to it are visible to new opens anywhere on the network. Already open instances of the file do not reflect these changes.”Howard and others, “Scale and Performance in a Distributed File System”, ACM Transactions on Computer Systems 6(1), February 1988, section 3. The Linux NFS client keeps the same promise. When a program opens a file, the client checks with the server, and when the program closes it, the client “writes back any pending changes”.From “Close-to-open cache consistency” in the nfs(5) man page. The promise covers an open that follows a close, and nothing else. A reader that already has the file open, or a writer that hasn’t closed it, is outside it.

Cached for a fixed time is the promise most clients actually keep for metadata. A client that keeps each entry for T seconds before asking again guarantees that what it shows is at most T seconds older than the server’s copy. The Linux NFS client caches a file’s attributes for 3 s to 60 s and a directory’s for 30 s to 60 s by default, set by the acregmin, acregmax, acdirmin, and acdirmax mount options.

Eventual consistency is the weakest useful promise. Werner Vogels put it as “if no new updates are made to the object, eventually all accesses will return the last updated value”, and called the gap before then the inconsistency window.Vogels, “Eventually Consistent”, revised for ACM Queue, December 2008. The model puts no bound on the window. Amazon S3 offered eventual consistency for years, and on December 1, 2020, AWS announced that S3 “now delivers strong read-after-write consistency automatically for all applications.”From the AWS announcement, posted December 1, 2020.

The second half of the figure matters most. Linearizable storage loses A’s edit as surely as eventual storage does, because the two machines never coordinated. A consistency model tells you when you’ll see another machine’s write. Stopping two machines from overwriting each other takes coordination, in which one of them is refused.

Finding out a copy is stale§

A cache has two ways to learn that its copy is out of date: it can ask, or it can be told. AFS tried both, and its paper measured the difference.

The AFS prototype asked. Its client checked a cached file’s timestamp with the server before every use, so “each open of a file thus resulted in at least one interaction with a server, even if the file were already in the cache and up to date.” Those checks, with status fetches, made up nearly 90 percent of the calls its servers handled. The revised AFS was told instead: “When a workstation caches a file or directory, the server promises to notify it before allowing a modification by any other workstation. This promise, called a Callback, dramatically reduces the number of cache validation requests received by servers.” For the redesign and its measurements in detail, see Anatomy of a file create over a network.

Callbacks have a cost of their own, and the AFS paper names it. The server has to remember every promise it made, and “before modifying a file or directory, a server has to notify every workstation that has a callback on that file.” If a client’s record of its promises drifts from the server’s, the two can disagree without either noticing. After a reboot, a client treats everything in its cache as suspect.

NFS chose to ask, on a timer. Its first published specification says the protocol “was intended to be as stateless as possible”, so that after a crash “a client need only retry a request until the server responds.”RFC 1094, “NFS: Network File System Protocol Specification”, March 1989, section 1.3. A server that keeps no promises can’t break any. The price is staleness, and the AFS authors noticed it at the time: they described NFS as a system “in which a file created on a workstation may not be visible on another workstation for 30 seconds.”

Leases§

A callback has a hole. A server that promised to notify a client can’t notify one that crashed or that the network cut off. It can wait forever, or break its promise and let the client serve stale data. Gray and Cheriton’s answer was to put an expiry date on the promise:

A lease is a contract that gives its holder specified rights over property for a limited period of time. In the context of caching, a lease grants to its holder control over writes to the covered datum during the term of the lease, such that the server must obtain the approval of the leaseholder before the datum may be written.

When a client writes, “the server must defer the request until each leaseholder has granted approval or the term of its lease has expired.” A lease holder that answers approves the write and drops its copy at once. One that doesn’t answer holds up the write only until its lease runs out. As long as the clocks behave, a crash or a lost message costs time, not correctness.

The lease term is a trade. Short terms limit how long a failed client can hold up writers, and long terms mean fewer renewals. Using file-access measurements from the V distributed system, the paper found that short terms are enough: across its workload, a 10 s term gave a server load within 5 percent of an infinite term. For how the paper placed AFS on the same scale, see Anatomy of a file create over a network.

Leases do need one thing that callbacks don’t: clocks that agree closely enough. The paper names the failure: “a server clock that advances too quickly can cause errors because it may allow a write before the term of a lease held by a previous client has expired at that client.” A client clock that runs slow does the same harm. Its fix is modest: “the correct functioning of leases requires only that clocks have a known bounded drift.” The server waits out that bound before it lets the write through, which is the allowance in the “A lease running out” figure.

NFS version 4 put leases at its center. Its specification says lock state “is maintained at the server under a lease-based model”, and that a client which doesn’t renew in time can lose it: “all state associated with the client’s lease may be released by the server.”RFC 7530, “Network File System (NFS) Version 4 Protocol”, March 2015, sections 1.4.5 and 1.5. Version 4 also added delegations, in which the server can “delegate certain responsibilities to the client”, so that the client can “locally service operations” such as OPEN, CLOSE, LOCK, and READ. “Delegations can be recalled by the server,” which “requires that a callback path exist between the server and client.”

A delegation that covers writes is ownership. The client holding it can accept writes into its own memory and send them later, because nobody else may write the file in the meantime. That’s what makes an owned file nearly as fast as a local one. The cost moves to the handoff: before another client can write, the owner has to send everything it holds and give the delegation back.

Advisory locks§

Leases coordinate caches automatically. Locks are what a program asks for when it wants to coordinate with other programs, and on Linux they come in two kinds. fcntl() record locks cover byte ranges, and flock() covers a whole file. Both are advisory: “Advisory locks are not enforced and are useful only between cooperating processes.”From the fcntl_locking(2) man page, which also covers lost locks and NFS. Linux once had mandatory locking too. Its man page calls the implementation “unreliable”, and says the feature “is no longer supported at all in Linux 5.15 and above.”

Traditional fcntl() locks carry a trap even on one machine. “If a process closes any file descriptor referring to a file, then all of the process’s locks on that file are released.” A library that opens and closes your locked file for its own reasons drops your lock without telling you.

Across machines, a lock is state that the server has to keep, and NFS was designed to keep none. The first specification left locking out: “Inherently stateful operations such as file or record locking, and remote execution, were implemented as separate services.” NFS version 3 described that separate service, the Network Lock Manager, as isolating “the inherently stateful aspects of file locking into a separate protocol.”RFC 1813, “NFS Version 3 Protocol Specification”, June 1995, section 1. Version 4 brought locks into the protocol itself, under the same leases as everything else. The Linux client maps flock() onto fcntl() locks over NFS: “Since Linux 2.6.12, NFS clients support flock() locks by emulating them as fcntl(2) byte-range locks on the entire file.”From the notes in the flock(2) man page.

A lock held over a network can also be lost. The fcntl_locking man page describes a network partition “which lasts long enough for the server to assume that the client is no longer functioning.” Since Linux 3.12, an NFS version 4 client that loses its lock makes I/O fail for any process that “thinks” it still holds it, until that process closes and reopens the file. Linux once tried to recover such locks silently, and stopped by default “because of the attendant risk of data corruption.”

Why locking across machines is hard§

The lost lock in the preceding section points at the real difficulty. A lock is a promise about the past: when the holder checked, it held the lock. By the time its write reaches the storage, that may no longer be true. Google’s Chubby paper describes the sequence precisely: “a process holding a lock L may issue a request R, but then fail. Another process may acquire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on inconsistent data.”Burrows, “The Chubby lock service for loosely-coupled distributed systems”, OSDI 2006, section 2.4.

The holder doesn’t have to crash for this to happen. Martin Kleppmann’s example is a garbage-collection pause: if it “lasts longer than the lease expiry period, and the client doesn’t realise that it has expired”, the client wakes and writes as if it still held the lock.Kleppmann, “How to do distributed locking”, February 8, 2016. Checking the lease immediately before writing doesn’t help, because the pause can fall between the check and the write.

Both sources reach the same fix. Each grant of the lock carries a number that only goes up, and every write carries the number of the grant it was made under. The storage remembers the highest number it has seen and rejects anything older. Chubby calls this a sequencer, “an opaque byte-string that describes the state of the lock immediately after acquisition”, including “the lock generation number”. Kleppmann calls it a fencing token, and notes that it “requires the storage server to take an active role in checking tokens.” For servers that can’t check, Chubby falls back on a lock-delay: when a holder disappears without releasing a lock, nobody else may take it for a period of up to one minute.

For shared storage, this means a lock protects writes only if the component that accepts the write checks it. A lock the storage never sees protects only clients that cooperate and act on time.

A worked example: Archil§

Archil makes a specific set of these choices, and the vocabulary of this page describes them.

In conditional mode, any number of clients write the same paths at once. Their writes run on our servers, as they do over NFS, our servers apply them in the order they arrive, and the last write to reach the disk wins. A client that does most of the writing in a path can check it out instead, which our docs call a delegation. The holder answers open, write, and rename from memory, at local speed, and sends its changes to our servers about once a second and on every fsync(). Other clients can read the path in the meantime. Ownership is checked where the write lands: our servers refuse a write to a checked-out path from any other client, including through the disk’s S3 API, so a client that has lost its checkout can’t overwrite the new holder. Unlike a lease, a checkout doesn’t expire on its own. If the holder dies, someone takes the path over with archil checkout --force, and the writes the old client never sent are lost.For more information, see Sharing disks in our docs.

Readers use a cache with a fixed lifetime. A client keeps entries for 30 s by default, and archil invalidate-cache drops them so the next read goes to our servers.

For what this means for agents that share a workspace, see Storage for agents.