Hacker News Reader

"In my head, there has always been a missing piece of software - a "database compiler", that can take the very complex and high-dimensionality abstract specification for a domain and codegen a purpose-built database engine."

You nailed it!

And this is in fact our design for TigerBeetle, an Iron Man suit that you can put any state machine business logic into. You get global consensus protocol and local storage engine, with all the performance of TigerBeetle, and it's a really nice experience writing your own business logic inside of that. You can even test everything using Deterministic Simulation Testing.

Long term, we want to extract this into a library. Reading the TB source, you'll see all these abstractions are something we're thinking about.

It is expensive in several dimensions to build a narrowly tailored database engine from scratch. Database engines are not modular, you can't assemble them from arbitrary parts while maintaining control of their basic characteristics.

Aren't things like LMDB and RocksDB sort of modular parts you can build databases around?

We dive into this in detail here in “Let's Remix Distributed Database Design!”, a talk given at the Recurse center: https://www.youtube.com/watch?v=rNmZZLant9o

TLDR: Here's also a 10 min lightning version given at HYTRADBOI '22, on why technology/research has changed enough that we need new storage engines to take advantage of where things are going: https://www.youtube.com/watch?v=yBBpUMR8dHw

That 2nd video is awful, it's just a talking head with the content repeated as text. It's the worst of both video and text.

???

Don't mind this guy and just watch the video. It's pretty much the same format that is used for conference videos everywhere.

It's fine.

The 2nd vid I downloaded. 18.5 meg. A transcription would be maybe 2K? And I could read it at my own speed instead of having to skip back when it covered things too fast, and there could be URLs to useful stuff like papers and wiki pages (like, perhaps, to Eytzinger Binary Search which I'd never heard of).

The video added precisely nothing to a text transcript and wasted an incredible factor for bandwidth. Just.. why?

Humans like me (and a couple other billion on YouTube) enjoy watching another human explaining stuff to them.

If plain text is your thing then that's good as well, to each its own.

I'm curious, did you already know what a Eytzinger Binary Search was?

No.

It’s kind of coming from the opposite direction, but it feels like Postgres extensions solve many of the needs you’re describing. They allow a developer to use the underlying database engine while extending it to include domain specific primitives.

That's the thing, I've written a lot of Postgres extensions over the decades. Those extensions are fundamentally limited by the underlying architecture of Postgres in myriad ways, though I've been very creative about pushing the limits. In the big picture the kinds of extensions that work well in Postgres are for a relatively narrow set of domains that roughly match what Postgres was designed for but for which it may lack some specific features.

The limitations and capabilities of a database are largely architectural. It isn't something you can "extend", it is either there or it isn't. This is why being able to codegen a purpose-built architecture would be interesting; instead of trying to force a domain into an architecture that doesn't fit well, we could produce an architecture that is a perfect fit for the domain while inheriting many of the basic quality of life features you expect.

I'd be fascinated to know what sort of things it is hard to write Postgres extensions for and how that interplays with their existing architecture choices, if you have the time to give some examples.

You know, we almost wrote TB as a Postgres extension!

I think it would have been the right thing to do 5 years ago, before some of the groundbreaking research that came out in 2018 like fsyncgate and “Protocol-Aware Recovery for Consensus-Based Storage” that really changed the way that distributed databases need to be designed [1].

These days we also have io_uring, Deterministic Simulation Testing and safer systems languages (Rust, Zig). And high availability, i.e. consensus, almost has to be part of the (distributed) database going forwards.

Beyond this, in the case of TB, a Postgres extension didn't satisfy our storage fault model, or our design goals of gray failure tail latency tolerance and static memory allocation.

What we're excited about with TB, is also this vision that people will one day be writing their own extensions for TB, swapping out the accounting state machine for another, with TB doing all the distributed heavy lifting.

[1] “Let's Remix Distributed Database Design!” https://www.youtube.com/watch?v=rNmZZLant9o

> In my head, there has always been a missing piece of software - a "database compiler", that can take the very complex and high-dimensionality abstract specification for a domain and codegen a purpose-built database engine.

Not just databases; this is a failing in our tooling more generally. "All" you need to do is code something flexible (in contxt, a feature-rich database), describe the (maybe probabilistic) things you know at compile time, and partially evaluate the first program optimally according to those constraints.

It's the same idea behind the Futamura projections, and unless there's something special that makes tailor-made databases significantly less diverse than arbitrary programs I doubt you'll see solutions here that allow you to mix and match very many components until the general case is also solved.

You have a middle ground which is a normal SQL database and a specific indexing engine tailored to your business case.

We do that for Cheméo, we use SQLite (or if the customer want PostgreSQL) as data store and query engine where it fits but some special indexes for some particular queries like a similarity search[0].

The advantage is that you can use the battle tested SQLite/PostgreSQL (companies love this "standard") and on top your domain specific engine which is stateless (we rebuild the indexes directly from the database, this way we have only one single source of truth and backup is easy).

[0]: https://www.chemeo.com/similar?smiles=CCC%28CCO%29CCC

TigerBeetle is designed to keep running even if all machines are experiencing radioactive levels of local storage corruption, or else shutdown safely when it detects that it must. We use automated testing to test TigerBeetle with read/write storage fault injection levels as high as 20-30%. On the other hand, this invariant is not typically given by other engines, per the storage fault research that's come out of UW-Madison the past few years. For example, “Protocol-Aware Recovery for Consensus-Based Storage”.

While other engines may have incredible test suites built up over years and years, they were also designed mostly before the advent of autonomous Deterministic Simulation Testing (think Jepsen except you can speed up time and replay bugs, for example, that would otherwise take 10 years to manifest in real time), which is a showstopper.

Finally, we wanted TigerBeetle to be highly available and distributed. TigerBeetle can run across 3 availability zones with 2 replicas in each, with seamless failover. You can stay running even if you lose a whole AZ plus another replica, thanks to Heidi Howard's Flexible Quorums. Again, this problem is not as simple as simply slapping on RAFT for distribution, because “Redundancy Does Not Imply Fault-Tolerance”, and because RAFT makes concessions around storage faults and dueling leaders for the sake of the readability of the paper, that we didn't want to make for TigerBeetle's actual implementation, hence our choice of Viewstamped Replication (MIT, '88, '12).

https://blog.chiselstrike.com/my-other-database-is-a-compile...