分布式一致性和分布式共识协议

在非分布式系统中的数据库系统的一个基本特性是ACID,即atomicity、consistency、isolation和durability。但在分布式系统下,CAP理论认为一致性C、可用性A和分区容错P不可能同时做到。

非分布式系统上的一致性

我们首先回顾一下非分布式系统上一致性的相关知识。

两种事务控制模型

ACID

对于关系型数据库,存在ACID事务控制模型维护事务的正确可靠性。

  1. 原子性
    原子性(atomicity)表现为事务中的所有操作要么全部完成,要么全部不完成(回滚),不会出现中间状态。以转账为例,假设A向B转账200元,那么原子性要求事务不存在A的钱扣了,但是B的钱没到账。
  2. 一致性
    一致性(consistency)表现为在事务开始前和结束后完整性约束(不变量)不被破坏。这里的“一致性常被称为“内部一致性”,以区别分布式系统中的外部一致性C。
  3. 隔离性
    隔离性(isolation)表现为数据库支持多个并发事务同时进行增删改。以转账为例,假设A和B同时向C转账200元,那么结束后C应当收到400元,而不存在只收到200块的情况。
  4. 持久性
    持久性(durability)表现为事务结束后对数据的修改是持久化的。例如系统发生宕机后,已提交的事务不应当消失。丢数据的一个常见例子是主从架构+异步复制,这种情况下durability难以保证。

BASE

BASE理论,即Basically Available、Soft State和Eventually Consistent,是相对于ACID准则的另一种事务控制模型,常被用在一些非RDBMS的事务控制的NoSQL中

在分布式系统的上下文下,BASE可以看做是对CAP理论做出的一种权衡,通常被以最终一致性的形式实现,参考下文。

事务更新的两条规则

提交规则

后像必须在提交前写入非易失存储器(数据库或运行记录)中。
当后像只写入日志而没写入数据库中也可以提交事务,因为出现故障之后可以使用后像REDO进行恢复。

先记后写规则

数据库中有先记后写原则,如果在事务提交前将后像写入数据库,则必须首先把前像记入日志。这样做的好处是在事务提交完成前如果出现故障,可以通过日志文件中的该前像进行UNDO,此时即使数据库没有被修改,也只是进行一次多余的UNDO操作。

故障恢复

WAL

在关系数据库中常使用预写式日志Write ahead log(WAL)算法,WAL要求在数据实际写入之前先写日志,这样能够保证在故障发生后能通过日志进行恢复。
事务有只有两种完成方式,提交即全做事务中的操作,和回滚即全不做事务中的操作。在事务的中间过程中可能对数据块的值进行修改,但最终这些修改必须要通过提交和回滚来实现持久化。
AI(后像,After Image),指的是每次更新时数据块的新值。对于一个已提交的事务,当故障发生时应当REDO它的后像。注意一旦事务提交,就不能UNDO它的前像,会破坏完整性约束;但是事务提交前任意的删改都可以通过UNDO来撤销。事务提交和往数据库写值(执行事务)是两个不同概念。
BI(前像,Before Image),指的是每次更新时数据块的旧值。对于一个未提交的事务或提交进行到一半,当故障发生时应当UNDO它的前像。
UNDO和REDO操作具有幂等性,即对前像UNDO或对后像REDO任意多次,结果都是相同的。

Shadow paging

并发事务控制

为了保证并发执行的事务在某一隔离级别上的正确执行的机制,我们需要并发事务控制。并发控制可以根据乐观程度分为基于Lock(如2PL)、Timestamp(如Basic T/O)和Validation(OCC系列算法)。

事务的隔离等级

在了解并发事务控制前,首先需要了解事务的隔离等级。
事务具有ACID的要求,隔离性I要求数据库能够支持并发事务。隔离性I的要求主要对应了四种隔离级别,分别是Read uncommitted、Read committed(Sql Server、Oracle等的默认隔离级别)、Repeatable read(MySQL的默认隔离级别)、Serializable,分别可以解决脏读、不可重复读(Nonrepeatable Read)、幻读几类问题。

  1. 脏读
    事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read Uncommitted隔离级别下可能产生脏读。考虑下面的序列。

    • A写入X
    • B读出X
    • A回滚
    • B读出的X是不合法的
  2. 不可重复读
    事务A在访问数据时,如果另一个事务在并发修改了该数据且提交,在Read committed隔离级别下可能产生不可重复读。考虑下面的序列。

    • A读取X
    • B写入Y
    • B提交
    • A写入Z
    • A提交失败
  3. 幻读
    在Repeatable Read隔离等级之下,事务A在访问数据时,事务开始后其他事务就不能对该数据进行修改了,因此杜绝了不可重复读。但是如果另一个事务在对其他的数据进行修改,例如在数据表中插入了一个新数据,那么会产生幻读现象,也就是一个事务的两次查询中数据笔数不一致。

  4. Serializable
    等同于在每个读的数据行上加S锁

