The Escrow Transactional Method (1986)

Imagine that we have a database consisting of three integers x, y, and z, each representing some amount of money. And, imagine that we have the following transaction that transfers money from x and y to z, with the invariant that all three dollar amounts are nonnegative.

if x - 10 >= 0:
  x -= 10
else:
  abort

if y - 20 >= 0:
  y -= 20
else:
  abort

z += 30
commit

Now imagine that we want to run this transaction many times concurrently with itself. Using a standard two-phase locking approach, a transaction would lock x, then lock y, and then lock z. This locking would limit the throughput of the system because when one transaction has an exclusive lock on x, no other transaction can touch x.

Worse, this locking is not necessary. Instead of issuing reads and writes, transactions can issue reads, increments, and decrements. As long as a transaction can guarantee that executing its increments or decrements will not violate its invariants no matter which other transactions commit or abort, the increments and decrements can be executed in any order, and transactions can issue their increments and decrements without locking.

This is the main idea behind escrow transactions.

The General Escrow Transactional Method

Escrow transactions provide the following API:

IF ESCROW(field=<F>, quantity=<C>, test=<condition>):
  continue with normall processing
ELSE:
  perform exception handling such as abort

If quantity C can be subtracted from field F with the guarantee that condition will not be violated, then the ESCROW call returns true. Otherwise it returns false. The tricky bit is that other in-progress transactions may have incremented and decremented F, and we don’t know which of these transactions will commit and which will abort.

For example, imagine we want to issue a ESCROW(a, 10, a >= 0) command where a = 50 and where there are outstanding transactions with the following increments and decrements: +30, +10, -15, -10 and -20. If all of these increments and decrements commit, then we’re safe to subtract 10 from a. However, if all the increments abort and all the decrements commit, then we cannot subtract 10 from a while preserving our condition.

Internal Design for the Escrow Method

To implement escrow transactions, we store a logical field record with each field in our database. The logical field contains four things:

inf: the lowest possible value the field can take on given that some in-progress transactions abort and some commit
val: the value the field can take on given that all transactions commit.
sup: the highest possible value the field can take on given that some in-progress transactions abort and some commit.
timestamp: a unique monotonically increasing timestamp.

In addition, whenever a transaction issues an escrow request, it appends an escrow journal entry to the logical field and updates the INF, VAL, SUP, and TIMESTAMP fields accordingly. The journal entry includes:

the transaction id,
the pool (an unimportant detail),
the lower bound on the condition (e.g. x >= 10 has lower bound 10; x <= 10 has lower bound -infty),
the upper bound on the condition (e.g. x >= 10 has upper bound infty; x <= 10 has upper bound 10),
the amount escrowed, and
the amount used (an unimportant detail).

An escrow journal can be successfully appended only if performing the increment or decrement satisfies the condition and all the conditions in existing journal entries. This is best explained with the example below.

When a transaction commits or aborts, its journal entry is removed and the values of INF, VAL, SUP, and TIMESTAMP are updated accordingly.

An Example

Consider a field A that is initially equal to 100. We have the following logical field: Next, transaction 1 makes a ESCROW(A, 50, A >= 0) request. The request is granted, and we get the following logical field:

Next, transaction 2 makes a ESCROW(A, 50, A >= 20) request. The request is denied because decrementing 50 would take INF below 20.

Next, transaction 2 makes a ESCROW(A, 20, A >= 30) request. The request is granted, and we get the following logical field:

Next, transaction 1 makes a ESCROW(A, 20, A >= 0) request. The request is denied because decrementing 20 from A would violated transaction 2’s journal entry.

Next, transaction 3 makes a ESCROW(A, -30, A <= 200) request. The request is granted, and we get the following logical field: Then, transaction 1 commits: Transaction 2 commits: Transaction 3 commits:

Utility and Benefits of Escrow Transactions

Escrow transactions allow increment/decrement transactions to run with higher degrees of concurrency. This is particularly important if the fields being incremented and decremented are hot spots in an application.

Moreover, escrow transactions are guaranteed to never deadlock since escrow requests are non-blocking. It is possible to have an escrow request wait on other escrow requests, but deadlock detection becomes quite a bit more complicated.

Odds and Ends

This paper also discusses how to perform recovery for escrow transactions, but the details are left for future work. It also discusses an API to USE escrowed values, but the paper admits that this feature is not really necessary.