DDIA 7 事务 读薄

DDIA 读书笔记

注：本人更倾向于将skew翻译成偏差而不是倾斜

1. ACID

Atomicity（原子性）

出错时终止事务，并将部分完成的写入全部丢弃。

一般来说，原子指的是不能分解成更小的部分的东西。如果写操作被组合到一个原子事务中，并且由于一个错误，事务不能完成，那么事务将被中止，数据库必须丢弃或撤消它在该事务中所做的任何写入操作。原子性简化了数据库的数据模型：如果一个事务被中止时，应用程序可以确保它没有任何改变，因此可以被重试。

Consistency（一致性）

应用层面的属性，数据中没有脏数据。

一致性的表述是：数据库之中的数据必须始终正确。例如，在一个会计系统，所有账户的收支必须平衡。应用程序有责任正确定义其事务，从而保持一致性。这不是数据库能保证的：如果你写了违反你的不变量的坏数据，数据库不能阻止你。应用程序可能会依赖于数据库的原子性和隔离性以达到一致性。

Isolation（隔离性）

并发执行的事务相对相对隔离。

Durability（持久性）

可靠的介质写入数据，不用担心数据丢失。

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

单对象写入

单个对象发生变化的时候，原子性和隔离性也是适用的。有如下场景：

在向数据库写入20KB的JSON文档：

在发送了第一个10KB之后网络连接中断，数据库是否只存储了无法完整解析的10KB JSON片段？
如果数据库在覆盖磁盘现有数据时发生电源故障，最终新值是否会和旧值混杂在一起？
如果在写入的过程中另一个客户端读取该文档，是否会看到部分更新的文档内容？

事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制。

多对象事务的必要性

没有原子性，错误处理就要复杂得多，缺乏隔离性，就会导致并发问题。

怎样确定是同一个事务里面的操作？一般的关系型数据库采用同一条TCP连接来区分。

处理错误和中止

尽管重试一个中止的事务是一个简单而有效的错误处理机制，但它并不完美：

问题	方案
事务实际上已经执行成功，网络传输时发生意外，让客户端看起来事务失败。那么重试会导致重复执行。	需要额外的应用层删除重复数据。
如果错误是因为系统超负荷，重试会使情况更糟糕。	设置重试次数上限
如果出现了永久性故障（例如违反约束），则重试毫无意义	不要重试
如果已经产生数据库之外的副作用（例如发邮件），则就算事务中止，副作用也已生效	可以考虑二阶段提交
客户端在重试的过程中也失败了，则没有其它应用负责重试	待写入数据可能会丢失

二阶段提交基本算法：

第一阶段(提交请求阶段)

协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者节点的响应。

参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。

各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个"同意"消息；如果参与者节点的事务操作实际执行失败，则它返回一个"中止"消息。

有时候，第一阶段也被称作投票阶段，即各参与者投票是否要继续接下来的提交操作。

第二阶段(提交执行阶段)

成功

当协调者节点从所有参与者节点获得的响应消息都为"同意"时：

协调者节点向所有参与者节点发出"正式提交"的请求。

参与者节点正式完成操作，并释放在整个事务期间内占用的资源。

参与者节点向协调者节点发送"完成"消息。

协调者节点收到所有参与者节点反馈的"完成"消息后，完成事务。

失败

如果任一参与者节点在第一阶段返回的响应消息为"终止”，或者协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

协调者节点向所有参与者节点发出"回滚操作"的请求。

参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。

参与者节点向协调者节点发送"回滚完成"消息。

协调者节点收到所有参与者节点反馈的"回滚完成"消息后，取消事务。

有时候，第二阶段也被称作完成阶段，因为无论结果怎样，协调者都必须在此阶段结束当前事务。

算法示意
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 协调者                                              参与者
                              QUERY TO COMMIT
                -------------------------------->
                              VOTE YES/NO           prepare*/abort*
                <-------------------------------
commit*/abort*                COMMIT/ROLLBACK
                -------------------------------->
                              ACKNOWLEDGMENT        commit*/abort*
                <--------------------------------  
end

3. 弱隔离级别

弱隔离级别可以防止下面的某些异常，但还需开发人员手动处理其他复杂情况（例如：显示加锁），只有序列化隔离可以防止下述所有问题，在后文会详细描述。下述异常的具体事例会在后文详细指出。

