海山数据库(He3DB)源码解读：海山PG 事务锁实现
背景
He3DB for PostgreSQL是受Aurora论文启发，基于开源数据库PostgreSQL 改造的数据库产品。架构上实现计算存储分离，并进一步支持数据的冷热分层，大幅提升产品的性价比。
He3DB for PostgreSQL中存在多个会话试图同时访问同一数据的情况，并发控制的目标就是保证所有会话高效地访问，同时维护数据完整性，并发访问控制的常用方式为两种：锁机制和多版本并发控制（MVCC）。因为 MVCC 并不能解决所有的并发控制情况，所以还需要使用传统的锁机制来保证那些通常不需要完整事务隔离并且想要显式管理特定冲突点的应用。
整体概述
按照功能划分，锁管理分为锁功能模块，锁级别管理模块，死锁处理模块。
锁功能模块：针对三种类型的锁功能，自旋锁，轻量级锁，事务锁。
锁级别管理模块：针对四种不同级别的锁管理器，表级别、页级别、元组级别、事务级别。
死锁处理模块：包括死锁检测功能和死锁处理功能。
图1 锁管理模块介绍
数据结构
RegularLock就是一般数据库事务管理中所指的锁，也简称为Lck。Regularlock的特点是：有等待队列，有死锁检测，能自动释放锁。
锁模式(LOCKMODE)是一个1~N的整数，指示了一种锁类型，可表示前面提到的8种锁类型的一种。锁掩码(LOCKMASK)是一个位掩码，用于指示持有或请求的锁类型的集合
锁模式typedef int LOCKMASK; |
锁掩码typedef int LOCKMODE; |
LockConflicts
LockConflicts 用于指示持有或请求的锁类型的集合 |
static const LOCKMASK LockConflicts[] = { 0, /* AccessShareLock */ LOCKBIT_ON(AccessExclusiveLock), /* RowShareLock */ LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* RowExclusiveLock */ LOCKBIT_ON(ShareLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* ShareUpdateExclusiveLock */ LOCKBIT_ON(ShareUpdateExclusiveLock) | LOCKBIT_ON(ShareLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* ShareLock */ LOCKBIT_ON(RowExclusiveLock) | LOCKBIT_ON(ShareUpdateExclusiveLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* ShareRowExclusiveLock */ LOCKBIT_ON(RowExclusiveLock) | LOCKBIT_ON(ShareUpdateExclusiveLock) | LOCKBIT_ON(ShareLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* ExclusiveLock */ LOCKBIT_ON(RowShareLock) | LOCKBIT_ON(RowExclusiveLock) | LOCKBIT_ON(ShareUpdateExclusiveLock) | LOCKBIT_ON(ShareLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock), /* AccessExclusiveLock */ LOCKBIT_ON(AccessShareLock) | LOCKBIT_ON(RowShareLock) | LOCKBIT_ON(RowExclusiveLock) | LOCKBIT_ON(ShareUpdateExclusiveLock) | LOCKBIT_ON(ShareLock) | LOCKBIT_ON(ShareRowExclusiveLock) | LOCKBIT_ON(ExclusiveLock) | LOCKBIT_ON(AccessExclusiveLock) }; |
LockMethodData
LockMethodData定义一个锁方法的统一管理表 |
typedef struct LockMethodData { int numLockModes; const LOCKMASK *conflictTab; const char *const *lockModeNames; const bool *trace_flag; } LockMethodData; |
LOCKTAG
LOCKTAG 加锁对象标识 |
typedef struct LOCKTAG { uint32 locktag_field1; /* a 32-bit ID field */ uint32 locktag_field2; /* a 32-bit ID field */ uint32 locktag_field3; /* a 32-bit ID field */ uint16 locktag_field4; /* a 16-bit ID field */ uint8 locktag_type; /* see enum LockTagType */ uint8 locktag_lockmethodid; /* lockmethod indicator */ } LOCKTAG; |
LOCK
LOCK 锁对象 |
typedef struct LOCK { /* hash key */ LOCKTAG tag; /* unique identifier of lockable object */ /* data */ LOCKMASK grantMask; /* bitmask for lock types already granted */ LOCKMASK waitMask; /* bitmask for lock types awaited */ SHM_QUEUE procLocks; /* list of PROCLOCK objects assoc. with lock */ PROC_QUEUE waitProcs; /* list of PGPROC objects waiting on lock */ int requested[MAX_LOCKMODES]; /* counts of requested locks */ int nRequested; /* total of requested[] array */ int granted[MAX_LOCKMODES]; /* counts of granted locks */ int nGranted; /* total of granted[] array */ } LOCK; |
PROCLOCK
PROCLOCK 锁持有者描述 |
typedef struct PROCLOCK { /* tag */ PROCLOCKTAG tag; /* unique identifier of proclock object */ /* data */ PGPROC *groupLeader; /* proc's lock group leader, or proc itself */ LOCKMASK holdMask; /* bitmask for lock types currently held */ LOCKMASK releaseMask; /* bitmask for lock types to be released */ SHM_QUEUE lockLink; /* list link in LOCK's list of proclocks */ SHM_QUEUE procLink; /* list link in PGPROC's list of proclocks */ } PROCLOCK; |
LOCALLOCK
LOCALLOCK 本地锁持有者描述 |
typedef struct LOCALLOCK { /* tag */ LOCALLOCKTAG tag; /* unique identifier of locallock entry */ /* data */ uint32 hashcode; /* copy of LOCKTAG's hash value */ LOCK *lock; /* associated LOCK object, if any */ PROCLOCK *proclock; /* associated PROCLOCK object, if any */ int64 nLocks; /* total number of times lock is held */ int numLockOwners; /* # of relevant ResourceOwners */ int maxLockOwners; /* allocated size of array */ LOCALLOCKOWNER *lockOwners; /* dynamically resizable array */ bool holdsStrongLockCount; /* bumped FastPathStrongRelationLocks */ bool lockCleared; /* we read all sinval msgs for lock */ } LOCALLOCK; |
LockAcquireResult
LockAcquireResult 事务锁申请的结果 |
typedef enum { LOCKACQUIRE_NOT_AVAIL, /* lock not available, and dontWait=true */ LOCKACQUIRE_OK, /* lock successfully acquired */ LOCKACQUIRE_ALREADY_HELD, /* incremented count for lock already held */ LOCKACQUIRE_ALREADY_CLEAR /* incremented count for lock already clear */ } LockAcquireResult; |
Regular Lock设计
设计原理
He3DB中使用了两种加RegularLock锁的方法：DEFAULT_LOCKMETHOD和USER LOCKMETHOD，前者为默认锁方法，后者为用户锁方法。He3DB中一般将DEFAULT_LOCKMETHOD作为默认加锁方法。当然用户也可以定义自己的锁方法，比如建议锁(AdvisoryLock)就是用户所创建的锁方法类型。
依据这两种不同的锁方法，可以生成两种不同类型的锁表。在Postmaster 启动时，分配一块共享内存区作为RegularLock方法表并适当地初始化RegularLock方法表的各个字段，此外还将初始化锁方法数组和其他一些共享变量。后台进程启动后通过锁方法来引用RegularLock。
用户锁方法应用于长期协作锁，即长事务。这种锁的用处在于提示应用程序某用户正在工作于某数据库元素上。因此，可以在一个数据库元组上加上用户锁，使得用户可以在长时间的检索和更新完该元组后再释放此锁。在该用户锁工作时，其他用户能检测到这个元组当前已经被另一应用级别用户加锁，其他用户在该元组上所能采取的操作将受到限制。
获取用户锁是无阻塞的，即进程或者得到用户锁，或者不能得到用户锁，不存在等待队列。因此如果一个进程持有了用户锁，则另一个进程就不能再获得它。当一个后台进程进程结束时，用户锁将自动被释放。默认锁和用户锁都是完整的，而且它们之间不互相于扰，即两种锁可以同时存在。
事务锁支持的锁模式
RegularLock支持的锁模式有八种，按排他(Exclusive)级别从低到高分别是：
- 访问共享锁(AecessSharelock)：一个内部锁模式，进行查询(SELECT操作)时自动施加在被查询的表上。
- 行共享锁(RowShareLock)：当语句中采用了SELECT…FORUPDATE和FORSHARE 时将使用行共享锁对表加锁。
- 行排他锁(RowExclusiveLock)：使用UPDATE、DELETE、INSERT语句时将使用行排他锁对表加锁。
- 共享更新排他锁(ShareUpdateExclusiveLock)：使用VACUUM(不带FULL选项)ANALYZE或CREATEINDEXCONCURRENTLY语时使用共享更新排他锁对表加锁。
- 共享锁(ShareLock)：使用不带CONCURRENTLY选项的CREATEINDEX语请求时用共享锁对表加锁。
- 共享行排他锁(ShareRowExclusivelock)：类似于排他锁，但是允许行共享。
- 排他锁(ExclusiveLock)：阻塞行共享和SELECT...FOR UPDATE。
- 访问排他锁(AccessExclusiveLock)：被ALTER TABLE、DROP TABLE 以及 VACUUM FULL操作要求。
其中，排他模式的锁(ShareRowExclusiveLock、ExclusiveLock、AccessExclusiveLock)表示在事务执行期间阻止其他任何类型锁作用于此表。
共享模式的锁(非排他模式的锁)表示允许其他用户同时共享此锁，但在事务执行期间阻止排他型锁的使用。排他模式和共享模式的锁都可以工作在以下授权级别上:
Access：锁定整个表模式
Rows：仅锁定单独的元组。
访问共享锁是最低限制的锁，访问排他锁是限制最严格的锁。共享行排他型锁与排他锁相似但它允许其他用户使用行共享锁。每种锁模式都有与之相冲突的锁模式，由锁冲突表1定义相关信息。
编号 | 锁模式 | 用途 | 冲突关系 |
1 | AecessSharelock | SELECT | 8 |
2 | RowShareLock | SELECT FOR UPDATE/FOR SHARE | 7 | 8 |
3 | RowExclusiveLock | INSERT/UPDATE/DELETE | 5 | 6 | 7 | 8 |
4 | ShareUpdateExclusiveLock | VACUUM | 4 | 5 | 6 | 7 | 8 |
5 | ShareLock | CREATE INDEX | 3 | 4 | 6 | 7 | 8 |
6 | ShareRowExclusivelock | ROW SELECT..FOR UPDATE | 3 | 4 | 5 | 6 | 7 | 8 |
7 | ExclusiveLock | BLOCK ROW SHARE/SELECT...FOR UPDATE | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
8 | AccessExclusiveLock | DROP CLASS/VACUUM FULL | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
表1 锁冲突表
在一般数据库系统中，使用S(共享锁)、X(排他锁)、IS(意向共享锁)、以X(意向排他锁)，以及SIX(共享意向排他锁)五种锁即可完成加锁需要，由于He3DB扩展了标准的SOL语句，所以对应于这些扩展的操作需要设计特定的锁完成加锁需求。
主要流程
He3DB通过三张锁表联合管理系统的加锁情况。
LockMethodLockHash：由锁方法ID到锁表数据结构的映射。
LockMethodProcLockHash：锁方法对应的PROCLOCK对象的Hash表指针。
LockMethodLocalHash：锁方法对应的LOCALLOCK对象的Hash表指针。
- RegularLock的空间计算
锁空间计算操作由函数LockShmemSize实现，用于估计锁表所需共享内存空间大小。这些空间包括,
- “Lock Hash”表所需空间。
- “ProcLock Hash”表所需空间。
- 为安全考虑多分配 10%的空间。
- RegularLock的初始化
锁的初始化操作由函数InitLocks实现，该函数初始化锁管理器的数据结构，主要工作有初始化LockMethodLockHash、LockMethodPrcLockHash和LockMethodLocalHash这三个Hash表。
- RegularLock加锁
加锁操作在函数LockAcquire中定义，它有四个参数LockTag、LockMode、SessionLock、dontWait:
LockTage 是被锁对象的唯一标识。
LockMode指示要获得的锁模式(SHARE/EXCLUSIVE)。
SessionLock 表示加锁的模式。如果为TRUE，表示为会话加锁:如果为FALSE，则为当前事务申请锁。
DontWait 表示申请锁是否允许等待。如果为TRUE，则在检査到无法获得锁之后不等待;如果为 FALSE，则可以等待。该函数的返回值 LockAcquireResult(数据结构7.12)表示加锁是否成功等结果信息。
申请加锁的流程如下:
1)首先用LOCKTAG和加锁模式得到具体的加锁类型，然后在本地表查找此加锁类型的信息。
2)如果没有，则在本地表插入此信息;否则，分配空间以记录锁拥有者的信息。
3)如果当前事务已经持有过此类型的锁，在本地表的计数器上加1，然后直接退出。否则在全局的锁表(LockMethodLockHash)中找这个锁。
4)如果在“Lock Hash”中找不到，则在“Lock Hash”中插入一个新元素。然后在ProcLock-Hash表里也查找对应的ProcLock。
5)如果在ProcLock Hash表找不到，则插入该ProcLock。
6)检查这个类型的锁会不会与已加的锁发生冲突，如果不会，则加锁:否则，根据函数参数决定等待还是退出。如果退出，还需清除锁表中相应的元素以保持一致性。
4. RegularLock的释放
与加锁相对应的操作是解锁，RegularLock的解锁操作定义在函数LockRelease中，该函数在本地锁表(LckMethodLocalHash)中查找锁标记为LockTag的锁，并释放该锁。如果SessionLock 为TRUE，则释放一个会话锁(SessionLock)，否则，释放一个常规的事务锁。如果发现任何等待进程现在是可以被唤醒的，将请求的锁赋予它们并将其唤醒。
该函数的流程如下:
1)用 LOCKTAG和加锁模式得到具体的锁类型，然后在本地表查找此类型的锁的信息。
2)找到此类型锁的拥有者，在它持有锁的计数器上减1。如果它已经不再持有此锁，则删除这个拥有者的信息。
3)如果这个类型的锁并没有真正释放，只是计数器减1，直接退出。
4)否则在全局的“Lock Hash”和“ProcLock Hash”表里査找此锁对应的Lock和Proclock，调用UnGrantLock 修改其信息。唤醒可以被唤醒的进程，并从“Local Hash”里移除该类型锁。
如果只需要释放一个本地锁，He3DB用函数RemoveLocallock来完成。
另外，He3DB还提供了能一次释放当前进程所持有的指定锁方法的全部的锁。该操作在函数 LockReleaseAll 中定义，如果参数 AlLocks为FALSE，则释放除 Sessionlock 之外所有的锁，否则释放所有的锁(包括SessionLock)。
5. RegularLock的申请
该操作在函数GrantLocalLock中定义，如果当前进程已经获得所需的锁，那么只需要对当前该锁的引用计数加1，即更新LOCALLOCK 结构表示所需的锁已经被授予了。
6.RegularLock的注销
该操作为RegularLock的申请操作的逆过程，定义在函数UnGrantLock中。它取消对一个锁的分配，即更新LOCK和PROCLOCK数据结构以显示该锁不再由当前持有者持有或请求。如果在该锁上存在任何等待者则需要由ProcLockWakeup 唤醒。
7.锁的冲突检测
该操作用来检测当前后端所请求的锁和已持有的锁是否冲突，它定义在函数LockCheckConficts中。如果存在冲突，返回STATUS_FOUND，否则返回STATUS_OK。一个进程所有锁之间并不冲突，即使是由不同事务所持有的(例如会话锁和事务锁并不冲突)。所以在决定请求的新锁是否和已持有锁之间是否冲突时，我们需要减去我们本身所持有的锁。
8.两阶段提交
两阶段提交中涉及以下三种关于锁的操作:
获取一个Prepared事务的锁。该操作定义在函数lock_twophase_recover中。该函数在数据库启动的时候被调用，这个重新获取锁的过程不会和其他事务有冲突。
分布式数据库预提交COMMITPREPARED时释放该两阶段提交记录指示的锁。该函数定义在Elock twophase postcommit中.
分布式数据库进行两阶段提交ROLLBACKPREPARED时释放锁操作，该操作定义在函数lock_twophase_postabort中。
9. 锁的清理
该操作定义在函数CleanUpLock中，在释放锁之后执行，主要是清理ProcLock队列入口。
图2 RegularLock模块使用流程
主要接口
对外接口函数 | 接口说明 |
void InitLocks(void) | 初始化事务锁 |
Size LockShmemSize(void) | 事务锁空间分配 |
LockAcquireResult LockAcquire(const LOCKTAG *locktag, LOCKMODE lockmode, bool sessionLock, bool dontWait) | 事务锁申请 |
bool LockRelease(const LOCKTAG *locktag, LOCKMODE lockmode, bool sessionLock) | 事务锁释放 |
void LockReleaseAll(LOCKMETHODID lockmethodid, bool allLocks) | 释放全部锁 |
bool LockCheckConflicts(LockMethod lockMethodTable, LOCKMODE lockmode, LOCK *lock, PROCLOCK *proclock) | 锁冲突检测 |
作者介绍
徐元慧，移动云数据库高级系统架构师，负责云原生数据库He3DB的架构设计与研发。
