1 of 33

Eric Burnett, Oct 2019

One Minute Presubmits

London Build Meetup Talk

Proprietary + Confidential

2 of 33

The Space

Proprietary + Confidential

3 of 33

Presubmits...

Proprietary + Confidential

4 of 33

Goal:

60 seconds

Proprietary + Confidential

5 of 33

Latency vs Happiness

Proprietary + Confidential

6 of 33

Latency vs Happiness

Proprietary + Confidential

7 of 33

The Problem

Proprietary + Confidential

8 of 33

Builder-centric world

Proprietary + Confidential

9 of 33

Storage-centric world

Proprietary + Confidential

10 of 33

Digression: Directories

Logically, a nested mapping from

path -> [attributes, contents]

Does not have to be on a single disk anywhere.

Could be a flat ‘manifest’:

/src/lib/a/a.txt -> [775, “aabbccdd1122”]

/src/lib/a/b.txt -> [775, “12341234aabb”]

Or a merkle tree: ------------------------------------------------------->

Proprietary + Confidential

11 of 33

Remote Execution principles

Move work off-host	Reuse prior results	Copy as little as possible
Work moved off-host can be parallelized onto the right number of right-sized workers.	Small, well-defined units of work are cacheable, and cached results don’t need to be executed again.	Data is only needed in two places: where it’s produced, and where it’s used. Every intermediate copy is unnecessary overhead. And file data is cacheable too!

Proprietary + Confidential

12 of 33

Structure of a “Build”

Source Fetch	Fetching the main repository
Dependency Fetch	Fetching dependencies Repositories and binary artifacts both
Transforms	Transforming the source code before building Applying patches, generating build files, injecting constants, leak checks, include checks, ...
Build/Test	Running the compile and/or tests
Results	Uploading artifacts for persistence

Proprietary + Confidential

13 of 33

Chart

Charts are generated from data in Google Sheets. To create a version of this chart with your data, click on the chart, and in the upper right hand corner, click the drop down arrow and select “Open source”��
In Google Sheets, select “File > make a copy.” In the copy, edit data as needed.
In Google Slides, click “Insert > Chart > From Sheets” and scale and align the new chart to the existing version. Move the new chart to the background by selecting “Arrange > Order > Send to back” and delete the original.

89%

Build / Test

7%

Dependency Fetch

1%

Source Fetch

0.5%

Results

Presubmit time, before Remote Execution

3%

Transforms

Proprietary + Confidential

14 of 33

Chart

Charts are generated from data in Google Sheets. To create a version of this chart with your data, click on the chart, and in the upper right hand corner, click the drop down arrow and select “Open source”��
In Google Sheets, select “File > make a copy.” In the copy, edit data as needed.
In Google Slides, click “Insert > Chart > From Sheets” and scale and align the new chart to the existing version. Move the new chart to the background by selecting “Arrange > Order > Send to back” and delete the original.

Presubmit time, with Remote Execution

12%

Build / Test

54%

Dependency Fetch

6%

Source Fetch

4%

Results

24%

Transforms

Proprietary + Confidential

These numbers are the same, except now using a build time of 1m.

Somewhat optimistic, in that neither Chrome nor Tensorflow has a build/test this quick today, but both do hit <50% regularly, and have key optimizations soon to land that’ll reduce the build stage’s share further.

But for full disclosure, I don’t yet see builds where fetching often dwarfs build+test.

Let’s make this concrete.

On Chrome builders, incremental source sync’s take between 30s and 5 minutes. Tensorflow is much smaller than these, but it’s not happening incrementally, so it’s still something like 2 minutes to get the code downloaded and into place.
And then we have source transforms....tensorflow’s copybara transformation stage takes something like 90 seconds all by itself.
Downloading tools, installing them into the local environment...30 seconds to a couple minutes in these examples. This all sounds a lot like the problems Remote Execution has already had to solve. If only we could apply the same solutions…
Uploading logs and artifacts - surprisingly time-consuming! Often 10s on the low end; easily extends into minutes too.

In total, we have a couple minutes on the low end to tens of minutes on the high end in pure overhead: making our precious CI runner do work other than running the build and tests.

15 of 33

Chart

