Have you ever wondered how DNF (or any RPM-based package manager) knows what packages are in a software repository, or what dependencies each package requires? In each repository, the repodata/ directory (located at the basedir of the repository) contains some XML files with metadata for the repository and its packages. These XML files are usually generated by createrepo_c (GitHub). Package managers download and parse these metadata to know what packages there are, file paths in each package, etc.

createrepo_c is named the way it is because createrepo (written in Python here) was a thing. While I never really dug into how the latter works… well, let's just say I see why they abandoned the project and rewrote it in C.

Introducing Subatomic v1

Subatomic is our solution for handling RPM package repositories. It is responsible for receiving package uploads from subatomic-cli, signing packages, and generating metadata. The current stable version v0.15.0 is written in Go, currently deployed in Terra. v0 of Subatomic does not handle metadata generation directly. Instead, it simply shells out to createrepo_c. Since we're hosting Subatomic on a server that isn't as powerful as most people think, we encounter bottlenecks when uploading packages to Subatomic. Every builder in our CI during mass rebuild has to wait for each other between uploads, and every time an upload finishes, createrepo_c takes a few minutes just to generate the metadata.

I said screw this, and initiated the "RIIR": I rewrote Subatomic from Go to Rust, and wrote the logic for metadata generation from the ground up.

During development and benchmarking, the createrepo logic was exposed via satm createrepo, but this has since then been extracted to a separate binary kiritan to make it easier for everyone to try it out.

Performance Analysis

kiritan comes with 2 modes: auto, where the program scans for changes in the repository automatically, and manual, where the invoker specifies the changes manually. In auto mode, the invoker can also specify --no-cache, which disables caching. In both auto, auto --no-cache, and manual, kiritan runs faster than createrepo_c. With caching enabled, the improvement is extremely significant.

The (not-so-formal) benchmarks are performed on Terra Rawhide (5675 packages, around 50 GiB). Old benchmark results are provided as a reference since I didn't run hyperfine with logs. Here are my specs extracted from fastfetch:

OS: Ultramarine Linux 44 (Plasma Edition) x86_64
Kernel: Linux 7.1.3-cachyos1.fc44.x86_64
CPU: 13th Gen Intel(R) Core(TM) i9-13900H (12+8) @ 5.40 GHz
Memory: 15.24 GiB
Swap: 16.00 GiB
Disk: NVME SSD

Performance with Cache Enabled

 $ hyperfine -w 1 '/home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto --incremental' '/home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto --incremental' 'createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .' 
Benchmark 1: /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto --incremental
  Time (mean ± σ):     420.8 ms ±   6.0 ms    [User: 349.2 ms, System: 169.8 ms]
  Range (min … max):   415.4 ms … 436.1 ms    10 runs
 
Benchmark 2: /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto --incremental
  Time (mean ± σ):     313.7 ms ±   3.6 ms    [User: 411.4 ms, System: 190.5 ms]
  Range (min … max):   308.4 ms … 319.0 ms    10 runs
 
Benchmark 3: createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .
  Time (mean ± σ):      3.352 s ±  0.301 s    [User: 4.643 s, System: 0.587 s]
  Range (min … max):    3.043 s …  3.777 s    10 runs
 
Summary
  /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto --incremental ran
    1.34 ± 0.02 times faster than /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto --incremental
   10.69 ± 0.97 times faster than createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .

Note that createrepo_c skips writing repodata when nothing is changed, but that doesn't really matter here. satm createrepo / kiritan is still 8 times faster than createrepo_c without multi-threaded zstd, and over 10 times faster with multi-threaded zstd.

Memory Analysis with Cache Enabled

Here are the memory graphs for satm createrepo and createrepo_c. While it's just pure speculation, the first spike in the first graph is probably due to generating primary.xml, filelists.xml, and other.xml at the same time. Apart from maybe zstdmt, we can guarantee that the memory complexity in auto mode with or without caching is O(number of removed packages), since we need to store a vector of keys (filenames) for deleting removed entries in our cache, but that's strictly the only part where things are not "constant allocations". Note that temporary allocations are required when parsing rpm metadata (O(number of files in package)), but we don't think this should be accounted for in the overall memory complexity.

The peak is not seen with --zstd-multi 0 (which is the default value).

While we don't have concrete proofs, we suspect the memory complexity of createrepo_c to be O(n). You will see why in a minute.

Performance with Cold Cache

 $ hyperfine -p 'rmz repodata .subatomic-cache || true' -w 1 -m 5 '/home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto' '/home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto' 'createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .'
Benchmark 1: /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto
  Time (mean ± σ):     31.496 s ±  0.710 s    [User: 41.689 s, System: 22.112 s]
  Range (min … max):   30.380 s … 32.231 s    5 runs
 
Benchmark 2: /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto
  Time (mean ± σ):     31.434 s ±  0.775 s    [User: 41.745 s, System: 22.170 s]
  Range (min … max):   30.192 s … 32.276 s    5 runs
 
Benchmark 3: createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .
  Time (mean ± σ):     32.947 s ±  0.750 s    [User: 48.678 s, System: 23.213 s]
  Range (min … max):   31.878 s … 33.758 s    5 runs
 
