【论文阅读】基于LevelDB的分布式数据库研究

基于LevelDB的分布式数据库研究

基于LevelDB的分布式数据库的研究与实现 - 中国知网 (cnki.net)

实现了什么？

基于键值型NoSQL数据库LevelDB，并与数据一致性算法Raft、 数据分片和负载均衡相结合，设计并实现基于LevelDB的分布式数据库。

主要工作包括：

1、修改Raft算法读取策略，将只允许从Leader读取修改为允许从Follower读 取，减轻Leader负担，在读负载远远大于写负载时增加读取吞吐量，减少请求平均延迟；增加预选举机制，在发起正式选举之前首先发起预选举，只有收到大多数的回复之后才正式发起选举。解决Raft算法在网络分区时可能出现的对已提交日志丢弃问题。

2、实现基于关键字区间分布的数据分布功能，为顺序读写提供友好地支持；实现负载均衡功能，通过分区拆分、分区迁移，动态地调整系统负载；添加中间层，
实现在单个存储实例上为多个用户提供逻辑独立的存储空间。
3、设计并实现原型系统DLevel。该系统具备基本的增删改查功能，

基本概念

CAP 与 BASE

CAP:数据一致性(Consistency)、服务可用性 (Availability)和分区容错性(Partition-tolerance)。

CAP理论正式成为分布式系统领域基本 定理，该定理指出对于分布式系统来说，下面三点不可能同时兼得：

• 一致性（Consistency）：所有节点的数据在任何时刻都保持一致
• 可用性（Availability）：对系统的读写请求总是能够成功完成
• 分区容错性（Partition tolerance）：在节点宕机或者网络分区导致消息丢失时，系统仍能对外提供满足一致性和可用性的服务

BASE理论就是源于对分布式系统的实践总结，将强一致性降低为最终一致性。指Basically Available（基本可用）、Soft State（软状态）和Eventually Consistent （最终一致性）。

• 基本可用：分布式系统出现节点宕机或者网络分区的时候，允许损失一部分的一致性，来保证核心可用
• 软状态：相对于强一致性，必须保证多个节点的数据副本保 持一致而言，软状态允许允许系统不同节点间数据副本同步有一定的延 迟，允许数据副本处于不一致状态，不要求时时刻刻完全保持一致
• 最终一致性：虽然可能会存在不一致的时刻，但是经过一段时间的数据同步之后，系统中数据副本最终能够保持一致

LevelDB

架构图

主要包含六个主要部分。内存中的Memtable 和Immutable Memtable，磁盘中的SSTable、Log文件、manifest文件和Current文 件。Memtable和Immutable Memtable都是基于Skiplist实现，区别在Immutable Memtable是不可变的Memtable。SSTable是主要保存KV数据的数据结构，将KV 数据对封装在一起，按照key有序保存。SSTable文件存储在磁盘中，按照层级存 储，从高层Level 0层一直向低层Level n扩展，低层Level n的SSTable数据来自 于高层Level n-1 SSTable的合并结果，每个层级内SSTable的start_key_与end_key_的

levelDB特点：

1. LevelDB以机械磁盘作为主要存储介质，而非像Redis、Memcache等数据库，以内存作为主要存储介质
2. LevelDB按照Key有序排列，支持自定义key比较方式
3. Key和Value支持任意字节长度
4. 支持快照，数据采用Snappy压缩算法自动压缩，支持前向和后向迭代器
5. 支持原子批量操作，提供基本的操作接口Put、Get、Delete

RPC

RPC通常基于C/S 模式，Client在请求时携带预先定义的请求参数，调用Server端程序，Server在收 到客户端请求之后，解析请求参数，执行相应程序，返回client处理结果。

系统需求分析

设计目标

（1）具有LevelDB原生态的基本功能，提供包括Open、Close、Put、Get、 Delete、Scan等基本操作接口；
（2）通过数据分区算法将数据分布到多个存储集群中，提供远大于单机存储 容量的存储服务；
（3）通过Raft一致性算法来保证副本集内数据的强一致性，数据的写入成功
标志是成功写入到副本集中的大多数的成员。一旦数据写入成功，之后所有的客户
端都会看到最新的、一致的数据；
（4）在保证数据一致性的前提下，尽可能的提高系统的可用性，减少服务不 可用时间。

