探秘 Cassandra 数据文件合并优化

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
云原生多模数据库 Lindorm,多引擎 多规格 0-4节点
简介: 前言 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

相关文章
|
XML 缓存 运维
springboot注解(全)
springboot注解(全)
643 0
|
算法 Unix API
指数退避(Exponential backoff)在网络请求中的应用
## 一、背景 最近做云服务 API 测试项目的过程中,发现某些时候会大批量调用 API,从而导致限流的报错。在遇到这种报错时,传统的重试策略是每隔一段时间重试一次。但由于是固定的时间重试一次,重试时又会有大量的请求在同一时刻涌入,会不断地造成限流。 这让我回想起两年前在查阅[Celery Task 文档](http://docs.celeryproject.org/en/latest
12746 1
|
7月前
|
存储 前端开发 数据可视化
Grafana Loki,轻量级日志系统
本文介绍了基于Grafana、Loki和Alloy构建的轻量级日志系统。Loki是一个由Grafana Labs开发的日志聚合系统,具备高可用性和多租户支持,专注于日志而非指标,通过标签索引而非内容索引实现高效存储。Alloy则是用于收集和转发日志至Loki的强大工具。文章详细描述了系统的架构、组件及其工作流程,并提供了快速搭建指南,包括准备步骤、部署命令及验证方法。此外,还展示了如何使用Grafana查看日志,以及一些基本的LogQL查询示例。最后,作者探讨了Loki架构的独特之处,提出了“巨型单体模块化”的概念,即一个应用既可单体部署也可分布式部署,整体协同实现全部功能。
2468 70
Grafana Loki,轻量级日志系统
|
JavaScript IDE 开发工具
python中的SyntaxError: invalid character in identifier(语法错误:标识符中有无效字符)
【5月更文挑战第14天】python中的SyntaxError: invalid character in identifier(语法错误:标识符中有无效字符)
1384 8
|
前端开发 API UED
React组件生命周期详解
【9月更文挑战第4天】在React应用开发中,掌握组件生命周期对于管理状态和属性至关重要,并能有效提升应用性能。本文详细介绍了React组件生命周期的三个阶段:挂载、更新和卸载,并通过代码示例展示了如何避免状态更新导致的死循环及优化网络请求等问题,帮助开发者构建更高效、可维护的应用。
258 3
|
SQL 关系型数据库 MySQL
MySQL数据库——索引(6)-索引使用(覆盖索引与回表查询,前缀索引,单列索引与联合索引 )、索引设计原则、索引总结
MySQL数据库——索引(6)-索引使用(覆盖索引与回表查询,前缀索引,单列索引与联合索引 )、索引设计原则、索引总结
389 1
|
算法 Python
利用贝叶斯算法对简单应用实现预测分类
利用贝叶斯算法对简单应用实现预测分类
170 0
|
测试技术 数据处理 Python
测试报告导出PDF和excel的方法
测试报告导出PDF和excel的方法
289 1
vue2路由切换动画(左右横移动画)
vue2路由切换动画(左右横移动画)
223 0
|
缓存 弹性计算 监控
Cassandra性能压测及调优实战|学习笔记
快速学习Cassandra性能压测及调优实战
235 0
Cassandra性能压测及调优实战|学习笔记