10

我试图了解 Cassandra 中的Leveled Compaction Strategy是如何工作的，以保证 90% 的所有读取都将从单个 sstable 中得到满足。

来自 DataStax 文档：

新的 sstables 被添加到第一层 L0，并立即与 L1 中的 sstables 压缩。当 L1 填满时，额外的 sstables 会提升到 L2。在 L1 中生成的后续 sstable 将与它们重叠的 L2 中的 sstable 进行压缩。

4

1 回答 1

22

Cassandra 中的 LeveledCompactionStrategy (LCS) 实现了 LevelDB 的内部结构。您可以在LevelDB implementation doc中查看确切的实现细节。

为了给您一个简单的解释，请考虑以下几点：

  1. 每个 SSTable 都是在达到固定（相对较小）的大小限制时创建的。默认情况下，L0 获取 5MB 文件的文件，并且每个后续级别是大小的 10 倍。（在 L1 中，您将拥有 50MB 的数据，L2 将拥有 500MB 的数据，依此类推）。
  2. 创建 SSTable 时保证它们不会重叠
  3. 当一个级别填满时，会触发一个压缩，并且从级别 L 提升到级别 L+1 的马厩。因此，在 L1 中，您将在 ~10 个文件中拥有 50MB，在 ~100 个文件中拥有 L2 500MB，等等。

粗体字是证明从同一文件 (SSTable) 读取 90% 的相关细节。让我们一起做数学，一切都会变得更清楚。

假设您在 L0 中有键 A、B、C、D、E，每个键需要 1MB 的数据。

接下来我们插入键 F。因为 0 级已填充，所以压缩将在 1 级创建一个带有 [A,B,C,D,E] 的文件，而 F 将保持在 0 级。

这是 L1 中 1 个文件中约 83% 的数据。

接下来我们插入 G,H,I,J 和 K。所以 L0 再次被填满，L1 得到一个带有 [I,G,H,I,J] 的新 sstable。

现在我们在 L0 中有 K，在 L1 中有 [A,B,C,D,E] 和 [F,G,H,I,J]

这是 L1 中约 90% 的数据。

如果我们继续插入密钥，我们将绕过相同的行为，这就是为什么您可以从大致相同的文件/SSTable 中获得 90% 的读取。

本段中我提到的链接上给出了更深入和详细的信息（更新和墓碑会发生什么）（压缩选举的大小不同，因为它们是 LevelDB 默认值，而不是 C*s）：

当级别 L 的大小超过其限制时，我们在后台线程中对其进行压缩。压缩从级别 L 中选择一个文件，并从下一个级别 L+1 中选择所有重叠的文件。请注意，如果 level-L 文件仅与 level-(L+1) 文件的一部分重叠，则 level-(L+1) 处的整个文件将用作压缩的输入，并将在压缩后丢弃。另外：因为 level-0 是特殊的（其中的文件可能相互重叠），我们特别对待从 level-0 到 level-1 的压缩：一个 level-0 压缩可能会选择多个 level-0 文件，以防其中一些文件相互重叠。

压缩合并挑选的文件的内容以产生一系列级别-(L+1) 文件。在当前输出文件达到目标文件大小（2MB）后，我们切换到生成新的（L+1）级文件。当当前输出文件的键范围增长到足以与十多个级别（L+2）文件重叠时，我们也会切换到新的输出文件。最后一条规则确保稍后对 level-(L+1) 文件的压缩不会从 level-(L+2) 中提取太多数据。

于 2015-04-21T10:58:43.963 回答