功能需求

（1）具备分布式KV数据库的基本功能

• 打开与关闭，Open(dbname)、Close(dbname)
• 数据写入Put(key, value)，将key-value键值数据库写入数据库
• 数据查询Get(key)，通过关键字key返回对应的value
• 数据删除Delete(key)，删除关键字key对应的key-value键值对
• 获取指定范围内且数量小于limit的所有key-value数据Scan(start_key, end_key, std::map<std::string, std::string>, int limit)。

上述可以看出 这个系统是没有实现上层的KV到关系模型的转换 并且不支持SQL查询的。只是简单的KV操作

（2）支持副本集，通过数据复制来提高系统的可靠性，当有部分存储节点宕机时仍能保证系统的可用性；

（3）负载均衡，当数据分布不均衡时，通过分区的拆分和合并，分区的迁移 等方法来均衡系统中的数据分布；

（4）水平扩展，当存储容量需要扩展时，通过新增Storage Server Group来扩展系统的存储容量

三四基本暂时用不到，负载均衡和水平扩展是后面可能能加上的。

性能需求

1. 可用性。当元数据管理节点 或者存储节点发生故障时，只要不是超过所在集群的半数节点，系统仍能保证服务 可用。
2. 可靠性。本系统中通过数据复制将数据复制到大多数成员甚至所有成员， 当副本集内大多数节点存活时，数据就不会丢失。假设每个副本集节点损坏的概率p，副本集中节点数量为n。只有当副本集中所有节点都损坏时才会造成数据丢失， 因此本系统的可靠性为1-p^n。
3. 可维护性

系统整体设计

架构图如下：

CS架构，服务器端主要由元数据管理模块MetaInfo Server Group，存储模块Storage Server Group组成，两者之间通过心跳交互。

客户端通过网络请求首先连接至元数据管理模块，返回具体 的存储模块信息之后，再向存储模块发起网络请求，存储模块完成对应的操作请求 之后返回客户端操作结果。

？ 这样是不是就是被单模块限制了效率了？ 还是说这个元数据管理模块是raft group 基本是只读的，然后每个成员都可以处理，所以效率还是分布式的效率？

元数据管理模块 负责分区信息的管理、请求路由、负载均衡

存储模块：负责KV数据的读写请求，每个raft group中包括一 个主副本节点和多个从副本节点。存储模块由多个storage server group组成，每个 group负责特定分区的读写请求。

DLevel还包括集群管理模块，主要借助Zookeeper实现，存储模块和元 数据管理模块在启动时，在Zookeeper指定目录下创建znode，如果节点出现故障， 不能与Zookeeper进行心跳联系，Zookeeper就会产生相应的报告信息，以此用于集群管理。

关于zookeeper，这个文章是参考了：[22] Ti KV. https://github.com/tikv/tikv. [23] Pegasus. https://github.com/XiaoMi/pegasus. [44] FoundationDB. https://www.foundationdb.org/.

服务端

step 1：首先启动Zookeeper，便于Storage Server和Metainfo Server注册；

step 2：Storage Server初始化，因为Storage Server集群包括多个group，每个 group内部启动时通过Raft算法选举出当前group内的Leader，然后每个Storage Server在Zookeeper中创建各自znode节点。 // 怎么知道哪个是一个group呢？

Step 3：Metainfo Server初始化，Metainfo Server作为系统中心节点，一般配置 三个节点，通过raft算法进行管理。group选举出Leader， 然后每个Metainfo Server 在Zookeeper中创建各自znode节点。

Step 4：Storage Server和Metainfo Server启动成功之后，双方建立心跳连接，在心跳中Storage Server附带自身状态信息上传值Metainfo Server，用于Metainfo Server管理集群，进行负载均衡。

