Announcing Invar: A diskless transactional document DB
tl;dr - we've built a diskless NoSQL document database called Invar. It has well-defined durability guarantees, speaks Redis' native wire protocol, and persists data to S3-compatible object storage. We've open-sourced it. If you like it, please give it a star and say hi on our Discord :)
Back story
Invar's gestation is a little convoluted. It's the product of several system design iterations trying to solve some problems in an existing system, principally cost/GiB and tail latency.
Never let a crisis go to waste
Without breaking any confidences with past employers, the spark that started this journey came from an underperforming data pipeline with an excessive cloud bill attached to it [isn't it always thus?]. It was one of those many storage layers that worked just well enough, and didn't burn enough cash to garner a whole load of attention, but was a known frustration to SREs' on-call rotations, and product engineers who constantly agitated for a redesign. Eventually, the straw that broke the camel's back re. revising the architecture was pressure for more features, and after a few rounds of translating how this thing was on fire, from the esoteric to the concrete- i.e. "you can't deliver the roadmap you promised!", I got some Hammock Time under my belt to ponder on where to take this behemoth.
Discretion is the better part of valor
Some more context about the workload: the first system that needed attention was an AWS DocumentDB cluster which stored a bunch of key-value pairs which were ultimately a derivation of a domain-specific file format which users would upload (the derivation was complex, with hundreds of edge cases, but not germane to the system design). They were large-ish on their own: a long tail of files in the order of ~10MiB but at the upper end of the spectrum they'd cross into the gigabyte-range. Once processed and stored in DocumentDB, users could query this data using a proprietary S-expression-like language.
In a nutshell, the request path looked something like this:
User request
↓
Compute
↓
DocumentDB node
↓
Storage layer
In multi-tenant SaaS platforms, the correlation between resource usage and customer significance is often tenuous, but in this case there was a clear link between size/complexity of data stored and logo size; that's a diplomatic way of saying that high value customers would DoS us with 100s of GiB's of key/value pairs, and then complain when either the pipeline caught fire, or query latency became unacceptable. As this corpus grew into the hundreds of terabytes it became clear that colocating all these unrelated datasets into one giant cluster wasn't destined for Petabyte-scale.
The operative word there is unrelated: each file full of key/value pairs was a discrete dataset that customers would hit with point queries- there was no requirement for doing joins across datasets or anything exotic: ingest, parse, query. The rub is that we didn't have prior knowledge of exactly what kind of queries a customer would hit us with, so there was a degree of randomness there, and randomness is not something page caches do particularly well with.
Back to basics
While ingesting these files was a pain, it wasn't generally noticeable by end users unless the delay drifted into minutes/hours. What was much more obvious was the slow queries- a user would fire a predicate like:
(OR (= "some_key" 1.234) (> "other_key" 4.567))
at a REST API, and under the hood it'd go off and sift through this big keyspace to find stuff that matched. I want to qualify big though; it was only unwieldy because all these keys were munged together into one big DB, separated by a prefix; in reality, we'd be dealing with ~10^6 key-value pairs per dataset in the worst case. Even so, we had a long tail of queries taking double-digit seconds to complete, and a meaningful quantity which were timing out at the load balancer before finishing.
If you came up with the most crappy, pathologically bad storage format, e.g. dumping them all to a newline-delimited text file, a modern computer could grep through a million lines, at an average of ~1kb per line in well under a second, right? Nothing like some back-of-napkin math to give you a set of ground truths.
The workload:
1M lines
~1KiB/line
= ~1GiB total data to sift through
Assume fast fixed substring search (e.g.
grep+ Boyer-Moore)Ignore fixed costs like
fopen, page faulting, e.t.c for nowAssume cold reads, no page cache helping here
And let's throw it at a fairly average modern machine:
| Thing | Bandwidth |
|---|---|
| SSD | 5-15 GiB/s |
| RAM | 25-100+GiB/s |
grep* |
1-2GiB/s |
Even mediocre hardware is not the limiting factor here vs our 'workload' (grep); but even then, 1GiB/s / 1GiB ~= 1 second for even our toughest customers. So leaving aside bugs, the existing design was obviously not sympathetic to the underlying hardware.
The curse of network storage
Taking this from a degenerate single-machine case to a real cloud environment, you now additionally have to factor AWS's infrastructure limitations into your workload performance.
Remember that this corpus was living in DocumentDB. Consider a 3-node cluster of r6g.2xlarge nodes sitting on ~100TiB of data, there are a few salient points to keep in the back of your mind:
Since DocumentDB runs in a single-writer setup, you're not aggregating memory; you just have n separate page caches that can get messed up independently
An
r6g.2xlargeDocumentDB instance has an advertised baseline 12,000 IOPS availableAmazon publicly states that one DocumentDB IO operation is an 8k page read
A cold page read from the underlying Aurora storage layer has a p50 latency of 3ms
Background observation of our users' behavior showed a bias towards recency where a sliding window of ~5% of the newest uploads received basically all query traffic
We had a p99 latency goal of < 1 second, in an environment where we designed for ~10 public, user-issued queries/second; however those s-expressions would potentially hit multiple datasets in parallel, creating a 100:1 read amplification.
The ratio of corpus size to available memory and page throughput is important and eliding any other fixed costs, basically dictates whether that p99 is achievable or not.
You obviously can't devote all of the instances' 64GiB of RAM to page cache, but even if that were possible, the probability of a cache miss, even with our ~5TiB 'hot' working set is still extremely high.
If we take cacheable pages (remember a page is read in 8k chunks), C to be:
$$C = \frac {2^{36}}{8192} \approx 8,388,608$$
and the total in our working set, W:
$$W = \frac {5 \times 2^{40}}{8192} \approx 671,088,640$$
Which gives us a rather woeful ~98.75% miss rate probability.
$$P(miss) = 1-\frac{C}{W} \approx 98.75%$$
Given one of the design goals was to support hundreds of queries per second, it's a virtual certainty we'll hit the worst-case. But what about those 12k concurrent IOPS, don't they save us here? Not really, for a few reasons:
Index traversal is pointer-based (assuming we hit an index; due to the sparse/dynamic nature of the data, this was tricky, and index size itself became nontrivial) and therefore sequential by definition
Cursor iteration is also sequential. The index tells DocumentDB which document pages it needs, the query engine steps through the list, reads a document pointer, issues an 8KB page request to storage, waits the ~3ms for everything to arrive... and moves on to the next iteration
Aurora, as opposed to DocumentDB itself does have some support for colocating scans alongside the storage layer itself but this wasn't an option for us at the time, and would latterly have required a big rewrite without solving storage cost concerns
Given our p99 < 1 second requirement, and assuming that a cold storage page read takes ~3ms, we can tolerate no more than ~300 IOPS, (and presumed page misses per dataset...)
$$\frac {1,000} {3ms/IO} \approx 322iops$$
...which as we established earlier is unlikely to satisfy the 1 second upper bound if we assume, like we did from our single-node-text-file case, that an average dataset comprises ~1GiB's worth of key-value pairs (which breaks down to around 131,000 8k pages for DocumentDB to fetch).
Sympathy for the page cache
No cache algorithm is going to preemptively guess which pages need to be hot for a RAM:Working set ratio this small (yes, we could provision beefier boxes but at some point you hit a vertical limit that you can't throw more hardware at).
Remember the 5 rules? Data really does dominate. If you can figure out where it should be, at what time, you can generally get a half-decent design to fall out naturally. Going back to some things about our access pattern that we mentioned in passing:
In this case it was a WORM-type workload; datasets were never modified
Datasets were discrete: although parallel queries would fetch & merge resulting lists of values from multiple datasets, there were no joins or other exotic cross-dataset filtering or aggregation
Datasets exhibited a strong bias towards recency: since they were never modified, a user would simply upload a copy containing whatever modifications they had made; the now-old version could be demoted down a storage hierarchy
Latency wasn't a concern at import time; imports were a complex pipeline and parts were memory/CPU-bound, but throughput was more of a concern here; separating reads from writes would be ideal
Latency was a concern a query time; at this point, the hot working set really had to be hot, and the poor old page cache clearly didn't have enough out-of-band info to effectively decide that
V0: SQLite + Cache loader
Could we build something that better served our use case: sparse point-queries on millions of CoW key-value pairs that churned fairly frequently, without thrashing any caches?
What we came up with looked like this:
User request
↓
Compute + NVMe Disk Cache (ZFS)
↓
S3 (SQLite file per dataset)
Instead of munging all our de-structured dataset key-value pairs into one giant DB, we created an LZ4-compressed SQLite DB with a functionally equivalent schema for each one, and uploaded them as separate keys to S3.
Our 'hot' working set was colocated along side the application servers in the compute nodes, deployed as a stateful set on dedicated node groups in our EKS cluster fleet, using ZFS (we chose LZ4 for both S3 object compression and block-level compression but in hindsight, since S3 transfer times outweigh decompression time at scale, I'd probably pick zstd or gzip).
To glue all of this together, we consistently hashed traffic by dataset ID and built a pre-fetch mechanism for loading newly processed datasets into disk.
All this meant that cache invalidation now became a user-space problem. Devising a 'nice'/ergonomic/idiot-proof way of making it easy for application code to just load SQLite files on-demand, and quietly invalidate unneeded ones took a bit of trial and error: we considered AWS' own S3 mountpoint client, which at the time did not give us much control over cache invalidation without forking the repo. We also played around with our own FUSE implementation but the App -> Kernel -> FUSE Daemon -> Kernel -> App context switch was something we wanted to avoid as we imagined we'd want to do direct range queries against S3 on future versions of this system evolution (that never materialized, and I'm aware Mountpoint S3 also uses FUSE under the hood too :) We quietly wished that something like Zettacache made it upstream into OpenZFS; in its absence, I came across ZeroFS and SlateDB (more on that later); we also considered something along the lines of what Adroll did with userfaultd but decided on something a bit less exotic. Ultimately, we settled on a simple library embedded into the application which made S3 calls directly and handled invalidation on a background thread using a variety of algorithms, eventually settling on 2Q.
An interesting corollary to all of this is that since shipping V0, Amazon has added support for NVMe-based instance classes in DocumentDB clusters.
V1: LSM trees
Within the space of about a month, we got hit with two separate requirements that had a bearing on the future of this as-yet-unnamed SQLite + cache-loader.
The first, from the business side: could we offer dedicated, per-tenant databases to enterprise customers? It turns out we already had, by accident: one SQLite file per dataset, one dataset per tenant, was tenant isolation all along, we just hadn't noticed we'd built it. Want to bring your own S3 bucket/key infrastructure? Not a problem.
The second, from engineering: could this thing support OLTP-type workloads? V0 was designed for immutability from the get-go: SQLite files up through to the cache invalidation logic. Mutating a dataset meant re-uploading the whole thing, which is a fine strategy for "user replaces a file", but a terrible one for "user sends messages to an inbox".
V1 kept the spirit that of V0: a hot working set spread across a hash ring, and added a gossip layer to cut the miss rate whenever ring topology changed. But the storage engine itself changed: each node ran BadgerDB locally, an embedded Go LSM-tree store that actually supported mutation, with S3 relegated to storing incremental backups via BadgerDB's own backup API, running on a background goroutine. That was a real philosophical regression in terms of architectural purity in my mind, since S3 stopped being the source of truth. Where SQLite-on-S3 had been diskless by construction, BadgerDB-with-S3-backup was disk-first, but it did enable mutability, and the first workload that used it (an in-app messaging inbox) had a relaxed enough RPO that async backups were a perfectly acceptable tradeoff.
V1 turned out to be interstitial in more ways than one. Architecturally, it was clearly a stepping stone rather than a destination. Personally, it's also when I went full-time on this. The original framing was "tenant isolation as the product," and one more requirement fell out of that: MongoDB wire protocol support, for which I built a proof of concept in the same Go codebase (it was never open-sourced, and for both licensing and QA reasons, it's probably for the best). Somewhere in the middle of all of this, it became obvious that the database was a thing that needed to stand on its own, not live as a component buried inside some amorphous tenant-isolation platform. So I made the call to open source it, give it a name, and start over properly.
V2: Invar
Which brings us to SlateDB- the thing I'd wished, back in V0, that OpenZFS's ZettaCache had grown up to be. SlateDB is an LSM-tree storage engine built to sit directly on object storage, and it's the foundation Invar is actually built on: a Rust port, diskless by design, with S3 (or an S3-compatible store) as the durable source of truth and a best-effort local cache for latency-sensitive reads.
I didn't want "diskless" to compromise the DevEx, and running standalone, with no external functional dependencies, was a hard requirement since V0 that carries over into the present. So Invar can also run entirely on Fjall as a local, disk-only persistence layer. The wire protocol and semantics remain the same, minus S3. Having a solid story for local dev loops, CI builds, e.t.c is something I consider to be table-stakes functionality.
Right now I'm keeping the scope narrow: Redis compatibility is the most mature API surface, with some CI tests against real client libraries and frameworks (such as BullMQ), not just the raw command spec. It ported over to Rust pretty idiomatically. Before I widen the feature set further, I want a solid, boring process in place for how Invar takes contributions and evolves: for this to be a serious thing people can trust, the development itself has to scale beyond one person, and before you start adding combinatorial complexity to the feature set. MongoDB wire protocol support is on the horizon soon™, in some form, but there are a few non-technical barriers that I'll unpack elsewhere.
Alongside the database itself, I'm building a managed cloud offering, and despite swearing off it more than once, I still haven't let go of the enterprise "glue" I originally thought was the whole product: tenant management and ancillary tooling for running a fleet of these at scale. Looking back now, I just got the sequencing wrong: the workload (Invar) is easier to talk about than the workload isolation. I guess you should just do the thing you can explain to a 5 year old first.
Try it
If any part of this sounded familiar: a hot/cold access pattern that confuses page caches, a cloud bill that scales on the wrong trajectory, an ops team tired of debugging PVCs stuck in Pending, then Invar is on GitHub, Apache 2.0-licensed, and it speaks Redis, so there's a decent chance you can point something you already run at it today.
Stars, issues, and "why doesn't this command work" reports are all genuinely welcome. It's early, a little scrappy, and I think it's better this way.