前言
Cassandra是一款NoSQL分布式数据库，采用LSM Tree架构。众所周知，LSM有两个重要过程：数据顺序刷入磁盘生成数据文件（SSTable）和 数据文件合并（Compaction）。今天本文主要说一个Compaction过程中的优化。
数据文件合并（Compaction）
首先我们要明白Compaction这个过程到底要做什么事，再来看如何优化。我们先从数据文件（SSTable）说起。
SSTable: Sorted String Table
这个词源自Google BigTable论文，是一个不可修改的数据文件。最初数据来自于用户写入，并且缓存在内存中。当缓存满的时候，会将缓存中的数据刷入磁盘，也就生成了SSTable文件。刷入磁盘的SSTable里的数据是排好序的。比如，用户写入[1, 0, 2, 4] 这么4条数据，最后刷入磁盘，这4条数据在SSTable里的排列是这样的[0, 1, 2, 4]。
通过写缓存，可以利用磁盘顺序写性能更好的特点，尤其是机械盘。查询过程也很简单，因为数据排好序，只要二分搜索即可。
为什么要做Compaction
随着数据不断写入，缓存不断刷入磁盘生成SSTable的时候，我们会拥有很多SSTable。这时候会有什么问题呢？可以试想一下下面这个场景：
- 用户先写入
[1, 3, 8, 2]，刷入磁盘生成SSTable0:[1, 2, 3, 8] - 用户再写入
[0, 3, 7, 6]，刷入磁盘生成SSTable1:[0, 3, 6, 7]
这时候如果要查询3，不得不访问2个文件。因为2个文件都包含了3，得确定哪个3是最新的。更恶心的情况是，用户继续写入[0, 4, 5, 9]，虽然没有3，但是因为这个0~9这个范围包含了3，你任然需要搜索这个文件，确定有没有你要的数据（这种落空的情况可以通过Bloom filter优化）。
如果SSTable文件很多，查询效率就会显著下降。那么解决这个问题，就是做Compaction。将SSTable0和SSTable1合并后，我们能得到[0, 1, 2, 3, 6, 7, 8]，一个全新的SSTable，后续查询只要搜索这个新的SSTable文件即可。
这就是Compaction主要的作用，当然Compaction过程中还有一个重要任务是清理过期或者被删除的数据。
简单抽象一下Compaction过程：多个有序链表去重合并
如何合并多个有序链表
相信很多同学面试也遇到过这个问题，很直接的想法就是用一个优先队列解决。Java中是PriorityQueue这个类，它的实现就是一个小根堆。代码也很好实现：
public List<Integer> doCompaction(Iterator<Integer>[] sstables) {
LinkedList<Integer> result = new LinkedList<>();
Integer[] topElement = new Integer[sstables.length];
PriorityQueue<Integer> heap = new PriorityQueue<>(
(idx1, idx2) -> topElement[idx1] - topElement[idx2]
);
// 初始化
for (int i = 0; i < sstables.length; i++) {
if (sstables[i].hasNext()) {
topElement[i] = sstables[i].next();
heap.add(i);
}
}
while (!heap.isEmpty()) {
int sstableIdx = heap.poll(); // 最小元素出队
// 去重
if (result.isEmpty() || result.getLast() < topElement[sstableIdx]) {
result.add(topElement[sstableIdx]);
} else {
assert result.getLast() == topElement[sstableIdx];
}
if (sstables[sstableIdx].hasNext()) {
topElement[sstableIdx] = sstables[sstableIdx].next();
heap.add(sstableIdx); // 新元素入队
}
}
return result;
}这个复杂度是O(N·logM), N是总共的元素个数，M是有序链表数量。这个实现方法要比直接连一起排序快，直接排序是O(N·logN)。显然N>=M，所以前者更快。
优化1
上述方法看起来没有什么大问题，Cassandra之前一些版本也是这么实现的。但是仔细分析这个过程，会发现有一些不必要的开销。
首先每个元素都会经历poll和add两个过程，这两个过程的开销都是O(logM)。作为一个通用的PriorityQueue，poll和add之后都要保持堆的结构特性，所有要做下滤（shift down）和上滤（shift up），这两个操作都是O(logM)。poll之后，因为堆顶缺失，会将最后一个元素放到堆顶做一次下滤。add元素则直接放到堆尾，做一次上滤。
所以精确一点复杂度是O(2N·logM)。但是因为我们基本每次poll元素后都会再add一个元素，那么可以直接将新add的元素放入堆顶做一次下滤。这样就将原来 一次下滤&一次上滤 合成 一次下滤。这样理论上直接节省一半时间。
优化前过程：
优化后过程：
这个在SSTable数据基本不怎么重叠的情况下，效果更好。因为某个SSTable弹出的数据可能会一直处于堆顶，下滤只需要比较2次即可。
优化2
下滤调整元素的时候，每一层，需要做2次比较。先比较2个子节点谁最小，再把父节点和最小的比。
如果考虑上面说的那种情况，重叠比较少，某个SSTable一段连续的数据可能会一直最小，会处于堆顶，那么一直只需要2次比较就能确定堆顶元素。如果堆顶不是一个二叉，而是一个单链，那就只需要1次比较即可。所以Cassandra里的堆，是一个很短的有序单链 + 一个堆。这种情况还是挺常见的，经过一段时间的压缩后，尤其对于使用LeveledCompactionStrategy的场景来说。
最终堆形状如下：
优化3
引入一个equalParent变量，表示该元素是否和父节点相等。这样可以进一步节约一些比较次数，在某些情况下。比较是字节数组比较，所以还是有一定开销的，并不像文中抽象的问题那样，简单比较整数。
写在最后
为了营造一个开放的Cassandra技术交流环境，社区建立了微信公众号和钉钉群。为广大用户提供专业的技术分享及问答，定期开展专家技术直播，欢迎大家加入。另阿里云为广大开发者提供云上Cassandra资源，可用于动手实践：9.9元可使用三月（限首购）。
直达链接：https://www.aliyun.com/product/cds
