版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。
上一章中詳細講解了
table
中的
data block
的結構以及涉及的源碼，本章中将講解
table
結構中的
meta block
table
table
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>
先說說在meta block
中的作用table
一個meta block對應一個data block，meta block的作用是快速判斷對應的data block中是否存在某個key，詳情可以搜尋“Bloom Filter”
原理是這樣的，首先需要定義一個大的bitmap，實際就是一個字元串，bitmap中初始時每一位都是0，當往data block中添加key時，會根據這個key值算出一組hash值，hash值對bitmap位數取模後将bitmap中對應的位置設定為1；當需要查詢data block中是否存在某個key時，隻需通過這個key計算一組hash值，然後檢視hash值在bitmap中對應的位置的值是否為1，隻有有一個位置不為1，說明這個data block中不存在這個key
上面所說的算法中會存在hash沖突，如果bitmap中已經存了兩個key
key1 計算出的位置為 [1,3]
key2 計算出的位置為 [2,4]
當我們要查詢的
key3
計算出來的位置為[1,4]時，在
bitmap
中[1,4]兩個位置都是1，這個隻能說明data block中有可能存在key3，是以說bitmap是用來快速判斷key不在data block中，我們需要做的是使出現誤判的機率降到最低，可以得到一個公式
假設一個key要對應k個hash值，總共有n個key，bitmap的位數為m，那麼出現誤判的機率為
(1-(1-1/m)^(kn))^k
上面的公式是怎麼得到的呢？
假設我們現在要在bitmap中判斷某個key是否存在，先要算出k個hash值，而這k個hash值對應的位置上面恰恰都有1的機率是多少呢
假設一個位置上面恰恰為1的機率為p，那麼k個位置上面都為1的機率為p^k
p要怎麼得到呢？
p代表的是一個位置上面恰恰為1的機率，我們可以先得到這個位置不為1的機率為q，那麼，p=（1-q）
q要怎麼得到呢？
q代表的是一個位置上面不為1的機率，說明n個key在計算k個hash的時候都沒有落在這個點上，一次沒有落在這個點上的機率為1-1/m，kn次沒有落在這個點上的機率為(1-1/m)(kn)，那麼kn次落在這個點上的機率為1-(1-1/m)(kn)，一共有k個點，k個點都是1的機率就為(1-(1-1/m)(kn))k
好多年不搞數學，上面的公式解釋的好痛苦（-_-!!!）
為了保證誤判的機率最低，如果m和n固定的話，可以得到k的最優解為k=m/n*ln2，我也不知道怎麼算出來的，網上抄的（-_-!!!）
上面說了這麼多理論，接下來要開始撸代碼啦
搞懂 meta block
1 table/filter_block.h // [非常重要|難度:4 級] filter_block的結構
2 table/filter_block.cc
3 include/leveldb/filter_policy.h // [重要|難度:2級] 過濾政策
4 util/bloom.cc // [重要|難度:2級] 過濾政策具體實作
filter_policy.h
先介紹
filter_policy
，中文翻譯為過濾政策，這個地方隻是定義了一個接口，使用者可以重寫這個接口
class FilterPolicy {
public:
virtual ~FilterPolicy();
virtual const char* Name() const = 0; //傳回目前政策的名字
// dst就是上面講的bitmap，n表示一個key在bitmap中占多少位，這個函數就是通過傳進來的keys，來建構一個bitmap
virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0;
// bitmap中有沒有key
virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
};
// Return a new filter policy that uses a bloom filter with approximately
// the specified number of bits per key. A good value for bits_per_key
// is 10, which yields a filter with ~ 1% false positive rate.
//
// Callers must delete the result after any database that is using the
// result has been closed.
//
// Note: if you are using a custom comparator that ignores some parts
// of the keys being compared, you must not use NewBloomFilterPolicy()
// and must provide your own FilterPolicy that also ignores the
// corresponding parts of the keys. For example, if the comparator
// ignores trailing spaces, it would be incorrect to use a
// FilterPolicy (like NewBloomFilterPolicy) that does not ignore
// trailing spaces in keys.
extern const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
}
bloom.cc
filter_policy
的具體實作
class BloomFilterPolicy : public FilterPolicy {
private:
size_t bits_per_key_; // 前文中講到的n/m，bitmap的位數除以key的個數
size_t k_; // 前文中講到的k，一個key在bitmap中要算出多少個hash
public:
explicit BloomFilterPolicy(int bits_per_key)
: bits_per_key_(bits_per_key) {
// 構造方法，直接給bits_pre_key_指派
// 根據前文講到的k的最優解，k=n/m * ln2，ln2=~ 0.69，是以k的最優解為bits_per_key*0.69
// We intentionally round down to reduce probing cost a little bit
k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
// k_肯定不能小于1，如果k_太大的話，每次計算hash會消耗計算資源，劃不來，這個地方對誤判率和計算資源做了權衡，k_最大為30
if (k_ < 1) k_ = 1;
if (k_ > 30) k_ = 30;
}
// 過濾政策的名稱
virtual const char* Name() const {
return "leveldb.BuiltinBloomFilter2";
}
// dst就是上面講的bitmap，n表示一個key在bitmap中占多少位，這個函數就是通過傳進來的keys，來建構一個bitmap
virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
// 計算出bitmap有多少位
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.
// 如果n很小的話，誤判率會很高，是以設定了一個最小值，64位，也就是8個位元組
if (bits < 64) bits = 64;
// 加上7然後除以8，隻要不是整除，就會進一位
size_t bytes = (bits + 7) / 8;
// 算出實際的bitmap有多少位
bits = bytes * 8;
const size_t init_size = dst->size();
// 把bitmap放到dst後面，并用0填充，dst存放不止一個bitmap
dst->resize(init_size + bytes, 0);
// 将k_添加到dst的末尾，k_表示的是一個key算多少次hash
dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
// init_size是dst的初始長度，array指向目前bitmap的起始位置
char* array = &(*dst)[init_size];
// 又到了劃重點的時間，這個地方就是将key轉為hash值，然後将bitmap對應的點這是為1
// n是key的個數
for (int i = 0; i < n; i++) {
// Use double-hashing to generate a sequence of hash values.
// See analysis in [Kirsch,Mitzenmacher 2006].
// 關于bloomHash這裡就不多解釋了，有時間我會專門寫一篇關于hash的文章
// 這裡隻需要知道BloomHash就是闖進去一個key，傳回一個hash值，h就是傳回的hash值
uint32_t h = BloomHash(keys[i]);
// (h >> 17) | (h << 15) 這個和hash算法有關，通過一系列的位運算來随機種子
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
// k_表示的是一個key算多少次hash，如果用BloomHash來算hash的話，計算量太大，這裡用到了一個簡單的方法
// 就是前幾行中得到的随機種子再與h相加
for (size_t j = 0; j < k_; j++) {
// 得到要修改的位在第幾個位元組上
const uint32_t bitpos = h % bits;
// 取模 然後位移 再或上 定位到的位元組
array[bitpos/8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
// 判斷bitmap中有沒有key
virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
const size_t len = bloom_filter.size();
if (len < 2) return false;
const char* array = bloom_filter.data();
// len-1是因為bitmap的最後一位存放的是k_，也就是一個key要計算多少次hash
const size_t bits = (len - 1) * 8;
// 得到最後一個自己裡面存放的值
const size_t k = array[len-1];
if (k > 30) {
// k的計算方法是,k=m/n*ln2，m表示bitmap的位數，n表示key的個數，如果k大于30，說明key很少
// 既然key很少，周遊一遍data block也不會很耗資源
// 但是得到30多個hash的話就比較費資源了，那還不如認為目前data block中有可能有這個key
return true;
}
// 下面的代碼就和CreateFilter中的差不多了，隻要找到一個hash值對應的點不為1，那就說明key在這個data block中不存在
uint32_t h = BloomHash(key);
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < k; j++) {
const uint32_t bitpos = h % bits;
if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
h += delta;
}
return true;
}
};
}
// 暫時還不知道有啥用，後面補充
const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
return new BloomFilterPolicy(bits_per_key);
}
上面介紹一下bloom的具體實作，現在來介紹在table中的filter block怎麼建構了，這個地方的命名我個人覺得有點奇怪，block.h中介紹的是block的結構，真正來建構一個block的類是block_builder，而filter_block.h就是用來建構filter_block的
filter_block.h中有兩個類，一個是建構一個filter_block的，還有一個是來解析filter_block的
// filter_block.h
// filter block建構類，一個FilterBlockBuilder對象并不是隻存放一個
class FilterBlockBuilder {
public:
explicit FilterBlockBuilder(const FilterPolicy*);
// 開始建構filter block
void StartBlock(uint64_t block_offset);
// 在table添加key的時候，有一個地方會專門存放key，當一個data block完成時，就會用存儲的key來建構filter block
void AddKey(const Slice& key);
// 當一個filter block建構完成後，還需要做一些處理
Slice Finish();
private:
// 真正建構filter block的地方
void GenerateFilter();
// 上面講了那麼多就是說的這個，裡面有k_、bits_per_key_、filter block中是否存在key的方法和建立filter block的方法
const FilterPolicy* policy_;
// 把key通過追加的方式全部放在keys_中
std::string keys_; // Flattened key contents
// 存放了每個key的索引，和keys_一起用可以得到每個key
std::vector<size_t> start_; // Starting index in keys_ of each key
// 真正放bitmap的地方，table裡面所有data block的bitmap全部都在這裡面喲
std::string result_; // Filter data computed so far
// 臨時存放keys的地方，後面會提到
std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument
// 和start_類似，用來存放每個bitmap的索引，其實就是在result_中的起始位址，和result一起使用可以得到具體的bitmap
std::vector<uint32_t> filter_offsets_;
// 隻允許引用，不允許隐式構造
FilterBlockBuilder(const FilterBlockBuilder&);
void operator=(const FilterBlockBuilder&);
};
// filter block解析類
class FilterBlockReader {
public:
// REQUIRES: "contents" and *policy must stay live while *this is live.
FilterBlockReader(const FilterPolicy* policy, const Slice& contents);
bool KeyMayMatch(uint64_t block_offset, const Slice& key);
private:
const FilterPolicy* policy_;
const char* data_; // Pointer to filter data (at block-start)
const char* offset_; // Pointer to beginning of offset array (at block-end)
size_t num_; // Number of entries in offset array
size_t base_lg_; // Encoding parameter (see kFilterBaseLg in .cc file)
};
// filter_block.cc
static const size_t kFilterBaseLg = 11;
static const size_t kFilterBase = 1 << kFilterBaseLg;
// 構造方法，policy_裡面有k_、bits_per_key_、filter block中是否存在key的方法和建立filter block的方法
FilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy)
: policy_(policy) {
}
// 開始建構filter block，上一章我了解錯了，不是一個data block建構一個filter block，而是2k的資料建構一個filter block
/*
如果這一塊的邏輯讓我來寫的話，邏輯應該是這樣的
當一個data block建構完成後，調用StartBlock方法，配置設定一個的bitmap，
通過policy_裡面的CreateFilter方法将這個data block裡面的keys轉換成bitmap的對應的位；
上面的是寫入bitmap，怎麼讀取這個bitmap呢？
一個data block對應一個bitmap，如果要讀bitmap，就需要知道table中bitmap對應的是第k個data block
當周遊table裡面的data block時，就需要記錄k值
然後得到第k個bitmap
*/
/*
上面是我個人的邏輯，再看看大神的邏輯
上面我們是通過得到是第k個data block進而得到bitmap
大神的方法通過data block在table中的偏移量來得到是第幾個bitmap，方法如下
直覺上了解是每2k的data block就配置設定一個bitmap，通過data block的偏移量，然後除以2，就可以得到是第幾個bitmap了
那問題了，data block的大小門檻值是2k，但并不是說data block大小就是2k，如果data block中存放了一個7k的key-value,
那在得到bitmap的時候怎麼将這個data block分成多個2k呢？
【這裡我們補充一個變量filter_offsets_，它是用來存放每個bitmap的偏移量，如果要得到第n個bitmap，
隻需filter_offsets_[n]，得到第n個bitmap的偏移，然後result_+filter_offsets_[n]，就可以得到bitmap了】
還是上面7k的例子，如果除以2，需要配置設定3個bitmap，實際上第一個bitmap就是這個data block的索引了
那剩下的兩個bitmap呢？剩下的兩個bitmap是空的，這兩個bitmap在filter_offsets_中指向的還是第一個bitmap的位置
相當于在filter_offsets_中占了兩個位置，實際存放bitmap的result_啥也沒存
如果第1個data block大小是7k，第2個data block大小是5k
那麼第1個data block在table中的偏移量為7，7/2=3,在filter_offsets_中會有3條記錄，不過存放的都是第一個bitmap的偏移
第2個data block在table中的偏移量為12，12/2=6,在filter_offsets_中會加2條記錄，2條記錄存放的都是第二個bitmap的偏移
現在得到第1個data block的bitmap，偏移量/2=3，filter_offsets_的第3條記錄指向的是第1個bitmap的偏移，擷取成功
得到第2個data block的bitmap，偏移量/2=6，filter_offsets_的第6條記錄指向的是第2個bitmap的偏移，擷取成功
*/
void FilterBlockBuilder::StartBlock(uint64_t block_offset) {
// filter_index bitmap索引個數
uint64_t filter_index = (block_offset / kFilterBase);
assert(filter_index >= filter_offsets_.size());
// 隻要bitmap索引個數比目前索引個數大，就一直建構filter block，實際隻有第一次循環的時候在result_中放了一個bitmap
// 其他循環都隻是在filter_offsets_中存放第一次循環中得到的bitmap的偏移
while (filter_index > filter_offsets_.size()) {
GenerateFilter();
}
}
// 将key放在keys_中，将key的大小放在start_中，建構filter data的時候用到
void FilterBlockBuilder::AddKey(const Slice& key) {
Slice k = key;
start_.push_back(keys_.size());
keys_.append(k.data(), k.size());
}
// finish是在table建構時調用的
Slice FilterBlockBuilder::Finish() {
if (!start_.empty()) {
GenerateFilter();
}
// Append array of per-filter offsets
// 當所有bitmap全部建構完成後，将所有的偏移量放到result_中
const uint32_t array_offset = result_.size();
for (size_t i = 0; i < filter_offsets_.size(); i++) {
PutFixed32(&result_, filter_offsets_[i]);
}
// 最後再将所有bitmap的大小放到result_的後面
PutFixed32(&result_, array_offset);
// 将 2k 這個數字放在最後
// 那麼在解析result_的時候，讀取最後一個位元組，表示data block按多少k分割
// 讀取倒數第5到倒數第2個位元組（size），表示所有bitmap的大小
// result_+size就可以位元組偏移到記錄偏移點的地方，這有就可以一步一步解析了
result_.push_back(kFilterBaseLg); // Save encoding parameter in result
return Slice(result_);
}
// 劃重點
void FilterBlockBuilder::GenerateFilter() {
// 得到目前block中key的個數
const size_t num_keys = start_.size();
// 如果沒有key，說明之前已經建立過bitmap了，現在隻需要把目前偏移量放到filter_offsets_中
if (num_keys == 0) {
// Fast path if there are no keys for this filter
filter_offsets_.push_back(result_.size());
return;
}
// Make list of keys from flattened key structure
// start_存放的是所有key的起始位置，下面一步是把結束的位置也放進去
start_.push_back(keys_.size()); // Simplify length computation
// tmp_keys_上面再定義的時候沒有解釋，這裡詳細解釋，就是用來存放目前data block中的key的，不過是以slice的形式存儲的
tmp_keys_.resize(num_keys);
for (size_t i = 0; i < num_keys; i++) {
const char* base = keys_.data() + start_[i];
size_t length = start_[i+1] - start_[i];
tmp_keys_[i] = Slice(base, length);
}
// Generate filter for current set of keys and append to result_.
// 記錄result_的大小，實際是記錄下一個filter block的起始位置
filter_offsets_.push_back(result_.size());
// 得到filter block後放在result_裡面
policy_->CreateFilter(&tmp_keys_[0], static_cast<int>(num_keys), &result_);
tmp_keys_.clear();
keys_.clear();
start_.clear();
}
// 下面就是filter block的解析過程了
FilterBlockReader::FilterBlockReader(const FilterPolicy* policy,
const Slice& contents)
: policy_(policy),
data_(NULL),
offset_(NULL),
num_(0),
base_lg_(0) {
size_t n = contents.size();
// contents的大小不可能小于5，最後一個位元組記錄kFilterBaseLg，然後4個位元組記錄所有bitmap的大小
if (n < 5) return; // 1 byte for base_lg_ and 4 for start of offset array
// 這個在上面說過，最後一個位元組是kFilterBaseLg
base_lg_ = contents[n-1];
// 然後得到倒數第5到倒數第2個位元組，轉為uint32，就可以得到所有bitmap的大小
uint32_t last_word = DecodeFixed32(contents.data() + n - 5);
if (last_word > n - 5) return;
data_ = contents.data();
// offset_就是記錄偏移量的位置了
offset_ = data_ + last_word;
// num_記錄有多少個偏移量，總大小減去最後5個位元組，然後再減去bitmap的大小，剩下的就全是記錄偏移量了
// 一個偏移量占4個位元組，(n - 5 - last_word) / 4 就表示有多少個偏移量了
num_ = (n - 5 - last_word) / 4;
}
// 通過block的偏移量來判斷 key 在不在這個block中
bool FilterBlockReader::KeyMayMatch(uint64_t block_offset, const Slice& key) {
// block_offset 往右移11位，意思就是除以2k，也就是得到是第幾個bitmap
uint64_t index = block_offset >> base_lg_;
if (index < num_) {
// 然後再通過bitmap的偏移量得到真正的bitmap
uint32_t start = DecodeFixed32(offset_ + index*4);
uint32_t limit = DecodeFixed32(offset_ + index*4 + 4);
if (start <= limit && limit <= static_cast<size_t>(offset_ - data_)) {
Slice filter = Slice(data_ + start, limit - start);
// 判斷bitmap中有沒有key
return policy_->KeyMayMatch(key, filter);
} else if (start == limit) {
// Empty filters do not match any keys
return false;
}
}
return true; // Errors are treated as potential matches
}
【作者：antonyxu https://antonyxux.github.io/ 】
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)