facebook / facebook/rocksdb

User comparator is incompatible with hash memtable and with bloom filter

Open
#8,482 0 comments 0 reactions 1 assignee Claimed by @pdillinger View on GitHub
question up-for-grabs
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

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.