5. Transactions

distributedsystem/books/think-distributed-systems

1. Abstractions & The Power of Interfaces

Abstractions have the power to transform domains of discourse, reshaping entire operational environments by replacing complex, low-level interfaces with beautiful, high-level ones.

The Three Pillars of Abstraction (Abelson & Sussman, SICP):
1. Primitive expressions: The simplest entities of a language.
2. Means of combination: By which compound elements are built from simpler ones.
3. Means of abstraction: By which compound elements are named and manipulated as a single unit.
The Layering of “Beautiful” vs. “Ugly” Interfaces (Tanenbaum & Bos):
- Operating Systems: Consume the “ugly” physical layer (CPU, RAM, Disks) and present a beautiful interface (Processes, Memory, Files).
- Database Systems: Reject the OS interface as “ugly” and consume processes/files to present their own beautiful interface (Tables, Rows, Columns, and Transactions).
Agnostic vs. Aware Environments (Pat Helland):
- High-level concepts are agnostic (unaware of underlying complexities).
- Low-level concepts are aware (directly dealing with concurrency and physical constraints).
- The API acts as the translator, mapping agnostic concepts to aware environments.
Equivalence:
- Reduction (Top-down): High-level abstractions are reduced/compiled into low-level execution paths.
- Composition (Bottom-up): Low-level operations are composed to allow the high-level entity to emerge.
- Regardless of the perspective, the system guarantees semantic equivalence—returning the same output.

2. The Magic of Transactions

Transactions act as the ultimate developer experience (DX) benchmark by allowing developers to write code as if concurrency and failure do not exist.

The Problem of Concurrency (Race Conditions)

In a multi-user environment, updating an account balance consists of a read followed by a write. Concurrent execution of these operations can lead to interleaved states.

Example: If two concurrent transfers ( $t_{1}$ and $t_{2}$ ) of $10$ units occur on an account with an initial balance of $50$ , naive interleaving can result in a final balance of $40$ instead of the correct $30$ .

The Problem of Failure (Partial Application)

An operation involving multiple writes (e.g., transferring funds between two accounts) is inherently vulnerable to mid-sequence crashes.

Example: Debit occurs on the source account, but the system crashes before crediting the target account, leaving the system in an incomplete, inconsistent state.

The Transactional Solution

By enclosing operations within transactional boundaries (BEGIN ... COMMIT), the database system intercepts these race conditions and partial states, ensuring correctness and completeness without visible guardrails or explicit application-level failure detection.

3. The Model of Transactions

A transaction is a sequence of operations on a set of objects that ends with exactly one commit or exactly one abort.

ACID Characterization

Atomicity: Guarantees that a transaction executes as if it occurred completely or not at all.
Consistency: Guarantees that a transaction transitions the database from one valid state to another.
Isolation: Guarantees that concurrent transactions execute without cross-interference (traditionally via serializability).
Durability: Guarantees that committed changes are permanent and survive subsequent platform failures.

💡 Aha! Moment: Consistency is Distinct
Consistency is an application-level guarantee, whereas Atomicity, Isolation, and Durability are platform-level guarantees.

Example: A database column constraint checking balance >= 0 will cause the system to abort a transaction if a balance drops below zero. Without that constraint, a negative balance is structurally valid. The developer defines what constitutes a “consistent” state; the platform simply enforces AID to protect that definition.

Formal Design Time vs. Run Time Model

Design Time / Definition	Run Time / Execution
Program $P$	Transaction $t$
Operation $A$	Action $a$
Name $N$	Object $o$

Trace of a Transaction: Represented as a sequence of triples containing the transaction identifier, the action, and the target object:
$t_{x} = [⟨ t_{x}, a_{i}, o_{i} ⟩ ∣ i = 1 \dots n]$
Execution History: An interleaved sequence of multiple transaction traces:
$history = [⟨ t_{ij}, a_{i}, o_{i} ⟩ ∣ j = 1 \dots m, i = 1 \dots n]$

4. Correctness & Serializability

To ensure correctness under concurrent conditions, database systems rely on Serializability to define whether an interleaved history is valid.

Hoare Triples & Consistent Transitions

A transaction $t_{x}$ starting in a consistent state $C$ must output a consistent state $C$ :
${C} t_{x} {C}$

In a strictly sequential (non-concurrent) setting, transactions compose safely:
${C} t_{1} {C} \land {C} t_{2} {C} \Rightarrow {C} t_{1}; t_{2} {C}$

Serializability

A concurrent execution of transactions ( $t_{1} ∥ t_{2}$ ) is serializable if the resulting database state and transaction outcomes are equivalent to some serial execution ( $t_{1}; t_{2}$ or $t_{2}; t_{1}$ ):
${C} t_{1} ∥ t_{2} {C} \Rightarrow {C} t_{1}; t_{2} {C} \lor {C} t_{2}; t_{1} {C}$

Implementation: While implementing serializability naively is trivial (e.g., using a single global database lock), implementing it efficiently requires fine-grained locking of object subsets to maximize concurrent execution while enforcing sequential semantics.

5. Completeness & Failure Recovery (Undo Log)

To ensure completeness when failures occur, database systems use Backward Recovery (Undo) or Forward Recovery (Redo).

The Transaction Undo Log

For every active operation, an inverse “Undo” action is generated. The system records the Undo action in the Transaction Undo Log ( $o_{u}$ ) before the actual state-changing action is executed on the object.

Trace Scenarios:
- Commit Trace (No failure occurs):
  $t_{x} = [⟨ t_{x}, a_{i}, o_{i} ⟩ ∣ i = 1 \dots n]$
- Abort Trace (Failure occurs at step $k$ ):
  $t_{x} = [⟨ t_{x}, a_{i}, o_{i} ⟩ ∣ i = 1 \dots k] [⟨ t_{x}, \neg a_{i}, o_{i} ⟩ ∣ i = k \dots 1]$

Application-Level vs. Platform-Level Aborts

Application-Level Aborts: Triggered explicitly by code or implicitly by a database constraint violation. The system reads the active log and immediately applies the associated Undo actions.
Platform-Level Aborts: Occur when the system crashes mid-transaction. Upon restart, the database runs a recovery phase, scanning the Transaction Undo Log to identify all uncommitted transactions and executing their Undo operations.

Restartability of Undo Operations

Because crashes can happen during the recovery process itself, the act of applying Undo logs must be safe even if executed multiple times. Undo operations must satisfy two formal properties:

Noop (No-operation):
Applying an operation and immediately following it with its Undo operation must be equivalent to having only applied the Undo operation on the target state:
$⟨ t_{x}, a_{i}, o_{i} ⟩ ⟨ t_{x}, \neg a_{i}, o_{i} ⟩ = ⟨ t_{x}, \neg a_{i}, o_{i} ⟩$
Idempotence:
Applying an Undo operation multiple times must yield the exact same effect as applying it once:
$⟨ t_{x}, a_{i}, o_{i} ⟩ ⟨ t_{x}, \neg a_{i}, o_{i} ⟩ = ⟨ t_{x}, a_{i}, o_{i} ⟩ ⟨ t_{x}, \neg a_{i}, o_{i} ⟩ \dots ⟨ t_{x}, \neg a_{i}, o_{i} ⟩$

Nimendra's Notes 🪴

Explorer