3.1 Bloom Filter
3.1.1 基本概念
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数O(k)。
但是布隆过滤器的缺点和优点一样明显，误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素，因为我们无法得知指定position上被那些key映射。
假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，n是数据个数，k 是 Hash 函数的个数，对于给定的m，n，如何选择Hash函数个数 k 由以下公式确定：k = ln2 * m/n = 0.7 * m/n。此时误报率为：2^-k = 0.6185^m/n。当m/n=10时，误报率约为0.8%。
关于详细证明请参见布隆过滤器 (Bloom Filter) 详解。
3.1.2 LevelDB版本实现
LevelDB将bloom filter做为内置过滤器，供用户选择使用，其核心算法代码在bloom.cc中。
3.1.2.1 K值选择
根据前面的描述，最佳k值为0.7m/n，leveldb中实现基本一致：
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，稍有点不同的是leveldb中的k值是向下取整的。作者的解释是为了减少检测碰撞所需的时间，但这样增大了误报率，整体性能上应该是要比非向下取整后要差的。
K值得取值范围为1-30，作者推荐值为10(参见测试程序)，此时的误报率小于1%(约为0.8%)。
3.1.2.2 布隆插入
布隆位组构建逻辑如下：
class BloomFilterPolicy : public FilterPolicy
{
......
virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const
{
//动态计算布隆过滤器的位组大小(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);
//保存本次生成布隆位组时的K值
dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
char *array = &(*dst)[init_size];
//为每个key值hash出key个位置并置1
for (int i = 0; i < n; i++)
{
//使用double hashing计算出K个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中的布隆位组不是预先设定好，而是动态生成的。对一批key值设置一个布隆位组，由此保证误报率一直处于预期之内。另外，位组借用了std::string实现，并在位组最后额外保存了生成该布隆位组时采用的K值。
但有一点很奇怪，程序在resize之后紧接着做了一次push_back，这可能导致额外的一次内存分配、拷贝动作，对于leveldb这种对性能追求极致的程序并不应该，来看测试程序:
#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命令编译并运行该程序结果
desmondwangdeMacBook-Pro:demo desmondwang$ g++ -O2 a.cpp
desmondwangdeMacBook-Pro:demo desmondwang$ ./a.out
63
127
Hello, hellodddddddddddddddddddddddddddddddddddddddddddddddddddddddddda!
最后，LevelDB并没有真正的使用K个hash算法计算position，而是采用double hashing，公式如下：h(i,k)=(h1(k)+i∗h2(k))mod|T|。LevelDB中，h1(k)为根据hash算法计算出来的结果，而h2(k)为delta = (h >> 17) | (h << 15)。
3.1.2.3 布隆过滤
布隆过滤计算逻辑如下：
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;
}
......
};
实现逻辑非常简单，首先取出K值，随后采用和构建布隆位组相同的方式判断指定位组是否为1，如全部为1则认定存在该值，否则判断不存在。
3.2 Murmur Hash
布隆过滤中使用的Hash算法(BloomHash)最终调用的是hash.cc中的Hash函数，按作者说法它是Murmur hash的一个变种。关于Murmur hash简介如下:
由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。
代码实现如下：
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算法并没有深入研究，此处的各种优劣只能暂略。
3.3 CRC32
CRC（Cyclic Redundancy Check）中文名是循环冗余校验，在数据存储和数据通讯领域，为了保证数据的正确，采用检错的手段。
LevelDB自己实现了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;
}
关于CRC32网上有完整的算法说明，本文说明如下几点：
- 优先判断运行环境的CPU是否自身有计算CRC32的能力，如果有则使用CPU自身的能力计算CRC32。
- 绝大多数人定义宏的时候，将宏放到.h文件或者.c文件的最开始处。这其实违反了生命周期最小化原则。示例中STEP1、STEP2宏在函数内定义，并在函数结尾处解除宏定义，由此保证该宏仅在该函数内生效。
- 宏定义采用良好的do {} while(0)方式实现，这样做有两个好处：避免出现变量重复定义，以及避免误用。
3.4 总结
布隆过滤器是LevelDB1.2版本新增的特性，其目的在于进一步提升LevelDB的性能。
转载请注明：【随安居士】http://www.jianshu.com/p/366d6563fba8