3.0 Overview

脏读

客户端读到了其他客户端尚未提交的写入。
脏写

客户端覆盖了另一个客户端尚未提交的写入。
读偏差（不可重复读）

客户在不同的时间点看到了不同的值。（例如在银行转账动作和提交动作之间和之后查询数据库）
更新丢失

两个客户端同时执行读取-修改-写入操作序列，出现了其中一个覆盖了另一个的写入，但又没有包含对方最新的情况，最终导致了部分修改数据发生了丢失。
写偏差

事务首先查询数据，根据返回的结果作出某些决定，然后修改数据库。当事务提交时，支持决定的前提条件已不在成立。
幻读

事务读取了某些符合查询条件的对象，同时另一个客户端执行写入，改变了先前的查询结果。

3.1 读已提交（Read Committed）

最基本的事务隔离级别是读已提交，它提供了两个保证：

从数据库读时，只能看到已提交的数据（没有脏读（dirty reads））。
写入数据库时，只会覆盖已经写入的数据（没有脏写（dirty writes））。

防止脏读：

事务的任何写入只有在成功提交之后，才能被他人观察到。

例子：

如果事务需要更新多个对象，脏读意味着另一个事务会看到部分更新，而非全部。例如用户看到了新的未读电子邮件，而看不到未读计数器的更新，会造成用户的困惑。
如果事务发生中止，则所有操作都需要回滚。如果发生了脏读，意味着会看到一部分稍后会被回滚的数据，而这些数据并没提交到数据库中。之后引发的后果可能难以预测。

防止脏写：

如果两个事务同时尝试更新相同的对象，通常是推迟第二个写请求，直到前面的事务完成提交或中止。

例子：

如图，Alice和Bob尝试购买同一辆车，购买汽车需要两次数据库写入（更新买家和更新发票），而图中的操作车主被改为Bob，而发票却给了Alice。

读提交并不能解决图7-1中计数器增量的竞争情况，对于后者，第二次写入确实在第一个事务提交后才执行，虽然不属于脏写，但是计数器结果仍然是错的。在“防止更新丢失”中，会提到如何安全递增计数器。

实现读已提交：

防止脏写：行级锁。当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。

防止脏读：一种方式是使用相同的锁。但这会带来性能问题。大多数数据库会维护旧值和当前持锁事务将要设置的新值这两个版本。提交前，其它读操作会读到旧值，提交后会读到新值。

3.2 快照级别隔离与可重复读

爱丽丝在银行有1000美元的储蓄，分为两个账户，每个500美元。现在一笔事务从她的一个账户中转移了100美元到另一个账户。如果她在事务处理的同时查看其账户余额列表，不幸地在转账事务完成前看到收款账户余额（余额为500美元），而在转账完成后看到另一个转出账户（已经转出100美元，余额400美元）。对爱丽丝来说，现在她的账户似乎只有900美元——看起来100美元已经消失了。

这种异常被称为不可重复读（nonrepeatable read）或读取偏差（read skew）：如果Alice在事务结束时再次读取账户1的余额，她将看到与她之前的查询中看到的不同的值（600美元）。在读已提交的隔离条件下，不可重复读被认为是可接受的：Alice看到的帐户余额时确实在阅读时已经提交了。

快照隔离：每个事务都从数据库的一致快照（consistent snapshot） 中读取——也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

实现快照隔离：多版本并发控制（MVCC, multi-version concurrentcy control）, 一种典型的方法是读已提交为每个查询使用单独的快照，而快照隔离对整个事务使用相同的快照。

表中的每一行都有一个 created_by 字段，其中包含将该行插入到表中的的事务ID。此外，每行都有一个 deleted_by 字段，最初是空的。如果某个事务删除了一行，那么该行实际上并未从数据库中删除，而是通过将 deleted_by 字段设置为请求删除的事务的ID来标记为删除。在稍后的时间，当确定没有事务可以再访问已删除的数据时，数据库中的垃圾收集过程会将所有带有删除标记的行移除，并释放其空间。

观察一致性快照的可见性规则：

读事务开始时，创建该对象的事务已经提交。
对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交。

索引和快照隔离

索引如何在多版本数据库中工作？

