分区索引-过滤器

分区索引-过滤器

随着DB/mem比率的增大，过滤器/索引块的内存占用变得非常重要。尽管缓存索引块和筛选器块只允许将它们的一个子集存储在块缓存中，但它们相对较大的大小会对性能产生负面影响，原因是： i）占用块缓存空间，否则可能用于缓存数据； ii）错过后将它们加载到缓存中，从而增加磁盘存储的负载。在这里，我们将更详细地

索引/过滤块有多大？

默认情况下，每个SST文件有一个索引/过滤器块。索引/过滤器的大小根据配置而异，但对于大小为256MB的SST来说则不同，典型的索引/过滤块大小为0.5/5MB，大小为0.5/5MB的索引/过滤器块是典型的，这比4-32KB的典型数据块大得多。当所有索引/过滤器完全适合内存，因此每个SST生存周期读取一次时，这是很好的，当它们与块缓存空间的数据块竞争，并且可能从磁盘重新读取很多次时，就不需要那么多。

大型索引/过滤块有什么？

当索引/过滤器块存储在块缓存中时，它们实际上是在与这个稀缺资源上的数据块(以及彼此)竞争。大小为5MB的过滤器占用了可以用来缓存1000个数据块(大小为4KB)的空间。这将导致更多的数据块缓存丢失。大型索引/过滤器也更频繁地将彼此踢出块缓存，并加剧它们自己的缓存失效率。这只是索引/过滤器块的一小部分可能在缓存的生命周期中实际使用过。

索引/过滤器缓存失败后，必须从磁盘重新加载它，而且它的大尺寸无助于降低IO成本。虽然一个简单的点查找可能最多需要从LSM的每一层读取一对数据块(大小为4KB)，但它最终也可能加载多个兆字节的索引/过滤器块。如果这种情况经常发生，那么磁盘将花费更多的时间来服务索引/过滤器，而不是实际的数据块。

什么是分区索引/过滤器？

使用分区，SST文件的索引/过滤器被分区到更小的块中，并在这些块中附加一个顶级索引。当读取索引/过滤器时，只有顶级索引被加载到内存中。然后，分区索引/过滤器使用顶级索引按需将执行索引/过滤器查询所需的分区加载到块缓存中。顶级索引的内存占用要小得多，可以存储在堆或块缓存中，具体取决于cache_index_and_filter_blocks设置。

优点:

更高的缓存命中率: 分区允许以更细的粒度加载索引/过滤器，从而有效地利用缓存空间，而不是用大索引/块污染缓存空间。
更少的IO Util: 当索引/筛选器分区缓存失败时，只需要从磁盘加载一个分区，这与读取SST文件的整个索引/筛选器相比，在磁盘上的负载要轻得多。
索引/过滤器上永不妥协: 如果不进行分区，减少索引/过滤器内存占用的另一种方法就是牺牲它们的准确定，例如使用更大的数据块或更少的bloom位来分别拥有更小的索引和过滤器。

缺点:

顶级索引的额外空间: 其索引/过滤器大小的0.1-1%非常小。
更多磁盘IO: 如果顶级索引还没有在缓存中，它将导致一个额外的IO。为了避免它们可以存储在堆中，也可以存储在具有hi优先级的缓存中(要做的工作)
丢失空间位置: 如果工作负载需要频繁地随机读取同一个SST文件，那么每次读取时都会加载一个单独的索引/过滤器分区，这比一次性读取整个索引/过滤器的效率要低。虽然我们在基准测试中没有观察到这种模式，但这种情况只可能发生在LSM的L0/L1层，可以禁用分区(要做的工作)

成功案例

HDD, 100TB DB

在本例中，我们在HDD上有一个大小为86G的DB，并通过使用直接IO(跳过OS文件缓存)和一个大小为60MB的非常小的块缓存，模拟呈现给具有100TB数据的节点的小内存。分区将吞吐量从5个op/s提高了11倍，达到55个op/s。

./db_bench --benchmarks="readwhilewriting[X3],stats" --use_direct_reads=1 -compaction_readahead_size 1048576 --use_existing_db --num=2000000000 
--duration 600 --cache_size=62914560 -cache_index_and_filter_blocks=false -statistics -histogram -bloom_bits=10 -target_file_size_base=268435456 
-block_size=32768 -threads 32 -partition_filters -partition_indexes -index_per_partition 100 -pin_l0_filter_and_index_blocks_in_cache -benchmark_write_rate_limit 204800 
-max_bytes_for_level_base 134217728 -cache_high_pri_pool_ratio 0.9

SSD, Linkbench

在本例中，我们在SSD上有一个大小为300G的DB，并通过使用直接IO(跳过OS文件缓存)和大小为6G和2G的块缓存，模拟在同一节点上存在其他DBs时可用的小内存。如果不进行分区，当内存从6G减少到2G时，linkbench吞吐量从38k tps下降到23k。通过分区，吞吐量从38k下降到只有30k。

如何使用?

