作者归档：yubai

[蹭热度] 关于OceanBase在2020年第二次上榜TPCC的解读

OceanBase在2020年打破自己在2019年创造的记录，第二次问鼎，在最近又引起一波讨论，作为利益相关方（前ob初创团队员工、目前正在现东家做着类似的事情），也想蹭一波热度，来从数据层面分析解读下。

关于tpcc的背景知识，请大家上tpcc官网了解，不要轻信各种公众号文章，顺便贴一下tpcc排名页面（TPC-C排名页面：http://www.tpc.org/tpcc/results/tpcc_results.asp），这里我也顺便列一些关于tpcc几个关键的背景考点：

TPCC测试结果是需要委员会认证的，未经官方认证的测试结果并不具备可信性，委员会要在宕机恢复、RTO、RPO、性能波动、软硬件成本等方面进行评审。比如很多国内项目自己公布的TPCC测试结果，并不具备可信性。
根据TPCC测试标准，每个warehouse所能获得的tpmC上限是12.86，行业里如果某家厂商自己公布的测试结果算下来平均每个warehouse的tpmC超过12.86，说明它很可能在通过缩减warehouse数量来利用内存优势跑分，这是不符合标准规范的。
TPCC只有测试标准文档，没有官方的测试软件，参与评测的各家厂商需要根据标准文档自行开发测试软件。截至2020年，我还没有搜到之前参与过TPCC测试的厂商开源出来的测试工具。
事务一致性：TPC-C 测试要求 10% NewOrder 跨warehouse，以及 15% Payment 跨warehouse，除库存分析类的查询外禁止ANSI Isolation Levels中的的P3/P2/P1/P0，即达到Serializable级别，基于中间件的分库分表的系统比较难达到这种事务一致性要求。

下面对比下OceanBase在2019年和2020年两次tpcc测试结果的数据，列几个值得关注的点：

性价比：总的tpmc上涨10倍多，平均成本缺降低36.32%，主要应该是得益于单个节点算力密度的增加，CPU超线程数由64增加到84，内存由512G增加到712G，NVME盘有1.7T增加到3.5T，一般来说单个主机算力密度越高，综合成本越低。
ScaleOut能力：节点数量由207台增加到1557台，节点数增加652.17%，超线程数增加887.23%，而tpmc增加1061.86%，证明了系统在1600这个规模上的线性scale out能力。而且由于叠加了软件层面的优化，甚至达到超线性的效果。
数据规模：数据量由0.49PB增加到5.51PB，从TB级迈入PB级；内存容量在总数据量中占比为19.19%，系统一定会有读盘的请求。不过从tpcc的测试场景来看，对于OB这种LSM引擎还是更加友好的，毕竟占比最大的NewOrder与PayOrder，都有很强的时效性，这两个操作产生的数据应该可以几乎全部命中在内存中，内存使用效率远大于Btree类引擎。
单点能力：单个节点的处理能力被优化到极致，SQL语句处理能力达到46.49万/s，这得益于OB事务引擎大量使用无锁结构、完全的池化的内存管理和libeasy框架的高并发处理能力等。考虑到这还是带上了Paxos强同步redolog的场景，已经能把市面上的几个开源数据库按到地上摩擦的抠不出来了。
分布式事务：百万级的分布式事务处理能力，从24.7万/s，增加到286.95万/s，前几天好像看到有文章说OB的tpcc测试没有分布式事务，是没有仔细学习tpcc的FRD文档的。分布式事务的优化应该是得益于对Jim Gray和Lamport的合作的一篇文章的工业实现。
持久又稳定的输出：持续8个小时测试，吞吐抖动不超过2%，这一点看FDR中的图就行了
取巧：既然是跑分，OB也在某种程度上利用了规则，以降低硬件成本，不过这是在FDR中明确披露的“All other tables are replicated into 3 replicas: one full replica, one data replica and one log replica that are distributed among database nodes. A full replica contains cardinality, in-memory increments (mutations) that could be checkpointed to disk and redo log of the corresponding table. A data replica contains cardinality, checkpoints of in-memory increments (mutations) and redo log (both from the full replica). A log replica contains redo log only.” 与正常的应用在网站核心业务上3副本5副本的部署方式不同，OB在tpcc的性能测试中，3个副本不是对等的，其中1个完整副本包含redolog，LSM内存表，SST数据，这里隐含的意思是这个副本会做compaction；第2个副本只包含redolog，SST数据，它应该是在主副本完成compaction之后从主副本直接copy sst；第三副本只包含redolog。因此这里可以分析出来：整个1557台节点的内存基本都可以用于事务读写，两个副本基本没有内存开销；整个1557台节点的硬盘，用于存储2份数据文件而不是3份。之所以可以这样，是因为tpcc并没有规定或者考察RTO时间，所以只要保证RPO为零就行了。

