Distributed System Database

DDIA-事务

Posted by keys961 on March 8, 2019

本文大多说明的是单点下的事务，分布式场景较少涉及。

1. 理解事务

1.1. ACID

BASE: 即基本可用性（Basically Avaliable），弱状态（Soft state），最终一致性（Eventual consistency）。其唯一确定的是“它不是ACID”，此外没承诺任何东西。

1.1.1. 原子性

一组操作要么全部执行完毕，要么完全没有执行。即：出错时中止事务，将部分完成的内容回滚。

1.1.2. 一致性

不同场景下，“一致性”意义不同：

  • 数据复制时，引出副本的一致性（如最终一致性）
  • 一致性散列指动态分区再配合的方法
  • CAP中，一致性表示“线性化”（原子一致性/强一致性）
  • ACID中，一致性指数据库处于应用程序所期待的“预期状态”

本质上，是要求应用层维护状态一致（或恒等），应用程序有责任正确地定义事务来保证一致性。可以说，C本身不源于数据库。

1.1.3. 隔离性

并发执行的多个事务相互隔离，不能相互交叉。虽然它们可能同时进行，但事务提交后，结果必须和串行（一个接一个）执行相同，即可串行化。

而现实中，很少使用串行化隔离级别（因为性能），而使用弱隔离级别，提供比串行化更弱的保证，后面会叙述。

1.1.4. 持久性

一旦事务提交成功，即使存在硬件故障/数据库崩溃，事务写入的数据不会丢失。

对于单节点，其意味着数据被写入非易失存储设备；对于支持远程复制的数据库，持久性意味数据已被成功复制到多个节点。

1.2. 单对象与多对象事务操作

1.2.1. 单对象写入

原子性：利用日志恢复

隔离性：对象加锁

也可以用CAS的原子操作保证原子性和隔离性。

1.2.2. 多对象事务的必要性

许多情况下需要有：

  • 关系模型以及图模型下，处理“联系”时（外键/边）时，要处理这些引用的有效性
  • 文档模型下，若所有字段都在一个文档里，则可视为单个对象；但是缺乏Join支持的DB往往涉及反范式化，一次更新会涉及多个文档，则需要多对象事务
  • 存在二级索引时，还需要更新索引，即涉及到多个对象

虽然没有多对象事务保证，理论上也可以，但是上层处理异常时会非常复杂。

2. 弱隔离级别

2.1. 读已提交

最基本的隔离级别（有些还会有更弱的级别，叫做：读未提交，只防止脏写），只保证：

  • 防止脏读（读时，只能看到已提交的数据）
  • 防止脏写（写时，只会覆盖已提交的数据）

2.1.1. 防止脏读

脏读：事务读时，看见其它事务未提交的数据。

实现：（不上读锁）对于每个待更新的对象，维护一个旧值以及持有该对象锁的事务的新值，该事务提交前，其它事务读该对象的旧值，仅当提交后，才会读取到新值。

2.1.2. 防止脏写

脏写：先前的写入是事务的一部分，且事务未提交，该写入在事务提交前会被覆盖。

实现：先获取写入对象的锁，提交后再释放，从而延后其它事务对该对象的写入，防止被覆盖。

2.2. 快照级别隔离/可重复读

RC级别下，可能出现不可重复读/读倾斜的异常。

不可重复读/读倾斜：同一事务中，对某个相同对象的多次读取，值会变化。

在某些场景下，不可重复读不可以接受：

  • 备份场景，在RC下会产生部分旧版本数据和部分新版本数据，造成不一致
  • 分析查询与完整性检查，在RC下，部分新版本数据会导致分析结果无意义

解决该问题的方法常见有：实现快照隔离/可重复读级别。

该级别适用于：长时间运行只读查询的场景。读取时，能获取到对应时间点的一致性快照，查询结果含义明确。

2.2.1. 快照隔离/可重复读的实现——MVCC

脏写：通常采用上写锁的方式

脏读：不加锁，MVCC借鉴RC中防止脏读的方法，但更为通用。它保留了对象多个不同的提交版本（因此叫做多版本并发控制）。

在RC下，MVCC也适用，只需保留一个最新的已提交的旧版本和未提交的新版本。

RC下，每次查询单独创建一个快照；RR下，事务只使用一个快照。

2.2.2. 一致性快照的可见性原则

MVCC in MySQL

每个事务分配一个递增的版本号tid。每行记录有隐藏2列create_version, delete_version。

  • SELECT：返回create_version <= tid且delete_Version > tid || delete_version == null，其它不可见
  • INSERT：插入一行，create_version = tid
  • DELETE：对当前行，delete_version = tid
  • UPDATE：对当前行，delete_version = tid，另新建一行create_verison = tid

这里的可见只代表SELECT的可见，并不代表UPDATE/DELETE时的可见，即只读下保证了不出现幻读，但写的时候会出现幻读。