2PL

我们知道死锁有四个条件:互斥、占有且申请、不可抢占和循环等待。而为了解决死锁问题,一个方案就是一次性获得所有的锁,这样实际上破坏了占有且申请的条件。不过这样一次性锁协议牺牲了并发性。为此我们引入了2PL,2PL将加解锁过程分为两个阶段,在第一阶段只能加锁或者操作数据,不能解锁;在第二阶段只能解锁或者操作数据,不能加锁。相比于1PL并发度提高了,但是存在死锁问题了。

意向锁

意向锁的产生是为了提高执行效率,它要求如果我们对一个下层节点加锁,那么我们会对上层节点加意向锁。我们考虑一个数据表中有一些行正在被锁定,而我们现在试图加一个表级锁,这显然是要被阻塞的,但阻塞前我们需要遍历数据表的每一行才知道我们表中有些行被锁定了。为此意向锁要求在锁定行时对数据表也维护一个状态,表示当前数据表中有些行时被锁定的,因此你意向是获得表锁,那么请原地阻塞,别往下找了,现在是不可能的。
以意向共享锁IS为例,如果我们想对一行加S锁,那么我们先要对表加IS锁,表示我们对表中的某一行有加共享锁的意向。此外,如果把上下层节点组合起来看,能组合成四种锁的类型即SIS、SIX、XIS、XIX。以共享意向排他锁SIX为例,对数据表加S锁,说明要读取整个表,对数据表加IX锁,表示要更新数据表中的一些行。除了SIX,其他的锁并没有提高强度,可以退化为一个表级锁或者行级锁。以SIS为例,我们要读取整个表,对表加S锁,然后要读取其中一行,对表加IS锁,实际上可以简化为一个对表加S锁的操作。

T/O

OCC

MVCC

多版本并发控制(Multi-Version Concurrency Control, MVCC)是相对于单版本的概念, 有不同方式的实现,如基于锁的MV2PL,基于时间戳的MVTO,基于OCC的MVOCC。MVCC是为了提高数据库的读性能产生的一种思路,是一种解决读写冲突的无锁并发控制方式

分布式系统的特性

高可用性HA与容错FT

FT即Fault Tolerant,根据DDIA,这里的fault应当与failure区别,故障通常定义为系统的一部分状态偏离其标准,而失效则是系统作为一个整体停止向用户提供服务。能预料并应对故障的系统特性可称为容错(fault-tolerant)或韧性(resilient)。

从定义上来看,Fault tolerant的系统不允许服务中断(service interruption),但其开销较高;High availability的系统追求最小的服务中断

衡量容错能力通常可以通过MTBF、MTTR、MTTF等指标,分别表示开始工作到第一个故障的时间的平均值,平均修复时间和平均失效时间。

主从复制

对于逐步增长的用户规模和并发量,最初我们的做法是在单服务器单数据库的架构上修修补补。对于高并发的请求,我们使用服务器集群+负载均衡,对于数据库的压力,我们在服务器和数据库之间加上一层缓存。随着数据库压力的进一步增大,我们升级架构为主从架构,我们写请求始终在主库,并不断向从库同步,读请求则始终在从库。主从架构实际上是一个HA解决方案,能实现读写分离,从而提高读写效率。主从数据库还可以互为热备份,但会带来一些一致性的问题。

主从复制可以是同步的,也可以是异步的。其中异步复制在性能上是美好的,具有高吞吐量和低延迟。但是在一致性上会打折扣,一个例子就是Redis的哨兵机制。

分区

对于更大并发的要求,我们还可以实行垂直拆分/水平拆分,将数据表按列/行拆分为多个。

分布式集群

分布式集群相比主从架构提供了更好的冗余方式,集群可以管理超过两个节点,并且所有节点都是对等的,称为replica,这些replica可以(并且应当)在空间位置上广泛分布,并且具有负载均衡的能力。而主从数据库一般将一主n从整体视为一个节点,并不适用分库分表。

一致性

强一致性

分布式系统,特别是CAP理论中对一致性(consistency)的定义是all nodes see the same data at the same time,这个要求是比较高的,通常也称为强一致性(Strong consistency)、线性一致性(Linearizability)、外部一致性(External consistency)、原子一致性(atomic consistency)。
强一致性强调each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response。
考虑一个简单的主从架构的例子(来自Designing Data-Intensive Applications),在下图中比赛结果由Referee写入Leader主库,并向两个Follower同步复制,线性一致性需要这个过程是透明的。在本场景中即当我们任何一个读取返回新值后,所有后续读取都必须返回新值(可以参考C++内存模型中的可见性一块)。但简单的读写分离主从复制会出现当Leader只同步了Follower1而没有同步到Follower2时,对两个副本的读取结果分别返回新值和旧值的现象。

