User comparator is incompatible with hash memtable and with bloom filter
- Dominant language
- C++
- Stars
- 32.1k
- Forks
- 6.9k
- Avg merge
- 32m
- Merged PRs (30d)
- 1
Description
When setting a bloom filter with a user comparator, a `Get()` with a different key representation fails even though it is equivalent according to the user comparator. This happens because the bloom filter hashes the key bytes that were used in the `Put()` call.
The same happens when using a hash-based memtable, because only the key representation that was used in the `Put()` is hashed as a key for the memtable.
### Expected behavior
`Get()` should succeed with a different key representation if the user comparator considers the two representations equal.
### Actual behavior
`Get()` fails with `Status::NotFound()`.
### Steps to reproduce the behavior
```c++
#include
#include
#include
#include
#include
#include
using namespace rocksdb;
int main(int argc, char const *argv[])
{
class TruncatingComparator : public Comparator {
public:
const char* Name() const override { return "TruncatingComparator"; }
int Compare(const Slice& a, const Slice& b) const override {
return TruncateKey(a).compare(TruncateKey(b));
}
void FindShortestSeparator(std::string* s, const Slice& l) const override {}
void FindShortSuccessor(std::string* key) const override {}
private:
static Slice TruncateKey(const Slice& k) {
return k.size() < 4 ? k : Slice(k.data(), 4);
}
};
Options options;
options.create_if_missing = true;
TruncatingComparator comparator;
options.comparator = &comparator;
options.allow_concurrent_memtable_write = false;
options.memtable_factory.reset(NewHashSkipListRepFactory(1024 * 1024));
BlockBasedTableOptions table_options;
table_options.filter_policy.reset(NewBloomFilterPolicy(12));
options.table_factory.reset(NewBlockBasedTableFactory(table_options));
DB* db = nullptr;
Status s = DB::Open(options, "/tmp/rocksdb_comparator_db", &db);
assert(s.ok());
const std::string key1 = "keys1";
const std::string key2 = "keys2";
const std::string value = "value";
assert(comparator.Compare(key1, key2) == 0);
assert(db->Put(WriteOptions(), key1, value).ok());
{
PinnableSlice result;
assert(db->Get(ReadOptions(), db->DefaultColumnFamily(), key1, &result).ok());
assert(result == value);
// BUG: Get with a different byte representation fails at the hash-based memtable level
s = db->Get(ReadOptions(), db->DefaultColumnFamily(), key2, &result);
assert(s.ok());
assert(result == value);
}
assert(db->Flush(FlushOptions()).ok());
{
PinnableSlice result;
assert(db->Get(ReadOptions(), db->DefaultColumnFamily(), key1, &result).ok());
assert(result == value);
// BUG: Get with a different byte representation fails at the bloom filter level
s = db->Get(ReadOptions(), db->DefaultColumnFamily(), key2, &result);
assert(s.ok());
assert(result == value);
}
delete db;
return 0;
}
```
Contributor guide
Assessment
This issue has not been assessed yet.