Chorus: A fast WAL for object storage - Tyler Rockwood's Website

Recently, I’ve been fascinated by the trend of building data storage systems on object storage. Systems like TurboPuffer are all the rage in the search space right now. New storage primitives like SlateDB make creating bespoke storage systems feasible for a single developer or small team.

A former colleague of mine, Nicolae, actually wrote this really interesting protocol and formal model for a write-ahead log on object storage called OSWALD. It’s very cool work, and there are obviously a lot of benefits to object-storage-first systems:

You get bottomless storage out of the box.

You can move the compute around really easily, which drastically simplifies Day 2 operations.

Object storage is very robust and auto-scales incredibly well. It’s just a really good primitive to work with.

However, building on object storage always comes at the cost of write latency.

You can normally hide read latency behind a cache. As an example, TurboPuffer will have a cold start, download the objects to local NVMe, and then do all its searches from there, so its warm latency is incredibly fast. Before a user even hits Enter in the search bar, you can pre-warm the cache and provide instant search while still storing all the data as objects.

But you can’t hide write latency unless you sacrifice durability or move off object storage entirely. Then you lose all those nice benefits of object storage.

Rapid Storage Buckets

That’s why, earlier this year, I was interested to see that Google Cloud’s Rapid Storage Buckets had become generally available. As I understand it, they are basically a very thin veneer over the Colossus storage system at Google.

The really interesting thing is that the interface they expose differs from traditional S3 APIs. The write path is actually based on objects being appendable. In my testing, the appends have incredibly low latency. With fsync turned on, I see commit latency of 2 milliseconds at P99.

It is incredibly fast, and I’ve kept wondering: Can we build a robust, object-storage-first storage system without sacrificing write latency by putting the write-ahead log in a Rapid bucket and the rest of the data in a cheap regional bucket? The downside of these fast, appendable objects is that they are scoped to a single zone. If you want higher durability guarantees, you’re going to need to write to a quorum of zones via some kind of replication protocol.

Your use case may not require high availability. Especially for a write-ahead log, if you’re archiving every few seconds to regional storage, a couple of seconds of data loss may be acceptable. It will be awkward to swap to another bucket and reconfigure applications to write to another zone, but it’s a trade-off that I think you can make a good case for.

However, some use cases absolutely require higher availability and need to tolerate zone failures. In this case, we need a replication protocol, and there are really two ways to go about it. One is to use something like Raft, place each log in the group in a different zone, and replicate across zones. But managing consensus and performing reconfigurations complicates operations. Since storage and compute are decoupled, you need to enforce a single writer for each log anyway. The alternative is an OSWALD-like system in which the client manages replication to each zone.

Enter Chorus

That’s where this idea, which has been eating at me for a while, comes from. It takes the architectural inspiration of OSWALD and asks: Can we make that work for Rapid Storage Buckets? Can we get a single-writer write-ahead log that is incredibly fast but replicated across a region?

And that’s where Chorus comes in.

Chorus is a single-writer write-ahead log built on top of Rapid Storage Buckets. For its control plane, it uses a single regional linearizable register to perform Compare-and-Swap (CAS) operations on the log’s metadata. This register can be a single object in a regional storage bucket but can easily be swapped out for a database row in Firestore or Spanner. The data plane then consists almost entirely of appends to at least a quorum of zonal objects in different buckets. It comes batteries included with segment rotation, prefix truncation, and orphan cleanup.

Together, this gives you incredibly fast writes, a system built completely on object storage, and zone-fault tolerance. In fact, I benchmarked my implementation against a simple log on Hyperdisk High-Availability Block Storage, and the P99 for Chorus was faster than the P50 for Hyperdisk HA.

In the course of developing this, I wanted to do a few things:

Use a formal model: Like OSWALD, I wanted to use a formal model to verify that this really works and that there are no weird edge cases around recovery, rotation, or a crash at just the wrong time. Having a single regional register for metadata simplifies a lot of the edge cases. While I know the hardcore people use TLA+, I...