Devirtualization And Key Prefix Cache Benchmark

[English version]

去虚拟化与前缀缓存性能实测

去虚拟化： 消除虚函数调用，在我们的优化中，主要是 Comparator 虚函数调用

前缀缓存： 从 Key 中提取出固定长度（8字节）前缀，放入一个独立数组，在该数组上按整数进行二分搜索

更多内容，请参考 Devirtualization And Key Prefix Cache Principle

测试的机器是双路 E5-2682 V4 共 32 核 64 线程, 256G DDR4 2400Hz, 更新更好的机器，性能也会更好。

1. 测试参数

这里仅列出关键参数，并解释为什么设置成这样。为简化起见，该测试中不使用分布式 Compact。

1.1. db_bench 参数

参数名	参数值	效果
num	100000000	num 设大一些，使得 DB 的各种元数据无法全部装入 CPU Cache
key_size	8	会导致 db_bench 写入的 key 是连续的 big endian 整数
value_size	20	设小一些，最小化内存分配及 memcpy 对性能的影响
json	db_bench_enterprise.yaml	使用 ToplingZipTable, 连续的 big endian 整数会使用 UintIndex_AllOne 索引，这是 ToplingDB 最快且最小的索引
json	db_bench_community.yaml	使用 BlockBasedTable, 并设置足够的 BlockCache，速度比 ToplingZipTable 慢很多

1.2. db_bench_*.yaml 共同参数

参数名	参数值	效果
target_file_size_base	512K	把 target_file_size_base 设得很小是为了产生很多文件，从而体现 key prefix cache 的效果
max_bytes_for_level_base	4M	让每层都有足够数量的文件
max_bytes_for_level_multiplier	4	让每层都有足够数量的文件
Statistics::stats_level	kDisableAll	禁用性能测量

1.3. db_bench_enterprise.yaml 中 ToplingZipTable 参数

参数名	参数值	效果
acceptCompressionRatio	0.8	当测试更大的 value_size 时，可以设成很小的值，让 ToplingZipTable 放弃对 Value 的压缩
minDictZipValueSize	30	大于该测试中指定的 value_size=20, 让 ToplingZipTable 放弃对 Value 的压缩
minPreadLen	-1	读取 value 总是使用 mmap
enableStatistics	false	禁用性能测量，避免非必要开销

1.4. db_bench_enterprise.yaml 中 BlockBasedTable 参数

每层数据都不压缩，无 BloomFilter，因为根据该测试中 Key 的分布，只需要 SST 文件 meta data 就可以确定 key 是否在文件中，无需 BloomFilter。

2. 条件编译 TOPLINGDB_NO_OPT_FindFileInRange

为了体现我们的优化效果，新加了一个条件编译宏 TOPLINGDB_NO_OPT_FindFileInRange，用来控制是否启用我们的优化。

 int FindFileInRange(const InternalKeyComparator& icmp,
                     const LevelFilesBrief& file_level, const Slice& key,
                     uint32_t left, uint32_t right) {
+#ifdef TOPLINGDB_NO_OPT_FindFileInRange
+  #pragma message "TOPLINGDB_NO_OPT_FindFileInRange is defined, intended for benchmark comparing"
+  // here is upstream rocksdb code
   auto cmp = [&](const FdWithKeyRange& f, const Slice& k) -> bool {
     return icmp.InternalKeyComparator::Compare(f.largest_key, k) < 0;
   };
   const auto& b = file_level.files;
   return static_cast<int>(std::lower_bound(b + left, b + right, key, cmp) - b);
+#else // ToplingDB Devirtualization and Key Prefix Cache optimization
+  if (icmp.IsForwardBytewise()) {
+    BytewiseCompareInternalKey cmp;
+    return (int)FindFileInRangeTmpl(cmp, file_level, key, left, right);
+  }
+  else if (icmp.IsReverseBytewise()) {
+    RevBytewiseCompareInternalKey cmp;
+    return (int)FindFileInRangeTmpl(cmp, file_level, key, left, right);
+  }
+  else {
+    FallbackVirtCmp cmp{&icmp};
+    return (int)FindFileInRangeTmpl(cmp, file_level, key, left, right);
+  }
+#endif
 }

3. 编译

每次编译前 touch FindFileInRange 所在的文件 version_set.cc 再编译，确保编译了正确的代码。

3.1. 禁用 FindFileInRange 优化

touch db/version_set.cc
make db_bench -j`nproc` OPTIMIZE_LEVEL='-O3' DEBUG_LEVEL=0 \
     EXTRA_CXXFLAGS=-DTOPLINGDB_NO_OPT_FindFileInRange

3.2. 启用 FindFileInRange 优化