幻读：在一个读-写事务中，写操作（会附带一次当前读）证实之前的读是错误的，即之前的读成为鬼影（因为另一个事务的写入造成的）。

可见性原则

  • 每次事务开始时，列出其它所有正在进行或中止（Aborted）的事务，忽略它们的部分写入
  • 所有中止事务的所做的修改不可见
  • 较晚事务ID（晚于当前事务）的任何修改均不可见，不论它们是否提交
  • 除此之外，其它所有的写入对应用都是可见的。

换句话说，如果以下两个条件都成立，则可见一个对象：

  • 读事务开始时，创建该对象的事务已提交
  • 对象未被标记为删除，或已被标记为删除，但删除的事务在读事务开始时未提交

2.2.3. 索引和快照隔离

方案1：

索引直接指向对象的所有版本，然后过滤不可见的版本。后台GC决定删除某个旧版本时，对应索引条目也得删除。

方案2：

采用追加/写时复制的B-Tree，若更新，则创建一个新的副本，拷贝必要内容，然后让父结点（或递归直到根结点的所有结点）指向新结点。

每个写入事务会创建一个新的B-Tree Node，创建时，从特定的树根生长的树就是数据库的一个一致性快照。而根据事务ID过滤对象就不需要了，只需递归查找，因为后续的写入不会修改现有的B-Tree。此外，GC和压缩线程是必要的。

2.3. 防止更新丢失

更新丢失场景：在read-modify-write事务中，当两个事务在同样的数据对象上执行操作，出现一个覆盖另一个的写入，且没有包含对方最新值的情况。

如$T_1$执行：read(x), x = x + 1, write(x)的事务序列，$T_2$执行write(x)。在以下序列中会产生问题（初始x == 1）：

$T_{1}$begin $\rightarrow$ $T_{2}$begin $\rightarrow$ $T_2$write(x) == 3$\rightarrow\(T_2$`committed`$\rightarrow\)T_1$read(x) == 1（RR下）$\rightarrow$ $T_1$x = x + 1 ==> x == 2$\rightarrow$ $T_1$write(x) == 2$\rightarrow$ $T_1$committed。它覆盖了$T_2$的写入，写入丢失。

有多种解决方法。

2.3.1. 原子更新操作

避免在应用层执行read-modify-write，直接在数据库执行原子更新，避免更新丢失。以上面的为例，大部分数据库下都是并发安全的：

1

UPDATE counter SET value = value + 1 where key = 'foo';

实现通常有：

  • 对读取对象加X锁，保证更新提交之前没有其它事务能够读它（读是当前读）

    MySQL中，读分2类：

    • 当前读：
      • SELECTwith LOCK IN SHARE MODE，读取时上S锁
      • SELECTwith FOR UPDATE/INSERT/UPDATE/DELETE对相关行上X锁
    • 快照读：普通的SELECT，不上任何锁

  • 强制所有的原子操作都在单线程上执行

2.3.2. 显式加锁

若没有原子更新操作，可显式在读取时加锁，如：

1
2
3
4

BEGIN;
SELECT value FROM counter WHERE key = 'foo' FOR UPDATE; --Add lock
UPDATE counter SET value = value + 1 where key = 'foo';
COMMIT;

2.3.3. 自动检测更新丢失

允许并发执行read-modify-write，若检测到丢失更新，则中止事务并强制回退到安全的read-modify-write方式。

2.3.4. CAS

CAS通过无锁方式进行原子更新，通常配合一个循环实现。

2.3.5. 冲突解决与复制

加锁和原子更新的前提是只有一个最新的数据副本。

多主/无主复制下的多副本数据库，出现多个最新数据副本，加锁和原子更新不再适用。多副本数据库通常支持多个并发写，保留多个冲突版本，然后根据上层/特定数据结构解决和合并冲突。（取决于合并策略，若使用如“最后写入获胜”，写入仍会丢失）

2.4. 写倾斜/幻读

幻读：在一个读-写事务中，写操作（会附带一次当前读）证实之前的读是错误的，即之前的读成为鬼影（因为另一个事务的写入造成的）。

2.4.1. 出现的原因

操作模式为：

  1. 通过SELECT获得某些行的结果
  2. 根据结果，应用层代码决定是否继续写入，若写入，则执行3
  3. 若决定执行，则发起写入并提交事务，而该写入会改变2中的条件

例子：

1
2
3
4
5
6

--T1 & T2 [1]，假定结果为0
SELECT count(*) FROM users WHERE id = 1;
--T2, 结果为0，符合条件，插入 [2][3]，写入更改了[2]的条件
INSERT INTO user VALUES (1, 'AA');
--T1, 结果也为0，符合条件，插入 [2][3]
INSERT INTO user VALUES (1, 'AA'); --失败，T1[1]的读是错误的，幻读

