Rediscovering Transaction Processing From History and First Principles

In July 2020, I stumbled into a fundamental limitation in the general-purpose database design for transaction processing.

This insight led to the creation of TigerBeetle, and attracted a special team who would engineer a financial transactions database from first principles and bring it to production.

Today, as we announce our Series A of $24 million, I want to tell you the story of how TigerBeetle came to solve this fundamental limitation, but first I want to take you back to the future of transaction processing.

What is a Transaction?

40 years ago, Turing Award-winner Jim Gray, who is regrettably no longer with us, wrote a paper that would be published as A Measure of Transaction Processing Power.

Jim Gray's paper was striking to me for three reasons.

First, he proposed a metric to evaluate the performance of Online Transaction Processing (OLTP) databases in terms of "Transactions per Second" (TPS).

We take the term "TPS" for granted today, but DeWitt (the researcher who benchmarked a certain database company) and Levine (who worked with Gray at Tandem), would recognize that:

“By specifying the key metric for evaluating the performance of database systems [..], Jim launched a benchmark war that drove the industry forward at a frantic pace for more than 15 years. At the time of the publication of this seminal paper, database systems that could deliver 100 transactions/second were considered state of the art. Obtaining 1000 transactions/second was viewed as unreachable.”

In fact, the benchmark war was so intense that it led to the formation of the Transaction Processing Performance Council (TPC).

But the second thing I appreciated was how Gray (like McSherry et al. with Scalability! But at what COST?) brought it all back to cost-efficiency, to tie TPS to cost, and benchmark the cost per transaction.

Before Gray, not only was there no "standard transaction" so that it was "difficult to verify or compare TPS claims", there was also "no accepted way to price a system supporting a desired TPS rate". And Gray emphasized that this cost has as much to do with hardware, as with developer productivity:

“One can implement [our benchmark] transaction in a day or two on some systems. On others it takes months to get started. There are huge differences in productivity between different systems. [..] We estimate the leanest-meanest system would require six months of expert time to get [our benchmark] operational.”

So Jim taught the industry to think not only about "performance", but crucially also "price/performance".

Beautifully simple in hindsight.

Jim Gray's contributions never cease to amaze me. Did you know that he helped coin the term ACID, gave us the 5-minute rule, and wrote the book on transaction processing?

And yet, what surprised me most, was how Gray defined "transaction"—the T in TPS—not as a SQL transaction (as we might assume), but rather as a business transaction derived from the real world.

Indeed, the OLTP benchmark that propelled the industry forward by an order of magnitude, and that gave rise to the TPC, would define "the standard measure of transaction processing" (Jim’s words 20 years later) as a "DebitCredit".

In other words, to use "a database system to debit a bank account, do the standard double-entry bookkeeping and then reply to the terminal":

The transaction as defined by Jim Gray in the "DebitCredit" benchmark, where TPS is "Peak DebitCredit transactions per second with 95% of the transactions having less than one second response time".

The Power of Simplicity

It’s worth noting that SQL had been around for 10 years by this point, and that Jim Gray had worked on System R, for which SQL was originally designed. And yet he chose debit/credit as the measure of transaction processing power:

“Most of us have spent our careers making high-function systems. It is painful to see a metric which rewards simplicity; simple systems are faster than fancy ones. [...] Surprisingly, these minimal requirements disqualify many purported transaction processing systems, but there is a very wide range of function and usability among the systems that have these minimal functions.”

So it wasn't that the SQL transaction didn't exist, but rather, that the debit/credit transaction was the textbook example of an everyday transaction; the reason for a database to provide guarantees such as atomicity, consistency, isolation and durability in the first place.

While SQL turns 50 this year, debit/credit has for centuries been the simple schema selected to represent the myriad of financial state transitions for any business, in any sector. If SQL is the language of databases, then to quote Warren Buffett, debit/credit is "the language of business". The essential "who", "what", "when", "where", "why" and "how much" to record the movement of anything of value, from one person or place to another.

The rigor of debit/credit is flexible, since the simplicity of debit/credit is composable. You can represent a universe of business. And indeed, you can think of debit/credit like the first law of thermodynamics:

Money cannot be created or destroyed, but is transferred from one account to another, so that the sum of all debits and the sum of all credits remains equal.

Nevertheless, you can imagine my surprise when I discovered the history of Jim Gray's DebitCredit benchmark for the first time last year.

I had already created TigerBeetle, and the set of developer primitives we chose to process transactions was designed around (you guessed it) debit/credit. Not because the pioneer of OLTP had picked debit/credit as the canonical transaction processing workload. But because we had stumbled into a fundamental limitation in the general-purpose database design.

A Fundamental Limitation

In 2020, I had been consulting on a central bank payments switch by the Bill and Melinda Gates Foundation. The switch was at heart a transaction system, but consisting of thousands of lines of complex code around a general-purpose database, to process debits and credits as money moved.

My job was to find the bottleneck. So we traced all the SQL queries processed by the general-purpose database as financial transactions were processed by the switch.

Immediately, we saw an impedance mismatch:

For each financial transaction, there would be 10-20 SQL queries back and forth across the network, while holding row locks.

For example, for one debit/credit, there might be:

1. a query to select the account balances from two rows,

