• A
    Use only "local" range tombstones during Get (#4449) · 8c78348c
    Abhishek Madan 提交于
    Summary:
    Previously, range tombstones were accumulated from every level, which
    was necessary if a range tombstone in a higher level covered a key in a lower
    level. However, RangeDelAggregator::AddTombstones's complexity is based on
    the number of tombstones that are currently stored in it, which is wasteful in
    the Get case, where we only need to know the highest sequence number of range
    tombstones that cover the key from higher levels, and compute the highest covering
    sequence number at the current level. This change introduces this optimization, and
    removes the use of RangeDelAggregator from the Get path.
    
    In the benchmark results, the following command was used to initialize the database:
    ```
    ./db_bench -db=/dev/shm/5k-rts -use_existing_db=false -benchmarks=filluniquerandom -write_buffer_size=1048576 -compression_type=lz4 -target_file_size_base=1048576 -max_bytes_for_level_base=4194304 -value_size=112 -key_size=16 -block_size=4096 -level_compaction_dynamic_level_bytes=true -num=5000000 -max_background_jobs=12 -benchmark_write_rate_limit=20971520 -range_tombstone_width=100 -writes_per_range_tombstone=100 -max_num_range_tombstones=50000 -bloom_bits=8
    ```
    
    ...and the following command was used to measure read throughput:
    ```
    ./db_bench -db=/dev/shm/5k-rts/ -use_existing_db=true -benchmarks=readrandom -disable_auto_compactions=true -num=5000000 -reads=100000 -threads=32
    ```
    
    The filluniquerandom command was only run once, and the resulting database was used
    to measure read performance before and after the PR. Both binaries were compiled with
    `DEBUG_LEVEL=0`.
    
    Readrandom results before PR:
    ```
    readrandom   :       4.544 micros/op 220090 ops/sec;   16.9 MB/s (63103 of 100000 found)
    ```
    
    Readrandom results after PR:
    ```
    readrandom   :      11.147 micros/op 89707 ops/sec;    6.9 MB/s (63103 of 100000 found)
    ```
    
    So it's actually slower right now, but this PR paves the way for future optimizations (see #4493).
    
    ----
    Pull Request resolved: https://github.com/facebook/rocksdb/pull/4449
    
    Differential Revision: D10370575
    
    Pulled By: abhimadan
    
    fbshipit-source-id: 9a2e152be1ef36969055c0e9eb4beb0d96c11f4d
    8c78348c
table_cache.cc 17.7 KB