System Design Storage
Checksums and data integrity
Imagine uploading a vacation reel from your phone. Months later a friend downloads it through a CDN (content delivery network), a cache, and a replica in another region. Every hop can flip a bit. A is the short fingerprint that lets each hop ask: did these bytes stay the same?
At petabyte scale, (silent disk corruption) is expected, not rare. Without fingerprints at write, read, and repair time, wrong images, broken packages, or quiet database damage reach users. That is the problem this page solves: detect corruption early, repair from a healthy copy, and never promote a bad replica because it looked newer.
Integrity journey
Upload carries a digest with the bytes so the gateway can reject a mismatched transfer.
Commit metadata and data together so a digest never proves the wrong object version.
Verify on read
On mismatch, fetch another replica or fail closed instead of serving bad bytes.
Re-read idle data on a budget so rot is found before every copy is bad.
What actually happens when bytes hop
The vacation-reel story above is the default for any durable object store. Petabyte fleets copy objects across disks, networks, and regions. At that scale, silent bit flips are expected. The naive move is to trust the disk, or to checksum only at upload and never again. The counterexample is corruption after ingest: or a bad replica copy gets served forever as "valid" data because nothing rechecked the fingerprint.
On upload, the client (or gateway) computes a digest and stores it with the object version. On every later transfer (replica copy, restore, user download) the system recomputes and compares. A mismatch means quarantine, re-copy from a healthy source, and alert if the same disk keeps failing. That is : verify the bytes the user meant to store, not only the last hop that happened to work.
Fast codes like catch accidental flips cheaply on network frames and disk blocks. (for example SHA-256) matter for content addressing and adversarial resistance. A lets replicas compare huge datasets by walking only the branches that differ. Remember the boundary: checksums detect corruption. They do not authorize readers, encrypt sensitive data, or prove a malicious writer was allowed to upload the bytes.
How to choose a digest
Once you know corruption will show up, three questions decide which fingerprint to use and where to verify it.
1. Accidental errors or adversaries? Network frames and disk blocks often use . Content-addressed blobs and security-sensitive integrity need a .
2. Where do you verify? Client upload, storage write, replica transfer, read path, backup restore, and background each catch a different failure class.
3. Can metadata drift? Store checksum, version, chunk map, and encryption metadata together. A correct digest of the wrong version is still a user-visible bug.
Simple rule of thumb
Verify at every trust boundary you care about, keep digests versioned with the blob, and scrub on a budgeted schedule. Use CRC for speed on wires and blocks; use strong digests when identity or tamper resistance matters. In simple terms: fingerprint the bytes, store the fingerprint safely, and check it again before anyone trusts the data.
From problem to mechanism
Here is the silent-rot scenario slowed down so you can see where the naive approach fails and what the fix changes.
Problem. Petabyte fleets copy objects across disks, networks, and regions. At that scale, silent bit flips are expected, not exceptional.
Naive system. Trust the disk, or compute a only at upload and never again. There is no verify-before-repair, no versioned digest with metadata, and no background that finishes before correlated failures eat redundancy.
Break it. A flipped bit in replica R1 is copied to the other two during repair because versions were not compared. Or metadata and bytes drift so a digest proves the wrong object version correct.
Mechanism. Commit digest H(V) atomically with durable object version V's bytes and metadata. Any read, replica copy, or restore that returns bytes for V must recompute a matching digest, or fail closed / fetch another replica. Prefer over per-hop hope; use so repair only walks differing ranges (see Numbers to know below).
Correctness invariant
For every durable object version V, the stored digest H(V) is committed atomically with V's bytes and metadata. Any read, replica copy, or restore that returns bytes for V must recompute a matching digest, or fail closed / fetch another replica. Checksums detect corruption; they do not authorize writers or encrypt content.
Numbers to know, algorithms, and where to verify
The mechanism names what must hold; these figures and tables show how expensive it is, which algorithm fits which hop, and what to do when a check fails.
Numbers to know
Fleet-scale rot
~1 UBER / 10^14–10^15 bits
Large fleets experience media, software, and transfer faults, so verification and repair should be planned explicitly. A device’s uncorrectable bit-error-rate specification does not directly measure application-visible silent corruption; it concerns a particular error model and workload. Use fleet observations, device health, and verified restore results to choose scrub cadence rather than turning a quoted device rate into an exact count of corrupted user objects.
SHA-256 on hot path
50 KB ≈ ~33μs @ 1.5 GB/s
Digest CPU is rarely the bottleneck vs disk/network. Prefer strong digests for object identity; CRC for wire/block speed.
Merkle compare
10^9 leaves → ~30 tree levels
For a balanced binary tree with a billion leaves, one root-to-leaf path has about thirty levels. That is a tree-depth estimate, not an unavoidable thirty network round trips or the total cost of repairing arbitrary differences. Batch hash comparisons where possible; if many leaves differ, comparison and transfer work can approach a full scan. Rate-limit repair traffic so discovering corruption does not exhaust the disks serving healthy reads.
- Watch checksum mismatch rate by host and disk so a bad path shows up early.
- Track scrub coverage percent and repair backlog age before redundancy is gone.
- Fail restore rehearsals that mismatch manifests; keep the older generation instead.
Algorithm comparison
| Algorithm | Size | Speed | Collision resistance | Use case |
|---|---|---|---|---|
| CRC32 | 32-bit | ~20 GB/s | Weak (detects errors) | Network, disk blocks |
| Adler-32 | 32-bit | ~15 GB/s | Weaker than CRC32 | zlib compression |
| xxHash | 64-bit | ~30 GB/s | Good (non-crypto) | Hash tables, dedup |
| MD5 | 128-bit | ~5 GB/s | Broken (collisions) | Legacy ETags / dedup |
| SHA-1 | 160-bit | ~3 GB/s | Broken (SHAttered) | Git (migrating away) |
| Strong digest (SHA-256) | 256-bit | ~1.5 GB/s | Strong | CAS, object storage |
| BLAKE3 | 256-bit | ~10 GB/s | Strong | Modern alternative |
| Fast cyclic checksum | 32-bit | ~50 GB/s | Weak (error detection) | iSCSI, GFS, Btrfs |
A at ~1.5 GB/s still checksums a 50 KB object in ~33μs: fast enough for most object paths (see Numbers to know above). A 32-bit checksum has ~4.3B values, so accidental collisions become visible at huge scale; a 256-bit digest is sized for adversarial resistance, not only random flips.
Integrity pipeline and repair
Follow one object version through upload: compute a digest, transfer the bytes, verify the digest at ingest, and publish metadata only after the matching version is durable. Later, a read or replica transfer recomputes the digest for that version. If encryption or compression occurs between boundaries, keep the relevant plaintext and stored-byte integrity metadata distinct so each verification compares the representation it actually reads.
On mismatch, isolate the suspect copy and look for another copy that matches the trusted version metadata. Do not choose a repair source just because two replicas agree or one has a later timestamp: shared corruption or incorrect versioning can affect several replicas. If no verified source is reachable, return an integrity error and escalate recovery rather than spreading unverified bytes.
Client upload
Gateway ingest
Storage write
Replica transfer
Read path
Backup/restore
Background scrub
| Placement | What to verify | Failure response |
|---|---|---|
| Client upload | Client checksum matches bytes at gateway | Reject and ask client to retry |
| Storage write | Object version and checksum commit atomically | Do not expose until metadata and data agree |
| Replica transfer | Source chunk digest equals destination | Re-copy from healthy replica; mark bad source |
| Read path | Returned bytes match checksum for version | Fetch another replica or return integrity error |
| Backup / restore | Manifest checksums match restored chunks | Fail restore rehearsal; keep older generation |
- Store per-chunk digests with object version so checksum metadata versions with the blob.
- Verify on write and on read; lazy restore checks are too late after every replica copied rot.
- Give background scrubbing its own I/O budget so it does not steal from user traffic.
Runbook when a mismatch appears: quarantine corrupt chunks, repair from a healthy replica, re-check the path, and alert if the same disk, host, or network path repeats corruption. Never let a bad copy overwrite a good one because it looked newer.
Merkle trees for repair at scale
A Merkle tree caches hashes over groups of chunks, so two replicas first compare roots and descend only into differing subtrees. Matching roots provide strong evidence of equal content under the hash assumptions and identical tree construction. A single differing chunk can be localized through logarithmic depth; many differences require proportionally more traversal and data transfer. The tree locates disagreement, while the versioned trusted digest determines which copy is eligible as a repair source.
Merkle tree structure
Merkle Tree: binary tree of hashes
Root = H(H12 + H34)
/ \
H12 = H(H1+H2) H34 = H(H3+H4)
/ \ / \
H1=H(A) H2=H(B) H3=H(C) H4=H(D)
| | | |
Block A Block B Block C Block DWhere teams use them
- Wide-column store repair uses Merkle trees per token range for anti-entropy.
- Managed key-value stores compare replica trees so only drifted ranges sync.
- Git commits, Bitcoin transaction roots, and IPFS Merkle DAGs all share this shape.
- Certificate Transparency keeps append-only logs verifiable with Merkle inclusion proofs.
Where checksums show up in production
With the repair math in hand, here is how real storage stacks and HTTP caches use the same ideas, plus the line between detecting damage and fixing it in place.
Filesystem and storage examples
Some checksumming filesystems store data and metadata checksums separately from the protected block and can repair a bad read from an available redundant copy. The exact coverage and behavior depend on the filesystem and configuration. A scheduled scrub reads allocated data to discover damage before ordinary access does. Choose its interval and I/O budget from capacity and redundancy rather than assuming every filesystem completes a weekly full pass.
Object storage
- Upload compares the client digest at ingest and rejects a mismatched transfer.
- Storage keeps a checksum with object metadata and verifies it before download.
- Periodic background scrubbing walks all objects so rot is found before users notice.
- Modern APIs also accept strong digests and fast cyclic checksums at the edge.
Distributed file storage
- Fast cyclic checksums sit per chunk with meta files stored beside the data.
- Reads verify digests and report corrupt blocks so the system can re-replicate.
- Background scanners walk blocks on a multi-week cycle under an I/O budget.
Wide-column store
- per SSTable catches accidental flips on compaction and reads.
- Anti-entropy repair compares replicas with a instead of full scans.
Error detection
Checksums detect that corruption happened. Fixing usually means fetching another copy. CRC for packets and blocks; for content addressing; durable logs often CRC each batch.
ECC RAM, LDPC on SSDs, and Reed-Solomon erasure coding repair some damage without a full second copy. At scale: ECC → device correction → transport → erasure coding → application checksums.
Content addressing uses a digest of the exact stored representation as an identifier. Equal bytes produce the same identifier, allowing deduplication and integrity checks after retrieval. Compression, encryption, or normalization changes those bytes, so record which representation the digest covers. A bare hash does not authenticate the publisher if an attacker can replace both the object and its expected digest; a trusted manifest, signature, or authenticated metadata path supplies that missing trust.
GET /api/users/123
→ 200 OK
→ ETag: "a1b2c3d4e5f6"
GET /api/users/123
→ If-None-Match: "a1b2c3d4e5f6"
→ 304 Not Modified (no body!)At CDN scale, billions of conditional requests save terabytes of bandwidth with 304 responses.
Failure timeline, and what still breaks after the fix
Putting the pieces together, here is how silent rot plus a careless repair plays out, followed by the ways an improved design can still go wrong.
Timeline: silent rot then bad repair
T0 Object written to 3 replicas; digest stored with version metadata T1 Months later, disk on replica R1 flips a bit (bit rot) T2 No scrub yet: read path still hits healthy R2/R3 most of the time T3 R2 fails; repair job copies from R1 without verifying digest T4 Now 2 of 3 replicas are corrupt; next scrub finds majority-wrong data T5 Without end-to-end digests + quarantine, repair can amplify rot
Verify before promoting a repair source. Quarantine mismatches; never let a bad copy overwrite a good one because it looked newer.
Still fails when…
- Digest runs before compression or encryption but verifies a different byte representation later.
- Checksum sits in the same sector as data, so one media failure kills proof and payload.
- Aggressive scrub without an I/O budget melts disks under background verification load.
- Weak CRC alone is treated as adversarial integrity, or checksums are mistaken for encryption.
Trade-offs
- CRC is fast for accidental errors; a strong digest costs more CPU but resists collisions.
- End-to-end checks catch more bugs than per-hop checks but need application support.
- Frequent scrubbing improves safety but consumes I/O that could serve user reads.
Choosing and explaining checksums
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
Checksums detect accidental corruption across transfer, storage, replication, and backup restore.
Use fast CRC-style checks for integrity and cryptographic hashes when tamper resistance matters.
Verify at boundaries: upload, write, read, replication, compaction, and restore.
When it belongs
The system stores or moves large files, logs, backups, or replicated data.
Silent corruption would be expensive or unsafe.
You need deduplication or content-addressed storage.
How it fails
Checksum is computed before compression/encryption but verified after a different byte representation.
Metadata and checksum are corrupted together.
Repair copies bad data over good data because versions are not compared.
Trade-offs to weigh
CRC is fast for accidental errors; strong digest costs more but resists collisions.
End-to-end checks catch more bugs than per-hop checks but need application support.
Frequent scrubbing improves safety but consumes IO.
Common misunderstandings
Calling a checksum encryption.
Using weak hashes for security-sensitive integrity.
Forgetting checks during restore and migration.
Try it: detect corruption with a checksum
Compare a payload against a checksum captured at rest. Corrupt the bytes on the wire, then verify to see why storage and replication reject bad blocks.
Payload block
order:8842|qty:3
- Stored checksum
- 1395
- Live checksum
- 1395
- Last verify
- —
Verify integrity before trusting a block. Flip a bit in transit and the checksum should no longer match.
Going deeper
Production deep dive: integrity from producer to restore
A checksum detects accidental corruption of a specific byte representation. It does not prove who created the bytes, and a checksum stored beside data can be corrupted by the same faulty component.
What must stay true
Every durable object is verified against integrity metadata created outside the failure boundary being checked before it is served, replicated, repaired, or restored.
How the pieces fit
Client digest
original bytes
Transport verify
reject mismatch
Stored chunk CRC
per block / replica
Background scrub
read + compare
Version-safe repair
healthy source quorum
Stored data
4 PB
Across active objects and replicas.
Scrub budget
2 GB/s
Dedicated aggregate off-peak read bandwidth.
Full pass
≈ 23 days
4 PB ÷ 2 GB/s; too slow for a seven-day target.
Checksum versus MAC versus signature
CRC/cryptographic digest detects accidental change but is unkeyed. A MAC proves integrity to parties sharing a secret. A digital signature proves integrity and signer authenticity with asymmetric keys. Use a modern cryptographic hash where malicious collision resistance matters.
End-to-end ownership
The producer computes or supplies a digest, transport verifies it, storage records per-chunk checks independently, reads verify before returning bytes, and restore verifies again. Each layer emits mismatch location and object version so responsibility is diagnosable.
Scrub scheduling
Choose pass interval from durability target, data bytes, and safe background bandwidth. Prioritize old, rarely read, single-redundancy, and recently migrated data. Throttle against user latency and checkpoint progress, but never allow the oldest-unscrubbed age to grow silently.
Repair safety
Freeze the corrupt replica, compare immutable version/generation and independent checks from multiple sources, copy from a known-good version to a new location, verify, then atomically replace. Never let a blind last-writer repair overwrite the sole good copy.
ETags and deprecation
An HTTP ETag is an opaque cache validator, not universally a content digest; multipart uploads and transformations can change its meaning. Version stored algorithms, dual-write old+new digests, backfill and verify, switch readers, then retire weak algorithms such as MD5 where collision resistance is required.
Worked example: Scrub-capacity calculation
- 1A seven-day pass over 4 PB requires 4 PB ÷ 604,800 seconds ≈ 6.6 GB/s of sustained reads.
- 2At 70% utilization ceiling, provision roughly 9.5 GB/s so user bursts and repair do not starve the scrubber.
- 3Track oldest-unscrubbed age by tier; a 4 PB average can hide a cold tier that has not been verified for months.
The scrub interval is a capacity promise. “We scrub weekly” is incomplete without bytes, bandwidth, throttling, and proof that the pass finishes.
Integrity failure matrix
| Scenario | Consequence | How to contain it |
|---|---|---|
| Data and checksum corrupted together | Local comparison falsely passes. | Keep independent end-to-end digest or authenticated metadata outside that fault boundary. |
| Repair source is stale | Good current bytes are replaced by old bytes. | Compare immutable generation/version and validate source quorum before copy. |
| ETag assumed to be MD5 | Multipart object validation is wrong. | Treat ETag as opaque; use explicit checksum metadata/API. |
What to watch in production
- Graph checksum mismatches by layer/device, oldest-unscrubbed age, scrub bandwidth, repair outcomes, and unverified restore bytes.
- Quarantine instead of auto-repair when replicas disagree on version or no independent good copy exists.
- Inventory algorithms and formats so cryptographic deprecation can dual-write and backfill without a flag day.
A scenario to reason through
One replica has checksum X, two have checksum Y, but the X replica has a newer generation. Which bytes do you copy?
One solid approach
None automatically. Version and checksum disagree, so quarantine and consult authoritative metadata or the write log. Majority checksum alone can copy stale data over a newer valid version.
Going deeper
Checksum
The mechanism and its boundary
Checksums detect accidental corruption by comparing a computed digest with stored or transmitted metadata. They are integrity checks, not authorization or trust by themselves.
Integrity verification path
Chunk data
Compute digest
Store metadata
Verify on read
Work through the sizing assumptions
When it belongs
Data crosses networks, disks, queues, or replication paths. Silent corruption is worse than explicit failure. Large files are split into chunks and need partial verification.
Assumptions that matter
Background scrubbing has its own I/O budget. Large objects need chunk-level repair. Verification cost must fit read and write latency budgets.
Easy mistakes
An unkeyed checksum cannot prove who created data, because an attacker who replaces the data can often replace its checksum too; authenticated integrity needs a trusted signature or MAC. Checking only during upload misses damage introduced by later storage, replication, backup, or restore operations. A whole-object digest can detect a mismatch without identifying its damaged region, so large repairable objects benefit from trusted per-chunk digests as well.
How it fails
Corruption is copied to replicas before detection. Checksum metadata is lost or mismatched with the object version. Weak checksums miss adversarial or repeated collision cases.
Trade-offs to name
A stronger digest can reduce accidental collision risk or provide resistance to deliberate collision attacks, but its CPU cost depends on the algorithm and hardware, so choose and benchmark it for the threat model. Per-chunk digests identify which part of a large object needs repair, while requiring additional metadata that must remain associated with the correct object version. Verification on reads detects damage before serving data but adds work to that path, while background scrubbing can find cold-data corruption earlier at the cost of a separate I/O budget.
Wrap-up
You have seen the failure, the mechanism, and the operational signals. Use these exercises to check the ideas stuck, then follow the references for the primary sources.
Exercises
- Place digests on an object path. Upload → encrypt → store → replicate → CDN → download. Where do you compute and verify? What fails if you only check at the CDN edge?
- Scrub schedule math. 40 PB fleet, 2 GB/s aggregate scrub budget. How many days for a full pass? If UBER risk requires a 30-day cycle, what must change?
- Bad-repair tabletop. Two of three replicas mismatch the stored digest; the third is unreachable. Write the runbook step order so you do not promote corrupt bytes.
Topic-specific references
- Ghemawat, Gobioff, Leung: The Google File System (SOSP 2003) : checksums, replica repair, and silent corruption awareness.
- Bairavasundaram et al.: An Analysis of Latent Sector Errors (FAST 2008) : why scrubbing and redundancy must assume latent media faults.
- RFC 3385: Internet checksum considerations : strengths and limits of classic checksums versus stronger digests.
Key takeaway
Silent corruption is expected at disk-fleet scale. Fingerprint bytes at every boundary, keep digests versioned, scrub on a schedule, and use Merkle trees to repair only what drifted. Detection plus redundancy, not hope, is what makes object stores durable.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Use layered checksums, hashes, MACs, and signatures with end-to-end ownership, scrubbing, repair safety, ETag caveats, and algorithm migration.
Explain the decision
How does a checksum differ from a MAC?
Read the reasoning
A checksum detects accidental corruption; a keyed MAC also authenticates integrity against an attacker who lacks the key.
Apply it to a production scenario
One replica fails checksum during a scrub. How do you repair safely?
Read one approach
Compare independent replicas/version metadata, quarantine the bad copy, reconstruct from a verified source, then re-check and audit.
Work through the numbers
Scrubbing 5 PB every 30 days requires what average read throughput?
Read the worked calculation
About 1.93 GB/s decimal, continuously, before retries and repair traffic.
Reason through a failure
What must repair never do?
Read the recovery reasoning
It must not copy a corrupted or stale replica over the last good version; authority/version and integrity are verified independently.
Sources and further study
Continue with Connection Pooling.