Storage 4: Consistency

Clean and dirty slots

Data in a read cache is sometimes in sync with underlying storage, and sometimes—if the cache is incoherent—that data is older than underlying storage.

Conversely, sometimes data in a write cache is newer than underlying storage. This can happen if the write cache is coalescing writes or batching, and therefore contains data written by its user that have not been written yet to the underlying slower storage.

A slot that contains data newer than underlying storage is called dirty. A slot containing data that is not newer than underlying storage is called clean.

For an example of both incoherent caches and dirty slots, consider the following steps involving a single file, f.txt, that’s opened twice by stdio, once for reading and once for writing. (Either the same program called fopen twice on the same file, or two different programs called fopen on the same file.) The first column shows the buffer cache’s view of the file (which is coherent with the underlying disk). The other two show the stdio caches’ views of the file. The file initially contains all “A”s.

Buffer cache Stdio cache f1 Stdio cache f2
1. Initial state of f.txt “AAAAAAAAAA”
2. f1 = fopen("f.txt", "r") “AAAAAAAAAA” (empty)
3. fgetc(f1) “AAAAAAAAAA” “AAAAAAAAAA”
4. f2 = fopen("f.txt", "w") “AAAAAAAAAA” “AAAAAAAAAA” (empty)
5. fprintf(f2, "BB…") “AAAAAAAAAA” “AAAAAAAAAA” “BBBBBBBBBB”
6. fflush(f2) “BBBBBBBBBB” “AAAAAAAAAA” (empty)

At step 5, after fprintf but before fflush, f2’s stdio cache is dirty: it contains newer data than underlying storage. At step 6, after fflush, f1’s stdio cache demonstrates incoherence: it contains older data than underlying storage. At steps 2–4, though, f1’s stdio cache is clean and coherent.

A cache that never contains dirty slots is called a write-through cache. Write-through caches can’t perform write coalescing or batching for writes: every write to the cache goes immediately “through” to underlying storage. Such caches are mostly useful for reads. A cache that can contain dirty slots is called a write-back cache.

System call atomicity

Unix file system system calls, such as read and write, should have atomic effect. Atomicity is a correctness property that concerns concurrency—the behavior of a system when multiple computations are happening at the same time. (For example, multiple programs have the file open at the same time.)

An operation is atomic, or has atomic effect, if it always behaves as if it executes without interruption, at one precise moment in time, with no other operation happening. Atomicity is good because it makes complex behavior much easier to understand.

The standards that govern Unix say reads and writes should have atomic effect. It is the operating system kernel’s job to ensure this atomic effect, perhaps by preventing different programs from read or writing to the same file at the same time.

Unfortunately for our narrative, experiment shows that on Linux many write system calls do not have atomic effect, meaning Linux has bugs. But writes made in “append mode” (open(… O_APPEND) or fopen(…, "a")) do have atomic effect. In this mode, which is frequently used for log files, writes are always placed at the end of the open file, after all other data.