日志合并结构树(LSM)的原理与实现
对于日志合并结构树(Log-Structured Merge-Tree)的说明主要来自于 Patrick O'Neil等人在论文 《The Log-Structured Merge Tree》 中的介绍。 翻译参考： 分布式系统 The Log-Structured Merge-Tree(译) 基本概念 LSM树并不是树结构，而是由两个或更多的类树组件组成的集合。 组成部分 LSM树一般至少由两个部分组成： 一个较小的位于内存的组件，就是上图中的 C0 tree(or C0 component) 一个较大的位于磁盘的组件，就是上图中的 C1 tree((or C1 component) 尽管C1树常驻磁盘，但它的常被访问的磁盘页会被保留在内存中(如下图)，所以也可以看做是常驻内存里的。 读写操作 历史记录表的数据每生成一行新记录流程如下： 首先向顺序日志文件中写一条用于恢复这次插入行为的日志记录(WAL,write ahead log) 该行数据的索引被插入到常驻内存的 C0 树中 会适时地将这些C0树上的数据迁移到磁盘上的C1树中 每个索引的搜索过程都是先C0后C1 所以实质上在两个组成部分外还有一个组成部分，就是行为日志。 行为日志可以用来获取实际数据以及进行崩溃恢复。而 LSM中的L(log)指的就是这个部分。 C1树结构 上述C0树写入是无IO开销的，但是C0位于内存，成本远高于磁盘，这就需要有一种高效的刷盘方式到C1。 为了实现这个目的，在当C0树因插入操作而达到接近某个上限的阈值大小时，就会启动一个滚动合并(rolling merge)过程，来将某些连续的记录段从C0树中删除，并merge到磁盘上的C1树中。 C1树具有一个类似于B-树的目录结构，但是它是为顺序性的磁盘访问优化过的，所有的节点都是100%满的，同时为了有效利用磁盘， 做了以下优化: 在根节点之下的所有的单页节点都会被打包(pack)放到连续的多页块(multi-page block)上。对于 滚动合并 和较长的区间检索的情况将会使用 多页块 I/O，而在匹配性的查找中会使用单页节点以最小化缓存需求。对于根节点之外的节点使用256Kbytes的 多页块 大小，根节点根据定义通常都只是单个的页面。 滚动合并 滚动合并行为是一系列的合并步骤： 先读取包含C1树的叶节点的多页块，这会使...