PostgreSQL并发控制机制（2）：表级锁和行级锁__并发控制是多个事务在并发运行时，数据库保证事务一致性（Consistency）和隔离性（Isolation）的一种机制。主流商用关系数据库使用的并发控制技术主要有三种：严格两阶段封锁（S2PL）、多版本并发控制（MVCC）和乐观并发控制（OCC）。 : 世界上功能最强大的开源数据库...

### **个人介绍**

#### 作者：何小栋

#### 博客：http://blog.itpub.net/6906/

#### 个人简介：从事产品研发和架构设计工作，ITPUB数据库版块资深版主，对PostgreSQL数据库及其源代码有深入研究。现就职于广州云图数据技术有限公司，系统架构师。

#### 并发控制是多个事务在并发运行时，数据库保证事务一致性（Consistency）和隔离性（Isolation）的一种机制。主流商用关系数据库使用的并发控制技术主要有三种：严格两阶段封锁（S2PL）、多版本并发控制（MVCC）和乐观并发控制（OCC）。
#### 在工程实践上，PostgreSQL使用了MVCC的一种变体快照隔离SI结合封锁技术进行并发控制，本文介绍了锁相关的部分理论以及PostgreSQL的工程实践，最后结合案例对PostgreSQL的表级锁和行级锁进行了相关介绍。

### **一.相关理论**

#### 在开始之前，我们不妨考虑这么一个问题：不使用锁，仅仅使用快照隔离技术是否可以实现并发控制？答案是肯定的。其中的一种解决方案，使用类似于ORM框架Hibernate的乐观并发控制机制，通过延迟更新缓存执行结果，同时使用Tuple的数据版本号实现。该算法简单来说分为两步：第一步，在假设不冲突的情况下执行操作（不需要加锁和等待，因此不会出现延迟）；第二步，通过检查假设是否为真来对第一步进行验证，为真则执行实际的写并提交，否则重做。
#### 在PostgreSQL中，对于任一个tuple，xmin+xmax可以认为是该tuple的版本号，在不加锁的情况下，事务Ti对本事务生成的tuple快照（与其他事务的tuple快照相互隔离）进行处理并缓存结果，在事务提交前判断本次事务快照的tuple版本（xmin+xmax）与数据库中tuple的版本是否一致，如一致则执行实际的写操作并提交事务，否则回滚整个事务。不过这种方案很明显的一个缺点是在冲突很多的情况下，并发的冲突事务会频繁的回滚，看起来机器资源利用率很高，但其实大多时间都在做无用功；另外一个问题是由于Tuple版本的判断和真正写入数据库（事务完结）之间存在时间差，在这个时间差之间可能出现其他并发事务更新同一tuple的现象（脏写）。
#### 为了避免这种频繁回滚的情况，PostgreSQL使用了相对“悲观”的策略，通过封锁技术对存在争用的资源（relation、page、tuple等）进行锁定，在处理过程中判断并等待而非延迟至事务提交时才进行判断。基于数据库对象的多层次逻辑结构，PostgreSQL使用的是一种多粒度的封锁机制，下面从理论层面简单作一介绍。

#### **1、数据库对象逻辑结构**
#### PostgreSQL的逻辑对象体系结构如下图所示：

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2015_图片1--2020.9_.15_.png)

#### 从锁的角度来看，在层次“关系”以下，关系（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之间的相容性矩阵：

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2024_图片2--2020.9_.15_.png)

#### 从上面的相容性矩阵可以看出，IS除了X外，可与其他锁相容；IX除了S和X外，可与其他意向锁相容；S除了IS和S（自相容）外，与IX和X都不相容；X则与其他所有锁均不相容。
#### 上面介绍了意向锁协议，我们不禁要问的一个问题是：为什么要引入意向锁？我们不妨考虑以下问题：事务Ti修改关系R中的某个元组y，无疑我们需要在y上加X锁，但在R上需要加锁吗？如果不加锁，这时候另外一个并发事务Tj需要在关系上创建索引（显然，需要在关系上加S锁），由于关系上没有锁存在，那么Tj需要在元组这一层次上判断关系R的元组是否存在锁，这无疑会增加判断的复杂度和成本。从性能和可维护性上考虑，我们希望直接在关系这个层次上判断是否可以对整个关系加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种类型。不少PostgreSQL的初学者看到这么多锁估计会发懵，但如果我们结合上一节的多粒度锁机制来理解就会相对比较容易。

#### 我们从两个维度来看：粒度和操作。粒度分为Relation和Row，操作分为读（Share）、写（Exclusive）和读写（Share Exclusive），根据这两个维度得到下面的矩阵：

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2026_图片3--2020.9_.15_.png)

#### 这些锁中，Row Share和Row Exclusive可视为意向锁：真正需要锁定的数据项是元组而非关系，如出现冲突则留待元组级解决。除此之外，其他均为普通锁：锁定的数据项是关系，且无需在行上加锁。
#### 上述八种锁的相容性矩阵如下表所示：

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2027_图片4--2020.9_.15_.png)

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2028_图片5--2020.9_.15_.png)

