Radical MVCC

MVCC is very common in RDBMS; however, most databases, while separating WAL and data pages, still modify data pages while processing writes. This often causes issues with rollbacks and with versioning. With regard to versioning, the problem looks as follows: as the page data is modified, it is usually versioned with a TXID (there is no CSN available yet), and TXIDs and CSNs (and it is CSNs which determine visibility order) are ordered differently. Our proposal is different and (as we feel) is rather radical. 

Radical MVCC Invariant 1: No page modifications until CSN is obtained

First of all, we absolutely do not modify data pages until the point when the transaction “wins” its CSN. 

Visibility of the transaction’s own modifications to itself is ensured by maintaining a write set (for example, a per-table map of PK->value), and interposing it over/merging it with the data read from the conceptually immutable pages.

Commit: Logically Committed vs Materialized

At the point of obtaining the CSN, the transaction becomes logically committed (~= ”irreversible unless we crash”, so it is distinct from “durable”, more on it below). 

After obtaining the CSN, further processing of the transaction is separated into two independent (and parallel) activities: (a) traditional writing to WAL followed by fsync(), and (b) a less traditional “materialization” phase. During “materialization”, data from the transaction’s write set is applied to data pages.

As soon as the bunch of CSNs becomes fully materialized, we "publish" the last-materialized-CSN (strictly speaking, the semantics is "last CSN guaranteed to be materialized"), and then it is this last-materialized-CSN which becomes a "base CSN" to be used as a snapshot for the new transactions.

Note that "logically committed" doesn't mean "Durable" (not yet); what it means is "it will become Durable unless we crash"; of course, to preserve Durability, the usual logic of delaying reply to the client until WAL write+fsync() is completed shall be applied; still, the rest of RDBMS machinery can continue running unimpeded.

Radical MVCC Invariant 2: CSN is the only versioning primitive

The main advantage of Radical MVCC is its visibility model: versions are ordered by CSN, and this CSN is the ONLY versioning primitive. This, in turn, radically simplifies (and therefore speeds up) the main reading path; now, version check can be implemented as one single SIMD-oriented search.

This makes versioning embarrassingly simple: “Give me the version with maximum CSN out of those whose CSN is ≤ my snapshot CSN”. And it can also be easily implemented in a cache-friendly and SIMD-friendly manner, with the whole version resolution taking only 1 cache miss and fewer than 20 CPU cycles on top of it in the optimistic case; for example, if all the versions happen to fit into one single ZMM register, we need something along the lines of VPBROADCASTQ + VPANDQ + another VPBROADCASTQ + VPCMPUQ + KMOVW + POPCNT + VPERMQ + VMOVQ. Look, ma, no loops! (for up to 7 versions, that is).

Coalescing of In-Memory Updates

One further refinement includes coalescing updates from different transactions; note that unlike usual write coalescing, which applies to disk writes, we’re speaking about coalescing in-memory updates.

Note that to maintain correctness, we cannot coalesce different versions of the row; what we're speaking about here is creating several versions in one single shot. Indeed, if there were 100 updates to the same "hot" page (which 100 updates can be spread across 100 transactions!), we can save ourselves the cost of traversing the B-tree to find this page 100 times. 

It is important to note that in-memory coalescing has a nice property of scaling better than linear (i.e., overhead reduces under load), which also means an ability to survive under 100% load for some time. Of course, this effect will be offset by other worse-than-linear phenomena which are always present in the real-world system, but it still remains a very useful property. 

Linearization Caveat

One caveat of this model is that its naive implementations may fail on linearizability (which is a stronger condition than simple serializability and even SSI). To deal with it, it is sufficient to delay responses to incoming transactions until both (a) WAL write + fsync() completes AND (b) the transaction is fully materialized (and its CSN becomes <= than "published" last-materialized-CSN). This, of course, creates additional pressure to “materialize” pages earlier, but in many high-load real-world cases, in-memory coalescing described above is still expected to save quite a bit of work; moreover, our observation about the sublinear scaling effect still stands.

Replay-Based Rebasing OCC (Re2OCC)

