前言

学生时代基本没有什么太大的业务需求，无非就是打一些比赛和接点小单子，所以没有那么多好奇和探索的空间，对知识的接受仅仅是1就是1、2就是2。偶尔才会对一些技术细节感到好奇，例如HashMap的某参数为何是0.5？为何JVM要用三色标记不用两色标记等等？虽然这些问题刨根究底也能带来一些收获，但是和工作后遇到的问题相比，还是少了很多实用性。

另外发现自己还是缺失很多基础知识的体系梳理，例如在用MongoDB的发现，其只有redolog，并没有undolog，直接打破了很多八股选手的三观，和一些老员工讨论了很久，也没有个所以然。如果是专门研究数据库的哥们，可能觉得这只是个无聊的基础问题，但是对于没有深入研究数据库系统架构，只是简单会用、背了一些八股的人来说，这就是个很难解释的问题了。当时为了研究这个问题，甚至去重学了一遍CMU15445，最终得到了答案之后，才发现我的基础知识如此不扎实。

这些基础理论知识平时可能很难用到，然而在关键的数据库选型时期，作为一个合格的架构师的话，就需要深入了解其原理，分析数据库之间的差异，根据当前业务场景选择最优的数据库。

最近闲下来了，所以打算结合CMU15445、DDIA以及自己的理解，重新梳理一遍数据库整体的知识。

唠叨就此结束，不喜欢说废话，也不喜欢写废话。

最简单的数据库

这是DDIA书中给的一个例子，当年看的时候跳过了，其实非常有意义，毕竟再大再复杂的系统也是从一个小idea起步的。

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

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

解释一下：

$1 $2代表两个变量
">"在shell中代表重定向，会覆盖文件内容，">>"代表追加到下一行
"^$1,"代表过滤$1,开头的行
sed的-e指的是处理字符串，-f是处理文件。
sed的"s/^$1,//" 含义为：s/ x / y / => 替换x为y ，只替换一次。s / x /y /g => 全局替换。
tail -n 1 查到多行只取最后一行（想要多行取第一行可以用head -n 1）

所以这个最简单的数据库的执行流程为：

写操作
- 参数$1和$2分别作为Key和Value
- 把K、V整合成一个”K, V”字符串，作为一行，新的写入就另起一行
读操作
- 首先找到所有以“K，”开头的行
- 其次把“K，”替换成空，只保留V
- 最后，如果有多条匹配结果，那么取最后一条，也就是最新的数据

性能分析

写操作

顺序写，写性能拉满
读操作

寄，要遍历查找，性能非常拉胯

对于这样一个最简单的数据库而言，写性能不是特别要关注的地方，读操作才是最大的优化点，所以需要一些额外的空间、额外的数据结构来优化读操作。

所以索引的意义在于：

使用一些额外的数据结构加速读操作。

但是索引的缺陷在于：

写数据的时候，还得写索引。所以为了优化读，写性能也做出了部分牺牲。

散列索引

散列的用处在于：

生成一个散列表（其实就是一个map），key就是写操作写进来的key，value是实际value的首位地址。

有了这个额外的map，就能根据key直接去定位到value，读操作从而获得巨大优化，时间复杂度从n进化到1。

散列的大问题在于：

map必须放在内存中，坏消息是map只能随机写。好消息是内存中的随机写，在大部分场景下，也比磁盘中的顺序写快多了。
追加写文件会变得很大，避免大文件出现，需要分段 + 压缩 + 合并段。
1. 压缩。比如之前写过name=xxx了，后面又追加写了name=yyy，需要舍弃name=xxx，压缩空间。
2. 分段。单纯切分大文件。
3. 合并段。段里的内容压缩过，会越来越小，所以也要考虑段合并。

散列的小问题在于：

文件格式

CSV不够快，字符编码要转义，直接用二进制会好很多。
删除记录

删除的KV对需要做一个特殊标记，压缩的时候可以舍弃。
崩溃恢复

由于Map索引是在内存中，崩溃恢复需要遍历所有硬盘文件去二次生成，非常愚蠢，想象一下1T的数据，遍历生成Map得要多久，机房断电一次，恢复需要大半天，必然是不可接受的。
文件损坏

崩溃会导致写了一半的场景出现，需要加校验和。写之前计算校验和hash，崩溃恢复再去检测。
并发性能

读可以多线程，但是写只能单线程。
范围查询

范围查询性能巨差，比如我要找在100到105之间的所有v，那要遍历整个散列表，太蠢了！

SSTable

基于散列索引的优化思路

索引放在内存里必然是不可行的，数据库所在的容器，不管是正常重启、还是断电宕机，索引就会丢失，需要遍历所有数据重新生成，非常愚蠢。另外，数据无限增长，内存可能也会溢出。

所以索引肯定要想办法持久化。

既然在内存里都是随机写了，你写一个Map(散列)也是写，你写一个Tree也是写，那为什么不写Tree呢？

