作者：童牧
绪论
在基于 Percolator 提交协定的分布式数据库被提出的期间，学术研究上还呈现了一种叫确定性数据库的技术，在这项技术的倒退过程中也呈现了各种流派。本文将解说学术上不同的确定性事务和特点，并综合说说他们的长处和面临的问题。
本文将依照提出的程序进行解说：
- 确定性数据库的定义；
- 可扩大的确定性数据库 Calvin；
- 基于依赖剖析的确定性数据库 BOHM & PWV；
- 器重实际的确定性数据库 Aria。
确定性数据库的定义
确定性数据库的确定性指的是执行后果的确定性，一言蔽之，给定一个事务输出汇合，数据库执行后能有惟一的后果。
图 1 – 不存在偏序关系时的不确定性
然而这一确定性是须要基于偏序关系的，偏序关系代表的是事务在数据库系统中执行的先后顺序。图 1 中，两个事务并发执行，然而还没有被确认偏序关系，那么这两个事务的执行先后顺序还没有被确定，因而这两个事务的执行程序也是自在的，而不同的执行程序则会带来不同的后果。
图 2 – 应用事务管理器为排序输出事务排序
图 1 中的例子阐明，为了达到确定性的后果，在事务执行前，咱们就须要对其进行排序，图 2 中退出了一个事务管理器，在事务被执行前，会从事务管理器之中申请一个 id，全局的事务执行能够看作是依照 id 程序进行的，图中 T2 读到了 T1 的写入后果，T3 读到了 T2 的写入后果，因而这三个事务必须依照 T1 -> T2 -> T3 的程序执行能力产生正确的后果。
图 3 – 死锁的产生
确定性数据库的另一个长处在于可能躲避死锁的产生，死锁的产生起因是交互式的事务有两头过程，图 3 是对产生过程的解释，T1 和 T2 各写入一个 Key，随后在 T1 尝试写入 T2 的 Key，T2 尝试写入 T1 的 Key 时就产生了死锁，须要 abort 其中的一个事务。构想一下如果事务的输出是残缺的，那么数据库在事务开始的时候就晓得事务会做哪些操作，在下面的例子中，也就可能在 T2 输出时晓得 T2 和 T1 会产生写依赖的关系，须要期待 T1 执行结束后再执行 T2，那么就不会在执行过程中才可能发现死锁的状况了。产生死锁时会 abort 哪个事务是没有要求的，因而在一些数据库中，这一点也可能产生不确定性的后果。
数据库系统中的不确定性还可能来源于多个方面，比方网络谬误、io 谬误等无奈意料的状况，这些状况往往会体现为某些事务执行失败，在对确定性数据库的解读中，咱们会探讨如果防止因这些不可意料的状况而产生不确定的后果。
确定性是一个束缚十分强的协定，一旦事务的先后顺序被确定，后果就被确定了，基于这一特点，确定性数据库可能 优化正本复制协定所带来的开销 。因为能保障写入胜利，在有些实现中还可能预测读的后果。然而确定性并不是银弹， 弱小的协定也有着其对应的代价，本文会在具体案例中详细分析其缺点，以及确定性数据库所面临的艰难。
可扩大的确定性数据库 Calvin
Calvin 提出于 2012 年，和 Spanner 呈现于同一期间，尝试利用确定性数据库的特点解决解决过后数据库的扩展性问题，这一研究成果后续演变成为了 FaunaDB，一个商业数据库。
图 4 – Calvin 的架构图
图 4 是 Calvin 数据库的架构图，尽管比较复杂，然而咱们次要须要解决的问题有两个：
- 在一个 replica 当中，是如何保障确定性的？
- 在 replica 之间，是如何保障一致性的？
首先看第一个问题，在一个 replica 中，节点是依照 partition 散布的，每个节点外部能够分为 sequencer，scheduler 和 storage 三个局部：
- Sequencer 负责正本复制，并在每 10ms 打包所收到的事务，发送到相应的 scheduler 之上；
- Scheduler 负责执行事务并且确保确定性的后果；
- Storage 是一个单机的存储数据库，只须要反对 KV 的 CRUD 接口即可。
图 5 – Calvin 执行过程一
咱们以一系列的事务输出来进行阐明，假如有三个 sequencer，他们都接管到了一些事务，每 10ms 将事务打包成 batch。然而在第一个 10ms 中，能够看到 sequencer1 中的 T1 与 sequencer3 中的 T10 产生了抵触，依据确定性协定的要求，这两个事务的执行程序须要是 T1 -> T10。这些事务 batch 会在被发送到 scheduler 之前通过 Paxos 算法进行复制，对于正本复制的问题咱们之后再说。
图 6 – Calvin 执行过程二
图 6 中，这些 batch 被发送到对应的 scheduler 之上，因为 T1 的 id 比 T10 更小，阐明它应该被更早的执行。Calvin 会在 scheduler 上进行锁的调配，一旦这个 batch 的锁调配完结了，持有锁的事务就能够执行，而在咱们的例子中，锁的调配可能有两种状况，T1 尝试获取被 T10 占有的 x 的锁并抢占，或是 T10 尝试获取被 T1 占有的锁并失败，不管哪种状况，都会是 T1 先执行而 T10 后执行的后果。
图 7 – Calvin 的不确定性问题
思考 Calvin 的执行过程，就会狐疑是否会产生图 7 这样的问题，如果 T1 在 T10 齐全执行之后才被发送到 scheduler 上，那 T1 和 T10 的执行程序还是会产生不确定性。为了解决这个问题，Calvin 有一个全局的 coordinator 角色，负责协调所有节点的工作阶段，在集群中有节点还未实现发送 batch 到 scheduler 的阶段时，所有节点不会进入下一阶段的执行。
在 SQL 层面，有些 predicate 语句的读写汇合在被执行前是没有被确定的，这种状况下 Calvin 无奈对事务进行剖析，比方 scheduler 不晓得要向哪些节点发送读写申请，也不晓得如何进行上锁。Calvin 通过 OLLP 的策略来解决这一问题，OLLP 下，Calvin 会在事务进入 sequencer 的阶段发送一个试探性读来确定读写汇合，如果这个事后读取到的读写汇合在执行过程中产生了变动，则事务必须被重启。
咱们思考 Calvin 的一个问题，如何在 replica 之间保障一致性。在确定性协定的下，只须要保障统一的输出，就能够在多个正本之间保障执行后果的统一。其中统一的输出包含了输出的程序。
图 8 – Calvin 的不一致性问题
图 8 形容了 Calvin 中的不一致性问题，如果 T2 先于 T1 被同步到一个正本中，并且被执行了，那么正本间的一致性就受到了毁坏。为了解决这个问题，所有的正本同步都须要在一个 Paxos 组之内进行以保障 全局的程序性，这可能成为一个瓶颈，然而 Calvin 宣称能达到每秒 500,000 个事务的同步效率。
综合来看，Calvin 和 Spanner 呈现于同一年代，Calvin 尝试通过确定性协定来实现可扩大的分布式数据库并且也获得了不错的成绩。本文认为 Calvin 中存在的问题有两点：
- 全局的共识算法可能成为瓶颈或者单点；
- 应用 Coordinator 来协调节点工作阶段会因为一个节点的问题影响全局。
基于依赖剖析的确定性数据库 BOHM & PWV
在开始说 BOHM 和 PWV 之前，咱们先来回顾以下依赖剖析。Adya 博士 通过依赖剖析（写后写、写后读和读后写）来定义事务间的先后关系 ，通过依赖图中是否呈现环来判断事务的执行是否毁坏隔离性。这一思路也能够反过来被数据库内核所应用， 只有在执行的过程中防止依赖图中的环，那么执行的过程就是满足当时给定的隔离级别的要求的，从这个思路登程，能够让本来无奈并发执行的事务并发执行。
例 1 – 无奈并行的并发事务
例 1 中给出了一个无奈并发执行的并发事务的例子，其中 T1 和 T3 都对 x 有写入，并且 T2 须要读取到 T1 写入的 x=1，在通常的数据库系统中，这三个事务须要依照 T1 -> T2 -> T3 的程序执行，升高了并发度。
图 9 – BOHM 的 MVCC
BOHM 通过对 MVCC 进行了肯定的革新来解决这个问题，设置了每条数据的有效期和指向上一个版本的指针，图中 T100 数据的有效期是 100 <= id < 200，而 T200 数据的有效期是 200 <= id。MVCC 为写抵触的事务并发提供了可能，加上确定性事务晓得事务的残缺状态，BOHM 实现了写事务的并发。
PWV 是在 BOHM 之上进行的读可见性优化，让写入事务可能更早的（在残缺提交之前）就被读取到，为了实现这一指标，PWV 对事务的可见性形式和 abort 起因进行了剖析。
事务的可见性有两种：
- 提交可见性（Committed write visibility），BOHM 应用的策略，提早高；
- 投机可见性（Speculative write visibility），存在连锁 abort 的危险。
图 10 – 连锁 abort
图 10 是投机可见性的连锁 abort 景象，T1 写入的 x 被 T2 读取到，T2 的写入进一步的被 T3 读取到，之后 T1 在 y 上的写入发现违反了束缚（value < 10），因而 T1 必须 abort。然而依据事务的原子性规定，T1 对 x 的写入也须要回滚，因而读取了 x 的 T2 须要跟着 abort，而读取到 T2 的 T3 也须要跟着 T2 被 abort。
在数据库系统中有两种 abort 的起因：
- 逻辑起因（Logic-induced abort），违反了束缚；
- 零碎起因（System-induced abort），产生了死锁、零碎谬误或写抵触等状况。
然而十分侥幸的，确定性数据库可能排除因零碎起因产生的 abort，那么只有确保逻辑起因的 abort 不产生，一个事务就肯定可能在确定性数据库中胜利提交。
图 11 – 利用 piece 宰割事务的实现
图 11 是 PWV 对事务的宰割，将事务宰割成以 piece 的小单元，而后寻找其中的 Commit Point，在 Commit Point 之后则没有可能产生逻辑起因 abort 的可能。图中 T2 须要读取 T1 的写入后果，只须要期待 T1 执行到 Commit Point 之后在进行读取，而不须要期待 T1 齐全执行胜利。
图 12 – PWV 的性能
通过对事务执行过程的进一步细分，PWV 升高了读操作的提早，相比于 BOHM 进一步晋升了并发度。图 12 中 RC 是 BOHM 不提前读取的策略，从性能测试后果可能看出 PWV 在高并发下有着十分高的收益。
BOHM 和 PWV 通过对事务间依赖的剖析来获取抵触场景下的高性能，然而这一做法须要晓得全局的事务信息，计算节点是一个无奈扩大的单点。
器重实际的确定性数据库 Aria
最初咱们来讲 Aria，Aria 认为现有的确定性数据库存在着诸多问题。Calvin 的实现具备扩展性，然而基于依赖剖析的 BOHM 和 PWV 在这方面的体现不好；而得益于依赖剖析，BOHM 和 PWV 在抵触场景下避免性能回退的体现较好，但 Calvin 在这一状况下的体现不现实。
在分布式系统中为了并发执行而进行依赖剖析是比拟艰难的，所以 Aria 应用了一个预约机制，残缺的执行过程是：
- 一个 sequence 层为事务调配全局递增的 id；
- 将输出的事务长久化；
- 执行事务，将 mutation 存在执行节点的内存中；
- 对持有这个 key 的节点进行 reservation；
- 在 commit 阶段进行冲突检测，是否容许 commit，没有发生冲突的事务则返回执行胜利；
- 异步的写入数据。
图 13 – Aria 的架构图
图 13 是 Aria 的架构图，每个节点负责存储一部分数据。Aria 的论文里并没有具体的规定复制协定在哪一层做，能够在 sequencer 层也能够在 storage 层实现，在 sequencer 层实现更能发挥优势确定性数据库的劣势，在 storage 层实现能简化 sequencer 层的逻辑。
图 14 – Aria 执行过程一
图 14 中，输出事务在通过 sequencer 层之后被调配了全局递增的事务 id，此时执行后果就曾经是确定性的了。通过 sequencer 层之后，事务被发送到 node 上，T1 和 T2 在 node1 上，T3 和 T4 在 node2 上。
图 15 – Aria 执行过程二
图 15 中，假如 T1 和 T2 在 node1 上被打包成了一个 batch，T3 和 T4 在 node2 上被打包成了一个 batch。在执行时，batch 中的事务执行后果会放在所属 node 的内存中，而后进行下一步。
图 16 – Aria 执行过程三
图 16 是 batch1 中的事务进行 reservation 的后果，须要留神的是执行事务的 node 不肯定是领有这个事务数据，但 reservation 的申请会发送到领有数据的 node 上，所以 node 肯定能晓得和本身所存储的 Key 相干的所有 reservation 信息。在 commit 阶段，会发现在 node1 上 T2 的读汇合与 T1 的写汇合抵触了，因而 T2 须要被 abort 并且放到下一个 batch 中进行执行。对于没有抵触的 T1，T3 和 T4，则会进入写入的阶段。因为在 sequencer 层曾经长久化了输出后果，所以 Aria 会先向客户端返回事务执行胜利并且异步进行写入。
图 17 – Aria 执行过程四
图 17 是 T2 被推延执行的后果，T2 退出到了 batch2 之中。然而在 batch2 中，T2 享有最高的执行优先级（在 batch 中的 id 最小），不会有限的因为抵触而被推延执行，而且这一策略是可能保障惟一后果的。
图 18 – Aria 的不确定性问题
那么容易想到的是 Aria 也可能会有如 Calvin 一样的不确定性问题。图 18 中，T1 和 T2 是存在抵触的，应该先执行 T1 在执行 T2，如果 T2 在 T1 尚未开始 reservation 之前就尝试提交，那么就不可能发现自己与 T1 存在抵触，执行程序变为了 T2->T1，毁坏了确定性的要求。为了解决这个问题，Aria 和 Calvin 一样存在 coordinator 的角色，利用 coordinator 来保障所有的节点处在雷同的阶段，图 18 中，在 T1 所在的 node1 实现 reservation 之前，node2 不可能进入 commit 阶段。
图 19 – Aria 的重排序
确定性数据库的劣势之一就是可能依据输出事务进行重排序，Aria 也思考了这一机制，首先 Aria 认为 WAR 依赖（写后读）是可能平安的并行的，进一步在 commit 阶段对 reservation 的后果进行冲突检测时，能够将读后写依赖转化为写后读依赖。在图 19 上方的图中，如果依照 T1 -> T2 -> T3 的程序执行，那么这三个事务须要串行执行。然而在通过重排后并行执行的后果中，T2 和 T3 的所读取到的值都是 batch 开始之前的，换言之，执行程序变为了 T3 -> T2 -> T1。而在图 19 的下方，即便将 RAW 依赖转化为了 WAR 依赖，因为依赖呈现了环，仍旧须要有一个事务被 abort。
相比于 Calvin，Aria 设计的长处在于执行和 reservation 的策略领有更高的并行度，并且不须要额定的 OLLP 策略进行试探性读，并且 Aria 可能提供一个后备策略，在高抵触的场景下开其一个额定的抵触事务处理阶段，本文不再详细描述，感兴趣的同学能够看 Luyi 老师在知乎上写的文章。
图 20 – Aria 的 barrier 限度
图 20 是 Aria 的 barrier 限度，具体表现为，如果一个 batch 中存在一个事务的执行过程很慢，例如大事务，那么这个事务会拖慢整个 batch，这是咱们相当不违心看到的，尤其是在大规模的分布式数据库中，很容易成为稳定性的毁坏因素。
总结
确定性是一个很强的协定，然而它须要全局的事务信息来实现，对上述的确定性数据库的总结如下。
基于依赖剖析的 BOHM 和 PWV：
- ↑ 充分利用 MVCC 的并发性能
- ↑ 可能避免抵触带来的性能回退
- ↓ 单节点扩大艰难，不适宜大规模数据库
分布式设计的 Calvin 和 Aria：
- ↑ 单版本，存储的数据简略
- ↓ 长事务、大事务可能拖慢整个集群
- ↓ barrier 机制须要 coordinator 进行实现，存在 overhead
- ↓ 如果一个节点呈现故障，整个集群都将进入期待状态
相比之下，基于 Percolator 提交协定的分布式数据库，只须要枯燥递增的时钟就可能实现分布式事务，对事务的解耦做的更加好。
图 21 – 共识算法档次的比照
共识算法的档次是确定性数据库一个很重要的性能晋升点，图 31 下方是咱们常常接触的在存储引擎层面进行共识算法的做法，尽管系统对下层而言变得简略了，然而存在着写放大的问题。确定性协定可能保障一样的输出失去惟一的输入，因而使得共识算法可能存在于 sequencer 层，如图 21 上方所示，极大晋升了一个正本外部的运行效率。
总结，确定性数据库目前次要面临的问题一是在 Calvin 和 Aria 中存在的 coordinator 角色对全局的影响，另一点是存储过程的应用形式不够敌对；而长处则在于确定性协定是一个两阶段提交的代替计划，并且可能应用单版本的数据来晋升性能。