The Lark Devlog

What `kill -9` can't tell you

Back in July I wrote about why Lark has its own storage format, and I ended that post by talking about our internal chaos monkey. The design rule for our storage engine was simple: every way it can fail should leave you with wasted space rather than wrong data. Writes land in a write-ahead log first, a background worker folds them into the main blob file, new copies get written out before any pointers move, and to prove that all of this holds up, chaos monkey connects to a real Lark server and hits it with kill -9 at random moments for hours on end.

There's a catch with kill -9, though, and it took me a little while to fully appreciate what it meant for us. When you kill a process, the process dies, but the operating system is still standing right there. Every write the process handed to the kernel before the signal arrived is sitting safely in the OS page cache, and the kernel will cheerfully finish flushing those bytes to disk in order.

A power cut or a kernel panic is a very different kind of failure. Only bytes that have actually been synced to the drive are safe. Anything sitting in the page cache might land on disk only partially, broken up into 4 KB pages or even 512-byte sectors, and it might land out of order or not at all.

We'd been testing the polite kind of crash. Over the past couple of months we've gone back and built the tools to test the impolite kind, along with a set of model-based tests to check our assumptions from a few other angles. None of the bugs they uncovered ever hit production or customer data, but this is an area where investing early in worst-case scenario testing pays off dividends later on.

Three kinds of "did we lose anything?"

When you're trying to be sure a storage engine won't lose or corrupt someone's data, "does it work?" is really three separate questions, and each one wants a different kind of test.

The first question is whether the storage engine is logically right when nothing is crashing at all. Earlier on, most of our tests worked the way tests usually do: write a specific sequence of operations that we thought might be tricky, read the data back, and check that it looks right. The problem with that is that you only test the sequences you thought to write.

Recently we added model-based differential tests. Instead of hand-written scenarios, the test generates random batches of writes, deletes, updates, compactions, evictions, and server restarts, and feeds the exact same stream of operations to two places at once: the real Lark storage engine, and a tiny, dead-simple in-memory model that just applies writes in order to a plain JSON tree. After every step, the blob has to return the exact same answer as the model across whole-root reads, point reads, and shallow reads. We run one suite directly against the storage engine and another against the full server, with a nightly job running thousands of longer sequences that would be too slow for every pull request. Most of this random test data is not like anything a 'real' use-case would run through Lark, but it's helpful in teasing out edge cases.

The second question is whether the data stays right in a real process running under load over hours. That's chaos monkey's job, and we upgraded it in two ways that mattered a lot. Previously, each kill-and-restart cycle mostly checked the writes from that cycle. Now it carries its verified state forward across the entire run, so data written in cycle one is still being checked after ten more restarts and compactions. We also changed it to let paths go idle and get evicted from memory before each kill, which forces the pre-kill check to read back through the on-disk blob and the held write-ahead log rather than just reading what was already sitting in RAM.

The third question is the one we were missing: is the data right after the machine itself dies at any moment? That's where crash images come in, and I'll walk through how we built that in a moment.

What the models found

Before we even got to simulated power cuts, setting an independent model next to the storage engine turned up bugs that had been sitting quietly in the code. None of them needed exotic timing or a crash at the exact wrong microsecond. They were ordinary logic bugs in combinations of operations we simply hadn't thought to write a test for by hand.

The worst of them was a stale null byte during deletes. In lark-blob, when a value grows too large for its current spot and moves to the end of the file, its parent index gets updated to point to the new offset. If you deleted that key, we marked it deleted. If a later compaction batch deleted that same key a second time, the code went looking for the value to zero out its type tag and wrote a single null byte at the old offset from before the move. By that point, that old space might have been handed back out by the free list to completely unrelated live data. A string sitting there could come back truncated, or a container header could become unreadable. The fix was straightforward once we saw it: deleting a key that's already deleted is now a no-op.

