Concurrency is a mechanism for maintaining atomicity and isolation when multiple transactions run concurrently in a database, two properties of ACID.
There are three main types of concurrency control technologies: Multi-Version Concurrency Control (MVCC), Strict Two-Phase Locking (S2PL), and Optimistic Concurrency Control (OCC). There are many variations of each technique. In MVCC, each write operation creates a new version of the data item, while retaining the old version. When a transaction reads a data item, one of the versions is selected to ensure the isolation of a single transaction. The main advantage of MVCC is that "the reader doesn't block the writer, and the writer doesn't block the reader", in contrast, for example, an S2PL-based system must block the reader when the writer writes to an item because the writer gets an exclusivity lock for the item. PostgreSQL and some RDBMS use a variant of MVCC, known as Snapshot Isolation (SI).
To achieve SI, some RDBMS (e.g., Oracle) use a rollback segment. When a new data item is written, the old version of the data item is written to the undo segment, and the new data item is subsequently overwritten into the data area. PostgreSQL uses a simpler approach. The new data item is inserted directly into the relevant table page. When an item is read, PostgreSQL responds to a single transaction by applying visibility check rules to select the appropriate version of the item.
The three exceptions defined in the ANSI SQL-92 standard are not allowed by SI: dirty reads, unrepeatable reads, and phantom reads. However, SI cannot be truly serializable because it allows serialization of exceptions such as write skew and read-only transaction skew. Note that the ANSI SQL-92 standard, which is based on the classical definition of serialisability, is not the same as the definition in the current theory. To resolve this issue, start with version 91 Serial Snapshot Isolation (SSI) has been added. SSI can detect serialization anomalies and can resolve conflicts caused by such anomalies. So, postgresql 9Version 1 or later provides a true serializable isolation level. (SQL Server also uses SSI; Oracle still only uses SI. ）
The level of transaction isolation in PostgreSQL.
The following table describes the level of transaction isolation implemented by PostgreSQL:
1: In version 90 and earlier, this level has been used as "serializable" because it does not allow the three exceptions defined in the ANSI SQL-92 standard. However, with version 9The implementation of SSI in 1, which has been changed to "repeatable read" and introduces a true serializable level.
Whenever a transaction starts, the transaction manager assigns a unique identifier called a transaction ID (txid). PostgreSQL's txid is a 32-bit unsigned integer, which is about 4.2 billion (ten million). If the built-in txid current() function is executed after the trade has started, the function will return the current txid as shown below:
testdb=# begin;begintestdb=# select txid_current();txid_current---825(1 row)0 means the txid is invalid.
1 indicates the bootstrap txid, which is used only when the database cluster is initialized.
2 indicates frozen txid.
Txids can be compared with each other. For example, from the perspective of txid 100, txid greater than 100 is "future" and is not visible from txid 100; Txids less than 100 are "past" and visible (Figure 1.)1 a））。
Figure 11 Transaction ID in PostgreSQL
Due to the lack of txid space in the actual system, PostgreSQL treats the txid space as a circle. The first 2.1 billion txids are "past" and the next 2.1 billion txids are "future" (Figure 1.)1 b）。
Note that the begin command does not assign txid. In PostgreSQL, when the first command is executed after the begin command is executed, the transaction manager allocates a tixd and the transaction starts.
There are two types of heap tuples in a table page: normal data tuples and toast tuples. This section describes only commonly used tuples.
The heap tuple consists of three parts: the heaptupleheaderdata structure, the null bitmap, and the user data (Figure 1.)2）。
The heaptupleheaderdata structure contains seven fields, but only four of them are required for subsequent sections:
t xmin holds the txid of the transaction into which the tuple is inserted. t xmax holds the txid of the transaction that deletes or updates this tuple. If this tuple is not deleted or updated, t xmax is set to 0, which means invalid. t cid holds the command id (cid), which is the number of sql commands executed before this command was executed within the current transaction, starting at 0. For example, let's say we execute three insert commands within a single transaction:'begin;insert;insert;insert;commit;'。If the first command inserts this tuple, the t cid is set to 0. If the second command inserts this tuple, the t cid is set to 1, and so on. t ctid holds a tuple identifier (TID) that points to itself or to a new tuple. TID, as described in section 3section, which identifies tuples in a table. When the tuple is updated, the t ctid of the tuple points to the new tuple; Otherwise, the t ctid points to itself.
1. Install testdb= create extension pageinspect; create extension2、 testdb= create table t1 as select * from (select row number() over() as row num,oid from pg class) t where rownum<2; select 13, TESTDB= select lp as tuple, t xmin, t xmax, t field3 as t cid, t ctidfrom heap page items(get raw page('t1', 0));tuple | t_xmin | t_xmax | t_cid | t_ctid---1 | 850 | 871 | 0 | 0,1)2 | 851 | 854 | 1 | 0,3)3 | 854 | 863 | 0 | 0,4)4 | 863 | 865 | 0 | 0,5)5 | 865 | 869 | 0 | 0,7)6 | 866 | 0 | 0 | 0,6)7 | 869 | 0 | 0 | 0,7)(7 rows)1. Query the PG attribute table to view the system columns added to the table, as well as the two column IDs and Name:
postgres=# select attname, format_type (atttypid,atttypmod) from pg_attributewhere attrelid = 'foo.bar'::regclass::oid order by attnum;attname | format_type---tableoid | oidcmax | cidxmax | xidcluster management techniquescmin | cidxmin | xidctid | tid id | integername | character varying(5) (8 rows)By explicitly querying the xmin, we can see the transaction ID of the inserted record by looking up the xmin value of each record. Note the xmin values for all records in the following logs:
We can also find its xmax by explicitly selecting each record. If xmax is 0, it was never deleted and is visible.
CMIN and CMAX Introduction CMIN: Insert a command identifier (starting from 0) in a transaction. cmax: deletes the command identifier in the transaction (starting from 0). CMIN and CMAX are both command IDs that represent tuples, that is, CMIN is the command ID that generates the tuple, and cmax is the command ID that deletes the tuple. cmin indicates the command ID of the inserted data, and cmax indicates the deletion of data. So how do you know if it's inserted or deleted by a field? To solve this problem, we need to understand the combo cid.
When only data is inserted in our transaction, the t cid stores the cmin, because only the cmin is valid at this time. When an update or delete operation is performed, cmax is generated. When there are both cmin and cmax, that is, when there are both inserts and updates in the same transaction, the t cid stores the combo cid, and when there are both inserts and updates in the transaction, the t cid stores the combo cid.
This section describes how to insert, delete, and update tuples. Then, briefly describe the Free Space Mapping (FSM) for inserting and updating tuples.
To focus on tuples, headers and line pointers are no longer represented below. Figure 3shows an example of how a tuple is represented.
Figure 1Representation of 3 tuples.
With the insert operation, a new tuple is inserted directly into a page of the target table (Figure 1).4）。
Figure 14 tuple insertion.
Let's say a transaction with a txid of 99 inserts a tuple into the page. At this point, the header field of the inserted tuple is set as follows.
Tuple 1: t xmin is set to 99 because the tuple is inserted by txid 99.
t xmax is set to 0 because the tuple has not been deleted or updated.
t cid is set to 0 because the tuple is the first tuple inserted by txid 99.
t ctid is set to (0,1) and it points to itself because this is the latest tuple.
During the delete operation, the target tuple is tombstoned. The value of the txid where the delete command is executed is set to the txmax of the tuple (Figure 1.)5）。
Figure 15。Tuple deletion.
Let's say tuple 1 is deleted by txid 111. At this point, the header field of tuple 1 is set as follows:
Tuple 1: T xmax is set to 111.
If txid 111 is committed, tuple 1 is no longer needed. In general, unwanted tuples are referred to as dead tuples in PostgreSQL.
Dead tuples should eventually be removed from the page. Cleaning up dead tuples is called vacuum processing, which will be described in Chapter 6.
In the update operation, PostgreSQL logically deletes the latest tuple and inserts a new tuple (Figure 1.)6）。
Figure 16 Update the line twice.
Let's say the line inserted by txid 99 is updated twice by txid 100.
When the first update command is executed, tombstone tuple 1 by setting t xmax to txid 100, and then insert tuple 2. The t ctid of tuple 1 is then rewritten to point to tuple 2. The header fields for tuple 1 and tuple 2 are as follows:
Tuple 1: t xmax is set to 100.
t ctid rewritten from (0, 1) to (0, 2).
Tuple 2: t xmin is set to 100.
t xmax is set to 0.
t cid is set to 0.
t ctid is set to (0,2).
When the second update command is executed, tuple 2 is tombstoned and tuple 3 is inserted as in the first update command. The header fields for tuple 2 and tuple 3 are as follows:
Tuple 2: T xmax is set to 100.
t ctid rewritten from (0, 2) to (0, 3).
Tuple 3: t xmin is set to 100.
t xmax is set to 0.
t cid is set to 1.
t ctid to (0,3).
As with the delete operation, if txid 100 is committed, tuple 1 and tuple 2 will become dead tuples, and if txid 100 is aborted, tuple 2 and tuple 3 will become dead tuples.
When inserting a heap or index tuple, PostgreSQL uses the FSM of the corresponding table or index to select the pages that can be inserted.
As stated in 12.As mentioned in Section 3, all tables and indexes have their own FSMs. Each FSM stores information about the amount of free space for each page in the corresponding table or index file.
All FSMs are stored with the "fsm" suffix, and if necessary, they are loaded into shared memory.
pg_freespacemap
The extended PG FreespaceMap provides free space for the specified table index. The following query shows the ratio of free space for each page in the specified table.
testdb=# create extension pg_freespacemap;create extensiontestdb=# select *,round(100 * ail/8192 ,2) as "freespace ratio"from pg_freespace('accounts'); blkno | ail | freespace ratio---0 | 7904 | 96.00 1 | 7520 | 91.00 2 | 7136 | 87.00 3 | 7136 | 87.00 4 | 7136 | 87.00 5 | 7136 | 87.00This section describes the status of transactions in PostgreSQL, how clogs are run, and how clogs are maintained.
PostgreSQL defines four transaction states: in progress, committed, aborted, and sub committed.
The first three states are self-explanatory. For example, when a transaction is in progress, its status is in progress.
Sub Committed is for sub-transactions, and its description is omitted from this document.
The clog consists of one or more 8 KB pages in shared memory. It logically forms an array where the indexes of the arrays correspond to their respective transaction IDs, and each item in the array holds the state of the corresponding transaction IDs. Figure 17 shows clog and how it works.
Figure 17 How clogging works.
t1: txid 200 commits; The status of txid 200 has changed from in progress to committed.
t2: txid 201 aborted; The status of txid 201 has changed from in progress to aborted.
When the current txid advances and the clog can no longer store it, a new page is appended.
When a transaction state is required, an intrinsic function is called. These functions read the clog and return the status of the requested transaction.
When the PostgreSQL service is shut down or the checkpointing process runs, the data for the clog is written to a file stored in the PG XACT subdirectory. (Note that PG XACT is at 9.)6 or earlier is called pg clog. These files are named etc. The maximum file size is 256 KB. For example, if a clog uses 8 pages (pages 1 to 8, with a total size of 64 kb), its data is written to 0000 (64 kb). If the clog uses 37 pages (296 kb), its data is written to 0000 and 0001, which are 256 kb and 40 kb in size, respectively.
When PostgreSQL starts, the data stored in the pg xact file is loaded to initialize the clog.
The size of the clog keeps increasing because new pages are attached whenever the clog is filled. However, not all data in the clog is required. Vacuum processing periodically deletes such old data (clog pages and files).
A transaction snapshot is a dataset that stores information about whether all transactions are active at a point in time for a single transaction. An active transaction here means that it is in progress or has not yet started.
The text representation format for the postgresql internally defined transaction snapshot is "100:100:". For example, "100:100:" means "txids less than 99 are inactive, and txids equal to or greater than 100 are active".
The built-in function pg current snapshot and its text representation format.
The function pg current snapshot shows a snapshot of the current transaction.
testdb=# select pg_current_snapshot();pg_current_snapshot---100:104:100,102(1 row)The earliest txid where xmin is still active): All older transactions will either be committed and visible, or rolled back and terminated.
xmax first txid that has not yet been allocated): All txids greater than or equal to that value have not been started at the time of the snapshot and are therefore not visible.
xip_list
List of Active Transaction IDs at snapshot): This list contains only the active transaction IDs between xmin and xmax.
For example, in the snapshot "100:104:100,102", xmin is "100", xmax is "104", and xip list is "100,102".
Here are two specific examples:
Figure 18 Example of a transaction snapshot representation.
The first example is "100:100:". Here's what the snapshot means (Figure 1.)8(a)）：
Txids equal to or less than 99 are not active because XMIN is 100.
Txids equal to or greater than 100 are active because xmax is 100.
The second example is "100:104:100,102". Here's what the snapshot means (Figure 1.)8(b)）：
Txids equal to or less than 99 are inactive.
Txids equal to or greater than 104 are active.
txid 100 and 102 are active because they are present in the xip list, while txid 101 and 103 are inactive.
Transaction snapshots are provided by the transaction manager. At the Read Committed isolation level, a snapshot is taken every time a SQL command is executed; Otherwise (repeatable read or serializable), the transaction only takes a snapshot when the first SQL command is executed. The transaction snapshot obtained is used for the visibility check of the tuple, which is shown in 1Section 7.
When a captured snapshot is used for visibility checks, the active transactions in the snapshot must be considered in progress, even if they are actually committed or aborted. This rule is important because it causes a difference in behavior between Read Committed and Repeatable Read (or Serializable). We refer to this rule repeatedly in the following sections.
For the remainder of this section, the transaction manager and transactions will use specific scenarios in Figure 19 to describe.
The transaction manager always saves information about the transactions that are currently running. Suppose three transactions are started one after the other, transaction A and transaction B are isolated at read committed, and transaction c is isolated at repeatable read.
t1：
transaction a starts and executes the first select command. When the first command is executed, transaction A requests the txid and snapshot at the current moment. In this case, the transaction manager allocates txid 200 and returns a transaction snapshot of "200:200:".
t2：
transaction b starts and executes the first select command. The transaction manager allocates txid 201 and returns a transaction snapshot "200:200:" because transaction A (txid 200) is in progress. Therefore, transaction A is not visible from transaction b.
t3：
transaction c starts and executes the first select command. The transaction manager allocates txid 202 and returns a snapshot of the transaction'200:200:', so transaction A and transaction B are not visible from transaction c.
t4：
transaction a has been committed. The transaction manager deletes information about the transaction.
t5：
Transaction B and Transaction C execute their respective select commands.
Transaction B requires a transaction snapshot because it is at the Read Committed level. In this case, Transaction B gets a new snapshot "201:201:" because Transaction A (txid 200) is committed. As a result, transaction A is no longer visible to transaction B. Transaction C doesn't require a transaction snapshot because it's at the repeatable read level and uses the snapshot it gets, which is "200:200:". As a result, transaction A is still invisible to transaction c.
A visibility check rule is a set of rules that use the tuple's t xmin and t xmax, clog, and the taken snapshot of the transaction to determine whether each tuple is visible or invisible. These rules are too complex to explain in detail. Therefore, this document shows the minimum rules required for subsequent descriptions. Below, we omit the rules related to subtransactions and ignore the discussion about t ctid, i.e., we don't consider updating tuples more than twice within a transaction.
The number of selected rules is ten, which can be divided into three cases.
Tuples with a t xmin status of aborted are always not visible (Rule 1) because the transaction into which the tuple was inserted has been aborted.
/* t_xmin status == aborted */rule 1: if t_xmin status is 'aborted' then return 'invisible' end if• rule 1: if status(t_xmin) = aborted ⇒ invisible
Tuples with a t xmin status of In Progress are inherently invisible (rules 3 and 4) except in one case.
/* t_xmin status == in_progress */if t_xmin status is 'in_progress' thenif t_xmin = current_txid thenrule 2: if t_xmax = invalid thenreturn 'visible'rule 3: else /* this tuple has been deleted or updated by the current transaction itself. */return 'invisible'end ifrule 4: else /* t_xmin ≠ current_txid */return 'invisible'end ifend ifIf t xmin is equal to the current txid (i.e., the tuple was inserted by the current transaction) and t xmax is not invalid, then the tuple is invisible because it has been updated or deleted by the current transaction (rule 3).
An anomaly is when the tuple is inserted into the current transaction and t xmax is invalid. In this case, the tuple must be visible to the current transaction (Rule 2) because this tuple is the tuple inserted by the current transaction itself.
rule 2: if status(t_xmin) = in_progress ∧ t_xmin = current_txid ∧ t_xmax = invaild ⇒ visible
rule 3: if status(t_xmin) = in_progress ∧ t_xmin = current_txid ∧ t_xmax ≠ invaild ⇒ invisible
rule 4: if status(t_xmin) = in_progress ∧ t_xmin ≠ current_txid ⇒ invisible
Tuples with a t xmin status of committed are visible (rules 6,8, and 9), with the following three exceptions.
/* t_xmin status == committed */if t_xmin status is 'committed' thenrule 5: if t_xmin is active in the obtained transaction snapshot thenreturn 'invisible'rule 6: else if t_xmax = invalid or status of t_xmax is 'aborted' thenreturn 'visible'else if t_xmax status is 'in_progress' thenrule 7: if t_xmax = current_txid thenreturn 'invisible'rule 8: else /* t_xmax ≠ current_txid */return 'visible'end ifelse if t_xmax status is 'committed' thenrule 9: if t_xmax is active in the obtained transaction snapshot thenreturn 'visible'rule 10: elsereturn 'invisible'end ifend ifend ifThe first exception is when t xmin is active in the snapshot of the transaction taken (Rule 5). In this case, the tuple is not visible, as t xmin should be considered in progress.
The second exception is if t xmax is the current txid (rule 7). In this case, as with Rule 3, the tuple is not visible because it has been updated or deleted by the transaction itself.
Conversely, if t xmax has a status of in progress and t xmax is not the current txid (rule 8), the tuple is visible because it has not been deleted.
The third exception is when t xmax has a state of committed and t xmax is inactive in the taken transaction snapshot (Rule 10). In this case, the tuple is not visible because it has been updated or deleted by another transaction.
Conversely, if t xmax has a state of committed, but t xmax is active in the taken snapshot of the transaction (Rule 9), the tuple is visible because t xmax should be considered in progress.
rule 5: if status(t_xmin) = committed ∧ snapshot(t_xmin) = active ⇒ invisible
rule 6: if status(t_xmin) = committed ∧ t_xmax = invalid ∨ status(t_xmax) = aborted) ⇒visible
rule 7: if status(t_xmin) = committed ∧ status(t_xmax) = in_progress ∧ t_xmax = current_txid ⇒ invisible
rule 8: if status(t_xmin) = committed ∧ status(t_xmax) = in_progress ∧ t_xmax ≠ current_txid ⇒ visible
rule 9: if status(t_xmin) = committed ∧ status(t_xmax) = committed ∧ snapshot(t_xmax) = active ⇒ visible
rule 10: if status(t_xmin) = committed ∧ status(t_xmax) = committed ∧ snapshot(t_xmax) ≠active ⇒ invisible
This section describes how PostgreSQL performs visibility checks, which is the process of selecting the appropriate version of a heap tuple for a given transaction. This section also describes how PostgreSQL protects against exceptions defined in the ANSI SQL-92 standard: dirty reads, repeatable reads, and phantom reads.
Figure 110 shows a scenario that depicts a visibility check.
Figure 110。Describe the scenario for the visibility check.
In Figure 1In the scenario shown in 10, the SQL commands are executed in the following sequence:
T1: Start trading (txid 200).
T2: Start trading (txid 201).
t3: Run the select command for txid 200 and 201.
T4: Run the update command for txid 200 and T5: run the select command for txid 200 and 201.
t6: Commit txid 200
t7: run the select command of txid 201.
To simplify the description, let's assume that there are only two transactions, txid 200 and 201. The isolation level for txid 200 is read committed, and the isolation level for txid 201 is read committed or repeatable read.
How we select command to perform visibility checks on each tuple.
select commands of t3:
At t3, there is only tuple 1 in table tbl and is visible according to rule 6. As a result, the select command in both transactions returns "jekyll".
rule6(tuple_1) ⇒status(t_xmin:199) = committed ∧ t_xmax = invalid ⇒ visible
testdb=# --txid 200testdb=# select * from tbl;name---jekyll(1 row)testdb=# --txid 201testdb=# select * from tbl;name---jekyll(1 row)rule7(tuple_1): status(t_xmin:199) = committed ∧ status(t_xmax:200) =in_progress ∧ t_xmax:200 = current_txid:200 ⇒ invisible
rule2(tuple_2): status(t_xmin:200) = in_progress ∧ t_xmin:200 =current_txid:200 ∧ t_xmax = invaild ⇒ visible
testdb=# --txid 200testdb=# select * from tbl;name---hyde(1 row)rule8(tuple_1): status(t_xmin:199) = committed ∧ status(t_xmax:200) = in_progress ∧ t_xmax:200 ≠ current_txid:201 ⇒ visible
rule4(tuple_2): status(t_xmin:200) = in_progress ∧ t_xmin:200 ≠ current_txid:201 ⇒ invisible
testdb=# --txid 201testdb=# select * from tbl;name---jekyll(1 row)select command of t7:
The following describes the behavior of t7's select command at two isolation levels.
When txid 201 is at the read committed level, txid 200 is considered committed because the transaction snapshot is "201:201:". Therefore, under Rule 10, tuple 1 is not visible, while under Rule 6, tuple 2 is visible. The select command returns "hyde".
rule10(tuple_1): status(t_xmin:199) = committed ∧ status(t_xmax:200) = committed ∧ snapshot(t_xmax:200) ≠active ⇒ invisible
rule6(tuple_2): status(t_xmin:200) = committed ∧ t_xmax = invalid ⇒ visible
testdb=# --txid 201 (read committed)testdb=# select * from tbl;name---hydeConversely, when txid 201 is at the repeatable read level, txid 200 must be treated as in progress because the transaction snapshot is "200:200:". Therefore, under Rule 9, Tuple 1 is visible, and under Rule 5, Tuple 2 is not. The select command returns "jekyll". Note that non-repeatable reads do not occur at the repeatable read (and serializable) level.
rule9(tuple_1): status(t_xmin:199) = committed ∧ status(t_xmax:200) = committed ∧ snapshot(t_xmax:200) = active ⇒ visible
rule5(tuple_2): status(t_xmin:200) = committed ∧ snapshot(t_xmin:200) = active ⇒ invisible、
testdb=# --txid 201 (repeatable read)testdb=# select * from tbl;name---jekyll(1 row)Suppose two transactions, i.e., tx a and tx b, are running at the same time. Their isolation levels are Read Committed and Repeatable Read, and their txid is 100 and 101, respectively. First, tx a inserts a tuple. Then, it's promised. The inserted tuple has a t xmin of 100. Next, tx b executes the select command; However, according to Rule 5, the tuple inserted by TX A is not visible. As a result, phantom readings do not occur.
rule5(new tuple): status(t_xmin:100) = committed ∧ snapshot(t_xmin:100) = active ⇒ invisible
Transaction A
testdb=# --tx_a: txid 100testdb=# start transactiontestdb-# isolation level read committed;start transactiontestdb=# insert tbl(id, data)values (1,'phantom');insert 1testdb=# commit;committestdb=# --tx_b: txid 101testdb=# start transactiontestdb-# isolation level repeatable read;start transactiontestdb=# select txid_current();txid_current---101(1 row)10testdb=# select * from tbl where id=1;id | data---0 rows)