月度归档:2016年09月

两阶段提交的工程实践

两阶段提交(2 Phase Commit简称2PC)协议是用于在多个节点之间达成一致的通信协议,它是实现“有状态的”分布式系统所必须面对的经典问题之一。本文通过对比经典2PC协议,和Google工程实践的基础上,分析一种优化延迟的2PC协议。为了方便说明,本文主要针对分布式数据库中,跨域sharding2PC方案的讨论。主要参考文献:Gray J, Lamport L. Consensus on transaction commit[J]. ACM Transactions on Database Systems (TODS), 2006, 31(1): 133-160.

  • 经典两阶段提交概述

    • 先来回顾下经典的2PC协议,有两个角色:一个协调者(coordinator)和若干参与者(participant),协议执行可以分为如下几个阶段:

      • 预处理阶段:严格来说,预处理阶段并不是2PC的一部分,在实际的分布式数据库中,这个阶段由协调者向若干参与者发送SQL请求或执行计划,包括获取行锁,生成redo数据等操作。

      • Prepare阶段:客户端向协调者发送事务提交请求,协调者开始执行两阶段提交,向所有的事务参与者发送prepare命令,参与者将redo数据持久化成功后,向协调者应带prepare成功。这里隐含的意思是,参与者一旦应答prepare成功,就保证后续一定能够成功执行commit命令(redolog持久化成功自然保证了后续能够成功commit)。

      • Commit阶段

        • 执行Commit:协调者收到所有参与者应答prepare成功的消息后,执行commit,先在本地持久化事务状态,然后给所有的事务参与者发送commit命令。参与者收到commit命令后,释放事务过程中持有的锁和其他资源,将事务在本地提交(持久化一条commit日志),然后向协调者应答commit成功。协调者收到所有参与者应答commit成功的消息后,向客户端返回成功。

        • 执行Abortprepare阶段中如果有参与者返回prepare失败或者超时未应答,那么协调者将执行abort,同样先在本地持久化事务状态,然后给所有参与者发送abort命令。参与者收到abort命令后,释放锁和其他资源,将事务回滚(有必要的情况下还要持久化一条abort日志)。

    • 经典2PC的局限

      • 协调者宕机:2PC是一个阻塞式的协议,在所有参与者执行commit/abort之前的任何时间内协调者宕机,都将阻塞事务进程,必须等待协调者恢复后,事务才能继续执行。

      • 交互延迟:协调者要持久化事务的commit/abort状态后才能发送commit/abort命令,因此全程至少2RPC延迟(prepare+commit),和3次持久化数据延迟(prepare写日志+协调者状态持久化+commit写日志)。

  • Percolator系统的两阶段提交

    • 概述:percolatorgoogle基于bigtable实现的分布式数据库,在bigtable单行事务的基础上,它使用全局的Timestamp Server来实现分布式的mvcc(后续专门讨论,本文不展开了);还有2PC协议来实现多行事务。由于bigtable屏蔽了数据sharding的细节,在percolator看来事务修改的每一行记录,都被看作一个参与者,事务没有区分预处理和prepare阶段,可以认为事务开始后,即进入了2PCprepare阶段。

      percolator2PC协调者并不持久化状态,而是引入primary record的概念,将事务执行过程中修改的第一个record作为primary record,在这个record中记录本次事务的状态,而在事务执行过程中其他被修改的record里面记录primary recordkey(这里我觉得priamry record保存单独的表中更优雅,否则priamry record被用户删除的话,并不好处理)。在commit阶段,先在primary record中记录事务状态(包括事务IDmvcc版本号等),成功后,才将各个参与者的修改提交(包括持久化mvcc版本号,释放行锁等)。在事务执行过程中,如果协调者宕机,那么其他参与者可以通过查询primary record中保存的事务状态来决定回滚或提交本地的修改。

    • 创新与局限:在仅提供行级事务的bigtable基础上,percolator创新的实现了多行事务和mvccprimary record的设计简化了2PC协议中对协调者状态的维护,是一套比较优雅的2PC工程实现。但是直接构建在KV基础上的数据库事务,也存在着诸多局限:

      • 底层KV屏蔽了sharding细节,且不提供交户型的事务上下文机制,对存储引擎的读写只能在一次RPC提交,使得加锁、修改、提交都必须是一次bigtable的提交操作,延迟代价是巨大的。

      • 尽管primary record的设计简化了2PC的协调者状态维护,但是commit时仍然要等待primary record持久化事务状态成功后,参与者才能进行commit,这一次延迟不可避免。

  • 2PC协议优化

    • 通过对经典2PCpercolator实现的分析,可以得到如下几个对2PC的改进思路:

      • 底存存储需要暴露sharding细节,提供以分区为单位的事务上下文管理机制,使得在预处理过程中,行锁和数据修改为内存操作,避免持久化的代价。

      • 简化协调者为无状态逻辑

      • 减少2PC执行关键路径上的持久化和RPC次数

    • 优化的2PC协议:

      • 预处理阶段:协调者向若干参与者发送SQL请求或执行计划,一个sharding即对应一个参与者,针对这个事务,在每个参与者中会维护一个通过事务ID索引的事务上下文,用于维护行锁、redo数据等,有必要的情况(redolog过多)下,这个阶段可能会异步的持久化redolog

      • Prepare阶段:协调者收到客户端提交事务的请求,向各个参与者发送prepare命令,命令中携带了当前事务的参与者列表,参与者收到prepare命令后,将事务的redolog、参与者列表、prepare日志持久化后,向协调者和其他参与者发送prepare成功的消息。

      • Commit阶段:协调者收到所有参与者应答prepare成功的消息后,即向客户端返回事务提交成功;对于每个参与者,当它确认所有参与者都prepare成功后,将本地事务提交并释放行锁等资源,并异步的持久化一条commit日志,然后向其他参与者发送commit成功的消息。

      • Finish阶段:对于每个参与者,当它确认所有参与者都commit成功后,将本地事务上下文释放,并异步的持久化一条finish日志。

    • 参与者与协调者状态转移图 参与者状态转移

      协调者状态转移

    • 宕机处理与事务状态恢复要点

      • 预处理阶段宕机:无论参与者还是协调者,在这个阶段宕机,事务都无法继续进行,可依靠参与者轮询协调者状态来尽快结束事务释放行锁。

      • Prepare阶段宕机:一旦所有参与者完成prepare,无论协调者是否宕机,事务最终都会被提交。对于参与者来说,如果没有持久化prepare日志,那么在回放日志时这个事务会被丢弃;如果已经持久化prepare日志,在日志回放完成后,需要向所有其他参与者查询事务状态。

      • Commit阶段宕机:这个阶段已经没有协调者的事了,所以只考虑参与者即可,如果已经持久化commit日志,那么回放日志后,它要在内存中保存这个事务状态,直到确认其他参与者都已完成commit;如果未持久化commit日志, 那么在日志回放完成后,需要向所有其他参与者查询事务状态。

      • Finish阶段宕机:同上,这个阶段已经没有协调者的事了,所以只考虑参与者即可,如果已经持久化finish日志,那么在回放过程中自然的释放事务上下文即可;如果未持久化finish日志,那么 它要在内存中保存这个事务状态,直到确认其他参与者都已完成commit

      • 事务状态的查询处理:如状态转移图所示,对于其他参与者的状态查询,在检查sharding匹配后,判断如果本地已经没有对应的事务上下文的情况下,按如下逻辑处理:

        • 收到其他参与者查询Prepare状态的请求:说明对方处于prepare阶段,自己没有这个上下文,说明事务肯定已经abort,所以直接回复事务abort

        • 收到其他参与者查询Commit状态的请求:说明对方处理commit阶段,自己已经确认可以finish,说明事务肯定已经正常提交,所以直接回复commit成功。

    • 延迟分析与协议局限

      • 预处理阶段的redologCommit日志、Finish日志为异步持久化,不影响事务延迟;Prepare日志为同步持久化,需要等待持久化成功才能发送应答。参与者之间的Prepare状态与Commit状态的查询,不影响事务延迟,而协调者只需要等待所有参与者的Prepare应答后即可向客户端返回,因此协议全程只有 一次RPC交互延迟+一次日志持久化延迟。

      • 对读事务的影响:各个参与者上的事务,要等所有参与者Prepare成功后才能提交和释放行锁;可能出现协调者先应答了客户端,客户端再来读取时,一些sharding上的行锁还未释放(即事务还未提交),读事务需要等待直到事务提交。

