iterator `Seek` slowdown after delete many keys
- Dominant language
- C++
- Stars
- 32.1k
- Forks
- 6.9k
- Avg merge
- 32m
- Merged PRs (30d)
- 1
Description
> Note: Please use Issues only for bug reports. For questions, discussions, feature requests, etc. post to dev group: https://groups.google.com/forum/#!forum/rocksdb or https://www.facebook.com/groups/rocksdb.dev
Hi, guys~ I found that the `Iterator->Seek()` is very slow after delete many keys, and I found a related issue #5265, but i am not sure my problem is same as this one, so can you give me some advice? or if my problem is indeed the same as issue #5265, how can we solve it completely?
* my program pseudo-code:
```lua
for i = 1, 100000, 1 do // put 100000 keys
DB->Put("/prefix/" + str(i))
end
Iterator->Seek("/prefix/") // cost about 20 us
for i = 1, 100000, 1 do // delete 100000 keys
DB->Delete("/prefix/" + str(i))
end
Iterator->Seek("/prefix/") // cost about 13 ms
```
* pref context for `Seek`:
> cost 12762 us
```
perf context(user_key_comparison_count = 420038
block_cache_hit_count = 1
block_read_count = 0
block_read_byte = 0
block_read_time = 0
block_cache_index_hit_count = 0
index_block_read_count = 0
block_cache_filter_hit_count = 0
filter_block_read_count = 0
compression_dict_block_read_count = 0
secondary_cache_hit_count = 0
block_checksum_time = 0
block_decompress_time = 0
get_read_bytes = 0
multiget_read_bytes = 0
iter_read_bytes = 88
internal_key_skipped_count = 180000
internal_delete_skipped_count = 30000
internal_recent_skipped_count = 0
internal_merge_count = 0
write_wal_time = 0
get_snapshot_time = 0
get_from_memtable_time = 0
get_from_memtable_count = 0
get_post_process_time = 0
get_from_output_files_time = 0
seek_on_memtable_time = 1716
seek_on_memtable_count = 2
next_on_memtable_count = 210000
prev_on_memtable_count = 0
seek_child_seek_time = 8258
seek_child_seek_count = 3
seek_min_heap_time = 512
seek_internal_seek_time = 9508
find_next_user_entry_time = 12749803
write_pre_and_post_process_time = 0
write_memtable_time = 0
write_thread_wait_nanos = 0
write_scheduling_flushes_compactions_time = 0
db_mutex_lock_nanos = 0
db_condition_wait_nanos = 0
merge_operator_time_nanos = 0
write_delay_time = 0
read_index_block_nanos = 0
read_filter_block_nanos = 0
new_table_block_iter_nanos = 2013
new_table_iterator_nanos = 0
block_seek_nanos = 2651
find_table_nanos = 0
bloom_memtable_hit_count = 1
bloom_memtable_miss_count = 1
bloom_sst_hit_count = 1
bloom_sst_miss_count = 0
key_lock_wait_time = 0
key_lock_wait_count = 0
env_new_sequential_file_nanos = 0
env_new_random_access_file_nanos = 0
env_new_writable_file_nanos = 0
env_reuse_writable_file_nanos = 0
env_new_random_rw_file_nanos = 0
env_new_directory_nanos = 0
env_file_exists_nanos = 0
env_get_children_nanos = 0
env_get_children_file_attributes_nanos = 0
env_delete_file_nanos = 0
env_create_dir_nanos = 0
env_create_dir_if_missing_nanos = 0
env_delete_dir_nanos = 0
env_get_file_size_nanos = 0
env_get_file_modification_time_nanos = 0
env_rename_file_nanos = 0
env_link_file_nanos = 0
env_lock_file_nanos = 0
env_unlock_file_nanos = 0
env_new_logger_nanos = 0
get_cpu_nanos = 0
iter_next_cpu_nanos = 0
iter_prev_cpu_nanos = 0
iter_seek_cpu_nanos = 12756520
```
* iostat context:
```
thread_pool_id = 4
bytes_read = 0
bytes_written = 0
open_nanos = 0
allocate_nanos = 0
write_nanos = 0
read_nanos = 0
range_sync_nanos = 0
fsync_nanos = 0
prepare_write_nanos = 0
logger_nanos = 0
cpu_write_nanos = 0
cpu_read_nanos = 0
file_io_stats_by_temperature.hot_file_bytes_read = 0
file_io_stats_by_temperature.warm_file_bytes_read = 0
file_io_stats_by_temperature.cold_file_bytes_read = 0
file_io_stats_by_temperature.hot_file_read_count = 0
file_io_stats_by_temperature.warm_file_read_count = 0
file_io_stats_by_temperature.cold_file_read_count = 0
```
### Expected behavior
`Iterator->Seek()` is fast
### Actual behavior
`Iterator->Seek()` is slow
### Steps to reproduce the behavior
`none`
Contributor guide
Research direction
Start with the Iterator->Seek() entry point and compare the reported behavior with issue #5265. Reproduce the pseudo-code if possible, then use the supplied perf context counters to determine why deleted keys are skipped so slowly; done means identifying whether this is the same problem and documenting a confirmed fix or explanation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100