Summary
  /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 20 auto ran
    1.00 ± 0.03 times faster than /home/mado/repos/subatomic/target/release-optimized/satm createrepo --input . --output repodata/ --zstd-multi 0 auto
    1.05 ± 0.04 times faster than createrepo_c --update --skip-stat --local-sqlite --workers 20 --ignore-lock .

At first glance you will think the difference isn't that much. You might be right if we're just talking about speed.

Memory Analysis with Cold Cache

For kiritan, during the scanning part, we can clearly see the memory usage is mostly linear. Again, the final peak is caused by zstdmt internal allocations. If you find this peak concerning, this can be avoided by disabling multi-threaded compression, but metadata generation will take slightly longer. The time difference is almost always negligible if the cache is cold.

Meanwhile, we can clearly see the memory usage for createrepo_c increases as time goes on, hence the suspicion that its complexity is O(n), linear to the number of packages:

Can We Go Faster?

You might be wondering if we can improve on the speed/performance. The short answer is no. The longer answer is maybe.

The bottleneck here isn't actually CPU, it's actually an IO bottleneck. During execution of both satm and createrepo_c, I was constantly getting 85%~90% IO utilisation, and all the free memory was converted to buffered memory by the kernel. The reason for high IO usage is for obtaining the package sha256 checksum, which is used for checking and identifying the package in metadata. The checksum is unfortunately not stored in the package header (since modifying the file changes its checksum). This is the only reason why we need to read the entire rpm package file.

Technically we could just not produce checksums and fully rely on PGP signatures, but this is pretty impractical and I'm not even so sure if the checksum field is optional in the metadata. A simple test (setting the checksum to an empty string) shows that without checksums, satm createrepo would finish in less than 1 s on the same setup.

rpm already stores per-file checksums in the package. Combined with the header checksums, not having a checksum for the entire package probably will not cause direct security issues. It's not practical right now, but it might happen in the (far) future.

Manual Mode

There are no equivalent benchmarks for manual mode: "no-op" is just not a thing in manual mode. We think running --add *.rpm would produce pretty much the same performance as auto, since the only difference is that satm needs to list out all files in the input folder recursively in auto mode. This completes extremely quickly, as seen in the benchmarks for auto.

Potential Downsides

One downside of subatomic & kiritan (probably) is the use of a separate cache, which is by default at $(pwd)/.subatomic-cache. In the above benchmark, the size of the cache was 251.0 MiB, which consists of mainly what we call XML "fragments" of the metadata. You can estimate the size of the cache by adding up the size of all the uncompressed XMLs together. This should be acceptable since you need plenty of storage to store lots of packages; if you have storage concerns, you have a bigger problem.

Some other current downsides (that will probably change in the future) include:

• Limited choice for compression. We currently only support ZSTD, but this might change in the future depending on demand.
• Limited choice for checksum type. Only sha256 is supported at this moment, but this will probably change in the future.
• Support for more metadata specifications. It will be really appreciated if you can submit pull requests for other repodata formats in your favourite RPM distribution. We currently only have support for:
  • primary.xml
  • filelists.xml
  • other.xml
  • appstream.xml
  • comps.xml

Under the Hood

The core mechanisms of libsubatomic revolves around the heed crate, which is a high level Rust API for LMDB. LMDB is a key-value database that enables zero-copy read access:

With memory-mapped files, LMDB delivers the read performance of a pure in-memory database while retaining the persistence of standard disk-based databases.

libsubatomic creates LMDB databases for storing KV pairs of rpm filename and the serialised XML fragment (with quick-xml) for the corresponding package. Think of it as if we are storing many BTreeMap<PathBuf, Vec<u8>> on the filesystem. Package parsing is achieved by the rpm Rust crate. The cache (databases) are first populated, then iterated and streamed to zstd, sha2::Digest, and std::fs::File, in parallel using rayon.

In auto mode with a populated cache, libsubatomic uses jwalk to recursively iterate through all rpm files in the given directory and check if the database contains an entry for that filename already. This step is usually instant (20 ms in the above test).

libsubatomic fully utilises zero-copying and streaming. All owned values have either a constant size, or a lifetime between the package getting parsed and the package getting inserted into the database. The only notable exceptions are:

• We temporarily store a vector of paths to removed packages after all fragment insertions and before the final xml generation.
• We do not control the memory usage of zstd. Its memory usage may be significant if multi-threading is enabled. Note that this is off by default.

Since subatomic v1 is still in heavy development, we are still improving our codebase to reduce package-lifetimed allocations, but don't put too much expectations on further speed improvements.

Subatomic and kiritan are open source software. The source code is licensed under AGPL-3.0-or-later, available here:

GitHub - FyraLabs/subatomic: A modern package delivery system for RPMs

A modern package delivery system for RPMs. Contribute to FyraLabs/subatomic development by creating an account on GitHub.

GitHubFyraLabs

Wrapping Up

That should be all of kiritan and subatomic for now. If you have any questions, you can create GitHub issues in the above repository.