关于POLARDB 的数据存储部分的论文翻译还在继续，此为第五部分
——————————————————————————————
5 CONSISTENCY MODEL 一致性模型
A Revision of Raft 简化的raft
分布式存储系统需要一个一致性的协议，去保证所有的 commit 对数据的修改能在不同的情况下，不丢失数据。在设计之初，我们在深刻的考虑部署的复杂性等问题后，我们选择了 raft 协议，然而马上就出现了陷阱。
Raft 被设计为高度的序列化和容易理解的模式，他的日志是不允许同时在 leader 和 followers 中提交，这意味着日志的提交需要 follower的确认，同时需要被leader commit 并顺序性的应用到所有的节点，但如果在这个过程中，最后的队列的信息不能被提交，除非所有的信息都持久化在磁盘并进行回应，这将产生严重的延迟和吞吐量的问题。这里我们观测到，IO的深度从8 到32 会导致吞吐下降一半。
综上所述，RAFT 不适合用于多连接，并将日志在leader 和多个follower中进行数据的传输，当一个连接阻塞或变慢时，日志条目到达跟踪器的顺序会打乱。换句话说，队列前面的一些日志条目实际上比后面的要晚到达。但是Raft跟踪器必须按顺序接受日志条目，这意味着它不能发送一个确认通知leader后续的日志条目已经被记录到磁盘，直到前面那些丢失的日志条目到达。此外，当大多数追随者被某些丢失的日志条目阻塞时，leader会被卡住。在实际的情况中，使用多个连接在高并发环境中是一个常见的情况，我们需要重新对RAFT协议进行变化，以适应我们的应用。
在传统事务处理系统中如数据库系统中，并发算法允许在执行中交错和执行次序打乱中执行，并得到逻辑顺序性的结果。这些系统自然可以容忍由传统存储语义引起的无序I/O完成，并自行解决该问题，以确保数据一致性。实际上，MySQL和AliSQL等数据库并不关心底层存储的I/O序列。数据库的锁定系统将保证在任何时间点，只有一个线程可以在一个特定的页面上工作。当不同线程同时在不同的页面上工作时，数据库只需要成功执行I/O，它们的完成顺序无关紧要。因此，我们利用这一点，在PolarFS中放松Raft的一些约束，以开发一个更适合高I/O并发的共识协议。
本文提出了一种改进的一致性raft协议，名为 parallelraft 下面几节将介绍 parallelRaft 如何解决以上提到的一些问题，这个并行的parallelraft架构类似与raft ，同时也是通过复制log 来进行数据复制的。Leader将日志条目复制到follower，我们遵循与Raft相同的问题分解方法，并将ParallelRaft划分为更小的片段: 包括了 日志复制，leader 的选举 和 数据的追加。
5.2 OUT OF ORDER LOG REPLICATION
Raft 展现序列化有两个方面，1 在leader 发送整个日志给follower 的情况下，follower 需要去给相关的回馈，通知发送者他已经接受到日志和记录，以及那些日志已经被看到和保存了。2 当leader 确认日志广播给所有的 follower ,他也需要去确认整个过程和日志在所有的follower被确认和committed。并行的raft打破了这些这些限制和执行中的顺序，产生的乱序，因此，这里有一个基本的不同，在raft 和 parallelraft，在paralelraft当一个事件被确认，并不意味着其他的在他之前发生的事件都已经committed，这里这个协议保证的是
1 没有序列化的限制，所有committed的状态将于我们典型的一些传统的数据库不同
2 所有的committed在任何情况下都不会丢失。
parallelRaft 在无序日志的执行中的规则是：日志执行的过程中，如果日志之间无联系则可以进行乱序执行，如果日志执行中有顺序的问题，有冲突的日志部分将严格的按照他们到达的先后顺序来执行。这里新的数据版本，将不会先于老的数据版本被应用，parallelraft 能够很容易的获知事务之间的冲突问题，其中LBA 存储了整个日志中没有被应用的日志信息头，follower 会根据 ACK-COMMIT-APPLY的 parallelraft中指示的步骤来进行那些是需要进行一致性维护。
out of order acknowledge
follower 在接收到leader复制的日志后，Raft的 follower 不会确认它，直到所有之前的日志条目都被持久存储，这需要的等待时间，并且当有大量并发I/O写正在执行时，平均延迟显著增加。然而，在ParallelRaft中，一旦日志被成功写入，follower就可以立即committed它。这样就避免了额外的等待时间，从而优化了平均延迟。
out of order commit
raft leader 按串行顺序提交日志，在前面所有日志都提交之前，不能提交日志。而在ParallelRaft一个日志可以在大多数副本被确认后立即提交。对于存储系统来说，这种提交语义是可以接受的，但通常这样的方式在TP系统中是不被接受的。例如，NVMe不检查读或写命令的LBA，以确保并发命令之间的任何类型执行的顺序，也不保证这些命令的完成顺序。
Apply with Holes in the log
在RAFT 协议中，所有的日志的应用都遵循严格的顺序性，而在parallelRaft中是允许存在乱序的日志复制和commit的，那么日志如何能够安全的被应用，避免日志在应用的过程中丢失，对于parallelraft是一项挑战。
Parallelraft 中在每个日志中都引入了一个数据结构，被称为look behind buffer, 这个look behind buffer 包含了N个之前日志修改过的LBA 的修改信息，N的尺寸决定了parallelraft 中并行中可以乱序执行的日志的跨度，这里的缓冲存储的是 LBA 的信息，缓冲可以判断 parallelraft 在执行中的判断事务之间是否有冲突的问题，这样可以安全地应用与任何其他条目不冲突的日志，否则应该将它们添加到挂起列表中，并在检索到缺失的日志记录后进行恢复。根据我们使用RDMA网络的PolarFS的经验，N设置为2对于其I/O并发性已经足够好了。
基于上述乱序执行方法和规则，可以成功地实现数据库所需的存储语义。此外，通过消除ParallelRaft for PolarFS中不必要的串行限制，还可以缩短多副本并发写的延迟。
注明：LBA 为 逻辑块地址的简称