一种选择是使索引简单地指向对象的所有版本，并且需要索引查询来过滤掉当前事务不可见的任何对象版本。当垃圾收集删除任何事务不再可见的旧对象版本时，相应的索引条目也可以被删除。
每个写入事务（或一批事务）都会创建一颗新的B树，当创建时，从该特定树根生长的树就是数据库的一个一致性快照。没必要根据事务ID过滤掉对象，因为后续写入不能修改现有的B树；它们只能创建新的树根。但这种方法也需要一个负责压缩和垃圾收集的后台进程。

解决读取偏差：

快照隔离，数据库在一个对象中维护多个时间点上的值
事务具有一个自增ID，这个ID相当于时间点；事务只能读取到时间点比他早的值

3.3 防止更新丢失

写事务还会带来一些其他值得关注的冲突问题，最著名的就是更新丢失问题。前面图7-1就是一个著名的例子。这种冲突还可能发生在其他不同的场景：

递增计数器（觉得是计数器而不以为然？那换成账户余额）
对某复杂对象对的一部分内容执行修改，例如对JSON文档中一个列表添加新元素（需要读取&解析文档，执行更改并写回修改后的文档）
两个用户同时编辑wiki页面，且每个用户都尝试将整个页面发送到服务器，覆盖数据库中现有内容以使更改生效。

解决方案：

原子写
- 许多数据库提供了原子更新操作，从而消除了在应用程序代码中执行读取-修改-写入序列的需要。如果你的代码可以用这些操作来表达，那这通常是最好的解决方案。例如，下面的指令在大多数关系数据库中是并发安全的：
- 1
  
  UPDATE counters SET value = value + 1 WHERE key = 'foo';
显式锁定
- 如果数据库的内置原子操作没有提供必要的功能，防止丢失更新的另一个选择是让应用程序显式地锁定将要更新的对象。然后应用程序可以执行读取-修改-写入序列，如果任何其他事务尝试同时读取同一个对象，则强制等待，直到第一个读取-修改-写入序列完成。
- 1 2 3 4 5 6 7
  
  BEGIN TRANSACTION; SELECT * FROM figures WHERE name = 'robot' AND game_id = 222 FOR UPDATE; UPDATE figures SET position = 'c4' WHERE id = 1234; COMMIT;
  FOR UPDATE子句告诉数据库应该对该查询返回的所有行加锁。
自动检测
- 另一种方法是允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其读取-修改-写入序列。（MySQL不检测）
比较并设置(CAS)
- 只有当前值从上次读取时一直未改变，才允许更新发生。如果当前值与先前读取的值不匹配，则更新不起作用，且必须重试读取-修改-写入序列。

~~冲突解决与复制~~

题外话：分布式数据库中如果采用”最后写入胜利LWW”的冲突解决方案，则很有可能出现更新丢失的情况。

3.4 写偏差与幻读

两个事物读取相同的对象集合，然后更新其中的一些对象。如果更新的对象不同，可能会发生写入偏差；如果更新的对象相同，则可能发生脏写或丢失更新。

例如：你正在为医院写一个医生轮班管理程序。医院通常会同时要求几位医生待命，但底线是至少有一位医生在待命。医生可以放弃他们的班次（例如，如果他们自己生病了），只要至少有一个同事在这一班中继续工作。如果两人恰巧都感到身体不适，并同时点击了调班按钮，接下发生的事如图7-8所示：

由于数据库采用的是快照级别隔离，两个检查都会返回有两名医生，所以两个事务都安全地进入下一个阶段。最后结果是没有医生在值班，显然违背了至少一名医生在班的业务要求。

更多写偏差的例子：

写偏差定义：

它既不是脏写，也不是丢失更新，因为这两个事务正在更新两个不同的对象（Alice和Bob各自的待命记录）。在这里发生的冲突并不是那么明显，但是这显然是一个竞争条件：如果两个事务一个接一个地运行，那么第二个医生就不能歇班了。异常行为只有在事务并发进行时才有可能。

幻读定义：

一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读。快照隔离避免了只读查询中幻读，但是在像我们讨论的例子那样的读写事务中，幻影会导致特别棘手的写入偏差情况。