Loading

[LockFree之美] 使用Hazard Version实现的无锁Stack与Queue

  • 概述

这篇文章(http://oceanbase.org.cn/?p=82)的第6小节讲述了Hazard Version的实现原理,它的设计思想最早由OB团队的席华锋提出,本文不再赘述,本文主要分享Hazard Version的实现要点,以及使用它实现无锁StackQueue的方法,已经在多核系统上的性能测试,代码已在github共享。

  • ABA问题

如《共享变量的并发读写》一文所述,Hazard Version主要解决的是无锁数据结构处理内存释放的问题,为此我们先来回顾一下无锁编程领域最经典的“ABA问题”,使用链表实现的无锁Stack来举例:

使用一个top指针来指向栈顶,使用CAS原子操作对top进行修改,来实现pushpop,一个常见但错误的实现可能是这样的:

	void push(Node *node) {
		Node *curr = top;
		Node *old = curr;
		node→next = curr;
		while (old != (curr = CAS(&top, old, node))) {
			old = curr;
			node→next = curr;		
		}
	}
	Node *pop() {
		Node *curr = top;
		Node *old = curr;
		while (NULL != curr
			old != (curr = CAS(&top, old, curr→next))) {
			old = curr;
		}
		return curr
	}

push的逻辑没问题,问题在于pop,它在还未“锁定”top的情况下,就引用了topnext字段,而此时的top指向的内存空间可能已经被释放甚至重用,一方面可能直接引起非法地址访问使得程序直接崩溃;更严重的可能造成隐蔽的“ABA问题”,考虑如下时序:

  1. Stack状态为 A→B →Ctop指向A

  2. 线程Itop(即节点A的地址)赋值给curr,并取得curr→next指针(为B)放入寄存器

  3. 线程II执行完整pop流程,Stack状态变为B→Ctop指向B,节点A被弹出后释放

  4. 线程II执行完整pop流程,Stack状态变为Ctop指向C,节点B被弹出后释放

  5. 线程II执行完整push流程,新申请节点为被复用的AStack状态变为A→Ctop指向A

  6. 线程I继续执行,CAS判断top值仍为A,则原子替换topB,链表被改坏

我们无法通过简单的修改pop逻辑来避免“ABA问题”,因为这里的纠结之处在于要“锁定(取出)”top,就要使用CAS原子的将top改为它的next指针,但是要安全的引用top→next又要先“锁定(取出)”top。因此解决“ABA问题”的根本,在于保证pop逻辑引用top指针时,它不会被释放,而在释放节点内存空间时,严格保证不会再有其他人引用这个节点。Hazard PointerMichael M M. Hazard pointers: Safe memory reclamation for lock-free objects[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(6): 491-504.)技术是一个里程碑式的创新,真正在实际工程中解决“ABA问题”(memsql/oceanbase都在使用),Hazard Version是对Hazard Pointer在易用性上的改进,原理一致,详细介绍请参考《共享变量的并发读写》一文。

  • Hazard Version实现要点和局限

    • Hazard Version设计概要


      如上图所示,Hazard Version数据结构主要由三部分组成

      • 全局的Current Version变量

      • 每个线程局部一个Hazard Version变量

      • 每个线程局部一个待回收的内存块链表Retire List

      Hazard Version提供如下三个操作逻辑:

      • 每个线程要开始访问“可能被其他线程释放”的内存块前,将当前Current Version的值保存在线程局部的Hazard Version中,对共享内存块的操作完成后,再清除线程局部的Hazard Version值。

      • 要释放一个共享内存块时,原子的将Current Version1后,将旧值保存在内存块中,然后将它挂在线程局部的Retire List上。

      • 当待回收的内存块过多时,遍历所有线程的Hazard Version,以及全局的Current Version,获得最小值(Min Version),遍历待回收的内存块,将Version小于Min Version的内存块回收掉。

    • 获取Min Version的原子性问题

      如上所述,遍历所有线程,获取Min Version的操作并不保证原子性,可能出现一个线程获取到一个很小的Current Version后,被切换出去,而错过了同时进行的遍历操作。这个问题可以通过简单的double check来规避,线程拿到Current Version,保存到线程局部的Hazard Version后,再检查一下当前Current Version是否发生变化,如果已发生变化,则重试直到Current Version不再改变为止。因为如果Current Version未发生变化,即使遍历被错过,Current Version也参加了遍历,所以得到的Min Version就是真正的Hazard Version最小值。

    • 无锁遍历Retire List

      回收内存时,每个线程优先回收自己本地的Retire List,如果全局待回收的节点仍然比较多,则遍历其他线程的Retire List进行回收,这里会涉及多线程操作Retire List(即它的owner线程挂入新节点,而其他线程要进行遍历),一个简单的做法是要遍历Retire List时,使用CASRetire List替换为NULL,取得旧值后,在当前线程本地进行遍历,对遍历剩下的节点,就挂到线程本地的Retire List上去。

    • CAS小技巧

      CAS操作通常在循环中执行,一次CAS执行失败后,要重新准备新的compare参数和assign参数。比如原子修改栈顶:

      Node *old_v = top;
      
      node→next = old_v;
      
      while (old_v != CAS(&top, old_v, node)) {
      
      old_v = top;
      
      node→next = old_v;
      
      }

      因为CAS无论成功与否,都可以返回旧值,因此这里可以用一个临时变量保存CAS的返回值,避免重新取一次top,毕竟重新取top很可能造成缓存miss

      Node *curr_v = top;
      
      Node *old_v = curr_v;
      
      node→next = curr_v;
      
      while (old_v != (curr_v = CAS(&top, old_v, node))) {
      
      old_v = curr_v;
      
      node→next = curr_v;
      
      }
    • Hazard Version的局限

      相对Hazard Pointer来说,Hazard Version这个本质上是管理多个线程Hazard Version的“滑动窗口”,它通过增加获取Min Version的代价,来减小各个线程获取和重置Hazard Version的代价。因此它有与“滑动窗口”一样的局限性,太久不释放的Hazard Version,会阻塞内存回收。在使用时需要注意,对Hazard Versionrequirerelease操作之间,不能有耗时过长的逻辑。

    • Hazard Version代码仓库:

      https://github.com/kayaklee/libhalog/blob/master/src/clib/hal_hazard_version.h

  • 无锁Stack

    使用Hazard Version实现无锁Stack比较简单,因为push不涉及“ABA问题”,所以只需要在pop时使用Hazard Version保护即可。

    代码请参考:https://github.com/kayaklee/libhalog/blob/master/test/clib/hv_sample_lifo.cpp

    性能测试结果:如下图所示,在美团云12核虚拟机上,6个线程push6个线程pop,不带pop结果检查情况下,最快接近780/spush+pop次数。

     stack_perf

  • 无锁Queue

    Stack不同,实现无锁Queue的一个难点在要维护HeadTail两个指针,在Queue由空变为非空,和非空变为空的时候,需要保证原子的修改和判断这两个指针,这几乎是没有办法实现的。一个变通的方法,是受到Hazard Pointer论文的启发,在初始状态下,引入一个Dummy Header节点,无论push还是pop,都始终保证headtail不会变为NULL

    这样一来,push操作不需要管head指针,每次都只修改tail即可;而pop操作,是取head→next节点中的值作为队首数据,确认head→next不为空,然后原子的将head改为head→next。因为pushpop操作都存在先拿tailhead指针,然后引用它们的next成员的操作,因此都需要使用Hazard Version进行保护。

    代码请参考:https://github.com/kayaklee/libhalog/blob/master/test/clib/hv_sample_fifo.cpp

    性能测试结果:如下图所示,在美团云12核虚拟机上,6个线程push6个线程pop,不带pop结果检查情况下,最快超过1300/spush+pop次数。

    queue_perf

  • StackQueue性能测试数据和虚拟机cpu信息:

    https://github.com/kayaklee/libhalog/tree/master/test/clib/hv_performance_record

Loading