复制状态机作为分布式系统的主要容错手段,典型地使用复制日志来实现。该方法维持一组服务器上的多个复制日志彼此相同,同时要求每个状态机按照顺序执行日志中的命令,由此保证每台服务器产出相同的状态,从而可以容忍少数服务器故障。复制状态机方法需要使用分布式共识协议保证多个复制日志能够就下一个日志条目达成共识,同时需要在故障和消息延迟情况下保证多个状态机对外的数据一致。共识协议作为复制状态机的核心组件,需要被简洁高效地实现。但诸如Paxos、ViewStamped Replication、Zab这些主流的共识协议,算法本身难以理解,工程实现上也需要进行额外扩展或性能优化,不便于构建实际系统。此外,基于复制状态机构建满足给定一致性模型的分布式服务,需要根据服务特性和应用场景进行特定设计,没有通用的解决方案。基于以上问题,本文的研究内容如下:(1)本文分析对比主流的共识协议,基于可理解性和易于工程实现的需求,选择Raft协议作为核心算法。但现有Raft协议实现,大多数为实验性质,在完整性上有所欠缺或在正确性上缺乏验证,少数可行实现都是作为大型服务的一部分,没有封装成一个通用的基础库形式。因此本文从零开始构建了一个简洁高效的Raft实现,其严格遵循Raft协议规范,细化完善协议中不够明确的隐式处理,能够保证本文实现在各种复杂故障场景下具备高度正确性和可靠性。针对在节点崩溃或网络分区故障下,Raft算法因不同节点日志冲突而较长时间无法达成一致的问题,本文提出了加速的日志回溯优化方案,使得排解上百条日志条目冲突所需的消息通信次数降低了 20%,并且能够避免消息数目随着日志冲突加剧而线性增长,使其维持在一个稳定范围内,使得落后的节点能够快速更新,保证了 Raft算法在这些场景下的运行效率和活性。(2)为了验证Raft实现在解决一致性问题上的有效性,本文选择形式简单易于实现的KeyValue服务作为一致性问题的研究对象,避免因服务类型复杂化而引入额外干扰。以Raft实现为基础,本文继续完善Raft模块与客户端的交互行为,构建出一个容错的分布式KeyValue服务。对比常用的一致性模型,以提供简单直观的数据特性为目标,本文选择线性一致性作为KeyValue服务的约束模型,通过对客户端请求执行重复检测与处理,确保同一个客户端请求仅被执行一次,从而保证系统符合线性一致性语义。实验部分引入分布式测试框架,通过模拟客户端并发请求、网络分区、消息传输延迟丢失乱序重复、服务器崩溃等各种故障场景,对Raft实现和KeyValue服务进行了充分的测试,服务的高可用性得到验证。采用开源的线性一致性验证模块Porcupine,检测KeyValue服务在消息被延迟丢弃、网络分区故障条件下并发客户端操作的历史记录,测试结果证明了 KeyValue服务具有线性一致性,同时也间接验证了 Raft实现的正确性和可靠性。