_vvhw

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

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

"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.

Yes, agreed with you as to buffer underflows. Here, I really like that Zig has checked arithmetic enabled by default in safe builds. It's a small decision (to many) but so important. It surprises me that Rust does not do this for safe builds. A panic is stronger (and safer) than only wrapping or (implicit) saturating arithmetic.

Thanks, that's a great insight!

Does it follow that the fact that temporal violations could be used to violate runtime spatial checks, therefore means that spatial safety in itself is entirely without value?

What are your thoughts also on buffer underflows? I ask since I take it you also work on offensive security.

There is in fact a spectrum with respect to memory safety. For example, temporal vs spatial safety.

Furthermore, no language is “memory safe” in the absolute sense. For example, not even the borrow checker can protect you from buffer bleeds.

After the Zig compiler that is, which dwarfs TB's code base. The Zig core team are all machines. ;)

Thanks! I don't think we could have done TigerBeetle the way we did, without Zig. It's been two years now, and looking back the choice has worked out well for our design decisions. For example:

- single-threaded control plane (thread-per-core architecture),

- static memory allocation at startup (we never call malloc() or free() thereafter—no UAFs) for extreme memory efficiency (TB can address 100 TiB storage using only 1 GiB statically allocated memory),

- explicit memory alignment expressed in the type system (for Direct I/O), and of course,

- Zig's comptime which is insane. We use it to do all kinds of things like optimize the creation of Eyztinger layouts, or to eliminate length prefixes in our on disk LSM table formats.

Thanks!

What we realized for TigerBeetle, is that double-entry is often lifted and brought directly into the networked world of distributed systems as double-entry, as a ledger database.

However, most distributed financial systems of record also spend alot of their time talking to other distributed financial systems of record. So there are all these different entities (e.g. banks) all running different infrastructure and all wanting not only to track money within their own system but also to move money safely between systems.

Historically, double-entry is great at tracking transactions within a system or entity, but it's not great at this intersection between double-entry and distributed systems, because of the way that networks fail.

We were seeing that these systems all end up with the equivalent of a two-phase commit coordinator, which is alot of work to implement correctly on top of double-entry. And everyone is building these ad hoc ledgers that are not only ledgers but also two-phase commit coordinators.

So what we've done for TigerBeetle [1], is to take double-entry and marry it with distributed systems, to make it really easy to track transactions as money enters and leaves a system, by providing two-phase double-entry transfers out of the box. For example, not only a debits/credits balance, but also the concept of pending/posted debits/credits balance.

And then to package this all up as a mission-critical safe and performant (1m TPS) open source database that the whole ecosystem can partner with and build on.

[1] I did a deep dive into TigerBeetle in a recent talk at the Recurse Center called “Let's Remix Distributed Database Design!“ going into the storage fault research that we've implemented for TigerBeetle. For example, the safety reasons for why we didn't pick RAFT as our consensus, or the latency reasons for why we don't use LevelDB or RocksDB, and how our testing is inspired by FoundationDB's Deterministic Simulation Testing — https://www.youtube.com/watch?v=rNmZZLant9o

What I mean is, if you're implementing Paxos/RAFT—what do you expect of the disk, that it's perfect?

What then would you specify as the clearly defined storage fault model for non-Byzantine protocols such as Paxos/RAFT that rely on stable storage for correctness?

“the performance of the underlying hardware has increased so much in the last decade that the simplicity of SQLite has become a more important tradeoff”

Thanks for articulating this so clearly! It's going to be interesting also to see how much simplicity is realized from new thread-per-core designs leveraging io_uring to get rid of multithreading, locks and memory barriers scattered throughout the control plane. The performance dynamics are all changing and it's easier than ever to be writing simple, fast systems, that hit the 90% sweet spot.

You've probably also seen McSherry et. al's “Scalability! But at what COST?” [1]