Charts are generated from data in Google Sheets. To create a version of this chart with your data, click on the chart, and in the upper right hand corner, click the drop down arrow and select “Open source”��
In Google Sheets, select “File > make a copy.” In the copy, edit data as needed.
In Google Slides, click “Insert > Chart > From Sheets” and scale and align the new chart to the existing version. Move the new chart to the background by selecting “Arrange > Order > Send to back” and delete the original.

Builder utilization

12%

Build / Test

54%

Dependency Fetch

6%

Source Fetch

4%

Results

24%

Transforms

CPU

Network

Disk

Memory

Proprietary + Confidential

16 of 33

The Solution

Proprietary + Confidential

17 of 33

Move everything off-host

Proprietary + Confidential

18 of 33

New world

Proprietary + Confidential

19 of 33

Storage-centric principles

Operate on metadata	Cacheable operations	Minimal builder
Where possible, remove the data and operate only on metadata. Data can be fetched from storage where/when it’s needed.	Avoid executing the same process on the same data twice. Carve up data operations into small enough chunks that cache hits are common.	Prefer to do heavy lifting in trusted services, and use builders to orchestrate - execute scripts, small tools and remote builds. Individual builders should not need significant resources, and lost builders should not be a significant setback.

Proprietary + Confidential

20 of 33

Build phases - goals

Source Fetch	Make the inputs of the build available Need metadata, plus contents of a minority of files
Dependency Fetch	Resolve and make available the dependencies to the build Similar to ‘source fetch’; mostly static build-over-build
Transforms	A combination of source analysis and source-to-source rewrites Acting on a minority of files and/or highly cacheable
Build/Test	What we’re actually trying to accomplish! Only build configuration is required locally, plus metadata
Results	Persisting artifacts so they’re available later If files are already remote, handles are O(1) to save

Proprietary + Confidential

So, getting back to a build. Let’s think about what each of these phases is actually accomplishing for a second:

Source fetch: making the inputs of the build available, to be locally transformed.
Dependency fetch: Getting the secondary inputs referenced by the source, so we have everything we need. Might be novel, but most of the time most of the dependencies are the same as they were before.
Source transforms: some combination of source-level analysis and source-to-source rewrites. Might be as simple as applying a patch, or as complex as looking for forbidden dependencies across all the source files.
Compile/execution: the work we actually want to accomplish!
Uploading logs and artifacts: taking the work done on this local builder and persisting it somewhere, so it can outlive the presubmit run itself.

What could each look like in our off-host, storage-centric world?

21 of 33

Source Fetch

Build a virtual directory - merkle tree or manifest - of the repository at the desired ref.

New data copied into storage (not shown)

Reference the virtual directory for downstream work.

Proprietary + Confidential

22 of 33

Dependency Fetch

Build a virtual directory of the each dependency at the desired ref.

At build time, stitch these together with the top-level source into a single virtual directory containing all input files at the appropriate locations.

Proprietary + Confidential

23 of 33

Transforms

Strategically rewrite the virtual directory as needed.

Applying a patch: point additions/removals/ replacements of a few specific files.

Applying a transform: shard the work and apply it recursively, caching based on

<tool, rule, blob, path?> -> blob

or subtrees of the same.

Proprietary + Confidential

24 of 33

Build/Test

Execute the build tool on top of the virtual directory.

The build tool must be virtualization-aware: either take the virtual directory as input, or run on a FUSE filesystem with logic to get metadata (digests) from it and to insert remote outputs into it.

Proprietary + Confidential

25 of 33

Results

Persist handles to remote files instead of the file contents themselves.

May also persist whole directories, if desired: e.g. state of the file tree after every step and at the end of the build.

Optionally, extend the lifetime/durability of these remote files for persistence.

Proprietary + Confidential

26 of 33

New world

Proprietary + Confidential

27 of 33

Chart

Charts are generated from data in Google Sheets. To create a version of this chart with your data, click on the chart, and in the upper right hand corner, click the drop down arrow and select “Open source”��
In Google Sheets, select “File > make a copy.” In the copy, edit data as needed.
In Google Slides, click “Insert > Chart > From Sheets” and scale and align the new chart to the existing version. Move the new chart to the background by selecting “Arrange > Order > Send to back” and delete the original.

