facebook / facebook/rocksdb

iterator `Seek` slowdown after delete many keys

Open
#10,300 8 comments 0 reactions 0 assignees View on GitHub
performance question
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.