相对乐观和局部悲观是一体两面的关系,识别它的要点就在于是否有全局有效性验证,这也和分布式数据库的架构特点息息相关。但是关于悲观协议,还有很多内容没有提及,下面我们就来填补这一大块空白。
要先跳出来,从并发控制技术整体的分类体系看。
并发控制的分类体系,学术界标准也不一:
狭义乐观协议和其他悲观协议这种分类方式更清晰些,所以就选择“ Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery”中的划分体系。书中一幅图,梳理不同的并发控制协议。
先分为悲观、乐观。因为这里的乐观协议是指狭义乐观并发控制,所以包含内容较少,只有前向乐观并发控制和后向乐观并发控制;而悲观协议又分为基于锁和非锁两大类,其中基于锁的协议是数量最多的。
基于锁的协议显然不只是2PL,还包括有序共享(Ordered Sharing 2PL, O2PL)、利他锁(Altruistic Locking, AL)、只写封锁树(Write-only Tree Locking, WTL)和读写封锁树(Read/Write Tree Locking, RWTL)。但这几种协议在真正的数据库系统中很少使用,所以就不过多介绍了,我们还是把重点放在数据库系统主要使用的2PL上。
2PL就是事务具备两阶段特点的并发控制协议,两阶段指:
加锁阶段严格区别于紧接着的释放锁阶段。
在t1时刻之前是加锁阶段,在t1之后则是释放锁阶段,我们可以从时间上明确地把事务执行过程划分为两个阶段。2PL的关键点就是释放锁之后不能再加锁。而根据加锁和释放锁时机的不同,2PL又有一些变体。
保守两阶段封锁协议(Conservative 2PL,C2PL),事务在开始时设置它需要的所有锁。
严格两阶段封锁协议(Strict 2PL,S2PL),事务一直持有已经获得的所有写锁,直到事务终止。
强两阶段封锁协议(Strong Strict 2PL,SS2PL),事务一直持有已经获得的所有锁,包括写锁和读锁,直到事务终止。SS2PL与S2PL差别只在于一直持有的锁的类型,所以它们的图形是相同的。
理解这几种2PL变体,回想13的Percolator模型。当主锁(Primary Lock)没有释放前,所有的记录上的从锁(Secondary Lock)实质上都没有释放,在主锁释放后,所有从锁自然释放。所以,Percolator也属于S2PL。TiDB的乐观锁机制是基于Percolator的,那么TiDB就也是S2PL。
事实上,S2PL可能是使用最广泛的悲观协议,几乎所有单体数据都依赖S2PL实现可串行化。而在分布式数据库中,甚至需要使用SS2PL来保证可串行化执行,典型的例子是TDSQL。但S2PL模式下,事务持有锁的时间过长,导致系统并发性能较差,所以实际使用中往往不会配置到可串行化级别。这就意味着我们还是没有生产级技术方案,只能期望出现新的方式,既达到可串行化隔离级别,又能有更好的性能。最终,我们等到了一种可能是性能更优的工程化实现,这就是CockroachDB的串行化快照隔离(SSI)。而SSI的核心,就是串行化图检测(SGT)。
SSI是一种隔离级别的命名,最早来自PostgreSQL,CockroachDB沿用了这个名称。它是在SI基础上实现的可串行化隔离。同样,作为SSI核心的SGT也不是CockroachDB首创,学术界早就提出了这个理论,但真正的工程化实现要晚得多。
PostgreSQL在论文“Serializable Snapshot Isolation in PostgreSQL”中最早提出了SSI的工程实现方案,这篇论文也被VLDB2012收录。
串行化理论的核心是串行化图(Serializable Graph,SG)。这图用来分析数据库事务操作的冲突情况。每个事务是一个节点,事务之间的关系则表示为一条有向边。啥关系可表示为边呢?
串行化图的构建规则是这样的,事务作为节点,当一个操作与另一个操作冲突时,在两个事务节点之间就可以画上一条有向边。事务之间的边的分类:
案例看咋用这几条规则构建一个简单的串行化图:
图中共三个事务先后执行:
最终产生一个DAG,能构建出DAG,说明相关事务可串行化执行,无需中断任何事务。
可用SGT验证典型死锁情况。事务T1、T2分别以不同顺序写两个数据项,就会形成死锁:
串行化图体现,显然构成环:
SGT中,WR依赖和WW依赖都与直觉相符,RW反向依赖较难理解。PostgreSQL论文专门描述了一个RW反向依赖场景。
该场景需维护两张表:
同时,还有三个事务T1、T2、T3:
例子很像银行存款系统的日终翻牌。因为T1要报告当天收入,所以要在T3后执行。事务T2记录当天每笔入账,须在T3前执行,这样才能出现在当天报表。三者顺序执行可正常工作,否则异常,如下:
T2先拿到一个批次号x,随后T3执行,批次号关闭后,x这个批次号其实已经过期,但是T2还继续使用x,记录当前的这笔收入。T1正常在T3后执行,此时T2尚未提交,所以T1的报告中漏掉了T2的那笔收入。因为T2使用时过期的批次号x,第二天的报告中也不会统计到这笔收入,最终这笔收入就神奇地消失了。
在理解了这个例子的异常现象后,我们用串行化图方法来验证一下。我们是把事务中的SQL抽象为对数据项的操作,可以得到下面这张图。
图中batch是指批次号,reps是指收入情况。
接下来,我们按照先后顺序提取有向边,先由T2.R(batch) -> T3.W(batch),得到T2到T3的RW依赖;再由T3.W(batch)->T1.R(batch),得到 T3到T1的WR依赖;最后由T1.R(reps)->T2.W(reps),得到T1到T2的RW依赖。这样就构成了下面的串行化图。
显然这三个事务之间是存在环的,那么这三个事务就是不能串行化的。
这个异常现象中很有意思的一点是,虽然T1是一个只读事务,但如果没有T1的话,T2与T3不会形成环,依然是可串行化执行的。这里就为我们澄清了一点:我们直觉上认为的只读事务不会影响事务并发机制,其实是不对的。
RW反向依赖是特别存在,在于传统的锁机制无法记录这种情况。因此论文“Serializable Snapshot Isolation in PostgreSQL”提出,增加一种锁SIREAD,记录快照隔离(SI)上所有执行过的读操作(Read),从而识别RW反向依赖。
SIREAD并不是锁,只是一种标识。但这方案面临困境:读操作涉及数据范围太大,跟踪标识带来的成本可能比S2PL还高,也就无法达到最初目标。
CockroachDB做了关键设计,读时间戳缓存(Read Timestamp Cache,RTC)。
执行任何读取操作时,操作的时间戳都会被记录在所访问节点的本地RTC。当任何写操作访问这节点时,都以将要访问的Key为输入,向RTC查询最大的读时间戳(MRT),如MRT>这写入操作的时间戳,继续写入就会形成RW依赖。这时须终止并重启写入事务,让写入事务拿到一个更大的时间戳重新尝试。
RTC是以Key范围组织读时间戳。这样,当读取操作携带了谓词条件如where子句,对应操作就是个范围读取,会覆盖若干Key,那整个Key的范围也可被记录在RTC。这样处理好处是,可兼容一种特殊情况。
如事务T1第一次范围读取(Range Scan)数据表,where“>=1 and <=5”,读取到1、2、5,T1完成后,事务T2在该表插入4,因为RTC记录范围区间[1,5],所以4也可被检测出存在RW依赖。这个地方,有点像MySQL间隙锁的原理。
RTC是个大小有限,采用LRU淘汰算法的缓存。达存储上限时,最老的时间戳被抛弃。为应对缓存超限,会将RTC中出现过的所有Key上最早的那个读时间戳记录,作为低水位线(Low Water Mark)。如一个写操作将要写的Key不在RTC中,则会返回该低水位线。
SGT的运行机制和传统的S2PL一样属于悲观协议。但SGT没有锁的管理成本,所以性能比S2PL更好。
CockroachDB基于SGT理论进行工程化,使可串行化真正成为生产级可用的隔离级别。从整体并发控制机制看,CockroachDB和上一讲的TiDB一样,虽然在局部看是悲观协议,但因为不符合严格的VRW顺序,所以在全局来看仍是一个相对乐观的协议。
这种乐观协议同样存在[第13讲]提到问题,所以CockroachDB也在原有基础上进行了改良,通过增加全局的锁表(Lock Table),使用加锁的方式,先进行一轮全局有效性验证,确定无冲突的情况下,再使用单个节点的SGT。
串行化理论,只有当相关事务形成DAG图时,这些事务才是可串行化的。这个理论不仅适用于SGT,2PL的最终调度结果也同样是DAG图。在更大范围内,批量任务调度时DAG也同样被作为衡量标准,如Spark。
参考
看到SGT使用了DAG检测时,就想到Spark和“环路检测”。所以,知识学到最后,还是需要从底层和基础去探寻答案。
Q:读时间戳缓存RTC,是为防止RW反依赖,这里读时间戳比写时间戳大的判定,是否和分布式数据库的时钟机制有关,如果授时不存在误差,是否就无需RTC设计?
A:RTC设计是为简化SIREAD,不是因为时间误差,就算用TSO没有时间误差,也需要RTC。
Q:有数据库教材将MVCC作为一种重要的并发控制技术,与乐观协议、悲观协议并列。如何理解MVCC与乐观协议、悲观协议的关系呢?
MVCC与乐观、悲观协议无直接关系,因为乐观悲观本质区别在“何时校验冲突”,而 MVCC 是另一层次技术,对冲突检验的时间点没任何影响,不论乐观悲观协议,都可以有 MVCC。
Q:MVCC可看作单个数据的无锁结构吗?乐观锁和悲观锁是全局事务级别的并发控制。
A:MVCC是一种数据库并发控制策略,为每个数据行维护多版本来实现高并发。每个版本都有一个时间戳,因此不同事务可同时访问同一行数据的不同版本,避免了锁竞争和阻塞。
而乐观锁/悲观锁是在事务级别实现并发控制的策略:
因此,MVCC和乐观锁、悲观锁都是用于实现并发控制的策略,但MVCC更适于单个数据的无锁结构,且可提供更好并发性能。