ArangoDB-存储引擎分析

当今很多主流DB都使用了 LSM Tree 的存储模型，包括 LevelDB，HBase，Google BigTable，Cassandra，InfluxDB 等。

ArangoDB果断采用了RocksDB做的底层存储引擎，RocksDB存储模型使用的是LSM-Tree数据结构，老规矩先上图。

存储模型
WAL（Write Ahead Log）

在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 WAL 文件中，之后插入到内存中的 MemTable 中。这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。当程序挂掉重启时，可以从 WAL 文件中重新恢复内存中的 MemTable。WAL文件结构如下图，按照写入的顺序来存储变长的K-V，按照固定长度来分组存储（可能一个K-V跨多个分组）的目的是便于读取。

MemTable

MemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构，通常用 SkipList 来实现。MemTable 提供了 k-v 数据的写入、删除以及读取的操作接口。其内部将 k-v 对按照 key 值有序存储，这样方便之后快速序列化到 SSTable 文件中，仍然保持数据的有序性。

Immutable Memtable

顾名思义，Immutable Memtable 就是在内存中只读的 MemTable，由于内存是有限的，通常我们会设置一个阀值，当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

（跳表结构可以简单理解为有序支持近似二分查找的时间复杂度为log2(N)）

SSTable

SSTable 就是 MemTable 中的数据在磁盘上的有序存储，其内部数据是根据 key 从小到大排列的。通常为了加快查找的速度，需要在 SSTable 中加入数据索引，可以快读定位到指定的 k-v 数据。

SSTable 通常采用的分级的结构，例如 LevelDB 中就是如此。MemTable 中的数据达到指定阀值后会在 Level 0 层创建一个新的 SSTable。当某个 Level 下的文件数超过一定值后，就会将这个 Level 下的一个 SSTable 文件和更高一级的 SSTable 文件合并，由于 SSTable 中的 k-v 数据都是有序的，相当于是一个多路归并排序，所以合并操作相当快速，终生成一个新的 SSTable 文件，将旧的文件删除，这样就完成了一次合并过程。

（上图为按照多块来存储的结构。每块的K-V都是有序的，多块也是有序的）

随着K-V的写入，会生成很多的SST文件，这部分文件需要被合并到一起。从而降低打开文件数量，并且移除已经不存在的记录。通常可以 配置两种方式，通用合并（下图左侧）与level合并（右侧）

Compaction

当数据不断从 Immutable Memtable 序列化到磁盘上的 SSTable 文件中时，SSTable 文件的数量就不断增加，而且其中可能有很多更新和删除操作并不立即对文件进行操作，而只是存储一个操作记录，这就造成了整个 LSM Tree 中可能有大量相同 key 值的数据，占据了磁盘空间。为了节省磁盘空间占用，控制 SSTable 文件数量，需要将多个 SSTable 文件进行合并，生成一个新的 SSTable 文件。比如说有 5 个 10 行的 SSTable 文件要合并成 1 个 50 行的 SSTable 文件，但是其中可能有 key 值重复的数据，我们只需要保留其中新的一条即可，这个时候新生成的 SSTable 可能只有 40 行记录。

读取

LSM Tree 的读取效率并不高，当需要读取指定 key 的数据时，先在内存中的 MemTable 和 Immutable MemTable 中查找，如果没有找到，则继续从 Level 0 层开始，找不到就从更高层的 SSTable 文件中查找，如果查找失败，说明整个 LSM Tree 中都不存在这个 key 的数据。如果中间在任何一个地方找到这个 key 的数据，那么按照这个路径找到的数据都是新的。

在每一层的 SSTable 文件的 key 值范围是不重复的，所以只需要查找其中一个 SSTable 文件即可确定指定 key 的数据是否存在于这一层中。Level 0 层比较特殊，因为数据是 Immutable MemTable 直接写入此层的，所以 Level 0 层的 SSTable 文件的 key 值范围可能存在重复，查找数据时有可能需要查找多个文件。

优化读取

因为这样的读取效率非常差，通常会进行一些优化，例如 LevelDB 中的 Mainfest 文件，这个文件记录了 SSTable 文件的一些关键信息，例如 Level 层数，文件名，小 key 值，大 key 值等，这个文件通常不会太大，可以放入内存中，可以帮助快速定位到要查询的 SSTable 文件，避免频繁读取。

小结
LSM Tree 的思想非常实用，将随机写转换为顺序写来大幅提高写入操作的性能，但是牺牲了部分读的性能。总的来说就是通过将大量的随机写转换为顺序写，从而极大地提升了数据写入的性能，虽然与此同时牺牲了部分读的性能。只适合存储 key 值有序且写入大于读取的数据，或者读取操作通常是 key 值连续的数据。

所有记录在业务上是有序的，对key的查询其实会执行类似二分查找。
持久化是通过写入有序文件来实现的。高性能的写入是通过先写入内存结构来保证的（写满的内存结构刷到持久化文件）。
提供了level机制对数据做分层，优先查询新写入的level来优化查询性能。
问题
write-ahead logs，预写日志；分布式很常见的WAL机制，为了提升写入性能，一定是先写缓存后刷磁盘的，不会直接写磁盘的，那样性能会非常低，但先写内存后写磁盘会带来一个问题，一旦机器挂掉了，内存数据没有刷到磁盘中，那这部分数据就会丢失。因此大部分分布式系统，比如：HBase、Elasticsearch、Dgraph等都是数据写内存之前，先预写日志，日志会实时刷到磁盘上，然后再将数据写内存，一旦内存中数据丢失了，可以通过磁盘上的日志回放这些数据，从而保证高可用性。

思考
ArangoDB之所以支持的索引花样多一些，其中很大的原因是来自于底层数据模型的支持。那么我们如何基于底层的数据模型，来映射到DB给用户开放的API层的写入机制和查询索引呢：）感兴趣的同学可在评论区谈谈自己的观点。