Classical OCC (we’re referring to Kung & Robinson as “classical”) is great for parallelization but involves a lot of wasted work in the case of conflicts. We’ll be presenting a “Replay-Based Rebasing OCC” (Re2OCC), which should greatly reduce the costs of recovery from conflicts; while rebasing is certainly not a novel concept for OCC, certain aspects of our implementation (in particular, using conflicting writing sets to augment previous results in the SQL context) are not so common. 

Classical OCC

If the kettle is full, let’s pour out the water to reduce the problem to a previously solved one: an empty kettle.

– Mathematical joke

Classical OCC consists of three phases: Read - Validation - Write. Here, the Validation Phase merely checks (using read/write sets of transaction T and transaction Tprev) whether they conflict. The output of the Validation Phase is simple yes/no: if the Validation Phase for transaction T is successful, the transaction T commits; if not, the transaction T is aborted and retried.

Our Take on Classical OCC over MVCC - PRe2OCC (Precursor for Re2OCC)

Specifying Classical OCC a bit further, we’ll consider a rather specific implementation of OCC over MVCC. 

Under PRe2OCC, there are multiple writing transactions running in parallel, one transaction per thread. Each transaction T effectively runs over an MVCC snapshot corresponding to the "last transaction committed before T starts (“last transaction committed” indicated by the largest CSN in existence, see below); let’s call it “base CSN”, or T.Tstart. When transaction T is about to finish, it enters the Validation Phase (which is based on (a) the read-set and write-set of transaction T, and (b) the write-set of transaction Tprev, which has already been published by Tprev, see below), and this validation has to be run over all transactions committed since T.Tstart, up to and including the last-committed transaction (which is a moving target, as other threads may commit while we’re validating). 

Whenever T is validated against all already-committed transactions, we can try obtaining a CSN for it; obtaining a CSN fixes global serialization order and effectively means committing (Writing, in terms of Kung&Robinson) the transaction. At the point of commit, we’re also publishing transaction T’s write set (technically, transaction T will write its write set to a shareable memory area earlier, and at the point of commit will simply issue a single CAS saying that new CSN=XYZ corresponds to a specific write-set pointer, which will also make the write set visible to the rest of the world). The key point here is that all the write sets are immutable after they’re published, so absolutely no synchronization is needed while traversing them. Note that from our current point of view, it doesn’t matter whether commit also immediately makes the committed transaction visible to the readers, or this visibility is delayed (for example, as described in Radical MVCC)

Note that in our PRe2OCC, we store write-sets as a literal list of affected PKs. On the other hand, we store read-sets not as a list of PKs we’ve read, but as a list of SQL-like predicates, along the lines of “SELECT * FROM TBL WHERE X=?“, or “SELECT * FROM TBL WHERE X < ? AND Y=?“. Note that a simple list of actually-read PKs is not sufficient to implement full-scale SERIALIZED/SSI isolation anyway, as SQL-like ranges are needed to prevent phantom reads. Therefore, we need SQL-like ranges for read sets anyway, but we don’t really need a literal list of PKs we have read. As a very nice side effect, it makes our read-sets very small in size (and for OLTP we’re dealing with, write-sets are naturally limited to at most a few thousand per transaction, too).

PRe2OCC is more specific than Kung & Robinson’s OCC, and is arguably quite hardware-friendly (when comparing to Hekaton’s model, we’d even go further and argue that PRe2OCC is both closer to Kung & Robinson’s OCC, and more hardware-friendly than Hekaton’s one). Still, conceptually it is pretty much a Classical OCC with some relatively minor clarifications/refinements. 

PRe2OCC Invariant

Probably the most important invariant of PRe2OCC is the following: 

Write-sets published at the point of obtaining CSNs are immutable and represent THE db history. Everything else is just views over this history.

This invariant also stands for Re2OCC and Re2OCC-SF described below.

Defining Replay-Based Rebasing OCC (Re2OCC)

When life gives you lemons, make lemonade

– proverb

Prerequisite for Re2OCC: we need write transactions to be One-Shot (non-conversational) Transactions, so they can be transparently restarted by the RDBMS itself. Note that read transactions can still be interactive. 

