Checksum & Data Integrity

Metadata

1. Overview

What problem does it solve?

Data gets corrupted. When transmitting data across a network, electromagnetic interference can flip a 0 to a 1. When storing data on a hard drive, cosmic rays, degraded magnetic platters, or buggy firmware can cause "bit rot" — silent corruption of stored data over time.

A Checksum is a small-sized datum computed from an arbitrary block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage.

What breaks without it?

• Silent Corruption: An image file is downloaded, but half the pixels are scrambled.
• Database Destruction: A database reads a corrupted index block from disk, assumes the data is correct, and overwrites good data with garbage.
• Network Errors: TCP packets arrive with flipped bits, causing the application to parse invalid JSON and crash.

2. Motivation

In the 1970s, as networks grew, engineers realized that relying on physical cables to transfer bits perfectly was a pipe dream. TCP includes a 16-bit checksum in its header. If the calculated checksum of the received packet doesn't match the checksum stored in the header, the TCP stack silently drops the packet and waits for a retransmission.

However, TCP checksums are weak (they miss certain types of errors). Furthermore, data can be corrupted after it leaves the network (e.g., while being written to a hard drive). Therefore, modern distributed systems (like Kafka, HDFS, and Cassandra) implement their own application-level checksums.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Checksum Verification Flow

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef process fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef data fill:#cce5ff,stroke:#007bff,stroke-width:2px;
    classDef check fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef fail fill:#f8d7da,stroke:#dc3545,stroke-width:2px;

    subgraph Sender / Writer
        D1[Original Data<br/>'Hello']:::data --> Calc1((Calculate<br/>Checksum)):::process
        Calc1 --> C1[Checksum: 0x8B]:::check
    end

    D1 -. "Network / Disk" .-> D2
    C1 -. "Network / Disk" .-> C2

    subgraph Receiver / Reader
        D2[Received Data<br/>'HelXo']:::data --> Calc2((Calculate<br/>Checksum)):::process
        C2[Received Checksum<br/>0x8B]:::check --> Compare{Does 0xA2<br/>== 0x8B?}
        Calc2 --> C3[Calculated Checksum<br/>0xA2]:::check
        C3 --> Compare
        
        Compare -- YES --> OK[Data Valid]:::check
        Compare -- NO --> ERR[Corruption Detected!]:::fail
    end

6. Internal Working

Types of Checksums

1. Parity Bit (1 bit)

   • Simply counts the number of 1s in the data. If it's even, append a 0. If odd, append a 1.
   • Weakness: If two bits flip, the parity stays the same, and the error is missed.

2. Fletcher's Checksum / Adler-32

   • Computes two running sums of the data.
   • Pros: Very fast. Better than parity. Used in zlib.

3. CRC32 (Cyclic Redundancy Check)

   • Treats the data as a massive polynomial and divides it by a fixed polynomial key. The remainder is the checksum.
   • Pros: The industry standard for network and disk data. Extremely good at detecting burst errors (multiple contiguous flipped bits). Hardware accelerated on modern Intel/AMD CPUs (CRC32C).
   • Cons: Not cryptographically secure. An attacker can easily modify the data and forge a matching CRC.

4. MD5 / SHA-256 (Cryptographic Hashes)

   • Pros: Cryptographically secure. Impossible for an attacker to tamper with the data without changing the checksum.
   • Cons: Much slower to calculate than CRC32. Overkill if you only care about accidental corruption.

The Storage Pattern

In databases (like Cassandra or HBase), data is written to disk in "Chunks" (e.g., 64 KB). For every chunk, a 4-byte CRC32 checksum is calculated. The checksums are stored in a separate file (e.g., data.db and data.crc32). When reading data.db, the database reads the corresponding 4 bytes from data.crc32, calculates the checksum of the read data, and crashes/retries if they don't match.

7. Implementation

Why C? Checksums are fundamentally about bitwise operations, raw memory manipulation, and byte-level mathematical shifts. High-level languages hide this. C is the language in which operating systems, filesystems, and core database storage engines calculate CRC32.

/*
031 - Checksum & Data Integrity
A simple implementation of the CRC32 algorithm in C.
Demonstrates generating a checksum and verifying data integrity.
*/

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>

// Pre-computed CRC32 polynomial table for performance
uint32_t crc32_table[256];
bool table_computed = false;