通过线性一致性可以实现分布式锁、选举、和唯一性约束等功能。我们使用共识算法实现的是线性一致性,而主从复制则不是。由此可见,分布式一致性(Consistency)和共识(Consensus)是完全不同的两个概念,但是后者是实现前者的一个工具。

我们还需要区分Linearizability和Serializability。Linearizability来源于分布式系统和并发编程,其语境是single-operation, single-object, real-time order,线性一致性保证了写操作对后续的读操作是可见的。线性一致性往往对应于CAP中的C,线性一致性是composable 即local的,即如果每一个对象上的操作是线性的,那么系统上的所有操作都是线性的。Serializability来源于数据库,其语境是multi-operation, multi-object, arbitrary total order,它是一个有关事务的保证,涉及一组操作。它保证了在多个对象上执行的多个事务等同于某个序列化的执行过程。Serializability相当于ACID中的I,如果用户的每一个事务都能保证correctness即ACID中的C,那么顺序执行的事务也能保证correctness。不同于Linearizability,Serializability本身不给事务的执行顺序加上任何的real-time约束,也就是不需要操作是按照真实时间严格排序的。Serializability 也不是composable的,它也不表示任何的确定性的顺序,它只是要求存在一些等价的执行序列。

Serializability + Linearizability = Strict Serializability。

全序广播

全序广播(total order boardcast)有关一致性的另一个概念。首先,total order即全序关系,是相对于偏序关系(partial order)的一个概念。全序要求在序列中的任何元素都能有确定的先后关系,而偏序则只要求序列中某些元素具有先后关系。整除关系是一个典型的偏序关系。

实现全序广播等价于实现线性一致的存储

弱一致性

有的时候系统保证在更新操作后的一段时间后,系统能够达到一致性状态,这称为弱一致性。弱一致性和强一致性的区别是弱一致性存在“不一致窗口”,在不一致窗口中系统不一定保证用户总能看到最新的值。
弱一致性可以分为最终一致性、因果一致性、单调读一致性、单调写一致性等。

最终一致性也被称为乐观复制(optimistic replication),是一种获得HA的常见方式,要求当没有新的对X的提交发生时,最终所有对X的访问都返回最后一次更新的值。最终一致性通常用来提供BASE语义。我们常见的主从架构实现的是最终一致性

分布式一致性与事务一致性

从概念上分布式中的一致性(CAP中的C)和事务一致性(ACID中的C)是完全不一样的,CAP中的一致性要求多副本的系统的行为表现得像单系统一样,并且对这个系统的修改是原子的。而事务一致性强调事务前后不变量不能改变。

可用性

可用性即reads and writes always succeed。这个要求系统能够始终在正常时间内对用户的请求进行响应。当然由于可能出现的一致性问题,这个响应不一定是正确的。

分区容错性

分区容错性即the system continues to operate despite arbitrary message loss or failure of part of the system。由于分布式集群中常出现网络分区情况,即集群中的一部分机器与另一部分机器中断连接,这可能是由于网络故障,产生网络分区;也可能是由于某些节点宕机。网络分区可能产生的一个后果是脑裂(split brain),也就是存在多个节点认为自己是领导者。

我们除非设计出一个永远不会出故障的网络,否则我们必须要容忍P。于是C和A便成为了trade-off。由于网络分区的概率比较小,并且是易于探测的,所以C和A大多数情况是能够比较好地满足的,所以说我们要做的不是根除网络分区及其导致的部分失效(partial failure)问题,而是去正确地处理它,这就引入了诸如2PC、RWN、Paxos等协议。

分布式事务

由于分布式系统中存在多个副本,所以维护这些副本的一致性成为核心问题之一。分布式事务相对于仅涉及单个数据库事务的难点在于其提交或回滚不仅决定于自身,还决定于其他节点上事务执行的状态。从理想考虑,只要有一台节点失效,其他节点就要进行rollback。为了实现这一点,需要一个协调者(Coordinator)来根据所有参与者(Cohorts)的情况判断是否完成提交或终止提交。同时协调者的故障称为单点故障,也就是这个故障能够直接导致集群无法运行,需要特别考虑。
为了解决分布式事务上的ACID问题,我们引入了2PC、3PC、消息队列之类的算法。

2PC和3PC

出于篇幅限制,见文章2PC和3PC

可调一致性

诸如Cassandra的系统在最终一致性的基础上提供了可调一致性。对于任何读写操作,系统允许用户配置成功写操作的最小节点数W、成功读操作的最小节点数R和副本节点的数量N。我们可以根据读写请求的数量来动态调整可用性C和一致性A之间的trade-off。

