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

在非分布式系统中的数据库系统的一个基本特性是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是为了提高数据库的读性能产生的一种思路,是一种解决读写冲突的无锁并发控制方式

分布式系统的非功能需求

可用性和可靠性

可用性(availability)需要系统在任何给定的时刻都能够正确工作。可靠性(reliability)需要系统可以无故障地持续运行。这两者的区别是可靠性强调的是较少的崩溃次数,而可用性指的是较长的服务时长。例如,系统A可以运行一年,但每隔一个月会崩溃一次,并花费1s恢复;系统B无崩溃工作一年,但需要每年停机维护2小时。那么系统A的可用性会强一点,但系统B的可靠性会强一点。

高可用性HA与容错FT

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

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

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

安全性

安全性强调的是在故障的情况下系统能够正确操作而不造成灾难。

可维护性

可维护性描述发生发生故障的系统被恢复的难易程度。

分布式系统上的数据存储

在高并发的场景下,我们对服务器和数据库性能的扩展方案可以分为两种思路水平扩展(horizontal scaling, scale out)和垂直扩展(vertical scaling, scale up)。在这两种思路的领导下有三种方案,即共享内存(shared-memory)、共享磁盘(shared-disk)和无共享(share-nothing)。

一个最原始的系统通常是单服务器单库的架构,这也意味着在高并发的场景下,我们需要逐步进行升级,首先我们可以对服务器进行集群化和负载均衡。对于数据库的压力,我们在服务器和数据库之间加上一层缓存。随着数据库压力的进一步增大,我们使用主从架构。对于更大并发的要求,我们还可以采用分区的方案。

分布式的架构主要源于三点需求:扩大数据在地理上的分布范围从而减少延迟(latency),为系统提供容错/高可用性从而提高可用性,通过将请求负载均衡到各个机器上以提高伸缩性(Scalability)(例如读写分离)。

复制

复制(replicate),指通过网络连接的多台机器上保留相同数据的副本(replica)。复制可以是single leader的、multi leader的或者leaderless。

Single Leader架构

最常用的是leader-based replication,又称为active/passive或者主从(master/slave)架构,由一个Leader(Master/Primary)负责协调多个Follower(Read replica, Slave, Sencondary)。主从架构是一个HA解决方案,能实现读写分离,从而提高读写效率。主从数据库还可以互为热(hot)/温(warm)备份(standby),但会带来一些一致性的问题。
主从架构下的复制可以是同步的,也可以是异步的。异步复制在性能上是美好的,具有高吞吐量和低延迟,但是在一致性和持久性上会打折扣,每个节点上的数据可能是不一样的,并且主库已经向客户端确认的写入可能会丢失。异步复制的一个典型是Redis的哨兵机制。同步复制的情况下一旦一个从库失去响应,就会阻塞所有写入操作。在下图中,Follower1是同步的,Follower2是异步的。通常情况下的同步复制指的是半同步(semi-synchronous),即设置一个Follower为同步的,其余的为异步的。

处理集群成员变更

处理宕机

在主从架构下的从节点宕机的处理采取简单的catch up recovery。

我们讨论主节点的故障的处理方式,即故障切换(failover)。Failover主要涉及确认Leader失败、选举新Leader和重新配置系统三个主要步骤。对于确认Leader失败步骤,我们应当审慎地选取一个Timeout时间,因为Leader的超时可能是由于网络负载导致的,此时如果我们认为Leader宕机而开始选举会导致网络负载进一步恶化。对于选举步骤,我们需要在剩余的节点中决议出一个拥有旧Leader中最新数据副本的Follower以期最小化数据损失,一般通过共识协议解决。对于重新配置系统步骤,我们需要处理新Leader选出后老Leader重新连接的情况。一方面这可能导致脑裂(split brain),即新老Leader同时接受来自客户端的写请求,从而导致冲突。错误地解决脑裂问题可能导致新老Leader都被关闭,从而导致集群无主的现象。另一方面,在异步复制的环境下,新Leader可能没收到老Leader宕机前的写入操作,此时这部分的写入可能被丢弃掉,从而影响到持久性。

日志复制