In Replay-based Rebasing OCC (Re2OCC), the same three phases remain, but the Validation Phase differs significantly from the classical one (effectively, it becomes a Validation+Rebasing Phase). The basic idea is that if we already know that we have an overlapping write-set in Tprev, then we can use this write-set (alongside the memoized results of T’s statements) to “rebase” memoized results after the intervening write-set is applied. 

During our Validation+Rebase, we’re still running through all transactions from T.Tstart+1 through the currently-last-committed one, still comparing the read/write sets of T and Tprev, and proceeding with commit/Write if no conflicts are found. However, in case of conflict (let’s name this conflict between two transactions a transaction-level conflict), our behavior changes drastically; specifically, in case of conflict we do NOT exit the Validation Phase; instead, we “rebase” the write-set of transaction T re-using (a) read-set and memoized-request-results of transaction T, and (b) write set of Tprev. 

To rebase the transaction, we simply re-run the same transaction from the very beginning; the transaction will issue the same requests - but this time, when performing the request (such as “SELECT AMOUNT FROM USERS WHERE USERID=?”), we will follow a different path. First of all, whenever facing such a request, we’ll check whether the result (which we memoized during the Read Phase) is still valid (i.e., whether specifically this result conflicts with any of Tprev’s writes). If no such statement-to-transaction conflict is detected (case A), we can and will reuse this memoized result. If statement-to-transaction conflict is detected, we will see if an updated result can be derived from memoized result plus TPrev’s write set (case B); in a surprisingly high number of cases, we can do it trivially (in particular, for the “SELECT AMOUNT” statement above, a TPrev’s update of the same row will show in its write set, so we’ll be able to satisfy the request right from the write set). And only in case C (when there is a statement-to-transaction conflict AND the result cannot be derived from a combination of memoized result + Tprev’s write set) will we have to rerun the request against the database pages, or resort to the classical “abort and retry” of the whole transaction. 

Note that case C is one point where combining Re2OCC with previously described Radical MVCC requires additional clarification: in Radical MVCC, we do not materialize pages until later, so naive reading of pages with newer CSN won’t work. However, we still can read pages from an older (already materialized) CSN, and apply all the write-sets on top of it (even with Radical MVCC, write-sets are published simultaneously with obtaining CSN per our description of PRe2OCC above). 

Note that regardless of the complexity of SQL involved, all the execution plans access pages only via point-reads and/or via range-scans, both of which allow applying write-sets on top using the very same interposing/merging logic as we already used in Radical MVCC. 

PRe2OCC vs Re2OCC - Flow
Radical MVCC and Replay-Based Rebasing OCC (Re2OCC) - Image 1

Advantage over Classical OCC / PRe2OCC

The advantage we get over classical OCC is significant: (i) we do NOT throw away all the work done by already-run statements within transaction T (throwing them away only when they’re affected by Tprev’s write set), and (ii) we DO reuse recently-updated data from Tprev’s write set (which is readily available and is very likely "hot" within CPU caches). 

Note that while the rebasing process described above guarantees that, by the time we end it, we get a valid set of writes that are valid “as if” T is executed after Tprev, at this point we may need to rebase against another transaction, Tprev2, and so on. Also, the rebasing process per se does not guarantee against starvation (at least in theory, new transactions can arrive faster than we’re able to validate them; proving otherwise would be next to impossible); see, however Re2OCC-SF variation below. 

One interesting property is that quite a few real-life cases can be resolved within Case A and Case B above, so that we’re essentially reusing information we already paid for. The write-set is something OCC traditionally treats as evidence that our work is obsolete; we're treating the very same write-set as the information needed to make that work current again.

Scenarios We Can Resolve within Case A and Case B

The fastest page access is the page access you don't perform.

– ‘No Bugs’ Bunny

It is important to note that with Re2OCC, many real-world scenarios will be resolved within Case A and Case B, which are extremely fast, as they need only very limited in size and very cache-friendly read/write sets of T and Tprev. Also, let’s note that the list of scenarios below is not exhaustive; they should be treated as just examples.

Point Overwrites

