5 Transactions (67)

Transaction - A bounded sequence of operations that the system treats as one indivisible, all-or-nothing state change, with a clear commit or abort decision and no visible intermediate effects.

ACID (Atomicity, consistency, isolation, and durability)

5.1 Abstractions (68)

Abstraction can be identified as one of the three fundamental building blocks of computer programs:

Primitive expression - Simplest entities.
Means of Combination - Compound elements that are built from simpler elements.
Means of abstraction - Compounds are named and manipulated as a unit.

You can think of layers (using figure 5.1) to think about how abstraction can take an ugly layer and transform it into a beautiful layer. This doesn’t always mean how it looks it could be talking about hardware (ugly) into operating systems (beautiful).

Also bring to mind the idea that you can have Primitive layers that will be part of higher level abstraction or combinations.

Instead of beautiful and ugly you can use the terms agnostic and aware. Let’s look at figure 5.3 to see how we could see components and how we can use the vocab.

From a top-down perspective, we see a reduction. We start with an agnostic entity and reduce it 
into the specific aware components that must execute in order to realize that abstraction.

or

From a bottom-up perspective, we see a composition. We take multiple aware components and 
compose them into a single agnostic action that emerges at a higher level of abstraction.

5.2 The magic of transactions (70)

You might find yourself thinking that your web app is transactional (everything can be guaranteed) but with anything that is distributed you will find that nothing is guaranteed. Working with a a database and the CRUD that goes along with it you will get the feeling that everything is just action -> implementation -> end state.

Let’s take a look at the code that is written and debug what is truly transactional and what is obfuscated. The API endpoint /transfer accepts a post request, containing 3 params: source, target, amount.

app.post('/transfer', async (req, res) => {
  const { source, target, amount } = req.body;

  # No visible failure detection or mitigation.
  const query = `
    BEGIN;
      UPDATE accounts SET balance = balance $1 WHERE id = $2;
      UPDATE accounts SET balance = balance + $1 WHERE id = $3;
    COMMIT;`;

  await db.none(query, [amount, source, target]);

res.status(200).end();
});

As you can see there is 0 guardrails for this transaction. No checks to see if the user has the money. No checks for if the user is even in the data base.

5.2.1 Concurrency (70)

We talked about in earlier chapters that there will always be a race condition within a distributed system. You could have more than 1 app of service trying to take money from an account. If you are trying to have 10 units taken from an account at the same time and both see 50 as the start you will end up with 40 at the end of both transactions. Transaction say they guaranteed correctness but in this case the singular action as correct but the whole process wasn’t.

5.2.2 Failure (71)

Let’s go back to the transfer of units from one account to the next. If we were to try and first subtract money from one account and then add to an other we have some failure points that we need to think about.

End result of 50 -> 40 and 50 -> 60
What happens if nothing happens, not correct to the end result 50, 50
What happens if just the subtraction happens, not correct to the end result 40, 50  

5.3 The model of transactions (72)

A transaction is a sequence of operations on a set of objects that ends with exactly one commit or exactly one abort. A transaction guarantees both correctness and completeness. This is guarenteed by four fundamentals ACID.

ACID

¡ Atomicity guarantees that a transaction executes observably equivalent to completely or not at all.
¡ Consistency guarantees that a transaction transitions the database from one consistent state to another consistent state.
¡ Isolation guarantees that a transaction executes as though it is the only transaction executing, preventing interference.
¡ Durability guarantees that when a transaction commits, its effects are permanent, preventing it from going back on its word.

Quickly talking about consistency, this is an application level guarantee. As this can be set up requirements of the application. Thinking about theses to creations of tables.

CREATE TABLE accounts (
  ...
  balance INT
  ...
);

# and

CREATE TABLE accounts(
  ...
  balance INT CHECK(balance >= 0)
  ...
);

Both of these can have a consistent guarantee but only one will let the balance go below 0.

For the next purpose we will go beyond just thinking about a table as rows and columns and think of them as a collection of objects, each represented by a name-value pair. So in this sense a program is a a sequence of operations performed on a set of names.

