Checksum Granularity and the Read-Modify-Write Penalty

One checksum can cover one byte or one gigabyte. The choice sets three things at once: how much data is lost when damage is detected, how much work a small overwrite costs, and whether the checksum can be recomputed without reading the rest of the region. Filesystems converged on a small set of answers for reasons that are mostly about the third, and the reasoning is worth reconstructing because it explains why a 4 KiB write can cost a 128 KiB read.

The three-way trade

Consider a 128 KiB extent covered by a single checksum. Verification on read is cheap: one pass over 128 KiB, one comparison, one verdict. Damage reporting is coarse: if the checksum fails, the filesystem knows only that something in those 128 KiB is wrong, and it must either discard all of it or verify sub-regions with additional information it may not have. Small writes are expensive: to change one byte, the writer must produce a new 128 KiB block whose checksum covers the new content, which means reading the other 131,071 bytes, patching, and writing the whole thing back — unless the filesystem uses copy-on-write at a finer granularity, in which case the extent is split first.

Now consider 512 bytes per checksum. Verification on read costs one pass and 256 comparisons for the same 128 KiB, negligible. Damage reporting is precise to 512 bytes. Small writes are cheap: changing one byte touches one 512-byte block, and its checksum covers only that block. The cost moves to metadata: 256 checksums of 4 bytes each is 1 KiB of checksum per 128 KiB of data, under one percent, and the checksums must be stored somewhere with an address for each — which is exactly the block-pointer or side-table problem described in checksum placement across pointers and metadata trees.

The trade is therefore not primarily about checksum bytes. It is about the ratio between the filesystem’s write granularity and its checksum granularity. When they are equal, a write is a write. When the checksum covers more than the write, every write becomes a read-modify-write over the checksum’s region. When the checksum covers less than the write, a write becomes several writes plus several checksums, which is fine as long as they are committed together.

Why the sector size forced the answer

Hard drives have been formatted in 512-byte sectors for decades, and 512 bytes is also the smallest unit the drive guarantees to write atomically with respect to power loss. That guarantee is the reason 512-byte checksums were natural: a checksum over exactly one sector is written in the same indivisible operation as the data it covers, so no tear can separate them.

The industry’s move to 4096-byte physical sectors — driven by the error-correcting code efficiency of longer sectors, since a 4 KiB sector amortises the ECC field over eight times the payload — broke that correspondence. A 512-byte logical block on a 4096-byte physical sector is emulated by the drive: reading one 512-byte block requires reading the whole 4 KiB physical sector and extracting the requested portion, and writing one 512-byte block requires reading the physical sector, merging the new 512 bytes, and writing all 4 KiB back. That is a read-modify-write inside the drive, invisible to the filesystem, with a cost that depends on the drive’s internal buffering.

The consequence for checksum design is that a checksum narrower than the physical sector no longer maps to an atomic unit. A filesystem that checksums 512 bytes and writes 512 bytes on a 4 KiB-sector drive gets, at best, a drive that performs the merge and the ECC update internally; at worst, a drive that reports success for a write that will be lost if power fails during the internal merge. Filesystems that want a guarantee they control therefore align both their block size and their checksum granularity to 4 KiB or larger, and the modern default for a data block in a checksumming filesystem is 4 KiB at minimum and often 16 or 128 KiB.

/* Number of checksum-covered units in a write, and whether the write
   forces a read of the surrounding unit. */
#include <stddef.h>
#include <stdint.h>

struct geometry {
    uint32_t unit;    /* bytes covered by one checksum */
    uint32_t block;   /* bytes the filesystem writes at a time */
};

/* Returns the bytes that must be read before a write of `len` at `off`. */
uint64_t rmw_read_bytes(struct geometry g, uint64_t off, uint64_t len)
{
    if (g.block >= g.unit && (off % g.unit) == 0 && (len % g.unit) == 0)
        return 0;                       /* aligned write: no read needed */
    uint64_t first = off - (off % g.unit);
    uint64_t last  = ((off + len + g.unit - 1) / g.unit) * g.unit;
    return last - first - len;          /* bytes of the units not overwritten */
}