最后，OceanBase问鼎tpcc，证明了share nothing架构是分布式数据库在性能、可用行、扩展性、强一致性上的正确路线方向，也打破了美帝在数据库行业的垄断地位，作为从业者我对这个方向充满信心，也希望其他正在做这个事的小伙伴继续努力，老板和投资人们保持长期有耐心继续投入。

[转载] 谷歌 F1 Online DDL的关键点：状态间兼容性

这篇文章是我读到的对于F1 Online schema change最透彻的解读，作者是我的同事董欢庆，他曾在IBM、中科院、华为长期从事存储领域工作，现在是美团分布式数据库团队核心专家。

原文地址：https://zhuanlan.zhihu.com/p/120719499

摘要：

Online DDL 是分布式数据库领域的重要基础，可以说与事务模型、共识协议一样重要。最近重读F1的Online Schema Change这篇 paper，也希望能用通俗易懂的方式帮助更多人理解它。因此有了这篇短文，实际上是个人的 Paper 阅读笔记。

理解这篇文章的原理的关键点：每个状态能正确运行的前提条件是什么；每个状态的DML能保证什么。然后就能理解状态之间的兼容性：所谓不兼容，就是违背了某个状态的前提条件。

这里没有覆盖文章中所有章节，着重在于说明上述的关键点。如果想知道所有细节，还需要读原文。

Ch1 大致介绍了下问题的背景以及状态间兼容性的概念；Ch2 以添加一个二级索引为例，介绍 F1 的 Online DDL 的一些关键点和流程；Ch3 简述了删除一个二级索引的过程；Ch4 简略描述了下 Optional 对象的操作简化。

数据库事务隔离标准分析

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)”，从低到高的自然语言定义依次为：

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.
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.
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协议。为了方便说明，本文主要针对分布式数据库中，跨域sharding的2PC方案的讨论。主要参考文献：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成功的消息后，向客户端返回成功。
    - 执行Abort：prepare阶段中如果有参与者返回prepare失败或者超时未应答，那么协调者将执行abort，同样先在本地持久化事务状态，然后给所有参与者发送abort命令。参与者收到abort命令后，释放锁和其他资源，将事务回滚（有必要的情况下还要持久化一条abort日志）。
- 经典2PC的局限
  - 协调者宕机：2PC是一个阻塞式的协议，在所有参与者执行commit/abort之前的任何时间内协调者宕机，都将阻塞事务进程，必须等待协调者恢复后，事务才能继续执行。
  - 交互延迟：协调者要持久化事务的commit/abort状态后才能发送commit/abort命令，因此全程至少2次RPC延迟（prepare+commit），和3次持久化数据延迟（prepare写日志+协调者状态持久化+commit写日志）。
