3.1 Bloom Filter
3.1.1 基本概念
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的蚀同。當(dāng)一個(gè)元素被加入集合時(shí)缅刽，通過K個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的K個(gè)點(diǎn)，把它們置為1唤崭。檢索時(shí)拷恨，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢元素一定不在谢肾；如果都是1，則被檢元素很可能在小泉。
相比于其它的數(shù)據(jù)結(jié)構(gòu)芦疏，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢冕杠。布隆過濾器存儲空間和插入/查詢時(shí)間都是常數(shù)O(k)。
但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯酸茴，誤算率是其中之一分预。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加薪捍。但是如果元素?cái)?shù)量太少笼痹，則使用散列表足矣。另外酪穿，一般情況下不能從布隆過濾器中刪除元素凳干，因?yàn)槲覀儫o法得知指定position上被那些key映射。
假設(shè) Hash 函數(shù)以等概率條件選擇并設(shè)置 Bit Array 中的某一位被济，m 是該位數(shù)組的大小救赐，n是數(shù)據(jù)個(gè)數(shù)，k 是 Hash 函數(shù)的個(gè)數(shù)只磷，對于給定的m经磅，n，如何選擇Hash函數(shù)個(gè)數(shù) k 由以下公式確定：k = ln2 * m/n = 0.7 * m/n钮追。此時(shí)誤報(bào)率為：2^-k = 0.6185^m/n预厌。當(dāng)m/n=10時(shí)，誤報(bào)率約為0.8%元媚。
關(guān)于詳細(xì)證明請參見布隆過濾器 (Bloom Filter) 詳解轧叽。
3.1.2 LevelDB版本實(shí)現(xiàn)
LevelDB將bloom filter做為內(nèi)置過濾器，供用戶選擇使用惠毁，其核心算法代碼在bloom.cc中犹芹。
3.1.2.1 K值選擇
根據(jù)前面的描述，最佳k值為0.7m/n鞠绰，leveldb中實(shí)現(xiàn)基本一致：
class BloomFilterPolicy : public FilterPolicy
{
private:
size_t bits_per_key_;
size_t k_;
public:
explicit BloomFilterPolicy(int bits_per_key)
: bits_per_key_(bits_per_key)
{
// 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)
if (k_ < 1)
k_ = 1;
if (k_ > 30)
k_ = 30;
}
......
};
LevelDB將m/n命名為bits_per_key腰埂，稍有點(diǎn)不同的是leveldb中的k值是向下取整的。作者的解釋是為了減少檢測碰撞所需的時(shí)間蜈膨，但這樣增大了誤報(bào)率屿笼，整體性能上應(yīng)該是要比非向下取整后要差的。
K值得取值范圍為1-30翁巍，作者推薦值為10(參見測試程序)驴一，此時(shí)的誤報(bào)率小于1%(約為0.8%)。
3.1.2.2 布隆插入
布隆位組構(gòu)建邏輯如下：
class BloomFilterPolicy : public FilterPolicy
{
......
virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const
{
//動態(tài)計(jì)算布隆過濾器的位組大小(n * m /n = m)
// 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);
//保存本次生成布隆位組時(shí)的K值
dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
char *array = &(*dst)[init_size];
//為每個(gè)key值hash出key個(gè)位置并置1
for (int i = 0; i < n; i++)
{
//使用double hashing計(jì)算出K個(gè)position而非采用K中hash算法
// Use double-hashing to generate a sequence of hash values.
// See analysis in [Kirsch,Mitzenmacher 2006].
uint32_t h = BloomHash(keys[i]);
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;
array[bitpos / 8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
......
}
LevelDB中的布隆位組不是預(yù)先設(shè)定好灶壶，而是動態(tài)生成的肝断。對一批key值設(shè)置一個(gè)布隆位組，由此保證誤報(bào)率一直處于預(yù)期之內(nèi)。另外胸懈，位組借用了std::string實(shí)現(xiàn)担扑，并在位組最后額外保存了生成該布隆位組時(shí)采用的K值。
但有一點(diǎn)很奇怪趣钱，程序在resize之后緊接著做了一次push_back涌献，這可能導(dǎo)致額外的一次內(nèi)存分配、拷貝動作首有，對于leveldb這種對性能追求極致的程序并不應(yīng)該燕垃，來看測試程序:
#include <iostream>
#include <string>
int main()
{
std::string name;
name = "hello";
name.resize(63,100);
std::cout << name.capacity() << std::endl;
name.push_back((char)97);
std::cout << name.capacity() << std::endl;
std::cout << "Hello, " << name << "!\n";
}
采用g++ -O2命令編譯并運(yùn)行該程序結(jié)果
desmondwangdeMacBook-Pro:demo desmondwang$ g++ -O2 a.cpp
desmondwangdeMacBook-Pro:demo desmondwang$ ./a.out
63
127
Hello, hellodddddddddddddddddddddddddddddddddddddddddddddddddddddddddda!
最后，LevelDB并沒有真正的使用K個(gè)hash算法計(jì)算position井联，而是采用double hashing卜壕，公式如下：h(i,k)=(h1(k)+i?h2(k))mod|T|。LevelDB中低矮，h1(k)為根據(jù)hash算法計(jì)算出來的結(jié)果印叁，而h2(k)為delta = (h >> 17) | (h << 15)。
3.1.2.3 布隆過濾
布隆過濾計(jì)算邏輯如下：
class BloomFilterPolicy : public FilterPolicy
{
......
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();
const size_t bits = (len - 1) * 8;
//獲取K值
// Use the encoded k so that we can read filters generated by
// bloom filters created using different parameters.
const size_t k = array[len - 1];
if (k > 30)
{
// Reserved for potentially new encodings for short bloom filters.
// Consider it a match.
return true;
}
//判斷是否存在
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;
}
......
};
實(shí)現(xiàn)邏輯非常簡單军掂，首先取出K值轮蜕，隨后采用和構(gòu)建布隆位組相同的方式判斷指定位組是否為1，如全部為1則認(rèn)定存在該值蝗锥，否則判斷不存在跃洛。
3.2 Murmur Hash
布隆過濾中使用的Hash算法(BloomHash)最終調(diào)用的是hash.cc中的Hash函數(shù)，按作者說法它是Murmur hash的一個(gè)變種终议。關(guān)于Murmur hash簡介如下:
由Austin Appleby在2008年發(fā)明穴张，并出現(xiàn)了多個(gè)變種细燎，都已經(jīng)發(fā)布到了公有領(lǐng)域(public domain)。與其它流行的哈希函數(shù)相比皂甘，對于規(guī)律性較強(qiáng)的key玻驻，MurmurHash的隨機(jī)分布特征表現(xiàn)更良好。
代碼實(shí)現(xiàn)如下：
uint32_t Hash(const char *data, size_t n, uint32_t seed)
{
// Similar to murmur hash
const uint32_t m = 0xc6a4a793;
const uint32_t r = 24;
const char *limit = data + n;
uint32_t h = seed ^ (n * m);
// Pick up four bytes at a time
while (data + 4 <= limit)
{
uint32_t w = DecodeFixed32(data);
data += 4;
h += w;
h *= m;
h ^= (h >> 16);
}
// Pick up remaining bytes
switch (limit - data)
{
case 3:
h += static_cast<unsigned char>(data[2]) << 16;
FALLTHROUGH_INTENDED;
case 2:
h += static_cast<unsigned char>(data[1]) << 8;
FALLTHROUGH_INTENDED;
case 1:
h += static_cast<unsigned char>(data[0]);
h *= m;
h ^= (h >> r);
break;
}
return h;
}
直觀上看代碼比Murmur hash更為簡潔偿枕，本人對hash算法并沒有深入研究璧瞬，此處的各種優(yōu)劣只能暫略。
3.3 CRC32
CRC（Cyclic Redundancy Check）中文名是循環(huán)冗余校驗(yàn)渐夸，在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域嗤锉，為了保證數(shù)據(jù)的正確，采用檢錯(cuò)的手段墓塌。
LevelDB自己實(shí)現(xiàn)了CRC32算法瘟忱，核心代碼如下:
uint32_t Extend(uint32_t crc, const char *buf, size_t size)
{
static bool accelerate = CanAccelerateCRC32C();
if (accelerate)
{
return port::AcceleratedCRC32C(crc, buf, size);
}
const uint8_t *p = reinterpret_cast<const uint8_t *>(buf);
const uint8_t *e = p + size;
uint32_t l = crc ^ 0xffffffffu;
#define STEP1 \
do \
{ \
int c = (l & 0xff) ^ *p++; \
l = table0_[c] ^ (l >> 8); \
} while (0)
#define STEP4 \
do \
{ \
uint32_t c = l ^ LE_LOAD32(p); \
p += 4; \
l = table3_[c & 0xff] ^ \
table2_[(c >> 8) & 0xff] ^ \
table1_[(c >> 16) & 0xff] ^ \
table0_[c >> 24]; \
} while (0)
// Point x at first 4-byte aligned byte in string. This might be
// just past the end of the string.
const uintptr_t pval = reinterpret_cast<uintptr_t>(p);
const uint8_t *x = reinterpret_cast<const uint8_t *>(((pval + 3) >> 2) << 2);
if (x <= e)
{
// Process bytes until finished or p is 4-byte aligned
while (p != x)
{
STEP1;
}
}
// Process bytes 16 at a time
while ((e - p) >= 16)
{
STEP4;
STEP4;
STEP4;
STEP4;
}
// Process bytes 4 at a time
while ((e - p) >= 4)
{
STEP4;
}
// Process the last few bytes
while (p != e)
{
STEP1;
}
#undef STEP4
#undef STEP1
return l ^ 0xffffffffu;
}
關(guān)于CRC32網(wǎng)上有完整的算法說明奥额，本文說明如下幾點(diǎn)：
- 優(yōu)先判斷運(yùn)行環(huán)境的CPU是否自身有計(jì)算CRC32的能力，如果有則使用CPU自身的能力計(jì)算CRC32酷誓。
- 絕大多數(shù)人定義宏的時(shí)候披坏，將宏放到.h文件或者.c文件的最開始處态坦。這其實(shí)違反了生命周期最小化原則盐数。示例中STEP1、STEP2宏在函數(shù)內(nèi)定義伞梯，并在函數(shù)結(jié)尾處解除宏定義玫氢，由此保證該宏僅在該函數(shù)內(nèi)生效。
- 宏定義采用良好的do {} while(0)方式實(shí)現(xiàn)谜诫，這樣做有兩個(gè)好處：避免出現(xiàn)變量重復(fù)定義漾峡，以及避免誤用。
3.4 總結(jié)
布隆過濾器是LevelDB1.2版本新增的特性喻旷，其目的在于進(jìn)一步提升LevelDB的性能生逸。
轉(zhuǎn)載請注明：【隨安居士】http://www.reibang.com/p/366d6563fba8
