This week, Alex Miller wrote a blog post titled Decomposing Transaction Systems. He approached explaining transactions from a new fresh angle, but one which immediately felt intuitive. Alex decomposed transaction into four steps:

Every transactional system does four things:

• It executes transactions.
• It orders transactions.
• It validates transactions.
• It persists transactions.

Alex gives examples how these steps map to both generic OCC and PCC systems, as well as examples of real-world systems like FoundationDB and Spanner.

Then, Mark Brooker, followed up with a post of his own about how these steps map to Aurora DSQL.

So I naturally thought to map them to Firebolt. We haven’t published in-depth technical articles about Firebolt transaction manager, but there is 10 minute video, where we describe how it works to CMU’s Database class.

So let’s go step by step

Executing a transaction means evaluating the body of the transaction to produce the intended reads and writes.

Firebolt execution happens in parallel across the nodes of Firebolt engine cluster. There is no coordination between nodes or between clusters at that stage. We use MVCC, so all the writes create new version of data which is invisible to other transactions.

Validating a transaction means enforcing concurrency control, or more rarely, domain-specific semantics.

Firebolt employs OCC and therefore validation happens after execution, when transaction is ready to commit. Default isolation level in Firebolt is Snapshot Isolation, which means that transaction manager needs to check for Write/Write conflicts, i.e. to check if the current transaction (the one about to commit) did not write to the same rows as transactions which were active when the current transaction started, but committed before. If such conflicts are detected, the current transaction is aborted. Note, that validation step happens independently without coordination with other transactions trying to commit.

Ordering a transaction means assigning the transaction some notion of a time at which it occurred. 

Persisting a transaction makes making it durable, generally to disk.

This is where Firebolt differs from classic OCC sequence of Execute -> Order -> Validate -> Persist. In Firebolt, Order and Validate are swapped, and Order happens together with Persist. After Validation step, Firebolt’s transaction manager will atomically pick the Log Sequence Number (LSN) to correspond to current transaction’s commit, and persist it in Write Ahead Log (WAL). But it also checks whether some other transaction managed to commit since validation was completed, because if it did - the validation step needs to be repeated. Think about it as Compare and Swap operation - transaction manager atomically assigns and writes new highest LSN, but only if it didn’t changed since the validation step.

Firebolt uses FoundationDB to store all of its metadata including the WAL. So the Order + Persist step is implemented as FoundationDB transaction to ensure atomicity. But also, once persisted, the WAL is automatically replicated just like any write into FoundationDB would.

In addition to that replication which is there to ensure durability, Firebolt also replicates WAL’s content into Kafka topics. This happens asynchronously, and is not part of transaction protocol, i.e. it is not needed for correctness, but it is a performance optimization technique - all of Firebolt compute engines subscribe to that Kafka topic, and see all changes, which allows them to do some prefetching and prepare for the new state of the system.

Additional note

Alex has the following note in his blog

MVCC databases may assign two versions: an initial read version, and a final commit version. In this case, we’re mainly focused on the specific point at which the commit version is chosen — the time at which the database claims all reads and writes occurred atomically.

This is exactly what’s happening in Firebolt’s implementation of MVCC. When transaction starts, it obtains from transaction manager LSN to be used for reads - which define the snapshot in Snapshot Isolation.

For read-only transactions, there is nothing else, as their commit is no-op. So read-only transactions only get Execute step - there is no Validate, Order or Persist steps.

The read-write transactions get LSN of commit during Order + Persist step described above.