前言
最近对 LSM 树、Cassandra 的读取过程感兴趣，奈何印象模糊，故去官网查阅、复习了一下。顺便译成此文。
Cassandra、HBase、LevelDB 均是采用了 LSM 树进行存储，故三者的读写过程都大同小异，都具有 commitLog、memTable、SSTable(LSM) 结构，理解本文可举一反三。
简介
读取时，Cassandra 会合并 MemTable 和至少一个 SSTable 的结果。
Cassandra 寻找数据的过程有多个步骤。从 MemTable 中的数据开始，以 SSTables 结尾：
- 检查 MemTable
- 检查行缓存（如果启用）
- 检查布隆过滤器
- 检查分区键缓存（如果启用）
- 如果在分区键缓存中找到了分区键，则直接转到压缩偏移量映射表；如果未找到分区键，则检查 Partition Summary ，选中 Partition Summary 后，访问对应的分区索引
- 使用压缩偏移量映射表定位磁盘上的数据
- 从磁盘上的 SSTable 中获取数据
MemTable
如果 MemTable 具有所需的分区数据，则读取该数据，然后将其与 SSTables 中的数据合并。访问 SSTable 数据的步骤如下。
Row Cache（行缓存）
它在所有数据库中都是典型的，读取速度最快，通过将访问频繁的数据放入内存中实现。操作系统页缓存（page cache）最适合提高读取性能，尽管行缓存也可以为读取密集型操作（读取操作占负载的95％）提供一些改进。行缓存禁止用于写密集型操作。如果启用行缓存，会将 SSTables 中的部分分区数据存储在内存中。在 Cassandra 2.2和更高版本中，它存储在堆外内存中，这样减轻了 JVM 的 GC 压力。当缓存已满时，行缓存使用 LRU 策略回收内存。
行缓存大小以及要存储的行数都是可配置的。配置存储行数很重要，可以使类似查询“最后10项”的速度非常快。如果启用了行缓存，则将从行缓存中读取所需的分区数据，从而有可能节省两次从磁盘上查找的时间。行缓存中存储的行是经常访问的行，在访问它们时，这些行将合并并从 SSTable 保存到行缓存中。存储后，数据可用于以后的查询。行缓存不可以通过写操作添加。如果对该行进行写操作，则该行缓存将失效，直到读取该行后才再次被缓存。同样，如果更新分区，则会从缓存中逐出整个分区。如果行缓存中没有想要的数据，则检查布隆过滤器。
Bloom Filter（布隆过滤器）
首先，Cassandra 会检查布隆过滤器，以查找哪些 SSTables 可能具有请求分区数据。布隆过滤器存储在堆外存储器中。每个 SSTable 都有一个关联的布隆过滤器。布隆过滤器可以确定 SSTable 不包含哪些分区的数据。布隆过滤器还可以查出相应分区数据存储在一个 SSTable 中的可能性。它可以通过缩小键池大小来提高查找分区键的速度。但是，由于布隆过滤器是一个概率函数，因此可能导致误报。布隆过滤器找出的 SSTable 中也可能没有对应的数据。如果布隆过滤器不可以确定是哪个 SSTable ，Cassandra 会检查分区键缓存。
每十亿个分区，布隆过滤器大约会占用1-2GB大小空间。在极端情况下，每行可以对应一个分区，因此在一台机器上可以轻松拥有数十亿个这样的条目。如果要以内存换取性能，则布隆过滤器是可调的。
Partition Key Cache（分区键缓存）
如果启用分区键缓存，会将分区索引存储在堆外内存中。键缓存占内存小，且可配置，每次“命中”都可以减少一次查找。如果在键缓存中找到分区键，则可以直接转到压缩偏移量映射表，从磁盘上找到对应的数据。分区键缓存一旦预热就可以更好地发挥作用，并且可以大大提高冷启动时读取的性能。如果节点上的内存非常有限，可以限定保存在键缓存中的分区键的数量。如果在键缓存中找不到分区键，则搜索 Partition Summary。
分区键缓存的大小以及存储在键缓存中的分区键的数量都是可配置的。
Partition Summary（分区稀疏索引？这个直接翻译不太好～）
Partition Summary 是一种堆外内存结构，存储了分区索引的采样（可以理解为分区稀疏索引～）。分区索引包含所有分区键，而 Partition Summary 每隔 X 个键进行采样，并映射索引文件中第 Xth 键的位置。例如，如果 Partition Summary 设置为每20个键采样一次，它会将 SSTable 文件的开头作为第一个键，然后是第20个键及其在文件中的位置，依此类推。虽然不如分区键的位置那么精确，但是 Partition Summary 可以缩短扫描时间。找到可能的分区键值的范围后，然后确定分区索引。
通过配置采样频率，您可以以内存换取性能，Partition Summary 的粒度越小，使用的内存就越多。配置 index_interval 属性可以更改采样频率。可以通过配置 index_summary_capacity_in_mb 属性设置占用固定大小的内存，默认为堆大小的5％。
Partition Index（分区索引）
分区索引位于磁盘上，存储了映射到所有分区键的位置。检查了 Partition Summary 中的分区键范围后，然后转到分区索引以查找所需分区键的位置。对范围内的列将进行遍历查找。使用找到的信息，分区索引进入压缩偏移量映射表，以在磁盘上找到包含数据的压缩块。如果必须搜索分区索引，则需要两次磁盘搜索才能找到所需的数据。
Compression offset map（压缩偏移量映射表）
压缩偏移量映射表存储了分区数据的确切位置。它存储在堆外内存中，可以通过分区键缓存或分区索引进行访问。从压缩偏移量映射表确定了磁盘位置后，就可以从对应的的 SSTable 中查询出被压缩的分区数据。
注意：在分区内，并非查询所有行的代价都相同。由于不需要查询分区级索引，因此查询分区的最开始（第一行，由自定义键决定）的开销稍低一些。
每TB数据，压缩偏移量映射表将占用 1-3 GB。压缩数据越多，压缩块的数量就越多，压缩偏移量映射表也就越大。尽管使用压缩偏移量映射表会消耗 CPU 资源，默认情况下还是会启用压缩。启用压缩将使页缓存更有效，通常来说，利大于弊。
翻译自官方文档