分布式存储初探

缘起

最近公司内部在做dmp服务，目前的方案都是搭建不同的redis集群，将数据灌到redis集群中系统查询服务供线上使用。但是随着数据量的增大以及数据源的多样性，再加上线上服务需要多机房的支持，后续继续使用redis集群必然导致成本过高。 当然也考虑过使用hbase来支持线上服务，但是线上服务对请求相应要求高，而hbase有延迟高的风险，所以有了本次对分布式kv数据库的一些调研性工作。

为什么需要分布式数据库

在使用分布式数据库之前，我们一般使用mysql来支持一般的线上业务，即使在单机存储有限的情况下，我们也可以使用sharding的方式分库分表来支撑数据量大的情况，但是sharding又有其自身各种各样的弊端，例如其跨节点join的复杂性和网络传输问题。所以由于单机的数据存储有限，无法满足我们对数据的存储和查询，于是分布式存储应运而生。

分布式数据库需要解决哪些基本问题

1. 数据如何存储
2. 数据如何查询，如何索引
3. 如何保证HA
4. 如何保证一致性

下面将分别对如上4个问题介绍现在业界内的比较成熟的开源产品是如何解决的。

数据的存储和查询

任何持久化存储，最后都要落到磁盘上。而且根据数据的实际应用，数据的存储和数据的查询必然紧密联系的。目前业界内比较成熟的存储引擎在索引数据时使用的数据结构包括：B-Tree,B+Tree和LSM-Tree，下面我将详细讲解这三个结构的异同。

B-Tree

B树是一种多路自平衡搜索树，它类似普通的二叉树，但是B书允许每个节点有更多的子节点。B树示意图如下：

B树的特点：

1. 所有键值分布在整个树中
2. 任何关键字出现且只出现在一个节点中
3. 搜索有可能在非叶子节点结束
4. 在关键字全集内做一次查找，性能逼近二分查找算法

B+ Tree

B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：

从图中也可以看到，B+树与B树的不同在于：

1. 所有关键字存储在叶子节点，非叶子节点不存储真正的data
2. 为所有叶子节点增加了一个链指针

B/B+树普遍在文件系统和mysql中被用来做索引的实现。大家知道mysql是基于磁盘的数据库，索引是以索引文件的形式存在于磁盘中的，索引的查找过程就会涉及到磁盘IO消耗，磁盘IO的消耗相比较于内存IO的消耗要高好几个数量级，所以索引的组织结构要设计得在查找关键字时要尽量减少磁盘IO的次数。根据mysql内部对记录按照页管理的方式，其查找索引过程中需要磁盘IO的次数只需要树的高度h-1次，而$ O(h)=O(log_dN) $，其中d为每个节点的出度，N为记录个数，通常d的值是非常大的数字，因此h非常小，通常不超过3。

另一方面，mysql选择使用B+树而不使用B树的原因如下：

1. B+树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储data，所以一个节点可以存储更多的内节点，每个节点能索引的范围更大更精确。也就是说使用B+树单次磁盘IO的信息量相比较B树更大，IO效率更高。
2. mysql是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而B树每个节点的key和data在一起，无法进行区间查找。

LSM树(Log Structured Merge Tree)

首先我们要了解一个事实，随机读写磁盘是非常慢的，但是顺序读写磁盘却要比随机读写主存快至少3个数量级。

LSM树的设计目的是为了实现顺序写磁盘，而顺序写意味着我们省去了随机写的磁盘寻道时间，这样可以为随机读磁盘提供更多的磁盘IO机会，以此来提高读的性能。

所以LSM的设计思想就呼之欲出了：将对数据的修改增量保持在内存中，当到达执行的大小限制后将这些修改操作批量写入磁盘。

但是LSM具体是如何实现这个思想的呢？

LSM树弄了很多个小的有序结构，比如每m个数据，在内存里排序一次，下面m个数据，再排序一次，这样一次做下去，我们就可以得到N/m个有序的小结构。在查询的时候，因为不知道某个数据到底在哪里，所以就从最新的一个小的有序结构里做二分查找，找到就返回，找不到就继续找下一个有序小结构，一直到找到为止。其复杂度为$N/m * log_2m$。

但是上面这种方式会存在一些问题：

1. 数据先写到内存中，中间断电或进程crash会造成数据丢失，所以需要写WAL来作为数据恢复的依据。
2. 随着小的有序结构越来越多，读的性能会越来越差，这个时候就需要对小文件做合并，合并成大的有序结构。
3. 这其实是一个优化项，LSM树使用布隆过滤器来对小文件中是否存在要查找的数据做粗略的判断。

目前使用LSM树的数据库包括hbase,leveldb,rocksdb。

高可用和一致性问题

HA包括服务高可用和数据完整性。针对第一点一个比较通用的方式就是以主备的形式来提供服务，像redis的master-slave架构，而第二点则通常将数据冗余存储在多台服务器上来实现数据的备份达到高可用的目的，像hdfs和kafka，zookeeper更是同时满足以上两点的更典型的一个案例。

