本文试图讨论这些问题：MySQL的redolog和binlog为什么要用XA？MongoDB的oplog是按照什么顺序复制的？Raft真的只能串行申请吗？数据库复制和事务是完全独立的两个不同的东西？为什么MySQL不早点做一个Raft插件，直接用Raft实现高可用呢？本文旨在说明Fault-TolerantTransaction的几种实现方式。虽然乍一看可能都是Raft+KVEngine+ConcurrencyControl，容易被认为是同一类方法，但实际上它们有很大的不同，在讨论中不应忽略它们之间的差异。1.基本概念中讨论的Fault-Tolerance是指通过网络进行通信的多个计算机节点。在部分节点StopFailure的情况下，仍然尽量保证可用性；具体的Fault-Tolerance方法不讨论，默认读者对Raft等算法有基本的了解；具体的ConcurrencyControl方法不展开讨论，默认读者基本了解；会涉及到Spanner、TiKV、MongoDB等具体的数据库。1、基于RSM的Fault-TolerantKVReplicatedStateMachine应该是在《Implementingfault-tolerantservicesusingthestatemachineapproach》中最先提出的。是一种非常简单实用的实现容错的方法。其核心思想是：多个状态机的初始状态相同，以相同的顺序执行相同的命令序列，那么它们的最终状态也相同。由于状态是相同的，任何一个状态机宕机都可以被另一个状态机替换，因此实现了FaultTolerant。这里提到了几个概念，例如命令、执行顺序和状态机。它们都是抽象的概念，只有对应到具体的应用场景才有实际意义。在KVEngine场景下，命令是Put/Get等操作，状态机是KVEngine本身，执行顺序由ReplicationLog决定。既然提到了RSM和KV，那么基于RSM的KV也就指日可待了。先用Raft把发给KVEngine的操作复制过来，在Apply的时候丢回给KVEngine执行，这样就得到了一个Fault-Tolerant的KVEngine。看起来很简单，但我在这里显然忽略了很多细节：SerialorparallelApply：Raft被诟病串行Commit和serialApply，但这不是Raft的错；两个日志：Raftcopy需要一个Log，KVEngine也会有一个WAL，会带来IO放大。可以合二为一吗？Checkpoint：为了加快Recovery，需要checkpoint；只读操作是否需要复制？命令是否可以是复合操作：单行可以使用CAS操作吗？多行事务操作可以作为命令使用吗？2.基于RSM的事务我们再考虑最后一个问题，RSM中的命令可以直接作为事务吗？既然Raft是一个串行的Apply，那么把事务的所有操作作为一个命令丢给状态机执行似乎没有问题。但问题是实际事务是交互的，即包含if-else等逻辑，而且该逻辑还可能依赖于数据库系统之外的状态，所以不能简单地使用WriteBatch+Snapshot来实现一个事务.还是有ConcurrencyControl的逻辑。为了解决并发控制的问题，我们在RaftLeader上实现了一个LockTable和TransactionManager。以S2PL方式为例：读数据前加读锁，写数据前加写锁；读操作通过Raft读取数据，写操作缓冲区在本地；当用户决定提交事务时，可以释放读锁；通过Raft写一个事务，日志包含所有的写操作；当RaftApplytransactionlog时，将写操作应用到KVEngine并释放写锁。这里举的例子是S2PL，但是对于其他的并发控制方式基本是通用的。比如SnapshotIsolation，事务开始时获取KVSnapshot，所有读操作使用Snapshot，写操作获取写锁，数据buffer在本地。事务提交时，检查[begin,end]之间是否存在写冲突，如果没有，则使用Raft写入事务日志，Apply事务日志后，将写操作应用到KVEngine，最后释放写锁.这种方式接近于Spanner的做法，有几个特点：只需要Leader维护LockTable和TransactionManager，事务并发控制基本在Leader节点上完成；从RSM的角度来看，这里的LockTable起到了命令排序的作用，作用是保证所有的StateMachines按照相同的顺序执行命令；加锁操作不遵循复制协议，应用复制协议后解锁操作完成，从复制开始到Commit会一直持有锁：即复制协议Commit是该复制协议的Commit交易。如果Failover发生在Commit之前，事务将被中止；Raft复制的是事务的REDO。3.基于共享存储的事务再看上面的模型，复制协议做的事情很简单，与其他模块的耦合度也很小。它只维护一个有序的Log，所以我们可以把它从share-nothing扩展到share-storage模型。也就是说，如果我们把普通的单机事务引擎放在一个高可用存储上，就可以得到一个基本可用的Fault-Tolerant事务引擎，甚至不需要实现复制协议。但事情显然没有那么简单：如何实现只读节点，并提供读取和扩展的能力；如何在计算节点上更快地进行故障转移；如何将更多操作下推到存储节点。4、基于高可用KV的事务回到最开始的第一种方案。KV、Raft、LockTable、TransactionManager在一个节点上实现。看来耦合度还是比较大的。我们可以分层吗？如何进一步简化？比如Google的经典做法是基于GFS实现Bigtable，基于Bigtable实现Percolator。分层设计易于迭代，易于开发，易于调试。因此，我们可以考虑单独提取KV层，基于KV实现LockTable和TxnManager：TxnManager:Modifyfromthetransaction从所有Keys中选择一个PrimaryKey来记录交易状态，因此KV进一步变为Key=>{Value,Lock,TxnStatus}；MVCC：即使我们不甘心SingleVersion，我们还是想用MultiVersion并发控制，那么KV就变成了{Key,Version}=>{Value,Lock,TxnStatus}。看过Percolator和TiKV设计的应该不会陌生。它们基于一个高可用的KV，将交易的状态下沉到KV中。这种设计可以很容易地扩展到分布式事务场景。如果KV可以伸缩，那么上层交易也可以伸缩。5、基于单机事务引擎实现高可用事务以上方案看似比较简单，但是有一个细节不容忽视：锁基本上是在复制协议提交后释放的，换句话说，锁事务持有的会从事务中释放出来，从开始到多个节点写完日志，都会经历多次网络延迟，IO延迟，在拥塞情况下面临排队延迟的风险。锁意味着互斥，互斥意味着降低交易吞吐量。翻译：对于并发和冲突的事务，提交顺序由LockTable决定，与复制协议的Log顺序一致；交易的SerializationOrder与RSM中的Order一致。但是，这里有个问题：复制协议提交后一定要释放锁吗？提前发布会不会破坏秩序的一致性？RSM的Order一定要和交易的SerializationOrder一致吗？先不回答，我们来看****基于单机事务引擎高可用事务的解决方案。在正常的单机事务处理过程中，增加一个复制环节：本地事务提交后，不会立即返回给用户，而是写入binlog，等待binlog复制到其他节点后再返回用户。这种方式的事务延迟好像是本地事务的延迟，加上复制日志的延迟；但是和之前的方案相比，本地事务可以先提交，锁可以提交再释放，整体的事务吞吐量会比较低。改善。看起来比之前的方案还要简单，事务和复制模块完全分离，但是这里忽略了一个复杂的问题：复制用哪个日志，基于数据库的Journal，还是写一个binlog？基于什么Replication按顺序执行。如果是基于Journalreplication，可以使用Journalorder。如果是基于binlog，顺序是什么？如果有两条日志，两条日志其实就是说TransactionSerializationOrder和RSM的StateMachineOrder不一样吧？产生事务并发异常，或者导致状态机不一致？由于直接复制Journal会造成一系列复杂的耦合问题，所以大部分数据库选择单独写一个binlog/oplog来实现复制，但是在实现的时候可以优化一下，因为如果真的写两个日志会有原子性问题（一个是成功的）写的和另一个没有）和IO放大的问题。这里的设计空间比较大，就不详细讨论了，只考虑简化模型下的复制顺序问题。对于并发执行的事务，为了确定复制顺序，这里维护了一个自增ID，叫做OpTime。后续复制会按照OpTime的顺序，OpTime小的先复制。如果只在事务的开始和结束之间分配OpTime，就会出现问题：冲突并发的事务T1先提交，OpTime较大，意味着它们会被复制到后面；Commit之后的事务T2会先复制Commit，先commit的事务T1可能会因为复制失败而回滚；对于事务，这种场景出现的异常类似于Read-Uncommitted，事务T2读取了未提交的数据。所以OpTime的分配需要有更强的限制：对于并发和冲突的事务，OpTime的顺序应该和事务的SerializationOrder一致：在S2PL场景下，我们可以在Lock之后，Commit之前分配OpTime满足这个要求。因为按照S2PL调度，事务的Commit-Point在Lock完成和Unlock之间。与上面的例子相比，如果将事务T2的OpTime推迟到T1之后，复制的顺序会随之改变，不会出现之前的异常。对其他并发控制方法的扩展也是类似的，比如上面的SnapshotIsolation。提交前会检查[begin,end]是否有冲突，有冲突直接重启事务。相当于在[begin,end]区间内分配OpTime。该方法通过OpTime保存了TransactionSerializationOrder和RSM的Order的关系：并发冲突事务，OpTime的顺序与事务SerializationOrder相同；并发但不冲突的事务，OpTime的顺序是不确定的，因为谁先提交不会影响正确性；存在关系之前的事务，并且OpTime也必须满足此优先关系。但是这里留给读者思考的问题是：如何根据OpTime进行复制，因为在事务Abort的情况下，OpTime不能持续增加，只能单调增加。2.比较第一个其实是Spanner，第二个是TiKV和Percolator，第三个是MySQL和MongoDB。它们在复制上的区别：第一种方案，事务的redo被复制，事务提交的顺序由RaftLog的顺序决定。Failover等机制完全基于RSM模型；方案二中，Raft只是复制KV，事务的顺序与RaftLog的顺序无关，KV层的Failover完全独立于事务的恢复；第三种方案不同于传统的RSM模型，因为它实际上是先apply，然后Replication，Commit，可以实现并发Apply。从复杂度来看：第二种最简单明了，从Raft，到RaftKV，再到TransactionalKV，层次感好；第二个是第一个，Leader节点会额外实现LockTable，TransactionManager，这个和Raft是紧密结合的，但是事务提交的顺序是RaftLog的提交顺序，不会造成混淆；最复杂的是第三个。由于事务提交的顺序与Optime的顺序不一致，复制、读写等各个过程都会受到影响。影响，看似简单实则耦合。从事务并发的角度来看：第三种方案肯定可以支持并发，而且锁持有时间更短，只写一次本地日志；***第二种方案持有锁的时间比较长，***在Apply的时候理论上是可以实现并发的，如果没有其他的约束的话。从读写开销来看：一是ReplicationLog和EngineLog可以合并，每个事务只需要复制一次RaftLog；second是第二种，一般是把binlog和存储引擎的journal分开，需要写两遍；但是oplog是可以写入存储引擎的，可以一次IO提交（MongoDB的方式）；***是第二种方法，给KV加了更多的数据，放大了更多。然而，这只是理论上的分析。实际的复杂性和性能在很大程度上取决于实现而不是理论。3.总结如果我们从一个很粗略的层面来看，我们会认为这些系统只是几个技术点的组合，每个技术点看起来都很简单，然后我们认为交易系统无非就是这样.但实际上，交易系统绝不是简单的KV+Raft+SnapshotIsolation。它们的不同组合最终会创造出不同的系统。这篇文章留下了很多问题。RSM的Order通常被认为是全序，而Transaction的SerializationOrder是偏序（偏序关系由事务冲突定义）。如何统一它们？RSM的Checkpoint和TransactionCheckpoint的统一？RSM的Recovery和TransactionRecovery的关系？写入两个日志（journal和binlog）的系统的两个日志是什么关系？