Design time/definition	|	Run time/execution
__	__	__
Program P	|	Transaction t
Operation A	|	Action a
Name N	|	Object o

We model a transaction as a trace, which consists of a sequence of triples in the form of 
⟨tx, ai, oi⟩, where

¡ tx represents the transaction.
¡ ai represents the operation.
¡ oi represents the object modified by the operation.

The trace of a transaction tx can be expressed as tx = [⟨tx, ai, oi⟩ | i = 1 .. n]. The 
inclusion of the transaction tx in the triple allows us to analyze the interleaving of multiple
transactions.

The database may interleave the execution of two or more transactions. This 
execution of a set of transactions is referred to as a history. A history is denoted by this
sequence:

history = [⟨tij, ai, oi⟩ | j = 1 .. m, i = 1 .. n]

The database system translates the failure-agnostic definition into a failure-aware and
failure-tolerant execution to guarantee correctness and completeness (see figure 5.7).

5.3.1 Correctness (74)

So we need to talk about how a data base can take an agnostic and turn it into an aware while maintaining correctness. We might want to use a Hoare Triple which will state the precondition, transaction, and postcondition.

      { C } tₓ { C }

So if we were to have t1 and t2 that are transactions of the current state. We and we are in a nonconcurrent system we could say that t1 will go from consistent state to and consistent state, and the same could be said for t2. Therefore

      { C } t1 { C } ∧ { C } t2 { C } => { C } t1;t2 { C }

A history without concurrency, known as a serial history, does not exhibit concurrency anomalies

5.3.2 Serializability (75)

Serializability is a consistency model. A consistency model is a predicate on execution histories. Histories then are serializable if the exicution of t1, t2 is equivalent to either of the following:

¡ The sequential execution of t1 • t2
¡ The sequential execution of t2 • t1

5.3.3 Completeness (77)

Now we need to talk about completeness. In the earlier chapter we talked about the 2 strategies to deal with recovery: backward (undo) and forward (redo).

So in this case we have 2 valid traces for the transaction history. The one where everything goes to plan and then one where we tried and failed to execute the transaction. These 2 way are called:

¡ Commit trace is the execution that unfolds in the absence of failure, executing all
  regular operations:
      tx = [⟨tx, ai, oi⟩ | i = 1..n]
¡ Abort trace is the execution that unfolds in the presence of failure, executing some
  regular operations and their Undo operations, effectively restoring the system to
  its state before the transaction:
      tx = [⟨tx, ai, oi⟩ | i = 1..k] [⟨tx, ¬ai, oi⟩ | i = k..1]

Keep in mind that if we can define an application level abort we are usually fine, but a platform level abort might be more difficult as you might not know which component failed and what to undo at that point.

5.3.4 Application-level abort (77)

An application level abort occurs when a transaction is explicitly or implicitly aborted. This can be triggered in two ways:

explicitly - by triggering an abort command 
implicit - triggered by conditions such as a consistency violation triggers automatic termination.

5.3.5 Platform-level abort (78)

A platform-level abort occurs when a crash failure and subsequent restart occur at an arbitrary point during the execution of a transaction.

There is a problem here as recording the undo and performing the undo are not always going to get you to the original state of the system before the transaction. If you try for an undo before the action had taken place you will be performing the undo on the old state. There can also be crashes during the undo and might result in more than 1 undo.

Money not taken from an account but being “refunded” to make an account greater than it was before the error

Money taken from the account, and then having an error during the refund and more than the refund being added back.

To prevent these problems undo operations must be both idempotent and restartable (noop + idempotent)

¡ Noop (no operation)—Applying an operation and its corresponding Undo 
  operation on an object should be equivalent to applying the Undo operation only on
  the object:
      ⟨tx, ai, oi⟩ ⟨tx, ¬ai, oi⟩ = ⟨tx, ¬ai, oi⟩
¡ Idempotent—Applying an operation and its Undo operation multiple times should
  have the same effect as applying them once:
      ⟨tx, ai, oi⟩ ⟨tx, ¬ai, oi⟩ = ⟨tx, ai, oi⟩ ⟨tx, ¬ai, oi⟩ ... ⟨tx, ¬ai, oi⟩