但是说到主备和数据冗余，其意味着需要将数据或状态同时存储在多台服务器上，那么在发生主服务crash，需要从服务提供服务或启用副本数据时，就要求其状态和数据要与主服务或数据保持一致，这就是分布式系统之间典型的一致性问题。

在目前的分布式领域中，有关一致性问题的解决有几个经典算法：Poxas,Zab和Raft，介于Poxas算法太难理解，这里我们只介绍raft。

Raft算法

Raft 通过选举一个高贵的领导人，然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。 通过领导人的方式，Raft 将一致性问题分解成了三个相对独立的子问题：

1. Leader 选举
2. 日志复制
3. 安全性

在raft算法中，每个服务器都处于三种状态之一：leader,candidate,follower。在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。跟随者都是被动的：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。领导人处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导人）。第三种状态，候选人，是用来在选举新领导人时使用。下图展示了这些状态和他们之前转换关系。

任期：在集群中，时间被划分成一个个的任期，每个任期开始都是一次选举。在选举成功后，领导人会管理整个集群直到任期结束。如图：

下面介绍一下raft算法是如何工作的。

领导人选举

Raft 使用一种心跳机制来触发领导人选举。当服务器程序启动时，他们都是跟随者身份。之后他会根据不同的触发条件转换成其他状态：

1. 在一段时间之内接收到其他服务器发来的RPC请求，刷新本地超时计时，继续处于跟随者状态。
2. 在一段时间之内没有接收到任何消息，即选举超时，那么他会认为系统中没有leader，其将自己变为选举者状态，并向其他服务器发起RPC请求，请求他们投票给自己成为leader。

在2的情况下，若一个候选者获取了一个集群中大多数服务器节点的投票，那么他赢得这次的选举称为领导人;当一次选举中有两个服务器同时半数投票，则此次选举没有leader，继续下一届选举。在一次选举内，每个服务器最多只会对一个服务器进行投票，按照先来先服务原则。一旦某个候选人赢得此次选举，他就立即称为领导人，然后他会定期向所有跟随者发送心跳消息来建立自己的权威并阻止新的领导人产生。

在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导人的附加日志项RPC。如果这个领导人的任期号（包含在此次的 RPC中）不小于候选人当前的任期号，那么候选人会承认领导人合法并回到跟随者状态。如果此次RPC中的任期号比自己小，那么候选人就会拒绝这次的RPC并且继续保持候选人状态。

日志复制

一旦一个领导人被选举出来，他就开始为客户端提供服务。客户端的每一个请求都包含一条被复制状态机执行的指令。领导人把这条指令作为一条新的日志条目附加到日志中去，然后并行的发起附加条目RPCs给其他的服务器，让他们复制这条日志条目。当这条日志条目被安全的复制，领导人会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端。如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导人会不断的重复尝试附加日志条目RPCs（尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

每一个日志条目存储一条状态机指令和从领导人收到这条指令时的任期号。日志中的任期号用来检查是否出现不一致的情况，同时也都有一个整数索引值来表明它在日志中的位置。

raft通过维护以下特性来保证不同服务器的日志之间的高层次的一致性：

• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

这种特性其实更像是一种数学归纳法。

然后我们来谈一谈当发生领导人崩溃，导致一些服务器上的日志不一致时，新的领导人要如何来处理。在Raft算法中，领导人处理不一致是通过强制跟随者直接复制自己的日志来解决了。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖。但是这种覆盖会通过一些限制来保证这样的操作是正确的，安全的。

具体的保证日志一致性的操作如下：

1. 领导人针对每个跟随者维护了一个nextIndex，指下一次需要发给跟随者的日志条目的索引地址。
2. 当一个领导人刚获得权利的时候，他初始化所有的nextIndex为他自己的最后一条日志的index + 1。
3. 如果一个跟随者的日志和领导人不一致，那么在下次的附加日志RPC时的一致性检查会失败，在被跟随者拒绝之后，领导人就会减小nextIndex值并进行重试。
4. 最终nextIndex会在某个位置使得领导人和跟随者的日志达成一致。

当这种情况发生，附加日志RPC就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志 RPC 成功，那么跟随者的日志就会和领导人保持一致，并且在接下来的任期里一直继续保持。 领导人从来不会覆盖或者删除自己的日志。

安全性

上面说到在新选举领导人和跟随者的日志发生冲突时，会通过一些限制来保证日志覆盖的正确性，这些限制体现为，当进行选举时，保证任何领导人对于给定的任期号，都拥有之前任期的所有被提交的日志条目。raft限制只有一个候选人包含了所有已经提交的日志条目，它才可以赢得选举。选举人为了赢得选举，必须联系集群中的大部分节点，同时每一个已经提交的日志也必然出现在集群中的大部分节点，而两个过半集合肯定有一个交集。这就保证了至少有一个以上的节点持有集群中所有已经提交的日志，同时投票人会拒绝掉那些日志没有自己新的投票请求。在比较日志时，投票给候选人的条件为：

