Binary Encoding and Checksums¶

Why not just write structs to disk¶

type Header struct {
    Magic uint32
    Seq   uint64
    Len   uint16
}

// Tempting, and wrong for a file format:
b := unsafe.Slice((*byte)(unsafe.Pointer(&h)), unsafe.Sizeof(h))
f.Write(b)

Writing a struct's raw memory produces a file that depends on the compiler and CPU that wrote it:

Padding: the compiler inserts invisible bytes so Seq is 8-byte aligned. unsafe.Sizeof(Header{}) is 24, not 14 (measured), and the padding contains whatever was in memory (Memory Layout of Go Values).
Endianness: x86 and ARM store 0x12345678 as bytes 78 56 34 12 (little-endian); some other architectures store 12 34 56 78. A file is only portable if its byte order is fixed.
Type sizes and layout rules belong to one compiler and one architecture (int is 4 bytes on 32-bit platforms, 8 on 64-bit).

So every on-disk format defines its encoding explicitly, byte by byte, and code encodes and decodes field by field. encoding/gob and encoding/json are self-describing but slow and verbose; storage formats and wire protocols use explicit binary layouts.

Fixed-width little-endian integers¶

Go's encoding/binary does exactly this, without unsafe:

var buf [14]byte
binary.LittleEndian.PutUint32(buf[0:], h.Magic)
binary.LittleEndian.PutUint64(buf[4:], h.Seq)
binary.LittleEndian.PutUint16(buf[12:], h.Len)

// Append-style, growing a reusable buffer:
b = binary.LittleEndian.AppendUint64(b, seq)

// Decoding, with one bounds check up front:
if len(p) < 14 {
    return ErrCorrupt
}
magic := binary.LittleEndian.Uint32(p[0:])
seq := binary.LittleEndian.Uint64(p[4:])