touch db/version_set.cc
make db_bench -j`nproc` OPTIMIZE_LEVEL='-O3' DEBUG_LEVEL=0

4. 使用 db_bench_enterprise.yaml

4.1. 使用 db_bench 灌入数据

仅灌入数据，并执行 flush，保证 LSM 每一层都有数据，是否启用 FindFileInRange 优化不影响灌数据。

$ ./db_bench -json=sideplugin/rockside/sample-conf/db_bench_enterprise.yaml \
             -key_size=8 -value_size=20 -batch_size=10 -num=100000000 \
             -disable_wal=true -benchmarks=fillseq,flush

Set seed to 1672971774512063 because --seed was 0
Initializing RocksDB Options from the specified file
Initializing RocksDB Options from command-line flags
Integrated BlobDB: blob cache disabled
RocksDB:    version 7.10.0
Date:       Fri Jan  6 10:22:54 2023
CPU:        64 * Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz
CPUCache:   40960 KB
Keys:       8 bytes each (+ 0 bytes user-defined timestamp)
Values:     20 bytes each (10 bytes after compression)
Entries:    100000000
Prefix:    0 bytes
Keys per prefix:    0
RawSize:    2670.3 MB (estimated)
FileSize:   1716.6 MB (estimated)
Write rate: 0 bytes/second
Read rate: 0 ops/second
Compression: Snappy
Compression sampling rate: 0
Memtablerep: CSPPMemTabFactory
Perf Level: 1
------------------------------------------------
Initializing RocksDB Options from the specified file
Initializing RocksDB Options from command-line flags
Integrated BlobDB: blob cache disabled
DB path: [/dev/shm/db_bench_enterprise]
fillseq: 0.452 micros/op 2211711 ops/sec 45.214 seconds 100000000 operations; 59.1 MB/s
flush memtable

4.2. 灌入数据后 LSM 树的形态

** Compaction Stats [default] **
Level    Files      Size     Score    省略...
-----------------------------------   省略...
  L0      1/0       1.64 MB   0.4     省略...
  L1     17/0       3.14 MB   0.8     省略...
  L2     76/0      15.26 MB   1.0     省略...
  L3    328/0      63.70 MB   1.0     省略...
  L4   1336/0     255.22 MB   1.0     省略...
  L5   5392/0    1023.65 MB   1.0     省略...
  L6   2952/0     558.28 MB   0.0     省略...
 Sum  10102/0       1.88 GB   0.0     省略...

4.3. 确认使用了 UintIndex_AllOne 索引

通过 WebView 可以查看单个 SST 的信息，可以看到，ToplingZipTable 确实使用了 UintIndex_AllOne 索引。

在 MyTopling(MySQL) 中最常用的主键索引 auto_increment id 就会使用到 UintIndex 系列索引，如果 id 中间没有空洞，就是 UintIndex_AllOne。我们在 db_bench 这里用 key_size=8 主动选择该索引。

4.4. read 性能测试

$ ./db_bench -json sideplugin/rockside/sample-conf/db_bench_enterprise.yaml \
             -num=100000000 -benchmarks=readrandom -use_existing_db=true

该 db_bench 命令执行单独的 readrandom 测试，use_existing_db=true 表示使用之前灌入的数据。

以下火焰图中 @@ 表示匿名 namespace。

禁用 FindFileInRange 优化

# 省略 省略 省略 以下结果中删减若干空格并适当换行
------------------------------------------------
DB path: [/dev/shm/db_bench_enterprise]
readrandom: 1.544 micros/op 647552 ops/sec 154.428 seconds 100000000 operations;
           17.3 MB/s (100000000 of 100000000 found)

火焰图（单独查看，可细化至每个函数）

启用 FindFileInRange 优化

# 省略 省略 省略 以下结果中删减若干空格
------------------------------------------------
DB path: [/dev/shm/db_bench_enterprise]
readrandom: 1.009 micros/op 991406 ops/sec 100.867 seconds 100000000 operations;
           26.5 MB/s (100000000 of 100000000 found)

火焰图（单独查看，可细化至每个函数）

解释说明

平均下来，FindFileInRange 优化版的耗时只有原版的 65%, 并且，根据火焰图，我们可以算出 FindFileInRange 本身的性能提升幅度。

因为 FindFileInRange 之外其它部分的耗时在两个测试中是个不变量，所以，我们使用 FindFileInRange 耗时除以其它部分的耗时，就是 FindFileInRange 的相对耗时数值。这个相对耗时数值是可以直接比较的，最终我们算出，FindFileInRange 本身的性能提升幅度是 4.25 倍。这个计算过程，大致是小学五年级数学应用题的水平。