Percolator系统的两阶段提交
- 概述：percolator是google基于bigtable实现的分布式数据库，在bigtable单行事务的基础上，它使用全局的Timestamp Server来实现分布式的mvcc（后续专门讨论，本文不展开了）；还有2PC协议来实现多行事务。由于bigtable屏蔽了数据sharding的细节，在percolator看来事务修改的每一行记录，都被看作一个参与者，事务没有区分预处理和prepare阶段，可以认为事务开始后，即进入了2PC的prepare阶段。
  
  percolator的2PC协调者并不持久化状态，而是引入primary record的概念，将事务执行过程中修改的第一个record作为primary record，在这个record中记录本次事务的状态，而在事务执行过程中其他被修改的record里面记录primary record的key（这里我觉得priamry record保存单独的表中更优雅，否则priamry record被用户删除的话，并不好处理）。在commit阶段，先在primary record中记录事务状态（包括事务ID，mvcc版本号等），成功后，才将各个参与者的修改提交（包括持久化mvcc版本号，释放行锁等）。在事务执行过程中，如果协调者宕机，那么其他参与者可以通过查询primary record中保存的事务状态来决定回滚或提交本地的修改。
- 创新与局限：在仅提供行级事务的bigtable基础上，percolator创新的实现了多行事务和mvcc，primary record的设计简化了2PC协议中对协调者状态的维护，是一套比较优雅的2PC工程实现。但是直接构建在KV基础上的数据库事务，也存在着诸多局限：
  - 底层KV屏蔽了sharding细节，且不提供交户型的事务上下文机制，对存储引擎的读写只能在一次RPC提交，使得加锁、修改、提交都必须是一次bigtable的提交操作，延迟代价是巨大的。
  - 尽管primary record的设计简化了2PC的协调者状态维护，但是commit时仍然要等待primary record持久化事务状态成功后，参与者才能进行commit，这一次延迟不可避免。

2PC协议优化
- 通过对经典2PC和percolator实现的分析，可以得到如下几个对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成功。
- 延迟分析与协议局限
  - 预处理阶段的redolog、Commit日志、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的实现要点，以及使用它实现无锁Stack与Queue的方法，已经在多核系统上的性能测试，代码已在github共享。

ABA问题

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

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

	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的情况下，就引用了top的next字段，而此时的top指向的内存空间可能已经被释放甚至重用，一方面可能直接引起非法地址访问使得程序直接崩溃；更严重的可能造成隐蔽的“ABA问题”，考虑如下时序：

Stack状态为 A→B →C，top指向A
线程I将top（即节点A的地址）赋值给curr，并取得curr→next指针（为B）放入寄存器
线程II执行完整pop流程，Stack状态变为B→C，top指向B，节点A被弹出后释放
线程II执行完整pop流程，Stack状态变为C，top指向C，节点B被弹出后释放
线程II执行完整push流程，新申请节点为被复用的A，Stack状态变为A→C，top指向A
线程I继续执行，CAS判断top值仍为A，则原子替换top为B，链表被改坏…

我们无法通过简单的修改pop逻辑来避免“ABA问题”，因为这里的纠结之处在于要“锁定（取出）”top，就要使用CAS原子的将top改为它的next指针，但是要安全的引用top→next又要先“锁定（取出）”top。因此解决“ABA问题”的根本，在于保证pop逻辑引用top指针时，它不会被释放，而在释放节点内存空间时，严格保证不会再有其他人引用这个节点。Hazard Pointer（Michael 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 Version加1后，将旧值保存在内存块中，然后将它挂在线程局部的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时，使用CAS将Retire 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 Version的require和release操作之间，不能有耗时过长的逻辑。
- 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个线程push，6个线程pop，不带pop结果检查情况下，最快接近780万/s的push+pop次数。
无锁Queue

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

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

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

性能测试结果：如下图所示，在美团云12核虚拟机上，6个线程push，6个线程pop，不带pop结果检查情况下，最快超过1300万/s的push+pop次数。
Stack与Queue性能测试数据和虚拟机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。

变更操作

