Invalid key may not be dropped during DoCompactionWork
- Dominant language
- C++
- Stars
- 39.4k
- Forks
- 8.2k
- PR merge metrics
- No merged PRs in 30d
Description
In the `Status DBImpl::DoCompactionWork(CompactionState* compact)` we have codes below to clean the redundant keys:
```c++
if (!has_current_user_key ||
user_comparator()->Compare(ikey.user_key, Slice(current_user_key)) !=
0) {
// First occurrence of this user key
current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());
has_current_user_key = true;
last_sequence_for_key = kMaxSequenceNumber;
}
if (last_sequence_for_key <= compact->smallest_snapshot) {
// Hidden by an newer entry for same user key
drop = true; // (A)
} else if (ikey.type == kTypeDeletion &&
ikey.sequence <= compact->smallest_snapshot &&
compact->compaction->IsBaseLevelForKey(ikey.user_key)) {
// For this user key:
// (1) there is no data in higher levels
// (2) data in lower levels will have larger sequence numbers
// (3) data in layers that are being compacted here and have
// smaller sequence numbers will be dropped in the next
// few iterations of this loop (by rule (A) above).
// Therefore this deletion marker is obsolete and can be dropped.
drop = true;
}
```
From my understanding of the above codes, if there are multi user keys appears, with sequence numbers are not greater than smallest snapshot. Then only the user key with sequence number most closed to smallest snapshot will be kept, while others will be dropped (Similar logic for deletion type, too). It works fine definitely. But consider such scenario:
```
Put('key', 'v1'); \\ seq 0
Put('key', 'v2'); \\ seq 1
GetSnapshot(); \\ snapshot 0
Put('key', 'v3'); \\ seq 2
Put('key', 'v4'); \\ seq 3
GetSnapshot(); \\ snapshot 1, assume it is the latest snapshot
......
```
What we truly need is the <'key', 'v2'> (for snapshot 0) , <'key', 'v4'> (for snapshot 1), and the latest Put/Delete of 'key'. However, after running DoCompactionWork, only <'key', 'v1'> be dropped, while the other invalid kv pairs (seq 2, and so on) are still stored in LSM-tree, wasting disk space.
I wonder if there exists an better garbage collection algorithm to avoid such problem.
Contributor guide
Assessment
This issue has not been assessed yet.