A surprising number of practically important scenarios will be resolved simply by reusing Tprev’s write set to satisfy point reads; examples of such scenarios include:

  • cases covered by Thomas Writer’s rule (“blind writes”)
  • “blind increments” (see e.g. TPC-C W_YTD and D_YTD)
  • “escrow locks”

It is important to note that we do NOT need to address these scenarios separately; rather, all of them (and most likely quite a few others) will be handled automagically as soon as we implement “point read accounting for Tprev’s write-set”. 

Phantom Invalidations

Rebasing Sets over Phantom Invalidations

Another example is a request such as “SELECT * FROM TBL WHERE FLD > ?”. Such a request (to satisfy SERIALIZABLE isolation level, prohibiting Phantom Reads) may be invalidated by Tprev inserting a new record satisfying the predicate. In this case, if the result is small enough to fit into memoization (which it should be for any sane OLTP), we can simply add a row from the Tprev write-set to the memoized result set from T. An interesting sub-case here is when we have “SELECT * FROM TBL WHERE FLD > ? ORDER BY FLD LIMIT 10”; in this scenario, we are able to rebase the set only if the intervening Tprev’s modification is insertion (or if we stored an extra row within the memoized result “just in case”).

Rebasing Aggregates over Phantom Invalidations

Another interesting example is when we have a request such as “SELECT MAX(FLD) FROM TBL WHERE OTHERFLD > ?”. As above, such a request may be invalidated by Tprev inserting a new record that satisfies the predicate. In this case, however, we may still rebase the result of this request merely from the memoized result of SELECT MAX() and the write-set of Tprev: due to the semantics of MAX(), the result of such a request is a maximum of (a) the memoized result of this request from T, and (b) the value of FLD of the inserted row from the write-set of Tprev. Let’s note that in other aggregate-related scenarios the handling may be value-dependent: for example, if we delete a row which satisfies the predicate for the same MAX() request, we can rebase without reading page data only if the current T’s memoized result is not equal to the value of FLD in the deleted row (which is indicated in the TPrev’s write-set). Let’s further note that for similar incremental handling of AVG(), we will probably need to memoize not just the returned value, but a pair of SUM() and COUNT(). On yet another note, it also applies to aggregates with a GROUP BY clause. 

Handling JOINs

Let’s consider “SELECT o.id, c.name FROM orders o JOIN customer c ON c.id = o.customer_id”, invalidated by Tprev updating customer.name for some specific customer_id. Here, there are two distinct cases: 

  • Tprev’s customer_id equals the customer_id in one of the rows of the memoized result of the request. In such a case, we return c.name from Tprev. 
  • Tprev’s customer_id does not match the customer_id in the memoized request result. In such a case, the result of the request stays unaffected.

Effectively, what we're doing is applying point-overwrite to JOIN; in a similar manner, the methods we described for phantom invalidations can be applied to JOINs as well. 

Differences from Existing Approaches

In OCC, there are quite a few approaches that refer to “rebasing” or “replay”/”retry”; those we were able to identify, and how do they differ:

  • Document-based and other non-SQL DBs, re-applying mutations to the documents or configurations, such as Google Firebase Firestore and Cisco NSO. This is an entirely different field with a very different setup and implications. 
  • Approaches effectively aiming for multi-master scenarios, such as sqlite3rebaser. Once again, the task definition and solutions are very different from our case.
  • Implementations that use pure automated replay without reusing previously obtained results; AFAWK (=As Far As We Know), TiDB uses such an approach. In contrast, we feel that reusing previously obtained results is crucial for reducing wasted work.
  • Schemas that rely on rebasing mathematically commutative operations; AFAWK, MDCC uses it. However, a lot of business logic is not mathematically commutative; even simple “escrow locks” should be identified in the logic as a separate step to apply this approach to them.
  • Approaches that do both replay and rebase, but do not use results from the conflicting write set to implement rebase (performing full-scale searches in main data instead); to the best of our knowledge, this is what experimental research DBs such as MV3C, Morty, and Minerva do. We feel that while this is the closest to our Re2OCC, our technique of using the data only from the write set (wherever possible) speeds things up significantly, especially for all-important simple conflicts (those covered by Case A and Case B), which cover many scenarios, including blind writes/increments and escrow locks. While our rebase is incremental, in most practical cases, we expect it to outperform full-scale search (especially when accounting for the fact that double- and triple-conflicts are exponentially rare). 
  • On the other hand, we can see Re2OCC as an Incremental View Maintenance (IVM) used to implement transaction repair/rebase.

