论文总字数：34187字

摘 要

随着移动互联的飞速发展，当今的数据库需要支持海量规模数据的存储与高并发读写，同时需要满足高可扩展性、高可用性。传统的关系型数据库因吞吐率低而成为服务端应用的瓶颈所在，且单机数据库的扩展性差、可用性低、垂直扩展的价格高昂，这些缺点使得越来越多的人开始关注NoSQL数据库。本设计开发了一款分布式键值型NoSQL数据库，底层使用一致性算法Raft来保障集群的消息同步，可选择接入不同的存储引擎来应对不同的数据读写场景，同时支持数据分片，副本自动负载均衡，动态扩容。整个应用使用Go语言实现，可通过Docker自动化部署。

本设计的主要工作包括：

1、实现Raft算法模块。在原Raft论文的理论基础上，实现选主机制、心跳机制、日志复制以及日志压缩等功能，节点之间使用RPC进行通信；

2、设计并实现可插拔的存储引擎模块。本模块对外封装基础接口，可以支持多种存储引擎。本设计接入了LevelDB、RocksDB、BoltDB三种常用的存储引擎；

3、设计并实现分片存储模块。该模块通过算法对数据集进行分区，把分片均匀地分配给不同的副本组来管理；

4、设计并实现MetaServer模块，用于管理集群的副本分布信息，提供副本负载均衡，支持动态扩容；

5、设计并实现客户端API，支持命令行交互。将整个应用打包成镜像，使用Docker自动化部署。最后，对整个系统做单元测试，验证各个模块的功能，同时做好集成测试、压力测试，验证本系统的数据一致性，确保系统能承受高并发，具有高可用性、可扩展性；

关键字：分布式数据库 键值型存储 Raft 可选存储引擎 数据分区

Distributed Key-Value Database Based on Multiple Storage Engine

ABSTRACT

With the rapid development of mobile Internet, the current database needs to support the storage and high concurrent reading/writing of massive data, and needs to meet the high scalability and high availability. The traditional relational database has become the bottleneck of server application because of its low throughput, and the single database has poor scalability, low availability and high price of vertical expansion, which makes more and more people begin to pay attention to NoSQL database. In my design, a distributed Key-Value NoSQL database is developed, which uses Raft algorithm to ensure the consistency of data. It can choose to access different storage engines to cope with different data reading and writing scenarios. At the same time, it supports data fragmentation, replica load balancing, and dynamic capacity expansion. The whole application is implemented in go language and can be automatically deployed through docker.

The main work of my design includes:

1. Implement the Raft algorithm module. Based on the theory of the original Raft paper, leader election, heartbeat, log replication and log compression are implemented, and RPC is used to communicate between nodes;
2. Design and implement pluggable storage engine module. This module encapsulates the basic interface and can support a variety of storage engines. This design accesses three commonly used storage engines: LevelDB, RocksDB and BoltDB;
3. Design and implement the module of memory partition. In this module, the data set is partitioned by algorithm, and the partition is evenly distributed to different replica groups for management;
4. Design and implement MetaServer module to manage the replica distribution information of cluster, provide replica load balancing and dynamic capacity expansion;
5. Design and implement client API, support command line interaction. Package the whole application as an image and use docker to automate deployment. Finally, unit test is done to the whole system to verify the functional modules of the system. At the same time, integration test and pressure test are done to verify the data consistency of the system to ensure that the system can withstand high concurrency, high availability and scalability.

Keywords: Distributed Database Key-Value Storage; Raft; Optional Storage Engine; Data Partition;

目 录

摘 要 I

ABSTRACT II

第一章 引言 1

1.1研究背景和意义 1

1.2分布式数据存储的国内外研究现状 3

1.2.1 分布式一致性算法的研究现状 3

1.2.2 分布式存储模型的研究现状 3

1.3论文研究的内容 5

第二章 理论知识和关键技术 6

2.1分布式系统的数据同步 6

2.1.1 RPC(Remote Procedure Call)^[26]通信 6

2.1.2 一致性算法Raft^[12] 7

2.2分布式系统理论 12

2.2.1 数据分区 12

2.2.2 负载均衡 14

2.3存储引擎 15

2.3.1 B/B Tree模型 15

2.3.2 LSM-Tree模型 17

2.3.3 Hash模型 18

第三章 需求分析与系统设计 19

3.1 系统需求分析 19

3.1.1 功能需求 19

3.1.2 性能需求 20

3.2 系统整体架构设计 21

3.3 数据同步模块设计 22

3.3.1 Leader选举与心跳 23

3.3.2 日志复制 24

3.3.3 日志压缩 25

3.4 存储引擎模块设计 26

3.5 MetaServer模块设计 27

3.5.1 水平伸缩 27

3.5.2 负载均衡算法 28

3.6 分片存储模块设计 28

3.6.1 分区算法 29

3.6.2 数据读写 30

3.6.3 副本迁移 31

3.4 客户端交互模块设计 32

第四章 系统实现 34

4.1 数据同步模块实现 35

4.1.1 Leader选举 35

4.1.2 日志复制 37

4.1.3 日志压缩 39

4.2 存储引擎模块实现 40

4.2.1 抽象存储引擎层 40

4.2.2 接入存储引擎 40

4.3 MetaServer模块实现 41

4.4 分片存储模块实现 43

4.4.1 数据读写 43

4.4.2 副本迁移 45

4.5 客户端交互模块实现 46

第五章 系统部署与测试 48

5.1 系统环境 48

5.2 Docker自动化部署 49

5.3 系统测试 50

5.3.1 数据读写功能测试 50

5.3.2 数据一致性测试 51

5.3.3 系统水平扩展测试 52

第六章 总结与展望 54

6.1 全文总结 54

6.2 课题展望 54

参考文献 56

致谢 59

第一章 引言

1.1研究背景和意义

在19世纪60年代，流行网状数据库和层次数据库，但开发者使用这两种数据库进行数据存储的时候，需要明确数据的结构和路径，这使得检索信息非常复杂且耗时。1970年，IBM的Edgar F.Codd发布了一种便捷管理数据的方案，首次提出了数据库的关系模型理论^[1]，在接下来的几年，他又提出一系列关系型数据库的数学理论。基于这些数学理论，Ray Boyce等人使用简单的关键字语法，设计出了一种通用的关系型数据库语言SQL。SQL语言使得开发者能便捷地操控关系数据库。Larry Ellison意识到Codd提出的关系数据库能全面管理错综复杂的数据信息，非常有商业价值，于是他带领研发团队开发了Oracle数据库^[2]，取得了巨大成功。

到了80年代，信息技术快速发展，越来越多的企业发现了关系型数据库管理数据信息的便捷之处，甲骨文的Oracle^[2]、IBM的DB2^[3]等优秀关系型数据库快速占领了市场。随后，开源的数据库也层出不穷，MySQL^[4]、PostgreSQL^[5]等开源数据库受到人们的推崇。

请支付后下载全文，论文总字数：34187字