Step 5：Metainfo Server初始化分区节点映射关系表。

Step 6：完成启动，系统对外提供服务。

存储模块

改造成为分布式版本首先需要添加网络通信模块，本文通过RPC实现网络通信。本文通过一致性算法Raft实现副本集。

服务接入层主要由RPC模块和命令处理模块组成，存储节点的服务接入层同时可能收到多个客 户端的请求，因此接入层需要具备一定的并发处理能力。服务接入层首先对来自客 户端的消息后做简单的处理，如消息格式的合法性验证、消息内容的规范性验证等，然后交给数据同步层。

数据同步层主要由分布式一致性算法Raft组成，用于将接入层接收的请求同 步到group副本集中。数据同步层主要由一致性模块、状态机和日志模块组成。先将数据接入层处理的消息经由一致性模块同步到副本集中的所有节点，通常是 由领导者将自身数据同步到追随者。数据同步时的数据一般都是序列化之后的操 作日志，然后再交由日志模块，解析提取出具体的客户端请求。副本集中的每个节 点拥有相同的日志序列，再加上状态机，所有节点最初处于相同的状态，应用相同 的操作序列之后，之后也处于相同的状态，从而实现一致性状态机。数据同步层通过Raft算法保证数据的强一致性

数据存储层主要由LevelDB存储引擎组成。

元数据管理模块

总体上为一个Raft集群，由三个MetaInfo Server组成，每个MetaInfo Server内部大致分为三层，分别是接入层、数据同步层和服务层，服务层主要完成请求路由和负载均衡两个主要功能。

元数据集群存储分区与存储节点的映射关系表， 客户端请求到达元数据管理集群之后，通过查找映射关系表，返回客户端具体的存 储集群。

数据同步模块

Client首先向Leader发起写入请求，Leader将写入操作序列日志写入到本地， 然后Leader再向Follower进行转发，Follower写入本地后向Leader返回确认信 息，Leader收到来自大多数Follower的确认信息就向client返回确认。

配置管理模块

每个集群都拥有多个节点，且同一集群中的多个节点运行相同的 服务，存在一些相同的配置。

对于同一个集群中如 果要修改这些参数，则必须同时修改多个节点中的参数，在分布式环境下非常容易出问题。本系统主要借助Zookeeper来完成集群配置管理。Zookeeper是一种分布 式协调服务，通过提供简单的架构和API解决了分布式环境中协调和管理服务，方便程序开发。

这里就是用zookeeper来管理元数据？

watch 节点 当节点发生变动时， 元数据管理集群会收到变动事件，从而感知到存储集群的变化，随即进行相应的应 对策略。

客户端模块

针对我们的需求，用户交互模块加上sql、事务即可。

缓存模块来缓存路由表，只要路由表没有发生变更，就不用每次都经过元数据管理路由。当发生路由表变更时，元数据管理集群向client发送请求，更新 路由表。

也就是说 给某个节点发请求，可以不用再查询元数据，而是根据缓存直接路由。

读写流程

写入

读取

总结一下：在我们的架构设计中，也可以采用CS架构，在客户端的启动过程中就与元数据管理器进行交互，缓存路由，但是这个表大不大呢？ 然后根据这个缓存的内容直接读取；

如果是我们有上层的查询的话，客户端要不要进行粗粒度的查询处理呢？ 不进行的发给服务器，然后那缓存的就白缓存了？

系统实现

存储模块

数据同步模块实现

Leader选举

为了解决网络分区所带来的错误，使用预选举来感知集群网络状况，直到收到大多数节点的回复，才开始真正的选举。

类图如下:

主要包括RaftNode类、RaftNodeManger类、RaftService类三个类。

RaftNode类是对Raft算法中节点的封装描述，定义节点的行为。包括节点初 始化init、节点启动start和终止shutdown和join、处理leader选举中的请求服务 handler_request_vote、处理raft group成员添加和移除的add_peer和remove_peer、 重置选举时间reset_election_timeout等。

