databasekey-value-storeleveldbrocksdbbloom-filter

How does LevelDB handle sequence number in bloom filter?


I have read the source code of LevelDB. I found that it uses internal key when calling AddKey() of filter_block. If we call Get() later, it will construct a lookup key using the last sequence number, and the key will be passed to function KeyMayMatch(). But the last sequence number is different from the sequence number used in AddKey(), so why can bloom filter return the right result?


Solution

  • In RocksDB, to create bloom you have to specify the number of bytes per key to be added to bloom. Although the Internal key is a combination of user key and sequenceNumber, the latter will be stripped off while creating filter. The sequence number will not be a part of the key used to construct the bloom. So when you call Get() the given key is passed to KeyMayMatch(), if the bloom filter results true, then rocksdb scans the files to fetch the key (if it is present. Remember bloom filter can give false positives). If the bloom results false, the key is not present in the DB.