前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PostgreSQL数据库的SSI实现

PostgreSQL数据库的SSI实现

作者头像
博文视点Broadview
发布2023-05-06 19:14:21
8350
发布2023-05-06 19:14:21
举报

👆点击“博文视点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原则。

代码语言:javascript
复制
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依赖的情况二:先读后写

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

代码语言:javascript
复制
//事务开始,目前不存在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,快快扫码抢购吧!)

代码语言:javascript
复制
如果喜欢本文欢迎 在看丨留言丨分享至朋友圈 三连

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

▼点击阅读原文,查看本书详情~
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-09-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 博文视点Broadview 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
数据库
云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档