Dune: Shared artifact cache

[jeremiedimino]

The PR describes how to add a global shared artifact cache so that build artifacts can be shared between different workspaces. For instance, this could speed up builds with opam as build artifacts could be shared between switches using the same version of the OCaml compiler.

Overview

The cache should be stored by default in the XDG cache directory (Xdg.cache_dir) and be enabled via either a command line flag or a configuration option in the user config file. When enabled, dune will continuously fill the cache with the newly build artifacts and will reuse artifacts from the cache when appropriate.

When the global cache is enable, it is expected that the last command in this script is much faster than the first one:

$ dune build
$ dune clean
$ dune build

When using a global cache, it is important that artifacts imported from the cache are exactly the same as freshly built ones. In particular, build commands must be reproducible. For instance, this means that the pwd must not end up in the produced artifacts.

By default, many build commands are not reproducible, and part of this work is to track them down. In addition to the above, we need a mode in which dune will not import artifacts from the cache but will instead check that freshly built artifacts are the same as the ones stored in the cache.

Given that it will not be possible to make build using older OCaml compiler reproducible, and that it will not be possible to make all user rules be reproducible, we need a way to mark some rules as non-reproducible. One way to do that is to add new kinds of dependencies that are tracked by dune, such as allowing to mark a rule as depending on the pwd. When a rule depends on the pwd, the pwd must be included in the hash that is computed in build_system.ml to implement incremental builds. Artifacts produced by rules that depend on the pwd should not be promoted to the shared artifact cache since that would be useless.

Sometimes, commands also include some random data in their output. Such rules should be marked as contains random data and their result should not be promoted to the shared cache as well.

Implementation

The shared cache is a key-value store, where keys are the hash of rules as computed in build_system.ml:752 and the values are the contents of targets. A simple way to represent this cache is to create one directory per key and store the targets as plain files in this directory. To avoid creating a directory with a huge number of sub-directories, which is inefficient on some OSes, we should use the following directory structure: <first-two-letters-of-the-hash>/<hash>.

Sharing files in the global cache should be done via hard links, in order to save on disk space and on build times. Files promoted to the global cache should be marked as read-only, to ensure that they are not modified by accident.

Often, build commands will directly open their targets with O_TRUNC. For this reason, it is important to delete the targets of a rule before executing the rule, to be sure that the command won't try to mutate the file in the global cache.

Metadata in the global cache

In addition to storing the contents of targets in the global cache, we also want to store their digest. This will ensure that dune doesn't have to recompute it when reusing these targets. The digests should be stored in a file in the same directory as the targets.

For consistency, dune should ensure that the list of files mentioned in this metadata file correspond to the list of targets it expects. This should allow to detect hash collision.

The metadata filename should not conflict with one of the target names. We can simply use the following name: <hash>.meta.

Atomicity

In case several instances of dune are running at the same time, it is important to ensure that all the targets are promoted at once to the global cache. For this reason promoting targets should be done in two steps:

• create the directory entry in a temporary directory in the global cache, using a name that is unique to the running process
• rename this directory to its final destination

Versionning

It is possible that we will want to change the format of the cache in the future. To simplify things, we can store everything in a sub-directory v1 of the global cache.

Trimming the cache

Over time, the cache will grow a lot. We need to provide a dune command to deal with the cache. For instance dune cache trim -by 50% to reduce the size of the cache by 50%. When deleting entries from the cache, dune should start by deleting:

• files with a hard link count of 1. These corresponding to files that are not used by any existing workspace
• files with the oldest access times. These are files that haven't been used in a while

Monitoring disk usage

The user should be able to specify a limit for the global cache. When using the global cache, dune should automatically trim the cache when it grows too much.

[jordwalke]

We're working on a tool that can cache Dune packages, ocaml compilers, or any other opam package. It is agnostic to build system, but does work very well with Dune. It works especially well with Dune because Dune respects fully out of source builds. It's called esy and you can check it out at https://esy.sh.

[jeremiedimino]

Yep, I saw esy, it looks like a cool project!

[jeremiedimino]

I finally gave esy a try and it is indeed really cool. The fact that in one command you get the whole development environment including the compiler, merlin and all the project dependencies is really impressive. The setup time once things are cached is really fast as well. In many way it feels like the right way to do develop opam packages.

Here is my comparison of the esy workflow and the duniverse one of putting all the source code together and letting dune do its magic: it seems to me that the esy workflow is better if you work on a single project while the duniverse one is better if you work on a large collection of packages at once.

More precisely, esy works at the granularity of whole packages, so there is no way we can beat the setup time by considering a huge monorepo at once like we do with duniverses or jenga inside Jane Street. Additionally, the amount of code the build system has to consider while the developer is working is a single project, which is a much smaller input and will naturally give fast turnarounds without requiring heavy machinery.

On the other hand, a big monorepo allows one to modify a library and see the effect on large number of reverse dependencies without effort. This literally allows one to do a breaking change and upgrade the whole world. It would be impossible to maintain a code base such as the Jane Street one without being able to do that. While there seems to be some support for this in esy, it doesn't seem like it would scale to say, 5000 reverse dependencies.