2. locks held on these rows for the duration of the SQL transaction,

3. network traffic moving the data to the code in the application layer,

4. a decision outside the database on whether there was enough money,

5. more network traffic to write the new balances back to the database,

6. and finally, a write to record the debit/credit.

No matter how much hardware we gave the database, no matter how much money we spent, we couldn't improve throughput.

The limitation was fundamental:

A function of the concurrency control of the general-purpose database design: row locks interacting with the network round-trip time (RTT).

For example, if a debit/credit required a minimum of 2 network RTTs while holding locks, and with an RTT of 0.5ms, then other transactions would not be able to obtain the held locks for at least 1ms.

Worse, there are only 1000 milliseconds in a second, and if you look again at Gray’s benchmark, you will see that there is the concept of a "branch" account—a row touched by most transactions, since a bank (or business) may have ten million customers to debit, but only a few internal accounts to credit.

In other words, a large set of rows interacts with a small set of rows, with these hot rows locked in most transactions, serializing system performance, and reversing gains from horizontally scaled systems (in fact, rendering them cost-prohibitive!).

As Jim Gray understood 40 years ago, and as we learned, the OLTP workload is characterized by intrinsic contention.

For years, this fundamental limitation of the general-purpose database design to scale transaction processing had been latent. But as the world has become more transactional, the problem has become existential.

The World is Becoming More Transactional

In the last 7 years, instant payments in India increased by 7000x to 14 billion transactions per month, with these expected to triple in the next 3 years.

The trend is global, with Brazil's Pix replacing the country’s cash payments, with the introduction of FedNow in the US, and with transactions increasing also in other sectors:

• energy, as the world moves to clean energy and the supply of energy begins to follow the sun, energy providers want to arbitrage energy prices more frequently,

• gaming, as games become more connected with massively multiplayer in game economies, and

• cloud, as server prices move from monthly to per-second billing, and real time spend caps become a challenge.

In less than a decade, the world has become at least three orders of magnitude more transactional. And yet the three most popular general-purpose database designs, Postgres, MySQL and SQLite, while great for building apps, are 20-30 years old, designed for a different era of transaction processing.

Transaction Processing From First Principles

Therefore, we asked the question:

What if we could take the four primary colors of computer science (network, storage, memory and compute) and blend them from first principles into a transaction processing database for the future?

We saw that there were greater gains to be had than settling for a Postgres extension or stored procedures.

While we couldn’t completely eliminate network round-trips (i.e. embedding the database in a single application process would still have required replication and consensus for durability and availability)—we could amortize them and completely eliminate row locks.

With the insight that 1 debit/credit is 128 bytes, or 2 CPU cache lines of information:

We designed TigerBeetle to provide debit/credit as a first-class primitive, to pack up to 8000 debit/credits in a 1 MiB query, and so process up to 8000 transactions in a single round-trip to the database, without row locks.

By fixing the impedance mismatch, what before took at least 8000 SQL queries with a general-purpose database could now take 1 query with TigerBeetle.

This is the big 1000x performance idea in TigerBeetle. We did nothing special.

But this also solves cost-efficiency and developer productivity. TigerBeetle can power orders of magnitude more TPS with a fraction of the hardware, and with a richer set of primitives.

For example, to send a pending debit/credit to reserve funds, and then a debit/credit to post these funds, or else have TigerBeetle roll back the funds after a timeout. (TigerBeetle makes a perfect two-phase commit coordinator!).

Advancing Safety

Finally, much has changed in technology in the last thirty years. While Postgres, MySQL and SQLite are "tried and tested", this also means that some of the ways they can lose data are now known in the literature.

Therefore, beyond performance, there was the opportunity also to advance safety, which becomes crucial especially as scale increases.

We could tap into a rich reservoir of research to make TigerBeetle:

• one of the first databases to apply 2018 Protocol-Aware Recovery for storage fault-tolerance,

• one of the first to adapt NASA’s Power of Ten Rules for Safety-Critical Code, with static memory allocation and 6000+ assertions to verify correctness at runtime, and

• one of three (along with FoundationDB) to run in a deterministic simulator and apply model checking techniques—but on the actual code.

Back to the Future of Transaction Processing

The past four years of TigerBeetle have seen many highlights:

• The thrill of realizing that debit/credit could unlock orders of magnitude more performance.

• The magic of running TigerBeetle in a deterministic simulator—the velocity and quality we were able to achieve, to ship production in four years.

• The validation of our first customer, an energy provider transacting clean energy more efficiently.

• And of course, the joy of discovering that Jim Gray saw the future of transaction processing, long before we did.

Today, it is my great pleasure, as we look to serve the next thirty years of transaction processing, to welcome our long term partner Natalie Vais to the board, and to announce our $24 million Series A led by Spark Capital, with participation from Amplify Partners and Coil, as well as angels, including: Alex Gallego, Founder and CEO of Redpanda; Uriel Cohen, Co-Founder and Executive Chairman of Clear Street; Sachin Kumar, Co-Founder and CTO of Clear Street; and Alex Rattray, former Stripe, to whom we owe much gratitude.

Thanks to Hannes Mühleisen, Alex Petrov and Simon Eskildsen for reading drafts of this post.