优化	耗时占比	相对耗时	倍数
禁用	42.68%	42.68/(100-42.68) = 0.7446	`4.25` = 0.7446/0.1751
启用	14.90%	14.90/(100-14.90) = 0.1751	1.00

5. 使用 db_bench_community.yaml

5.1. 使用 db_bench 灌入数据

除了使用 db_bench_community.yaml 之外，其它参数与 db_bench_enterprise 完全相同。

$ ./db_bench -json=sideplugin/rockside/sample-conf/db_bench_community.yaml \
             -key_size=8 -value_size=20 -batch_size=10 -num=100000000 \
             -disable_wal=true -benchmarks=fillseq,flush
Set seed to 1672996553785931 because --seed was 0
Initializing RocksDB Options from the specified file
Initializing RocksDB Options from command-line flags
Integrated BlobDB: blob cache disabled
RocksDB:    version 7.10.0
Date:       Fri Jan  6 17:15:53 2023
CPU:        64 * Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz
CPUCache:   40960 KB
Keys:       8 bytes each (+ 0 bytes user-defined timestamp)
Values:     20 bytes each (10 bytes after compression)
Entries:    100000000
Prefix:    0 bytes
Keys per prefix:    0
RawSize:    2670.3 MB (estimated)
FileSize:   1716.6 MB (estimated)
Write rate: 0 bytes/second
Read rate: 0 ops/second
Compression: Snappy
Compression sampling rate: 0
Memtablerep: CSPPMemTabFactory
Perf Level: 1
------------------------------------------------
Initializing RocksDB Options from the specified file
Initializing RocksDB Options from command-line flags
Integrated BlobDB: blob cache disabled
DB path: [/dev/shm/db_bench_community]
fillseq      :       0.449 micros/op 2225012 ops/sec 44.944 seconds 100000000 operations;   59.4 MB/s
flush memtable

我们可以看到，因为使用的 MemTable 相同，所以写数据的性能也基本相同。

5.2. 灌入数据后 LSM 树的形态

** Compaction Stats [default] **
Level    Files      Size     Score    省略...
-----------------------------------   省略...
  L0      1/0       1.16 MB   0.3     省略...
  L1      1/0       3.22 MB   0.8     省略...
  L2      4/0      12.89 MB   0.8     省略...
  L3     19/0      61.16 MB   1.0     省略...
  L4     79/0     254.35 MB   1.0     省略...
  L5    318/0    1023.89 MB   1.0     省略...
  L6    555/0       1.74 GB   0.0     省略...
 Sum    977/0       3.07 GB   0.0     省略...

文件的数量比使用 ToplingZipTable 要少，应该是因为 TableBuilder::EstimateFileSize() 的实现不同， ToplingZipTable 返回的是 Add 进来的 key value 尺寸之和，BlockBasedTable 有自己的计算方式。

文件数量更少，FindFileInRange 本身的耗时就更少，在这一点上 BlockBasedTable 占了一点小便宜。

同是没有压缩，但 BlockBasedTable 的文件尺寸更大，这是因为 ToplingZipTable 的 Index 使用了 UintIndex_AllOne, 空间占用是 O(1), Index 尺寸与数据没有关系，所以实际上可以认为不占用空间。

ToplingDB 对 BlockBasedTableBuilder::EstimateFileSize() 的计算有个选项参数 use_raw_size_as_estimated_file_size, 在 json/yaml 中定义为 BlockBasedTable Factory 的选项，如果为 true，这个计算方式就与 ToplingZipTable 相同，但是在该测试中为了尽量让 BlockBasedTable 的行为与 RocksDB 上游相同，我们没有定义该选项（默认 false）。

5.3. 查看 BlockIndex

ToplingDB 在 WebView 中对 BlockBasedTable 也实现了查看 SST 元信息的功能。

5.4. read 性能测试

$ ./db_bench -json sideplugin/rockside/sample-conf/db_bench_community.yaml \
             -num=100000000 -benchmarks=readrandom -use_existing_db=true

该 db_bench 命令执行单独的 readrandom 测试，use_existing_db=true 表示使用之前灌入的数据。

以下火焰图中 @@ 表示匿名 namespace。

禁用 FindFileInRange 优化

# 省略 省略 省略 以下结果中删减若干空格并适当换行
------------------------------------------------
DB path: [/dev/shm/db_bench_community]
readrandom: 4.182 micros/op 239138 ops/sec 418.168 seconds 100000000 operations;
            6.4 MB/s (100000000 of 100000000 found)

火焰图（单独查看，可细化至每个函数）

启用 FindFileInRange 优化

