早上起来听一个数据库技术的直播论坛，讲师频繁提到一个词：Compaction。这个词以前在了解LevelDB的时候，也略有了解，不过也仅限于简单了解，今天就趁机对此做一个梳理。
说明：网上其实对此已经有了非常多的相关文章，自己今天其实也就是一个梳理，让自己能有一个比较好的理解。
为什么需要Compaction？
附录的参考1已经说的比较清楚了，对于数据库，通常情况下，数据都不可能完全保存在昂贵的内存里，因此持久化是必须的。但是怎么持久化就是一个大问题了，因为你需要随时平衡好的读写性能。
传统数据库大都是以B+树之类的算法为基础架构进行设计，不过很多新型的数据库（如HBase, LevelDB, RocksDB等）都以LSM树为基础进行设计。
LSM树的核心特点是利用顺序写来提高写性能，但因为分层的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。
它的大概结构是这样的：
上图的Level 0到Level 4是5个层级的持久化文件集合，于是我们对为什么需要Compaction还没解决，就引入以一个新的问题：
为什么需要分成这么多个Level的文件集合？
要讲清楚这个问题，还不是那么简单，带着这个问题，午休都没睡好。
MyISAM存储引擎：
不妨尝试说说这个问题，先从最简单的持久化到单个文件开始，用过早期的MySQL应该都知道，早期常用的一个存储引擎叫MyISAM，在物理层面其实就是将表结构，索引和数据分开存储到独立的一个文件上。
这个设计上很简单，但是性能上却不太好，最大的一个问题就是表锁问题，这样的并发性能注定是很差的，所以这个存储引擎基本已经放弃治疗了。（并不是说把数据单独存到一个文件上就会导致表锁，而是MyISAM这个引擎的实现所导致的）
InnoDB存储引擎：
这是目前MySQL上最常见的存储引擎，在物理存储上它会将所有数据和索引存储在一个单一的文件（表空间）上（抛开那些日志文件等之类的不说），不过这个单一的文件却有很复杂的结构设计。若干的行会组成一个页，若干的页会组成区（extent），若干的区组成段（segment），若干的段最后组成整个的表空间，相当于有了一个层次化的目录，如下图：
有这样一个目录，在查询上应该也是有优势的，传统的数据库应该都是类似的设计。而在实现上，InnoDB是支持行级锁的，这对比MyISAM也是大大的优势。
不过，相对于MyISAM这种过时的引擎有优势还是不行的，在当今的大数据时代，还是有问题的：
怎么做分布式？MySQL确实可以做多节点，主从分离等，但这并不是真正的分布式，而是类似是每个节点都是一个镜像，每个节点上的数据都是同步的，因为InnoDB从设计上就只能做到这样了。
设计和实现上很复杂，因为数据本身并不是均匀分布的，怎么避免某些页变得特别大，从而影响性能，就是一个很难处理的问题。（从某种意义上说，这应该也可以说是compaction吧）
冷热数据也比较难区分。目录是一个静态的层级结构，一层一层就能查到相应的数据，对于数据来说，地位都是平等的，没法区分冷热数据，只能通过缓冲区的大小来控制缓存的命中率，实现一种类似热数据的功能。
不过，到此，LSM架构已经呼之欲出了。
LSM架构
前面已经有一个示意图，这里重复一下：
上图的每个层级的Level都会包含包含多个文件（绿色框），它的流程大概是数据会先写到内存上，然后刷到Level 0的持久化文件上，而Level 0的文件达到某些条件就会刷到Level 1上，以此类推。这样的设计是比较灵活的，我理解这里的优势：
分布式的可能性更容易了：都是不同的文件分布到多个节点上显然更容易了；
通过策略的控制，应该是有机会让热数据尽量保留在低Level的层级上，例如Level 0，Level 1等，这样查询显然更加高效；
结合不同的存储硬件，可以实现相对低的成本来达到更高的性能。对于硬件，通常有内存，固态硬盘，机械硬盘，而它们的读写性能差距也是非常大的。于是我们不同的Level的数据就有可能使用不同的存储介质，如下图：
如上图，例如我们可以将Level 1，Level 2，Level 3存储在固态硬盘上，而Level 4及更高层级的数据存储到机械硬盘上，如果我们的策略能保证热数据大都落在前面三个层级上的话，我们的性能将会大大提升。
这就是为什么需要这么多个Level的文件的原因了。而这会直接导致需要Compaction，因为不同层级的Level需要做数据平衡。
Compaction的大致流程
Compaction的大致流程其实主要包含两个：
一个是怎么将内存的数据刷到Level 0上，这个流程叫：Minor Compaction
另一个是怎么将数据从Level i平衡到Level i+1，这个流程叫：Major Compaction
Minor Compaction
这个流程其实是很简单的，如下图:
其实就是直接将内存数据刷到Level 0的一个文件上。这里得先说一下各个Level的特点：
Level 0的各个文件的key的范围是允许有重叠的，如上图，第一个文件上存储了2-100的，第二个文件存储了15-100的，第三个文件存储了0-50的，第四个存储了100-300。例如key=30的记录，在level 0这个层级上，就可能出现在前三个文件上，看起来会影响查询效率，但是因为Level 0的文件是比较小的，所以效率应该还是很高的。
其他Level层级内的文件是严格排序的，例如在Level 1这个层级，从0-100，101-150，150-200，201-300，这是严格排序的，一个key只可能会出现在其中的一个文件。
总体上，要查找key=30的记录，会先在Level 0的相关文件进行查询，如果没查到，就查Level 1的第一个文件，如果还是没有查到就查Level 2的第一个文件，以此类推就可以了。
好了，查询介绍完了，回到Minor Compaction，新的数据直接就刷到了Level 0的第四个文件上，它的key的范围是100-300，就是这么简单。
Major Compaction
从Level i到Level i+1的流程示意图：
如上图，假如我们发现Level 0这个层级的15-80这个文件太大了，触发了Compaction，它的key的范围是15到80，这时需要先将Level 0和Level 1这两个层级的文件中，key范围有交集的文件都找出来，于是在Level 0中找到了3个，在Level 1中找到了一个，然后对这4个文件的记录进行归并排序，生成新的Level 1中的两个文件0-50和51-100。
其他层级上的Major Compaction也是类似的。简单理解是这样，但是在实现上应该还是很复杂的。
PS：
本来只是先简单做一个梳理，但是写起来，发现要说清楚并不简单。
附录
Compaction：https://leveldb-handbook.readthedocs.io/zh/latest/compaction.html
Leveled Compaction：https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
截图大都来自上面两个页面。
