并發控制是多個事務在并發運作時，資料庫保證事務一緻性(Consistency)和隔離性(Isolation)的一種機制。主流商用關系資料庫使用的并發控制技術主要有三種：嚴格兩階段封鎖(S2PL)、多版本并發控制(MVCC)和樂觀并發控制(OCC)。
在工程實踐上，PostgreSQL使用了MVCC的一種變體快照隔離SI結合封鎖技術進行并發控制，本文介紹了鎖相關的部分理論以及PostgreSQL的工程實踐，最後結合案例對PostgreSQL的表級鎖和行級鎖進行了相關介紹。
一、相關理論
在開始之前，我們不妨考慮這麼一個問題：單純使用快照隔離是否可以實作并發控制？答案是肯定的。其中的一種解決方案，類似于ORM架構Hibernate樂觀鎖的機制，基于Tuple資料版本記錄實作。在PostgreSQL中，對于任一個tuple，xmin+xmax可以認為是該tuple的版本号，在不加鎖的情況下，事務Ti對本事務生成的tuple快照(與其他事務的tuple快照互相隔離)進行處理，在事務送出時判斷快照版本(xmin+xmax)與資料庫中該tuple的版本是否一緻，如涉及的所有tuple版本均與本地版本一緻則送出，否則整個事務復原。不過這種方法在沖突很多的情況下，出現沖突的并發事務會頻繁的復原，看起來機器資源使用率很高，但其實大多時間在做無用功(大量事務出現沖突而復原)，而且由于Tuple版本的判斷和事務真正完結之間有時間差，在這個時間差之間可能出現其他并發事務更新同一Tuple的現象(髒寫異象)。為了避免這種頻繁復原的情況，PostgreSQL使用了相對“悲觀”的政策，通過封鎖技術對相同的資源(relation、page、tuple等)進行鎖定，在處理過程中判斷并等待而非不是延遲至事務送出時才進行判斷。
基于資料庫對象的多層次邏輯結構，PostgreSQL使用的是一種多粒度的封鎖機制，下面從理論層面簡單作一介紹。
1、資料庫對象邏輯結構
大凡資料庫的體系結構都會提到對象邏輯結構，就PostgreSQL而言，其邏輯對象體系結構如下圖所示：
資料庫對象層次結構
從封鎖的角度來看，在層次“關系”以下，關系(relation)是最大的可封鎖資料元素(Data Item)，每個關系由一個或多個頁(Page)組成，每個頁保護一個或多個元組(Tuple)。
2、多粒度鎖機制
按上一節介紹的對象邏輯層次結構，我們可以相應的指定意向鎖協定，該協定既包括“普通”鎖(即讀S鎖和寫X鎖)又包括“意向”鎖(以I開頭，IS表示意向共享鎖，IX表示意向排他鎖)，規則如下：
1.在任何資料元素上加鎖(S或X鎖)，必須從層次結構的根開始；
2.如已處于将要封鎖的元素位置，則不需要進一步查找，直接在資料元素上加S或X鎖；
3.如将要封鎖的元素在目前層次之下，則在目前節點加意向鎖(如IS或者IX鎖)，目前節點上的鎖被授予後才能繼續往下查找子節點。重複2和3直至找到滿足條件的節點。
下面是S、X、IS和IX之間的相容性矩陣：
IS
IX
S
X
IS
Y
Y
Y
N
IX
Y
Y
N
N
S
Y
N
Y
N
X
N
N
N
N
從相容性矩陣可以看出，IS除了X外，可與其他鎖相容；IX除了S和X外，可與其他意向鎖相容；S除了IS和S(自相容)外，與IX和X都不相容；X則與其他所有鎖均不相容。
上面介紹了意向鎖協定，我們不禁要問的一個問題是：為什麼要引入意向鎖？
考慮以下情況，事務Ti修改關系R中的某個元組y，無疑我們需要在y上加X鎖，但在R上需要加鎖嗎？如果不加鎖，這時候另外一個并發事務Tj需要在關系上建立索引(顯然，需要在關系上加S鎖)，那麼Tj可以直接在關系加鎖或者需要在元組層次上判斷關系R的元組是否存在S鎖和X鎖，無異增加判斷的複雜度和代價。從性能和可維護性上考慮，希望直接在關系這個層次上判斷是否可以對整個關系加S鎖，我們是以引入意向鎖。就上例而言，事務Ti在關系R上加意向排他鎖(IX)，在元組y上加X鎖，然後并發事務Tj期望擷取R上的S鎖，從相容性矩陣可得，S與IX不相容，Tj必須等待。可以看到，在同一個層次上執行封鎖判斷邏輯，顯得高效且十分簡潔。除此之外，引入意向鎖還有助于并發事務在更低層次(粒度)上解決沖突，進而有效的提高系統的并發，提升系統性能。
值得一提的是，除了IS和IX，還有一種意向鎖SIX，也就是共享意向寫鎖(Share + IX)。在事務需要通路整個關系但隻需要寫關系中的部分資料元素時在關系上加該鎖。
3、兩階段鎖(2PL)
兩階段鎖(2PL)，簡單來說就是把鎖操作分為兩個階段：加鎖和解鎖，且要求在加鎖階段不允許解鎖，在解鎖階段不允許再加鎖。工程實踐中，實際使用的是強嚴格兩階段鎖(SS2PL，一般稱為S2PL)，在2PL的基礎上要求在事務結束後才解鎖。
使用兩階段鎖協定的并發控制産生可串行的排程。下面是簡單的證明：
不失一般性，考察以下遵循兩階段鎖協定但不可串行化(形成環)的排程：T1->T2->...->Tn->T1。
T1->T2表示在排程中T1有操作與T2的操作相沖突，因為沖突，是以T1必須釋放鎖，T2獲得鎖才能繼續執行。以此類推，T2和T3類似，...，Tn-1和Tn類似，Tn和T1類似，由此可以得出結論：T1釋放鎖之後，又擷取了另外一個鎖，否則Tn->T1不應存在，這違反了兩階段鎖協定。是以，遵循兩階段鎖協定的排程不可能出現環，由此可證明遵循兩階段鎖協定是可串行化的。
在商用資料庫中，Informix是使用S2PL的代表，而PostgreSQL則在執行DDL(如drop table等)時使用S2PL，而DML時使用SI。
二、PostgreSQL中的表級鎖和行級鎖
基于上面介紹的理論基礎，了解PostgreSQL中的鎖相對容易一些(Oracle、MySQL同理)。
1、表級鎖
PostgreSQL表級鎖包括：Access Share(AS)、Row Share(RS)、Row Exclusive(RE)、Share Update Exclusive(SUE)、Share(S)、Share Row Exclusive(SRE)、Exclusive(E)、Access Exclusive(AE)，共8種類型的表級鎖，初學者看到這麼鎖估計會發懵，但如果我們結合上一節的多粒度鎖機制來了解相對比較容易。
從兩個次元來看：粒度和操作。粒度分為Relation和Row，操作分為讀(Share)、寫(Exclusive)和讀寫(Share Exclusive)，根據這兩個次元得到下面的矩陣：
Row
Relation
讀
Row Share
Access Share、Share
寫
Row Exclusive
Exclusive、Access Exclusive
讀寫
Share Update Exclusive、Share Row Exclusive
這些鎖中，Row Share和Row Exclusive可視為意向鎖：真正需要鎖定的資料項是元組而非關系，如出現沖突則留待元組級解決。除此之外，其他均為普通鎖：鎖定的資料項是關系，且無需在行上加鎖。
上述八種鎖的相容性矩陣如下表所示：
模式
Access Share
Row Share
Row Exclusive
Share Update Exclusive
Share
Share Row Exclusive
Exclusive
Access Exclusive
樣例SQL
Access Share
Y
Y
Y
Y
Y
Y
Y
N
Select
Row Share
Y
Y
Y
Y
Y
Y
N
N
Select for Update/Share
Row Exclusive
Y
Y
Y
Y
N
N
N
N
Insert/Update/Delete
Share Update Exclusive
Y
Y
Y
N
N
N
N
N
Vacuum,Alter Table,Create Index Concurrently
Share
Y
Y
N
N
N
N
N
Create Index
Share Row Exclusive
Y
Y
N
N
N
N
N
N
Create Trigger,Alter Table
Exclusive
Y
N
N
N
N
N
N
N
Refresh Material View Concurrently
Access Exclusive
N
N
N
N
N
N
N
N
Drop/Truncate/...
上一節提到，PostgreSQL在執行DDL時使用S2PL，在執行DML時使用SI，為了區分，PostgreSQL在執行DDL時關系上的鎖是Access Exclusive而不是Exclusive，在執行DML查詢語句時關系上的鎖是Access Share而不是Share，從相容性矩陣可以看出，這樣的區分可以實作在寫(Row Exclusive)的時候不會阻塞多版本讀(Access Share)，多版本讀(Access Share)的時候不會阻塞寫(Row Exclusive)。
而傳統意義上的讀鎖(Share Lock)，在PostgreSQL中用于Create Index，排斥所有含有Exclusive的寫鎖，但不排斥其他讀鎖(Share Lock)，意味着建立索引時不可以修改資料，但允許查詢資料或者同時建立其他索引；正常意義上的寫鎖Exclusive，用于物化視圖的并發重新整理，會排斥除多版本讀外的其他所有鎖。
小結一下，在PostgreSQL中：
1.多版本讀鎖和寫鎖-2類：Access Share和Access Exclusive
2.意向鎖-2類：Row Share和Row Exclusive，它們之間的差異在于Row Share排斥僅表級的Exclusive&Access Exclusive，其他相容鎖如出現沖突則在行級解決
3.共享鎖-3類：細分為Share Update Exclusive、Share、Share Row Exclusive，目的是為了不同的SQL指令精細化控制鎖，提高系統并發
4.傳統寫鎖-1類：Exclusive，僅用于物化視圖重新整理
2、行級鎖
PostgreSQL的行級鎖有4個，從兩個次元來看：主(唯一)鍵相關和模式(排他和共享)，見下面的矩陣：
主鍵相關
主鍵無關
排他
FOR UPDATE
FOR NO KEY UPDATE
共享
FOR KEY SHARE
FOR SHARE
排他模式
FOR UPDATE：對整行進行更新，包括删除行
FOR NO KEY UPDATE：對除主(唯一)鍵外的字段更新
共享模式
FOR SHARE：讀該行，不允許對行進行更新
FOR KEY SHARE：讀該行的鍵值，但允許對除鍵外的其他字段更新。在外鍵檢查時使用該鎖
值得一提的是，PostgreSQL的行級鎖并沒有在記憶體中存儲而是使用了元組Header的标記位存儲(相應的資料結構是HeapTupleHeaderData)，是以理論上PostgreSQL可以支援無限多的元組鎖。
//t_infomask說明
1 #define HEAP_HASNULL 0x0001
10 #define HEAP_HASVARWIDTH 0x0002
100 #define HEAP_HASEXTERNAL 0x0004
1000 #define HEAP_HASOID 0x0008
10000 #define HEAP_XMAX_KEYSHR_LOCK 0x0010
100000 #define HEAP_COMBOCID 0x0020
1000000 #define HEAP_XMAX_EXCL_LOCK 0x0040
10000000 #define HEAP_XMAX_LOCK_ONLY 0x0080
#define HEAP_XMAX_SHR_LOCK (HEAP_XMAX_EXCL_LOCK | HEAP_XMAX_KEYSHR_LOCK)
#define HEAP_LOCK_MASK (HEAP_XMAX_SHR_LOCK | HEAP_XMAX_EXCL_LOCK | \
HEAP_XMAX_KEYSHR_LOCK)
100000000 #define HEAP_XMIN_COMMITTED 0x0100
1000000000 #define HEAP_XMIN_INVALID 0x0200
#define HEAP_XMIN_FROZEN (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
10000000000 #define HEAP_XMAX_COMMITTED 0x0400
100000000000 #define HEAP_XMAX_INVALID 0x0800
1000000000000 #define HEAP_XMAX_IS_MULTI 0x1000
10000000000000 #define HEAP_UPDATED 0x2000
100000000000000 #define HEAP_MOVED_OFF 0x4000
1000000000000000 #define HEAP_MOVED_IN 0x8000
#define HEAP_MOVED (HEAP_MOVED_OFF | HEAP_MOVED_IN)
1111111111110000 #define HEAP_XACT_MASK 0xFFF0
//t_infomask2說明
11111111111 #define HEAP_NATTS_MASK 0x07FF
10000000000000 #define HEAP_KEYS_UPDATED 0x2000
100000000000000 #define HEAP_HOT_UPDATED 0x4000
1000000000000000 #define HEAP_ONLY_TUPLE 0x8000
1110000000000000 #define HEAP2_XACT_MASK 0xE000
1111111111111110 #define SpecTokenOffsetNumber 0xfffe
3、案例研究
下面通過一個案例來對表級鎖和行級鎖作進一步的闡述，以便有直覺的感受。
該案例建立一張表，插入10,000行資料，然後啟動3個會話，同時對該表執行更新操作。
drop table lockdemo;
create table lockdemo(id int,c1 varchar);
insert into lockdemo(id,c1) select x,'c1'||x from generate_series(1,10000) as x;
根據資料結構HeapTupleHeaderData的描述，使用插件pageinspect dump元組資訊查詢行鎖。
drop function get_tuple_locks;
create or replace function get_tuple_locks(pi_name in varchar)
returns setof record as $$
SELECT '(0,'||lp||')' AS ctid, -- tuple ctid
t_xmax as xmax, -- xmax
CASE WHEN (t_infomask & 128) > 0 THEN 't' END AS lock_only, -- 0x0080，HEAP_XMAX_LOCK_ONLY
CASE WHEN (t_infomask & 4096) > 0 THEN 't' END AS is_multi, -- 0x1000，HEAP_XMAX_IS_MULTI
CASE WHEN (t_infomask2 & 8192) > 0 THEN 't' END AS keys_upd, -- 0x2000，HEAP_KEYS_UPDATED
CASE WHEN (t_infomask & 16) > 0 THEN 't' END AS keyshr_lock, -- 0x0010，HEAP_XMAX_KEYSHR_LOCK
CASE WHEN (t_infomask & 16+64) = 16+64 THEN 't' END AS shr_lock -- 0x0010 & 0x0040，HEAP_XMAX_SHR_LOCK = HEAP_XMAX_KEYSHR_LOCK | HEAP_XMAX_EXCL_LOCK
FROM heap_page_items(get_raw_page(pi_name,0))
ORDER BY lp;
$$
language sql;
另外，PostgreSQL提供了pgrowlocks插件用于查詢行級鎖。
create extension pgrowlocks;
我們先啟動兩個session，其中session 1先執行更新lockdemo的c1字段，随後session 2執行同樣的更新SQL
session 1
[local:/opt/data5012]:5012 [email protected]=# select pg_backend_pid();
pg_backend_pid
----------------
1714
(1 row)
Time: 2.994 ms
[local:/opt/data5012]:5012 [email protected]=# begin;
BEGIN
Time: 0.154 ms
[local:/opt/data5012]:5012 [email protected]=#* update lockdemo set c1 = 'x';
UPDATE 10000
Time: 15.786 ms
[local:/opt/data5012]:5012 [email protected]=#*
[local:/opt/data5012]:5012 [email protected]=#* select txid_current();
txid_current
--------------
529
(1 row)
Time: 2.916 ms
session 2
[local:/opt/data5012]:5012 [email protected]=# select pg_backend_pid();
pg_backend_pid
----------------
1712
(1 row)
Time: 0.616 ms
[local:/opt/data5012]:5012 [email protected]=# begin;
BEGIN
Time: 0.310 ms
[local:/opt/data5012]:5012 [email protected]=#* update lockdemo set c1 = 'y';
查詢session 1和2的鎖資訊
-- session 1
[local:/opt/data5012]:5012 [email protected]=# select pid,locktype,relation::regclass,page,tuple,transactionid,mode,granted,fastpath from pg_locks where pid = 1714;
pid | locktype | relation | page | tuple | transactionid | mode | granted | fastpath
------+---------------+----------+------+-------+---------------+------------------+---------+----------
1714 | relation | lockdemo | | | | RowExclusiveLock | t | t
1714 | virtualxid | | | | | ExclusiveLock | t | t
1714 | transactionid | | | | 529 | ExclusiveLock | t | f
(3 rows)
Time: 5.251 ms
-- session 2
[local:/opt/data5012]:5012 [email protected]=# select pid,locktype,relation::regclass,page,tuple,transactionid,mode,granted,fastpath from pg_locks where pid = 1712;
pid | locktype | relation | page | tuple | transactionid | mode | granted | fastpath
------+---------------+----------+------+-------+---------------+------------------+---------+----------
1712 | relation | lockdemo | | | | RowExclusiveLock | t | t
1712 | virtualxid | | | | | ExclusiveLock | t | t
1712 | transactionid | | | | 529 | ShareLock | f | f
1712 | tuple | lockdemo | 0 | 1 | | ExclusiveLock | t | f
1712 | transactionid | | | | 531 | ExclusiveLock | t | f
(5 rows)
Time: 0.797 ms
[local:/opt/data5012]:5012 [email protected]=#
可以看到，session 1持有lockdemo的RowExclusiveLock意向鎖，該鎖不會阻塞session 2持有同樣的RowExclusiveLock鎖，同時session 1持有事務ID 529的排他鎖。session 2持有lockdemo的RowExclusiveLock意向鎖，并且持有lockdemo上的"排他行級鎖"(page = 0，tuple = 1)，同時期望擷取事務529的共享鎖，但由于session 1已持有529的排他鎖無法授予(granted = f)，是以session 2需等待。
這時候我們啟動session 3，執行同樣的更新SQL
[local:/opt/data5012]:5012 [email protected]=# select pg_backend_pid();
pg_backend_pid
----------------
1837
(1 row)
Time: 0.644 ms
[local:/opt/data5012]:5012 [email protected]=# begin;
BEGIN
Time: 0.455 ms
[local:/opt/data5012]:5012 [email protected]=#* update lockdemo set c1='z';
查詢session 3的鎖資訊
[local:/opt/data5012]:5012 [email protected]=# select pid,locktype,relation::regclass,page,tuple,transactionid,mode,granted,fastpath from pg_locks where pid = 1837;
pid | locktype | relation | page | tuple | transactionid | mode | granted | fastpath
------+---------------+----------+------+-------+---------------+------------------+---------+----------
1837 | relation | lockdemo | | | | RowExclusiveLock | t | t
1837 | virtualxid | | | | | ExclusiveLock | t | t
1837 | tuple | lockdemo | 0 | 1 | | ExclusiveLock | f | f
1837 | transactionid | | | | 532 | ExclusiveLock | t | f
(4 rows)
Time: 0.705 ms
[local:/opt/data5012]:5012 [email protected]=#
可以看到，session 3的鎖資訊與session 2的鎖資訊略有不同：session 3持有lockdemo的RowExclusiveLock意向鎖，期望擷取lockdemo上的"排他行級鎖"(page = 0，tuple = 1)，但由于session 2已持有無法授予(granted = f)，是以需等待。
實際上，按照PostgreSQL源碼的注釋說明[1]，Locking tuples的處理方式如下：
When it is necessary to wait for a tuple-level lock to be released, the basic
delay is provided by XactLockTableWait or MultiXactIdWait on the contents of
the tuple's XMAX. However, that mechanism will release all waiters
concurrently, so there would be a race condition as to which waiter gets the
tuple, potentially leading to indefinite starvation of some waiters. The
possibility of share-locking makes the problem much worse --- a steady stream
of share-lockers can easily block an exclusive locker forever. To provide
more reliable semantics about who gets a tuple-level lock first, we use the
standard lock manager, which implements the second level mentioned above. The
protocol for waiting for a tuple-level lock is really
LockTuple()
XactLockTableWait()
mark tuple as locked by me
UnlockTuple()
PostgreSQL使用了标準鎖管理器(在記憶體中存儲行級鎖)，實作(元組)上的二級鎖。
按此邏輯，由于沒有沖突，session 1完整的執行了以上的處理邏輯，釋放了記憶體中的元組排他鎖；而session 2獲得了元組排他鎖，但無法擷取XID 529的共享鎖，是以等待；session 3無法擷取元組排他鎖，是以等待。
使用pageinspect/pgrowlocks檢視元組上的行級鎖：
[local:/opt/data5012]:5012 [email protected]=# select get_tuple_locks('lockdemo');
get_tuple_locks
----------------------
("(0,1)",529,,,,,)
("(0,2)",529,,,,,)
("(0,3)",529,,,,,)
("(0,4)",529,,,,,)
("(0,5)",529,,,,,)
("(0,6)",529,,,,,)
("(0,7)",529,,,,,)
("(0,8)",529,,,,,)
...
[local:/opt/data5012]:5012 [email protected]=# select * from pgrowlocks('lockdemo');
locked_row | locker | multi | xids | modes | pids
------------+--------+-------+-------+-------------------+--------
(0,1) | 529 | f | {529} | {"No Key Update"} | {1714}
...
由于更新SQL沒有帶條件，是以XID 529在lockdemo上的每個元組都加鎖。
三、參考資料