We also found a cluster of bugs that we started calling ghost values. If a single compaction batch wrote a nested path underneath an existing primitive value (turning a number into an object with children) and then, in that same batch, deleted the children it had just written, the blob kept the original primitive around. Restart the server and the number was back, even though every client had seen it removed. Along similar lines, nulls written inside an update were being stored as values instead of treated as deletes during compaction, and if you deleted a node and wrote beneath it in the same batch, its old children would reappear alongside the new ones.

One more showed up in the read path rather than compaction. If a parent object was already loaded in memory and you read a child key that didn't exist, the lookup quietly inserted that key into the in-memory parent with a null value. Because Firebase treats null and absent as the same thing in most places, almost nothing noticed. Where it did show up was in limited queries, which could count the phantom null child as a real row and return one fewer result than you asked for, and in conditional writes on the parent, which failed because the parent's hash had changed behind the scenes simply because somebody read a missing key.

Every one of those was caught because the "dumb" in-memory model didn't have clever optimisations, didn't have a compaction pass, and didn't agree with what the server gave back.

Building a crash simulator

Once the logical model tests were clean, we still had the gap I mentioned at the start: what happens when the plug gets pulled halfway through a write?

You can't easily test power cuts by actually cutting power to a machine thousands of times in a loop, and even if you could, when something broke you'd never be able to reproduce the exact disk state that caused it. So instead we built a simulator that turns one real server run into hundreds of synthetic crash images.

It starts with an io-trace feature on the server. We run a seeded workload against a real database and storage worker -- growing values that have to move and free their old space, new children that shift multi-page collection indexes in place, overwrites, and deletes -- and io-trace records a journal of every durable file operation the server performs: every file creation, write, truncate, fdatasync, rename, remove, and directory sync, along with markers for when each client write was issued and acknowledged.

Then crash_model replays that journal against a simulated disk. For every file, it tracks two things: the bytes as the running process currently sees them in the page cache, and the bytes that are actually on the drive as of the last sync.

At any point in the journal, we can ask the simulated disk to produce a crash image:

We also run the power-loss simulator under two different rules for directory operations (creating, renaming, or removing a file). One models ext4's journal, where directory entries commit in order and an fdatasync that has to commit metadata brings earlier entries along with it. The other models the strict POSIX minimum, where a new file's directory entry isn't guaranteed to survive a power cut unless you explicitly fsync the directory itself. (POSIX promises you much less than you might think!)

Each crash image gets written out to a temporary directory and handed back to the real Lark server startup code to recover. To pass, every recovered image has to clear four bars:

  1. If the newest write-ahead log file ends in a torn line from an unacknowledged write, the server must refuse to load that database, name the file and line number, and leave the file untouched. The test then trims that torn final line the way an operator would and boots again.
  2. Once opened, the database has to contain every write that was acknowledged before the crash, and its state has to match some valid prefix of the writes that were in flight.
  3. The server then has to accept a fresh batch of writes on top of the recovered database and run several more compactions to completion.
  4. Finally, it has to restart twice more and read back identically each time.

Those last two steps are doing real work. Some kinds of on-disk damage don't show up on the first read after recovery; they sit quietly in the free list or an index header and only bite you two compactions later when that region gets reused.

And because a test harness this involved is only trustworthy if you know it can actually fail, we added a "lost-write control" test alongside it. It takes a valid image, deliberately removes one uncompacted line from the WAL, runs the same recovery check, and asserts that the test catches the missing write.

What changed in the write path

Pointing the crash simulator at our July storage design showed us a gap right away.

In the July post, I explained that when a value outgrows its spot, we write the new copy to the end of the file and make sure it's on disk before we update the parent pointer. That covered moves. What it didn't cover is that compaction also patches existing bytes in place -- updating parent index entries, container headers, and values that still fit in their old space. A single compaction batch can touch existing bytes across dozens of 4 KB pages in the blob. If the power goes out halfway through flushing those in-place writes, some pages have the new batch's changes and some still have the old ones. Replaying the WAL on startup isn't enough on its own if a container header or child index in the blob was left half-updated.