RaftService类是由定义的protobuf文件raft.proto经过protoc编译自动生成的， raft.proto文件主要定义request_vote和append_entries两个主要rpc服务的接口， 其发送的参数数据格式与返回数据格式。

具体的内容图4-12所示： request_vote rpc请求参数包括节点server_id，当前term号，最后一条日志 last_log_term及最后一条日志下标last_log_index；回复参数包括当前term号以及 是否投票。pre_vote参数与request_vote参数相同，pre_vote rpc用于探测当前集群 中节点之间的网络状况，防止网络分区时处于小部分分区的节点，持续发起Leader 选举造成term号的交替增加，最后分区合并时小部分分区的节点当选Leader，从 而对网络分区期间提交的日志进行丢弃和覆盖。

RaftNode的 具体实现在RaftNodeImpl类中完成，RaftNode类中通过成员变量RaftNodeImpl* impl_来调用具体的实现，使得类的实现与类本身解耦，同时达到类的内容实现对于类的使用者透明。

RaftService类是由定义的protobuf文件raft.proto经过protoc编译自动生成的， raft.proto文件主要定义request_vote和append_entries两个主要rpc服务的接口，其发送的参数数据格式与返回数据格式如下：

ppend_entries rpc请求参数包括节点server_id，当前term号，上一条日志号 prev_log_term，上一条日志下标prev_log_index，当前请求中待复制的日志entries， 注意这里是列表形式，可以一次性提交复制多条日志，最后是系统已提交的日志

RaftNodeManage类对RaftNode进行管理，通过std:map记录group中的 RaftNode的信息，负责Group中Node的添加、移除及获取当前Group的成员信 息等。

选举流程如下，在发送request_vote rpc之前，首先发送pre_vote rpc探测当前集群中的网络状况。当收到 pre_vote rpc的大多数回复之后，才开始Raft算法伪代码中描述的选举流程。

日志复制

日志复制模块的类图如图。日志复制模块相关的类主要LogStorage类、LogReplicator类、LogReplicatorGroup类和FSM类。

LogStorage类主要负责存储日志，主要包括添加单条日志append_log_entry和 批量添加日志append_log_entries、与Leader同步日志match_log，去除与Leader不 一致的log entry，获取尚未同步的log entry等。

LogReplicator类是Leader在日志复制时为每个Follower创建该类具体实例来 管理日志复制，负责记录的主要数据如目前已经同步的日志条目log_index_、下一 个待同步的日志条目next_index_、日志同步的timeout_、已同步的日志条目等等。 LogReplicator类的主要行为包括开始与Follower同步start、停止与Follower同步、 stop和join、检查与Follower日志一致性并强制同步catch_up、保持心跳等。
FSM类主要实现状态机，用于接收每个raft node上执行的事件。当Leader确 定日志已经同步到大多数节点时，便将操作apply到状态机中。一旦提交到状态机 之后，便表示该日志已经commit。

日志同步的具体流程

提高性能的措施：

1. 主要采用日志批量提交（batch），对于Leader一次收集一定size的client的 请求然后批量发送给Follower。但这种方式需要考虑size大小限制
2. Leader可以将LOG发送给Follower和Append到本地并行处理

读取模式

Raft算法中标准的读写只能经由Leader完成，Follower不能对外提供任何读写 请求，如果有客户端连接到Follower之后，会将请求转至Leader。Leader始终具有最新的已提交日志记录，这种设计保证每次都能读取都能读取到最新的数据，但对于读请求来说，如果允许从Follower读取，则会一定程度上减轻Leader的负担，增加读取的效率，但关键在于如何保证读取尽可能新的数据。

读取模式

Raft算法中标准的读写只能经由Leader完成，Follower不能对外提供任何读写 请求，如果有客户端连接到Follower之后，会将请求转至Leader。Leader始终具有最新的已提交日志记录，这种设计保证每次都能读取都能读取到最新的数据，但对于读请求来说，如果允许从Follower读取，则会一定程度上减轻Leader的负担，增加读取的效率，但关键在于如何保证读取尽可能新的数据。