#### 上一节提到，PostgreSQL在执行DDL时使用S2PL，在执行DML时使用SI。为了与传统的共享锁（读锁）和排他锁（写锁）区分，PostgreSQL在执行DDL时关系上的锁是Access Exclusive而不是Exclusive，在执行DML查询语句时关系上的锁是Access Share而不是Share，从相容性矩阵可以看出，这样的区分可以实现在写（Row Exclusive）的时候不会阻塞多版本读（Access Share），多版本读（Access Share）的时候不会阻塞写（Row Exclusive）。而传统意义上的读锁（Share Lock）则用于Create Index，排斥所有含有Exclusive的写锁，但不排斥其他读锁（Share Lock），这意味着创建索引时不可以修改数据，但允许查询数据或者创建其他索引；常规意义上的写锁Exclusive，用于物化视图的并发刷新，会排斥除多版本读外的其他所有锁。
#### 小结一下，在PostgreSQL中：
#### n 多版本读锁和写锁-2类：Access Share和Access Exclusive
#### n 意向锁-2类：Row Share和Row Exclusive，它们之间的差异在于Row Share排斥仅表级的Exclusive&Access Exclusive，其他相容锁如出现冲突则在行级解决
#### n 传统共享锁-3类：细分为Share Update Exclusive、Share、Share Row Exclusive，目的是为了不同的SQL命令精细化控制锁，提高系统并发
#### n 传统写锁-1类：Exclusive，用于物化视图刷新
#### **2、行级锁**
#### PostgreSQL的行级锁有4个，从两个维度来看：主（唯一）键相关和模式（排他和共享），见下面的矩阵：
![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2029_图片6--2020.9_.15_.png)

#### **排他模式**
#### n FOR UPDATE：对整行进行更新，包括删除行
#### n FOR NO KEY UPDATE：对除主（唯一）键外的字段更新。
#### **共享模式**
#### n FOR SHARE：读该行，不允许对行进行更新
#### n FOR KEY SHARE：读该行的键值，但允许对除键外的其他字段更新。在外键检查时使用该锁
#### 值得一提的是，PostgreSQL的行级锁并没有在内存中存储而是使用了元组Header的标记位存储（相应的数据结构是HeapTupleHeaderData），没有了内存上的限制，因此理论上PostgreSQL可以支持无限多的元组锁。
#### HeapTupleHeaderData数据结构：
```
//t_infomask说明
               1 #define HEAP_HASNULL            0x0001  /* has null attribute(s) */
              10 #define HEAP_HASVARWIDTH        0x0002  /* has variable-width attribute(s) */
             100 #define HEAP_HASEXTERNAL        0x0004  /* has external stored attribute(s) */
            1000 #define HEAP_HASOID             0x0008  /* has an object-id field */
           10000 #define HEAP_XMAX_KEYSHR_LOCK   0x0010  /* xmax is a key-shared locker */
          100000 #define HEAP_COMBOCID           0x0020  /* t_cid is a combo cid */
         1000000 #define HEAP_XMAX_EXCL_LOCK     0x0040  /* xmax is exclusive locker */
        10000000 #define HEAP_XMAX_LOCK_ONLY     0x0080  /* xmax, if valid, is only a locker */
                    /* xmax is a shared locker */
                 #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  /* t_xmin committed */
      1000000000 #define HEAP_XMIN_INVALID       0x0200  /* t_xmin invalid/aborted */
                 #define HEAP_XMIN_FROZEN        (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
     10000000000 #define HEAP_XMAX_COMMITTED     0x0400  /* t_xmax committed */
    100000000000 #define HEAP_XMAX_INVALID       0x0800  /* t_xmax invalid/aborted */
   1000000000000 #define HEAP_XMAX_IS_MULTI      0x1000  /* t_xmax is a MultiXactId */
  10000000000000 #define HEAP_UPDATED            0x2000  /* this is UPDATEd version of row */
 100000000000000 #define HEAP_MOVED_OFF          0x4000  /* moved to another place by pre-9.0
                                         * VACUUM FULL; kept for binary
                                         * upgrade support */1000000000000000 #define HEAP_MOVED_IN           0x8000  /* moved from another place by pre-9.0
                                         * VACUUM FULL; kept for binary
                                         * upgrade support */
                 #define HEAP_MOVED (HEAP_MOVED_OFF | HEAP_MOVED_IN)1111111111110000 #define HEAP_XACT_MASK          0xFFF0  /* visibility-related bits */
//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 pg12@testdb=# select pg_backend_pid();
 pg_backend_pid----------------
           1714
(1 row)
Time: 2.994 ms
[local:/opt/data5012]:5012 pg12@testdb=# begin;BEGINTime: 0.154 ms
[local:/opt/data5012]:5012 pg12@testdb=#* update lockdemo set c1 = 'x';UPDATE 10000Time: 15.786 ms
[local:/opt/data5012]:5012 pg12@testdb=#*
[local:/opt/data5012]:5012 pg12@testdb=#* select txid_current();
 txid_current--------------
          529
(1 row)
Time: 2.916 ms
```

Time: 5.251 ms
-- session 2

Time: 0.705 ms
[local:/opt/data5012]:5012 pg12@testdb=#
```
#### 可以看到，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 pg12@testdb=# 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 pg12@testdb=# select * from pgrowlocks('lockdemo');
 locked_row | locker | multi | xids  |       modes       |  pids
------------+--------+-------+-------+-------------------+--------
 (0,1)      |    529 | f     | {529} | {"No Key Update"} | {1714}
```
#### 由于更新SQL没有带条件，因此XID 529在lockdemo上的每个元组都加锁。

### **三.小结**

#### 本文通过介绍相关理论并结合案例对PostgreSQL的表级锁和行级锁的实现机制和背后的设计思想作了一个简单介绍，目的是希望从系统设计的角度对PG的锁机制给出一些新的认识。

### **四.参考资料**

#### [1] PostgreSQL Source Code，README.tuplock

#### [2] PostgreSQL Manual

#### [3] Postgres Professional，erogov，Locks in PostgreSQL

#### [4] Unlocking the Postgres Lock Manager，BRUCE MOMJIAN

![CENTER_PostgreSQL_Community]( /images/news/2020/20200915_2015_最新底部文章.png)

PostgreSQL并发控制机制（2）： 表级锁和行级锁

PostgreSQL并发控制机制（2）：表级锁和行级锁