Leveled Compaction Strategy 如何确保 90% 的读取来自一个 sstable [英] How does the Leveled Compaction Strategy ensure 90% of reads are from one sstable

问题描述

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

来自 DataStax 文档:

<块引用>

新的 sstables 添加到第一级 L0，并立即与 L1 中的 sstables 压缩.当 L1 填满时，额外的 sstable 被提升到 L2.在 L1 中生成的后续 sstable 将与 L2 中与其重叠的 sstable 压缩.

解决方案

Cassandra 中的 LeveledCompactionStrategy (LCS) 实现了 LevelDB 的内部结构.您可以在 LevelDB 实施文档中查看确切的实施细节.

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

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 中选择所有重叠的文件.请注意，如果 L 级文件仅与 (L+1) 级文件的一部分重叠，则 (L+1) 级的整个文件将用作压缩的输入，并将在压缩后丢弃.旁白:因为 0 级是特殊的(其中的文件可能相互重叠)，我们特别对待从 0 级到 1 级的压缩:如果其中一些文件，0 级压缩可能会选择多个 0 级文件文件相互重叠.

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

I am trying to understand how the Leveled Compaction Strategy in Cassandra works that guarantees 90% of all reads will be satisfied from a single sstable.

From DataStax Doc:

new sstables are added to the first level, L0, and immediately compacted with the sstables in L1. When L1 fills up, extra sstables are promoted to L2. Subsequent sstables generated in L1 will be compacted with the sstables in L2 with which they overlap.

解决方案

LeveledCompactionStrategy (LCS) in Cassandra implements the internals of LevelDB. You can check the exact implementation details in LevelDB implementation doc.

In order to give you a simple explanation take into account the following points:

1. Every SSTable is created when a fixed (relatively small) size limit is reached. By default L0 gets 5MB files of files, and each subsequent level is 10x the size. (in L1 you'll have 50MB of data, L2 500MB, and so on).
2. SSTables are created with the guarantee that they don't overlap
3. When a level fills up, a compaction is triggered and stables from level-L are promoted to level-L+1. So, in L1 you'll have 50MB in ~10 files, L2 500MB in ~100 files, etc..

In bold are the relevant details that justify the 90% reads from the same file (SSTable). Let's do the math together and everything will become clearer.

Imagine you have keys A,B,C,D,E in L0, and each keys takes 1MB of data.

Next we insert key F. Because level 0 is filled a compaction will create a file with [A,B,C,D,E] in level 1, and F will remain in level 0.

That's ~83% of data in 1 file in L1.

Next we insert G,H,I,J and K. So L0 fills up again, L1 gets a new sstable with [I,G,H,I,J].

By now we have K in L0, [A,B,C,D,E] and [F,G,H,I,J] in L1

And that's ~90% of data in L1.

If we continue inserting keys we will get around the same behavior so, that's why you get 90% of reads served from roughly the same file/SSTable.

A more in depth and detailed (what happens with updates and tombstones) info is given in this paragraph on the link I mentioned (the sizes for compaction election are different because they are LevelDB defaults, not C*s):

When the size of level L exceeds its limit, we compact it in a background thread. The compaction picks a file from level L and all overlapping files from the next level L+1. Note that if a level-L file overlaps only part of a level-(L+1) file, the entire file at level-(L+1) is used as an input to the compaction and will be discarded after the compaction. Aside: because level-0 is special (files in it may overlap each other), we treat compactions from level-0 to level-1 specially: a level-0 compaction may pick more than one level-0 file in case some of these files overlap each other.

A compaction merges the contents of the picked files to produce a sequence of level-(L+1) files. We switch to producing a new level-(L+1) file after the current output file has reached the target file size (2MB). We also switch to a new output file when the key range of the current output file has grown enough to overlap more then ten level-(L+2) files. This last rule ensures that a later compaction of a level-(L+1) file will not pick up too much data from level-(L+2).

这篇关于Leveled Compaction Strategy 如何确保 90% 的读取来自一个 sstable的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！