如果事务是只读查询，则快照隔离可以解决。如果事务还有写操作，那就是发生了写倾斜，需要真正的可序列化隔离。

从读操作来看，写倾斜属于幻读。从写操作来看，写倾斜属于更新丢失。

—选自红旺语录

产生写偏差的原因：

上述所有写偏差的例子遵循了以下类似的模式：

首先输入一些匹配条件，即采用SELECT查询所有满足的行
根据查询的结果，应用层代码来决定下一步的操作（有可能继续，或者报告错误中止）
如果应用程序决定继续执行，他将发起数据库写入（INSERT，UPDATE或DELETE）并提交事务。而这个写操作可能会改变步骤2作出决定的前提条件。如果提交写入之后再重复执行步骤1的SELECT查询，就会返回不同结果（只有一名医生值班，会议室已被预订，棋盘已经出现数字，用户名已经被占用，余额已经不足等）。

解决方法：

for update 锁定一部分行，并告知数据库这些行用于更新；

这种方式仅适用于查询时能返回一部分行并修改这些行的情况。如果是先查询，发现没有，然后再添加一行，使得查询先决条件改变，那我们就不能预先锁定不存在的行
如果无法使用可序列化的隔离级别，则此情况下的次优选项可能是显式锁定事务所依赖的行。在例子中，你可以写下如下的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


BEGIN TRANSACTION;
SELECT * FROM doctors
  WHERE on_call = TRUE 
  AND shift_id = 1234 FOR UPDATE;
  
UPDATE doctors
  SET on_call = FALSE
  WHERE name = 'Alice' 
  AND shift_id = 1234;
    
COMMIT;

使用触发器（针对不同数据库）
物化冲突
- 把多个对象的冲突变成具体的行上的冲突
- 不到万不得已不要用
可序列化Serializable的隔离等级

上述**物化冲突（materializing conflicts）**的方法，因为它将幻读变为数据库中一组具体行上的锁冲突。不幸的是，弄清楚如何物化冲突可能很难，也很容易出错，而让并发控制机制泄漏到应用数据模型是很丑陋的做法。出于这些原因，如果没有其他办法可以实现，物化冲突应被视为最后的手段。在大多数情况下。可序列化（Serializable） 的隔离级别是更可取的。

4. 可序列化

可序列化（Serializability）隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样。因此数据库保证，如果事务在单独运行时正常运行，则它们在并发运行时继续保持正确 —— 换句话说，数据库可以防止所有可能的竞争条件。

目前大多数提供可序列化的数据库都使用了三种技术之一：

字面意义上地串行顺序执行事务。
两相锁定（2PL, two-phase locking），几十年来唯一可行的选择。
乐观并发控制技术，例如可序列化的快照隔离（serializable snapshot isolation）。

真正的串行执行

在单个线程上按顺序一次只执行一个事务。这样做就完全绕开了检测/防止事务间冲突的问题，由此产生的隔离，正是可序列化的定义。以下是满足串行执行的约束：

每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢。
写入吞吐量必须低到能在单个CPU核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
跨分区事务是可能的，但是它们的占比必须很小。

两阶段加锁（2PL）

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于共享模式（shared mode）或独占模式（exclusive mode）。锁使用如下：

若事务要读取对象，则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。
若事务要写入一个对象，它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁（无论是共享模式还是独占模式），所以如果对象上存在任何锁，该事务必须等待。
如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得排他锁相同。
事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是“两阶段”这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

性能：性能很差。这一部分是由于获取和释放所有这些锁的开销，但更重要的是由于并发性的降低。按照设计，如果两个并发事务试图做任何可能导致竞争条件的事情，那么必须等待另一个完成。

谓词锁（predicate lock）

谓词锁类似于前面描述的共享/排它锁，但不属于特定的对象（例如，表中的一行），它属于所有符合某些搜索条件的对象，

这里的关键思想是，谓词锁甚至适用于数据库中尚不存在，但将来可能会添加的对象（幻象）。如果两阶段锁定包含谓词锁，则数据库将阻止所有形式的写入偏差和其他竞争条件，因此其隔离实现了可串行化。

索引区间锁

不幸的是谓词锁性能不佳：如果活跃事务持有很多锁，检查匹配的锁会非常耗时。因此，大多数使用2PL的数据库实际上实现了索引范围锁（也称为间隙锁（next-key locking）），这是一个简化的近似版谓词锁。例如扩大锁定范围为：某个时间点的所有房间或者该房间的所有时段。