Little-endian is the conventional choice for storage formats (LevelDB, RocksDB, Protocol Buffers' fixed-width fields) because almost every machine running a database today is little-endian: on those machines PutUint32 and Uint32 compile to a single store or load. Network protocols traditionally use big-endian ("network byte order"), as in Designing a Binary Protocol. Either works if it is written down.

Varints: small numbers in few bytes¶

Most lengths in a key-value store are small — a 20-byte key, a 100-byte value — yet a uint32 length always costs 4 bytes. A varint (variable-length integer, the encoding used by Protocol Buffers, LevelDB, and Go's encoding/binary) stores 7 bits per byte and uses the high bit as a "more bytes follow" flag.

Value	Binary	Varint bytes (measured with `binary.AppendUvarint`)
1	`0000001`	`01`
127	`1111111`	`7F`
128	`1 0000000`	`80 01`
300	`10 0101100`	`AC 02`

Worked example, 300: the low 7 bits are 0101100 (0x2C); more bits remain, so emit 0x2C | 0x80 = 0xAC. The remaining bits are 10 (2); nothing remains after them, so emit 0x02. Decoding reverses it: (0xAC & 0x7F) | (0x02 << 7) = 44 + 256 = 300.

The encoder is a short loop:

func appendUvarint(dst []byte, v uint64) []byte {
    for v >= 0x80 {
        dst = append(dst, byte(v)|0x80)
        v >>= 7
    }
    return append(dst, byte(v))
}

In practice, use binary.AppendUvarint / binary.Uvarint. The decoder's return value encodes the failure modes, and every caller must check it:

v, n := binary.Uvarint(p)
switch {
case n > 0:
    p = p[n:] // ok: consumed n bytes
case n == 0:
    return ErrCorrupt // input ended in the middle of the varint
default:
    return ErrCorrupt // n < 0: value overflows 64 bits (-n bytes were read)
}

Measured: binary.Uvarint([]byte{0xAC}) (a truncated 300) returns n = 0; eleven 0xFF-style continuation bytes return n = -11. Every decoder must be bounds-checked, because the bytes may come from a torn or corrupted file. A decoder that trusts a length read from disk is a crash — or a giant allocation — waiting for the first bad block.

Length-prefixed byte strings¶

Keys and values are arbitrary bytes, so they cannot be terminated by a special byte. They are stored as varint length + raw bytes:

func appendBytes(dst, b []byte) []byte {
    dst = binary.AppendUvarint(dst, uint64(len(b)))
    return append(dst, b...)
}

// readBytes returns the next length-prefixed string and the rest of the input.
func readBytes(p []byte) (b, rest []byte, ok bool) {
    n, w := binary.Uvarint(p)
    if w <= 0 || uint64(len(p)-w) < n { // varint invalid, or length beyond the buffer
        return nil, nil, false
    }
    p = p[w:]
    return p[:n:n], p[n:], true // full slice expression: callers can't append into p
}

b is a view into the input buffer — no copy. This is how a WAL record, a write batch, or an SSTable block entry is parsed in the storage engine. The length check compares the length with the bytes remaining; never compute offset + length and compare that, because with untrusted values the addition can overflow and pass the check — the storage engine's fuzzer found exactly that bug in a block decoder.

Checksums: detecting corruption¶

Data on disk gets corrupted: torn writes after power loss, firmware bugs, bit flips in RAM or on the bus, a bug in your own code that writes the wrong bytes. A storage engine must detect corruption rather than return wrong data. Every unit of data written — each WAL record, each SSTable block — carries a checksum of its contents, verified on read.

CRC32-C¶

The standard choice is CRC32-C (Castagnoli polynomial). A CRC is not a cryptographic hash; it is designed to detect accidental errors, and it catches every single-bit error, every burst error up to 32 bits long, and all but about 1 in 4 billion random corruptions. Modern x86 (SSE4.2) and ARMv8 have instructions for it, and Go's hash/crc32 uses them automatically:

var castagnoli = crc32.MakeTable(crc32.Castagnoli)

sum := crc32.Checksum(block, castagnoli)
// Incremental: cover a type byte and then the payload without concatenating.
sum = crc32.Update(crc32.Update(0, castagnoli, []byte{typ}), castagnoli, payload)

Measured on an Apple M1 Pro: 6.4 GB/s over a 64 MiB buffer, and 463 ns for a 4 KB block — far below the cost of reading the block from an SSD, so checksumming every block is affordable. Check any implementation against the standard test vector: the CRC32-C of the ASCII string "123456789" is 0xE3069283 (verified with hash/crc32). Note that crc32.ChecksumIEEE uses a different polynomial; mixing the two between writer and reader makes every block look corrupt.

Masking stored CRCs¶

LevelDB stores a masked CRC rather than the raw one:

const maskDelta = 0xa282ead8

func mask(crc uint32) uint32   { return (crc>>15 | crc<<17) + maskDelta } // rotate right 15, add constant
func unmask(m uint32) uint32   { r := m - maskDelta; return r>>17 | r<<15 }

The reason is subtle: computing the CRC of a byte string that itself contains embedded CRCs (a block that stores checksums of its own contents) interacts badly with CRC's linearity. Masking breaks that relationship. Copy this idea if you follow LevelDB's format.

What to cover with the checksum¶

The checksum must cover everything needed to interpret the data, including the type and length fields, not just the payload. If the length is outside the checksum, a corrupted length makes the reader compute the checksum over the wrong range and may report a false "corruption" — or worse, read a valid-looking region of a different record. The storage engine's WAL checksums the fragment type and data, and the block trailer covers the block and its compression type.

Other hash functions you will see¶

Function	Use
CRC32-C (`hash/crc32`)	Integrity of blocks and records on disk
xxHash / XXH3 (`github.com/cespare/xxhash`)	Fast non-cryptographic hashing; RocksDB's newer default block checksum
FNV (`hash/fnv`), `hash/maphash`	Hashing keys for Bloom filters and hash tables (`maphash` is seeded per process — never persist its values)
SHA-256 (`crypto/sha256`)	Content addressing, security — far too slow for per-block checks

Format versioning¶

Every file your engine writes should begin or end with a magic number (identifies the file type, catches "opened the wrong file") and include a format version. LevelDB's SSTable footer — and the Go engine's — ends with the 8-byte magic 0xdb4775248b80fb57. When you later change the format, the version lets new code still read old files: files written by a database live much longer than the code that wrote them.

Common pitfall¶

Checking the checksum only "when debugging" or making verification optional by default. Corruption that is not detected at read time is silently returned to the user as data, copied into new files by compaction, and replicated — by the time someone notices, every copy is corrupted and the original bytes are gone. Verify checksums on every read of a block from disk (a block cache hit can skip it, since the block was verified when loaded), and treat a mismatch as an error that stops the operation.

Review questions¶

Why is unsafe.Sizeof of Header 24 rather than 14, and why does that make raw struct writes unsuitable for a file format?
Encode 300 as a varint by hand. What does binary.Uvarint return for a truncated input, and for an overflowing one?
Why must a length check compare against the remaining bytes instead of computing offset + length?
Why must the checksum cover the length and type fields, not only the payload?
What happens if the writer uses crc32.ChecksumIEEE and the reader uses the Castagnoli table?