Tree这个数据结构大类中有一种叫有序树(Ordered Tree)，有序树包含了二叉搜索树、平衡树等，平衡树又包含了AVL树、红黑树、B树等等，那么多树可以用。以最简单的二叉搜索树为例。

假设每个节点的数字就是我们的key，前序遍历这棵树，就可以得到顺序的1 3 4 6 7 8 10 13 14，从而可以顺序写入磁盘，以最快的速度持久化这个索引树。数据已经是有序的话，那查找根本不需要n的时间复杂度。

SSTable索引工作流程

有了有序的索引，那么SSTable的设计就很简单了：

有数据写入的时候，先写到内存的Ordered Tree中。
内存的Tree肯定不可能无限写下去，到了一定阈值就要持久化了，持久化下来的这个文件可以叫做SSTable（Sorted String Table）文件。这个阈值一般设为4M、8M、16M等等（具体设为多少要结合实际的设计，用benchmark反复的测，测出一个最佳的值。另外，这个阈值之所以都是4的倍数，是考虑到硬盘和内存之间的4KB对齐）所以随着时间累积，数据段会越来越多。
有查询请求的时候，先去内存里的Tree查，内存里的Tree没有的话，就去最新的段里面查，最新的段没有，就去其次新的段里查。一直找到为止。
1. 当定位到某个段时，读出来的这堆数据已经是有序的了，随便二分就找到了。
后台异步起一个线程，定期压缩这些段，同理，如果段被压缩的很小，那还要定期合并。

为数不多的致命弱点

数据库崩溃这种问题，内存里Tree数据依然丢失，这时候搞一个日志，顺序写进去就行，先写日志，后写Tree。

业界实际使用

上述流程就是LevelDB和RocksDB的键值存储引擎的核心思想。这种类型的索引统称为日志结构合并树（Log Structure Merge Tree，LSM Tree）。LSM是一整套

LSM树的设计难点

如果key不存在，那要先遍历内存里的Tree，再去遍历所有的段，效率会很低。这时候可以用布隆过滤器优化。
数据被处理成了一个个SSTable，合并策略怎么设计？

B+Tree

~~B、B+这些传统的烂八股就不再提了。~~

LSM的思想是把所有数据拆成多个SSTable，一个SSTable就可以认为是一个B树。

B+树不做拆分，所有数据就组织在一个完整的树中，B+树的叶子节点是一个存储单位，一般也是4K的N倍，节点和节点之间用指针关联。

从二者的主要思想可以看出，LSM是顺序写，而B+树是随机写，因为B+树的叶子节点们在磁盘空间中是指针关联而非连续的，所以B+树的核心在于覆盖写。

说到覆盖写，就要说到固态硬盘和机械硬盘的区别。

机械硬盘的写操作大致原理是磁头移动+旋转盘移动，然后复写扇区，主打一个覆盖写，所以机械硬盘天然适配B+树。

固态硬盘的写操作大致原因是将数据块擦除又重写，多了一步擦除，主打一个顺序写，所以固态硬盘天然适配LSM。

所以现在的数据库越来越喜欢往LSM上靠，例如阿里的OceanBase等。

开发软件就像做数学题，业务需求是题目，硬件是可用条件，最好的设计总要绞尽脑汁将可用条件压榨到极致。

B+树和LSM树的对比

写性能

B+树从整体写流程上看，要先写到RedoLog中，再写入到B+树中，如果插入数量较多，还会触发多个Page的写。考虑到Page满了，还会触发页分裂，有页分裂就会有页合并，这些操作都是要上锁的，所以写操作进一步被拖累了。

LSM虽然没有以上问题，但是同样会有写放大的缺陷，因为SSTable需要反复的压缩和合并，本来一次写操作，可能会被放大成很多次。但是写放大毕竟出现不会太频繁，而且合并和压缩可以后台线程异步操作，也不用考虑往insertMany操作要不要像B+树那样往多个页面写，直接一把梭子写进SSTable就可以了，所以整体来说，LSM的写入性能是比B+强的。

空间碎片

B+会有碎片，因为他的最小存储单位是Page，一个Page4M、M、16M已经预分配好了，往往不可能全部刚好写满，必有碎片。

LSM树因为是顺序写入，所以数据是很紧凑的，即使出现了碎片，也会定期处理SSTable去除碎片。

可预测性

LSM树由于不定期的要进行压缩和合并，不可避免的会影响到正常的写操作，而且这些压+合是很难预测的。另外，如果写入量很高，压缩如果没有配置好，压缩速率跟不上写入速率，这样会导致SSTable线性增长，从而增大读操作的压力，因为读操作要遍历的SSTable变多了。

事务隔离的实现

在LSM中，一个Key可能会出现在多个SSTable中，事务隔离是依赖于给Key加锁的，而B+树一个Key只会存在于一个Page，对事务实现非常友好。

重学数据库（1）-索引

前言