The arithmetic is unremarkable; the point is that the return value is zero only when the write is aligned to the checksum unit and covers whole units. Every unaligned write pays the difference, and a workload of small random writes pays it on every operation.

What granularity does to damage reporting and repair

Precision matters most when there is redundancy to repair from. On a mirrored or erasure-coded layout, a mismatch localises the damage to one unit, and the repair reads the corresponding unit from the other copy and writes it back. With a 512-byte unit, the repair touches 512 bytes. With a 128 KiB unit, the repair touches 128 KiB, and if the other copy is also damaged somewhere inside that region the repair cannot complete — the two copies disagree and neither can be proven correct at the granularity of the unit.

The same logic applies to erasure coding. RAID-Z and similar schemes stripe data and parity across devices in units of the sector size, typically 4 KiB. A checksum granularity that matches the stripe unit lets the reconstruction logic identify which device contributed the bad data and reconstruct only that device’s contribution. A coarser checksum granularity forces reconstruction of the entire stripe, which is possible but reads more devices and increases the chance of hitting a second failure during the reconstruction window.

There is an argument for coarse granularity as well, and it is about checksum overhead on small metadata, the same trade that decides whether a checksum belongs in a pointer or in a side table. A 16 KiB node with a 4-byte checksum has negligible overhead; the same node split into 4 KiB pieces with a checksum each has four checksums and four addresses, which in a tree structure means four pointers instead of one and a taller tree. Filesystems that checksum metadata typically do so per node rather than per sector — btrfs verifies a whole tree block against the CRC32C in its header, and ZFS a whole indirect block against the checksum in its parent pointer — accepting coarser damage reporting in exchange for a smaller tree, because metadata damage is usually fatal for the affected subtree anyway. The repair arithmetic that follows from this choice is worked through in the self-healing read path, where a single bad block on a parity stripe costs a full-stripe read.

The interaction with compression and encryption

Two transforms break the assumption that checksum granularity equals storage granularity.

Compression changes the size of what is stored. If a checksum covers a logical region before compression, verification must decompress before comparing, and the amount of data that must be decompressed to verify one unit is the uncompressed size of that unit — which is what the filesystem records in the block pointer alongside the compressed size. If the checksum covers the compressed bytes, verification is cheaper but a bit flip in the compressed stream can expand into arbitrary output, so the decompressor’s own validation becomes the first line of defence and the checksum only confirms the input.

Encryption has a stronger requirement: the checksum must be computed over plaintext, because ciphertext depends on the initialization vector and the block’s location, and verifying ciphertext would only detect faults in the ciphertext itself, not in the decryption. This is why checksums in encrypting filesystems are recorded over the logical content and verified after decryption, and why a failed decryption (from a wrong key or a corrupted IV) surfaces as an error before the checksum is even consulted.

Both transforms mean that the effective granularity seen by the verification code is the logical block size, while the granularity seen by the device is the physical sector. A filesystem that stores 128 KiB logical blocks compressed to 9 KiB occupies three physical sectors and carries one checksum; a mismatch on read tells the filesystem that the 128 KiB logical region is bad, and the repair granularity is the whole 128 KiB even though only 9 KiB of medium is suspect.

Choosing in practice

The default that most checksumming filesystems adopt is a data block of 128 KiB with a checksum per block, and a metadata block of 4 to 16 KiB with a checksum per block. Small-file and database workloads often reduce the data block size to 4 or 8 KiB, trading tree depth and metadata volume for finer repair granularity and cheaper overwrites — a decision that is visible as a per-dataset block size setting in ZFS and as a nodesize setting in btrfs.

The penalty that cannot be designed away is the one at the boundary between the filesystem’s unit and the application’s write size. An application that writes 512-byte records into a filesystem with 4 KiB checksum units either batches them, in which case the checksum is computed once over the batch and no read is needed, or writes them individually, in which case each write is a read-modify-write of a 4 KiB unit. That cost is invisible to a workload that appends sequentially and dominant in one that updates records in place. Log-structured and copy-on-write designs avoid it by never updating a unit in place: they allocate a new unit, write it in full, and change the pointer. The cost of that strategy is deferred to deletion and reclamation, and the checksum arithmetic is the reason the strategy exists at all.