Cassandra SSTable 合并策略（一）：STCS

1. 背景

Cassandra 是我最喜欢的分布式数据库，之前项目中借助于 Cassandra 来实时存储大量的广告点击事件，后续处理激活事件进行归因分析中，可以精确的定位到某条点击样本数据。当时点击事件表已经达到 TB 级别，某条点击样本查询却依然能在毫秒级别返回，让我很是惊叹。现在回想起来，那时候其实还可以做的更好，因为表创建时某些附加属性研究的不够深入，如果研究深入同时结合当时业务场景，选择恰当的 Compaction 策略，相信性能应该会更好。

2. 什么是 STCS

STCS 全名是 Size Tiered Compaction Strategy，看过 STCS 的实现原理后，我更喜欢将其翻译成 “按容量分桶合并策略”。STCS 按照容量大小对待合并的 SSTable 列表进行排序，根据预先定义的 SSTable 最小容量阀值（默认 50M）和最小（默认 0.5）最大（默认 1.5）倍数，按照某种规则持续构建桶的过程。最终容量小于阀值的 SSTable 被放置在一个桶中，对于容量大于阀值的 SSTable，如果容量相近大概率会放置在相同的桶中，细节方面参考下面的详细步骤。

3. 详细步骤

3.1 步骤 1：排序

待合并的 SSTable 列表按照容量大小进行排序：

3.2 步骤 2：处理第一个 SSTable

目前桶还没有构建，第一个 SSTable 无处安置，此时会创建一个新桶放置这个 SSTable，新桶会使用 SSTable 的容量作为桶的容量。

3.3 步骤 3：处理第二个 SSTable

根据当前 SSTable 容量和已创建的 Bucket 进行匹配，满足下面条件中的一个即匹配成功：

• SSTable 容量在此开区间中：(Bucket 容量 * 最小倍数, Bucket 容量 * 最大倍数)；

• SSTable 容量和 Bucket 容量都小于阀值。

对于匹配结果：

• 失败：创建新桶放置当前 SSTable；

• 成功：当前 SSTable 会放置在匹配的 Bucket 中，Bucket 的容量会重新计算：桶中 SSTable 容量之和除以 SSTable 个数。

3.4 步骤 4：处理第 n 个 SSTable

声明以下变量：

• minThreshold：最小 SSTable 阀值；

• low：最小倍数；

• high：最大倍数

• sn：第 n 个 SSTable

假设已经创建的桶为：bucket1、bucket2、......、bucketm，其中 m <= n - 1，桶的 volume 属性为其容量，那么完整的处理流程如下：

经过上面一系列的操作，最终待合并的 SSTable 会分别放置在桶中，后续每个桶中的所有 SSTable 会执行合并操作。