一致性协议

在主流的强一致容错的分布式实时存储系统中，一般有两种设计方案：

• Layered structure，以BigTable为代表。在这类系统中，数据库的逻辑和存储是由两个子系统分开处理的。在数据存储层，一般会提供一个类似文件系统接口分布式存储系统，该类系统会基于数据块提供一些比较弱的一致性语义(参见GFS)。上层的数据库逻辑再在此之上做封装做到数据容错。
• Non-layered structure。这类系统基本都遵循replicated-state-machine(RSM)的架构，用一致性协议算法把RedoLog复制到不同的机器并按照相同的顺序进行重放，Raft算法是对这类系统的一个经典描述。Pegasus采用的是non-layered structure，其中的一致性算法是PacificA。

下面简单的给出了一些PacificA和Raft的一些对比：

• 在PacificA中，一条记录只有备份到全部机器才能提交；而Raft是一个备份过半即可提交的算法。这种实现方式使得Raft能更好的平滑掉写延时的偶发性毛刺。但是在实际的业务中，我们的集群是单机房部署的，所以PacificA的表现也能令人满意。
• Raft可以容忍小于一半的副本不可用。PacificA只要有一个副本不宕机，写流程就不会阻塞住(在Pegasus中，配置的最小副本数仍旧是过半的)。
• 在Raft中，leader的选举是一个复杂的过程。而PacificA中，任何一个副本都可以替换掉原来不可用的leader。
• Raft对并发replication的支持不够友好。在一些实现(如Kudu)中，Raft被实现为stop-and-wait的模型，即上一批replication不收到回复，下一批replication的消息就不会发出；另一些实现(如etcd)中，replication可以用pipeline的方式进行，但如果底层的网络通道是无序的(如两个节点间有多个TCP连接)，pipeline的方式会造成比较大的带宽浪费。
• PacificA必须依赖第三方的中心节点来协助进行一致性的仲裁，而Raft不需要任何依赖。这也使得PacificA中的元数据必须依赖一个外部系统来做可靠存储。就实际来看，这类可依赖的系统是存在的：如Zookeeper, etcd。总的来看，我们认为PacificA在实现上足够简单，并且该一致性协议所带来的性能开销不会成为系统的上的瓶颈，因而我们最终选择了PacificA。

在PacificA的实现上，我们也结合实际对算法本身做了一些改进：

• PacificA要求写Primary完成后才能开始写Secondary。在我们的实现中这二者是并行执行的。
• PacificA对于一个分片(ReplicaGroup)的删除和召回并没有描述，我们为了实现表的软删除，实现了这一过程。
• PacificA对于ReplicaGroup的成员变更，以及Learner加入的流程均缺乏清楚的描述。我们在实现中对这些内容进行了补充。
• PacificA对于三副本全挂(我们称之为DDD)的情况没有进行说明，我们结合实际情况进行了处理。