从零开始深入理解存储引擎

作者：zhengweiwu

很多应用都属于数据密集型应用，而非计算密集型；对于这类应用，CPU往往不是第一限制性因素，关键在于数据量、数据复杂度和数据的快速多变性；因此数据库的选型在应用系统设计中就显得比较重要。数据库（数据引擎）最核心的任务就是"读到写入的值"，我们尝试从"最简单的脚本文件数据读写" 一步一步扩展讨论到"分布式键值数据库"，在这个过程中我们会遇到很多"挑战"，并尝试逐步解决。

1. 单机存储引擎

从两行代码的shell脚本读写文件开始，我们通过逐步解决如下问题得到了一个单机可用的存储引擎(LSM Tree)：

1. 读取慢

2. 磁盘耗尽

3. 文件压缩合并

4. 重新组织数据文件格式提高压缩合并效率

5. 内存排序数据以实现预期的数据文件格式

6. 有序数据文件的压缩合并

7.引入预写日志解决重启内存数据丢失

不使用已有的任何数据引擎，我们重新来思考一个问题：如何从零构建一个可存储/读取数据的"数据库"?

我们先看如下这个最简单的"数据引擎"。

#!/bin/bash

db_set() {
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

使用上述shell脚本写入两条数据（key分别为 123456 和 42）之后，本地文件中的两行记录如下所示（用,区分key和value）

123456,{"name":"London","attracions":["Big Ben", "London Eye"]}
42,{"name":"san Francisco", "attractions":["Golden FateBridge"]}

上面这个"数据引擎"写操作性能足够好，因为只需要数据文件追加写入一条记录即可；

但它的读性能较差，因为需要_全文件检索_ (grep | sed)，同一个key若有过多次写操作，在数据文件中会存在多行记录，查询时只取最后一条(tail -n 1)即可。

因数据文件格式固定，当前还不支持删除操作，以及 key 中不能存在逗号, value中不能存在换行符等问题

1.2 引入索引提高读性能

当前的第一个任务就是 提高读性能。我们可以引入单独维护的索引(内存中维护的Hash Map)提升查询性能；因此写入时除了写数据文件，还需要写索引，这会降低写入的速度；这也是存储系统中很重要的权衡设计；到底关注读性能还是写性能，在技术选型的时候需要开发人员决定。

哈希索引添加索引之后，如下所示:

添加了内存中的Hash Map来快速定位Key所在的位置，hash value是文件字节偏移量(byte offset)；读取时直接从文件指定偏移位置读取到换行符即是Value值。

此时可以提供高性能的读写，但需要所有的 Key 可以全部放在内存中供索引即可；写操作仍是一次追加写，读操作只需要一次磁盘寻址即可。

引入了内存索引之后，很自然的一个问题就是机器重启，内存索引丢失怎么办？ 可以重新遍历文件构建索引，后面再讨论其他更合理的方案。
另外，相同的key若有多次写操作，则本地数据文件中也会存在多条记录；因此就有磁盘耗尽的风险；极端情况下，对同一个key持续不断的写入，直到磁盘写满，实际上只有最后一条记录是有效的。磁盘空间放大特别显著；
同时，hash map需要全部存在于内存中，若key的数量超过内存限制，也会有问题

1.3 如何避免磁盘耗尽？

文件分段，分段压缩

假定数据文件写满1GB之后就可以关闭，创建新的数据文件供后续的写入。如下 segment1写满之后就创建了 segment2；每个 segment 就是一个独立的文件；

分段合并之后的新段中仅保留每个键最新的值；通过段合并，减少段日志文件数量和总体的大小；

如上图，purr在 segment1和segment2中存在多次，经过压缩合并之后，仅保留最新的值(2114)即可；

同时要注意，上述segment中的key是无序的，是按照写入顺序来存储的；

这个"数据引擎"也还是不完善的，比如对删除记录如何处理？崩溃恢复
如何进行？区间查询是否支持？等等用这几个问题引出我们接下来的讨论

为实现区间查询和快速文件合并，对上面的日志段文件添加一个要求：Key有序。则该文件就可称之为 有序字符串表(SSTable - sorted string table)；SSTable相比上述无序的哈希索引的日志段，有如下优点：

合并更高效：多个有序文件可以使用多路归并排序，简单高效; 如下图三个segment合并到一个segment的过程；文件合并过程中会去除相同的键；

内存中的hash map不需要保存所有键：得益于键有序，类似二分查找，找到最大的小于目标键的值之后顺序遍历即可；(如下示例，日志文件中保存a-z共26个key的键值对，内存中的hash map可以稀疏存储 a/h/n/t 4个键即可，若查找d，只需要遍历查找a到h之间的文件地址空间即可)

现在还有两个问题需要解决:
1.如何构造出来这个有序的数据文件，因为数据写入时乱序的，总要有个地方对数据进行排序 2.这个数据文件内部是如何存储和检索kv对的，也就是SSTable内部文件结构如何

1.4 如何构建和维护SSTables

持续的数据写入排序不可能在文件中完成，因此我们使用内存来解决这个问题；基于内存的有序数据结构还是很多的，出于简单高效的原则，我们选择跳表作为有序数据的内存实现：

数据写入时直接写入到内存中的跳表即可，当跳表数据量达到阈值时(如1GB)就可以持久化写入(dump)到磁盘文件中，因为跳表是有序的，因此生成的文件也就是有序的，符合 SSTable的要求；

此时还有一个问题：若跳表dump到一半的时候（如上图中顺序遍历并持久化到 71），此时写入 20，待dump结束之后，跳表重建，20这个值也就丢了

因此正在dump的跳表是不能够再接收写入的，但是系统还是要接收来自客户端的写请求，因此还需要一个能够接受写请求的跳表；如下图所示：

在活跃跳表需要持久化的时候会变为不可写跳表，同时创建一个新的活跃跳表接收写请求。我们将活跃跳表称之为memtable，不可写跳表称之为immutable。只有跳表写入到磁盘SSTable的过程中内存中才存在两个跳表，除此之外，内存中只存在一个活跃的跳表接收写请求。

是时候讨论一下SSTable的文件结构了，因为只有清楚了SSTable是如何存储数据的才能理解读请求是如何处理的

1.5 详解SSTable的文件格式

首先，需要思考一个问题：一对kv如何在文件中存储？比如name:zhengwei，如果在文件中直接拼接编码成namezhengwei, 我们不知道key是name，还是namezheng；若使用特殊字符区分，则kv对中也就不允许存在特殊字符；最合理的办法还是存储key和value的长度；读取指定长度的字节序列作为目标值。

在写入到文件的时候，在key value前面分别追加key和value的长度就能通过偏移量的方式直接获取到key和value的内容；如上图中的 4 和 8，这样的一条记录，我们先称它为Entry。

这里有一个小问题就是：key_length和value_length分别用几个字节来存储呢？1字节太少，只能存储256长度的字节序列，若有超长字符串就存不下；若字节太多，如4字节，又存在了很大的空间浪费；
可以参照UTF-8变长字节编码的方式来实现，根据前几个比特位是否为0来表示使用几个字节表示字节长

我们已经有了一条记录，那么这条记录如何组织进SSTable中呢？也为了利用磁盘的页缓存特性，我们将多条记录组织成块(Block)

在字典序上，Entry1 < Entry2 < ... < Entry n；虽然有序，但是每个Entry的长度是不相等的，所以就不能直接利用数组的下标索引直接进行二分查找；为了实现二分查找，我们在Entry后面附加和每条记录一一对应的的offset数组，数组的每个元素存储的是对应Entry的偏移地址；

offset数组只记录对应Entry的偏移量，在offset中实现二分查找，需要查找对应key的时候，回溯到红色箭头所指向的Entry查找即可，类似于间接二分查找。

通过以上讨论，我们将数据组织到Block中，并且可以在Block内实现快速查找。接下来我们就来讨论如何将Block持久化到磁盘文件中，又如何在磁盘数据文件中检索到该Block

以上的Block存储的是数据，因此我们称它为DataBlock。将每个DataBlock经过压缩并生成CRC校验码，写入到文件之后我们就能得到每个DataBlock在文件中的偏移量offset和size。同时我们也知道该DataBlock中的 max key；因此，max key 、offset、 size就是该DataBlock的索引信息，如下图所示:

随着向DataBlock添加数据达到DataBlock的阈值之后，就将DataBlock写入文件，等所有DataBlock持久化之后，Index Block也完成了构建，Index Block中的每一个Entry索引了一个DataBlock，Key就是DataBlock的最后一个Entry Key，Value就是DataBlock在数据文件中的起始位置和大小。

IndexBlock本质上和DataBlock是一致的，无非存储的Value是DataBlock的索引信息

最后将Index Block也追加写入到数据文件中，如下左图示例:

当前SSTable只有DataBlock和IndexBlock，后续可能会有更多类型的Block加入进来，就跟操作系统启动时候的BIOS总是从固定地址执行机器指令一样，我们需要在SSTable添加固定的"启动位置"，即Footer(上图右侧所示)，可以认为其中的IndexBlock索引是B+树的根节点；Footer是固定大小的（48字节),最后的魔数用于验证文件是SSTable类型，中间空余部分填充空序列就好。

