google / google/leveldb

Invalid key may not be dropped during DoCompactionWork

Open
#898 5 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.