[1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/...

Indeed!

I was so glad to see you cite not only the Rebello paper but also Protocol-Aware Recovery for Consensus-Based Storage. When I read your first comment, I was about to reply to mention PAR, and then saw you had saved me the trouble!

UW-Madison are truly the vanguard where consensus hits the disk.

We implemented Protocol-Aware Recovery for TigerBeetle [1], and I did a talk recently at the Recurse Center diving into PAR, talking about the intersection of global consensus protocol and local storage engine. It's called Let's Remix Distributed Database Design! [2] and owes the big ideas to UW-Madison.

[1] https://github.com/coilhq/tigerbeetle

[2] https://www.youtube.com/watch?v=rNmZZLant9o

And yet many non-Byzantine consensus protocols are equipped to handle the network fault model, which could be seen as equally Byzantine under this definition.

The problem is really that many formal proofs of consensus have focused only on the network fault model, and neglected the storage fault model.

Both network/storage fault models require practical engineering efforts to get right. I think a better term for this is “near-Byzantine” fault tolerance. It's what non-Byzantine fault tolerance looks like when implemented correctly in the real world—the GP comment is a great example of how to approach and think about this from an engineering perspective.

I dive into this in detail also here: https://www.youtube.com/watch?v=rNmZZLant9o

We are using Zig for TigerBeetle—churn has not been bad and `zig fmt` is pretty good.

Balance tracking seems to be the Achilles' heel of SQL databases.

For example, my experience has been that in the world of payments, the nature of money transactions is to debit perhaps many different accounts on the one side, but credit only a handful of accounts on the other, so that group commit can't fully amortize fsync.

Performance panaceas mostly come down to sharding, but sharding doesn't work well where you need strict updates to balances.

At work, we saw this play out several times in different systems, and decided to do something about it. We took the ledger of an open-source payments switch called Mojaloop, and extracted it as a distributed financial accounting database called TigerBeetle, designed to track financial transactions at scale.

The key performance insight was to dial up group commit. We batch up balance updates so that a single DB query can do on the order of 10k balance updates. We then fsync the batch with a single write before commit, moving the performance needle out from 1k-10k TPS to 1m TPS.

This is the advantage of a purpose-built database that's designed for counting at scale.

More information, including our design decisions are in the repo here: https://github.com/coilhq/tigerbeetle

”I fight for the users!”

Hey Reini! I've always loved your smhasher benchmarks. Appreciate also that you have Mitzenmacher's tabulation hashing in there, which is my goto.

We don't use SQLite—I don't know how you got that impression? You can find out more about TB's actual storage engine here [1].

However, I have only tremendous respect for SQLite. And to be fair, it's meant to be run embedded, the application is responsible for security, and many applications couldn't go far wrong picking SQLite. It's a fantastic piece of engineering.

[1] https://www.youtube.com/watch?v=yBBpUMR8dHw

> It sounds like payments might be part of the larger concept of declarative programming (DP)

Yes, exactly! The idea with TigerBeetle's state machine [1] is to expose double-entry accounting as a higher level financial primitive, so that developers can think in terms of declaring transfers from one account to another. The business logic behind the scenes is detailed. The interfaces and data structures are simple.

[1] https://github.com/coilhq/tigerbeetle/blob/main/src/state_ma...

> Maybe TigerBeetle could be generalized to support any multi-step distributed process?

That's part of the plan—that the distributed database framework of TigerBeetle can be used as an ”Iron Man suit” to support any kind of state machine, with high availability and fault tolerance.

> I sense a bit of Fear of God motivating your story, something that motivated your management to care -- who is that authority, so that I might get them on my case?

Haha! :) The authority is none other than Remzi Arpaci-Dusseau at UW-Madison, along with NASA's Power of 10: Rules for Developing Safety-Critical Code [1]. Storage faults and safety bugs, or the general lack of assertions in so many software projects, do indeed terrify us as a team!

It's also all credit to Coil's leadership, for caring and being willing to invest long term in better open source infrastructure for payments for everyone—and particularly Interledger, as an open interoperability protocol, to create an ”open network of networks” for payments, to fix the problem of payments for everyone [2].

I'm glad also to see that sibling comments have given tips on how to unblock that nightmare scenario you encountered!