// Initialize the CRC32 table (IEEE 802.3 polynomial: 0xEDB88320)
void make_crc32_table() {
    uint32_t polynomial = 0xEDB88320;
    for (uint32_t i = 0; i < 256; i++) {
        uint32_t c = i;
        for (int j = 0; j < 8; j++) {
            if (c & 1) {
                c = polynomial ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        crc32_table[i] = c;
    }
    table_computed = true;
}

// Calculate CRC32 for a block of raw bytes
uint32_t calculate_crc32(const uint8_t *data, size_t length) {
    if (!table_computed) {
        make_crc32_table();
    }

    uint32_t crc = 0xFFFFFFFF; // Initial value
    
    for (size_t i = 0; i < length; i++) {
        // XOR the current byte with the current CRC
        uint8_t index = (crc ^ data[i]) & 0xFF;
        // Shift CRC right and XOR with table value
        crc = (crc >> 8) ^ crc32_table[index];
    }
    
    return crc ^ 0xFFFFFFFF; // Final XOR
}

// ── Test Harness ──

int main() {
    printf("--- Data Integrity Simulator ---\n\n");

    // 1. Original Data
    const char *original_data = "Hello, Distributed Systems!";
    size_t length = strlen(original_data);
    
    printf("1. Writer wants to save data:\n");
    printf("   Data: '%s'\n", original_data);

    // 2. Calculate Checksum
    uint32_t expected_checksum = calculate_crc32((const uint8_t*)original_data, length);
    printf("   Calculated CRC32: 0x%08X\n\n", expected_checksum);

    // 3. Simulate transmission/storage (Perfect)
    printf("2. Reader reads data perfectly...\n");
    uint32_t actual_checksum = calculate_crc32((const uint8_t*)original_data, length);
    if (actual_checksum == expected_checksum) {
        printf("   ✅ SUCCESS: Checksums match (0x%08X). Data is intact.\n\n", actual_checksum);
    }

    // 4. Simulate Corruption (Bit Rot)
    char corrupted_data[100];
    strcpy(corrupted_data, original_data);
    
    // Flip a single bit (change 'H' to 'I')
    corrupted_data[0] = 'I'; 

    printf("3. Reader reads CORRUPTED data from disk:\n");
    printf("   Data: '%s'\n", corrupted_data);
    
    uint32_t corrupt_checksum = calculate_crc32((const uint8_t*)corrupted_data, length);
    
    if (corrupt_checksum != expected_checksum) {
        printf("   ❌ ERROR DETECTED!\n");
        printf("      Expected : 0x%08X\n", expected_checksum);
        printf("      Actual   : 0x%08X\n", corrupt_checksum);
        printf("      Action   : Drop data, fetch from replica.\n");
    }

    return 0;
}

Sample Output

--- Data Integrity Simulator ---

1. Writer wants to save data:
   Data: 'Hello, Distributed Systems!'
   Calculated CRC32: 0x487AB1CC

2. Reader reads data perfectly...
   ✅ SUCCESS: Checksums match (0x487AB1CC). Data is intact.

3. Reader reads CORRUPTED data from disk:
   Data: 'Iello, Distributed Systems!'
   ❌ ERROR DETECTED!
      Expected : 0x487AB1CC
      Actual   : 0x616CE40B
      Action   : Drop data, fetch from replica.

Notice how flipping a single bit (H -> I) drastically changed the entire CRC32 checksum, making the corruption instantly obvious.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. TCP already has a checksum. Why does Kafka calculate its own CRC32 for messages? Hint: TCP only protects data while it's on the wire. If a switch's internal memory is corrupted, or if the data rots on the hard drive after being saved, TCP can't help you.

2. When should you use MD5 vs CRC32? Hint: Use CRC32 for detecting accidental hardware/network corruption (fast). Use MD5/SHA256 for detecting malicious tampering or verifying file authenticity (secure).

3. In a distributed database, what happens when a node reads a corrupted block from its disk? Hint: The checksum fails. The node throws away the read, fetches a clean copy from a replica node, returns it to the client, and repairs its own disk asynchronously.

13. Used By (Downstream Blocks)

• 038 Write-Ahead Log (WAL) — Every entry appended to a WAL includes a checksum to ensure recovery doesn't halt due to a partially written or corrupted log entry.
• 039 SSTable & LSM Tree — The foundational storage structure for Cassandra and RocksDB relies heavily on block-level checksums.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Block-based Checksums

Modify the C code to simulate a file. Instead of one checksum for the whole string, divide the string into chunks of 8 characters. Calculate and store a CRC32 for each chunk. Corrupt one character, and write logic to identify exactly which chunk was corrupted.

Exercise 2: The Parity Bit

Implement a simple 1-bit parity generator in C that counts the number of 1 bits in a byte array. Then, write a test showing its critical flaw: flip exactly two bits in the array and show how the parity check still incorrectly passes.

Website Metadata