川菜餐馆网站建设模板美食餐厅企业建站php源码程序,常德网站建设套餐报价,scratch网站开发,强的小企业网站建设事务隔离是数据库系统设计中根本的组成部分#xff0c;本文主要从标准层面来讨论隔离级别的发展历史#xff0c;首先明确隔离级别划分的目标#xff1b;之后概述其否定之否定的发展历程#xff1b;进而引出 Adya给出的比较合理的隔离级别定义#xff0c;最终总结隔离标准一…事务隔离是数据库系统设计中根本的组成部分本文主要从标准层面来讨论隔离级别的发展历史首先明确隔离级别划分的目标之后概述其否定之否定的发展历程进而引出 Adya给出的比较合理的隔离级别定义最终总结隔离标准一路走来的思路。
目标
事务隔离是事务并发产生的直接需求最直观的、保证正确性的隔离方式显然是让并发的事务依次执行或是看起来像是依次执行。但在真实的场景中有时并不需要如此高的正确性保证因此希望牺牲一些正确性来提高整体性能。通过区别不同强度的隔离级别使得使用者可以在正确性和性能上自由权衡。随着数据库产品数量以及使用场景的膨胀带来了各种隔离级别选择的混乱数据库的众多设计者和使用者亟需一个对隔离级别划分的共识这就是标准出现的意义。一个好的隔离级别定义有如下两个重要的目标
正确每个级别的定义应该能够将所有损害该级别想要保证的正确性的情况排除在外。也就是说只要实现满足某一隔离级别定义就一定能获得对应的正确性保证。实现无关常见的并发控制的实现方式包括锁、OCC以及多版本 。而一个好的标准不应该限制其实现方式。
ANSI SQL标准(1992)基于异象
1992年ANSI首先尝试指定统一的隔离级别标准其定义了不同级别的异象(phenomenas) 并依据能避免多少异象来划分隔离标准。异象包括
脏读Dirty Read: 读到了其他事务还未提交的数据不可重复读Non-Repeatable/Fuzzy Read由于其他事务的修改或删除对某数据的两次读取结果不同幻读Phantom Read由于其他事务的修改增加或删除导致Range的结果失效如where 条件查询。
通过阻止不同的异象发生得到了四种不同级别的隔离标准 ANSI SQL标准看起来是非常直观的划分方式不想要什么就排除什么并且做到了实现无关。然而现实并不像想象美好。因为它并不正确。
A Critique of ANSI(1995)基于锁
几年后微软的研究员们在A Critique of ANSI SQL Isolation Levels一文中对ANSI的标准进行了批判指出其存在两个致命的问题
1不完整缺少对Dirty Write的排除
ANSI SQL标准中所有的隔离级别都没有将Dirty Write这种异象排除在外所谓Dirty Write指的是两个未提交的事务先后对同一个对象进行了修改。而Dirty Write之所以是一种异象主要因为他会导致下面的一致性问题
H0: w1[x] w2[x] w2[y] c2 w1[y] c1这段历史中假设有相关性约束xyT1尝试将二者都修改为1T2尝试将二者都修改为2顺序执行的结果应该是二者都为1或者都为2但由于Dirty Write的发生最终结果变为x2y1不一致。
2歧义
ANSI SQL的英文表述有歧义。以Phantom为例如下图历史H3
H3r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1假设T1根据条件P查询所有的雇员列表之后T2增加了一个雇员并增加了雇员人数值z之后T1读取雇员人数z最终T1的列表中的人数比z少不一致。但T1并没有在T2修改链表后再使用P中的值是否就不属于ANSI中对Phantom的定义了呢这也导致了对ANSI的表述可能有严格和宽松两种解读。对于Read Dirty和Non-Repeatable/Fuzzy Read也有同样的问题。
那么如何解决上述两个问题呢Critique of ANSI的答案是宁可错杀三千不可放过一个即给ANSI标准中的异象最严格的定义。Critique of ANSI改造了异象的定义
P0: w1[x]…w2[x]…(c1 or a1) (Dirty Write)P1: w1[x]…r2[x]…(c1 or a1) (Dirty Read) P2: r1[x]…w2[x]…(c1 or a1) (Fuzzy or Non-Repeatable Read) P3: r1[P]…w2[y in P]…(c1 or a1) (Phantom)此时定义已经很严格了直接阻止了对应的读写组合顺序。仔细可以看出此时得到的其实就是基于锁的定义:
Read Uncommitted阻止P0整个事务阶段对x加长写锁Read Commited阻止P0P1短读锁 长写锁Repeatable Read阻止P0P1P2长读锁 短谓词锁 长写锁Serializable阻止P0P1P2P3长读锁 长谓词锁 长写锁
问题本质
可以看出这种方式的隔离性定义保证了正确性但却产生了依赖实现方式的问题太过严格的隔离性定义阻止了Optimize或Multi-version的实现方式中的一些正常的情况
针对P0Optimize的实现方式可能会让多个事务各自写自己的本地副本提交的时候只要顺序合适是可以成功的只在需要的时候才abort但这种选择被P0阻止针对P2只要T1没有在读x后续没有与x相关的操作且先于T2提交。在Optimize的实现中是可以接受的却被P2阻止。
回忆Critique of ANSI中指出的ANSI标准问题包括Dirty Write和歧义其实都是由于多Object之间有相互约束关系导致的如下图所示图中黑色部分表示的是ANSI中针对某一个异象描述的异常情况灰色部分由于多Object约束导致的异常部分但这部分在传统的异象定义方式中并不能描述因此其只能退而求其次扩大限制的范围到黄色部分从而限制了正常的情况。 由此可以看出问题的本质由于异象的描述只针对单个object缺少描述多object之间的约束关系导致需要用锁的方式来作出超出必须的限制。相应地解决问题的关键要有新的定义异象的模型使之能精准的描述多object之间的约束关系从而使得我们能够精准地限制上述灰色部分而将黄色的部分解放出来。Adya给出的答案是序列化图。
A Generalized Theory(1999)基于序列化图
Adya在Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions中给出了基于序列化图得定义思路为先定义冲突关系并以冲突关系为有向边形成序列化图再以图中的环类型定义不同的异象最后通过阻止不同的异象来定义隔离级别。
序列化图Direct Serialization Graph, DSG
序列化图是用有向图的方式来表示事务相互之间的依赖关系图中每个节点表示一个事务有向边表示存在一种依赖关系事务需要等到所有指向其的事务先行提交如下图所示历史的合法的提交顺序应该为T1T2T3 这里的有向边包括三种情况
写写冲突wwDirectly Write-Depends表示两个事务先后修改同一个数据库Object(w1[x]…w2[x]...)先写后读冲突wrDirectly Read-Depends一个事务修改某个数据库Object后另一个对该Object进行读操作w1[x]…r2[x]...先读后写冲突rwDirectly Anti-Depends一个事务读取某个Object或者某个Range后另一个事务进行了修改r1[x]…w2[x]… or r1[P]…w2[y in P]基于序列化图的异象定义
根据有向图的定义我们可以将事务对不同Object的依赖关系表示到一张同一张图中而所谓异象就是在图中找不到一个正确的序列化顺序即存在某种环。而这种基于环的定义其实就是将基于Lock定义的异象最小化到图中灰色部分
1P0(Dirty Write) 最小化为 G0(Write Cycles)序列化图中包含两条边都为ww冲突组成的环如H0
H0: w1[x] w2[x] w2[y] c2 w1[y] c1可以看出T1在x上与T2写写冲突T2又在y上与T1写写冲突形成了如下图所示的环。 2P1(Dirty Read) 最小化为 G1Dirty Read异象的最小集包括三个部分G1a(Aborted Reads)读到的uncommitted数据最终被abortG1b(Intermediate Reads) 读到其他事务中间版本的数据以及G1c(Circular Information Flow)DSG中包含ww冲突和wr冲突形成的环。
3P2(Fuzzy or Non-Repeatable Read) 最小化为 G2-item(Item Anti-dependency Cycles) DSG中包含环且其中至少有一条关于某个object的rw冲突
4P3(Phantom) 最小化为 G2(Anti-dependency Cycles): DSG中包含环并且其中至少有一条是rw冲突仍然以上面的H3为例
H3r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1T1在谓词P上与T2 rw冲突反过来T2又在z上与T1wr冲突如下图所示 对应的隔离级别
通过上面的讨论可以看出通过环的方式我们成功最小化了异象的限制范围那么排除这些异象就得到了更宽松的通用的隔离级别定义
PL-1Read Uncommitted阻止G0PL-2Read Commited阻止G1PL-2.99Repeatable Read阻止G1G2-itemPL-3Serializable阻止G1G2
其他隔离级别
除了上述的隔离级别外在正确性的频谱中还有着大量空白也就存在着各种其他隔离级别的空间商业数据库的实现中有两个比较常见
1Cursor Stability
该隔离界别介于Read Committed和Repeatable Read之间通过对游标加锁而不是对object加读锁的方式避免了Lost Write异象。
2 Snapshot Ioslation
事务开始的时候拿一个Start-Timestamp的snapshot所有的操作都在这个snapshot上做当commit的时候拿Commit-Timestamp检查所有有冲突的值不能再[Start- Timestamp, Commit-Timestamp]被提交否则abort。长久以来Snapshot Ioslation一直被认为是Serializable但其实Snapshot Ioslation下还会出现Write Skew的异象。之后的文章会详细介绍如何从Snapshot Ioslation出发获得Serializable。
总结
对于事务隔离级别的标准数据库的前辈们进行了长久的探索
ANSI isolation levels定义了异象标准并根据所排除的异象定义了Read Uncommitted、Read Committed、Repeatable Read、Serializable四个隔离级别A Critique of ANSI SQL Isolation Levels认为ANSI的定义并没将有多object约束的异象排除在外并选择用更严格的基于Lock的定义扩大了每个级别限制的范围Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions认为基于Lock的定义过多的扩大了限制的范围导致正常情况被排除在外从而限制了Optimize类型并行控制的使用指出解决该问题的关键是要有模型能准确地描述这种多Object约束并给出了基于序列化图的定义方式将每个级别限制的范围最小化。
参考
A History of Transaction Histories
ANSI isolation levels
A Critique of ANSI SQL Isolation Levels
Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions
Generalized Isolation Level Definitions
原文链接
本文为阿里云原创内容未经允许不得转载。
