PostgreSQL数据库的SSI实现

👆点击“博文视点Broadview”，获取更多书讯

PostgreSQL数据库默认的隔离级别是 Read Committed，它同时支持Repeatable Read和Serializable。在9.1（不含）之前的版本中，PostgreSQL的Serializable级别等价于Snapshot Isolation，而非真正的Serializable。

Snapshot Isolation主要存在写偏序（Write Skew）问题，这个问题在PostgreSQL 9.1中已通过Serializable Snapshot Isolation（SSI）方法解决。

本文主要对PostgreSQL数据库的SSI实现进行分析。

01

SSI介绍

主流数据库通常基于S2PL或MVCC实现并发控制，写偏序异常在这两种并发控制下有不同的表现：

①在S2PL下，当操作序列中含有写操作时，会阻塞其他事务的读和写，因此不会有并发的读写操作，这样可以避免写偏序异常。 ②MVCC保留元组的多个版本，实现了读和写互不阻塞，只有写和写互相冲突。这种性质导致了可能会有并发的读写操作，因此会产生写偏序异常，进而导致事务的不可串行化。

▊ 依赖关系

在事务调度时，会根据读写操作是否冲突调整并发事务之间读写操作的执行顺序（参照2.2节）。假设有如下两个事务序列。

• T1：R1(x)W1(y)。
• T2：R2(y)W2(x)。

在可串行化调度下，这两个事务中的冲突关系如下。

• R1(x)和W2(x)冲突。
• W1(y)和R2(y)冲突。

假如R1(x)发生在W2(x)之前，那么就构成了事务T1->T2的顺序依赖关系。这时W1(y)也必须发生在R2(y)之前，否则就无法构成可串行化调度。

假如W2(x)发生在R1(x)之前，那么就构成了事务T2->T1的顺序依赖关系，这时R2(y)也必须发生在W1(y)之前，否则也无法构成可串行化调度。

也就是说，在可串行化调度下，事务的执行顺序可以由事务之间读写操作的顺序决定，论文Generalized Isolation Level Definitions中对事务之间的依赖关系做了进一步的分析，如表1所示。

表1  SSI中的读写依赖关系

▊ S2PL和SSI

在S2PL中，读锁和写锁互相冲突，写锁和写锁也互相冲突，而每个事务中的各个操作又都是串行执行的，因此事务的执行顺序和读写的依赖关系能够对应起来，不会出现事务之间的读写操作互相依赖的情况。

以rw依赖为例，如图1所示，当事务T1读取X对象时会在X上加读锁，而事务T2要修改X对象时需要在X上加写锁，事务T2需要等待事务T1提交（S2PL保证在事务提交时才会放锁）。也就是说，事务T1一定在事务T2之前提交。这种执行顺序产生的结果和先执行T1再执行T2的结果是一样的。

图1  S2PL的示例

同理，先写后读操作也需要写事务先提交之后，读事务才能读到写事务写入的值。并发的写操作则需要在先加锁的写事务提交之后（即释放锁），后申请锁的写事务才能获得锁，并开始写操作。

在S2PL下，可以避免写偏序异常。在《PostgreSQL技术内幕：事务处理深度探索》一书的2.1节中介绍过写偏序异常，如果对图2中的两个事务应用S2PL，则会产生死锁。如图2所示，死锁检测机制能保证终止其中一个事务，因此S2PL可以避免写偏序异常。

图2  S2PL和写偏序

▊ MVCC和SSI

MVCC的特点是“写不阻塞读，读不阻塞写”，也就隐含着不同事务针对同一个对象的写写操作还是冲突的。

在Serializable隔离级别下，如果出现了并发更新（写），参照First Commit Win（FCW）原则，则后提交的事务会被终止。

在MVCC下能够保证事务是按照ww依赖的顺序执行的，也就是说，如果两个事务T1和T2存在T1->T2的ww依赖，则可以保证T1是在T2之前执行的。

First Commit Win：事务T1的持续时间可以表示为{start_time(T1), commit_time(T1)}，它修改的对象集合可以表示为{X|x1, x2,…, xn}。当事务T1提交时，如果：