To close that hole, we changed the role of sidecar.lark (the small companion file that tracks reusable free space) and tightened the order in which a compaction batch reaches disk:

1. Write new/relocated data to free or appended space in blob.lark (nothing points to it yet)
2. Sync blob.lark
3. Write sidecar.lark with the updated free list AND a full copy of every in-place byte change
4. Sync sidecar.lark
5. Write the in-place changes into blob.lark
6. Sync blob.lark
7. Truncate the in-place copy off sidecar.lark
8. Write the new WAL sequence number to the `sequence` file  <-- commit point

The sequence file is the commit point for the batch. Until step 8 happens, the write-ahead log still holds all the operations in the batch and will replay them on startup.

If power fails during step 1 or 2, nothing in the blob points to the new bytes yet, so they're just harmless dead space. If power fails during step 3, the flush section at the end of the sidecar fails its xxh64 checksum on startup, which tells us we never reached step 5 and the blob hasn't been touched. And if power fails during step 5 -- right in the middle of modifying live bytes in the blob -- the sidecar has a complete, checksummed copy of every in-place write we were trying to make. On the next load, before anything reads the blob, finish_interrupted_flush simply replays those byte patches from the sidecar to finish the job.

We also stamped the sidecar with the WAL sequence number it corresponds to. Previously, if we crashed mid-batch after updating the sidecar's free list, the next run could trust that free list even though the batch never committed, which risked handing out byte regions that the blob was still using. Now, if the sidecar's sequence doesn't match the committed sequence file, the server ignores the sidecar on open. All that costs you is that the free list isn't reused until the next full compaction, which brings us right back to our favourite failure mode: wasted space instead of wrong data.

Along the way we fixed a few smaller durability details that the POSIX directory model flagged. Creating a new blob, sidecar, or WAL file now syncs the parent directory (and in strict/power-safe mode, a new WAL file's directory is synced before any write in it is acknowledged), and we moved those directory syncs off the hot path so they don't stall other databases sharing the same CPU core. We also changed how the server handles a torn trailing line at the end of a WAL file: instead of quietly skipping the broken line and then stalling compaction later, it now refuses to load that database and logs the exact file and line number so nothing is ever swept under the rug.

There are still limits to this approach

I'm much happier with where our storage testing is today than I was in August, but it's worth being clear about what these tests do and don't prove.

First, our crash images run against a software model of a disk and filesystem, not against a cabinet full of physical drives having their power relays clicked on and off. They prove that our write and sync ordering holds up under the rules of that model. They can't protect you if a cheap SSD lies to the kernel about having finished an fdatasync while the bytes are still sitting in volatile controller cache.

Second, generating and recovering hundreds of crash images across multiple compactions and restarts takes real time, so we don't run the crash-image suite on every pull request. CI verifies that the suite compiles on every push, and we run the actual crash-image tests whenever we touch compaction, the WAL, or durable write ordering.

Third, how much recent data can be lost when a machine dies still depends on which durability mode you choose to run. We recently rewrote our durability documentation to spell this out in plain numbers:

Mode Process crash can lose Machine crash can lose Write speed
Default Up to the last 2 seconds Up to about 30 seconds on a default Linux install Fastest
Power-safe Up to the last 2 seconds Up to the last 2 seconds Fast
Synchronous Nothing confirmed Up to about 30 seconds on a default Linux install Slower
Strict Nothing confirmed Nothing confirmed Slowest

In every mode, data that has already made it into the blob is safe; the trade-off is strictly about the tail of very recent writes vs. per-write latency.

All of these storage and crash-recovery improvements are part of the 0.3.0, 0.4.0, and upcoming 0.5.0 releases on GitHub, and they're already running on Lark Cloud.