数据库事务隔离标准分析

1 概述与背景

这是数据库事务原理和工程实践系列文章的第一篇,本文主要在Jim Gray的论文<A Critique of ANSI SQL Isolation Levels>基础上分析关系数据库的事务隔离级别标准和不同隔离级别情况下的行为。第2节主要讨论ANSI标准的下的隔离级别,第3节主要讨论基于悲观锁实现的事务隔离级别,第4节主要讨论基于多版本技术的事务隔离,最后总结排序本文讨论到的各个隔离级别。
ACID是关系数据库的一组重要特性,其中Isolation(隔离性)描述了数据库允许多个并发事务同时对其数据进行读写和修改的能力,隔离性可以防止多个事务并发时由于交错执行而导致数据的不一致。在最极端的情况下,数据库完全串行化执行每一个事务,所有事务之间遵守全序关系,在这种情况下,不存在并发事务间的隔离问题,但是在实际工程实践中,处于对数据库性能吞吐量的考虑,允许多个事务之间按照一定的规则,打破串行话的全序关系,ANSI SQL Isolation Levels即规定了这种“规则”,通过将隔离性划分为4个级别,来换取多层级的事务间并发能力(即数据库的吞吐能力)。
注,本文内容融入了作者个人的理解,并没有严格遵守<A Critique of ANSI SQL Isolation Levels>原文的内容;其中cursor stability隔离级别将在后续文章中讨论,快照隔离级别与ANSI标准异象的比较也有所不同。

2 ANSI事务隔离级别

ANSI SQL-92标准(http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt)将数据库并发事务间的隔离性行为划分为3种”异象(phenomena)”,从低到高的自然语言定义依次为:
  1. P1 脏读 (“Dirty read”): SQL-transaction T1 modifies a row. SQL- transaction T2 then reads that row before T1 performs a COMMIT. If T1 then performs a ROLLBACK, T2 will have read a row that was never committed and that may thus be considered to have never existed.
  2. P2 不可重复读 (“Non-repeatable read”): SQL-transaction T1 reads a row. SQL- transaction T2 then modifies or deletes that row and performs a COMMIT. If T1 then attempts to reread the row, it may receive the modified value or discover that the row has been deleted.
  3. P3 幻读 (“Phantom”): SQL-transaction T1 reads the set of rows N that satisfy some <search condition>. SQL-transaction T2 then executes SQL-statements that generate one or more rows that satisfy the <search condition> used by SQL-transaction T1. If SQL-transaction T1 then repeats the initial read with the same <search condition>, it obtains a different collection of rows.
通过依次禁止这三种异象,ANSI确定了4种标准隔离级别,如下表所示:
级别 P1(脏读) P2(不可重复读) P3(幻读)
Read Uncommitted 允许 允许 允许
Read Committed 禁止 允许 允许
Repeatable Read 禁止 禁止 允许
(Anomaly) Serializable 禁止 禁止 禁止
Note: The exclusion of these penomena or SQL-transactions executing at isolation level SERIALIZABLE is a consequence of the requirement that such transactions be serializable.

如标准文档所述,禁止了P1/P2/P3异象的事务即满足Serializable级别,但矛盾的是,标准文档中对Serializable又做了如下说明:

The execution of concurrent SQL-transactions at isolation level SERIALIZABLE is guaranteed to be serializable. A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions

它要求多个并发事务执行的效果与某种串行化执行的效果一致,但是仅仅禁止P1/P2/P3异象,并不一定能够保证“serial execution”的效果,因此论文中将ANSI Serializable称为Anomaly Serializable。

P1/P2/P3的形式化描述

根据标准文档的定义,可以将这三种异象使用形式化语言描述如下,称为A1/A2/A3(其中w1[x]表示事务1写入记录x,r1表示事务1读取记录x,c1表示事务1提交,a1表示事务1回滚,r1[P]表示事务1按照谓词P的条件读取若干条记录,w1[y in P]表示事务1写入记录y满足谓词P的条件):

  • A1 脏读:w1[x] … r2[x] … (a1 and c2 in any order)
  • A2 不可重复读:r1[x] … w2[x] … c2 … r1[x] … c1
  • A3 幻读:r1[P] … w2[y in P] … c2 … r1[P] … c1

上述A1/A2/A3形式化描述,根据标准定义的P1/P2/P3异象的自然语言描述转化而来,但是ANSI标准定义的异象只针对了单个记录或谓词描述,对于多条记录需满足业务一致性的场景并未能覆盖(比如两个账户间转账要求余额总和不变),举例如下:

  • H1:r1[x=50]w1[x=10] r2[x=10]r2[y=50] c2 r1[y=50]w1[y=90] c1
    • 事务1执行账户x向账户y转账40,事务2读取到了进行到了一半的事务1(Read Uncommitted),破坏了余额总和的一致性
    • 因为事务1并未回滚,H1的行为并不符合A1的形式化定义
  • H2:r1[x=50] r2[x=50]w2[x=10]r2[y=50]w2[y=90] c2 r1[y=90] c1
    • 事务2执行账户x向账户y转账40,事务1在事务2提交前后读取到了破坏余额总和一致性的数据(Unrepeatable Read)
    • 因为事务1并未重复读取记录x,H2的行为并不符合A2的形式化定义
  • H3:r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1
    • 事务2增加新雇员并更新雇员总数z,事务1在事务2提交前后读取到了破坏雇员列表与雇员总数的一致性的数据(Phantom)
    • 因为事务1并未重复读取谓词P指定的数据集合,H3的行为并不符合A3的形式化定义

因为要增强对上述H1/H2/H3异象的约束,论文将A1/A2/A3的形式化描述称为“狭义的描述(strict interpretations)”,然后增加了“广义的描述(broad interpretation)”,去除了strict interpretations中对事务提交、回滚和数据读取范围的约束,只保留事务之间读写的时序关系,即事务之间只要包含如下时序的操作,即可能产生包含H1/H2/H3在内的异象,如下:

  • P1 脏读:w1[x] … r2[x] … ((c1 or a1) and (c2 or a2) in any order)
  • P2 不可重复读:r1[x] … w2[x] … ((c1 or a1) and (c2 or a2) in any order)
  • P3 幻读:r1[P] … w2[y in P] … ((c1 or a1) and (c2 or a2) in any order)

在上述形式化描述下,禁止P1即可禁止H1,禁止P1/P2即可禁止H2,禁止P1/P2/P3即可禁止H3。至此,ANSI标准隔离级别定义的三种异象,可以被扩展为适用范围更广的的P1/P2/P3的形式化定义,这种隔离级别定义被论文称之为“phenomena-based”,即基于“异象”的隔离级别定义。

3 基于锁的事务隔离

