本文为《数据密集型应用系统设计》第三章第一节的读后感

数据需要持久化，将内存中的状态落到磁盘上，就需要使用存储引擎。最简单的存储引擎就是一个数据文件呗，每次写入就写到文件上，而读操作就去数据文件上找数据。但是数据量大了，把所有文件找一遍就不靠谱了，需要加索引。我们就先从最简单的索引，hashmap 说起。

从 hashmap 说起

hashmap 就是一种特别简单的索引，其具有非常好的读写性能，但是有一个缺点，需要全部加载到内存中。虽然我们也可以将 hashmap 序列化后落盘，但是其实现查询功能还是必须整个加载。在数据量比较大的情况下，这显然是个大问题。

Riak 中的默认存储引擎 Bitcask 就是采用的 hashmap 作为索引。Bitcask 将数据加载到文件中，并在内存中维护 hashmap，记录每个 key 对于的 value 在文件中的偏移。这样每次查找的时候，只需要按照 Key 找到数据所在的文件和偏移，就能找到数据了。这种方式其实非常常见，文件系统很多都是这么干的。

当然这只是一个粗略的解释，实际的实现远比这复杂。

比如，都写到一个文件里，那如果这个文件坏了怎么办，如果并发很高怎么办？所以，应该拆成多个段文件。

比如，如果要更新数据怎么办？是直接回到原来的地方去更新么？那就失去了顺序写的巨大性能优势了。更好的方式是先一股脑追加写，不但可以顺序写，这对崩溃恢复也更友好（因为可能更新一半的时候挂掉）。

但是追加写不是很浪费空间么？这就需要做事后合并了。（合并的时候显然还是要更新索引的，并且合并也导致了一定的「写放大」，写放大就是一次数据库写导致了多次的磁盘写）

如果要删除数据怎么办？其实和更新类似，应该先写在原来的数据上打一个墓碑标志（删除标志），然后在合并数据文件的时候，将其跳过。

LSM-Tree (SSTable)

如果我们要解决 hashmap 索引必须加载到内存中的问题，我们需要找到一种基于磁盘的索引机制。

首先我们来看 SSTable (sorted string table)，其要求文件上的数据的 key 要有序，并且在合并文件中，相同的键只能有一条记录。有序性带来一个很大的好处，我们只需要很少量的索引，就可以快速确定某个文件里面有没有待查找的键的对应的值，以及如果有的话在什么区间了。

但是写入磁盘这种事情，要做到在一个文件上有序是很困难的，因为写入会以任意顺序发生。所以顺序还是要在内存中维护。一种常见的做法是，写入时现在内存中维护一个有序结构（比如红黑树）。当红黑树比较大了以后，将其写入磁盘。

很明显，这种做法存在一个问题，就是如果在写入磁盘前崩溃，内存里的数据就丢了。解决这个问题的方法通常是增加一个 WAL 文件，即先将记录写到磁盘上（这里是顺序写），在机器从崩溃中恢复的时候用于恢复数据。

LevelDB 和 RocksDB 正是使用了这种算法，类似的还有 Cassandra 和 HBase。

由于最初这个算法被称为 (Log-Structured Merge Tree)，后来这种基于合并和压缩排序文件的存储引擎就被称为 LSM 存储引擎。

我们可以想象一下 LSM 的最坏场景，查找一个不存在的键，这几乎就是灾难，因为几乎要遍历所有的数据文件（或者说数据的索引文件）。一个解决方案是用布隆过滤器来判断数据是否存在。布隆过滤器的特点是，如果存在则不会误判，如果不存在则可能误判，即存在假阳性错误，这不会导致数据读取错误，只会在假阳性发生时带来性能上的损失，还好，假阳性不常发生。

BTree

事实上，BTree 才是数据库所有的真正王者，几乎是关系数据库索引的标准实现。

LSM Tree 是日志结构的，它将磁盘看成可变大小的块，每个块为几兆或更大，并始终按照顺序入段。

而 BTree 则将磁盘看成固定大小的页，页是读写的最小单元。可以说，这种设计更接近硬件。一个页面指向其他的一些页面，并形成一个高扇出（出度高）的树状结构。

由于数据是按块存储的，BTree 在新增数据或删除数据的时候，很可能会出现一个页面放不下，或者多个页面数据稀疏的情况，这时候就会发生「页分裂」和「页合并」操作。

LSM Tree vs BTree

LSM-Tree 通常对于写入更友好，而 BTree 则对于读应用更友好。

BTree 在写入数据的时候，需要写入 WAL 和页，并且每次都要写整个页，还可能发生页分裂。而 LSTM-Tree 不是面向页的操作，其能更好的利用顺序写的优势，写入通常更快。

面对精确的查询需求，BTree 往往有更大的优势。不仅如此，在需要实现事务的场景下，数据库采用 BTree 也会更方便，因为可以直接在树上实现锁。而 LSM-Tree 的结构，要想实现锁，可能还得新增其他数据结构。