Leader节点负责将日复制到Follower节点上。日志复制有如下的几种形式。

  1. 基于语句
    这种模式下,主库直接记录下每个写入请求如INSERT等,并转发给从库。这种方式存在一些弊端,例如SQL语句中可能存在随机函数或者时间函数导致每个库上的执行结果不一致,或者数据库中使用了AUTO INCR等语句时,对每个副本上语句的执行顺序也有要求。
  2. 基于WAL
    无论是为存储日志结构的LSM树还是覆写单个磁盘块的B树,其修改都涉及预写式日志WAL。在这些情况下日志是包含所有写入的仅追加序列,因此通过相同的日志可以在另一个节点上构建相同的副本。
    缺点是WAL的信息和数据库的底层存储紧密耦合,这使得更改底层存储格式变得困难。例如通常不可能在Leader和Follower上运行不同版本的数据库。
  3. 逻辑日志复制/基于行的日志复制
  4. 基于触发器的复制

一致性问题

日志复制的不同实现方式可能产生一致性问题。例如在读写分离的架构下,同步复制对可用性的损害是很大的,但如果采用异步复制的方式,在从库落后的情况下,同时对主库和从库的查询可能产生不同的结果,从而产生一致性问题。主从复制的架构是最终一致的(eventually consistency),也就是在副本之间实现同步间存在不一致窗口,称为复制延迟(replication lag)。复制延迟的持续时间是不确定的。

Multi Leader架构

Leaderless架构

分区

分布式集群

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

分布式系统上的一致性

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

强一致性

分布式系统,特别是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)的一个概念。全序要求在序列中的任何元素都能有确定的先后关系,而偏序则只要求序列中某些元素具有先后关系。整除关系是一个典型的偏序关系。

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

弱一致性

有的时候系统保证在更新操作后的一段时间后,系统能够达到一致性状态,这称为弱一致性。弱一致性和强一致性的区别是弱一致性存在“不一致窗口”,在不一致窗口中系统不一定保证用户总能看到最新的值。弱一致性可以分为最终一致性、因果一致性、单调读一致性、单调写一致性、有界旧一致性、前缀一致性等。
在Azure Cosmos中将一致性的强弱程度建立以下的关系。Strong–Bounded staleness–Session–Consistent prefix–Eventual。从前向后的延迟。可用性和扩展性越好,但一致性会差一点。

最终一致性

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

读己所写一致性

读己所写一致性(read-your-writes consistency)又称为read-after-write consistency,如下图所示,读己所写一致性要求客户端总能读到自己最新提交的写入。特别地,读己之写一致性不对其他用户的更新做出承诺。

读己所写一致性可以通过以下的一些方式实现:

  1. 当读取可能被修改过的内容时,强制从主库读。
  2. 对于大部分内容都可能被修改的系统来说,以上的方法并不适用,此时可以跟踪上次被更新的时间,并强制在上次更新后的某段时间内强制从主库读取。
  3. 客户端维护最近一次写入的时间戳,系统只从至少拥有该时间戳的修改的从库中进行查询。
  4. 当数据副本分布在多个数据中心时,可能带来额外的复杂性,这里略过,详见DDIA。

会话一致性

会话一致性能够保证在该会话内一致前缀读、单调读、单调写、读己所写、write-follows-reads一致性。

单调读一致性

单调读一致性要求客户端在已经读到某个数据的某个版本之后,不可能在稍后的读中读到该数据先前的某个版本。如下图所示,User2345首先从Follower1读到了55555这个评论,但是在稍后的对Follower2的读中却没有读到,这是因为Follower2此时还没有收到Leader异步复制过来的日志。令User2345读Follower1的时刻为X,则User2345在晚于X的一个时刻读取到了数据早于X时刻的版本,这违背了单调读一致性,即发生了时光倒流的“现象”。

DDIA指出单调读一致性介于强一致性和最终一致性之间,保证了先前读取到较新的数据的情况下后续不会读到更旧的数据。

一致前缀读

有界旧一致性

有界旧一致性(Bounded staleness)保证了读到的数据和最新版本最多差K个版本。

因果一致性

可用性

可用性即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)。

  1. 非拜占庭的Fail-stop模型。
  2. 最多一个进程失败。
  3. 可靠通信。即通信最终会被送达,且仅被送达一次。
  4. 异步通信。没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序。例如基于TCP的通信并不满足这个条件,因为TCP承载的消息是不可以乱序的。

拜占庭将军问题

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

诸如Paxos之类的算法只能对节点宕机进行容错,而不能对节点的拜占庭故障进行容错。实用拜占庭容错算法(Pratical Byzantine Fault Tolerance, PBFT)是一种多项式复杂度的状态机复制算法。

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