Architecture - Repositories - part 8

We're zooming through most of the architecture pretty fast right now.

CAS - Content Addressable Storage

Software using CAS technology is everywhere. git uses it. It's widely used for caches - Bazel uses it. There are some other distributions that also use it to various degrees.

The idea is simple: Instead of having a data storage model where the "key" to access the data is based on something obvious like the "name" or variations thereof (think N-V-R), what if the store is addressable by something that uniquely relates to the content - e.g. a checksum.

This means that if you know the checksum, you can access the data directly without iterating over the content index to see if the data is present in the store - the lookup is O(1).

Auto-deduplicating

The cool thing is that if you have to store the same thing into the store, you would just store the same data at the same "address", and, because it's already there, you can omit the second copy. So the cost of duplicates is very low - a single address lookup.

Another cool thing about a CAS is that if a client knows the "key" and obtains a new "key" that is identical, that client also knows that they do not have to re-download the data at the address of that key again. This is the part that saves us download time on updates.

When a package change gets pushed into the build system, most of the time things like the binaries change. But the data stays likely the same for many of the updates. The licenses stay the same. The manual pages stay the same. Most of the time. If you do updates of your packages and the package manager finds out that the content bytes of a subpackage didn't change, there is no download for data for that subpackage. The package manager just needs the new metadata file. And that's just a few ascii bytes.

Here's how the data CAS looks in a repository:

$ tree data|head -n 12
data
├── 00
│   ├── 04
│   │   └── 000450637e660459ae312f74529001def5fc7126987013fffc2c9ddc0d6b3e48
│   ├── 07
│   │   ├── 0007238250ffd91775616988511b7aad5dcececd35130c48340745491520c0d9
│   │   └── 0007537f80dcf22b9b234ac391259ca1535da491efdf24bfa23e52bc68829c00
│   ├── 08
│   │   └── 000852cdde45e214f01a91f5e3e0d467c09c94d97a74df63fe59d98e1012741d
│   ├── 0a
│   │   ├── 000a3b34615add792d6a4a82d7fa886b4848b182e70e37b336d1fc27200bdb4f
│   │   └── 000a62017d238b5900d5d01f0ce0072f01d12ed6530a3ec4d7525153345b7c7b

Boring, right? It's too long to paste here entirely.

There's more than one CAS here.

There's more than just a data CAS in the repo. There's quite a few. And we'll show you why these are here and where they come from.

Inside the pkgs substructure you'll find all the metadata of every package in the repository. The metadata is logically structured to enforce the uniqueness of the N-V-R and at the same time not have thousands of inodes in a single directory - because that is terrible for performance.

So the pkgs structure consists of pkg-meta files that are in a directory with the name: {name}/{subpackage}/{version}/{release}/{arch}. Here's how that looks on disk:

$ tree pkgs/|head -n 20
pkgs/
├── acl
│   ├── bin
│   │   ├── 2.3.2
│   │   │   ├── 2
│   │   │   │   └── x86_64
│   │   │   │       └── pkg-meta
│   │   │   ├── 3
│   │   │   │   └── x86_64
│   │   │   │       └── pkg-meta
│   │   │   ├── 4
│   │   │   │   └── x86_64
│   │   │   │       └── pkg-meta
│   │   │   ├── 5
│   │   │   │   └── x86_64
│   │   │   │       └── pkg-meta
│   │   │   ├── 6
│   │   │   │   └── x86_64
│   │   │   │       └── pkg-meta
│   │   │   └── 7

Now, if you cross-reference this with the post about packages I did just before this one, you'll know that there's a few sha256 entries in each package, and each of them corresponds to another CAS; Here's what they are:

• license-refs stores a CAS to map all SPDX licenses used by the packages
• provenance stores a CAS to map all the build provenance for each package
• recipes stores a CAS to all the recipes used by each package (including patches, etc.)
• sources stores the upstream source tarballs used during package build

Why all these things?

Because with all these things here, you can verify yourself that what I built is what you'd get if you take the sources, and the build root components from the provenance records, and the build specific configs, and build it again. It should all match bit for bit.

The sources and recipes are needed to replicate the inputs of what The Ur Project used to build each package. And the provenance shows you exactly what sources and what supporting build software was present in the build root during that build, as well as what options and which version of the autobuilder was used.

Without that information, reproducible builds are not possible. But with these records and data structures in the CAS part of each repository, every user can follow the breadcrumbs back to how every part every package in the distro came together.

The license refs are the last part of our provenance/SBOM deliverable. They serve as a final record of what the license(s) of the packages in the repository are. This will serve SBOM tooling later at some point when it becomes more relevant, but the infrastructure will have to lean on this.

--sofar (aka Auke)