在上一节的讨论中,P1/P2/P3这三种形式化定义指出了三个不同级别的异象,但是并没有与实际的工程实践相关联,在本小节中,我们将介绍基于锁(lock base)的事务隔离实现,并且将不同的加锁行为与上述三种异象关联起来讨论。
在讨论加锁行为之前,需要定义如下几种读写和锁的操作:
  • Predicate lock 谓词锁(gap锁):Locks on all data items satisfying the search condition
  • Well-formed Writes 合法write:Requests a Write(Exclusive) lock on each data item or predicate before writing
  • Well-formed Reads 合法read:Requests a Read(share) lock on each data item or predicate before reading
  • Long duration locks 长周期锁:Locks are held until after the transaction commits or aborts
  • Shord duration locks 短周期锁:Locks are released immediately after the action completes
通过组合上述读写锁操作,我们能够构建不同级别的事务隔离标准。因为“No Well-formed Writes”或“Short duration write locks”的保护等级可能造成dirty write,它的约束已经低到难以找到实际应用场景,我们将其忽略,因此所有写入操作都使用“Well-formed Writes, Long duration Write locks”,通过对读取操作应用不同的保护等级,得到4种隔离级别,使用locking前缀与ANSI隔离级别区分,如下表所示:
Read Lock Write Lock
Locking
Read Uncommited
none required
Well-formed Writes,
Long duration Write locks
Locking
Read Commited
Well-formed Reads,
Short duration read lock
Well-formed Writes,
Long duration Write locks
Locking
Repeatable Read
Well-formed Reads,
Long duration data-item Read locks,
Short duration Read Predicate locks
Well-formed Writes
Long duration Write locks
Locking
Serializable
Well-formed Reads,
Long duration Read locks
Well-formed Writes
Long duration Write locks
将locking标记的四种隔离级别与ANSI隔离级别对比:
  • Well-formed Reads, Short duration read lock 禁止了 P1发生,r2[x]将被读锁阻塞,直到事务1提交或回滚
  • Well-formed Reads, Long duration data-item Read locks, Short duration Read Predicate locks 禁止了P2发生,w2[x]将被写锁阻塞,直到事务1提交或回滚
    • 其中Short duration Read Predicate locks的作用论文中并没有说明,实际上它保护了r[P]的一致性,保证r[P]读取到的多行数据是一个“well-formed history”
  • Well-formed Reads, Long duration Read locks 禁止了P3发生,w2[y in P]将被谓词写锁阻塞,直到事务1提交或回滚
如上所述,Lock Base的隔离级别能够完全覆盖ANSI基于异象的隔离级别约束,论文中也称“phenomena-based”是“disguised versions of locking”。

4 基于快照的事务隔离

对于基于锁实现事务隔离的数据库,读写、写写事务之间也可能因为锁冲突而被阻塞,数据库的整体吞吐能力受到比较大的限制,特别是在目前多核的CPU条件下,难以充分发挥计算能力。因此现代关系型数据库和NewSQL,比如MySQL/Oracle/PostgreSQL/OceanBase/TiDB等,都使用多版本并发控制(mvcc)技术,来实现事务隔离,它的核心设计思想是,为数据的每次修改保存一个用时间戳标记的版本,数据读取不需要加锁,而是在读取事务开始的时候获取当前时间戳(snapshot),对于每条数据,将版本号小于snapshot的最大已提交版本的内容作为读取结果返回。
Snapshot Isolation保证只读事务与读写事务相互不阻塞,只读事务通过读取合法的历史快照,保证了读取到的数据的一致性,我们在快照隔离下与A1/A2/A3逐个对比分析:
  • P1描述的w1[x] … r2[x] …操作时序不可能出现,因为在快照隔离下,实际的操作时序为w1[x] … r2[last version of x] …,因此可知快照隔离禁止P1
  • P2描述的r1[x] … w2[x] … 它实际的操作时序为r1[x] … w2[new version of x] …,可以知道快照隔离也禁止了P2。至此,我们可以确定快照隔离的效果至少大于Read Committed
  • P3描述的r1[P] … w2[y in P] … 它实际的操作时序为r1[P] … w2[new version of y in P] …,可以知道快照隔离也禁止了P3,达到了第2小节中ANSI的Anomaly Serializable级别
但是,从上一小节基于锁的隔离级别定义来分析,快照隔离的安全级别可能并没有那么高,我们来看如下两种异象的形式化描述:
  • A5A Read Skew: r1[x]…w2[x]…w2[y]…c2…r1[y]…(c1 or a1)
  • A5B Writer Skew: r1[x]…r2[y]…w1[y]…w2[x]…(c1 and c2 occur)
    • 扩展的Write Skew(并非来自原文):r1[P]…r2[P]…w1[x]…w2[y]…(c1 and c2 occur)
快照隔离性高于Read Committed:第一,考虑到快照隔离读已提交的数据版本的特性,禁止了P1,因此保证至少不低于Read Committed。第二,A5A的Read Skew异象符合P2的定义,并且从一致性的角度分析,事务1对x和y的读取的两个值不在线性的历史中,可能会违背某种外部约束(比如保证x+y的和为一个常量),因此Read Committed隔离级别下允许A5A Read Skew异象。总和以上两点,我们可以得出结论,快照隔离性高于Read Committed。
快照隔离性与Repeatable Read不相容:考虑到快照隔离能够保证读取到的数据在一个一致的历史快照上,禁止了P1/P2/P3,因此保证不低于ANSI的Anomaly Serializable级别;但是,另一方面,经典的快照隔离对于多写冲突是基于First- committer-wins的处理方式,依赖冲突的事务间至少修改同一条记录(现代快照隔离有更优的SSI,我们将在后续的文章中介绍)无法避免上述A5B Write Skew的两种异象,而基于锁事项的Repeatable Read级别却可以禁止A5B。快照隔离与Repeatable Read双方禁止的异象,有可能在对方出现,因此他们的隔离性无法相比较。

5 总结

从前面几个小节的隔离性分析来看,我们可以得到如下几种隔离级别的关系:
Read Uncommitted < Read Committed < (Repeatable Read >< Snapshot) < Serializable
本文首先介绍了ANSI基于“异象”的隔离级别标准,并分析了其狭义和广义的描述;然后介绍了基于锁的隔离级别标准,与ANSI隔离级别进行了比较;最后分析快照隔离级别,在ANSI隔离级别标准基础上,提出了两种新的“异象”,得出快照隔离在几种标准隔离级别特性中的位置。

两阶段提交的工程实践