对于T1事务而言，是不符合逻辑的（失败的），出现了幻读。

2.4.2. 解决方法

  1. 若步骤3写入的内容是步骤1查询的一部分，那么查询时FOR UPDATE是能保证不出现幻读
  2. 若步骤1查询的结果为空，无从对查询结果加锁，那么可以认为引入一些加锁对象，然后加锁，这叫实体化冲突

3. 串行化

3.1. 实际串行执行

即避免并发，转向单线程执行。

H-Store、Redis就是使用这种方式。

优点：可能效率更高，避免锁开销；

缺点：吞吐量上限是单个CPU核的吞吐量。

因此，事务也需要做出调整。

3.1.1. 采用存储过程封装事务

交互式事务处理会消耗大量资源在网络通信上（因为每一步读写都有网络通信开销），且交互式事务往往会等待请求，吞吐量低。

因此将整个事务代码打包成一个存储过程，并将所有数据全部加载到内存中，让存储过程高效执行，从而无需等待网络或I/O，减少了网络通信开销，提高吞吐量。

3.1.2. 分区

对于高写入需求的程序，单线程事务处理容易造成严重瓶颈。

可扩展到多个CPU核多个节点，构成集群，并分区（如Redis Cluster）。

而若事务跨分区（取决于数据结构，如键值比较容易切分，而如二级索引则需要大量的跨区协调），则需要协调，需要跨越所有分区加锁执行，严重影响性能。

3.1.3. 小结

实际串行执行下，需要事务满足：

  • 事务简短高效
  • 活动数据集可完全加载到内存，很少访问的数据可写入磁盘
  • 若写吞吐量要求高，要构建集群并分区
  • 跨分区事务最好避免

3.2. 2PL——唯一广泛使用的串行化算法

3.2.1. 实现

  1. 读取时，加S锁（若被其它事务加X锁，则等待）
  2. 写入时，加X锁（若被其它事务加了S或X锁，则等待）
  3. 先读后写，锁升级，从S到X
  4. 锁持续到事务结束后释放

2PL容易产生死锁，DB可以检测死锁并中止某个事务打破死锁，重试则有应用层实现。

3.2.2. 性能

访问延迟有很大的不确定性，容易死锁（从而造成重试），效率和性能比较低下。

3.2.3. 谓词锁

谓词锁：指锁住满足某一查询条件的所有数据项，它不仅包括当前满足条件的记录，也包括即将要插入，更新或删除并满足查询条件的数据项。

其它事务若要更新对象，首先检查旧值和新值是否都匹配谓词锁（事务查询时会尝试获取谓词锁，通常是共享的；更新时，获取独占的谓词锁），若别的事务持有这样的谓词锁并发送冲突，必须等到那个事务提交/中止后才能获取。

由于后面加粗内容所述，将谓词锁和2PL结合使用，可避免幻读。

2.4.1.中可能死锁

3.2.4. 索引区间锁

索引区间锁：对谓词锁的简化（锁过多，匹配耗时），将锁添加到索引项以及索引间隙上，当某个事务持有了该锁，其它事务不能在对应区间内更新数据（因为肯定会更新索引），从而避免了幻读。

它也有共享和独占两类

若没有适合的索引施加索引区间锁，那么可回退到整个表施加锁。（性能不好，但安全）

3.3. 可串行化的快照隔离

SSI算法提供可串行化的保证，却基于快照隔离/RR，是一种乐观的并发控制机制，性能损失很小。

多事务下，读-写不阻塞，仅当事务尝试提交时，才检测冲突。

3.3.1. 如何检测查询结果是否发生变化

  • 检测对旧MVCC对象版本的读取（读之前存在未提交的写入）
  • 检测影响先前读取的写入（读之后发生写入）

a) 检测对旧MVCC对象版本的读取

跟踪由于MVCC可见性规则而忽略的写操作，当事务提交时，检查跟踪的写操作现在是否提交，若已提交则中止事务并重试。

b) 检测影响先前读取的写入

与之前的“索引区间锁”类似，只有一点差异：SSI锁不会阻塞其它事务。

步骤：

  1. 事务尝试读取时，上共享索引区间锁
  2. 事务尝试修改时，可根据共享锁获取到读该条目的其它事务，并上独占锁（但不会阻塞其它事务的读，而是在读事务提交时告知它该数据可能发生变化）
  3. 然后类似规则a)，事务提交时，若它被通知到的变化已经被提交，那么事务中止、重试

3.3.2. 性能

权衡跟踪粒度：粒度小则元数据开销大，粒度大可能扩大受影响的范围

与2PL对比：不需等待其它事务所持有的锁，读写互不阻塞

与串行执行对比：可突破单个CPU核的限制

其它：事务中止比例显著影响SSI性能，因此读-写事务要尽可能短（读事务则无限制）

CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++