Why Lark has its own storage format
Lark is a realtime database with a Firebase-compatible API, and the obvious way to build something like that is the way Supabase did it, where you write the realtime layer and the auth and the rules engine yourself, and then put all of it in front of a storage engine that already exists and already works. Postgres has been keeping people's data safe for thirty years and I have not, so that seemed like a pretty easy call to make. Writing your own durability layer is something that you avoid if at all possible.
So I went looking for the database to put underneath, and this story is about what I found, why none of it really fit, and what we ended up building instead.
What the data actually looks like
Before the rest of this makes sense you need to picture the shape of the data, because data typically stored in Firebase is a little unusual and it's the big reason this got complicated.
Firebase realtime database is based around one magical idea: what if you could take a JSON tree, and then just sync it between people? The constraint underlying that magic is that the entire database, whether it's 10MB or 100GB, is one giant JSON document living in a single tree. That means a chat message and a game session are both just values sitting at some path inside it, and you read and write by addressing those paths. There's nothing in there that acts as a natural boundary the way a row or a document would, and you're free to modify the structure, adding keys to any part of the tree, whenever you'd like. That's a big part of why Firebase is so pleasant to build against, and it turns out to be where many of its toughest technical challenges come from.
In addition to the shape of the data, the write pattern itself presents some challenges. Realtime apps tend to write very small things very often, like a player's position that updates thirty times a second while somebody drags a token across a map. That's a handful of bytes landing over and over on the same small part of a tree that might be enormous.
So the question I was really asking every database I looked at was a pretty specific one: can you change a few bytes deep inside a very large JSON structure without rewriting the whole thing to disk?
Postgres
My first stop was Postgres, which I know has jsonb, a genuinely nice binary JSON format which I have used many times in the past for smaller data.
The trouble is that there's no partial disk update path for it. Postgres is an MVCC database, so changing any part of a row writes a whole new version of that row, and once a value gets large enough it also goes through TOAST, which means that on every write your JSON gets pulled out of storage, decompressed, modified, recompressed and written back as new chunks. jsonb_set() looks like it's making a surgical little change, but underneath it's rewriting the entire value.
None of which is a criticism. It's a very reasonable design for the workload Postgres is built for, where a row is a modest thing that you update every now and then. It just means our write cost would scale with the size of the tree rather than the size of the change, and in our case the tree could be gigabytes in size.
The other option is to stop storing the tree as JSON at all and normalize it into rows with a path column instead. People do this and it works fine, but then you spend the rest of your time rebuilding tree operations by hand on top of it, since reading a subtree turns into a query and all of Firebase's semantics have to be reimplemented in SQL anyway. My gut feeling was that this wouldn't scale effectively and would lead to a lot of footguns in the future.
MySQL
MySQL 8 does support real in-place partial updates of JSON columns, so it seemed at first to be an excellent fit. If you change a value and the new one fits in the space the old one was using, it'll patch those bytes directly, and it will even ship a binary diff to your replicas rather than the whole document. That was precisely the mechanism I'd been hunting for.
Then I dug deeper. The update has to go through particular functions (JSON_SET, JSON_REPLACE or JSON_REMOVE, so assigning a new document to the column outright never qualifies), the source and target column have to be the same, and the new value can't be any larger than the old one. And then there's the condition that ended it for us, which is that partial update only applies when you're replacing values that already exist in the JSON tree. You can't add a new key to an object and stay on the fast path.
Adding new keys is most of what a realtime database does! Every time somebody posts a chat message or joins a game, that's a new key appearing somewhere in the tree under a freshly generated push ID. So the thing we'd be doing most often is the one operation that falls back to rewriting the whole document.
MongoDB
The obvious next thought is to go use a database that was actually built for JSON documents, so I investigated MongoDB.
MongoDB caps a single document at 16MB. That's a deliberate limit and a sensible one for document workloads, but our tree is conceptually one document and it can be hundreds of gigabytes, so it would have to be split up across a lot of them. I actually did prototype a version of this, by breaking the JSON tree itself down into 'segments'. Essentially I would try and detect natural boundaries in the data (for example, a sub-tree that had a lot of push ID keys each of which had a small value in them). However, there were a lot of edge cases to deal with, such as merging segments back together, partial tree deletions, and even deciding where to choose segment boundaries in the first place seemed highly dependent on the shape of the data being stored, so it likely would have required some kind of 'hinting' by the end user for large databases...all of which led me to realize this wasn't going to work well.
In the end, this approach would have required me to end up writing a tree-structured storage on top of MongoDB, which was the thing I was trying to avoid by using MongoDB in the first place.
(In fairness to Mongo, WiredTiger is smarter about updates than "rewrites the document" makes it sound, and it can journal changes as deltas. The document boundary was our blocker rather than the write path.)
Somebody already solved this
At this point I'd started reading papers instead of documentation, which is usually a sign that things have gone sideways.
And I found one! In 2020 Oracle published a paper on OSON, which is the binary JSON format behind their native JSON type. It describes a tree encoded with jump offsets so that you can navigate straight to a node without scanning past its siblings, field names deduplicated into a dictionary so that a million objects with a position key can be stored more efficiently, and updates that patch bytes in place instead of rewriting. It was more or less exactly the thing I needed, and I remember being pretty relieved for about ten minutes.
Then, of course: it's Oracle Database. The design is published and the implementation is very much not available to me.
That's the point where this stopped feeling like my decision to make. The right structure for the problem already existed and had been worked out by people far better at storage engines than I am, and the only way to actually have it was to build it.
So we built one
lark-blob is what came out of that, and it takes many of the ideas from the paper and builds on top of them with some additional tricks that work well for our needs. A database lives in a single file as a depth-first tree, so any subtree is a contiguous run of bytes that can be read in one go (which works very well for modern NVMe storage drives), and every parent carries an index of where its children live so that getting to a path is a few jumps rather than a scan. Structural field names live in a dictionary and get referenced by index, which is why ten thousand player objects that all share the same handful of fields take up considerably less room on disk than the JSON that produced them.
In front of that there's a write-ahead log. Writes land in the log first, which is a small append to a JSONL file and nothing else, and then a background worker folds them into the blob a few seconds later. Because that worker is applying changes rather than rewriting, its cost scales with how much you wrote and not with how big your database is, so folding a few megabytes of recent writes into a two hundred gigabyte blob takes milliseconds. It can also do some de-duping before it writes, so if you are writing to the same path rapidly, we don't pay the disk operations cost for each individual write when compacting.
When a value grows too big for the space it's currently sitting in, we write the new copy at the end of the file and update its parent to point at the new location, which leaves a hole where it used to be. Those holes get tracked in a small companion file (the "sidecar") and handed back out to later writes, and that's what keeps the blob from growing forever. Every so often, once enough dead space has piled up, a separate tool rewrites the file clean (like defragmenting your hard drive from back in the day).
Never losing data
Of course, the most important piece of this is making sure that when you save something, you can get it back later. Our core rule is simple: every way this can fail should leave you with wasted space rather than with wrong data.
Everything else follows from that. When a value moves we write the new copy and make sure it's safely on disk before we touch the pointer that makes it live, so if we crash in between then the pointer is still referring to the old copy, which is still perfectly good, and the new bytes are simply orphaned until something reclaims them later (and since the write ahead log is the source of truth and applying it to the blob is idempotent, we just redo the compaction and no data is lost). Folding writes into the blob only ever adds bytes or patches them in place and never removes anything, so there's never a window where your data is gone but its replacement hasn't arrived yet. And when we do rewrite the file completely we build the new one alongside the old and only swap them once the new one is fully written down.
That little companion file tracking reusable space is deliberately treated as a hint rather than as the truth. If we crash between updating the blob and updating the sidecar, we might forget that some space was free, which costs you a bit of disk until the next cleanup.
Breaking it on purpose
Reasoning carefully about crash safety is a good start, but it only gets you so far on its own, because the only way to actually prove it is to actually crash it.
For the purpose, we created our internal tool 'chaos monkey', named after the famous Netflix one, and doing much the same job in a narrower place. It connects to a real Lark server and writes to it continuously, keeping its own record of every write the server said it had saved, and then at some random moment it kills the server. There's no shutdown and no warning, and it may well be in the middle of writing to disk when it happens. Then it starts the server back up and asks whether everything it was told had been saved is still there.
Then it does it again, over and over, for hours.
It'll also run the compaction tool in between kills, so that recovery gets tested through the most expensive code path, and it checks that the files on disk still parse as what they claim to be. But the heart of it is really just that one question, asked at the worst possible moment.
In conclusion
To be perfectly honest, this is the part of the entire Lark project that is the most stressful to me. If a realtime database frontend goes down for a few hours, it's inconvenient but not catastrophic. If data is lost, it's a disaster. That's why we've put so much effort into our storage format, and why we were so hesitant to build our own in the first place. Now that we've finished, we're confident that what we've built is well-suited to providing the best experience for Lark users -- marrying fast latency alongside durability that's designed for the flexibility required by "it's just a JSON tree". But it's something we'll continue to safeguard and monitor as Lark grows, and we'll keep using every tool we have, from unit tests to full-blown intentional crashes, to help us do so.
Until next time, keep your data safe!