因此，打开一个SSTable就是首先读取文件最后48字节(Footer)，拿到IndexBlock的位置和大小之后就能将IndexBlock加载到内存中基于间接的二分查找就能找到对应的DataBlock，进而再在DataBlock内执行间接二分查找就能找到对应的值。这也就是SSTable的读取过程，如下所示:

如图中序号标定的顺序，经过上述步骤就能获取到 DataBlock中的数据。

经过上述对SSTable文件结构的讨论，我们发现一个问题：查找一个Key是否在的路径还是很长。
因此可以加入Bloom Filter实现快速判断Key是否存在该SSTable中的判断，布隆过滤器的假阳性我们是可以接受的，此处就不再详细讨论了

汇总一下我们目前的设计:

数据都落盘到了SSTable中，自然就会存在空间放大，而且虽然每个文件是有序的，但是并不能做到全部SSTable的整体有序，在读命令还是需要在所有文件中同时检索，读放大也很明显；

1.6 SSTable的压缩合并

每个immutable持久化到磁盘中的SSTable文件是有序且可能存在重复键的，如同一个key: name，可能在 SSTable1、SSTable2或其他SSTable中存在，如下图所示，每个SSTable都可以看作一段时间内写入值的有序集合。我们把从immutable直接生成的SSTable的集合称为Level 0。

因此，Level 0中存在严重的磁盘空间放大问题，自然就会想到消除重复，而消除重复的方法就是合并(compaction)。

如上图所示，Level 0层的 SSTable 1 和 SSTable 2合并成Level 1层的SSTable1，Level 1层的SSTable 2同样由上层的SSTable和本层的SSTable合并而成。

这里表述不太严谨，Level 1 层的数据文件不存在重复值，且SSTable1的键都小于SSTable2中的键。应该是每层的多个文件和下层的多个文件合并生成新层的多个文件，具体涉及到的文件和Key的交集范围有关，结合后面的讨论会更好理解。

我们给出一个具体的示例来解释Compaction:

因Level 1层中的文件数量超限，选择level1中key范围在0-30的sstable文件需要合并到下一层中，而下一层和该文件key有交集的sstable是 0-15 和 16-32 这两个文件；多路归并有序合并之后level1中的文件删除，下一层的文件也会重新生成；

不同的数据库会有不同的合并策略，不做更多的讨论。从上图中我们也能看到，数据是逐层下沉，除 Level 0外，每一层的SSTable都只会保存部分数据，同一层内不会有键重复；其实Level 0中的SSTabl往下层合并时，也是同样的道理。

经过上面对写流程的讨论，之前遗留的两个问题也就有了答案:

如何读取数据: 首先读取memtable，读到则直接返回；读不到则读取immutable，进而读取Level 0 -> Level 1 ... 直到每一层的 SSTable都读完；若在其中的一步读到了数据，则不再往下读取，适时终止。
如何删除数据：需要删除的数据, Value中存入特殊值，若读取到特定值则返回不存在；在Compaction过程中也会跳过这些有特殊值的键（也称标记删除或“墓碑”）

此时架构如下:

此时还有一个问题就是：数据初始是写入到：memtable中的，若还没来得及dump到文件中，发生了机器故障，重启之后内存丢失，memtable中写入的值也会丢失。
要想保证不丢失数据必须要落盘，为了保证写入性能不受影响，以及磁盘顺序读写性能是最高的，我们可以引入预写日志(WAL-write ahead log）。
数据首先顺序追加到预写日志中，待数据落盘落盘之后再写入到memtable中，待memtable中的数据持久化到磁盘时，该memtable对应的预写日志也就可以删除了。

1.7 LSM Tree

我们上面已经详细讨论了sstable的文件格式，不再详细讨论WAL的文件格式，有很多开源的实现；我们可以简单理解为每个memtable和immutable都对应一个WAL文件，待immutable写入到SSTable之后，对应的WAL也就可以删除了，因为该部分数据已经持久化到磁盘了。

若发生机器重启，则需要顺序重放WAL中的请求以将内存中的跳表恢复到宕机之前的状态

讨论到此，我们已经有了一个单机存储数据的数据库，即使发生重启，数据也不会丢失。实际上这就是一个LSM Tree存储引擎。也是是LevelDB / RocksDB 所采用的方案；在 Cassandra/HBase 中也有该方案的身影；基于合并和压缩排序文件原理的存储引擎通常称为 LSM存储引擎；

1.8 和B+树的对比

除了上面提到的基于LSM的存储引擎之外，还有基于B+树的存储引擎，它也几乎是关系数据库的标准实现，3-4层的B+树就可存储大量数据，不需要遍历太深（分支因子为500的4KB页的四级树可存储256TB）

如下图所示，对B+树讨论的资料很多，可以自行参考一下；不再展开

我们来对比一下 B+ Tree 和 LSM-Tree

B+树适合读多写少，LSM树适合写多读少；
LSM树写入的时候只需要一次顺序写WAL日志文件及一次内存写操作即可，成本很小；但是读取却需要多层读取，只有所有的SSTable都不存在键才能返回不存在；B+树写入需要随机写磁盘，极端情况下面对页分裂还会有多次的随机写磁盘；而读取的时候从目标位置返回值即可；在有索引和页缓存的情况下，读性能表现更好；
B+树至少写两次数据，一次WAL，一次页本身; LSM因为压缩及合并，也会存在写放大；
B+树是原地更新数据，读放大较小，写放大较大。LSM树是非原地更新，同一条数据存在多条记录，会存在空间放大；数据读取需要检测多个文件，读放大比较严重，compaction/压缩缓解了读放大和空间放大，但是又引入了写放大；因此有很多技术用来优化写放大，比如 KV分离技术和延迟压缩技术，不再讨论。
LSM树磁盘空间利用率更高，碎片更少；
因为是顺序写，Block构建好之后顺序写磁盘即可。
LSM压缩过程可能会影响正在进行的读写操作；后台压缩合并操作抢占业务进程对磁盘的读写操作；
B+树在事务方面表现更好，键只有一处，方便加锁；

因此，LSM经常应用在数据分析或其他离线场景，对读取的延迟容忍略高一些，但是需要接收比较多的写请求；B+树更多应用到在线或需要加锁的场景中。

1.9 OLAP 与 OLTP

我们详细的讨论了LSM 树，并简单对比了B+树，它们是OLAP(online analytic processing)和OLTP中日志结构流派和原地更新流派的代表；

还有融合了 OLAP & OLTP 的HTAP，代表数据库如下图所示:

我们可以简单认为OLTP服务与在线业务，直接和C端用户交互；在线数据经过ETL之后存储到OLAP中一份用于商业分析或离线特征计算后再反哺到在线业务（比如TDW / 用户画像特征等）

如下是ETL (Extract - Transform-Load, 提取/转换/加载)的过程：

将不同业务系统的数据库经过提取之后转换为分析需要的数据结构，加载到OLAP等数据仓库中，供分析师使用；

一般情况下供分析师使用的表通常很宽(有几百上千个字段/列，经过聚合多个数据源和业务数据得到)，但是每次分析时可能只会使用其中很少的列（比如用户画像表，会有很多字段，但是一次sql可能只是涉及到很少的字段- select max(age) from table where gender = 'male'）；在OLTP数据库中，存储以面向行的方式来布局；为提高查询性能，面向列存储可优化分析场景下的查询性能；列存如下图所示：

左下角是表结构，有a/b/c 三列，当前有 a1到a5共5行数据；若查询只涉及 b 列，行存储情况下(Row layout)需要间隔性的从磁盘中读取有效数据，每次从磁盘load 4KB 的页到内存中，页中包含了a/b/c三列的数据；想要获取的b列数据只占用1/3页空间；该场景下所有存储页都需要读一遍，执行一次完整的表遍历才能拿到所有的b列；

列存储情况下，会将一列单独存储，因此列存数据库下会有三个数据文件，分别存储a列，b列和c列。需要分析b列，只需要把对应的文件加载到内存即可。查询没有涉及的a列和c列对应的文件不需要读取。

为进一步描述列存储，再看下面这个示例：

表共有8列，在列存储情况下，每一列作为一个文件存储，如product_sk列，就会作为一个独立文件，存储内容为：69,69,69,74,31,31,31；

列存储，因为相同列数据类型相同，且 distinct 后数量较少，更方便压缩; 如上述 product_sk文件，连续的69和31是可以压缩存储的；不再讨论。

上面简单讨论了两类数据库，但实际上数据库的种类繁多，即使一个LSM也会存在很多的变形。DB Engines Ranking中对数据库排名如下(共有 418 种数据库参与排名):

DB-Engines Ranking 链接

如上排名中包含 Relation 、Document 、Key-value 、Search Engine 、Graph 等多种数据库类型。

可用的数据库系统如此之多，我们可以拿来就用；但因为选择太多，以及需求和设计目标的差异，个中精妙又不尽相同，我们总要清楚哪些适合自己，又该如何使用；

1.10 数据库的可靠性、可扩展性和可维护性

系统总是不可靠的，我们应该构建什么样的系统？我们进行如下的讨论，也顺便引出下一部分的讨论：单机故障了怎么办？单机数据存不下了怎么办？

1.10.1 可靠性

可靠性的定义为:即使发生了某些错误，系统仍可以正常工作；

容错一定是有范围的，业务系统容错主要考虑到单机房故障维度就可以了，更大范围容错成本太高了；因此，单容器故障、错误输入、非法访问、流量洪峰等都应该囊括在可靠性考虑范围内；

硬件故障以硬盘为例，平均无故障时间为10-50年，因此一个包含1万个磁盘的存储集群中，每天都会有磁盘故障；硬件故障是无法避免的；

软件故障bug总是持续存在的；需要进行全面的测试；同时在部署运行时，也需要进程隔离，允许进程崩溃并自动重启；

人为失误人比机器更不可靠；比如出现配置错误导致系统异常；如下的可能方案来减少人为失误：

以最小出错方式来设计系统，精心设计的抽象层/API及管理界面，使做正确的事情很轻松，搞破坏很复杂；
提供一个功能齐全的沙箱环境，放心的尝试/体验；
充分的测试；
快速恢复机制；灰度发布，最小快速验证；
详细而清晰的监控子系统，如火箭离开地面，只能依赖遥测监控；现在很多的上线发布就像没有遥测监控的火箭发射一样，只能等待坠毁事故的发生；

1.10.2 可扩展性

定义：主要指负载增加时，有效保持系统性能的扩展性；通常使用如请求 QPS、聊天室同时活动用户数量、缓存命中率等具体量化的数字描述负载；

举个例子，以Twitter查看推文流和发布推文而言:发布推文：平均 4.6K-12K QPS推文流浏览：300K QPS因此消息存储有两种方式：1) 拉模式 2）推模式
拉模式，所有消息放在全局 tweet 表中；用户浏览推文流时，首先查找所有关注对象，再关联到推文，以时间序展示；发布推文只是生成一条记录；压力在查看时的关联查询；
推模式，对每个用户维护一个序列“邮箱”，发推文时，先查询其关注者，再将推文存储到每个关注者的时间线缓存中；查看时只需要遍历自己的“邮箱”即可；压力在发推文时候的“信件投递”

twitter开始时使用方案一，但读压力与日俱增；转而采用第二种方案；第二种方案最大的问题是当明星博主拥有超过3000万粉丝时，扇出巨大，需要写巨量的“邮箱”；最终方案融合，大多数博主因为粉丝较少，持续采用第二种方案；少量粉丝巨大的明星博主采用方案一，推文被单独存储，推文展示时合并渲染；因此，每个用户粉丝的分布情况就是可扩展的关键负载参数；

对于如何描述性能，一般采用响应时间、吞吐量及延迟等描述；如下图对请求的耗时分布的展示：

亚马逊以P99.9定义内部服务响应时间，即使只是1000个请求中的一个请求失败了，但考虑到请求最慢往往购买了更多的商品，反而是最有价值客户；除此之外，SLO/SLA也用于描述服务质量；

1.10.3 可维护性

对系统而言，开发阶段成本不是最大的，后续维护、缺陷修复、适配新功能、偿还技术债务等等成本更高；

可运维性： 运维更轻松
简单性： 简化复杂度；做好抽象，隐藏细节，对外提供干净/易懂的接口；如高级语言屏蔽此层寄存器/系统调用的复杂度；
可演变性： 易于改变

2. 数据复制

经过第一部分的讨论，我们在单容器上得到了一个可高效读写的存储引擎，但机器总会故障，如何保证在机器故障的情况下，服务对外提供的读写能力不受到影响？自然就是数据在多个容器上存储多份，待机器故障后，使用其他机器的数据对外提供服务。那如何保证不同机器上有多份数据，且它们是一致的就成为接下来要解决的问题。

如果数据一成不变，数据复制就很容易；挑战就在于处理那些持续更改的数据，即如何确保多副本之间的数据是一致的。

同步的方式主要有三种: 1. 主从复制; 2. 多主复制; 3. 无主复制各有优缺点，我们首先看主从复制，这也是最常见的

2.1 主从复制

写请求发送到主节点（北京)，主节点按序将数据更改作为复制日志或更改流发送给所有从节点；从节点将变更数据流应用到自身的存储引擎中，也就拥有了和主节点一致的数据；读请求也就可以请求从节点获取数据；

若客户端等待主节点将数据同步到所有从节点再响应客户端，这个耗时会比较久；而且强同步策略也会在任一从节点故障不能响应主节点的时候堵塞所有客户端的写操作

2.1.1 同步复制与异步复制

如上图，从节点1的复制是同步的，主节点等待从节点1完成写入变更之后才会响应客户端；从节点2的复制是异步的，主节点不等待从节点2的返回就会给用户响应；

同步复制的优点是，一旦向用户确认，则所有的从节点与主节点都是强一致的。即使主节点发生故障，仍可以在任一从节点中访问最新数据；缺点则是：任一从节点堵塞（崩溃/网络超时）则用户的写请求都将堵塞；

主从复制模式还经常配置为全异步模式。此时如果主节点故障，则所有尚未复制同步到从节点的写请求都将丢失。优点则是吞吐性能较高，因为不管从节点落后多少日志数据，主节点总是可以响应写请求；

我们折中一下，不管集群规模多大，我们配置一个同步的从节点，其他从节点为异步复制。若主节点故障，则将同步的从节点提升为主节点；若同步的从节点故障，则从异步节点中挑选一个作为同步节点；该模式也被称为半同步。

当需要新增加一个从节点提升容错能力，或者替换失败的节点，就需要增加从节点。但如何确保新添加的从节点与主节点数据一致呢？也就是从节点如何从“一无所知”追赶到拥有主节点的所有数据

如上图所示，当从节点向主节点请求数据同步的时候，主节点做两件事情，一个是产生一个数据快照（拥有所有的存量数据）；另一个是记录此刻开始发生的数据更改日志(同步开始后的增量数据)；从节点首先将数据快照应用到自身节点，然后将发起同步请求开始的主节点的数据更改日志（即快照时候的数据变更, 上图中的红色部分）应用到自身；日志同步流中的节点通常称之为 LSN( 日志序列号/ Log Sequence Number)

举个例子：在时间点 t5 从节点请求数据同步，此时主节点生成一个快照，包含 t0-t5的数据；同时，此时该从节点的写命令日志序列LSN=100；从节点将快照数据加载之后，会从 LSN: 100 处开始重放写命令日志序列；待重放完也就拥有了 t5 到此刻的增量数据，后面就是保持实时数据同步了。
不管主节点还是从节点都可能宕机，故障重启或者网络中断，在此情况下如何故障恢复也是一个挑战

从节点故障：追赶式恢复若从节点重启或者网络中断后恢复，因为有本地副本的复制日志，从节点知道故障前最后一次写入的LSN，则使用该LSN从主节点继续同步追赶

主节点失效：切换若主节点故障，则需要挑选某个从节点提升为主节点；客户端也需要更新，这样之后的写请求才会写到新的主节点；其他从节点也需要接受来自新主节点的数据变更。

自动切换的步骤通常如下:

确认主节点失效。一般都基于超时心跳来检测主节点是否还存活，可能是控制节点检测心跳，也可能是集群内部根据流言协议Gossip决定主节点是否存活；
选举新的主节点。可以通过控制节点决定谁当选为新的主节点，也可以通过集群内选举的方式；这是典型的共识算法
重新配置系统使新主节点生效。

主从节点切换也会有很多需要考虑的挑战：
1）若使用异步复制，且主从切换前，新的主节点没有收到原主节点的所有数据；则会发生数据丢失。若切换之后原主节点又加入到集群，又该如何做呢？
2）若发生脑裂，有两个节点都认为自己是主节点，怎么办呢？
3）如何设置合适的超时来检测主节点失效呢？太长会导致恢复时间过久；太短可能会导致不必要的切换

我们继续讨论主从复制的技术细节到底是如何工作的？也就是主节点的数据如何序列化成网络数据传输到从节点

复制和存储引擎可以使用不同的日志格式，这样复制日志就能从存储引擎内部分离。这种复制日志称为逻辑日志，以区分存储引擎的数据表示。比如行插入/更新/删除，复制日志中包含所有相关列的新值，从节点解析这些逻辑日志后应用到自身即可；Mysql的二进制日志binlog就使用该方式；这种方式称为基于行的逻辑日志复制；

对外部应用程序来说，逻辑日志格式更容易解析；因此通过接出复制日志，可是方便的将数据库数据同步到离线数仓中除了基于逻辑日志的复制外，还有基于语句的复制和**基于 WAL 日志的复制
**基于语句的复制主节点记录执行的所有写请求，并将该操作语句作为日志发送给从节点；类同于每个从节点都在执行来自客户端的请求；非首选方案；会存在不适用的场景: 1）非确定性函数的语句，如 Now() Rand()，不同副本会产生不同的值； 2）有副作用的语句，如触发器/用户自定义函数，会在不同副本有不同副作用
**
基于预写日志(WAL)传输**主节点除了将WAL日志写入磁盘之外，还会通过网络将其发送给主节点；缺点是日志描述的数据非常底层，如哪些磁盘块的哪些字节发生改变；不同版本的存储可能会有差异，无法进行滚动升级，只能停机升级；

2.1.2 复制滞后问题

使用数据多副本部署除了能够解决节点故障之外，还期待能解决扩展性（多节点处理更多请求）和低延迟（副本部署在离用户更近的位置）。一个很现实的问题就是从节点读取到的信息不是最新的，也就是复制滞后问题。复制滞后可能带来以下问题:

读不到自己的写

如上图，用户查询时可能会请求到复制滞后的 从节点2 上；用户会觉得自己的写操作丢失了，实际上并没有；

这种情况下，我们需要实现“读写一致性”，方法有: 1）有必要则读主节点，比如：网络社交首页只有所有者能编辑，因此从主节点读取自己的首页配置，从节点读取其他人的配置；能够保证作者更新信息后及时看到。 2）客户端记录最近更新的时间戳，附带在请求中，如果从节点不够新，则将请求转发到另一个符合要求的节点来处理

单调读（不可重复读）

如上图，用户2345首次访问了从节点1看到了最新的内容，但是第二次访问了从节点2，但此时会读到旧数据；

单调读是一个比强一致性弱，但比最终一致性强的保证，单调读保证，如果某个用户依次进行多次读取，绝不会看到回滚现象

实现单调读的一种方式是：确保每个用户总是从固定的同一副本执行读取，如使用用户ID的哈希方法来决定副本读取；

分区数据时序错误

在观察者看来，答案（通常约10s, poons 先生）发生在问题（Cake夫人，您能看到多远的未来？)之前。

分区数据经常会遇到这个问题，问题和答案会保存在不同的分区中，不同分区的复制进度是不同的

需要确保任何具有因果关系的写入都交给同一个分区来解决。

2.2 多主节点复制

上面介绍的主从复制最为常见，但是在不考虑分片的情况下也有一个明显的缺点：系统只有一个主节点，所有的写入都要经由主节点。主节点的延迟会影响所有的写入操作。因此扩展引申出多主节点的复制。

2.2.1 多主节点复制的应用场景

1.多数据中心：在每个数据中心都配置主节点，数据中心内部仍是主从复制，跨数据中心则由主节点负责数据中心间的数据交换和更新。写请求不再需要跨地域执行，并且也能容忍整个数据中心失效的故障；

多主节点复制最大的问题就是冲突解决：不同的数据中心可能会同时修改相同的数据

2.离线客户端操作：比如日历或者印象笔记等应用，无论设备是否联网都是允许工作的，且同一个账户在多设备都可以登录。因此需要在下次联网的时候完成数据同步；从结构层面来讲，也等同于数据中心之间的多主复制，每个设备就是一个数据中心。

3.协作编辑：腾讯文档/Google Docs等允许多人同时编辑，每一行/单元格可以看作一个key，和多主复制也有类似之处。

2.2.2 处理写冲突

