1.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 可维护性

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

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