并发控制(数据库)

概述(缘起)

​ 通常,在我们处理应用程序并发编程问题时,我们往往会使用操作系统提供的各种锁API(互斥锁,读写锁,自旋锁,信号量,条件变量,屏障)等,保证对于共享资源的互斥访问,从而避免出现一些微妙的,出乎意料的结果。在数据库中,为了简化应用程序对并发的处理,数据库以不同程度的隔离性保证,封装了不同的并发控制策略提供给应用开发人员使用。一般来说,隔离性的强弱级别是和性能权衡的结果,隔离性越强,性能越差。

本文主要分为两部分:第一部分讨论单机数据库不同的隔离级别,都解决了怎样的并发问题,以及解决这些问题的常用技术;第二部分讨论在分布式数据库中,最终一致性会引起怎样的并发问题,以及相应的一些规避手段,并且简单讨论了一下在分布式下怎样实现强一致性(线性一致性和共识)。

隔离级别

​ 为了在隔离性和性能之间进行平衡,有很多数据库提供了不同的隔离级别。标准SQL定义了四种隔离级别:读未提交,读提交,可重复读,串行化。各种隔离级别的定义虽然看起来简单清晰,但事实上涉及到很多微妙的细节。更糟糕的是,大多数数据库的实现并没有完全遵循标准SQL对隔离级别的定义,而且不同数据库对同一种隔离级别的具体实现程度也往往不同。串行化往往存在严重的性能问题,弱隔离在一些特定场景下,有难以排查难以控制的竞态问题。因此,清楚地了解各种隔离级别的微妙含义,对开发鲁棒的应用程序非常重要。

一个贯穿各个隔离级别的示例

下面以一个MySQL的一个示例,来辅助说明各个几种隔离级别之间的差异。

1
2
mysql> create table T(aa int) engine=InnoDB;
mysql> insert into T(aa) value(1);

img

读未提交(read uncommitted)

基本上所有的数据库都实现了读未提交的隔离级别。

定义

  1. 当往数据库里写数据时,只能覆盖已经提交的数据(no dirty write)。

  2. 当向数据库里读取数据时,能够看到还未提交的数据(dirty read)。

如何避免脏写

通常情况下,数据库都是用过行锁的方式避免脏写的。当一个事务想要修改一个特定的对象(row or document)时,必须先锁住这个对象;后面如果有其他事务也想要修改这个对象,必须等待前一个事务完成并且释放锁。事务在完成提交或回滚时,释放锁。

读提交(read committed)

读提交是一种非常普遍的隔离级别,Oracle 11g, PostgerSQL, SQL Server 2012, MemSQL等,很多数据库的默认隔离级别都是读提交。(不少企业在使用中也把MySQL的隔离级别定义为读提交,并把binlog的日志设置为row用于解决日志和数据不一致的问题。)

定义

  1. 当往数据库里写数据时,只能覆盖已经提交的数据(no dirty write)。

  2. 当向数据库里读取数据时,只能读取到已经提交的数据(no dirty read)。

如何避免脏读

  1. 和避免脏写类似,也可以使用行锁来避免脏读。即,一个事务要读取一个特定对象之前,也要先锁住这个对象,读取完成后立即释放锁。然而这种方式对性能消耗非常大,一个耗时较长的写操作,可能会饿死很多只读操作。一个长时间的备份读操作,会饿死很多写操作以及写操作后面的读操作。

  2. 大多数数据库,会通过保存旧数据和正在修改中的新数据两个版本,来避免脏读。当一个写事务正在进行时(还没进行提交或回滚),此时到达的读事务只能读取到旧版数据。当写事务已经完成了提交或回滚,后续到来的读事务就读取新版的数据。

可重复读(repeatable read)

​ 可重复读也是一个非常常见的特性,很多数据库都支持可重复读:PostgerSQL, MySQL InnoDB引擎,Oracle, SQL Server, LevelDB等。可重复读为单个事务里的多个操作提供一个一致性的视图,对于一些耗时特别长的操作,例如备份,查询分析,整体性检查等操作非常有用。

MySQL InnoDB的默认隔离级别就是可重复读(repeatable read),并且组合各种技术在一定程度上解决了lose updates,write skew,phantoms(幻读) 等问题。