分布式共识

分布式共识的特性

分布式共识协议被用来解决一个fault-tolerant的分布式系统上出现的一致性问题。通过共识协议,我们能够让一个集群的行为如同一个单机版的可靠的节点一样,即使其中有一小部分的节点宕机或分区。分布式共识协议常被用作在replicated state machine的上下文中。
具体地讲,分布式共识具有以下三个特性

  1. agreement
    决议需要得到所有节点的认同,通常是首先批准一个多数票的决议,然后进行同步。
  2. validity
    决议的值需要满足合法性要求。
  3. termination(liveness)
    决议过程能够在有限步内结束,并产生结果。

FLP不可能性

论文Impossibility of Distributed Consensus with One Faulty Process证明了异步通信情况下的只要有一个进程宕机,就无法达成共识。这里的共识需要满足termination、agreement和validity。相对于同步通信,

拜占庭将军问题

拜占庭将军问题指在一个有n个节点的集群内部,有t个节点可能发生任意错误的情况下,如果n <= 3t,一个正确的共识不可能达成。

CAP理论

CAP理论认为一致性(consistency)、可用性(availability)和分区容错性(partition tolerance)是不可能同时被满足的。这里的一致性指的是强一致性。

复制状态机

复制状态机(Replicated State Machine)的提出源自Paxos算法。复制状态机通过同步日志,使得多个节点从相同的初始状态开始,按顺序执行相同的命令,转移到相同的状态,复制状态机中向所有节点同步的内容是操作本身,我们可以理解为同步的是某个值的增量。与复制状态机相对应的是在ZAB等协议中常出现的primary backup system,它向所有节点同步的是操作的结果,我们可以认为同步的是值本身。容易看出RSM的设计使得我们回滚操作变得简单,仅仅删除掉后面的日志即可,但不好的地方在于RSM往往需要比PBS系统较多的日志条目,因为PBS可以只保存对状态机有修改的操作

基于RSM的日志复制形式是State-machine replication,能够实现FT通常地,一个支持F个(独立随机的)故障的系统需要2F+1个replica,对于fail-stop情况,即故障的系统保证不产生任何输出时,只需要F+1个replica即可。特别地,对于拜占庭故障,即某个节点向不同方向发送不同值的情况下,根据消息是否加密验证需要2F+1和3F+1个节点。

通常的SMR的实现是串行的,即每一个SMR的副本以单线程的形式处理Propose-Append-Broadcast-Apply的过程,只有当客户A的请求Apply之后,才能继续处理客户B的Propose。事实上,SMR的一个实现细节就是为所有的输入选择一个特定的顺序,注意到现实中的输入是偏序的,但SMR要求一个全序(total order)的输入。这样每一个非故障的副本才能在同样的状态通过同样的输入到达同样的结果

Pipeline是对串行方式SMR的一个优化,即使用一个线程接收请求,一个线程处理请求,一个线程响应客户端

分布式共识算法被用来解决SMR中存在的问题,例如如何选主,如何处理网络分区等,常见的分布式共识算法包括Paxos和Raft等。这里的共识(Consensus)指的是由一系列独立的实体为一个值进行投票

2PC、RWN、Paxos等分布式共识算法的区别

首先从设计上讲2PC和Paxos之流就奔着不同的目标而去。诸如2PC之类的协议是为了实现分布式事务,因此它涉及到的是对多个值修改的ACID性质,而分布式共识协议是为了管理一个值的多个replica。例如,我们可以认为2PC针对多个Partition,而共识算法针对于多个Replication。

再从可用性上考虑,分布式共识协议是为了维护复制状态机,即通过Leader保证复制状态机的输入是全序(total order的),从而可以通过复制状态机保证各个节点上的日志是一致的。进一步地,共识协议提供了Leader宕机情况下的选主策略,从而保证了集群的HA。特别注意到在这里,2PC算法中的Leader,也就是协调者在宕机之后集群会整体阻塞,而分布式共识算法能够极大程度避免这一点。

从CAP理论上来讲,2PC是CA的,它要求所有节点保持全体一致。诸如Paxos的Quorum类算法是CP的,它仅要求实现多数一致。RWN是AP的,因此它实现的是可调一致性而不是强一致性。

Raft

出于篇幅限制,有关Raft已经移到新文章Raft公式算法中。

Paxos

Paxos将网络中的节点分为proposer、acceptor和learner三种类。其中proposer即提案的提出者,acceptor对提案经投票,投票的最终结果交给learner进行同步。

Reference

除去在原文中标注引用的内容外,本文还参考了一下内容:

  1. DDIA
  2. 本文中提到的所有概念的原论文,例如FLP定理等。
  3. Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores