Calvin：一个为分区数据库设计的快速分布式事务框架

之前一直听说过 Calvin，也知道有基于 Calvin 的分布式数据库 FaunaDB，但一直没太关注 Calvin 是如何实现的。最近刚好看到一篇文章，讨论了 Calvin vs Spanner，立刻就引起了我的兴趣。因为 TiKV 是基于 Google Spanner 来构建的，所以在很多方面，我们跟 Calvin 也有很强的对比性。当然，仅仅通过一篇 blog 是不够的，所以我还是决定先看看 Calvin 相关的论文，知道 Calvin 主要做了啥，才好跟 TiKV 对比。

Calvin 在设计的时候，并不是为了某一个独立的系统设计的。Calvin 提供了一个事务调度层和数据复制层，采用一个确定锁机制，来为不同的存储系统提供分布式事务支持。可以看出，Calvin 的愿景还是非常伟大的，这种可拔插，分层的设计我们 TiDB 这边也是非常推崇的。这也就更加深了我研究它的兴趣。

Traditional Distributed Transaction

对于很多传统的分布式数据库来说，通常会使用 Agreement Protocol （譬如通常的 two-phase commit）机制来实现分布式事务，但这个会有一些问题。

首先就是网络开销比较大，一次事务要经过多次网络交互。有时候这些开销可能比实际的事务执行时间还长。同时，为了保证事务的一致性，我们需要对访问的数据进行加锁处理，而这个锁通常只有在事务完成之后才会被释放。虽然我们能做很多优化，譬如将多个并发的请求作为一个 batch 减少网络开销，但这个仍然没有办法减少锁冲突开销。

另外，在分布式事务上面使用锁，也容易引起死锁问题，而处理因为死锁导致的事务终止或者重试，也会增大事务的延时和降低整个系统的吞吐。

Deterministic Database

Calvin 并没有采用通用的 2PC 实现，Calvin 的目标是尽量的减少分布式事务的开销，采用的方式很简单，当一个事务需要多个节点一起参与的时候，不同节点在获取锁和开始执行事务之前，就已经在外面确定好了如何执行这个事务。

Calvin 是一个 deterministic database，也就是说，对于需要处理的事务，Calvin 会在全局确定好事务的顺序，并按照这个顺序执行。这些事务的执行顺序，我们可以认为是一个全局的有序 log，并且 Calvin 会通过复制机制来备份到不同的副本上面。所有的副本都是可以并行的顺序执行这些 log 的。这样，即使一个副本当掉，另外副本也仍然能执行并且 commit 事务。

Calvin Architecture

在前面说到，Calvin 致力于提供的是一个通用的分布式事务解决方案，所以它可以适配非常多的 storage，只要这些底层的 storage 系统实现了通常的 CRUD 操作。也就是说，我们可以在单机上面使用 RocksDB，然后加上 Calvin，就可以对外提供一个支持分布式事务的数据库了。

Calvin 主要分为三层：

• Sequencing layer，也就是 sequencer，负责拦截事务并且将它们放到一个全局的事务序列里面。这个序列也就是事务执行的顺序。Sequencer 也同时会处理复制和日志。
• Scheduling layer，也就是 scheduler，它使用一种 deterministic locking scheme 的技术来编排事务的执行，在保证 sequencer 指定的顺序下，尽可能的允许多个事务并发的执行。
• Storage layer，最终的数据存储层，可拔插，能支持不同的 storage。

上面三层都是可以水平扩展的，Calvin 的整个架构如下:

对于 Calvin 来说，只要理解了 sequencer 和 scheduler 是如何设计的，那么其实就能理解 Calvin 是如何工作的了。

Sequencer

Sequencer 的主要作用就是接受客户端发过来的事务请求，然后将它们排序，记录到日志。因为这些事务是顺序排好序了，所以只要依次执行，就一定保证整个系统的事务一致性。最简单的做法当然就是用一个节点来处理，但大家知道这铁定不行，首先就是会有单点问题，另外就是随着数据量的膨胀，单个节点铁定承载不了。

