分布式数据库设计——分布式事务与数据恢复
摘要
主要是介绍分布式数据库的设计上在分布式事务与数据恢复处理⽅法。事务管理是数据库中存储引擎的⼀个相当独⽴并且重要的组件，它可以保证对数据库的⼀系列操作看起来就像只有⼀步操作⼀样。这⼤⼤简化了⾯向数据库的应⽤的开发，特别是在⾼并发场景下，其意义更为重要。
⼀、事务ACID原则
A：原⼦性
原⼦性保证了事务内的所有操作是不可分割的，也就是它们要么全部成功，要么全部失败，不存在部分成功的情况。成功的标志是在事务的最后会有提交（Commit）操作，它成功后会被认为整个事务成功。⽽失败会分成两种情况，⼀种是执⾏回滚（Rollback）操作，另⼀种就是数据库进程崩溃退出。
原⼦性是数据库提供给使⽤者的保证，是为了模拟现实原⼦操作，如上⽂提到的转账。在现实⽣活中，⼀些看似不可分割的操作转换为计算机操作却并不是单⼀操作。⽽原⼦性就是对现实⽣活中原⼦操作的保证。
C：⼀致性
⼀致性其实是受⽤户与数据库共同控制的，⽽不只是数据库提供的⼀个服务。它⾸先是⼀个业务层⾯的约束，⽐如开篇中的例⼦，甲向⼄转100 元。业务应⽤⾸先要保证在甲账户扣款 100 元，⽽且在⼄账户增加 100 元，这个操作所带来的⼀致性与数据库是⽆关的。⽽数据库是通过 AID 来保证这两个正确的动作可以得到最终正确的结果。
这⾥的⼀致性与模块⼀中的分布式⼀致性有本质区别，想了解详细对⽐的同学，请移步到“05 | ⼀致性与 CAP 模型：为什么需要分布式⼀致性”，这⾥就不进⾏赘述了。
I：隔离性
事务的⼀个伟⼤之处是能处理并发操作，也就是不同的事务在运⾏的时候可以互相不⼲扰，就像没有别的事务发⽣⼀样。做并发编程的同学会对此深有体会，处理并发操作需要的精⼒与经验与处理串⾏操作完全不在⼀个等级上。⽽隔离性恰好能将实际上并发的操作，转化为从使⽤者⾓度看却是串⾏的，从⽽⼤⼤降低使⽤难度。
当然在实际案例中，以上描述的强并发控制性能会偏低。⼀般数据库会定义多种的隔离级别来提供不同等级的并发处理能⼒，也就是⼀个事务在较低隔离级别下很可能被其他事务看见。详细内容我会在“隔离级别”部分进⾏说明。
D：持久性
持久性⽐较简单，就是事务⼀旦被提交，那么它对数据库的修改就可以保留下来。这⾥要注意这个“保存下来”不仅仅意味着别的事务能查询到，更重要的是在数据库⾯临系统故障、进程崩溃等问题时，提交的数据在数据库恢复后，依然可以完整地读取出来。
⼆、事务管理器
事务主要由事务管理器来控制，它负责协调、调度和跟踪事务状态和每个执⾏步骤。当然这与分布式事务两阶段提交（2PC）中的事务管理器是不同的，
2.1 页缓存
关于事务管理器，⾸先要提到的就是页缓存（Page Cache）或者缓冲池（Buffer Pool），它是磁盘和存储引擎其他组件的⼀个中间层。数据⾸先被写⼊到缓存⾥，⽽后同步到数据磁盘上。它⼀般对于其他组件，特别是对于写⼊来说是透明的，写⼊组件以为是将数据写⼊磁盘，实际上是写⼊了缓存中。这个时候如果系统出现故障，数据就会有丢失的风险。
缓存⾸先解决了内存与磁盘之间的速度差，同时可以在不改变算法的情况下优化数据库的性能。但是，内存毕竟有限，不可能将磁盘中的所有数据进⾏缓存。这时候就需要进⾏刷盘来释放缓存，刷盘操作⼀般是异步周期性执⾏的，这样做的好处是不会阻塞正常的写⼊和读取。
刷盘时需要注意，脏页（被修改的页缓存）如果被其他对象引⽤，那么刷盘后不能马上释放空间，需要等到它没有引⽤的时候再从缓存中释放。刷盘操作同时需要与提交⽇志检查点进⾏配合，从⽽保证 D，也就是持久性。
当缓存到达⼀定阈值后，就不得不将有些旧的值从缓存中移除。这个时候就需要缓存淘汰算法来帮忙释放空间。这⾥有 FIFO、LRU、表盘（Clock）和 LFU 等算法，
最后存在部分数据我们希望它们⼀直在缓存中，且不受淘汰算法的影响，这时候我们可以把它们“锁”（Pinned）在缓存⾥。⽐如 B 树的⾼节点，它们⼀般数据量不⼤，且每次查询都需要访问。还有⼀些经常访问的元数据也会长期保存在缓存中。
2.2 ⽇志管理器
其次是⽇志管理器，它保存了⼀组数据的历史操作记录。缓存内的数据没有刷⼊磁盘前，系统就崩溃了，通过回放⽇志，缓存中的数据可以恢复出来。另外，在回滚场景，这些⽇志可以将修改前的数据恢复出来。
2.3 锁管理器
risky
最后要介绍的就是⾮常重要的锁管理器，它保证了事务访问共享资源时不会打破这些资源的完整性约
束。同时，它也可以保证事务可以串⾏执⾏。关于锁的内容我会在后⾯详细说明。
三、数据库如何恢复事务
数据库系统是由⼀系列硬件和软件组成的复杂⽣态系统，其中每个组件都有产⽣各种稳定性问题的可能，且将它们组合为数据库系统后，这种可能被进⼀步放⼤了。⽽数据库的设计者必须为这种潜在的稳定性问题给出⾃⼰的解决⽅案，并使数据库作出某种“承诺”。
提交⽇志，即 CommitLog 或 WAL（Write-Ahead Log）就是应对此种问题的有效⼿段。这种⽇志记录了数据库的所有操作，并使⽤追加（Append）模式记录在磁盘的⽇志⽂件中。
上⽂中我们知道数据库的写操作⾸先是写⼊了缓存，⽽后再刷⼊磁盘中。但是在刷盘之前，其实这些数据已经以⽇志的形式保存在了磁盘的提交⽇志⾥⾯。当数据没有刷⼊磁盘⽽仅仅驻留在缓存时，这些⽇志可以保证数据的持久性。也就是，⼀旦数据库遭遇故障，可以从⽇志中恢复出来数据。
3.1 提交⽇志的特性
⾸先，提交⽇志⾮常类似于上⼀讲介绍的 LSM 树的磁盘⽂件特性，都是顺序写⼊且不可变。其益处也是相同的，顺序写保障了写⼊的⾼性能，不可变保证了读取可以安全地从前到后读取⾥⾯的数据。
提交⽇志⼀般都会被分配⼀个序列号作为唯⼀键，这个序号不是⼀个⾃增数字，就是⼀个时间戳。此外，每条⽇志都⾮常⼩，有些数据库会将它们进⾏缓存⽽后批量写⼊磁盘。这就导致，默写情况下⽇志不能完全恢复数据库，这是对于性能的考虑，⼤部分数据库会给出不同的参数来描述⽇志缓存刷盘的⾏为，⽤户可在性能与恢复数据完整性上作出平衡。
⽽事务在提交的时候，⼀定要保证其⽇志已经写⼊提交⽇志中。也就是事务内容完全写⼊⽇志是事务完成的⼀个⾮常重要的标志。
⽇志在理论上可以⽆限增长，但实际上没有意义。因为⼀旦数据从缓存中被刷⼊磁盘，该操作之前的⽇志就没有意义了，此时⽇志就可以被截断（Trim），从⽽释放空间。⽽这个被截断的点，我们⼀般称为检查点。检查点之前的页缓存中的脏页需要被完全刷⼊磁盘中。
⽇志在实现的时候，⼀般是由⼀组⽂件组成。⽇志在⽂件中顺序循环写⼊，如果⼀个⽂件中的数据都是检查点之前的旧数据，那么新⽇志就可以覆盖它们，从⽽避免新建⽂件的问题。同时，将不同⽂件放⼊不同磁盘，以提⾼⽇志系统的可⽤性。
couchdb3.2 物理⽇志 Redo Log 与逻辑⽇志 Undo Log
事务对数据的修改其实是⼀种状态的改变，⽐如将 3 改为 5。这⾥我们将 3 称为前镜像（before-image），⽽ 5 称为后镜像（after-image）。我们可以得到如下公式：
1. 前镜像+redo log=后镜像
2. 后镜像+undo log=前镜像
redo log 存储了页⾯和数据变化的所有历史记录，我们称它为物理⽇志。⽽ undo log 需要⼀个原始状态，同时包含相对这个状态的操作，所以⼜被称为逻辑⽇志。我们使⽤ redo 和 undo 就可以将数据向前或向后进⾏转换，这其实就是事务操作算法的基础。
3.3 Steal 与 Force 策略
redo 和 undo 有两种写⼊策略：steal 和 force。
卡内基梅隆大学排名
steal 策略是说允许将事务中未提交的缓存数据写⼊数据库，⽽ no-steal 则是不能。可以看到如果是 steal 模式，说明数据从后镜像转变为前镜像了，这就需要 undo log 配合，将被覆盖的数据写⼊ undo log，以备事务回滚的时候恢复数据，从⽽可以恢复到前镜像状态。
force 策略是说事务提交的时候，需要将所有操作进⾏刷盘，⽽ no-force 则不需要。可以看到如果是 no-force，数据在磁盘上还是前镜像状态。这就需要 redo log 来配合，以备在系统出现故障后，从 redo log ⾥⾯恢复缓存中的数据，从⽽能转变为后镜像状态。
短裙用英语怎么说从上可知，当代数据库存储引擎⼤部分都有 undo log 和 redo log，那么它们就是 steal/no-force 策略的数据库。
3.4 ARIES 数据恢复算法
这个算法全称为 Algorithm for Recovery and Isolation Exploiting Semantics。
该算法同时使⽤ undo log 和 redo log 来完成数据库故障崩溃后的恢复⼯作，其处理流程分为如下三个步骤。
1. ⾸先数据库重新启动后，进⼊分析模式。检查崩溃时数据库的脏页情况，⽤来识别需要从 redo 的什么位置开始恢复数据。同时搜集
undo 的信息去回滚未完成的事务。
2. 进⼊执⾏ redo 的阶段。该过程通过 redo log 的回放，将在页缓存中但是没有持久化到磁盘的数据恢复出来。这⾥注意，除了恢复了
已提交的数据，⼀部分未提交的数据也恢复出来了。
3. 进⼊执⾏ undo 的阶段。这个阶段会回滚所有在上⼀阶段被恢复的未提交事务。为了防⽌该阶段执⾏时数据库再次崩溃，存储引擎会
记录下已执⾏的 undo 操作，防⽌它们重复被执⾏。
ARIES 算法虽然被提出多年，但其概念和执⾏过程依然在现代存储引擎中扮演着重要作⽤。
以上我们讲解了数据库如何恢复数据，保持⼀致性状态。它对应着 AID（C 如前⽂所⽰，是⼀种约束，⼀般不认为是数据库提供的功能）中的 AD。同时我们也要知道以提交⽇志为代表的数据库恢复技术，在没有事务概念的数据库中也扮演着重要的作⽤，因为页缓存是⽆处不在的，解决主存掉电丢失数据的问题，是提交⽇志的主要功能。
四、隔离级别
数据库最强的隔离级别是序列化，它保证从事务的⾓度看⾃⼰是独占了所有资源的。但序列化性能较差，因此我们引⼊了多种隔离界别来提⾼性能。在本讲的最后我会介绍分布式数据库中常⽤的并发控制⼿段，它们是实现隔离级别的有效⽅案，其中以多版本⽅式实现快照隔离最为常见。
序列化的概念与事务调度（Schedule）密切相关。⼀个调度包含该事务的全部操作。我们可以⽤ CPU 调度理论来类⽐，当⼀个事务被调度后，它可以访问数据库系统的全部资源，同时会假设没有其
他事务去影响数据库的状态。这就类似于⼀个进程被 CPU 调度，从⽽独占该CPU 资源（这⾥的 CPU 指的是时分系统）。但是实际设计调度时，会允许调度事务内部的操作被重新排序，使它们可以并⾏执⾏。这些都是优化操作，但只要不违反 ACID 的原则和结果的正确性就可以了。
那什么是序列化呢？如果⼀个调度被说成是序列化的，指的是它与其他调度之间的关系：在该调度执⾏时没有其他被调度的事务并⾏执⾏。也就是说，调度是⼀个接着⼀个顺序执⾏的，前⼀个调度成功完成后，另⼀个调度再执⾏。这种⽅法的⼀个好处是执⾏结果⽐较好预测。但是，我们发现这种做法有明显的缺陷：性能太低。在实现时，⼀个序列化调度可能会并⾏执⾏多个事务操作，但是会保证这样与⼀个个顺序执⾏调度有相同的结果。
以上就是序列化的概念，它揭⽰了序列化也会存在并发执⾏的情况。这⼀点很重要，在隔离理论中，⼀个隔离概念只是描述了⼀种⾏为，⽽在实现层⾯可以有多种选择，只要保证这个⾏为的结果符合必要条件就没有问题了。
序列化是最强的事务隔离级别，它是⾮常完美的隔离状态，可以让并⾏运⾏的事务感知不到对⽅的存在，从⽽安⼼地进⾏⾃⼰的操作。但在实现数据库事务时，序列化存在实现难度⼤、性能差等问题。故数据库理论家提出了隔离级别的概念，⽤来进⾏不同程度的妥协。在详解隔离级别之前，来看看我们到底可以“妥协”什么。
这些“妥协”被称为读写异常（Anomalies）。读异常是⼤家⽐较熟悉的，有“脏读”“不可重读”和“幻读”。写异常不太为⼤家所知，分别是“丢失更新”“脏写”和“写偏序”。读异常和写异常是分别站在使⽤者和数据本⾝这两个⾓度去观察隔离性的，我们将成对介绍它们。传统上隔离级别是从读异常⾓度描述的，但是最近⼏年，⼀些论⽂也从写异常⾓度出发，希望你能明⽩两种表述⽅式之间是有联系的。下表就是经典隔离级别与读异常的关系。
从中可以看到序列化是不允许任何读写异常存在的。
可重读允许幻读的产⽣。幻读是事务⾥⾯读取⼀组数据后，再次读取这组数据会发现它们可能已经被
修改了。幻读对应的写异常是写偏序。写偏序从写⼊⾓度发现，事务内读取⼀批数据进⾏修改，由于幻读的存在，造成最终修改的结果从整体上看违背了数据⼀致性约束。
读到已提交在可重读基础上放弃了不可重读。与幻读类似，但不可重读针对的是⼀条数据。也就是只读取⼀条数据，⽽后在同⼀个事务内，再读取它数据就变化了。
刚接触这个概念的同学可能会感觉匪夷所思，两者只相差⼀个数据量，就出现了两个隔离级别。这背后的原因是保证⼀条数据的难度要远远低于多条，也就是划分这两个级别，主要的考虑是背后的原理问题。⽽这个原理⼜牵扯出了性能与代价的问题。因此就像我在本专栏中反复阐述的⼀样，⼀些理论概念有其背后深刻的思考，你需要理解背后原理才能明⽩其中的奥义。不过不⽤担⼼，后⾯我会详细阐述它们之间实现的差别。
⽽不可重读对应的是丢失更新，与写偏序类似，丢失更新是多个事务操作⼀条数据造成的。
jimmy eat world最低的隔离级别就是读到未提交，它允许脏读的产⽣。脏读⽐较简单，它描述了事务可以读到其他事务为提交的数据，我们可以理解为完全没有隔离性。⽽脏读本⾝也会造成写异常：脏写。脏写就是由于读到未提交的数据⽽造成的写异常。
以上，我们详细阐述了经典的隔离级别。但是这套理论是⾮常古早的，较新的 MVCC 多版本技术所带
来的快照隔离⼜为传统隔离级别增添⼀个灵活选型。它可以被理解为可重读隔离级别，也就是不允许不可重读。但是在可重读隔离下，是可以保证读取不到数据被修改的。但快照隔离的⾏为是：⼀旦读到曾经读过的数据被修改，将⽴即终⽌当前事务，也就是进⾏回滚操作。在多并发事务下，也就是只有⼀个会成功。你可以细细品味两者的差异。
快照隔离可以解决丢失更新的问题，因为针对同⼀条数据可以做快照检测，从⽽发现数据被修改，但是不能防⽌写偏序的问题。
快照隔离是现代分布式数据库存储引擎最常使⽤的隔离级别，⽽解决写偏序问题，也是存储引擎在该隔离级别下需要解决的问题。
SSI（Serializable Snaphost Isoltion）正是解决这个问题的⽅案，
五、并发控制hit的过去式
figure out
⽬前存储引擎引⼊多种并发模型来实现上⾯提到的隔离级别，不同的模式对实现不同的级别是有偏好的，虽然理论上每种控制模型都可以实现所有级别。下⾯我就从乐观与悲观、多版本、基于锁的控制三个⽅⾯进⾏介绍。
5.1 乐观与悲观
乐观与悲观的概念类似于并发编程中的乐观锁与悲观锁。但是这⾥你要注意，实现它们并不⼀定要借助锁管理。
乐观控制使⽤的场景是并⾏事务不太多的情况，也就是只需要很少的时间来解决冲突。那么在这种情况下，就可以使⽤⼀些冲突解决⼿段来实现隔离级别。最常⽤的⽅案是进⾏提交前冲突检查。
冲突检查有多种实现模式，⽐如最常⽤的多版本模式。⽽另⼀种古⽼的模式需要检查并⾏事务直接操作的数据，也就是观察它们操作的数据是否有重合。由于其性能⾮常差，已经很少出现在现代存储引擎中了。这⾥需要你注意的是，乐观控制不⼀定就是多版本这⼀种实现，还有
其他更多的选择。
同样的，悲观控制也不仅仅只有锁这⼀种⽅案。⼀种可能的⽆锁实现是⾸先设置两个全局时间戳，最⼤读取时间与最⼤写⼊时间。如果⼀个读取操作发⽣的时间⼩于最⼤写⼊时间，那么该操作所在的事务被认为应该终⽌，因为读到的很可能是旧数据。⽽⼀个写操作如果⼩于最⼤读取时间，也被认为是异常操作，因为刚刚已经有读取操作发⽣了，当前事务就不能去修改数据了。⽽这两个值是随着写⼊和读取操作⽽更新的。这个悲观控制被称为 Thomas Write Rule，对此有兴趣的话你可以⾃⾏搜索学习。
5.2 多版本
多版本并发控制（MVCC，Multiversion concurrency control）是⼀种实现乐观控制的经典模式。它将每⾏数据设置⼀个版本号，且使⽤⼀个单调递增的版本号⽣成器来产⽣这些版本号，从⽽保证每条记录的版本号是唯⼀的。同时给每个事物分为⼀个 ID 或时间戳，从⽽保证读取操作可以读到事务提交之前的旧值。
MVCC 需要区分提交版本与未提交版本。最近⼀次提交的版本被认为是当前版本，从⽽可以被所有事务读取出来。⽽根据隔离级别的不同，读取操作能或者不能读取到未提交的版本。
使⽤ MVCC 最经典的⽤法是实现快照隔离。事务开始的时候，记录当前时间，⽽后该事务内所有的读取操作只能读到当前提交版本⼩于事务开始时间的数据，⽽未提交的数据和提交版本⼤于事务开始时间点的数据是不能读取出来的。如果事务读取的数据已经被其他事务修改，那么该数据应该在上⼀讲提到的 undo log 中，当前事务还是能够读取到这份数据的。故 undo log 的数据不能在事务提交的时候就清除掉，因为很可能有另外的事务正在读取它。
⽽当事务提交的时候，数据其实已经写⼊完成。只需要将版本状态从未提交版本改为提交版本即可。所以 MVCC 中的提交操作是⾮常快的，这点会对分布式事务有很多启⽰。李钟硕承认整容
⽽上⽂提到的 SSI 模式可以在 MVCC 的基础上引⼊冲突解决机制，从⽽解决写偏序问题。当提交发⽣的时候，事务会检测其修改和读取的数据在提交之前是否已经被其他已提交事务修改了，如果是，
则会终⽌当前事务，并进⾏回滚。同时这个冲突检测时机会有两个：⼀个是在事务内进⾏读取操作时就进⾏检测，称为前向检测（forward）。⽽相对的，在提交时进⾏检测被称为后向检测（backward）。你会明显感觉到，前者会快速失败，但是性能较低；⽽后者对异常的反应较慢，但速度会有优势。
5.3 基于锁的控制
基于锁的控制是典型的悲观控制。它会使⽤显⽰的锁来控制共享资源，⽽不是通过调度⼿段来实现。锁控制可以很容易实现“序列化操作”，但是它同时存在锁竞争和难扩展等问题。
nasty
⼀个⽐较知名的锁技术是两阶段锁（2PL），它将锁操作总结为两个阶段。
1. 锁膨胀阶段。在该过程中，事务逐步获得所有它需要的锁，同时不释放任何锁。这期间事务可以对加锁的数据进⾏操作。
2. 锁收缩阶段。该过程中，在上⼀过程中获得的锁全部被释放。这个事务是逐步的，这期间事务依然可以对还持有锁的数据进⾏操作。
以上过程简单明了，它是针对⼀次性加锁提出来的，⼀次性加锁的缺点是没有并发度，性能低；⽽两阶段锁可以保证⼀定的并发度，但其缺点是会有死锁的产⽣。
死锁是两个事务互相持有对⽅的锁，从⽽造成它们都⽆法继续运⾏。解决死锁需要引⼊超时机制，但超时机制⼜有明显的性能缺憾。此时，⼈们会引⼊死锁检测机制来尽早发现死锁。⼀般实现⼿段是将所有事务的锁依赖构建成⼀棵依赖图，⽽后使⽤图算法来发现其中的环形死锁结构，从⽽快速判断死锁的产⽣。
⽽与锁相对的⼀个概念就是“闩”（latch，读“shuān”）。⼀般资料说闩是轻量的，锁是重量的，这其实体现在两个⽅⾯。
⼀是说它们处理的对象。闩⼀般⽤在粒度很⼩的数据中，⽐如数据块、索引树的节点等。⽽锁⼀般作⽤在⼤颗粒操作，如锁定多⾏数据、事务和修改存储结构等。
⼆是它们本⾝的实现不同。闩⼀般使⽤ CAS 执⾏，是基于⽐较⽽后设置的⽆锁指令级别的操作。如果原始值发⽣变化就重新进⾏以上操作，这个过程叫⾃旋（spin）。⽽锁是使⽤独⽴的资源，且有锁管理器来控制。可想⽽知，调度锁也是⼀个⽐较耗时且复杂的过程。
这⾥就要解释上⽂中隔离级别“序列化”和“可重读”之间实现的差异了。“序列化”由于要保证⼀组数据重复读取的⼀致性，就需要引⼊重量级的锁，其代价是很⾼的；⽽“可重读”只需要保证⼀⾏数据重复读取是⼀致的，它可以使⽤轻量级的闩来实现。故隔离级别将它们分成两种是⾮常合理的，因为从原理看，它们是完全不同的。
qs世界大学排名2020博⽂参考