定义

​ 一个事务执行过程中看到的数据,总是跟这个事务在启动时看到的数据是一致的。当然,在可重复读隔离级别下,未提交变更对其他事务也是不可见的。

可重复读和快照的实现

​ 可重复读的隔离级别,也就是通常所说的快照隔离。快照隔离也通常是使用行锁来避免脏写,也就是说一个写事务会阻塞另一个更改相同对象的写事务;但是快照隔离的读事务不需要加锁,从性能角度来说,快照隔离的最大优势就在于:读事务永远不会阻塞写事务,写事务永远不会阻塞读事务。通常使用多版本并发控制(MVCC, multiversion concurrency control)的技术手段,来实现快照隔离这种特性。各种数据库的MVCC实现方案都大同小异,下面以MySQL InnoDB引擎的MVCC实现来举例说明。

MVCC的实现(MySQL为例)

InnoDB里面每个事务都有一个唯一的事务ID,叫做transaction id。这个ID是在事务开始的时候,向InnoDB的事务系统申请的,是按照申请顺序严格递增的。而每行数据也都有多个版本,每次事务进行更新的时候,都会生成一个新的数据版本(包括删除操作),并把transaction id赋值给这个数据版本的事务ID,记为row trx_id。类似于下图所示的情况:

img

上图中虚线框里是同一行数据的不同版本,当前版本是V4,它的k值为27,它是被transaction 30更新的,所以它的trx_id=30。事实上,在MySQL中,V1, V2, V3并不是物理上真实存在的,在MySQL中每次更新都会生成 undo log(回滚日志), 上图图中的三个箭头U1, U2, U3就指代undo log。 V1, V2, V3可以在需要使用的时候,实时被计算出来。例如,需要V2版本的时候,可以通过基于V4依次执行U3, U2计算出来。

有了严格递增的transaction id和undo log, 就可以很方便的实现MVCC。当一个事务启动的时候,以这个事务启动的时刻为临界点,如果一个数据对象的版本在该事务启动之前提交,则可见;如果一个数据对象的版本在该事务启动之后提交,则需要执行undo log,直到计算出可见的版本为止。

在实现上,InnoDB为每个事务都构造了一个数组,用来保存这个事务启动瞬间,当前正在“活跃”的所有事务ID。“活跃”是指,启动了但是还没提交的事务。数组里面事务ID的最小ID记为低水位,当前系统里面已经创建过的事务ID的最大值+1记为高水位。这个活跃数组和高水位,就组成了当前事务的一致性视图(read-view),即活跃数组,低水位,高水位,把整个transaction ID空间分成了四部分,每一部分对于当前事务的可见性规则如下:

img

  • 小于低水位的transaction id对于该事务可见。

  • 大于等于高水位的事务对该事务不可见。

  • transaction id落在活跃数组内的事务对该事务不可见(除了该事务本身)

  • transaction id大于低水位且小于高水位,且没落在活跃数组内的事务,对该事务可见(图中活跃数组下面的部分)。

示例(MySQL InnoDB)