Calvin 的 sequencer 是能独立水平扩展的，每个 sequencer 会使用一个 10ms 的 epoch 来批量收集一批 client 的请求， 将它们作为一个 batch，然后 sequencer 将这个 batch 持久化到 storage，并通过复制算法将其备份到其他的副本。 Sequencer 支持通常的 Master/Slave 异步复制，以及 Paxos 的复制。虽然异步复制性能好很多，不过为了保证数据安全，采用 Paxos 是一个更好的方案。

当一个 batch 被复制到足够的副本以后，这个 batch 对应的 GUID 会被存储到一个 Paxos 的 MetaLog 上面，为了更好的提高吞吐，Calvin 会将多个 GUID 作为 batch 存放到 MetaLog 里面。

也就是说，Calvin 在 sequencer 这层的处理其实就是将事务做 batch，通过 Paxos 将 batch 复制到不同的副本，然后在一个中心 Paxos 里面保存对应的 meta 信息。因为 MetaLog 里面保存的事务是顺序的，所以外面只需要读取 MetaLog，然后找到对应的事务数据，就能够顺序处理了。

如果真的如我上面这么猜测，Calvin 在 sequencer 这层其实还是有一个处理 MetaLog 瓶颈 Paxos。

当 transaction batch 复制成功之后，sequencer 就将这个 batch 发给所有的 scheduler，并带上 sequencer 的 Node ID，以及上面提到的 epoch number。

Scheduler

Calvin 通过 Sequencer 来保证事务的全局有序，如果完全顺序依次执行事务，一定可以保证事务的一致性，但这样性能会很慢。但如果并发执行，有可能会遇到不同事务操作相同数据的并发问题。

Calvin 在 Scheduler 这层使用了 deterministic lock scheme 机制保证事务能够被安全的并发执行。这个机制大概是这样的：

• 在所有的 scheduler 上面有一个总的 Lock manager
• 各个节点自己的 scheduler 只负责 lock 自己本地的数据
• 类似严格的 two phase locking，但加入了一些确定限制
• 所有的事务一定要拿到 lock 之后才能开始执行
• 所有在事务里面的 lock 顺序也是跟全局事务顺序一致的，也就是说，如果两个事务 A 和 B 需要独占一个 lock，A 事务在 B 事务的前面，那么 A 一定比 B 先拿到 lock
• 使用一个单独的线程来顺序处理 lock 请求
• Lock manager 必须按照全局事务顺序来授权 lock

按照这个机制，如果我没有猜错，Lock manager 应该也是一个单点。

当一个事务拿到所有的 lock 之后，scheduler 就要开始执行这个事务了，会做如下几个步骤处理：

1. Read/Write 分析，scheduler 会分析这次事务 read 和 write 需要处理的数据在哪里，那些在本地，那些在其他节点，其他节点的数据叫做 participant，对于需要 write 的节点，叫做 active participant，而对于 read 的节点，叫做 passive participant。
2. 执行 local read。
3. 执行 remote reads。scheduler 会将 read 请求发给其他 participants 去执行。
4. Collect remote read results
5. 执行事务，并且 apply local write，对于其他节点的 write，其他的 scheduler 会自己 apply。

小结

这里仅仅介绍了我对 Calvin 两个最重要的组件 Sequencer 和 Scheduler 理解，还有一些 dependent transaction 和 checkpoint 并没有说明。

按照我的理解，对于 Calvin 来说，它通过一个全局单点的 log 来保证事务的顺序性，同时有一个全局 lock manager 来保证事务执行的并发一致性，所以它对于冲突比较严重的分布式事务应该有很好的性能。但它毕竟存在几个逻辑上面的单点，所以到底能 scale out 到多少，以及最多能顶住多少的外部请求，我其实是存疑的。而且 Calvin 的源码实现比较简单，FaunaDB 又没有开源，所以我其实也并不清楚它如何实现的。

至于 Calvin vs Spanner 那边文章，因为已经有很多翻译了，这里就不在说明。后续看有没有时间写写 Calvin 跟 TiKV 这边对比的东西。