Job queues are deceptively tricky
Job queues are deceptively tricky
One of the fun things about being a programmer<br>is that as I look more into systems that I didn’t<br>know much about, what superficially appears to be<br>a simple system actually reveals interesting facets<br>of underlying complexity. In other words,<br>reality has a surprising amount of detail.
In this post, I want to talk about job queues,<br>which I’ve been thinking about for the past few days<br>(and while drafting this post in my head, I realized<br>I’d thought about them for longer at a previous job,<br>but not nearly with as much clarity.)
What do I mean by “job queue”? I mean a system<br>where there is some notion of submitting batch jobs,<br>scheduling them, and running them. Generally,<br>the system is expected to be FIFO or FIFO-like,<br>but that’s not required. Usually, the queue bundles<br>together a native way to schedule jobs periodically<br>– this lets you specify submissions using configuration<br>files (e.g. using JSON or YAML).
Job queues arise naturally in all sorts of situations<br>where throughput requirements are high, but latency<br>requirements are not that high. Continuous integration<br>is a common example. Another example is summaries<br>for the purpose of data analysis.
Over the past year or two, a handful of lenses that<br>I’ve found useful when thinking about system design are:
Being wary of queues: Queues tend to typically be<br>the_problems_of_queues">close to full or close to empty,<br>requiring some thought around appropriate sizing.<br>I’ve also learnt a bunch of counter-intuitive<br>behavior of queues when it comes to latency<br>from Marc Brooker’s blog.In blog posts I’ve read about queues, the focus is generally on latency, not on throughput, which is I think partly why I never really mentally linked “queues” and “job queues” earlier.
Limits:<br>This is based on the Tiger Style<br>guide written by the folks at TigerBeetle,<br>which talks about explicit limits on various things.<br>On generalization, this leads to the notion of<br>tolerances and having budgets for modular reasoning.Funnily enough, near the start of my career at Apple, I remember being mildly bemused at certain discussions where teams would discuss how much memory budget they would have to bargain for, especially for low-level code. I have grown more respect for that approach over time.
Fault models: Roughly speaking, a fault model<br>describes your assumptions related to errors<br>and reliability in your dependencies.
I’ve learnt a bunch on this topic from the talks<br>and tweets by the TigerBeetle CEO Joran Dirk Greef,<br>as well as writing by Alex Miller.
I will try to demonstrate how these lenses can apply<br>for system design later in this post.
The problem at hand
At $WORK, we have a background job for packing “reference repos”.<br>A reference repo is a git repo which has been aggressively repacked<br>– if you’re unfamiliar with repacking, you can think<br>of this as more “aggressively compressed”.
These are stored in object storage, and a new repo can be<br>set up on a machine by downloading the reference repo,<br>and fetching a delta of changes for the tip of the default branch.<br>When it comes to very large repos, for the downloader,<br>this approach helps cut down latency compared to the<br>more typical approach of doing a git clone operation.
The actual details of how git does aggressive repacking is not super<br>relevant for this post. What does matter is that there are,<br>roughly speaking, two forms of repacking available:
Wholesale repacking: This will lead to git ignoring any<br>baseline information about how packing should be done,<br>and recompute everything from scratch. Say for the repo<br>under test, this takes 7 hours.If you’re surprised at the thought of a git operation taking several hours, (1) you should be happy that you don’t have this problem and (2) some of the sub-operations here are seemingly single-threaded, regardless of repo size.
Incremental repacking: This will lead to git reusing the<br>baseline information already stored in the repo about packing,<br>so it will only repack things which have changed.<br>So if you did a clone, then did a fetch, then only<br>the newer changes from fetch will be repacked,<br>and only some cursory checks will be performed<br>on the history received from the clone operation.<br>Say this takes 2 hours.
OK. So that’s the setup.
We have the option of doing the<br>more expensive thing, which takes 7 hours. This buys us<br>a smaller reference repo, which means faster downloads,<br>faster un-tarring and lower disk usage.<br>To give a size ballpark, a wholesale repacked repo<br>can be up around 50-60% smaller than an incrementally<br>packed repo.
We have the option of doing the cheaper thing,<br>which takes 2 hours. This buys us more up-to-date reference repos,<br>which means that if the downloader still cares<br>about getting the latest changes,<br>the delta it will fetch subsequently will be smaller,<br>so it’ll be faster and put less load on the server.<br>But also, if the extra disk usage is in the hundreds<br>of megabytes or gigabytes, then that’s not...