index_type = IndexType::kTwoLevelIndexSearch
- 这是为了启用分区索引
NewBloomFilterPolicy(BITS, false)
- 使用完整的过滤器
partition_filters = true
- 这是为了启用分区过滤器
metadata_block_size = 4096
- 这是索引分区的块大小
cache_index_and_filter_blocks = false [if you are on <= 5.14]
- 无论如何，分区都存储在块缓存中。这是为了控制顶级索引的位置(很容易放入内存): 固定在堆中或缓存在块缓存中。将它们存储在块缓存中是比较少实验的。
cache_index_and_filter_blocks = true and pin_top_level_index_and_filter = true [if you are on >= 5.15]
- 这将把所有的东西都放到块缓存中，但也会固定非常小的顶级索引。
cache_index_and_filter_blocks_with_high_priority = true
- 推荐设置
pin_l0_filter_and_index_blocks_in_cache = true
- 建议设置此属性，因为此属性也扩展到索引/筛选器分区。
- 只有在压缩样式基于级别时才使用它
- 注意: 如果没有设置strict_capacity_limit(这是默认情况)，那么将块固定到块缓存中可能会超出容量。
块缓存大小: 如果您过去将筛选器/索引存储到堆中，不要忘记使用从堆中节省的内存量来增加块缓存大小。

当前的限制

如果没有启用分区索引，则无法启用分区过滤器。
我们有相同数量的筛选器和索引分区。换句话说，当索引块被删除时，过滤器块也被删除。如果它被证明会导致缺陷，我们可能会在将来改变它。
过滤块大小由索引块被剪切的时间决定。我们将很快扩展metadata_block_size，以便在过滤器和索引块上都强制执行最大大小，即，当索引块被删除或其大小即将超过metadata_block_size (TODO)时，筛选器块将被删除。

幕后

这里我们为开发人员提供了实现细节。

BlockBasedTable格式

您可以在这里学习BlockBasedTable格式。对于分区，不同之处在于索引块

[index block]

存储为

[index block - partition 1]
[index block - partition 2]
...
[index block - partition N]
[index block - top-level index]

SST的页脚指向顶级索引块（它本身是索引分区块上的索引）。每个索引块分区都遵循与kBinarySearch相同的标记格式。顶级索引格式也符合kBinarySearch格式，因此可以使用普通数据块读取器读取。

类似的结构用于对过滤块进行分区。每个过滤块的格式与kFullFilter一致。顶级索引格式与kBinarySearch格式一致，类似于索引块的顶级索引。

注意,通过对SST检查工具(如sst_dump)进行分区，可以报告索引/过滤器上的顶级索引的大小，而不是索引/过滤块的总体大小。

构建器

分区索引和过滤器分别由PartitionedIndexBuilder和PartitionedFilterBlockBuilder构建。 PartitionedIndexBuilder维护subindex_builder，(指向ShortenedIndexBuilder的指针)来构建当前索引分区。当由flushpolicy确定时，构建器保存指针和索引快中的最后一个键,并创建一个新的活动ShortenedIndexBuilder。当::Finish 在构建器上调用时，它会在最早的子索引构建器上调用::Finish并返回结果分区块。接下来对PartitionedIndexBuilder::Finish的调用还将包括SST上以前返回的分区的偏移量，该偏移量用作顶级索引的值。最后一次调用PartitionedIndexBuilder::Finish将完成顶级索引并返回该索引。将顶级索引存储在SST上后，其偏移量将用作索引块的偏移量。

PartitionedFilterBlockBuilder继承自FullFilterBlockBuilder，后者有一个用于构建bloom过滤器的FilterBitsBuilder。它还有一个指向PartitionedIndexBuilder的指针，并在其上调用ShouldCutFilterBlock来确定何时应该删除筛选器块(就在何时删除索引块之后)。要删除一个过滤器块，它将完成FilterBitsBuilder并将结果块与PartitionedIndexBuilder::GetPartitionKey()提供的分区键一起存储，并为下一个分区重置FilterBitsBuilder。在每次调用PartitionedFilterBlockBuilder::Finish时，都会返回一个分区，并使用前一个分区的偏移量来构建顶级索引。最后一次调用::Finish将返回顶级索引块。

让PartitionedFilterBlockBuilder依赖于PartitionedIndexBuilder的原因是为了优化在SST文件上交错索引/过滤器分区。我们可能会在未来减少这种依赖关系。

读取器

分区索引是通过对顶级索引块进行操作的PartitionIndexReader读取的。当NewIterator被调用时，在顶级索引块上有一个TwoLevelIterator。这个简单的实现是可行的，因为每个索引分区都具有与数据块相同的kBinarySearch格式，因此可以作为较低级别的迭代器轻松地插入。如果设置了pin_l0_filter_and_index_blocks_in_cache，则低级迭代器被固定到PartitionIndexReader上，因此只要PartitionIndexReader还活着，它们对应的索引分区就会被固定在块缓存中。BlockEntryIteratorState使用一组固定的分区偏移量来避免将索引分区解除固定两次。

PartitionedFilterBlockReader使用顶级索引查找筛选器分区的偏移量。然后，它调用BlockBasedTable对象上的GetFilter来从块缓存加载过滤器分区上的FilterBlockReader对象(如果还没有加载到缓存中，则加载到缓存中)，然后释放FilterBlockReader对象。延长tableoptions。为了过滤分区，PartitionedFilterBlockReader不会释放这些块的缓存句柄(即，将它们固定在块缓存中)。相反，它维护filter_cache，这是一个固定的FilterBlockReader映射，当PartitionedFilterBlockReader被销毁时，它还用于释放缓存条目。