无论使用哪种方式，查询条件都要附加到某个索引上。接下来，如果另一个事务想要插入、更新或删除同一个房间和/或重叠时段的预定，则肯定需要更新这些索引，就一定会与共享锁冲突，因此会自动处于等待状态直到共享锁释放。

这样就有效防止了写倾斜和幻读的问题。由于开销比谓词锁低得多，可以认为是一种比较好的折衷方案。

如果没有合适的索引可以施加区间锁，则数据库可以退回到对整个表施加共享锁。这种方法性能肯定不好，还会阻断其他事务的写操作，但的确可以保证安全性。

序列化快照隔离 (Serializable Snapshot Isolation)

悲观与乐观的并发控制

两阶段锁是一种所谓的悲观并发控制机制（pessimistic） ：它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。这就像互斥，用于保护多线程编程中的数据结构。

序列化快照隔离是一种乐观（optimistic） 的并发控制技术。在这种情况下，乐观意味着，如果存在潜在的危险也不阻止事务，而是继续执行事务，希望一切都会好起来。当一个事务想要提交时，数据库检查是否有什么不好的事情发生（即隔离是否被违反）；如果是的话，事务将被中止，并且必须重试。只有可序列化的事务才被允许提交。

如果存在很多争用（contention）（很多事务试图访问相同的对象），则表现不佳，因为这会导致很大一部分事务需要中止。如果系统已经接近最大吞吐量，来自重试事务的额外负载可能会使性能变差。

但是，如果有足够的备用容量，并且事务之间的争用不是太高，乐观的并发控制技术往往比悲观的要好。可交换的原子操作可以减少争用：例如，如果多个事务同时要增加一个计数器，那么应用增量的顺序（只要计数器不在同一个事务中读取）就无关紧要了，所以并发增量可以全部应用且无需冲突。

基于过期的条件做决定

数据库如何知道查询结果是否可能已经改变？有两种情况需要考虑：

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

检测是否读取了过期的 MVCC 对象

为了防止这种异常，数据库需要跟踪一个事务由于MVCC可见性规则而忽略另一个事务的写入。当事务想要提交时，数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样，事务必须中止。

为什么要等到提交？当检测到陈旧的读取时，为什么不立即中止事务？

如果事务是只读事务，则不需要中止，因为没有写入偏差的风险。
事务可能被提交的时候中止或者可能仍然未被提交，因此读取可能终究不是陈旧的。

检测写是否影响了之前的读

当事务写入数据库时，它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁，但锁并不会阻塞事务指导其他读事务完成，而是像警戒线一样只是简单通知其他事务：你们读过的数据可能不是最新的啦。

可序列化的快照隔离的性能

与往常一样，许多工程细节会影响算法的实际表现。例如一个权衡是跟踪事务的读取和写入的粒度（granularity）。如果数据库详细地跟踪每个事务的活动（细粒度），那么可以准确地确定哪些事务需要中止，但是簿记开销可能变得很显著。简略的跟踪速度更快（粗粒度），但可能会导致更多不必要的事务中止。

可序列化快照隔离的最大优点是一个事务不需要阻塞等待另一个事务所持有的锁。就像在快照隔离下一样，写不会阻塞读，反之亦然。这种设计原则使得查询延迟更可预测，变量更少。特别是，只读查询可以运行在一致的快照上，而不需要任何锁定，这对于读取繁重的工作负载非常有吸引力。

与串行执行相比，可序列化快照隔离并不局限于单个CPU核的吞吐量。

中止率显著影响SSI的整体表现。例如，长时间读取和写入数据的事务很可能会发生冲突并中止，因此SSI要求同时读写的事务尽量短（只读长事务可能没问题）。对于慢事务，SSI可能比两阶段锁定或串行执行更不敏感。

5. 总结

	脏读	脏写	不可重复读	写倾斜	幻读
读未提交 read uncommitted	×	×	×	×	×
读已提交 read committed	√	√	×	×	×
快照隔离, 也是可重复读 repeatable read	√	√	√	×	×
可序列化 serializable	√	√	√	√	√

文章目录