[Summary] Chapter#05 "The Internals of PostgreSQL" Concurrency Control

Concurrency Control

Concurrency Control maintains atomicity and isolation.There are three concurrency control techniques:

• Multi-version Concurrency Control (MVCC)
• Strict Two-phase Locking (S2PL)
• Optimistic Concurrency Control (OCC)

If an MVCC transaction reads a data item, the system selects one of the versions to ensure isolation of the individual transaction. MVCC readers don’t block writers and writers don’t block readers. On the other hand in S2PL system block reader when writer writes an item because writer acquires lock for an item. PostgreSQL and RDBMS use a variation of MVCC called Snap Isolation(SI).
Implementation of SI and RDBMS use rollback segment and writing a new data item, the old version of item is written to the rollback segment and new item is overwritten to data area. New data is directly inserted into the relevant table page, and when reading items PostgreSQL selects the appropriate version of an item in response to an individual transaction.
Dirty reads, Non-repeatable Reads and Phantom Reads are prohibited by SI and SI cannot achieve true serializability because it allows serialisation anomalies, like write skew and read-only transaction skew. Serializable Snapshot Isolation can detect the serialisation anomalies and can resolve conflicts caused by such anomalies, and PostgreSQL provides Serialization Isolation level.

Transaction ID(txid):
PostgreSQL txid is 32 bits unsigned integer and it is provided unique when a transaction begins.

Tuple Structure:
Heap tuple in table pages are classified as a usual data tuple and Toast Tuple
A heap tuple comprises three parts: Heap tuple header data structure, Null bitmap and user data.
Heap tuple header data structure contain seven fields, four fields are required in the subsequent sections:

• t_xmin
• t_xmax
• t_cid
• t_citd

Inserting, Deleting and Updating Tuples:
Free space is used to insert and Update tuples.

Insertion:
With insertion operation, a new tuple is inserted directly into a pages of the target table.

Deletion:
In deletion operation, target tuple is deleted logically and the value of txid that executes delete command is set to t_xmax of the tuple.

Update:
In the update operation, PostgreSQL logical deletes the latest tuple and inserts new one.

Commit Log:
It is used to allocate the shared memory and is used throughout transaction processing and PostgreSQL holds the status of Commit Log. There are four transaction states:
IN_Progress, Committed, Aborted, ans Sub_Commited.
Sub_commited is a subtransaction.
Clog Comprise of 8kb pages in shared memory. Clog logically forms an array and corresponds to respective transaction ids and each item in the array holds the status of the corresponding transaction id.
Data of clog is written into files stored under the pg_xact subdirectory and files named 0000, 0001, and the max file size is 256 KB. The data continuously increases because a new page is appended whenever the clog is filled up.

Transaction Snapshot:
It stores information about activation of all transactions, active transaction means it is in progress or not yet started. The format for transaction snapshot is 100:100.

Visibility Check Rules:
Using t_xmin and t_xmax, determine each tuple whether it is a visible or invisible clog and obtain a transaction snapshot. Following the minimal rules required for the subsequent descriptions.

• Status of t_xmin is Aborted
• Status of t_xmin is In_Progress
• Status of t_xmin is Committed

Visibility check: **
**T1: Start transaction (txid 200)
T2: Start transaction (txid 201)
T3: Execute SELECT commands of txid 200 and 201
T4: Execute UPDATE command of txid 200
T5: Execute SELECT commands of txid 200 and 201
T6: Commit txid 200
T7: Execute SELECT command of txid 201

To simplify the description, assume that there are only two transactions, i.e. txid 200 and 201. The isolation level of txid 200 is READ COMMITTED, and the isolation level of txid 201 is either READ COMMITTED or REPEATABLE READ.

Phantom Reads in PostgreSQL’s Repeatable Read level
PostgreSQL implementation does not allow phantom reads and SI principle also does not allow.

Preventing Lost Updates:
It is also called ww-conflict, concurrent transactions update the same rows and it must be prevented in both the repeatable read and serializable levels.
When UPDATE command is executed, the function ExecUpdate is internally invoked.

Serializable Snapshot Isolation:
Following technical terms are used:

• Precedence Graph
• Serialisation Anomalies:

If a cycle that is generated with some conflicts is present in the precedence graph, there will be a serialisation anomaly.
Implementing SSI in PostgreSQL

PostgreSQL implemented many functions and data structures. Two data structures are used:
SIREAD Lock
Rw-conflict

False-positive Serialisation Anomalies:
Serializability of concurrent transactions is always fully guaranteed because false-negative serialisation anomalies are detected under some circumstances therefore users should keep this in mind when using Serializable mode.

Required Maintenance Processes:
Following concurrency control mechanism requirement:

• Remove dead tuples and index tuples that point to corresponding dead tuples
• Remove unnecessary parts of the clog
• Freeze old txids
• Update FSM, VM and the statistics

Freeze Processing:
In PostgreSQL, a frozen txid, which is a special reserved txid 2, is defined such that it is always older than all other txids. In other words, the frozen txid is always inactive and visible.

Reference