成员变更操作前，C(old)的多数派中持久化的成员组为[[C(old)]]
成员变更操作由leader执行，leader收到命令后，将成员组[[C(old),C(new)]]发送给C(old)∪C(new)的所有成员，在此之后新的日志同步需要保证得到C(old)和C(new)两个多数派的确认
leader收到C(old)和C(new)两个多数派确认后，将成员组[[C(new)]]发送给C(new)的所有成员，收到C(new)多数派确认后，表示成员变更成功，后续的日志只要得到C(new)多数派确认即可

协议约束

Version投票约束：持有Version较大的成员，不能给持有Version较小的候选人投票
最大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服务

选主投票原则

持有[[C(old),C(new)]]的候选人要得到C(old)和C(new)两个多数派都确认，才能当选leader
持有[[C(old)]]的候选人要得到C(old)多数派确认，才能当选leader
持有[[C(new)]]的候选人要得到C(new)多数派确认，才能当选leader

Joint-Consensus的协议分析

成员变更过程中，对[[C(old),C(new)]]的投票要求在C(old)和C(new)中都得到多数派的确认，是为了保证在C(old)投票“旧朝代结束”成功的同时，“新朝代开启”能够在C(new)生效，不会出现服务中断或者宕机重启后无法选出leader的情况。
对于成员变更的第二步，在[[C(old),C(new)]]形成两个多数派确认后，还要对[[C(new)]]在C(new)中进行投票，是为了结束需要向C(old)和C(new)都同步数据的“中间状态”。[[C(new)]]得到C(new)的多数派确认后，由于后面将要提到的“Version投票约束”原则的保证，可以确保后续宕机重启只有C(new)中的成员能够当选leader，因此无需再向C(old)同步数据。
Version投票约束，实际上是Paxos协议Prepare阶段对ProposalID的约束，如本系列的前一篇Multi-Paxos一文所述，选主过程本质上是Paoxs的Prepare过程，我们将成员组内容视为Paxos提案，那么Version就是ProposalID，Paxos不允许Prepare阶段应答ProposalID更低的提案，所以我们要求持有较大Version的成员不能给持有较小Version的候选人投票。从直观上来分析，Version投票约束可以保证，在[[C(new)]]形成多数派确认后，C(old)中那些错过了成员变更日志的成员，不可能再得到C(old)多数派的选票。
最大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后续的上任处理。
选主投票原则，持有[[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)同步的日志是否可能丢失。分析如下几种情况：

下线成员，C(new)与C(old)多数派成员数相同，比如ABCDE变更为ABCD，C(new)的任意多数派集合一定是C(old)的某个多数派，变更过程中使用C(new)同步的日志，在C(old)中依然能够保持多数派。
下线成员，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)中可以被多数派“重确认”，不会丢失。
上线成员，C(new)的多数派成员数大于C(old)，比如ABC变更为ABCD，C(new)的任意多数派集合一定包含了C(old)的某个多数派，变更过程中使用C(new)同步的日志，在C(old)中依然能够保持多数派。
上线成员，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原则，对成员组重新投票得到多数派确认。

阶段成员变更方案总结

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

成员组变更与日志同步
- Log Barrier

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

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

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

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

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

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

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

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

年故障率：

假设单盘容量为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集群

2条回复

利用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编译机

下载代码（https://github.com/kayaklee/distccMgr）

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

Oceanbase列传

分布式与存储技术

作者归档：yubai

[蹭热度] 关于OceanBase在2020年第二次上榜TPCC的解读

[转载] 谷歌 F1 Online DDL的关键点：状态间兼容性

数据库事务隔离标准分析

1 概述与背景

2 ANSI事务隔离级别

P1/P2/P3的形式化描述

3 基于锁的事务隔离

4 基于快照的事务隔离

5 总结

两阶段提交的工程实践

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

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

在线成员组变更的难点

成员组变更的基本思路

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

一阶段成员变更方法

成员组变更与日志同步

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

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

利用Bash脚本管理distcc集群

利用Bash脚本管理distcc集群

distcc介绍

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

一个小玩具