# 省略 省略 省略 以下结果中删减若干空格
------------------------------------------------
DB path: [/dev/shm/db_bench_community]
readrandom: 3.644 micros/op 274432 ops/sec 364.389 seconds 100000000 operations;
            7.3 MB/s (100000000 of 100000000 found)

火焰图（单独查看，可细化至每个函数）

解释说明

BlockBasedTable 和 ToplingZipTable 实际上都未使用压缩，BlockBasedTable 需要 BlockCache, 同时，读文件时也会有 PageCache（除非使用 direct io）
ToplingZipTable 不需要 BlockCache，只需要文件系统的 PageCache

BlockBasedTable 即便配置了 8G 的 BlockCache, 差不多是总的数据量的 3 倍，但 BlockBasedTable 仍然比 ToplingZipTable 慢得多。

下面我们用相同的方法来计算 FindFileInRange 优化版与原版的性能差异：

优化	耗时占比	相对耗时	倍数
禁用	11.65%	11.65/(100-11.65) = 0.1319	`4.19` = 0.1319/0.0315
启用	3.05%	3.05/(100-3.05) = 0.0315	1.00

可见，虽然 db_bench_community 因为使用 BlockBasedTable，速度比 ToplingZipTable 慢很多，但是根据相同的方法，这里算出来的禁用与启用优化之间的性能差异倍数是 4.19，与 db_bench_enterprise 中算出来的 4.25 之间的差异，可以认为是误差。

6. ToplingZipTable 与 BlockBasedTable 性能对比

使用相同的计算方法，我们可以计算 FindFileInRange 的性能改进幅度，也可以计算 ToplingZipTable 与 BlockBasedTable 的性能差异。

TableReader::Get 之外的耗时是个不变量，在这里 BlockBaseTable 因为文件数量小，这一块相对 ToplingZipTable 也会更小一些，从而 ToplingZipTable 会占一点便宜

BlockBasedTableReader::Get 在火焰图中分 4 部分（应该是火焰图工具的问题，这 4 部分本应统计到一起的），耗时占比加起来是 37.53 + 37.42 + 2.09 + 2.42 = 79.46%

SST	耗时占比	相对耗时	倍数
BlockBased	79.46%	79.46/(100-79.46) = 3.8685	`7.19` = 3.8685/0.5378
ToplingZip	34.97%	34.97/(100-34.97) = 0.5378	1.00

使用非优化的 FindFileInRange 火焰图来计算（34.08 + 36.86 + 2.09 = 73.03%）：

SST	耗时占比	相对耗时	倍数
BlockBased	73.03%	73.03/(100-73.03) = 2.7078	`8.75` = 2.7078/0.3094
ToplingZip	23.63%	23.63/(100-23.63) = 0.3094	1.00

计算出来 ToplingZipTable 的性能是 BlockBasedTable 的 7.19 和 8.75 倍，这个误差有点大，不好解释。

注意，这里有以下前提：

项目	ToplingZipTable	BlockBasedTable
压缩	未压缩	未压缩
Cache	PageCache 全命中	BlockCache 全命中
BloomFilter	总是不需要 BloomFilter	该测试产生的 SST 不需要 BloomFilter
索引	选中了 UintIndex_AllOne 这种最快的索引	通用索引

可见该测试条件均是双方的最优条件。ToplingZipTable 使用自己的通用索引 NestLoudsTrie 时，搜索 Key 的速度会慢一些，启用压缩时，获取 Value 的速度会慢一些。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Devirtualization And Key Prefix Cache Benchmark

[English version]

去虚拟化与前缀缓存性能实测

1. 测试参数

1.1. db_bench 参数

1.2. db_bench_*.yaml 共同参数

1.3. db_bench_enterprise.yaml 中 ToplingZipTable 参数

1.4. db_bench_enterprise.yaml 中 BlockBasedTable 参数

2. 条件编译 TOPLINGDB_NO_OPT_FindFileInRange

3. 编译

3.1. 禁用 FindFileInRange 优化

3.2. 启用 FindFileInRange 优化

4. 使用 db_bench_enterprise.yaml

4.1. 使用 db_bench 灌入数据

4.2. 灌入数据后 LSM 树的形态

4.3. 确认使用了 UintIndex_AllOne 索引

4.4. read 性能测试

禁用 FindFileInRange 优化

启用 FindFileInRange 优化

解释说明

5. 使用 db_bench_community.yaml

5.1. 使用 db_bench 灌入数据

5.2. 灌入数据后 LSM 树的形态

5.3. 查看 BlockIndex

5.4. read 性能测试

禁用 FindFileInRange 优化

启用 FindFileInRange 优化

解释说明

6. ToplingZipTable 与 BlockBasedTable 性能对比

Clone this wiki locally