[1] https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...

[2] http://interledger.org/

Thanks! Great to see that you're working on projects in Nim!

Thanks for a great question!

When we made the decision:

1. We were thinking long term. For example, a distributed database is a significant investment. I love the spirit and orthogonality of C, but we didn't want to pay the safety tax of C over the next 20 years. At the same time, Zig has that same spirit—it's not only a perfect replacement, but a leap forward in developer velocity, power, performance and ergonomics.

2. We realized that TigerBeetle would take 2 years to get to a production release. This meant that our timeline would intersect with Zig's stability—like skating to where the puck is going to be at, or catching the swell as it breaks, rather than riding out the last of an old wave. The number of surfers (quantity) was not a concern. Rather, we were impressed by the sheer quality and early maturity of Zig's compilation story, not to mention the quality of the Zig community in general. For example, it would be hard to find a better std lib crypto than what Zig already has right now, thanks to Frank Denis of libsodium.

3. The design of TigerBeetle is also a single-threaded control plane. We use io_uring for the data plane to eliminate multi-threaded context switches, so multi-threading for async I/O is less of a necessary evil than it used to be. All memory is statically allocated at startup. We never call free() so there are no UAFs. You can start to see why Rust's borrow checker made less sense for our domain than it would have for others. Of course, concurrency bugs can happen on a single thread, but we make use of other techniques to mitigate them.

4. We wanted the open source to be accessible to newcomers wanting to read or contribute to the project. We didn't want to pay the cost of a steep learning curve over the lifetime of the project. Zig turned out to be a hit here, as we've received feedback from engineers who've worked on Spanner or FoundationDB—remarking on Zig's readability, and this has proved to be a force multiplier, as they've come back again and again to the source, and even sent invaluable bug reports. For example, a bug that turned out to be in Apple's O_DSYNC, not even in TigerBeetle.

5. We do exhaustive fuzz testing and deterministic simulation testing from the inside out. See TigerBeetle's VOPR [1] for more details about our internal audit function.

6. We do exhaustive fuzz testing and deterministic simulation testing from the outside in. We're working with Will Wilson's new Antithesis startup https://antithesis.com to use their deterministic Linux hypervisor as our external audit function, to test our compiled TigerBeetle binaries in a deterministic cluster environment. This is different to Jepsen and more advanced in so many ways. For example, there's coverage guided fuzzing, and if we find any bugs, we can replay—again and again.

7. Finally, and most importantly, Andrew Kelley's design decisions, and Zig's approach to safety really resonated with us: no macros, no hidden control flow, no unused variables (this has caught several bugs for us already), checked arithmetic enabled by default in safe builds, spatial memory safety, out-of-memory safety, and explicit memory allocators—crucial since TigerBeetle does not do any dynamic memory allocation after startup. Zig is a superbly well-designed language. For example, Zig's comptime is immensely powerful.

If you're curious, we also speak to this as a team in the Q&A at the end of the Zig SHOWTIME talk [2] we did last year, and I go into this in detail in a talk I did at the Recurse center last month [3], also touching on why we picked VSR over RAFT or Paxos for the consensus protocol (that's a whole 'nother can of Paxos!). :)

P.S. We run a $20k bug bounty for our consensus code. If anyone can find a Zig bug that violates TigerBeetle's consensus or replication, then we have bounties up to $8192.

[1] https://github.com/coilhq/tigerbeetle#simulation-tests

[2] https://www.youtube.com/watch?v=BH2jvJ74npM

[3] https://www.youtube.com/watch?v=rNmZZLant9o

> By shifting business logic to stored procedures you avoid this.

Thanks, we considered stored procedures to bring the number of database queries down from 18 queries per payment to 1 query per payment. However, that would have provided only an order of magnitude improvement, and brought with it complexity of testing, compared to the state machine [1] we have in TigerBeetle.

At the same time, the biggest performance bottleneck is not only the number of roundtrips, but the lack of first-class batching in the interface per roundtrip. What we do in TigerBeetle instead, is we send 8192 transfers in a single network request. This brings the network/disk cost equation down from 1 query per payment, to 1/8192 query per payment. It's like group commit, on steroids.