Further Variation - Re2OCC-SF

One major problem with traditional OCC implementations is starvation: if (as in Classical OCC) we’re retrying transactions, one particularly long transaction which reads a lot of rows and then writes something has a high chance of conflicting with everything else and of being rejected over and over, causing so-called “starvation”. While Re2OCC, with its rebasing, drastically reduces the chances of it happening, it doesn’t provide formal guarantees against starvation. That’s why we designed Re2OCC-SF: a variation which is guaranteed to be starvation-free. Actually, it is very simple: if a transaction has gone over a certain threshold of missed CAS attempts (maybe a multiplier over the average number of such attempts out there) - it will impose a global lock. Fortunately, unlike Kung&Robinson, for Re2OCC-SF we don’t need to impose a lock on the transaction processing; rather, this lock of ours shall only need to prevent other transactions from obtaining their CSNs. This will guarantee progress for each individual transaction and, as a result, guarantee against each transaction starving, while allowing "blocked" transactions to run as long as possible.

As a further improvement, whenever we can prove that there exists a strict superset of all potential write-sets AND all potential read-sets of the transaction (which may be derivable from the one-shot transaction), then we can make the lock conditional: even if such a lock-with-read+write-set is in force, all the transactions whose write-sets don't conflict with the lock's read+write-set may still proceed, with a strict guarantee that our problematic transaction will not conflict with them and will therefore will be able to proceed.

On CSN CAS Becoming a Major Contention Point

Starting from PRe2OCC, we rely on a single CAS to obtain/allocate monotonic CSNs; while CSNs being monotonic is crucial at least for the WAL-based databases, it is possible to split generation of monotonic CSNs into several contested cache lines, reducing individual contention. The idea goes as follows:

  • what PRe2OCC/Re2OCC (as described above) does is effectively merge different competing transactions into an ordered stream;
  • now, we can say that we have several such independently ordered streams (created by PRe2OCC/Re2OCC), each such stream combining some of the transaction candidates into "meta-transactions". Each such meta-transaction creates a partial ordering within the global transaction space;
  • at this point, we have several meta-transactions, each of them containing one or more original user-level transactions. And we can use the same PRe2OCC/Re2OCC (with rebase, etc., if applicable) to resolve conflicts between meta-transactions and create a global order, assigning an individual CSN to each of the original transactions.

This will allow splitting one single contention point into several less contentious ones; note that in the extreme case, it can be generalized into a "pyramid" of threads processing transactions - meta-transactions - meta-meta-transactions - and so on, though the necessity of such a generic "pyramid" in real-life setups is unclear.

WIP: "Reverse Validation" and "Inserted CSNs"

When considering a pathological case of a transaction that calculates a certain app-level invariant (as in "calculate SHA-256 hash of the whole DB") and stores this invariant in a table, with this invariant being read very rarely, we came to the realization that this case, while being logically straightforward, is not handled properly by usual OCC+CSN logic. Indeed, such a pathological transaction will run enormously long, will repeatedly fail validation, and will be very expensive to rebase. OTOH, logically, it is very similar to an ordinary read transaction - if its write-set is (almost) never read, what's the difference if it is written?

This leads us to the following additional validation mechanism (kind of "reverse validation"): if a transaction is being validated, and (a) its write-set doesn't conflict with any of the already-committed write sets, and (b) its write-set doesn't conflict with any of the already-committed read-sets, then we can "insert" this transaction into already-existing CSN order (sic!), creating some kind of CSN like "123.1", meaning "a transaction right after CSN 123". The implementation mechanics are rather complicated (one implementation writes a special "reference CSN" into the CSN ledger, and there are severe materialization complications too), but overall, it looks perfectly logically consistent.

A still-open questions are a. "whether this additional complexity is worth the gains in such pathological cases", and "whether we can generalize it further to cover less pathological, i.e. more frequently used, aggregates".