75%

Build / Test

6%

Dependency Fetch

6%

Source Fetch

1%

Results

Presubmit time, after remoting Everything

11%

Transforms

Proprietary + Confidential

And voila...CI is fast, and bottlenecked on build & test again, as it should be.

In this scenario we have source fetching at 5 seconds - getting the handle to the main repo, maybe applying a patch to it.
Dependency fetching is a matter of stitching together a few pre-existing virtual directories: I put this at another 5 seconds but it could be done a lot quicker than that.
Transforms I said would take 10, pretty much just pulled that out of my hat. Really depends what you’re trying to do here.
Build and test - still a minute, for consistency with the last time this slide came up.
Persisting results - sub-second, just writing down the digests of interest, maybe annotating them for longer storage.

Total: 81 seconds. (Not 60 seconds, mostly because I forgot to fudge the numbers for that, but there’s no reason it couldn’t be *faster* than that, even on huge repos with many deps).

28 of 33

Additional benefits

Reproducibility

Recreate any state; re-run single process from exact same starting point
Cheaply iterate on any single step

Auditability

“Free” persistence of whole input or output directory for debugging; auditing inputs; tracking provenance
Diff directories across builds, steps.

Flexibility

New, resource-intensive transforms can cheaply be added, so long as they’re cacheable.

Proprietary + Confidential

This model is certainly good for latency and performance, but it provides a number of other benefits at the same time that may not be as obvious.

Want to reproduce a build for debugging? Here’s a manifest file that lists every single input that went to it, down to the hash, which is simple to pull to a directory of your own.
Want to audit the provenance of a build? Here’s the same manifest, plus breakdowns of each git repo that was sync’d, and a handle to all artifacts produced.
Want to find all builds that included file X? E.g. you checked in your private key, and really want to contain the damage while you rotate it. Yeah, you could track that, and could go so far as to poison every downstream artifact that was novel as of that build.
Want to iterate on one phase of this process, e.g. the source transform? Sure, just rerun from that step - as a side-effect of this model, everything can be implicitly checkpointed; no point redoing redundant work.

29 of 33

Requirements

1	Durable content-addressed and key-value storage options
2	‘Syncer’ to fetch repos, transform into virtual directories, and populate repo@ref -> root map
3	Logic (service or builder-side) for resolving dependency tree and stitching the relevant virtual directories together for a build
4	Logic (service or builder-side) for applying any necessary source->source transforms
5	Virtual-directory-aware build tool

Proprietary + Confidential

I’ve built a number of pieces of this as prototypes of various forms, so I’m confident it can be done. In broad strokes:

Set up machine(s) to sync to each new commit of repos as they come in and snapshot them.
We’re going to need a service to apply patches without pulling the entirety of the source tree.
We’re going to need build tools to take manifests as input, and/or a FUSE filesystem that can be backed by one.

From my experimentation, playing with manifests of a million files takes a few seconds.

At this point, you can get creative. Want to “sync” the source once, and then kick off 10 builds in parallel on the exact same snapshot? Go for it. Want to run different phases of a build on different machines? Why not. Want to build from a chromebook? Yeah, everything here could be applied to developer builds easily enough.

30 of 33

Deployment

1	Start at the repo: remove successively more tasks from builder, but still copy all files down for legacy phases OR
2	Start at the build: virtualize fetches, virtualize outputs, virtualize inputs. Expand to cover pre-build transforms, and push upwards.

Proprietary + Confidential

31 of 33

Current Work

BuildStream has a remote ‘source cache’ for caching + staging inputs in this fashion - though not used virtually yet?
https://github.com/bazelbuild/remote-apis/ gaining improved protos and APIs for interacting with remote files/directories, initially to be implemented for offloading fetch/extract style operations.

Bazel already avoids pulling action outputs (https://github.com/bazelbuild/bazel/issues/6862), and will soon(?) gain the ability to virtualize inputs (“remote repositories”) it fetches.

Proprietary + Confidential

32 of 33

Thank You

Proprietary + Confidential

33 of 33

Additional Content

Bonus: Build tool “Storage Backend” vision

Proprietary + Confidential