多主复制最大的挑战就是解决写冲突，如上图，跨地域的用户1 和用户2 同时修改了title，主节点1收到主节点2同步过来的请求时发现是冲突的，必需有一种冲突解决方案决定title最终是改为B还是改为C。

避免冲突

你可能想不到，处理冲突最理想的策略就是：避免发生冲突 。应用层保证对特定记录的写请求总是路由到同一个主节点，就不会发生写冲突。比如我们的服务部署了天津/深圳两个地域，两个地域是多主节点复制，则每一个用户只会路由到天津或者深圳其中一个地域，不会存在写冲突；从用户的角度开看，基本等价于主从复制模型。

所有副本数据收敛于一致状态

上述示例中，因为 title从A->B和A->C是并发的，不存在hapen-before关系，因此不管最终主节点1 和主节点2 的title是变成B还是变成C都是可以的，重要的是两个主节点对title存储的值要一致。

实现收敛于一致的可能方式:

每个写请求分配唯一的ID(时间戳/随机数/UUID)，每个副本仅保留最高ID作为胜利者写入，其他写入请求则丢弃；
为每个副本分配一个序号，序号大的副本写入优先级高于低序号的副本；
将冲突的结果都记录下来，依靠应用层（或用户）来决策。如上例中，将B/C都记录下来，让用户决策最终使用哪个标题；

方案1/方案2都可能造成写入数据丢失，方案1中若是基于时间戳，也被称为最后写入者获胜，后面再讨论

2.2.3 多主复制的拓扑结构

若存在多主节点，对其中一个节点的写入如何扩散到所有的主节点，通常有三种方式：

环形拓扑和星形拓扑中因为要避免无限循环写入，因此复制日志中需要记录已通过的节点标识，若节点收到了包含自身标识的数据更改请求，说明已经处理过，忽略即可；同时这两种拓扑类型若有节点故障也会导致同步中断；全链路拓扑（上图C）存在的最大问题是部分网络链路比其他链路更快的情况，如下图:

客户端B在主节点2上的操作早于客户端A在主节点2上的操作，就导致了更新操作早于插入操作；可以使用版本向量的技术来解决；

使用多主节点复制的数据库时，上述提到的问题都值得关注，看该数据库是如何解决这些问题的，方便我们技术评估和调研

2.3 无主节点复制

除了2.1和2.2中讨论的 主从复制 和 多主复制，还有一种副本同步的方式是无主复制

该模式下不再区分主节点和从节点，允许任何副本直接接受来自客户端的写请求。

用户1234 作为客户端写入时，将写请求发送到所有的副本，即使副本3宕机，客户端仍认为写入成功（多数节点返回成功），用户2345 读取的时候也会将读请求发送给所有节点，每个节点都会返回当前值和版本，客户端可以获取到最新的值(version=7)，并修复副本3的值（这一步也称为读修复）；

除了读修复之外，还有另一种方案，后台进程不断查找副本之间的数据差异，将缺少的数据完成修复，称之为反熵过程

2.3.1 读写quorum

客户端写入/读取都需要跟所有副本交互，那写入/读取多少多少个副本就认为是成功呢？

假定有n个副本，w表示写成功的副本数量，r表示读取成功的副本数量，只要满足w + r > n，则读取的副本节点中一定包含新值，因为此时参与读写的副本之间一定是有交集的；

此限制也不能完全保证结果正确，假定一种场景：1）写操作和读操作同时发生，写操作已经在一部分副本上完成，此时读请求仍有可能返回旧值；2）某些副本写入成功，部分写入失败，则成功的副本并不会回滚；读请求可能返回新值，也可能返回旧值

2.3.2 并发写的一致性

如果每个节点接收到请求就直接执行，所有节点最终很难达成一致；如上图，因为每个节点执行命令的时序不同，最终结果也是错误的；

最后写入者获胜

只要我们有办法判定哪个写入是最新的，那所有副本最终都会收敛到相同的值；我们可以针对每个写请求附加一个时间戳（客户端的本地时间），节点仅存储最新/最大时间戳的请求保存即可；这是cassandra仅有的冲突解决方案；

更多LWW-last write wins最终写入者获胜的信息可参考：链接

版本矢量

每个副本和每个主键均定义一个版本号，每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本看到的版本号。通过这些信息来决定要覆盖/保留哪些并发值。

3. 数据分片

通过第二部分的讨论，我们已经能够在多个容器通过复制技术保存数据的多份副本，在宕机/降低读延迟和读QPS扩展性上有了提升；但现在仍面临一个问题就是：数据在一台机器上存不下怎么办？
面对海量数据和非常高的查询压力，只是复制技术还不够，我们还需要将数据拆分成分片，用每个分片去承载部分数据和部分请求；对分片不同系统有不同的称呼，Shard、 Region、 Tablet、 vnode 、vBuciet、 Partition等都是对分片的领域特定称呼

3.1 键-值数据的分片

如上图，数据被分成了 4 个分片，每个分片有 3 个副本，共 12 副本，其中每个机器存储 3 副本，共存储在 4 台机器上；

这里就会引出第一个问题：全量数据如何均分到 4 个分片上？

3.1.1 基于关键字区间分片

