您好、欢迎来到现金彩票网!
当前位置:秒速飞艇 > 提交事务 >

干货 万字长文带你回顾OCC的前世今生

发布时间:2019-06-19 00:54 来源:未知 编辑:admin

  这篇文章带着大家一起概要描述了当前NewSQL的发展趋势及使用到的相关并发控制技术(可以点击文章链接回顾)。今天我们将为大家重磅带来该系列的续篇,以时间轴的方式带你一起全面回顾OCC在学术界及工业界的发展历程。

  OCC(Optimstic Concurrency Control),从广义上理解,OCC表示一种乐观并发控制的思想,只在事务提交时对事务是否符合串行化进行验证;而悲观并发控制(Pessimistic Concurrency Control)会对事务执行过程中的每个操作进行串行化验证。在这一思想的指导下,应用层的乐观锁也属于OCC;从狭义上理解,OCC特指一个具体的不依赖加锁的并发控制技术,与2PL/TO/MVCC等处于同一个概念层次,属于数据库内核层。本文以下提到的OCC指代的是狭义的概念。

  本文是该系列文章的第二篇,下一篇将致力于为你解读FoundationDB如何实现OCC。敬请关注蚂蚁金服OceanBase微信账号了解更多!

  上一篇提到了苹果新近开源的FoundationDB基于NoSQL+ACID架构实现了一个支持事务语义的NoSQL数据库,并由此简单回顾了一下开源社区从NoSQL到NewSQL运动的转变,同时强调了Google在这一变革中起到的决定性作用,最后列出了当前几种流行的NewSQL生产级分布式数据库所使用的并发控制技术及支持的隔离级别,可以明显看出FoundationDB在并发控制技术上的独树一帜。

  本篇为该系列文章的续篇,以时间轴的方式对不同时期的有代表性的论文(从理论研究、原型系统、生产系统三个维度分类)进行了梳理,带你简要回顾一下OCC在学术界及工业界的发展历程。

  这里需要先对OCC(Optimistic Concurrency Control)指代的概念做一个说明,从广义上理解,OCC表示一种乐观并发控制的思想,只在事务提交时对事务是否符合串行化进行验证;而悲观并发控制(Pessimistic Concurrency Control)会对事务执行过程中的每个操作进行串行化验证。

  在这一思想的指导下,应用层的乐观锁也属于OCC;从狭义上理解,OCC特指一个具体的不依赖加锁的并发控制技术,与2PL/TO/MVCC等处于同一个概念层次,属于数据库内核层。本文以下提到的OCC指代的是狭义的概念。

  本文重点在于沿着OCC发展的时间线的梳理,由于相关论文较多,作者无法深入探究每篇论文的详细内容,仅描述了论文中的大致思想,可能也有不全面或错误的地方,感兴趣的同学可以研读论文原著。

  OCC技术最早由CMU大学的H.T. KUNG教授提出,当时数据库并发控制研究的热点是2PL,作者直接列举了基于锁的并发控制协议的五宗罪:

  1. 加锁协议开销大,对于不会改变数据库约束完整性的只读事务也需要加读锁保护以防止别人修改;对于可能造成死锁的加锁协议还需要额外增加死锁检测开销

  3. 在持有锁的情况下可能会等待I/O操作,会大幅降低系统整体的并发吞吐量

  4. 加锁事务回滚时必须持有锁,直到事务回滚结束,降低了系统整体的并发吞吐量

  5. 只有在最坏情况下才需要加锁;很多真实的应用场景往往是高并发低竞争的

  作者据此提出了一种新的乐观并发控制方法用于解决上述问题(所谓的乐观是针对并发事务冲突概率极低的工作负载场景),该方法将一个事务的生命周期划分为三个阶段:

  假设系统中每个事务能够被赋予全局唯一的事务号,则有事务号Ti和Tj,且TiTj,可以将系统内是否存在一个与事务号顺序等价的并发事务调度序列作为可串行化标准,则检查事务Tj是否符合可串行化(即Ti在Tj之前完成),需满足如下三种条件之一:

  2、Ti的写集与Tj的读集不相交,且Ti在Tj开始写入阶段前完成写入阶段

  3、Ti的写集与Tj的读集和写集都不相交,且Ti在Tj完成读取阶段前完成读取阶段

  ⑤ 不相交,则验证成功,执行写入阶段(如果是只读事务无需执行)并递增提交事务号

  ① 在临界区内获取当前已提交的事务号/获取当前活跃事务列表/将自身加入活跃事务列表

  ③ 验证活跃事务(这些活跃事务均已完成读取阶段,读集和写集不会再发生变化,可理解为进入验证的事务列表)的写集与待验证事务的读集和写集是否相交

  ④ 相交,则发现冲突,在临界区内将本事务从活跃事务中去除并中止待验证事务

  根据上述规则,需要检查长事务开始时未提交的事务的写集。由于数据库系统只能维护有限的事务写集,作者建议只维护最近事务的写集,如果验证时无法找到事务号对应的写集,则中止待验证事务并重新执行。

  验证失败时事务需要中止并重新执行,存在一种极端情况使得事务持续地中止并重新执行,作者建议记录事务的失败验证次数,若超过一定阈值,则在临界区内重新执行事务,彻底排除其它并发事务的干扰。

  显然,上述方案都是针对单数据版本的集中化数据库系统,在分布式数据库系统中的OCC算法还有待后人扩展。

  这两篇论文提出了将原集中化数据库系统中的OCC应用到分布式数据库系统中的解决方案,第一篇论文的内容始终无法找到,本文猜测其基本思想为:

  作者紧接着在第二篇论文中指出了OCC在分布式系统中面临的两个关键问题及可能的解决方案:

  对论文[1]中OCC的串行版本进行了扩展,由此归类出两种OCC验证方案:

  这篇论文总体看来对OCC的评价是负面的,但罗列出的通用问题也为后续的OCC研究者指出了改进的方向。

  这篇论文给出了OCC在分布式系统实现层面的解决方案,系统采用多版本存储,数据对象的粒度为一个页面,事务流程简要描述如下:

  选取全局读时间戳,保证读取阶段能够看到一致的数据库视图。对于只读事务,在读取阶段结束后就可以提交。

  3、各结点统一使用该全局时间戳,基于论文[1]中提到的并行验证版本进行验证

  该论文从原型实现验证了OCC落地的可行性,并首次使用全局时间戳解决OCC读取阶段数据库视图不一致及全局事务中子事务串行化验证标准不一致的问题。

  论文认为[1]中的OCC是将事务进入验证阶段的时间作为事务提交时间戳并据此调度事务的可串行化,这会导致一些非必要的事务中止,提出一种在验证阶段基于访问数据的时间戳版本动态调整事务提交时间戳的方法,其基本思想如下:

  ① 事务执行过程中访问任意结点上的数据时都需要传递客户端上的事务提交时间戳区间信息

  ③ 结点将客户端提交时间戳区间信息与本地维护的提交时间戳区间求交集得到最新的提交时间戳区间信息

  ⑧ 客户端将回传信息与当前信息作交集得到最新的时间戳区间(通过这种方式使得结点能够感知到事务在其它结点上的依赖信息,便于早发现不符合串行化调度的事务)

  2、 验证和写入阶段(由于其它事务的读写操作与当前事务的验证阶段都会修改事务的时间戳区间,所以结点上的读写操作与验证时的调整操作需要互斥)

  ① 客户端向各参与结点发送验证/提交消息(消息中包含验证事务的最新提交时间戳区间)

  作者为了发现串行化冲突,需要结点在验证阶段开启时将本结点的事务时间戳区间信息广播到所有结点,等到全部结点回复后才开始对事务进行串行化检查,在分布式系统中人为设置了同步点,对扩展性会有一定的影响。

  其它关于OCC的研究主要集中在与传统并发控制技术的性能对比[5],如何减少不必要的事务中止率[9],同时支持2PL与OCC[4],如何防止事务饿死[10]及OCC在实时数据库系统中的应用[11],可以看出,这一时期OCC基本处于学术研究及原型验证阶段,当时的数据库工业界,如Oracle、DB2,还是使用了主流的并发控制技术,如2PL、MVCC。

  随着硬件技术的发展,如论文[12][19]中所述,多核(几十、几百)、大内存(T级别)的单节点配置已在市场上出现,意味着大多数OLTP场景下的数据处理可以完全运行在内存中,SAP HANA、MemSQL、TimesTen、SolidDB、Hekaton等内存数据库也应运而生。

  随着互联网应用的兴起,标榜着高可靠、高可用、高可扩展的NoSQL运动席卷而来,运行环境也由大型机过渡到分布式集群、多数据中心、多可用区等;NoSQL系统虽然实现了承诺的目标,但其不支持SQL语言、缺乏强一致性的短板一直备受开发人员的抱怨,于是NewSQL系统又进入了人们的视野,其主打口号是既具有NoSQL的所有优点并且还支持SQL语言及ACID事务,如F1、Spanner、CockroachDB、TiDB、OceanBase等。

  与传统并发控制方法相比,OCC的优点是在高资源竞争、低数据竞争场景下,能够减少事务运行同步开销,避免死锁,支持更高的事务吞吐率;缺点是在高数据冲突场景下有较高的事务中止率,浪费计算资源(2PL在此场景下事务中止率也很高,但能够提前中止,不用等到事务提交时)。

  上述两种场景,一个关注单机事务吞吐量;另一个关注分布式事务吞吐量,其性能优化目标可以统一描述为在硬件资源充足的情况下如何提高事务吞吐量。节约资源已不再是重点,减少系统同步,提高资源利用率才是核心问题。尤其是在分布式计算环境下,网络交互的延迟或异常容易导致2PL协议可能长时间持有锁从而导致系统整体事务吞吐率降低或死锁。OCC的价值在新的数据库基础设施环境上又获得了学术界与工业界的重视。

  Megastore是少有的在内核层实现OCC的生产级分布式数据库系统,在Entity Group的数据分区级别使用MVOCC实现了串行化隔离级别的事务,同一分区一次只能执行一个事务,分布多副本间可以并发执行事务。一个OCC事务三个阶段的实现大致描述如下:

  ② 从多数派副本中获取最新事务提交时间戳及事务日志的位置(可以通过查询本地coordinator中副本的数据状态做优化)

  ③ 选择一个合适的副本(综合考虑本地性、响应时间、事务提交时间等),使用Paxos协议同步事务日志并将其应用到本地Bigtable中

  ④ 若选择了本地副本,则异步更新coordinator中副本数据状态为有效

  ④ 发起一次完整的两阶段Paxos协议实例(可以优化为一阶段Paxos协议),一个事务日志位置只能由一个事务提交成功。如果成功,则将未成功接受当前事务日志的副本所对应的coordinator中的数据状态设置为失效,通知应用事务已提交;如果失败(prepare阶段发现提交的内容与达成一致的内容不匹配),则终止事务并重新执行

  由上述流程可以看出,Megastore将事务局限在一个EG且只能串行化执行,并发冲突的控制粒度在事务级别,导致事务吞吐率非常低。虽然论文[15]中提出了一种提高Megastore事务提交吞吐量的可能方案,但Google内部最终还是放弃了Megastore,转而使用了Spanner(使用MV2PL并发控制技术),因为Spanner通过2PL+2PC实现了跨分区的事务。

  真正把OCC在生产系统中落地的是内存数据库Hekaton,论文使用全内存的无锁哈希表存储多版本数据,数据的访问全部通过索引查找实现,一个OCC事务的生命周期实现如下:

  ① 获取事务开始时的当前时间作为读时间戳并赋予一个唯一的事务号,事务状态设置为active

  ② 在事务处理的过程中维护读集(指向读版本的指针)、写集(指向写版本的指针)、扫描集(重新执行扫描时需要的信息,如扫描条件)

  ② 读集有效性验证,检查读集中的版本是否依然可见;重新执行扫描集检查是否存在幻读

  ② 如果中止,将新数据的begin域设置为无效,尝试将旧数据的end域设置为无效(如果已被其它事务更新则忽略)

  ③ 处理提交依赖,如果提交,则减少依赖该事务的其它事务的提交依赖计数;如果中止,则通知依赖该事务的其它事务中止

  F1是Google内部研发的分布式关系数据库,存储层基于Spanner,自建SQL层,用于Google最重要的广告业务。F1在Spanner之上基于行级的修改时间戳列实现了乐观事务并将其设置为默认配置,论文提到使用乐观事务有如下优缺点:

  其中关于OCC优点的描述来自生产级分布式环境运维的最佳实践经验,虽然只是应用层的简单实现,但也从另一方面验证了OCC在现代分布式数据库环境中的技术价值。

  这篇论文可以称为是为OCC摇旗呐喊的战斗檄文。论文首先提出了事务级云存储系统的概念,有代表性的系统如工业界的Spanner、学术界的Calvin、开源界的MySQL Cluster。与传统事务级云数据库的区别在于更加透明的数据分区,包括自动化的分区拆分、合并、迁移、负载均衡,这使得高效的跨结点分布式事务成为一个必选功能。

  当前实现跨结点分布式事务的并发控制技术要么是2PL(Spanner、MySQL Cluster),要么是静态锁(Calvin,对事务操作进行静态分析后提前加锁),而OCC仅在应用层或Megastore中有所应用。OCC没有被普遍使用的原因有如下两点:

  OCC在这种场景下是有技术优势的,因此,论文致力于实现一个消除2PC中的锁机制且大幅降低事务误中止率的分布式数据库系统MaaT。MaaT的理论基础基于论文[8]并在系统实现上进行了优化,其基本思想如下:

  ① 在事务请求结点上分配一个全局唯一事务号,并在内存事务表中初始化事务信息(提交时间戳区间设置为0到正无穷,状态设置为running)

  ② 事务执行过程中第一次访问任意远程结点上的数据时都需要在结点本地的内存事务表中建立事务相关初始信息

  ① 客户端发送预写/验证消息到所有相关数据服务器(读写涉及到的服务器),消息中包括与服务器相关的读集、写集及在读取阶段从服务器获取的信息(所有在读对象上加写锁的活跃事务号及最大写时间戳)

  ③ 验证(保证事务的串行化顺序按提交时间戳排序,通过调整事务提交时间戳区间的上下限实现,调整的原则为尽量减少事务中止率)

  ④ 验证结束后,如果验证事务的提交时间戳区间有效(下限小于等于上限),则将事务状态改为validated;否则,将事务状态改为aborted

  ② 如果所有结点均返回committed,则计算所有提交时间戳区间的交集,区间无效,则事务最终状态为aborted;否则事务最终状态为committed,此时客户端需要从有效区间中选取任意的时间戳作为该事务的提交时间戳

  ③ 客户端向相关数据结点发送事务提交或中止消息,提交消息中包含更新数据及确定的提交时间戳

  ④ 对于abort消息,数据结点将本地事务表中的事务状态改为aborted,删除该事务在数据对象上加过的锁并记录事务中止日志

  ⑤ 对于committed消息,数据结点将本地事务表中的事务状态改为committed,提交时间戳区间设置为客户端确定的时间戳,删除该事务在数据对象上加过的锁并记录事务提交日志

  ⑥ 对于读集中的数据对象,如果事务提交时间戳大于读对象的最大读时间戳,则将读对象的最大读时间戳设置为事务提交时间戳

  ⑦ 对于写集中的数据对象,如果事务提交时间戳大于写对象的最大写时间戳,则将写对象的最大写时间戳设置为事务提交时间戳并修改写对象的内容

  论文提出的OCC实现方案被2017年的VLDB论文[21]作为测试OCC性能的参考实现,间接证明这里提出的OCC算法已经得到了学术界的认可,虽然论文[21]中对新OCC算法的性能与其它并发控制算法的比较仍然没有正面评价,但性能瓶颈已经转移到网络传输及CPU计算消耗,事务中止率及同步开销已成为性能瓶颈的次要因素,OCC的扩展性得到了提高。

  Centiman是一个在云环境基于NoSQL存储层+事务处理层(OCC)实现的具备串行化事务隔离级别的KV系统,由KV存储、事务处理子系统(包括处理结点和验证结点)、全局总控结点及客户端组成。

  1. 处理结点维护一个本地的已应用事务提交时间戳(watermark,此时间戳之前的数据更新已写入kv存储)及其它节点已应用事务提交时间戳的缓存(缓存定期异步更新)

  2. 每次读操作读取最新版本的kv,处理结点会计算最新的watermark时间(取全局最小),将key、version、watermark记入读集;写入操作需将kv缓存到处理结点的事务私有内存空间并将key记入写集

  1. 只读和读写事务都需要走验证流程(优化:处理结点若发现待验证事务的所有读时间戳都小于事务第一次读时的watermark,则直接向客户端返回提交)

  3. 将执行阶段记录的读集、写集按照key的某种分片规则分别发送到对应的验证结点,同时将事务私有内存中的数据异步写日志

  4. 每个验证节点维护一个滑动时间窗口,小于滑动时间窗口到来的验证请求则直接返回验证失败;落在滑动窗口内的验证请求按照事务提交时间戳顺序进行处理并持续推进滑动窗口

  5. 采用BOCC算法进行验证,对于事务在某个分片验证节点读集中的每个key,在验证结点缓存的事务写集中查找所有在读key时间戳和待验证事务提交时间戳之间提交的事务并验证读key是否与已提交事务的写集冲突 (优化:如果读key时间戳小于记录的watermark时间戳,则冲突检查区间可以缩小为在watermark时间戳和待验证事务提交时间戳之间)

  6. 若冲突,则中止事务;否则,将待提交事务的写集缓存在验证节点用于后续新事务的验证并提交事务

  7. 如果所有相关验证结点都同意提交事务,则发起验证的处理结点写提交日志并通知客户端,转入写入阶段;否则直接通知客户端事务已中止(可能存在有些验证结点认为应该提交,有些验证结点认为应该终止的状态,虽然事务整体是终止状态,但部分验证结点会存在冲突误判,论文中也是依赖watermark机制尽量减少误判)

  1. 处理结点将事务本地内存中的更新内容写入kv存储(写入过程不要求保证原子性,允许其它事务读到部分写入的新值;通过kv存储的MVCC机制保证提交时间戳靠后的事务写入的数据不会被提交时间戳靠前的事务写入的数据覆盖)

  2. 待全部写入成功后,更新本地watermark并异步记录事务已完成日志

  这个系统的实现架构是具有一定代表性的,所有不支持ACID事务的NoSQL系统都可以参照此原型架构实现串行化事务隔离级别,后续我们要研究的FoundationDB架构也与此类似,当然生产环境的数据库还会考虑更具体的问题,比如幻读的处理、性能优化等。

  至此,本文列举了OCC在这一时期在学术及工业界的主要结果,可以看出主要是性能优化,扩展性提高及生产级系统的实践。这里也忽略了一些有代表性的OCC系统,比如Percolator[13]、Silo[17],因为这些系统在并发控制实现中使用了锁机制并存在写读阻塞的情况,虽然可以降低事务中止率,但却违背了OCC读写不阻塞、没有死锁的理念。

  相比于前世理论研究的玩具,应用场景的缺乏,今生在内存及分布式数据库场景的落地,理论与工业界不断地性能优化等方面屡有建树,其技术带来的实际使用价值正越来越多地得到系统架构设计人员的认可,尤其是在跨分区、跨数据中心、跨地域分布式事务[22],实现串行化隔离级别等现今分布式数据库尚未深入触碰的领域有着巨大的挖掘潜力。

  本文按照时间线简要回顾了OCC从诞生、理论研究、原型系统验证到生产系统落地的发展脉络,从中可以看出OCC技术从1980年代初发展至今将近40年的时间了,一路走来磕磕绊绊,从不适用于传统单机数据库,到在内存数据库中落地生根;从不适用于分布式数据库,到完美实现在NoSQL分布式数据库上支持ACID事务,甚至在跨分区事务、跨地域分布式系统的研究中也体现出了巨大的优势,有理由相信OCC技术的乐观、尽量减少事务同步开销的理念在未来的云环境中会有更多的运用。

  在梳理OCC发展历程的过程中,笔者也逐渐总结出从技术角度应该如何分析实现了OCC的分布式数据库系统(仍有待完善):

  把OCC在生产系统中落地的只有Microsoft的内存数据库Hekaton和Google的分布式KV数据库Megastore。虽然论文[14]、[15]、[16]对Megastore、Hekaton及相关的OCC进行了原理性的概要描述,但还是无法从代码实现细节上对OCC落地时可能遇到的实际问题进行解惑。好在苹果今年4月份开源了FoundationDB(又一个使OCC落地的新军),让码农有机会从代码实现层面上更详细地了解如何将OCC落地。

  本文是该系列文章的第二篇,下一篇将致力于为你解读FoundationDB如何实现OCC。敬请期待!

http://toytownquilts.com/tijiaoshiwu/353.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有