基于Raft算法的分布式系统数据一致性研究

摘要

随着互联网的迅速发展，各类互联网应用软件层出不穷，相较于一些传统的应用软件，互联网应用软件有着庞大的用户基数，这使得任意单机系统都无法支撑起如此庞大的用户数量，为了解决该问题，人们开始选择将单个的应用以服务的形式进行拆分，然后将这些服务部署到多台机器上，每台机器运行的服务之间协调运作，一致对外提供服务，这样就构成了分布式系统。分布式系统的优势在于能够充分利用多台机器的算力来构建庞大而复杂的应用，在实现一个分布式系统时需要解决很多问题，其中一点就是如何保证不同节点间的数据一致性。　　Raft算法是由DiegoOngaro于2014年在其博士论文中首次提出的分布式共识算法，相较于当时正流行的Paxos共识算法，Raft共识算法更加易于理解和实现。但是Raft算法也有着其缺陷，首先它强调Leader节点的领导性，Leader节点的性能及稳定性一定程度上决定了集群的性能及稳定性，Raft算法在其Leader选举过程中采用的是一种随机超时加选举的方案，因此选举的结果存在不合理性。其次就是Raft算法的性能问题，Raft算法对于客户端请求采用的是串行化的处理方式，即同一时刻只能处理一条客户端请求，这种方式并不适合于多客户端的场景。　　针对上述Raft算法存在的问题，本文提出了一种基于节点优先级的Leader选举方案，并对该方案的活性、可靠性、及安全性进行了分析，同时对该方案工程实现的时序进行了说明。相较于原Raft算法的Leader选举方案，基于节点优先级的Leader选举方案能够在保证上述特性的基础上，根据集群中各节点间的优先级顺序，优先选举出集群中优先级最高且满足Leader选举安全性规则的节点成为Leader，选举的结果更加合理。然后针对Raft算法的性能问题，本文提出了一种多客户端场景下的并发写入方案，并围绕并发写入所带来的一系列问题制定了多条安全性规则，新提出的并发写入方案能够在保证算法安全性及活性的基础上显著提升Raft算法处理客户端写请求的性能。最后本文基于改进后的Raft算法设计并实现了一个高可用键值存储系统，基于该高可用键值存储系统设计了一系列的对比实验，通过对实验得到的结果数据进行分析，验证了本文提出的基于节点优先级的Leader选举方案和多客户端场景下的并发写入方案的可行性。

目录

声明

第一章 绪论

1.1研究背景与意义

1.2国内外研究现状

1.3课题研究主要内容

1.4内容及结构安排

第二章 Raft共识算法

2.1相关基本概念

2.1.1复制状态机模型

2.1.2对称与非对称共识算法

2.2 Leader 选举

2.2.1节点状态

2.2.2选举流程

2.3日志复制

2.3.1日志结构

2.3.2复制流程

2.4安全性规则

2.4.1 Leader 选举安全性

2.4.2日志提交安全性

2.4.3日志不一致的修复

2.5本章小结

第三章基于节点优先级的Leader选举

3.1 Raft 算法Leader 选举的弊端

3.2优先级选举相关概念

3.3优先级选举的流程

3.3.1资格确认

3.3.2资格写入

3.3.3正式投票

3.4优先级选举的活性与可靠性

3.4.1资格确认失败

3.4.2资格信息副本超过半数

3.4.3资格信息副本小于半数

3.5优先级选举的安全性论证

3.6优先级选举时序协调

3.7本章小结

第四章多客户端场景下的并发操作

4.1 Raft 算法的性能问题

4.2并发操作的基本流程

4.3并发操作引入的问题

(1) 日志空洞引起的数据不一致

(2) 随机的日志项接收顺序

(3) 无法确定满足安全性的Leader节点

4.4.1日志追加

4.4.2日志确认

4.4.3日志提交

4.4.4 Leader 选举

4.4.5日志修复

4.4.6过期日志删除

4.5本章小结

第五章实验与分析

5.1改进Raft算法的实现

5.1.1优先级Leader选举

5.1.2日志复制

5.2实验环境

5.3 Leader 选举

5.3.1选举结果

5.3.2 选举耗时

5.4 日志复制

5.4.1 写入性能

5.4.2 写入延迟

5.5 本章小结

总结与展望

致谢

参考文献

攻读硕士学位期间发表的论文及参与的项目