File Formats and Implementation Details

Concepts

Every backup starts by cutting files into content-defined chunks, roughly 1MB¹ in size, using the FastCDC algorithm. Chunks are then ID'd by their SHA-224 hash.

Next, we need to organize lists of chunks back into their respective files, and files back into their directories. Let's represent each directory as a tree, where each node is a file made of chunks:

"PXL_20240804_202813830.jpg": {
    "chunks": [
      "oo98aq2o7ma75pmgmu6qc40jm8ds5blod7ne3ooendmqe",
      "73rqnbmg905r3sv77eqcpvgjodbsv6m8mon6kdobj8vfq"
    ],
    "metadata": {
      "type": "posix",
      "mode": 33188,
      "size": 1097373,
      "uid": 1000,
      "gid": 100,
      "atime": "2024-08-17T19:38:42.334637269Z",
      "mtime": "2024-08-06T01:40:45.36797951Z"
    }
  }

A node can also be a subdirectory, whose ID is the SHA-224 of its serialized tree.

"Camera": {
  "tree": "cti2sslfl8i9j3kvvfqkv2bust1pd1oiks0n2nhkg6ecu",
  "metadata": {
    "type": "posix",
    "mode": 16877,
    "uid": 1000,
    "gid": 100,
    "atime": "2024-08-17T08:13:52.026693074Z",
    "mtime": "2024-08-16T07:35:05.949493629Z"
  }

Note that we save basic metadata (owners, permissions, etc.) but omit things we can't easily restore, or which depend on particular filesystems (inode numbers, change times, extended attributes, etc.). Backpak focuses on saving your files in a space-efficient format, not trying to make an exact image of a POSIX filesystem a la tar or rsync. Special files like dev nodes and sockets are skipped for this same reason.

Files

Packs

Saving each chunk and tree as a separate file would make the backup larger than its source material. Instead, let's group them into larger files, which we'll call packs. We aim for 100 MB per pack, though compression shenanigans can cause it to overshoot.¹

Each pack contains:

1. The magic bytes MKBAKPAK
2. The file version number (currently 1)
3. A Zstandard-compressed stream of either chunks or trees (which we'll collectively call blobs)
4. A manifest of what's in the pack, as (blob type, length, ID) tuples.
5. The manifest length, in bytes, as a 32-bit big-endian integer. This lets a reader quickly seek to the manifest.

Since a pack's manifest uniquely identifies all the blobs inside (and, for what it's worth, the order in which they're stored), the SHA-224 of the manifest is the pack's ID.

Indexes

Reading each pack every time to rediscover its contents would be a huge slowdown, and for cloud-stored repositories, a huge bandwidth suck. As we make a backup, let's build an index of all the packs we've built. Each index contains:

1. The magic bytes MKBAKIDX
2. The file version number (currently 1)
3. A Zstandard-compressed map of each pack's ID to its manifest

We can also use the index for resumable backups! As we finish each pack, we write a work-in-progress index to disk. If the backup is interrupted and restarted, we read the WIP index and resume from wherever the last pack left off.

Snapshots

After packing all our blobs and writing the index, the last step of a backup is to upload a snapshot. Each contains:

1. The magic bytes MKBAKSNP
2. The file version number (currently 1)
3. A CBOR file containing snapshot metadata (author, tags, and time), the absolute paths that the snapshot backed up, and the root tree of the backup.

We don't bother with compressing snapshots since they're so small.