[rgrinberg]

One place where esy would be really cool would be for our blackbox tests by the way. We require certain versions of packages, and some packages aren't yet ported to dune (and likely will never be). Esy would handle all that for us and make the testing fast a well.

[jordwalke]

"Here is my comparison of the esy workflow and the duniverse one of putting all the source code together and letting dune do its magic: it seems to me that the esy workflow is better if you work on a single project while the duniverse one is better if you work on a large collection of packages at once."

esy spans multiple languages including JavaScript and C/C++ (we have some basic pkg-config support). Our goals are to make everything "one click" easy even for native dependencies like SDL/libffi (which is also an esy package). What this means is that we're building a solution that works for any language or build system within that language. I don't think it will ever approach the Dune monorepo level of performance especially when it comes to incremental builds, but you should definitely check out esy's link feature which allows you to develop a set of packages locally, fairly efficiently. It's a way to take multiple packages, written in multiple different languages (potentially) and make them behave as if they are a monorepo. So you never need to rebuild dependencies and "re-pin" them. It just automatically rebuilds dependencies if there's any changes in those dependencies, and "reinstalls" them into isolated, carefully maintained sandboxes which works even when you have a network of different packages all linking in strange ways and when they all use different versions of the compiler/flags. The key to doing this safely is out-of-source builds (which is why Dune's ability to configure the location of _build directory was necessary). It allows us to carefully create safe locations that avoid problems.

It is not currently as fast as Dune's monorepo approach for incremental builds primarily because the granularity is at the package level, not library/target level. But if people tended to make smaller packages, and if build systems provided the right hooks, it could in theory approach something like Dune's performance for large monorepo development. My intuition is that it could get to be 75% of the theoretical maximum performance for incremental builds. One thing that brings esy package builds closer to monorepo performance is that it builds packages in parallel, safely. The main advantage, as you pointed out, of esy is the near-instant cold cache builds of dependencies because of the relocatability that esy provides. So for example, on each hg revision, we can instantly bootstrap builds for all dependencies and any compiler version. File level distributed build caches never seem to live up to their hype, but package level granularity has proven very useful.

My observation was that very very few people actually develop in a monorepo. I do because I work at a company with a huge codebase. This is not the norm though. The norm is that people develop at the package granularity, and esy primarily intends to support the use case of developing within an open source ecosystem, and then provides a link feature which lets you turn that ecosystem into a monorepo for large companies.

It would be awesome if there was some way to approach the theoretical maximum performance in esy. It seems like something large companies would be more interested in than the common open source dev.

I'm not saying that esy provides exactly what you are looking for, but I do think it is a little closer to achieving your goals than is immediately clear - and it does a bunch of other stuff (like unifying JavaScript dependency management and C/C++ pkg-config management) that are beyond your needs but still cool.

[jordwalke]

This comment is not related to performance, but I wanted to also point out the importance of esy in avoiding fragmentation as well. Many peoples' day to day jobs require access to npm packages and it's currently so hard to have a package that uses both npm and opam that people currently will duplicate an effort from the ocaml ecosystem, but copied/forked into the npm ecosystem because it's easier than any other alternative. There's nothing you can tell people to make them do the more costly approach - they will take (what they believe to be) the cheapest path, and that creates an unnecessary mess. With esy that is no longer the case - the cheapest thing to do is to use existing packages from npm and existing packages from opam, and only make new packages if the existing options weren't suitable.

[rgrinberg]

@jordwalke isn't the shared artifacts cache exactly the speedup that you're looking for? Esy will save you rebuilds at the package level, and the shared artifacts cache will save you rebuilds at the target level. Dune's cache is more powerful but it only works for dune, while esy's cache is more general but doesn't work as well. I believe the two are complimentary.

[jordwalke]

I don't know how you could take advantage of Dune shared artifacts when using a package manager for developing packages. The package boundary only ever exposes ocamlfind metadata as the shared information. Dune caching would track its own workspaces and use the information within it as the cache key - but esy has its own "workspace" cache key used to determine build caching, and it's just not compatible with what Dune will be looking at. Unless something were to unify the two. But esy has different concerns tracked in its workspace identifier - such as the set of linked packages (for which there is no Dune analog yet).

[jeremiedimino]

I'm still skeptical that the esy workflow would work for upgrading a large number of packages at once, but I'm very curious to see.

A good experiment would be the following: take all the packages listed in our opam repository, rename Base.List.map to something else and see how difficult it is to propagate this change through all the packages. If you can come up with a simple workflow for this case, then I'm happy to discuss more about this. In the meantime we'll continue working on the shared artifact cache approach.

[rgrinberg]

We now have an artifacts cache. Concerns regarding the implementation and bug reports should go in separate issues.

[Lupus]

Which version of dune is going to get this feature? Any documentation available?

[Lupus]

Looks like documentation is here: https://dune.readthedocs.io/en/stable/caching.html
Awesome! Thanks for all the great work on dune!