Cassandra的存储中存在两种压缩策略，即SizedTierCompaction和基于Google LevelDB的LeveledCompaction。开发者可以根据工作负载自由选择压缩策略。然而，LeveledCompaction的具体行为仍不太清楚，缺乏选择的依据。

于是，我决定调查一下原始的LevelDB实现。虽然互联网上有很多关于LevelDB的解释，但具体发出了哪些文件I/O操作并不清楚，所以我翻译了LevelDB开发者文档。结果，我发现它做得很好，所以我决定放心地使用LeveledCompaction。

参考：
– 从零开始学习LevelDB入门（基础篇）

LevelDB文件布局和压缩

LevelDB 文件布局和压缩

文件

Leveldb的实现在思想上类似于Bigtable的数据分块（第5.3节）。然而，由于构建表达的文件组织方式有些不同，因此在这里进行解释。

每个数据库都由存储在一个目录中的一组文件来表示。如下所示，存在几种不同类型的文件。

日志文件

最近的一系列更新被记录在一个日志文件(*.log)中。更新内容会被附加到当前的日志文件中。当日志文件大小达到预先定义的大小（默认为约4MB）时，它将被转换成一个排序表格（见下文），然后会创建一个用于后续更新的新日志文件。

当前日志文件的副本将存储在一个内存结构（memtable）中。由于所有的读操作都引用该副本，因此读指令将反映所有已记录的更新。

排列好的表格

已排序的表格(*.sst)以键的顺序存储一系列条目。每个条目都是键的值或键的删除标记（删除标记用于隐藏旧排序表中已删除的值）。

排序的表格集由一系列级别组成。从日志文件生成的排序表格将被放置在特定的年轻级别（也称为级别0）。当年轻文件的数量超过了特定的阈值（目前为4），所有年轻文件将与所有重叠的级别1合并，并生成一组新的级别1文件（每2MB数据创建一个新的级别1文件）。

年轻等级的文件可能存在重叠的键。然而，其他等级的文件具有不同的非重叠键范围。考虑级数L（L ≥ 1）。如果级别L的文件总大小超过(10^L) MB（即当级别为1时为10MB，级别为2时为100MB …），则级别L的某个文件将与所有重叠级别（L +1）的文件合并，并形成新的（L +1）级文件集。此合并操作通过仅使用批量读取和批量写入（即最小化昂贵的寻道操作）逐渐从年轻级别迁移到最高级别，从而具有将新的更新效果应用到文件系统中。

展现

MANIFEST文件是由构成每个级别的已排序表集合、相应的键范围以及其他重要元数据组成的列表。每次重新打开数据库时，都会创建一个新的MANIFEST文件（文件名中嵌入了一个新的编号）。MANIFEST文件以日志形式记录，所有状态变化（如添加或删除文件等）都会追加到该日志中。

现在的

CURRENT是一个简单的文本文件，用于保存最新的MANIFEST文件的名称。

信息日志

情报消息会被记录在名为LOG和LOG.old的文件中。

其他人

可能存在其他文件，可能是出于各种目的（如LOCK，*.dbtmp）。

等级0

• ログファイルが特定のサイズ(デフォルト1MB)まで成長したら：新しいmemtableとログファイルを作成し、今後の更新をここに向ける

 

• バックグラウンドで：

以前のmemtableの内容をsstableに書く
memtableを破棄する
古いログファイルと古いmemtableを削除する
新しく作ったsstableを若い(level-0)レベルに追加する

压缩

当级别L的大小达到上限时，会在后台线程中进行压缩。压缩会选择来自级别L的一个文件以及下一个级别L+1中所有与之重叠的文件。请注意，即使级别L文件只与级别(L+1)文件的一部分重叠，整个级别(L+1)文件也会被用作压缩的输入，并在压缩后被丢弃。顺便说一句：级别0是特殊的（其中的文件可能相互重叠），所以级别0到级别1的压缩会特别处理：级别0的压缩可以选择这些文件相互重叠时的一个或多个级别0文件。

压缩会合并所选文件并生成一系列的级别(L+1)文件。当当前的输出文件达到目标文件大小(2MB)时，将切换到生成新的级别(L+1)文件。另外，如果当前的输出文件与10个以上的级别(L+2)文件重叠并且显著增长，也会切换到生成新文件。这个最后的规则是为了确保后续级别(L+1)文件不会选择太多级别(L+2)文件进行压缩。

旧文件会被丢弃，新文件会被添加到等待状态。

特定级别的压缩通过键空间循环。更详细地说，每个级别L都会记住该级别L压缩的最后一个键。在下一个级别L的压缩中，将选择从该键之后开始的第一个文件。（如果没有这样的文件，则返回键空间的开头）

如果Compaction废弃了被覆盖的值，那么如果在较高级别上不存在具有与当前键重叠的范围的文件，还会丢弃删除标记。

时间

Level-0压缩从Level-0读取最多四个1MB文件，并读取所有Level-1文件的最差情况（总共10MB）。也就是说，读取14MB并写入14MB。

请从L级别中选择一个2MB文件，但除了特殊的级别0压缩外。并且从L+1级别中选择12个文件（L+1级别是L级别大小的10倍，所以有10个文件，另外的2个文件是因为L级别的文件范围通常与L+1级别的文件范围不对齐而产生的边界）。考虑到26MB的读写以及100MB/s的磁盘IO速率（现代驱动器的粗略范围），压缩的成本最坏情况下大约为0.5秒。

如果对后台写入进行了某种小的限制，例如将其限制在100MB/s的10%（即10MB/s），那么压缩可能最多需要5秒钟。如果用户以10MB/s的速度进行写入，那么我们可能会积累很多级别0文件（约50个，对应5*10MB）。由于每次读取都需要合并大量文件，这可能会极大地增加读取的成本。

解决方案1：为了缓解这个问题，在Level 0文件数量较多时，我认为需要提高日志开关的阈值。然而，值得注意的是，设置较大的阈值也可能带来更多的内存消耗，以维护相应的内存表。

解决方案2：当级别0文件数量增加时，我认为需要人工降低写入速率。

解决方案3：我们正在努力降低广泛合并的成本。可能大多数0级文件都存储在缓存中而未经过压缩，因此只需要担心合并迭代器的O(N)复杂度。

文件数量

可以使用更大的文件来代替始终创建2MB文件，以便提高总文件数，尽管这将需要更猛烈的压缩。 另外，您还可以将文件集分片到多个目录中。

根据在2011年2月4日进行的在ext3文件系统上的实验，当目录中存在不同数量的文件时，要打开100K个文件需要以下时间。

也许在现代化的文件系统中，并不需要分片，是吧？

恢复

• CURRENTをリードして最新のコミットされたMANIFESTを見つける

 

• 名指しされているMANIFESTファイルを読む

 

• 古いファイルをクリンナップする

 

• ここで全てのsstablesを開く事も出来るが、でも多分遅延した方がいいだろう…

 

• ログチャンクを新しいレベル0 sstableに変換する

 

復旧されたシーケンスで新しいログファイルに新しいライトを振り向ける

文件的垃圾回收

在每次压缩和恢复后，都会调用DeleteObsoleteFiles()函数。该函数将查找数据库中所有文件的名称，并删除所有非当前日志文件。它还会删除所有未被多个级别引用且不是活动压缩输出的表文件。