[1] https://github.com/coilhq/tigerbeetle/blob/main/src/state_ma...

> That's also why SQLite is very fast, as it runs in your application's memory as a library. But then your data is tied to the same limitations as the machine the application is on.

SQLite is one of my favorite storage engines. However, SQLite does not solve our storage fault model. For example, misdirected reads/writes, lost reads/writes, bitrot in the middle of the committed log. SQLite was also not explicitly designed to be integrated with a global consensus protocol as per ”Protocol-Aware Recovery for Consensus-Based Storage” from UW-Madison. For example, there are optimizations around storage fault tolerance in the commit log that you can do, or around deterministic storage across replicas for faster distributed recovery, that you can't do with SQLite. Check out the paper [2] from UW-Madison for the details, which apply also to LevelDB and RocksDB. We wanted our engine also to be able to run in our deterministic simulator. For example, no random thread scheduling etc.

[2] https://www.usenix.org/conference/fast18/presentation/alagap...

I had the experience of being part of a team in 2020 doing performance and safety analysis on Mojaloop [1], the open-source payments switch. The emphasis was mostly on identifying performance bottlenecks. For example, graphing waterfalls of database queries, estimating expected vs actual concurrency, digging into latency spikes, surprising timeout interactions, and missed group commit opportunities.

However, on the safety front, one of the most challenging issues was guaranteeing the rollback of funds in the event of failure as part of the two-phase commit protocol for moving money—coordinating this across multiple SQL queries, database transactions, Kafka queues, even multiple code repositories, especially as different systems experience clock drift or as disks or machines fail.

You want to ensure that the money either moves, or doesn't move, that it doesn't get lost somewhere in between. Yet most payment systems re-implement all this business logic on an ad hoc basis, again and again.

We therefore extracted these primitives from Mojaloop “once and for all” to create TigerBeetle [2], an open-source financial accounting database, that provides multi-AZ replication, automated leader election, and two-phase payments out-of-the-box.

Moving this business logic to the financial database layer opened up three orders of magnitude more performance, with TigerBeetle able to process a million transactions a second, all with an extremely high safety standard. For example, we do FoundationDB-style deterministic simulation testing, but with automated storage fault injection, such as 30% corruption on all replicas including the leader. Design docs, and links to talks are all in the GitHub repo [2].

Happy to answer questions from our experience, or chat if you're working on similar systems!

[1] https://mojaloop.io

[2] https://github.com/coilhq/tigerbeetle (Zig)

Zig takes a different approach to safety. For example, Zig has checked arithmetic enabled by default in safe builds, can guarantee static allocation, and can recover from memory allocation failure. It depends on the definition of “safer software”, but for many domains where safety is a field [1], these are also important design decisions.

[1] https://spinroot.com/gerard/pdf/P10.pdf

It's a pleasure. Let me know if you have any more questions about TigerBeetle. Our design doc is also here: https://github.com/coilhq/tigerbeetle/blob/main/docs/DESIGN....

You can run it as a CLI directly on any ZIP file that you pass by path. I do want to port it to Zig though, to get rid of the NPM install bootstrapping, have a single binary, and also gain Zig's checked arithmetic and spatial safety.

What a surprise to open up HN today and see Pure staring back at me!

Here's the HN thread from 2019 where rattray encouraged me just to go for it and open-source the original JavaScript version: https://news.ycombinator.com/item?id=20352439

That led to a contract with Microsoft, which then led to my work at Coil on TigerBeetle, a distributed database written in Zig: https://www.youtube.com/watch?v=rNmZZLant9o

PDF is also a minefield, for how many ways there are to mess with the format: https://blog.didierstevens.com/2008/04/29/pdf-let-me-count-t...

Thanks for the link to that comment of mine. Wow, that's a blast from the past!

Here's also a recent HN discussion about Pure, in the context of buffer bleeds and memory safe languages, with tptacek: https://news.ycombinator.com/item?id=31852820