1
2
3
4
5
6
mysql> CREATE TABLE `t` (
`id` int(11) NOT NULL,
`k` int(11) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB;
INSERT INTO t(id, k) VALUES(1, 1), (2, 2);
事务A 事务B 事务C
start transaction with consistent snapshot;
start transaction with consistent snapshot;
update t set k=k+1 where id = 1;
update t set k=k+1 where id=1;select k from t where id=1;
select k from t where id = 1; commit
commit
事务A 事务B 事务C’
start transaction with consistent snapshot;
start transaction with consistent snapshot;
start transaction with consistent snapshot; update t set k=k+1 where id = 1;
update t set k=k+1 where id=1;select k from t where id=1;
select k from t where id = 1; commit commit;
commit

在可重复读的隔离级别下,仍旧可能存在的并发问题

丢失更新(Lost Updates)

数据库修改数据的模式通常都是读取数据-修改数据-写回数据,当存在两个事务同时进行修改同一个数据对象时,往往会存在更新丢失,因为第二个事务会覆盖第一个事务的修改。

丢失更新乍看起来很像脏写(dirty write),两者关键的区别在于,脏写覆盖的是未提交事务的更改数据,丢失更新覆盖的是已提交事务的更改数据。

典型的丢失更新的场景:
  • 增加计数,例如: UPDATE counters SET value = value + 1 WHERE key = ‘foo’;

  • 在本地对复杂对象进行修改,例如:读取数据库里面的json文档,修改某些字段,写回数据库。

  • 两个用户同时编辑一个wiki页面,然后依次进行了保存。

如何避免丢失更新
  • 原子写:很多数据库提供了原子写的能力来避免丢失更新。

    • 例如MySQL InnoDB 可重复读隔离级别下: UPDATE counters SET value = value + 1 WHERE key = ‘foo’; 这条语句,在读取foo的值时,会对foo这一行加排它锁。

    • MongoDB提供了在本地更改JSON对象一部分内容的原子操作。

    • Redis使用lua存储过程,来原子性的修改存储对象。

    • 原子写虽然简单高效,容易理解,但是没法解决两人同时编辑wiki页面这类的丢失更新问题。

  • 显式加锁: 即对于可能存在丢失更新的并发写操作,在应用程序里进行显式的加锁。

  • 丢失更新自动检测:由事务管理器检查是否存在丢失更新类的并发事务,如果存在,中止事务并强制重试。幸运的是,借助MVCC的机制,能很高效的实现丢失更新自动检测。PostgreSQL 的repeatable read, Oracle的serializable以及SQL Server的snapshot隔离级别都实现了自动检测丢失更新。

  • Compare and set:注意,CAS中,compare的相关内容需要是当前读,而不是快照读。

1
2
--- This may or may not be safe, depending on the database implementation
UPDATE wiki_pages SET content = 'new content' WHERE id=12345 AND content = 'old content';

写倾斜(Write Skew)和幻影(Phantoms)

丢失更新是在多个事务并发读取并更新同一个数据对象的时候发生的,如果两个或多个事务并发检查一个约束条件(读取一个对象之后),然后分别更新不同的对象(更新对象之后就违反了先前的约束条件),这种竞态问题被称为写倾斜(Write Skew), 可以认为丢失更新是写倾斜的一种特例。写倾斜的概念比较抽象,下面是几个具体的例子:

  • 医院医生轮班系统,医院要求任何时刻至少要有一个医生oncall,如果有多个医生oncall,oncall的医生就可以请假(例如医生自己生病了),假设现在系统里有两个医生oncall, Alice和Bob。不幸的是他们两个同时提交了请假单,过程如下:

img

  • 会议室预定系统。约束:同一个会议室的同一个时间段不能被两个会议同时预定。
1
2
3
4
5
6
7
8
9
10
11
// A meeting room booking system tries to avoid double-booking(not safe under snapshot isolation)
BEGIN TRANSACTION;
-- Check for any existing bookings that overlap with the period of noon-1pm
SELECT count(*) from bookings
WHERE room_id=123 AND
end_time > '2020-04-13 12:00' AND start_time < '2020-04-13 13:00';
-- If the previous query returned zero:
INSERT INTO bookings
(room_id, start_time, end_time, user_id)
VALUES(123, '2020-04-13 12:00', '2020-04-13 13:00', 666)
COMMIT;
  • 游戏里面的角色卡位。约束:两个玩家,不能把角色移动到同一个位置上。

  • 申请账号。约束:用户申请的账号名唯一。

  • 支付系统。约束:用户能够支出的金额需要小于他的余额。

幻影和写倾斜的关系

可以说是因为幻影导致了读倾斜;幻影是指一个写事务更改了另一个事务的查询结果。可以简单回顾一下上面的几个写倾斜的例子,例如第二个医生提交事务之前,如果再查询一下会发现至少需要一个值班人员的约束已经被违反了。第二个预定会议室的插入操作在提交之前,如果再查询一下会发现这个会议室已经被其他人预定了…

可重复读的隔离级别解决了幻影读(幻读, Phantoms read)的问题, 然而对于写倾斜中的幻影问题,就是需要使用串行化的手段来解决。

如何避免写倾斜
  • 在应用程序中显式加锁

  • 数据库本身提供的约束,唯一性约束,触发器,物化视图,外键。

    • 例如账号系统要求username唯一的问题,可以使用唯一性约束来实现。

    • 缺点:通常只能解决一部分特定的write skew问题,而且实现往往比较丑陋。

  • 物化冲突

    • 主题思想是为查询条件加上互斥锁, 例如医生值班问题中: SELECT count() FROM doctors WHERE on_call = true and shift_id=2345 for update 注:此处*for update 会给符合查询条件的记录加排它锁。

    • 如果符合查询条件的记录不存在,引入虚拟的记录来实现加锁的操作,例如:对于会议室预定系统,可以把时间分成半小时一份的若干分片,然后这些分片和会议室ID的笛卡尔积形成一张表,然后就可以使用这张表给并发的预定会议请求加锁(每个预定操作都锁住这张表中的一些格子)

    • 缺点:有些write skew的场景难以用物化冲突来实现;物化冲突往往还是需要应用层显式地锁住查询所返回的记录(可能是虚拟记录);物化冲突如果隐式的帮应用锁住虚拟记录,可能会造成一系列难以理解的现象,例如MySQL的间隙锁。

串行化(Serializability)

定义

正如字面意思,串行化就是指串行的执行事务。

目前业界实现串行化的技术选型一般有以下三种:串行执行(Actual Serial Execution),两阶段锁(Two-Phase-Locking, 2PL),串行化快照隔离(Serializable Snapshot Isolation)

串行执行(Actual Serial Execution)

随着RAM的发展,以及一些研究者发现OLTP类的事务一般都执行时间很短,2007年左右,业界开始探索使用单线程执行事务,典型实现:Redis,VoltDB/H-Store, Datomic。特点:

  • 每个事务都很短,执行很快。因为慢事务会挂起后续所有的事务。

  • 数据存一般都放在内存中,因为读磁盘的操作太慢,会使后续的所有事务都需要等待。

  • 最大写吞吐量受限于单个CPU的处理能力。

  • 虽然可以通过根据key分区,分库的方式来提交写吞吐量,但是对于需要跨分区处理的事务存在明显的性能瓶颈。

两阶段锁(Two-Phase-Locking, 2PL)

2PL即读写锁的思路, 可以参考MySQL里的共享锁和排它锁。MySQL(InnoDB), SQL Server的串行化隔离级别,以及DB2的repeatable read隔离级别都是用两阶段锁的思路实现的。两阶段锁的处理流程如下:

  1. 在事务进行读取操作的之前,必须先获取读取对象上的读锁(lock in shared mode),一个对象上可以同时加多个读锁。但是存在读锁未释放的情况下,此时如果有写请求,则必须等待。

  2. 在事务进行写/修改数据对象之前,必须先要获取这个对象上的写锁(lock in exclusive mode);此时该对象上不允许有其他锁(读锁或写锁)存在;如果有其他锁存在,则必须等待。

  3. 如果一个事务先读取对象,然后修改对象。则需要先把获取到的读锁升级成写锁,升级写锁的处理过程和直接获取写锁类似。

  4. 在事务提交或中止完成的时候,释放锁。在事务执行过程中需要持有锁,在事务提交或中止完成的时候释放锁,这就是两阶段锁为什么叫两阶段锁。

实现

  • 宾语锁(predicate locks): 即对事务的where 条件进行加锁检查。

  • 索引范围锁(index-range locks):又称为next key locking,即对事务的where条件中的索引范围进行加锁,如果where条件里没有索引退化成表锁。

串行化快照隔离(Serializable Snapshot Isolation, SSI)

串行化快照隔离技术出现的相对较晚,2008年才被首次提出,在实践中性能还有待进一步验证。但从理论上来看,SSI技术不仅拥有快照技术的优点,读操作不阻塞写操作,写操作也不阻塞读操作,而且借助乐观的并发控制手段,解决了写倾斜的问题。目前SSI技术已经在PostgreSQL(>= 9.1), FoundationDB中得到了使用。

乐观并发控制

两阶段锁这类并发控制机制被称为悲观并发控制机制,悲观并发控制基于的理念是:为了避免出现并发错误,在操作数据对象之前先获取一个锁,如果另一个事务也要操作同一个数据对象则需要阻塞等待。乐观并发控制机制的理念是,不管有没有并发冲突的风险,先让事务并行执行,在事务提交的时候再检查是否有并发冲突的情况发生,如果没有则提交,如果有则中止并强制重试。乐观并发控制的主要缺点在于如果存在很多争用(contention)(很多事务试图访问相同的对象),这种场景下,乐观并发控制往往会因为需要中止很大一部分事务从而表现的性能不佳。如果系统已经接近了最大吞吐量,来自重试事务的额外负载可能会使系统的性能变得更糟。但是,如果有足够的备用容量,并且事务之间的争用不是太高,乐观并发控制技术往往比悲观并发控制的要好很多。

仔细观察上文中写倾斜的例子,不难发现这些写倾斜的事务都先基于一个前提(premise) 然后采取的行动(事务开始时候的事实,例如:“目前有两名医生正在值班”)。之后当事务要提交时,原始数据可能已经改变——前提可能已不再成立。问题在于数据库不知道应用程序的逻辑如何使用开始查询的数据,所以为了在这种条件下提供串行化的隔离级别,数据库系统必须要能检测到一个事务是否有可能会基于一个过时的前提做操作,如果检查到这种可能就中止该事务并稍后强制重试。数据库系统如何判断前提(premise)可能已经发生了变化呢?有两种情况需要考虑:

  • 检查对过时的MVCC对象的读取(读之前存在未提交的写入)

  • 检查影响先前读取的写入(读之后发生了写入)

检查过时的MVCC读(Detecting stale MVCC reads)

img

检查影响先前读取的写入(Detecting writes that affect prior reads)

img

分布式下的并发问题

隔离级别部分我们讨论的主要问题是:当数据库系统中有多个事务并发时,我们需要一些技术手段来避免由于临界条件所导致的竞态问题。然而在分布式数据系统中,我们要解决的问题主要是,当有多个读写请求并发执行时,我们需要一些技术手段来规避由于分布式系统中各个副本之间数据不同步(可能因为网络延时,单点故障等原因),导致的数据不一致的问题。

CAP定理: CAP分别代指 Consistency(一致性), Availability(可用性), Partition tolerance(分区容错性)。这个理论的实际意义在于,算术上已经证明了CAP这三个条件无法同时满足,由于网络中断之类的问题真实存在,因此Partition tolerance 是必须的,所以分布式系统设计的问题,就是根据业务属性在CA之间做出最佳权衡。

BASE理论:BASE分别代指Basically Available(基本可用),Soft state(软状态),Eventually consistent(最终一致性)。这个理论描述了分布式数据库在CA之间权衡之后,分布式下弱事务的特征。

单leader复制模型(Single-leader model)

单leader模式下,所有的写请求都路由到leader节点,因此write-write冲突问题和单机情况下相同(解决方案参考上文)。然而对于read-after-write冲突,leader节点宕机,leader节点与从属节点被网络故障隔离(脑裂)等问题,仍然需要仔细解决。

同步复制VS异步复制

  • 同步复制:

    • 优点:read-after-write能保证数据一致性。

    • 缺点:丧失了大部分的可用性,单节点故障就会导致系统整个不可用。leader节点故障需要手工切换。

  • 异步复制:

    • 优点:可用性很高,可以容忍从节点故障。

    • 缺点:丧失了大部分的一致性(虽然会最终一致),read-after-write冲突,导致读取的数据不一致。leader节点故障后,重新选择一个从节点作为主节点可能存在数据丢失。

  • 半同步:leader节点和从属节点有些是同步复制,有些是异步复制。

    • 优点:折中了同步复制和异步复制的优缺点,可以容忍异步复制的从节点故障,读同步从节点能得到数据一致性。

    • 缺点:对于异步复制的从节点read-after-write的问题仍旧存在;leader故障时,仍旧需要手工切换主节点。

最终一致性存在什么问题

读己之写(Reading Your Own Writes)

img

对于异步复制(最终一致性),一个用户在写请求之后,立即查询他写入的数据,可能由于读请求落到了还没更新的副本节点上,导致用户看不到他写入的内容。这种不一致的规避手段有几下几种:

  • 读取用户可能更改的内容时,从master读。其他内容,可以从slaver读。例如:用户读取自己的账号信息,朋友圈时,从master读;读取其他人的账号信息和朋友圈时,从slaver读。

  • 记录每个用户的最后更新信息的时间,以及每个slaver落后于master的时间gap,从而判断读请求是读master,还是读slaver。

  • 每个客户端都记录一个该客户端的最后更新时间,这个时间可以是逻辑时间,例如操作日志序列号。通过判断client的最后更新时间,以及slaver的最新更新时间,可以确定哪些slaver可以为这个client服务。

单调读(Monotonic Reads)

img

如图,用户1234添加了一条评论,然后用户2345先从一个延迟比较小的从库上读取的时候看到了评论的内容,然后用户2345刷新一下,从一个延迟比较大的从库上进行重新读取的时候,发现评论不见了。假设评论不支持删除,用户2345会感到非常困惑,仿佛发生了时光倒流。单调读是一种介于强一致性最终一致性之间的一种保证:一个用户依次进行多次读取,如果先读取到了较新的数据,后续不会读取到更旧的数据。实际应用中,一般使用下面的方法来保证单调读:

  • 指定用户从指定的副本slaver上读取数据,例如可以根据user_id进行hash,也可以根据地理位置,从最近的副本集群上读取。不过如果副本slaver故障,就需要重选一个副本slaver。

一致前缀读(Consistent Prefix Reads)

img

一致前缀读是一种因果关系。想象一下Poons先生和Cake夫人之间的以下对话:

Mr. Poons: Mrs. Cake,你能看到多远的未来?

Mrs. Cake: 大约十秒钟,Mr. Poons.

这两句话之间有因果关系:Cake夫人听到了Poons先生的问题并回答了这个问题。如果第三个人,先从一个延迟较小的从库上读取到了Mrs. Cake的话,然后又从一个延迟较大的从库上读取到了Mr.Poons的话,就会非常费解,仿佛Mrs.Cake真的有预测未来的能力。一致前缀读(consistent prefix reads) 是存在于分区(partitioned)或分片(shared)数据库中的一类特殊问题。一致前缀读需要保证:如果一系列写入按某个顺序发生,那么任何人读取这些写入时,也会看见它们以同样的顺序出现。 可以使用下面的方法来解决:

多leader复制模型(Multi-leader model)

img

多leader复制模型(又称多活模型)在存在多个数据中心时,非常有用。每个数据中心都是一个单主复制系统,可以就近提供服务,如果一个数据中心被网络故障隔离,另一个数据中心仍旧能继续提供服务。多个数据中心之间,通过leader同步数据,然而由于多个leader的存在,就需要解决并发写引起的冲突问题。

避免冲突

不同的user分配默认路由给不同的数据中心(不同的leader),例如中国北部地区的用户写宁夏数据中心的leader节点,中国南部地区的用户写贵州数据中心的leader节点。如果其中一个数据中心的leader发生故障,或者用户从一个地区迁徙到另一个地区,可能需要重新配置路由规则。

收敛到一致的状态

单leader数据库按顺序提交写操作:如果同一个字段有多个更新,则最后一个写操作将确定该字段的最终值。对于多leader数据库,我们很难界定跨leader的两个写操作谁前谁后,但是我们可以定义一些规则,使得所有副本在所有变更复制完成时都收敛至一个相同的最终值。可以使用的方法如下:

  • 给每个写请求分配一个uuid,发生写冲突时,以uuid比较大的那个写入为准,这种方法存在写丢失的情况(或者使用UTC时间戳进行比较)。

  • 给每个集群分配一个编号,如果两个集群写冲突,以集群编号大的那个集群的写入为准,这种方法也存在写丢失。

  • 合并写冲突的内容: 以某种方式将冲突的值合并在一起,例如,按字母顺序排序,然后连接它(两个人同时编辑一篇文章的题目,最终可以连接成:A标题/B标题)。

  • 以一种特定的数据结构记录下冲突的内容,并且在应用程序中写相应的冲突解决的逻辑(例如在用户下次查看时,提示用户做出选择)

无leader复制模型(Leaderless model)

img

在无leader复制模型的实现中,客户端一般发送读写请求到所有副本,并等待一定数量的读写请求正常返回。需要等待读请求的正常返回数量(r),写请求正常返回的数量(w)与总体副本的数量(n) 需要满足法定人数(quorum)关系:

1
w + r > n

无主复制模型可能存在的问题

  • 如果两个写入同时发生,不清楚哪一个先发生。在这种情况下,唯一安全的解决方案是合并并发的写入。例如,按字母顺序排序,然后连接它(两个人同时编辑一篇文章的题目,最终可以连接成:A标题/B标题)。

  • 如果写操作与读操作同时发生,写操作可能仅反映在某些副本上。在这种情况下,不确定读取操作是返回旧值还是新值。(解决这种并发冲突可以使用version verctor技术,记录各个操作之间的依赖关系,如果操作有依赖则需要返回新值)

  • 如果写操作在某些副本上成功,在一些节点上写入失败(例如,因为某些节点上的磁盘已满),最终在小于w个副本上写入成功了,因此整体上判定为写入失败,但整体写入失败并没有在写入成功的副本上进行回滚。这意味着如果一个写入虽然报告失败,后续的读取操作仍然可能会读取到这次失败写入操作的更改。

  • 如果携带新值的节点故障,数据从带有旧值的副本中恢复,则存储新值的副本数可能会低于w,从而打破了法定人数条件。

线性一致性(Linearizability)

上文中我们看到在最终一致性情况下,有reading your own writes,单调读,一致前缀读等很多不一致问题需要解决。而且对于应用程序开发人员来说,基于最终一致性的保证进行编程,也往往比较困难。线性一致性(Linearizability)是一种强一致性的保证,解决了最终一致性的问题,线性一致性的基本的想法是让整个系统看起来好像只有一个数据副本,而且所有的操作都是原子性的。在一个线性一致的系统中,一个客户端一旦成功完成了写操作,后续所有从这个数据库读数据的客户端保证能够看到刚刚写入的值。也就是说在线性一致性的保证下,数据库系统能够保障读到的值是最近的,最新的,而不是来自陈旧的缓存或副本。换句话说,线性一致性是一个新鲜度保证(recency guarantee)。如下图所示,一旦一个写操作完成,后面的所有读操作都能看到该写操作执行的结果。

img

线性一致性的核心特质是“表现得好像只有一个数据副本,而且所有的操作都是原子性的”,真正的单副本实现线性一致性很容易,只需要保证操作的原子性即可。然而,单副本无法提供分区容错,没办法解决单点问题。解决单点问题的主要方法是复制,所以下面是对在各种复制模型中对实现线性一致性的讨论:

  • 单主复制(可能线性一致)

    • 写操作都需要通过leader节点写入,如果读操作都读取主节点或同步复制的从节点,则能保证线性一致性的语义(可以对数据进行分区,每个分区有一个单独的leader,不会影响线性一致性,因为线性一致性只是对单一对象的保证)。

    • 异步复制往往不能满足线性一致性。

  • 共识算法(线性一致)

    • 共识协议包含leader选举,防止脑裂,防止陈旧副本等措施,可以安全地实现线性一致性。通常情况下,可以认为共识算法的目的就是要实现线性一致性,线性一致性和共识之间可以相互转换。
  • 多主复制(非线性一致)

    • 基于多主复制的系统通常不是线性一致的,因为需要同时在多个节点上处理写入,解决冲突,并将其异步复制到其他节点。
  • 无主复制(往往不是线性一致的)

    • 仅仅使用严格的法定人数读写( w + r> n )并不能保证无主复制系统是线性一致的,例如如果使用基于时钟决定“最后写入胜利的”write-write的冲突解决规则,可以确定是非线性的。另外,quorum算法中如果读请求读取到了陈旧值,但是没有进行同步修复,也可能导致非线性。

img

共识算法

共识算法的目标看起来虽然很简单,让几个节点就某件事达成一致(get serveral nodes to agree on something),然而在实现中却需要处理大量难以觉察的微妙问题。如果有其他方案,尽量不要自己实现共识算法。

两阶段提交( two-phase commit)

两阶段提交(2PC, two-phase commit)算法是解决原子提交问题最常见的办法,并在各种数据库、消息队列和应用服务器中都有实现。事实证明2PC也是一种共识算法,但不是一个非常好的算法。

img

详细分解两阶段提交的步骤如下:

  1. 当应用想要启动一个分布式事务时,它向协调者请求一个事务ID。此事务ID是全局唯一的。

  2. 应用在每个参与者上启动单节点事务,并在单节点事务上捎带上这个全局事务ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题(例如,节点崩溃或请求超时),则协调者或任何参与者都可以中止该事务。

  3. 当应用准备提交时,协调者向所有参与者发送一个准备请求,并打上全局事务ID的标记。如果发向任意一个参与者的请求失败或超时,则协调者向所有参与者发送针对该事务ID的中止请求。

  4. 参与者收到准备请求时,需要确保在任意情况下都确实可以提交事务。这包括将所有事务数据写入磁盘(出现故障,电源故障,或硬盘空间不足都不能是稍后拒绝提交的理由)以及检查是否存在任何冲突或违反任何约束。参与者只要向协调者回答了“是”,就相当于该节点承诺,只要请求,这个事务就一定可以不出差错地提交。

  5. 当协调者收到所有参与者对准备请求的答复时,会就对提交或中止事务作出明确的决定(只有在所有参与者投赞成票的情况下才会提交)。协调者必须把这个决定写到磁盘上的事务日志中,如果它随后崩溃了,恢复后也能知道自己所做的决定。这被称为提交点(commit point)

  6. 协调者把决定落盘之后,就会把提交或放弃请求会发送给所有参与者。如果这个请求失败或超时,协调者必须一致保持重试,直到成功为止。没有回头路:一旦做出了决定,不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃,事务将在其恢复后提交 — 由于参与者已经投了赞成票,因此恢复后它也不能拒绝提交。

三阶段提交

两阶段提交被称为阻塞(blocking)原子提交协议,因为存在2PC可能卡住并等待协调者恢复的情况。理论上,可以使一个原子提交协议变为非阻塞(nonblocking)的,以便在节点失败时不会卡住。 作为2PC的替代方案,已经提出了一种称为三阶段提交(3PC)的算法。然而,3PC假定网络延迟有界,节点响应时间有限;在大多数具有无限网络延迟和进程暂停的实际系统中,它并不能保证原子性;出于这个原因,2PC仍然在被使用。

Raft/Paxos/Zab/Viewstamped Replication

共识算法在实现中需要处理大量的微妙细节,所以这里只是简单地介绍一下共识算法的一些上层理念。总体上共识算法必须满足下面的几个性质:

  • 一致同意(Uniform agreement): 没有两个节点的决定不同。

  • 完整性(Integrity):没有节点决定两次,即决定后就不能反悔。

  • 有效性(Validity):如果一个节点决定了值 v ,则 v 由某个节点所提议。

  • 终止(Termination): 由所有未崩溃的节点来最终决定值。

其中一致同意完整性的属性定义了共识的核心思想:每个节点都同意了相同的结果,一旦同意了,就不能再改变主意。终止属性包含了分区容错的思想,事实上共识算法也需要在大部分节点都正常工作的情况下,才能安全的达成共识,但是可以容忍一小部分节点宕机或者被网络隔离。(有效性只是为了定义更严谨,不然,你可能可以实现一个一直投票为null的共识算法。)

在实际实现中,这几种共识算法内部都以某种形式使用一个领导者,但它们并不能保证领导者是独一无二的。相反,它们可以做出更弱的保证:协议定义了一个任期号码,并且保证每个任期中领导者是唯一的。每次当现任领导被认为挂掉的时候,节点间就会开始一场投票,以选出一个新领导。这次选举被赋予一个递增的任期编号,因此任期编号是全序且单调递增的。如果两个不同任期的领导者之间出现冲突(也许是因为前任领导者实际上并未宕机),那么带有更高任期编号的领导说了算。

在任何领导者被允许决定任何事情之前,必须先检查是否存在其他带有更高任期编号的领导,因此我们需要两轮投票:第一次是为了选出一位领导者,第二次是对领导者的提议进行表决。问题的关键在于,这两次投票的法定人群必须相互重叠(overlap):如果一个提案的表决通过,则至少得有一个参与投票的节点也参加过最近的领导者选举。如果在一个提案的表决过程中没有出现更高的任期编号,那么现任领导者就可以得出这样的结论:没有发生过更高任期的领导选举,因此可以确定自己仍然在领导,然后它就可以安全地对提议值做出决定。

参考资料