探秘 Cassandra 数据文件合并优化-阿里云开发者社区

开发者社区> 中国Cassandra技术社区> 正文

探秘 Cassandra 数据文件合并优化

简介: 前言 Cassandra是一款NoSQL分布式数据库,采用LSM Tree架构。众所周知,LSM有两个重要过程:数据顺序刷入磁盘生成数据文件(SSTable)和 数据文件合并(Compaction)。

前言

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之前一些版本也是这么实现的。但是仔细分析这个过程,会发现有一些不必要的开销。
首先每个元素都会经历polladd两个过程,这两个过程的开销都是O(logM)。作为一个通用的PriorityQueue,poll和add之后都要保持堆的结构特性,所有要做下滤(shift down)和上滤(shift up),这两个操作都是O(logM)。poll之后,因为堆顶缺失,会将最后一个元素放到堆顶做一次下滤。add元素则直接放到堆尾,做一次上滤。

所以精确一点复杂度是O(2N·logM)。但是因为我们基本每次poll元素后都会再add一个元素,那么可以直接将新add的元素放入堆顶做一次下滤。这样就将原来 一次下滤&一次上滤 合成 一次下滤。这样理论上直接节省一半时间。

优化前过程:
image

优化后过程:
image

这个在SSTable数据基本不怎么重叠的情况下,效果更好。因为某个SSTable弹出的数据可能会一直处于堆顶,下滤只需要比较2次即可。

优化2

下滤调整元素的时候,每一层,需要做2次比较。先比较2个子节点谁最小,再把父节点和最小的比。
如果考虑上面说的那种情况,重叠比较少,某个SSTable一段连续的数据可能会一直最小,会处于堆顶,那么一直只需要2次比较就能确定堆顶元素。如果堆顶不是一个二叉,而是一个单链,那就只需要1次比较即可。所以Cassandra里的堆,是一个很短的有序单链 + 一个堆。这种情况还是挺常见的,经过一段时间的压缩后,尤其对于使用LeveledCompactionStrategy的场景来说。

最终堆形状如下:
image

优化3

引入一个equalParent变量,表示该元素是否和父节点相等。这样可以进一步节约一些比较次数,在某些情况下。比较是字节数组比较,所以还是有一定开销的,并不像文中抽象的问题那样,简单比较整数。


写在最后

为了营造一个开放的Cassandra技术交流环境,社区建立了微信公众号和钉钉群。为广大用户提供专业的技术分享及问答,定期开展专家技术直播,欢迎大家加入。另阿里云为广大开发者提供云上Cassandra资源,可用于动手实践:9.9元可使用三月(限首购)。
直达链接:https://www.aliyun.com/product/cds

image

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
中国Cassandra技术社区
使用钉钉扫一扫加入圈子
+ 订阅

Cassandra已有10年+的沉淀,基于Amazon DynamoDB的分布式设计和 Google Bigtable 的数据模型。具备诸多优异特性:采用分布式架构、无中心、支持多活、弹性可扩展、高可用、容错、一致性可调、提供类SQL查询语言CQL等。Cassandra为互联网业务而生,已在全球广大互联网公司有成熟应用,是目前最流行的宽表数据库。阿里云在2019年8月份全球首发云Cassandra服务。

官方博客
相关链接