带你了解Greenplum的锁管理机制

引言

数据库系统有多种实现并发控制的机制，而锁作为其中一种实现方式，具有非常重要的作用。在这篇文章中，我们将介绍Greenplum中的锁管理机制是如何实现的。本周五（8月28日）的《深入浅出Greenplum内核》第六场活动中，来自Greenplum原厂的内核研发将深度揭秘MVCC并发控制的其他内容，尽请关注。

01 锁管理概述

在Greenplum实现中，针对不同的场景和目的定义了三种锁，分别是自旋锁（Spinlocks）、轻量级锁（LWLocks）和普通锁（Regular locks，也叫重量级锁）。

自旋锁是一种短期持有的锁。如果加锁之后程序指令很多，或者涉及到系统调用，则不适合使用自旋锁。自旋锁通常由硬件指令TAS来实现，等待锁的进程会忙等直到可以拿到锁，或是如果等待时间过长，会有超时机制。自旋锁没有死锁检测和出错时自动释放。

轻量级锁为共享内存中需要并发访问的结构体提供锁保护，支持两种模式：互斥模式和共享模式。轻量级锁并没有死锁检测机制，但是在elog出错恢复时，轻量级锁管理器会自动释放持有的轻量级锁，因此一个进程在持有轻量级锁时是可以安全地报错的。通常来说，在没有锁竞争的情况下，获取和释放一个轻量级锁都是很快的。当一个进程必须等待一个轻量级锁时，会阻塞在一个SysV信号量上，因此等待过程并不消耗CPU时间。等待进程按照申请锁的先后顺序获得授权，没有超时机制。

普通锁也叫做重量级锁，用于对数据库对象，比如表、数据记录等加锁。普通锁支持多种不同的加锁模式，同时也支持死锁检测以及在事务结束时自动释放。

接下来，我们将重点讲述普通锁的实现细节。

02 普通锁数据结构

1. 锁方法

锁方法是对锁行为的整体描述。在目前的Greenplum数据库中，有三种锁方法：DEFAULT、USER和RESOURCE。

#define DEFAULT_LOCKMETHOD  1
#define USER_LOCKMETHOD     2
#define RESOURCE\_LOCKMETHOD 3

其中，DEFAULT锁方法是系统默认的加锁方法，用于对常见数据对象加锁。USER锁方法主要用于意向锁（Advisory Locks）。RESOURCE锁方法用于对资源队列的访问加锁。

锁方法由结构体LockMethodData来表示。

结构体LockMethodData

其中，锁模式冲突表定义了各个锁模式之间的冲突关系。理论上，各个锁方法可以定义自己的锁模式以及锁模式冲突表，但目前这三种锁方法使用相同的锁模式和锁模式冲突表，具体定义如下表所示。

锁模式

锁模式冲突表

2. 锁结构体

在内存中普通锁由结构体LOCK来表示，该结构体记录了一个可加锁对象的锁信息。该结构体定义如下。

其中，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;

locktag_lockmethodid即我们前面讲的三种锁方法。locktag_type则指定了加锁对象的类型，例如LOCKTAG_RELATION、LOCKTAG_PAGE、LOCKTAG_TUPLE等等。locktag_field1/2/3/4根据加锁对象类型的不同，会表示不同的含义。举个具体的例子，假如我们要对某元组加锁，LOCKTAG的设置如下所示：

#define SET_LOCKTAG_TUPLE(locktag,dboid,reloid,blocknum,offnum) \
    ((locktag).locktag_field1 = (dboid), \
     (locktag).locktag_field2 = (reloid), \
     (locktag).locktag_field3 = (blocknum), \
     (locktag).locktag_field4 = (offnum), \
     (locktag).locktag_type = LOCKTAG_TUPLE, \
     (locktag).locktag_lockmethodid = DEFAULT_LOCKMETHOD)

我们可以看到，locktag_field1表示元组所属数据库ID，locktag_field2表示元组所属关系表ID，locktag_field3表示元组所在块号，locktag_field4表示元组在块内的偏移量，locktag_type是LOCKTAG_TUPLE，锁方法则是DEFAULT_LOCKMETHOD。

除了LOCK结构体外，我们还会使用另外一个结构体PROCLOCK。多个进程可能会同时持有或是等待同一个可加锁对象，对于每一个锁持有者或是等待者，我们会将其信息保存在一个结构体PROCLOCK中。

结构体PROCLOCK

其中PROCLOCKTAG唯一标识一个PROCLOCK对象，它包含了可加锁对象以及该对象的持有者或等待者，定义如下：

typedef struct PROCLOCKTAG
{
    LOCK       *myLock;         /* link to per-lockable-object information */
    PGPROC     *myProc;         /* link to PGPROC of owning backend */
} PROCLOCKTAG;

代表backend进程的结构体PGPROC、代表锁持有者或者等待者的结构体PROCLOCK，以及代表锁对象的结构体LOCK之间的关系如下图所示：

3. 单机死锁检测

由于我们允许进程以任意的顺序去申请锁，因此就可能会出现死锁的情况。死锁就是运行中的进程持有一些锁并再去申请其他的锁，形成了互相依赖的现象。对于单机版的死锁检测，我们采用了“乐观等待”的方法，即如果一个进程当前无法获取它要申请的锁，那么它会睡眠等待在该锁的等待队列中，同时它还会启动一个计时器（一般是一秒）。当计时器到时间时该进程还在等待，则此时才会运行死锁检测算法。

单机版的死锁检测算法使用等待图（waits-for graph, WFG）来检测死锁。在WFG图中，参与加锁的所有进程作为有向图中的顶点；如果进程A正在等待某一个锁，而进程B持有与之冲突的锁，那么我们就说A等待B，于是就存在一个从A到B的边。在Greenplum中，这种类型的边我们称之为hard edge。如果我们发现在这个WFG图中存在环，则说明有死锁的情况发生。此时我们需要撤销当前申请加锁的进程所在的事务来解除死锁。

在Greenplum的WFG图中还存在另外一种边。如果进程A和进程B同时都在某一个锁的等待队列里等待，A在B的后面，并且它们申请的锁是互相冲突的，那么由于B总是会先于A被唤醒，此时就存在了一个A等待B的情况，我们称这种等待的边为soft edge。对于由soft edge形成的死锁情况，我们可以尝试调整等待队列里进程的顺序。如果我们能找到一个顺序使得WFG图中不再有环存在，那么我们就无需撤销事务了。

03 结束语

锁是数据库系统中实现并发控制的一种重要机制。本文对Greenplum中的锁管理做了一个简单介绍，包括主要的数据结构，各个数据结构之间的关系，以及单机死锁检测算法的原理。希望进一步了解代码的读者可以参阅如下文件：

src/include/storage/lock.h
src/backend/storage/lmgr/lock.c
src/include/storage/lwlock.h
src/backend/storage/lmgr/lwlock.c
src/include/storage/s_lock.h
src/backend/storage/lmgr/s_lock.c