两阶段提交(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上的行锁还未释放(即事务还未提交),读事务需要等待直到事务提交。

[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

[Paxos三部曲之三] Paxos成员组变更

Paxos成员组变更

本文是Paxos三部曲的第三篇,在前一篇文章《使用Multi-Paxos协议的日志同步与恢复》(http://oceanbase.org.cn/?p=111)中,我们讨论了基于Multi-Paxos协议的日志同步方案,在这个方案中,我们有一个隐含的前提,就是Paxos成员组是确定的,并且所有成员启动后都能加载一致的成员组信息。而在实际的工程应用中,往往需要在不停服务的情况下修改成员组,最典型的比如类似spanner的系统,对子表的迁移操作过程,就包含了对其Paxos成员组的变更操作。本文将基于Raft论文,讨论通用的成员组变更方法,和简化的一阶段成员组变更方法,以及成员组变更与日志同步操作的关系。

请注意,本文假设读者已了解Basic-Paxos和Multi-Paxos协议,并且本文假设集群工作在上一篇文章所述的Multi-Paxos协议之下。

  • 在线成员组变更的难点

Paxos执行两阶段投票协议的前提是有一个明确的Paxos成员组,而对于完全无中心化的Paoxs协议来说,成员组的内容本身又需要通过Paxos协议来维护一致性。对于变更后的新成员组从什么时机开始生效,存在“先有鸡还是先有蛋”的问题,如果还像同步普通日志一样来同步新成员组,那么在新旧成员组交接的过程中宕机,则可能出现选票分裂的情况,比如由成员组ABC变更为ABCDE过程中宕机,AB未持久化新成员组,CED已持久化新成员组,那么在宕机重启后,会出现AB形成了旧成员组的多数派,而CDE形成了新成员组的多数派,会出现两个leader的情况。

因此我们可以总结对在线成员组变更方案的几个基本要求:

P1. 成员组正常Paxos日志同步服务不中断

P2. 任何情况下宕机都能够保证存活的多数派成员间能够选举leader

P3. 不会出现1个以上的多数派选出大于1个leader的情况

  • 成员组变更的基本思路

成员组变更代表了“旧朝代”的结束和“新朝代”的开启,可以理解为依次执行如下两个投票操作:

Pa. “旧朝代”的多数派成员对“旧朝代结束”这件事达成一致,达成一致后旧成员组不再投票

Pb. “新朝代”的多数派成员对“新朝代开启”这件事达成一致,达成一致后新成员组开始投票

但是简单的按照这种两阶段的操作进行成员变更,虽然能够保证上述P3的约束,但是无法满足P1和P2,比如Pa执行成功后,在Pb执行成功之前:没有成员组可以投票,服务会中断;如果集群宕机重启,新的成员组的各个成员由于还未对新成员组达成一致,而无法选出leader。

为了保证P1和P2的约束,我们在上述基本成员变更的基础上,将Pa和Pb合并为一步操作,即新旧成员组一起对“旧朝代结束+新朝代开启”这件事达成一致后,才表示成员组变更成功。在开始成员变更的投票后,集群就进入了一个“中间状态”,在这个过程中宕机恢复后可能退回“旧朝代”也可能进入“新朝代”,因此在这个中间状态过程中投票的日志,要求在新旧成员组中都达成一致。

在这个基本思路的指导下,可以抽象出一个通用的成员变更方法:Jonit-Consensus。

  • 通用成员组变更方法–Joint-Consensus

Joint-Consensus是Raft论文中提到的两阶段成员变更方案,这个方案比较通用,甚至可以做到完整的成员组替换,但是两阶段方案的工程实现都比较复杂,而通用的场景需求又不多,因此在他博士论文最终版的成员变更一章中,更多篇幅分析了简化的一阶段方案(下一节讨论),而把Joint-Consensus的篇幅省略了很多。但是作为成员变更方案的基础,我这里还是希望能够从Joint-Consensus开始,分析它的正确性,并且尝试推导出一阶段的成员变更方法。

Joint-Consensus的方案如下,设成员变更前的成员组为C(old),变更后的成员组为C(new),成员组内容中包含单调增长的Version。

    • 变更操作
      1. 成员变更操作前,C(old)的多数派中持久化的成员组为[[C(old)]]
      2. 成员变更操作由leader执行,leader收到命令后,将成员组[[C(old),C(new)]]发送给C(old)∪C(new)的所有成员,在此之后新的日志同步需要保证得到C(old)和C(new)两个多数派的确认
      3. leader收到C(old)和C(new)两个多数派确认后,将成员组[[C(new)]]发送给C(new)的所有成员,收到C(new)多数派确认后,表示成员变更成功,后续的日志只要得到C(new)多数派确认即可
    • 协议约束
      1. Version投票约束:持有Version较大的成员,不能给持有Version较小的候选人投票
      2. 最大commit原则:
        • 持有[[C(old),C(new)]]的成员当选leader后,要重新对[[C(old),C(new)]]分别在C(old)和C(new)内投票达成多数派,然后继续成员变更流程,对[[C(new)]]在C(new)内投票达成多数派。然后才能开始leader恢复流程和leader服务
        • 持有[[C(old)]]的成员当选leader后,要重新对[[C(old)]]在C(old)内投票达成多数派,然后才能开始leader恢复流程和leader服务
        • 持有[[C(new)]]的成员当选leader后,要重新对[[C(new)]]在C(new)内投票达成多数派,然后才能开始leader恢复流程和leader服务
      • 选主投票原则
        1. 持有[[C(old),C(new)]]的候选人要得到C(old)和C(new)两个多数派都确认,才能当选leader
        2. 持有[[C(old)]]的候选人要得到C(old)多数派确认,才能当选leader
        3. 持有[[C(new)]]的候选人要得到C(new)多数派确认,才能当选leader
  • Joint-Consensus的协议分析
    1. 成员变更过程中,对[[C(old),C(new)]]的投票要求在C(old)和C(new)中都得到多数派的确认,是为了保证在C(old)投票“旧朝代结束”成功的同时,“新朝代开启”能够在C(new)生效,不会出现服务中断或者宕机重启后无法选出leader的情况。
    2. 对于成员变更的第二步,在[[C(old),C(new)]]形成两个多数派确认后,还要对[[C(new)]]在C(new)中进行投票,是为了结束需要向C(old)和C(new)都同步数据的“中间状态”。[[C(new)]]得到C(new)的多数派确认后,由于后面将要提到的“Version投票约束”原则的保证,可以确保后续宕机重启只有C(new)中的成员能够当选leader,因此无需再向C(old)同步数据。
    3. Version投票约束,实际上是Paxos协议Prepare阶段对ProposalID的约束,如本系列的前一篇Multi-Paxos一文所述,选主过程本质上是Paoxs的Prepare过程,我们将成员组内容视为Paxos提案,那么Version就是ProposalID,Paxos不允许Prepare阶段应答ProposalID更低的提案,所以我们要求持有较大Version的成员不能给持有较小Version的候选人投票。从直观上来分析,Version投票约束可以保证,在[[C(new)]]形成多数派确认后,C(old)中那些错过了成员变更日志的成员,不可能再得到C(old)多数派的选票。
    4. 最大commit原则,是Paxos最重要的隐含规则之一,在成员变更过程中的宕机重启,持有[[C(old),C(new)]]的成员可能当选leader,但是[[C(old),C(new)]]可能并未形成多数派,根据成员变更协议,成员变更过程要在[[C(old),C(new)]]形成两个多数派确认后,才能对[[C(new)]]进行投票。否则如果立即对[[C(new)]]进行投票,宕机重启后,可能出现C(old)和C(new)两个投票组各自选出一个leader。因此,持有[[C(old),C(new)]]的成员当选leader后,无论[[C(old),C(new)]]是否已经形成两个成员组的多数派确认,我们都按照最大commit原则对它重新投票确认形成多数派后,才能继续leader后续的上任处理。
    5. 选主投票原则,持有[[C(old),C(new)]]的成员当选leader,需要得到C(old)和C(new)两个多数派都确认,是为了避免C(old)与C(new)各自形成多数派选出两个leader的情况。在成员变更过程中,可以归结为如下两种情况:
      • 对[[C(old),C(new)]]的投票已开始,但未形成两个多数派确认,集群宕机。那么重启选主时,要么持有[[C(old)]]的成员当选leader,要么持有[[C(old),C(new)]]的成员当选leader。
      • 对[[C(new)]]的投票已开始,但未形成多数派确认,集群宕机。那么重启选主时,要么持有[[C(new)]]的成员当选leader,要么持有[[C(old),C(new)]]的成员当选leader。

如上文所述,持有[[C(old),C(new)]]的leader要先完成成员变更流程。之后再执行Multi-Paxox中的日志“重确认”,因此日志“重确认”过程不会进入“要得到两个成员组确认”的情况。

Joint-Consensus允许C(old)与C(new)交集为空,在这种情况下成员变更后,旧leader要卸任,并且将leader权限转让给确认[[C(new)]]的一个多数派成员。

Joint-Consensus方案比较通用且容易理解,但是实现比较复杂,同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性,因此我们期望增强成员变更的限制,以简化操作流程,考虑Joint-Consensus成员变更,之所以分为两个阶段,是因为对C(old)与C(new)的关系没有做任何假设,为了避免C(old)和C(new)各自形成多数派选出两个leader,才引入了两阶段方案。因此如果增强成员组变更的限制,假设C(old)与C(new)任意的多数派交集不为空,这两个成员组就无法各自形成多数派,那么成员变更方案就可能简化为一阶段。

  • 一阶段成员变更方法

Raft作者在他博士论文最终版的成员变更一章中,简化了Joint-Consensus的篇幅,而着重介绍了一阶段的成员变更方法,在工程上一阶段的成员变更方法确实更简单实用,下面是我对一阶段成员变更方案的一些分析。

    • 每次只变更一个成员

如上一节所述,如果做到C(old)与C(new)任意的多数派交集都不为空,那么即可保证C(old)与C(new)无法各自形成多数派投票。方法就是每次成员变更只允许增加或删除一个成员。假设C(old)的成员数为N,分析如下:

      • C(new)成员数为N+1
        1. 假设选出的leader持有C(new),那么一定是C(new)中有多数派,即(N+1)/2+1的成员给leader投票,那么持有C(old)且未给leader投票的成员最多为(N+1)-((N+1)/2+1)=(N-1)/2,这个值小于C(old)的多数派值N/2+1,无法选出leader
        2. 假设选出的leader持有C(old),那么一定是C(old)中有多数派,即N/2+1的成员给leader投票,那么持有C(new)且未给leader投票的成员最多为(N+1)-(N/2+1)=N/2,这个值小于C(new)的多数派值(N+1)/2+1,无法选出leader
      • C(new)成员数为N-1
        1. 假设选出的leader持有C(new),那么一定是C(new)中有多数派,即(N-1)/2+1的成员给leader投票,那么持有C(old)且未给leader投票的成员最多为N-((N-1)/2+1)=(N-1)/2,这个值小于C(old)的多数派值N/2+1,无法选出leader
        2. 假设选出的leader持有C(old),那么一定是C(old)中有多数派,即N/2+1的成员给leader投票,那么持有C(new)且未给leader投票的成员最多为N-(N/2+1)=(N-2)/2,这个值小于C(new)的多数派值(N-1)/2+1,无法选出leader
    • 启用新成员组的时机

启用新成员组的时机是指从何时开始,对日志的投票开始使用C(new)进行,这里需要考虑的问题是成员变更过程中宕机,重启选主后,持有[[C(old)]]的成员被选为leader,在宕机前使用C(new)同步的日志是否可能丢失。分析如下几种情况:

        1. 下线成员,C(new)与C(old)多数派成员数相同,比如ABCDE变更为ABCD,C(new)的任意多数派集合一定是C(old)的某个多数派,变更过程中使用C(new)同步的日志,在C(old)中依然能够保持多数派。
        2. 下线成员,C(new)的多数派成员数小于C(old),比如ABCD变更为ABC,这个情况比较特殊,我们来仔细分析,这种情况下在C(new)中形成的多数派成员只能达到C(old)成员数的一半,从严格的Basic-Paxos协议来分析,只做到N/2的成员确认,是不能保证决议持久化的。但是我们放在Multi-Paxos的环境中,使用lease机制保证leader有效(leader“有效”的意思是:StartWorking日志已形成多数派,且完成日志“重确认”,参考上一篇《使用Multi-Paxos协议的日志同步与恢复》)的前提下,因为不会有1个以上的成员并发提出议案,同时又因为在N为偶数时,N/2的成员集合与N/2+1的成员集合的交集一定不为空,可以分析出:在leader 有效 的前提下,只要N/2(N为偶数)的成员确认,即可保证数据持久化。因此,在这种情况下,在C(new)形成多数派的日志,宕机重启后,在C(old)中可以被多数派“重确认”,不会丢失。
        3. 上线成员,C(new)的多数派成员数大于C(old),比如ABC变更为ABCD,C(new)的任意多数派集合一定包含了C(old)的某个多数派,变更过程中使用C(new)同步的日志,在C(old)中依然能够保持多数派。
        4. 上线成员,C(new)与C(old)多数派成员数相同,比如ABCD变更为ABCDE,某些情况下可能产生C(new)的多数派(如ABE)与C(old)的多数派(如AB)交集只达到C(old)的一半,情况与第2点相同。
  • 最大commit原则

这里的最大commit原则体现在,同步[[C(new)]]的过程中集群宕机,持有[[C(new)]]的成员当选leader,重启后无法确认当前多数派持有的成员组是[[C(new)]]还是[[C(old)]],需要leader将当前持有的成员组重新投票形成多数派确认后,才能开始leader后续的上任处理。否则可能出现连续变更情况下,成员组分裂选出2个leader的情况,如Raft报出的这个bug,https://groups.google.com/forum/#!topic/raft-dev/t4xj6dJTP6E,修正方法也很简单就是实用最大commit原则,对成员组重新投票得到多数派确认。

    • 阶段成员变更方案总结
  1. 成员变更限制每次只能增加或删除一个成员
  2. 成员变更由有效的leader发起,确认新的成员组得到多数派确认后,返回成员变更成功
  3. 一次成员变更成功前不允许开始下一次成员变更,因此新任leader在开始提供服务前要将自己本地保存的最新成员组重新投票形成多数派确认
  4. leader只要开始同步新成员组后,即可开始使用新的成员组进行日志同步
  5. 成员组实用Version标记,持有更大Version的成员不能给持有较小Version的成员投票
  • 成员组变更与日志同步

    • Log Barrier

对于下线成员的场景,我们需要保证所有日志在剩余在线的机器上能够形成多数派备份,否则可能丢失日志。比如下面的场景,logID为2的日志,在连续成员变更后,仅A上有,无法在A/B/C上形成多数派:

paxos_barrier_log

因此我们要求leader在持久化新的成员组时,要像普通日志一样为它分配logID(称为成员变更日志),它是一个“单向barrier”,即要求所有成员保证logID小于它的日志都持久化本地后,才能持久化成员变更日志,而logID大于它的日志则不受此约束。在上面的例子中,要求B/C保证在持久化 Cnew1之前,一定先保证2号日志持久化。

磁盘故障与存储系统的年失效率估算

对三副本与ErasureCode两种方式下,数据丢失概率的估算,组合数学和概率论知识早就还给老师了,贴到博客给大家看看计算方法是否正确。

  1. 对于R个副本的情况,设磁盘年故障概率为P,磁盘数为N,则整个机群有C(N, R) = N!/(R!*(N-R)!)种R副本的组合方式。机群数据总量为M,分片大小为T,那么有R个磁盘同时损坏造成数据丢失的概率是:

屏幕快照 2016-03-25 下午10.51.39

  1. 对于由E个块组成的EC组,假设最多允许R-1个块丢失,整个机群有C(N, E)种EC组的组合方式,因此有R个磁盘同时损坏造成数据丢失的概率是:

屏幕快照 2016-03-25 下午10.51.46

其中P(t, R)表示在t时间内连续损坏R块磁盘的概率,这个概率符合泊松分布即:

屏幕快照 2016-03-25 下午10.52.11

设为t的单位时间(设为1小时)内发生磁盘损坏的平均次数,根据google的统计,磁盘的年失败率(AFR: Fnnualized Failure Rate)如下图所示,我们取一个平均值4来进行计算。那么就是0.0004566。

屏幕快照 2016-03-25 下午10.56.04

年故障率:

屏幕快照 2016-03-25 下午10.52.25

假设单盘容量为6T,使用率为70%,数据分片大小为1GB,在一个1000块磁盘的集群中,不同恢复时间的年故障率对比为:

恢复用时 3副本年故障率 EC(8+4)年故障率
1 1.2 * 10E-9 4.0 * 10E-19
4 1.9 * 10E-8 1.0 * 10E-16
12 1.7 * 10E-7 8.2 * 10E-15
24 6.8 * 10E-7 1.3 * 10E-13

3副本的恢复代价较小,因此我们可以按照机群使用1小时恢复单盘数据,EC恢复代价比较大,因此我们按照机群使用24小时恢复单盘数据,这两种情况下的持久性分布达到11个9和13个9。

附Python计算代码:

#!/usr/bin/python
# -*- coding: utf-8 -*-
import decimal
import math

lamda=decimal.Decimal(str(4.0/24/365))
e=decimal.Decimal(str(math.e))
perC=6.0*0.7*1024 #单盘容量(T)*使用率

#级数
def factorial(n):
  S = decimal.Decimal("1")
  for i in range(1, n+1):
    N = decimal.Decimal(str(i))
    S = S*N
  return S

#组合运算
def C(n, m):
  return factorial(n) / (factorial(m)*factorial(n-m))

#泊松分布
def poisson(t, R):
  return ((lamda * t) ** R) * (e**(-lamda*t)) / factorial(R)

#t时间内损坏R块磁盘的概率
def probability(t, R):
  return poisson(t, R)

#多副本年失效概率, T=分片大小(G), N=磁盘个数, t=单盘故障的复制时间, R=副本数
def probability_3R(T, N, t, R):
  M = decimal.Decimal(str(N * perC / R))
  pt = M / T / C(N,R) * probability(t, R)
  return (1 - (1-pt)**(decimal.Decimal(str(365.0*24/t))))

#EC年失效概率, T=分片大小(G), N=磁盘个数, t=单盘故障的复制时间, R=损坏超过R块磁盘则可能丢数据, E=EC组大小
def probability_EC(T, N, t, R, E):
  M = decimal.Decimal(str(N * perC / (1.0 * E / (E - R + 1))))
  pt = (M / T) * C(E,R) / C(N,R) * probability(t, R)
  return (1 - (1-pt)**(decimal.Decimal(str(365.0*24/t))))

 

架构师需要了解的Paxos原理、历程及实战

受TimYang邀请撰写的Paxos分享,已发在TimYang的公众号,我就不全文转了。

Abstract:“这里提一个名词:‘最大 Commit 原则’,这个阳振坤博士给我讲授 Paxos 时提出的名词,我觉得它是 Paxos 协议的最重要隐含规则之一,一条超时未形成多数派应答的提案,我们即不能认为它已形成决议,也不能认为它未形成决议,跟‘薛定谔的猫’差不多,这条日志是‘又死又活’的,只有当你观察它(执行 Paxos 协议)的时候,你才能得到确定的结果。”

架构师需要了解的Paxos原理、历程及实战

利用Bash脚本管理distcc集群

利用Bash脚本管理distcc集群

distcc介绍

对于大型C/C++项目,编译时间往往长到无法忍受,而冒然的增加make并发度则有可能由于gcc吃光内存而把机器搞死,因此我们期望能够使用多台机器并行编译项目。distcc是一个分布式编译程序,它包含客户端distcc,和服务器端distccd两个程序,distccd是一个守护进程,绑定在由命令行参数指定的端口上,接收distcc的编译请求,执行编译任务。

一个简单的使用方式是,在多台编译机上启动distccd,在客户端通过环境变量指定多个编译机的ip地址和端口号,然后使用distcc替换gcc编译项目。由于distcc自身实现的问题,编译失败或者make过程中途终止,可能会使得编译机上的distccd的工作进程僵死,因此运行一段时间后,可能出现大部分编译机上的distccd进程都变得不可用。并且编译机出现异常后也不能被distcc发现,而往往是网络连接超时后,才能去重试其他编译机。

为了解决上述问题,我开发了一套简单的bash脚本(distccMgr),通过单点监控所有编译机的健康状态,来实时生成可用的编译机列表,并可以通过下发命令来定时或立即重启编译机上的distccd进程。distccMgr本身不需要启动任何守护进程,而是通过crontab来定时保持心跳,通过ssh远程执行命令来实现心跳通信。

使用distccMgr集中化管理distcc编译机

git clone git@github.com:kayaklee/distccMgr.git
  • 管理节点部署
修改配置文件
SUDO="sudo" #执行sudo的命令前缀,比如美团的就是"sudo -iusankuai sudo"
MASTER_ADDR=`hostname -i` #管理节点的ip地址

MASTER_USER=$USER #管理节点的运行账户,需要保证与编译节点的运行账号相互打通
MASTER_PORT=8899 #管理节点开启http服务的端口号
DISTCCD_PORT=8898 #编译节点启动distccd服务的端口号

DISTCC_DIR=$HOME/share/distcc #管理节点监控脚本的部署目录
MASTER_DIR=$HOME/share/distcc/resource #管理节点资源目录,用于给编译节点提供http下载服务
SLAVE_DIR=$HOME/distccd #编译节点部署distccd的目录
运行部署命令
./deploy.sh 
部署成功后
1. 会在crontab中建立两个定时任务
2. 会在本地生成cmd目录,生成slave_deploy.sh和distcc_install.sh,其中slave_deploy.sh中是编译机的部署命令,distcc_install.sh是安装distcc的命令
  • 编译节点部署
1. 在每台编译机上执行slave_deploy.sh
2. 在管理节点的$DISTCC_DIR目录中的iplist中增加编译节点的ip地址
  • 客户端部署
1. 运行distcc_install.sh安装distcc,成功后会增加定时任务更新最新的编译机列表到/tmp/udistcc
2. 每次make前source /tmp/udistcc
  • 命令所有编译机重启distccd进程
在管理节点上touch /tmp/restart_distcc

一个小玩具

用golang玩的图片编辑服务,就跑在这个Blog的主机上

其实不小,代码量挺大,先不开源了,先部署在自己的Blog上玩玩

编辑参数比较像阿里云的 阿里云图片服务文档

url规则:http://image.oceanbase.org.cn/?xesurl=[图片url]&xesactions=[编辑参数]

示例url(缩放并填充): http://image.oceanbase.org.cn/?xesurl=http://7xkpgt.com1.z0.glb.clouddn.com/lena.jpg&xesactions=400h_500w_4e_150-50-100bgc

示例url(文字水印):http://image.oceanbase.org.cn/?xesurl=http://7xkpgt.com1.z0.glb.clouddn.com/lena.jpg&xesactions=watermark%3D2%26type%3Dd3F5LW1pY3JvaGVp%26text%3D5LiL5Y2K6Lqr5ZGi%26color%3DI2ZlMjRkYw

[Paxos三部曲之二] 使用Multi-Paxos协议的日志同步与恢复

使用Multi-Paxos协议的日志同步与恢复

           本文是Paxos三部曲中的第二篇。在前一篇文章《使用Basic-Paxos协议的日志同步与恢复》(http://oceanbase.org.cn/?p=90)中,我们讨论了基于Basic-Paxos协议的日志同步方案,在这个方案中,所有成员的身份都是平等的,任何成员都可以提出日志持久化的提案,并且尝试在成员组中进行持久化。而在实际的工程应用中,往往需要一个成员在一段时间内保持唯一leader的身份,来服务对数据的增删改操作,产生redolog,并尝试在成员组中进行持久化。本文讨论如何利用Paxos协议选举唯一的leader,以及使用leader将redolog在成员组中进行持久化和恢复的方法。

  • Basic-Paxos协议回顾

让我们先来回顾下Basic-Paxos协议的执行流程:为了简化描述,我们假设一个Paxos集群,每个server同时担任proposer和acceptor,任何server都可以发起持久化redolog的请求,首先要向所有的server查询当前最大logID,从多数派的应答结果中选择最大的logID,加1后作为执行本次Paxos Instance的唯一标识;然后进入Paxos的prepare阶段,产生proposalID,并决定出要投票的redolog(即议案);在accept阶段对prepare阶段产生的议案进行投票,得到多数派确认后返回成功。由此我们可以看出Basic-Paxos协议的执行流程针对每条redolog都至少存在三次网络交互的延迟(1. 产生logID;2. prepare阶段;3. accept阶段)。下面我们逐个分析每个阶段的必要性:

  1. 产生logID,由于Basic-Paxos并不假设一段时间内只有唯一的proposer,因此可能由集群内的任意server发起redolog同步,因此不能由单一server维护logID,而是需要进行分布式协商,为不同的redolog分配全局唯一且有序的logID。
  2. prepare阶段,上述一阶段的分布式协商logID并不能保证并发多个server分配得到得logID是唯一的,即会出现若干条不同的redolog在同一个Paxos Instance中投票的情况,而这正是Basic-Paxos协议的基本假设,因此需要执行prepare,以决定出这个Paxos Instance内的要进行投票的redolog(即议案)。如果执行prepare决定出的议案与server自己要投票的redolog内容不同,则需要重新产生logID。
  3. accept阶段,对prepare阶段决定出的议案进行投票,得到多数派确认后表示redolog同步成功,否则需要重新产生logID。

在这三个阶段中,根据Paxos协议的约束,server应答prepare消息和accept消息前都要持久化本地redolog,以避免重启后的行为与重启前自相矛盾。因此最终可以得到使用Basic-Paxos进行redolog同步的延迟包括了3次网络交互加2次写本地磁盘。并且在高并发的情况下,不同redolog可能被分配到相同的logID,最差可能会在accept阶段才会失败重试。

 

  • Multi-Paxos协议概述

在Paxos集群中利用Paxos协议选举唯一的leader,在leader有效期内所有的议案都只能由leader发起,这里强化了协议的假设:即leader有效期内不会有其他server提出的议案。因此对于redolog的同步过程,我们可以简化掉产生logID阶段和prepare阶段,而是由唯一的leader产生logID,然后直接执行accept,得到多数派确认即表示redolog同步成功。

 

  • leader的产生

首先,需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志,它允许有多个“自认为是leader的server”来并发生成日志,这样的场景即退化为Basic-Paxos。

Multi-Paxos可以简单的理解为,经过一轮的Basic-Paxos,成功得到多数派accept的proposer即成为leader(这个过程称为leader Elect),之后可以通过lease机制,保持这个leader的身份,使得其他proposer不再发起提案,这样就进入了一个leader任期。在leader任期中,由于没有了并发冲突,这个leader在对后续的日志进行投票时,不必每次都向多数派询问logID,也不必执行prepare阶段,直接执行accept阶段即可。

因此在Multi-Paxos中,我们将leader Elect过程中的prepare操作,视为对leader任期内将要写的所有日志的一次性prepare操作,在leader任期内投票的所有日志将携带有相同的proposalID。需要强调的是,为了遵守Basic-Paxos协议约束,在leader Elect的prepare阶段,acceptor应答prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地。

对于leader Elect过程,我们并不关心leader Elect提案和决议的具体内容,因为无论执行多少次leader Elect,从Basic-Paxos的角度来看,都是同一个Paxos Instance在对已经形成的决议反复进行投票而已。而执行leader Elect这个过程,我们最关注的是要得到最近一次形成决议的proposer是谁,以及它的proposalID。在leader Elect过程中,得到多数派accept的proposer将成为leader,而它本次所用的proposalID即成为它任期内对所有日志(包括新增日志和后文将提到的重确认日志)进行投票时将要使用的proposalID(称为leader ProposalID)。

这里还需要考虑的一个问题是,由于多个server并发执行leader Elect,可能出现两个server在相近的时间内,先后执行leader Elect都成功,都认为自己是leader的情况。因此,当选leader在开始以leader身份提供服务之前,要使用leader ProposalID写一条日志(称为StartWorking日志),得到多数派确认后,再开始提供服务。这是因为根据Basic-Paxos的约束,可以推断出:先执行leader Elect成功的leader(称为L1),它的proposalID(称为P1)一定会小于后执行leader Elect成功的leader(称为L2)的proposalID(称为P2),而经过了两轮leader Elect,机群内多数派持久化的proposalID一定是P2,而此时L1使用P1执行accept时,由于P1<P2,它将无法得到机群内多数派的accept。

 

  • Confirm日志的优化

在Paxos协议中,对于决议的读取也是需要执行一轮Paxos过程的,在实际工程中做数据恢复时,对每条日志都执行一轮Paxos的代价过大,因此引入需要引入一种被成为confirm的机制,即leader持久化一条日志,得到多数派的accept后,就再写一条针对这条日志的confirm日志,表示这条日志已经确认形成了多数派备份,在回放日志时,判断如果一条日志有对应的confirm日志,则可以直接读取本地内容,而不需要再执行一轮Paxos。confirm日志只要写本地即可,不需要同步到备机,但是出于提示备机及时回放收到日志的考虑(备机收到一条日志后并不能立即回放,需要确认这条日志已经形成多数派备份才能回放),leader也会批量的给备机同步confirm日志。出于性能的考虑,confirm日志往往是延迟的成批写出去,因此仍然会出现部分日志已经形成多数派备份,但是没有对应的confirm日志的情况,对于这些日志,需要在恢复过程中进行重确认。

在实际的工程实践中,可以使用基于logID的滑动窗口机制来限制confirm日志与对应的原始日志的距离,以简化日志回放与查询逻辑。

 

  • 新任leader对日志的重确认

如上一节所述,在恢复过程中,拥有对应confirm日志的原始日志,可以被直接回放。而没有对应confirm日志的原始日志,则需要执行一轮Paxos,这个过程被成为重确认。

此外日志中的“空洞”,也需要进行重确认,因为当前leader再上一任leader的任期内可能错过了一些日志的同步,而这些日志在其他机器上形成多了多数派。由于logID连续递增,被错过的日志就成了连续logID连续递增序列中的“空洞”,需要通过重确认来补全这些“空洞”位置的日志。

新任leader在开始执行重确认前,需要先知道重确认的结束位置,因为leader本地相对于集群内多数派可能已经落后很多日志,所以需要想集群内其他server发送请求,查询每个server本地的最大logID,并从多数派的应答中选择最大的logID作为重确认的结束位置。也即开始提供服务后写日志的起始logID。

对于每条日志的重确认,需要执行一轮完整的Paxos过程,可能有些日志在恢复前确实未形成多数派备份,需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份,都重新尝试持久化的原则,我们称之为“最大commit原则”。之所以要遵守“最大commit原则”,是因为我们无法区分出来未形成多数派备份的日志,而这些日志在上一任leader任期内,也必然是“未决”状态,尚未应答客户端,所以无论如何都重新持久化都是安全的。比如A/B/C三个server,一条日志在A/B上持久化成功,已经形成多数派,然后B宕机;另一种情况,A/B/C三个server,一条日志只在A上持久化成功,超时未形成多数派,然后B宕机。上述两种情况,最终的状态都是A上有一条日志,C上没有,在恢复时无法区分这条日志是否曾经形成过多数派,因此干脆按照“最大commit原则”将这条日志尝试重新在A/C上持久化后再回放。

需要注意的是,重确认日志时,要使用当前的leader ProposalID作为Paxos协议中的proposalID来对日志执行Paxos过程。因此在回放日志时,对于logID相同的多条日志,要以proposalID最大的为准。

 

  • 幽灵复现日志的处理

使用Paxos协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象,如下图所示:

 

Leader

A

B

C

第一轮

A

1-10

1-5

1-5

第二轮

B

宕机

1-6,20

1-6,20

第三轮

A

1-20

1-20

1-20

  1. 第一轮中A被选为Leader,写下了1-10号日志,其中1-5号日志形成了多数派,并且已给客户端应答,而对于6-10号日志,客户端超时未能得到应答。
  2. 第二轮,A宕机,B被选为Leader,由于B和C的最大的logID都是5,因此B不会去重确认6-10号日志,而是从6开始写新的日志,此时如果客户端来查询的话,是查询不到6-10号日志内容的,此后第二轮又写入了6-20号日志,但是只有6号和20号日志在多数派上持久化成功。
  3. 第三轮,A又被选为Leader,从多数派中可以得到最大logID为20,因此要将7-20号日志执行重确认,其中就包括了A上的7-10号日志,之后客户端再来查询的话,会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。

对于将Paxos协议应用在数据库日志同步场景的情况,幽灵复现问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。

           为了处理幽灵复现问题,我们在每条日志的内容中保存一个generateIDleader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时,因为leader在开始服务之前一定会写一条StartWorking日志,所以如果出现generateID相对前一条日志变小的情况,说明这是一条幽灵复现日志(它的generateID会小于StartWorking日志),要忽略掉这条日志。

 

  • 总结

本文介绍了在Basic-Paxos协议基础之上构建Multi-Paxos协议的几个要点:通过使用Paxos选举leader来避免对每条日志都执行Paxos的三阶段交互,而是将绝大多数场景简化为一阶段交互,并且讨论了基于Paxos协议的最大commit原则;通过引入confirm日志来简化回放处理;通过引入Start Working日志和generateID来处理幽灵复现问题。

 

有关期权股票与缴税的分享

有关期权股票与缴税的分享

本文基于作者本人的经验而写,其间难免有纰漏或错误,内容仅供大家参考。

作为一个穷二代屌丝码农,靠积攒每月的固定工资,可以说很难追上一线城市不断上涨的房价,还好我们处在一个伟大的时代,选择加入一家高速发展的公司,分得一些期权或股票,熬几年到公司上市套现,屌丝也可以逆袭

授予”与“归属”

以目前的经验来看,公司一般会以期权(option)或限制性股份单位(RSU)的形式对员工进行长期激励,也有其他形式的,比如华为的内部股票,或者蚂蚁金服的“股份收益权”不在本次讨论的范围内。所谓“长期激励”,其实就是把承诺给你的OptionRSU,拆分到N年,每年给一部分,以防止你全拿了就立即跑路。

这里就要谈到“授予”和“归属”两个概念,“授予”是一个承诺,靠谱的公司一般会明确写在offer中,承诺到未来某个时间只要你没有离职或被开除就给你多少OptionRSU;“归属”就是到了上述约定的时间,公司按照之前的承诺,将“授予”你的OptionRSU登记在你的名下。比如HR给你的发的offer可能会写“授予”你MOption,分4年“归属”,入职两年后“归属”M/2份,之后每年“归属”M/4份。在这4年期间如果你离职了,那么从你离职之日之后按计划要“归属”的Option都将失效。

期权

期权(option)就是允许你在一段时间内(一般比较长达几年)以约定的价格和数量购买公司股票的权利。归属以后才能“行权”,“行权”就是指你按照约定的价格够买股票的行为。如果公司未来股价上涨,股价与行权价相差的部分,就是你的收益,当然也存在风险即公司股价跌至行权价以下,这样的话Option就沦为废纸了。这里我们只讨论公司股价高于行权价的情况,行权需要缴纳两部分费用,第一部分就是行权本金,你要买多少股乘以行权价就是你要付出的本金;第二部分是个人所得税,用行权当日股价减去行权价,就是你的每股收益,乘以你要买的数量就是行权总收益计算个人所得税,具体缴税方式在后文说明。

一般期权归属后,会有一个有效期的,过了有效期就不能行权了,这个有效期一般会长达好几年,但是如果离职的话,一般就需要在几个月内行权,否则就会失效。

这里额外再说一下,一般来说行权价就是“授予”当时的股价,根据当时的公司的估值,以及公司发展和融资的状况,可以大概yy下几年后的股价。

限制性股份单位

限制性股份单位(RSU)简单说就是干股,也可以认为是行权价为0Option,唯一的区别是RSU不需要行权,“归属”后就变成你的股票了。但是同样需要你缴纳费用,就是个人所得税,一般是用归属当日的股价乘以归属的数量作为你的总收益计算个人所得税,具体缴税方式在后文说明。

这里需要注意的是,在公司尚未IPO的情况下,Option行权或RSU归属时的股价以公司最近一次发布的“公允价”计算;而如果已经IPO,那么就按照行权当天(或前n天的平均)收盘价计算。

股票与ADS的兑换

行权或RSU归属后,公司的股票就算是登记在你的名下了,如果在美国上市的话,还会有一个股票与ADS(美国存托股票,即资本市场上的流通股)的兑换比例,A股和H股可能也有类似的机制。所以一家上市公司给你发的offer中有股票授予的话,在你计算跳槽收益时要特别留意这个股票与资本市场上流通股的兑换比例。

关于个人所得税

有部电影曾经说过人生有两件事是逃不掉的,死亡和纳税。如上文所述,在Option行权和RSU归属的时候需要缴纳个人所得税,根据“国税函[2006]902号”,“国税函[2009]461号”,“财税[2005]35号”的规定,我总结缴纳个人所得税有三种计算方式:

  1. 发行股票的公司并未上市,这种情况下要将行权或归属的总收益与当月工资一起合并计税。
  2. 发行股票的公司(下称为A)已经上市,但是和你签署劳动合同的公司(下称为B)不是上市公司并且A公司持有B公司的股份少于30%,这种情况下计税方式与第1点一样,将行权或归属的总收益与当月工资一起合并计税。
  3. 发行股票的公司已上市,和你签署劳动合同的公司正是上市公司或被上市公司控制了超过30%的股份,这种情况下行权或归属的总收益将在本年度内平摊到12个月计税,且不与工资合并计税。说法有点绕,我们来举一个实例,比如在2014年度某个同学行权若干次,RSU归属若干次,最后算得的总收益为M元,那么他本年度需要为行权和归属缴纳的个人所得税为:(M / 12 * 适用税率 – 速算扣除数) * 12与工资没有任何关系。

分析与总结

  1. 对于未上市的公司,option的缴税比RSU更灵活,你可以在option“归属”后自由的选择时间行权,行权的收益跟当月工资合并计税,像我们这种小虾米,自己平摊到几个月行权的话,一般不会达到45%的税率;而RSU则没那么自由,在“归属”的当月就要按照收益全额缴税,比较容易就达到45%的最高税率
  2. 上市后的OptionRSU的缴税可以按照国家规定平摊到一年度12个月计税,而option还要多付出比较高的本金,因此RSU的风险更低一些;由于是与工资分开计税的,所以谈offer时如果能在现金与股票中选择的话,平衡与现金与股票数量,能最大程度的降低缴税成本
  3. 小心“个人所得税”一节第2点的坑,如果被授予OptionRSU,签署劳动合同尽量争取与上市公司或上市公司持股超过30%的公司签署
  4. 如果被授予OptionRSU,决定跳槽前注意询问股票与资本市场流通股的兑换比例
  5. offer时要求明确“归属”方案,尽量别选择那些网上流传的公司,上市后,员工连自己有多少股票都不知道

最后,努力工作和读书吧,少跳槽多拿股票,屌丝也能买得起北京的房子。

参考资料:

国税函[2006]902

http://www.chinatax.gov.cn/n810341/n810765/n812183/n812831/c1196443/content.html

国税函[2009]461

http://www.chinatax.gov.cn/n810341/n810765/n812166/n812622/c1087262/content.html

财税[2005]35

http://www.mof.gov.cn/zhengwuxinxi/caizhengwengao/caizhengbuwengao2005/caizhengbuwengao20056/200805/t20080525_42773.html