如上图，我们按照“键”的区间来分区，字典序介于Bayey - Ceanothus的存储到分片2，介于Trudeau - Zywiec的存储在12号分片；为避免数据倾斜，关键字分区并不要求均匀分布，根据各首字母记录条数可以动态调配分区管理；

但有一个问题就是热点数据会导致某一分片承载的读写请求特别多，其中一种方案就是在分区键前追加其他信息让数据分散到多个分片，查询时也需要并发查询；

3.1.2 基于键的哈希值分片

如上图，将时间戳计算哈希值（此处使用MD5）取膜后映射到不同分片管理的分区中（分片0管理结果位于0-8192的键)。

3.2 分片再平衡

随着业务发展，数据量可能会越来越多，即使数据量不增多，查询压力也能越来越大；因此需要扩容更多的机器承载请求，即如何将数据从一个机器的分片移动到另一个机器的其他分片；

针对分片的再平衡，一般要满足:

再平衡之后，负载/数据存储/读写请求等指标在集群范围内更均匀的分布
再平衡执行过程中，数据库正常提供读写能力

再平衡一定伴随着数据在不同分片之间的迁移，需要迁移到的目标分片是新增的分片还是已有分片就有比较大的区别；

3.2.1 固定数量的分片

最简单的方案：创建远超实际节点数的分片数量，为每个节点分配多个分片；需要迁移时就从现有机器上挑选分片移动到新机器上即可；如上图新增节点4之后，将p4、p9、p14、p19 这 4 个分片迁移到新节点中；

我们可以将机器 硬件配置/热点分区 考虑进来，硬件配置高的机器多分配一些分片，热点访问量比较高的分区所在机器少分配一些分片；
分片的大小应该“恰到好处”：若数据量非常大，则在数据迁移时候成本很高，数据量太少就会产生太多的开销；
Riak ES Couchbase Redis等都使用该方案

3.2.2 动态分片

初始仅创建少量分片，当分片的数据增长超过一定阈值时（如10GB），就会拆分成2个分片，每个分片承担一半的数据；反之，分片也会合并；每个分片只会分配给一个机器，但是一个机器可以承载多个分片数据；

MongoDB HBase等使用该方案

3.2.3 按节点比例分区

动态分片的分片数量和整体数据集的大小成正相关；固定分片的每个分片大小和整体数据集大小成正相关；他们都与节点数没有关系；Cassandra则采用了第三种方式，使分片数和集群节点数成正相关；即每个机器有固定数量的分片；

节点数不变：分片大小和整体数据集大小正相关
节点数增加：分片内的数据会变的更小

现在我们解决了数据分片和分片再平衡的问题，每个分片都会有主从节点；分片数量和每个分片内主从节点的数量和角色都会变化，这里就有了一个新的问题：客户端如何知晓该把请求发往哪个分片的哪个节点呢？

3.3 请求路由

分片数据已经就绪，客户端应该把请求发送到哪个机器上呢？尤其是若发生了分片动态再平衡，分片与节点的关系也会随之变化；这本质上是一个服务发现问题；

如上所示，通常有三种方式：1）节点转发；2）代理层转发；3)客户端缓存分区关系。

3.3.1 节点转发

客户端连接任意节点，若节点恰好该数据则直接返回，若节点没有数据，则将请求转发到合适的节点，并将结果返回给客户端

3.3.2 代理转发 (proxy)

在客户端和数据库之间增加一个代理层（Proxy）, Proxy记录分片和节点机器的映射关系，负责请求的转发和响应；Proxy本身不处理请求，只是一个感知分片的负载均衡器。

该方案采用较多，一来客户端不需要有复杂的逻辑，Proxy可屏蔽分片/节点的动态变化；再者，处理类似于Redis中的 MGet 等涉及多个键的命令时，Proxy可以完成分发&合并结果的工作；最后，Proxy还可以处理"迁移中"的数据，如一个分片正在从一台机器迁移到另一台机器，命中该分片的请求该如何处理？

3.3.3 客户端缓存分区关系

客户端感知分区和节点的分配关系，客户端可直接联系到目标节点，不需要任何Proxy

3.3.4 分片和节点的映射关系如何维护？

在使用代理转发的选择下，需要去存储并感知分片和节点IP的映射关系：

一般采用独立的协调服务(zookeeper/ETCD)跟踪集群范围内的元数据变化。如上图，节点分片的动态再平衡（可能是人工通过控制节点触发，也可能是自动再平衡）会同步写到 Zookeeper中，Proxy通过watch感知到节点变化之后会将后续请求转发到正确的节点；

关键字区间会映射到不同的分区，多个分区会映射到同一个节点中，图例中仅展示了主节点；

经过上面所有的讨论，我们可以得到如下这个相对通用的分布式存储架构：

当然，还有事物、一致性保证、共识算法，异常处理等等很多问题我们并没有讨论；也会有遗漏和错误，烦请指正～

参考资料:

《数据密集型应用系统设计》

《数据库系统内幕》

作者：腾讯程序员
文章来源：腾讯技术工程

推荐阅读

更多腾讯AI相关技术干货，请关注专栏腾讯技术工程 欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。