∅ != {start_time(T1), commit_time(T1)} ∩ {start_time(T12, commit_time(T2)} &&

     commit_time(T2) < commit_time(T1)

那么，事务T1需要终止提交，这就是First Commit Win原则。

static TupleTableSlot *ExecUpdate(ModifyTableState *mtstate,…){    …        case TM_Updated:        {            //隔离级别 >= Repeatable Read，如果出现并发更新，则终止后提交的事务            if (IsolationUsesXactSnapshot())            ereport(ERROR,                    (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE),                     errmsg("could not serialize access due to concurrent update")));    …}

如果有两个事务T1和T2，T1先对X对象进行了更新（更新操作会产生X_old和X_new两个版本），然后T2去读X对象，由于T1没有提交，且当前的隔离级别是Serializable，所以T2读到的应该是T1更新前的X对象，也就是读取到的永远是X_old，这时候能够保证并发事务的执行结果和T2在T1之前执行等价。

因为只有T1提交且T2获得的隔离快照在T1提交之后，T2才能看到T1的更新结果X_new，这里实际上隐含了依赖（冲突）的两种情况，如图3所示。

• 如果T3开始时，T1没有提交，T3读到的是T1更新前的X_v0值，于是形成了T3->T1的rw依赖。
• 如果T4开始时，T1已经提交，T4读到的是T1写入之后的X_v1值，于是形成了T1->T4的wr依赖。

图3  MVCC下的写偏序产生的两种情况

从上述分析可以看出，无论是ww依赖还是wr依赖，都需要读X对象写之后的最新版本，所以它们需要先提交写事务，另一个事务才能够再次写或者继续读X对象。

而在多版本并发控制的情况下，rw依赖没有这种限制，因为读操作可以读到写操作前的历史版本，从而形成rw依赖。

▊ SSI方法

SI隔离级别最早出现在论文A Critique of ANSI SQL Isolation Levels中，这种方法通过保持对象的多个版本来实现写不阻塞读。

如果事务T1开始运行，则当事务T1读取X对象时，它并不一定获得X对象的最新版本，而可能是X对象的一个中间版本，事务T1在启动时会记录自己的时间戳start_timestamp(T1)，事务T1读取的X对象的值是start_timestamp(T1)之前提交的事务中最后一个对T对象进行修改的事务产生的值（但事务内的修改是可见的）。

当事务提交时，SI会获得事务提交的时间戳commit_timestamp(T1)。

如果一个事务T1在[start_timestamp, commit_timestamp]之间修改了元组，而另一个事务T2在提交时发现自己在[start_timestamp, commit_timestamp]之间也修改了事务T1修改的元组，则事务T2必须回滚，否则就可能会产生丢失更新异常。

SI存在写偏序异常，可以用一个黑白球问题来解释写偏序异常。假设当前表中有两条元组，一条元组表示黑球，另一条元组表示白球，如图4所示。

图4  写偏序异常：元组的初始状态

如果有两个并发事务，T1要更新白球为黑球，T2要更新黑球为白球，在MVCC机制下，它们分别都能看到原来v0版本的黑球和白球，但看不到被另一个事务更新后的黑球和白球，如图5所示。

图5  写偏序异常：并发更新

从更新后的结果中可以看出，表中仍然有一个黑球和一个白球，这不满足Serializable隔离级别，如图6所示。

图6  写偏序异常：并发更新后的结果

如果T1和T2串行执行，则无论谁先执行，都不会产生这种结果，如图7所示。

图7  事务T1和T2串行执行的两种结果

通过分析发现，T1->T2存在rw依赖，T2->T1也存在rw依赖，如图8所示。

图8  写偏序异常：并发更新中的rw依赖

在Serializable隔离级别下，如果存在rw依赖，则需要保证两个事务之间的执行顺序为读事务先于写事务，T1→T2的rw依赖要求T1先于T2执行，T2→T1的rw依赖则要求T2先于T1执行，显然这是不可能的，因为在事务的依赖关系中存在一个“环”，如图9所示。

图9  写偏序中的环

在SI隔离级别下，如果出现了写偏序异常，则代表事务的等待图中存在环，因此通过构建事务的等待图并查找等待图中的环，就可以检测写偏序是否存在。

如果发现等待图中有环，则终止环中的某个事务（打破环），这样就可以避免写偏序的发生。

但是查找环的过程需要维护快照相关的信息和事务的推进信息，导致资源的浪费，也降低了系统的性能，因此很多学者在这方面做了大量探索。其中论文Making Snapshot Isolation Serializable提出了如果等待图中出现环，那么这个环中必然包括“危险结构”（Dangerous Structures），这种“危险结构”是出现写偏序的必要非充分条件。

也就是说，有了这种“危险结构”不一定能构成环，但是如果出现了环，那么一定会存在这种“危险结构”，如图10所示。

Definition 3.5 (Dangerous Structures).

We say that the static dependency graph SDG(A) has a dangerous structure if it contains nodes P, Q and R (some of which may not be distinct) such that:

(a) There is a vulnerable anti-dependency edge from R to P

(b) There is a vulnerable anti-dependency edge from P to Q

(c) Either Q = R or else there is a path in the graph from Q to R; that is, (Q, R) is in the reflexive transitive closure of the edge relationship.

                     -- 引自Making Snapshot Isolation Serializable

图10  “危险结构”

02

“危险结构”

在论文Serializable Isolation for Snapshot Databases中基于“危险结构”的定义，提出了一种实现SSI的方法，相比维护等待图的方案，它具有如下优势。

• 能够保证所有事务都在SSI并发策略下执行，不会出现并发异常。
• 不会降低Read的性能，也不会对并发写的性能造成影响。
• 在限定条件下，它的吞吐量非常接近SI的性能，远远好于2PL的性能。
• 可以通过很小的修改就能在SI隔离级别的系统下实现SSI。

这个算法的主要实现方法是：每个事务都保存两个bool类型的变量，分别是inConflict和outConflict。

• T.inConflict变量：如果inConflict的值为true，那么代表有一个事务通过rw依赖指向事务T。
• T.outConflict变量：如果outConflict的值为true，那么代表当前事务T和另一个事务有rw依赖，且事务T是Read事务。

如果T.inConflict和T.outConflict的值都是true，那么代表当前事务既rw依赖其他事务，也被其他事务rw依赖，也就代表当前已经出现了“危险结构”，因此有出现并发异常的可能，这种事务也被称为Pivot事务。

如果这种Pivot事务出现，通常不会终止Pivot事务本身，而是尝试终止Pivot事务两端的事务。

当然“危险结构”不代表一定会出现异常，因此这个算法是偏保守的，有一定的误杀率，但是相比于去找“环”，这种方法的性能好很多，而且误杀率也能够控制在理想的范围内。

论文Serializable Isolation for Snapshot Databases基于上述的数据结构，将rw依赖的检查划分成了两种情况。

• 情况一：读操作读取的不是最新的值，会产生rw依赖。在MVCC系统中，每个数据项都会保存多个历史版本及一个最新版本。当读操作发生时会根据自己的快照（Snapshot）选择读取其中的一个版本，如果读操作可见的不是最新版本，那么读操作的事务和最新版本的事务就会产生rw依赖。如图11所示。

图11  rw依赖的情况一：读历史版本

• 情况二：读操作确实在写操作之前发生也可能会产生rw依赖。例如，在某个事务读取了数据项之后，另一个并发事务对这个数据项做了更新，这种需要借助SIREAD锁来检查rw依赖。SIREAD锁是一种特殊类型的锁，它和数据项上的读写锁不冲突，只是一个记录当前数据项已经被某个事务读取过的标记。当其他事务对数据项做修改（写）操作时，需要对这个数据项加X锁，这时候就可以检查该数据项上是否有SIREAD锁。如果有，就代表发生了rw依赖。需要注意的是，SIREAD锁并不会随着事务结束而释放，而是需要持续到所有的并发事务结束才能释放，如图12所示。

图12  rw依赖的情况二：先读后写

下面分析一下这个方法的伪代码。

//事务开始，目前不存在rw依赖，因此inConflict和outConflict都设置为falsemodified begin(T):    existing SI code for begin(T)    set T.inConflict = T.outConflict = false
//读操作modified read(T, x):    //获得SIREAD锁    get lock(key=x, owner=T, mode=SIREAD)    //如果此时数据项上有写锁（尚未释放证明写事务尚未提交）,    //那么我们读取到的是元组的旧版本，可能会产生rw依赖，    //（如果写事务不提交，则不存在冲突）    if there is a WRITE lock(wl) on x        set wl.owner.inConflict = true        set T.outConflict = true
    existing SI code for read(T, x)
    //逐个检查数据项的新版本，即比当前快照读到的x值更新的数据版本    for each version (xNew) of x     that is newer than what T read:        //新版本的事务必须提交，此时当前事务对新版本的事务构成了rw依赖，如果        //新版本的事务本身对外部的某个事务也构成rw依赖，那么就出现了“危险结构”        if xNew.creator is committed and xNew.creator.outConflict:            abort(T)            return UNSAFE_ERROR
        set xNew.creator.inConflict = true        set T.outConflict = true
//写操作modified write(T, x, xNew):    //获得写锁    get lock(key=x, locker=T, mode=WRITE)

    //如果数据项上还有SIREAD锁，那么代表这个数据项被其他事务r1.owner读取过，    //r1.owner这个事务正在运行或者在事务T开始之后才被提交，就会产生rw依赖    if there is a SIREAD lock(rl) on x      with rl.owner is running      or commit(rl.owner) > begin(T):        //如果当前事务和r1.owner产生了rw依赖，有另一个事务和r1.owner产生了rw依赖，        //那么，就真正出现了“危险结构”，需要终止事务T        if rl.owner is committed and rl.owner.inConflict:            abort(T)            return UNSAFE_ERROR                set rl.owner.outConflict = true        set T.inConflict = true
    existing SI code for write(T, x, xNew)    # do not get WRITE lock again
//提交事务modified commit(T):    //事务T是Pivot事务，终止T    if T.inConflict and T.outConflict:        abort(T)        return UNSAFE_ERROR
    existing SI code for commit(T)    # release WRITE locks held by T    # but do not release SIREAD locks

这个方法被应用在Berkeley DB上，实验证明，它的性能远优于S2PL。

此时，基于rw依赖的SSI理论已经趋于成熟，既有理论支撑，又有实践上的验证。

同时PostgreSQL用户在使用串行化隔离级别时也有解决写偏序异常的需求，这都促成了PostgreSQL在世界范围内首先在SI的基础上实现了真正商业级的SSI。

03

SSI的优化方法

由于PostgreSQL数据库和Berkeley DB的内部实现机制不同，因此PostgreSQL在实现SSI时使用的方法略有不同。不仅如此，PostgreSQL还在原有理论的基础上做了一些优化。

在T1->T2->T3的危险结构中，如果T1是只读事务，那么只有T3的提交时间早于T1获取快照的时间，才可能构成“环”。

证明：假设T1->T2->T3能够导致并发事务构成环，那么必然有一个事务Tn指向T1，由于T1是只读事务，因此，Tn->T1之间不可能是rw依赖或者ww依赖，只可能是wr依赖。wr依赖的定义是T1读到了Tn写入的值，即T1在获取快照的时候，Tn已经提交了。如果Tn提交的时间晚于T1获取快照的时间，Tn写入的值无法被T1读到，这就无法构成环，我们把Tn规约为T3，即可得到T3->T1必须满足T3的提交时间早于T1获取快照的时间，由此得证。

只读事务T1要想构成环，必须要指向一个读写事务T2，而且T1和T2必须是并发事务，假如和只读事务T1并发的事务中都没有产生写操作，也就不可能形成T1->T2的rw依赖，这时候T1中的快照就变成安全快照。如果只读事务中的快照是安全快照，那么就可以释放事务中已经记录的谓词锁，因为这个事务不可能再和其他事务产生rw依赖了。安全快照如图13所示。

图13  安全快照

有了安全快照的概念之后，我们还可以增加延迟事务的概念，用户可以通过“BEGIN TRANSACTION READ ONLY, DEFERRABLE”命令来开启一个延迟事务。

所谓延迟事务指当这个只读事务获得快照后，并不马上执行，而是等待所有的并发事务提交。

如果在等待过程中发生了rw依赖，那么这个快照被废弃，重新获得一个新的快照，并继续等待并发事务提交，直到等待过程中没有rw依赖发生，快照安全，才真正执行事务。

▼

本书摘自《PostgreSQL技术内幕：事务处理深度探索》一书，更多相关内容欢迎阅读此书！

▊《PostgreSQL技术内幕：事务处理深度探索》

张树杰 著

• 深入介绍数据库事务的经典理论、概念、方法
• 结合PostgreSQL的工程实践解读并发控制和故障恢复
• 揭秘日志复制、逻辑解码、Undo日志、快照隔离级别等技术
• 深入解读SSI实现、Zheap存储引擎、2PC等技术
• 源码解析、架构分析、关键细节、案例实现，一应俱全
• 数据库内核研发领域老兵，带你深度探索事务之旅

本书首先分析了PostgreSQL数据库事务的实现机制，包括事务的基本概念、两阶段锁的原理及实现方法、多版本并发控制的原理及实现方法、故障恢复的实现方法等，然后通过介绍物理复制、逻辑复制、Zheap引擎的原理及实现、SSI的实现、两阶段提交的原理及实现，使读者获得了对事务更深入的理解，从而使读者既能了解事务的原理，也能清楚事务的实现细节。

（京东满100减50，快快扫码抢购吧！）

如果喜欢本文欢迎 在看丨留言丨分享至朋友圈 三连

 热文推荐  
书单 | 振聋发聩，撼世经典！
让数据库从业者用实力对美国说不！
真正决定你成败的，是时间管理！
经验之谈：程序员应该如何学好大数据技术

▼点击阅读原文，查看本书详情~