Cassandra源码阅读(5)-LevelCompactionStrategy与TimeWindowCompactionStrategy

本文主要描述Cassandra的Level Compaction Strategy,并简单描述Time Window Compaction Strategy。

背景

Level Compaction Strategy(简称LCS)来自的google的LevelDB,但是略有不同。
在LevelDB中,SSTable被分为N个Level,其中Level0的SSTable之间是可以Overlap的(两个SSTable的keyrange有交叉区间),且没有数量限制,L1到LN的SSTable是不可以Overlap的,每一层都有SStable个数限制,越高层数量越大。对于一个Key,如果L0没有命中,只需要查N个SSTable即可,每一层只需要查一个。这也是为什么说LevelDB是读优化的。
在LevelDB中会根据实际SSTable的数量和每层的理想数量计算一个得分,然后去Compact得分最高的那一层。
但是这会在compact的速度没有追赶上写入速度时失效。

可以看下面这里例子:

Level SSTable个数 理想个数 得分
L0 988 4 247
L1 117 10 11
L2 12 100 0

问题在于L0的得分247远高于L1的11,所以这里会从L0中取出max_compaction_L0(默认32个)sstable和L1的117个一起Compact一次,假设生成120个新的120个SSTable,放到L1,再把这120个L1和32个L0再Compact一次,如此往复。
每一轮都会花大量的时间和IO带宽重写L1的数据。

这里如果能一次把L0中所有SST和L1一起Compact就好了,但是并不能这么做。原因是L0的SSTable之间是可以Overlapping的,在合并的时候需要创建布隆过滤器来帮助判断overlapping的key。

布隆过滤器必须在创建时指定错误率和大小,但是在Compaction的开始阶段并不知道有多少key overlap了,所以必须开的足够大,特别是SSTable并没有overlap的情况下,这个开的布隆过滤器就浪费掉了。如果L0一次compact的太多这个布隆过滤器就会浪费大量内存,甚至引发OOM。

LevelDB的做法是当Compaction没有赶上时,直接把写给阻塞掉,也就是写不进去了。但是Cassandra作为一个高可用数据库肯定不能这么做。LevelDb起初时设计成嵌入式库的,最初是给Chromium用的,所以并没有高可用和高并发环境下的考虑。

Cassandra并不能阻塞,所以Cassandra的做法如下:

  1. 先Compact高Level的SSTable
  2. 如果L0赶不上,启动STCS(SizeTieredCompactionStrategy)去Compact L0的SSTable,使L0的SSTable数量变少。

LCS的主要代码在org.apache.cassandra.db.compaction.LeveledManifest.getCompactionCandidates()

Level Compaction Strategy具体处理流程

  1. 从高Level到低Level,L0除外

  2. 计算分数Score=该level所有SSTable的大小之和/该level最大允许的大小。对于L0最大允许的大小是4*160MB(MaxSSTableSize),对于第N层 = levelFanoutSize^N x MaxSSTableSize ,其中levelFanoutSize默认是10.L1就是10 x MaxSSTableSize,L2就是100 x MaxSSTableSize。

  3. 如果Score > 1.001

    3.1 检查L0是否落后了,落后的标准是L0的SSTable个数大于32个,如果大于32个,就对L0的SSTable启动一次STCS Compact

    3.2 L0没有落后,就找该Level的候选SSTable。具体做法是选择一个SSTable,它的第一个key在上一次Compact的SSTable的末尾key的后面一个,这么做是为了避免每次都Compact最前面一段(如果到末尾了就从头开始),然后找更高一级与之有overlapping的SSTable作为候选。如图1所示

    3.3 选好了SSTable之后,为了防止高Level的SSTable很少被Compact,从高到低选一个处于3.2选出区间中的SST。比如之前是一个从L1到L2的Compact,从L1中选出0-30,从L2中选出0-12,12-33,那么从高到低选一个处于0-33内的SSTable就可以了。

  4. 如果Score没有大于1.001的,也就是高Level都OK,这时从L0中选取需要Compact的SSTable。具体选择过程如下

    4.1 把L0中的所有SSTable按照SSTableMetaData中的MaxTimestamp正序排序,假设有N个

    4.2 选择第i个和所有和它有overlapping的SSTable,i从0到N。

    4.2.1 去掉和正处于Compact状态的SStable有交集的部分,重复4.2直到SSTable数目大于32个,或者循环到N。

    4.3 如果4.2选出的SSTable大于32个,按照maxTimeStamp排序,取前32个。

  5. 上述步骤执行完了之后,如果候选的SSTable总大小大于maxSSTableInBytes,则从L1中选出与这些候选这有Overlapping的SSTable,并加入候选者。如果不大于maxSSTableInBytes,就只有L0的这些部分。

  6. 如果候选者只有L0的,那么Compact之后仍然留在L0,否则晋升进入L1(在构造CompactionCandidate中有一个getNextLevel控制)。

至此,LCS具体处理流程完毕。剩下的Compact部分与之前的介绍STCS(SizeTieredCompactionStrategy)的Compact部分一致。

图1 L1与L2的候选SSTable

图1 L1与L2的候选SSTable

TimeWindowCompactionStrategy

写完了LCS,再简单写一下TWCS的处理流程,TWCS是专门为时序数据优化的。时序数据的特点是一旦写入基本不变,会有一个TTL时间,一旦这个TTL过了,整个SSTable就可以直接删除掉了。
那么对于时序数据,为什么STCS不好用,因为STCS会生成越来越大SSTable,而这些大SSTable的Compact频率是非常低的,这就会导致老的本应该过期数据一直在磁盘上得不到删除。实际删除时间会比TTL大很多,结果就是无用数据占用大量磁盘。

TWCS的出现就是为了解决这个问题。TWCS的代码在org.apache.cassandra.db.compaction.TimeWindowCompactionStrategy.getNextBackgroundSSTables。TWCS的思想和实现都非常简单,就是每次都Compact老的SSTable。

具体做法大致是:

选择maxLocalDeletionTime小于gc_grace_seconds的那些SSTable作为候选者,遍历它们并记下他们中的最小的minTimestamp。最后去掉候选SSTable里面maxTimestamp大于最小minTimestamp的,也就是只留下maxTimeStamp比minTimestamp还小的。把剩下的这些作为候选SSTable来进行Compact.