• 请求投票的最新日志的任期应大于等于投票人的最新日志的任期，即req.lastLogTerm >= lastEntry.term
• 如果req.lastLogTerm == lastEntry.term，请求投票的最新日志的索引值应大于等于投票人的最新日志的索引值，即req.lastLogIndex >= lastEntry.index。

raft演示demo

更加详细的介绍见raft paper

几个成熟的分布式数据库架构

hbase

HBase是一个分布式的、面向列的开源数据库，它不同于一般的关系数据库,是一个适合于非结构化数据存储的数据库。另一个不同的是HBase基于列的而不是基于行的模式。HBase使用和BigTable非常相同的数据模型。用户存储数据行在一个表里。一个数据行拥有一个可选择的键和任意数量的列，一个或多个列组成一个ColumnFamily，一个Family下的列位于一个HFile中，易于缓存数据。表是疏松的存储的，因此用户可以给行定义各种不同的列。在HBase中数据按主键排序，同时表按主键划分为多个Region。

在分布式的生产环境中，HBase 需要运行在 HDFS 之上，以 HDFS 作为其基础的存储设施。HBase 上层提供了访问的数据的 Java API 层，供应用访问存储在 HBase 的数据。在 HBase 的集群中主要由 Master 和 Region Server 组成，以及 Zookeeper，具体模块如下图所示：

简单介绍一下 HBase 中相关模块的作用：

• Master HBase Master用于协调多个RegionServer，侦测各个RegionServer之间的状态，并平衡RegionServer之间的负载。HBaseMaster还有一个职责就是负责分配Region给RegionServer。HBase允许多个Master节点共存，但是这需要Zookeeper的帮助。不过当多个Master节点共存时，只有一个Master是提供服务的，其他的Master节点处于待命的状态。当正在工作的Master节点宕机时，其他的Master则会接管HBase的集群。
• Region Server 对于一个RegionServer而言，其包括了多个Region。RegionServer的作用只是管理表格，以及实现读写操作。Client直接连接RegionServer，并通信获取HBase中的数据。对于Region而言，则是真实存放HBase数据的地方，也就说Region是HBase可用性和分布式的基本单位。如果当一个表格很大，并由多个CF组成时，那么表的数据将存放在多个Region之间，并且在每个Region中会关联多个存储的单元（Store）。
• Zookeeper 对于HBase而言，Zookeeper的作用是至关重要的。首先Zookeeper是作为HBase Master的HA解决方案。也就是说，是Zookeeper保证了至少有一个HBase Master 处于运行状态。并且Zookeeper负责Region和Region Server的注册。其实Zookeeper发展到目前为止，已经成为了分布式大数据框架中容错性的标准框架。不光是HBase，几乎所有的分布式大数据相关的开源框架，都依赖于Zookeeper实现HA。

tair

通常情况下，一个集群中包含2台configserver及多台dataServer。两台configserver互为主备并通过维护和dataserver之间的心跳获知集群中存活可用的dataserver，构建数据在集群中的分布信息（对照表）。dataserver负责数据的存储，并按照configserver的指示完成数据的复制和迁移工作。client在启动的时候，从configserver获取数据分布信息，根据数据分布信息和相应的dataserver交互完成用户的请求。其架构图如下：

• ConfigServer功能
  1. 通过维护和dataserver心跳来获知集群中存活节点的信息
  2. 根据存活节点的信息来构建数据在集群中的分布表。
  3. 提供数据分布表的查询服务。
  4. 调度dataserver之间的数据迁移、复制。
• DataServer功能
  1. 提供存储引擎
  2. 接受client的put/get/remove等操作
  3. 执行数据迁移，复制等
  4. 插件：在接受请求的时候处理一些自定义功能
  5. 访问统计

tidb

整体架构如下：

TiDB 集群主要分为三个组件:

• TiDB Server TiDB Server 负责接收 SQL 请求，处理 SQL 相关的逻辑，并通过 PD 找到存储计算所需数据的 TiKV 地址，与 TiKV 交互获取数据，最终返回结果。 TiDB Server 是无状态的，其本身并不存储数据，只负责计算，可以无限水平扩展，可以通过负载均衡组件（如LVS、HAProxy 或 F5）对外提供统一的接入地址。

• PD Server Placement Driver (简称 PD) 是整个集群的管理模块，其主要工作有三个： 一是存储集群的元信息（某个 Key 存储在哪个 TiKV 节点）；二是对 TiKV 集群进行调度和负载均衡（如数据的迁移、Raft group leader 的迁移等）；三是分配全局唯一且递增的事务 ID。PD 是一个集群，需要部署奇数个节点，一般线上推荐至少部署 3 个节点。

• TiKV Server TiKV Server 负责存储数据，从外部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。存储数据的基本单位是 Region，每个 Region 负责存储一个 Key Range （从 StartKey 到 EndKey 的左闭右开区间）的数据，每个 TiKV 节点会负责多个 Region 。TiKV 使用 Raft 协议做复制，保持数据的一致性和容灾。副本以 Region 为单位进行管理，不同节点上的多个 Region 构成一个 Raft Group，互为副本。数据在多个 TiKV 之间的负载均衡由 PD 调度，这里也是以 Region 为单位进行调度。