布隆過濾器 Bloom Filter
布隆過濾器，用來判斷一個(gè)元素是否在集合中困檩。
它的特點(diǎn)是節(jié)省空間祠挫，但是有誤判。有可能誤判某個(gè)不存在的元素在集合中（false positive）悼沿，但是不會(huì)誤判存在的元素不再集合中（false negative）等舔。RocksDB可能也正是因?yàn)檫@個(gè)特性，才選擇布隆過濾器來作為默認(rèn)filter的數(shù)據(jù)結(jié)構(gòu)糟趾。
簡單地說慌植，布隆過濾器提供了這樣的語義:
- 某個(gè)元素可能在集合中
- 某個(gè)元素一定不在集合中
一個(gè)布隆過濾器由兩部分組成
- 一個(gè)長度為m的位數(shù)組，各個(gè)為初始值都是0
- k個(gè)不同的hash函數(shù)
當(dāng)有一個(gè)新的元素x需要插入到集合中义郑，并記錄在布隆過濾器中時(shí)
- 通過k個(gè)hash函數(shù)蝶柿，計(jì)算k個(gè)hash值
- 在位數(shù)組中，將計(jì)算得到的k個(gè)hash值對應(yīng)的位置為1
查詢時(shí)
- 通過k個(gè)hash函數(shù)非驮，計(jì)算k各hash值
- 在位數(shù)組中交汤，查看k個(gè)hash值對應(yīng)的位是否都是1，如果都是1劫笙，則說明被查詢的數(shù)在集合中
上面所說的false negative就是因?yàn)橛幸欢ǖ母怕受皆瑫?huì)發(fā)生兩個(gè)不同的元素x和y星岗，通過k各hash函數(shù)得到的k個(gè)值是相同的。
下圖簡單說明了布隆過濾器的原理戒洼。
An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.
更詳細(xì)的說明請參考 Wikipedia article.
RocksDB中Bloom Filter的用法
- 每一個(gè)SST文件對應(yīng)一個(gè)Bloom Filter俏橘。
- 當(dāng)SST文件寫入到磁盤中時(shí)，創(chuàng)建一個(gè)Bloom Filter圈浇， 并作為SST文件的一部分寫到磁盤上寥掐。
- Bloom Filter只能通過key集合創(chuàng)建，而沒有合并的操作汉额。所以曹仗，當(dāng)合并兩個(gè)SST文件時(shí)，新文件的Bloom Filter是創(chuàng)建出來的蠕搜，而不是合并得到的怎茫。
- 當(dāng)打開一個(gè)SST文件時(shí)，會(huì)將對應(yīng)的Bloom Filter load到內(nèi)存中妓灌。當(dāng)關(guān)閉SST文件時(shí)轨蛤，將對應(yīng)的Bloom Filter從內(nèi)存中刪除。
Bloom Filter類圖
職責(zé)說明
- BlockBasedTableBuilder
用于構(gòu)建一個(gè)SST文件的數(shù)據(jù)結(jié)構(gòu), 持有一個(gè)Rep對象來保存各種選項(xiàng)和成員變量. 詳見<RocksDB. BlockBasedTable源碼分析> - Rep
用于持有各種選項(xiàng)和成員變量, 其中filter_builder成員用于構(gòu)建bloom filter. - FilterBlockBuilder
接口類, 定義了構(gòu)建filter的接口, 包括IsBlockBased, StartBlock, Add, Finish等接口. - BlockBasedFilterBlockBuilder
實(shí)現(xiàn)了FilterBlockBuilder的接口, 用于構(gòu)造BlockBasedFilterBlock. 持有一個(gè)FilterPolicy* 類型的成員policy_, 用于對一組key創(chuàng)建filter block. - FilterPolicy
接口類, 定義創(chuàng)建filter的接口, 包括CreateFilter, KeyMayMatch等接口. - BloomFilterPolicy
實(shí)現(xiàn)了接口類FilterPolicy, 用于對一組key創(chuàng)建filter block.
Bloom FIlter創(chuàng)建流程分析
filter_policy作為BlockBasedTableOption的一個(gè)選項(xiàng)虫埂，在打開數(shù)據(jù)庫對的時(shí)候指定
BlockBasedTableOptions table_options;
table_options.format_version = first_table_version;
table_options.filter_policy.reset(NewBloomFilterPolicy(10));
Options options = CurrentOptions();
options.table_factory.reset(NewBlockBasedTableFactory(table_options));
options.create_if_missing = true;
options.compression = comp;
// DestroyAndReopen(options);
NewBloomFilterPolicy函數(shù)返回Bloom Filter的實(shí)現(xiàn)對象
const FilterPolicy* NewBloomFilterPolicy(int bits_per_key,
bool use_block_based_builder) {
return new BloomFilterPolicy(bits_per_key, use_block_based_builder);
}
參數(shù)說明
- bits_per_key：位數(shù)組的長度祥山。推薦的長度是10，約有%1的誤判率掉伏。
- use_block_based_builder ：是否使用block based filter缝呕，和block based filter對應(yīng)的是full filter。默認(rèn)值是true斧散，即使用block based filter供常。
如第二節(jié)所說，Bloom Filter是在生成SST文件的時(shí)候創(chuàng)建的鸡捐，而SST文件使用的是TableBuilder栈暇。以BlockBasedTableBuilder為例，來看Bloom Filter是如何被創(chuàng)建箍镜，并寫入到SST文件中源祈。
BlockBasedTableBuilder并沒有直接使用filter_policy來創(chuàng)建filter，而是通過Rep的成員變量filter_builder色迂。
std::unique_ptr<FilterBlockBuilder> filter_builder;
// 在BlockBasedTableBuilder::Rep的構(gòu)造函數(shù)里香缺，創(chuàng)建一個(gè)filter block builder
if (skip_filters) {
filter_builder = nullptr;
} else {
filter_builder.reset(
CreateFilterBlockBuilder(_ioptions, table_options, p_index_builder));
}
// CreateFilterBlockBuilder的實(shí)現(xiàn)
FilterBlockBuilder* CreateFilterBlockBuilder(
const ImmutableCFOptions& opt, const BlockBasedTableOptions& table_opt,
PartitionedIndexBuilder* const p_index_builder) {
if (table_opt.filter_policy == nullptr) return nullptr;
FilterBitsBuilder* filter_bits_builder =
table_opt.filter_policy->GetFilterBitsBuilder();
if (filter_bits_builder == nullptr) {
return new BlockBasedFilterBlockBuilder(opt.prefix_extractor, table_opt);
} else {
...
}
}
創(chuàng)建filter block builder的時(shí)候，將table_options傳了進(jìn)去脚草，讓BlockBasedFilterBlockBuilder可以獲取打開數(shù)據(jù)庫時(shí)創(chuàng)建的filter policy指針赫悄。
BlockBasedFilterBlockBuilder::BlockBasedFilterBlockBuilder(
const SliceTransform* prefix_extractor,
const BlockBasedTableOptions& table_opt)
: policy_(table_opt.filter_policy.get()),
prefix_extractor_(prefix_extractor),
whole_key_filtering_(table_opt.whole_key_filtering),
prev_prefix_start_(0),
prev_prefix_size_(0) {
assert(policy_);
}
filter builder通過該指針為一組key集合創(chuàng)建bloom filter。
filter builder的使用分為三個(gè)步驟馏慨。
- StartBlock：為下一個(gè)block創(chuàng)建一個(gè)新的bloom filter埂淮。filter builder并不是只為整個(gè)table創(chuàng)建一個(gè)bloom filter。而是創(chuàng)建一組bloom filter写隶，每個(gè)block有一個(gè)bloom filter倔撞。實(shí)際上，在計(jì)算filter數(shù)量的時(shí)候慕趴，是按照每2KB data創(chuàng)建一個(gè)filter痪蝇。所以在實(shí)現(xiàn)上，一個(gè)block對應(yīng)兩個(gè)filter冕房，一個(gè)filter對應(yīng)4KB data躏啰，一個(gè)filter是空的。在后面貼的源碼中可以看到這一點(diǎn)耙册，之所這樣實(shí)現(xiàn)给僵，可能是其它類型的filter對這樣的行為有依賴。這樣就可以在TableBuilder調(diào)用Flush接口時(shí)觸發(fā)filter builder的創(chuàng)建filter動(dòng)作详拙，而Flush接口是4KB調(diào)用一次帝际。
創(chuàng)建一個(gè)新的bloom filter前，檢查之前是否有沒有生成filter的數(shù)據(jù)饶辙。判斷標(biāo)準(zhǔn)是比較上一個(gè)block filter的序號(hào)和已有 的filter數(shù)量蹲诀。
void BlockBasedFilterBlockBuilder::StartBlock(uint64_t block_offset) {
uint64_t filter_index = (block_offset / kFilterBase);
assert(filter_index >= filter_offsets_.size());
while (filter_index > filter_offsets_.size()) {
GenerateFilter();
}
}
正常情況下，兩者應(yīng)該相差2弃揽。即新來一個(gè)data block脯爪，一個(gè)data block是4KB，除以默認(rèn)的2KB矿微，即新增2個(gè)filter痕慢。但是在調(diào)用GenerateFilter接口時(shí)，并沒有將新的key set分為兩部分冷冗，而是在第一次創(chuàng)建filter時(shí)為所有新增的key創(chuàng)建了filter守屉，filter_offsets size + 1，這時(shí)filter_index比filter_offsets size少1蒿辙，但是start_和entries_成員已經(jīng)空了拇泛，GenerateFilter再被調(diào)用一次，filter_offsets增加一個(gè)和前一個(gè)一樣的offset值思灌，其他什么都不做俺叭。
void BlockBasedFilterBlockBuilder::GenerateFilter() {
const size_t num_entries = start_.size();
if (num_entries == 0) {
// Fast path if there are no keys for this filter
filter_offsets_.push_back(static_cast<uint32_t>(result_.size()));
return;
}
// Make list of keys from flattened key structure
start_.push_back(entries_.size()); // Simplify length computation
tmp_entries_.resize(num_entries);
for (size_t i = 0; i < num_entries; i++) {
const char* base = entries_.data() + start_[i];
size_t length = start_[i + 1] - start_[i];
// 這里只拷貝指針，沒有做字符串的拷貝
tmp_entries_[i] = Slice(base, length);
}
// Generate filter for current set of keys and append to result_.
filter_offsets_.push_back(static_cast<uint32_t>(result_.size()));
policy_->CreateFilter(&tmp_entries_[0], static_cast<int>(num_entries),
&result_);
tmp_entries_.clear();
entries_.clear();
start_.clear();
prev_prefix_start_ = 0;
prev_prefix_size_ = 0;
}
在后面會(huì)詳細(xì)分析policy_->CreateFilter(&tmp_entries_[0], static_cast<int>(num_entries), &result_);的實(shí)現(xiàn)泰偿。
- Add
在TableBuilder中熄守，每插入一個(gè)key value對，就會(huì)將key插入到filter builder中。
然后在Flush時(shí)為之前插入的所有key創(chuàng)建filter裕照。
void BlockBasedTableBuilder::Add(const Slice& key, const Slice& value) {
...
// Note: PartitionedFilterBlockBuilder requires key being added to filter
// builder after being added to index builder.
if (r->filter_builder != nullptr) {
r->filter_builder->Add(ExtractUserKey(key));
}
...
}
對于PartitionedFilterBlockBuilder（即我們現(xiàn)在分析的filter builder策略）攒发，Add會(huì)調(diào)用AddPrefix接口來插入key的前綴。
因?yàn)閑ntries_是一個(gè)字符串類型晋南，所有key插入時(shí)都是直接append到字符串末尾惠猿，同時(shí)用一個(gè)vector<int>型的成員變量start_來記錄每個(gè)key在entries_中的offset。所以在取下一個(gè)key時(shí)负间，要先通過兩個(gè)成員變量prev_prefix_start_和prev_prefix_size_來確定下一個(gè)key的偏移量偶妖。
只有在key的prefix不存在時(shí)，才會(huì)插入政溃。
inline void BlockBasedFilterBlockBuilder::AddPrefix(const Slice& key) {
// get slice for most recently added entry
Slice prev;
if (prev_prefix_size_ > 0) {
prev = Slice(entries_.data() + prev_prefix_start_, prev_prefix_size_);
}
Slice prefix = prefix_extractor_->Transform(key);
// insert prefix only when it's different from the previous prefix.
if (prev.size() == 0 || prefix != prev) {
start_.push_back(entries_.size());
prev_prefix_start_ = entries_.size();
prev_prefix_size_ = prefix.size();
entries_.append(prefix.data(), prefix.size());
}
}
- Finish
當(dāng)TableBuilder創(chuàng)建完成后趾访，在TableBuilder的Finish接口中會(huì)調(diào)用filter builder的Finish接口來將offset數(shù)組append到創(chuàng)建的filter結(jié)果所存的result_字符串中，然后調(diào)用WriteRawBlock寫入到SST文件中董虱。
// 調(diào)用的地方
Status BlockBasedTableBuilder::Finish() {
...
// Write filter block
if (ok() && r->filter_builder != nullptr) {
Status s = Status::Incomplete();
while (s.IsIncomplete()) {
Slice filter_content = r->filter_builder->Finish(filter_block_handle, &s);
assert(s.ok() || s.IsIncomplete());
r->props.filter_size += filter_content.size();
WriteRawBlock(filter_content, kNoCompression, &filter_block_handle);
}
}
...
}
用于拼接的Finish方法實(shí)現(xiàn)
Slice BlockBasedFilterBlockBuilder::Finish(const BlockHandle& tmp,
Status* status) {
// In this impl we ignore BlockHandle
*status = Status::OK();
if (!start_.empty()) {
GenerateFilter();
}
// Append array of per-filter offsets
const uint32_t array_offset = static_cast<uint32_t>(result_.size());
for (size_t i = 0; i < filter_offsets_.size(); i++) {
PutFixed32(&result_, filter_offsets_[i]);
}
PutFixed32(&result_, array_offset);
result_.push_back(kFilterBaseLg); // Save encoding parameter in result
return Slice(result_);
}
到這里我們看到filter block展開之后的結(jié)構(gòu)如下
[filter 0]
[filter 1]
[filter 2]
...
[filter N-1]
[offset of filter 0] : 4 bytes
[offset of filter 1] : 4 bytes
[offset of filter 2] : 4 bytes
...
[offset of filter N-1] : 4 bytes
[offset of beginning of offset array] : 4 bytes
lg(base) : 1 byte
filter builder通過調(diào)用BloomFilterPolicy的CreateFilter接口來創(chuàng)建filter扼鞋。
CreateFilter的實(shí)現(xiàn)包括一下幾步：
- 計(jì)算下一個(gè)filter占用的位數(shù)。為了保證準(zhǔn)確率空扎，最小值是64位藏鹊。
- 確定下一個(gè)filter在dst中的起始偏移位置。resize之后转锈，起始偏移位置到dst的末尾盘寡，就是一個(gè)長度至少為64bit的bit數(shù)組。
- 對每一個(gè)key撮慨，計(jì)算得到num_probes_個(gè)hash值竿痰，對bits取余，然后將對應(yīng)bit位至1.
這樣就完成了一個(gè)filter的創(chuàng)建砌溺。
virtual void CreateFilter(const Slice* keys, int n,
std::string* dst) const override {
// Compute bloom filter size (in both bits and bytes)
size_t bits = n * bits_per_key_;
// For small n, we can see a very high false positive rate. Fix it
// by enforcing a minimum bloom filter length.
if (bits < 64) bits = 64;
size_t bytes = (bits + 7) / 8;
bits = bytes * 8;
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);
dst->push_back(static_cast<char>(num_probes_)); // Remember # of probes
char* array = &(*dst)[init_size];
for (size_t i = 0; i < (size_t)n; i++) {
// Use double-hashing to generate a sequence of hash values.
// See analysis in [Kirsch,Mitzenmacher 2006].
uint32_t h = hash_func_(keys[i]); // 計(jì)算hash 值
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < num_probes_; j++) {
const uint32_t bitpos = h % bits;
array[bitpos/8] |= (1 << (bitpos % 8)); // 將對應(yīng)bit位標(biāo)1
h += delta; // 相當(dāng)于更換hash函數(shù)
}
}
}
至此是BloomFilter創(chuàng)建相關(guān)流程分析影涉。可以用類似的思路來分析讀流程中规伐，BloomFilter是如何生效的蟹倾。
小結(jié)
BloomFilter標(biāo)識(shí)了某個(gè)key是否可能存在對應(yīng)的SST文件中。BloomFilter對于讀請求的優(yōu)化效果明顯, 不需要掃描整個(gè)SST文件, 因?yàn)樵诖蜷_SST文件時(shí), 會(huì)將Bloom Filter加載到內(nèi)存中, 通過掃描filter即可判斷某個(gè)key是否可能存在該SST文件中猖闪。
參考資料
https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
