分类目录归档:未分类

数据库事务隔离标准分析

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

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

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

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

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

一个小玩具

用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