leveldb 源码分析 12¶
本系列《leveldb 源码分析》共有 22 篇文章,这是第十二篇
8.FilterPolicy&Bloom 之 1¶
8.1 FilterPolicy¶
因名知意,FilterPolicy 是用于 key 过滤的,可以快速的排除不存在的 key。前面介绍 Table 的时候,在 Table::InternalGet 函数中有过一面之缘。 FilterPolicy 有 3 个接口:
virtual const char* Name() const = 0;
// 返回filter的名字
virtual void CreateFilter(const Slice* keys,
int n, std::string* dst)const = 0;
virtual bool KeyMayMatch(const Slice& key, const Slice& filter)const = 0;
CreateFilter 接口,它根据指定的参数创建过滤器,并将结果 append 到 dst 中,注意:不能修改 dst 的原始内容,只做 append。 参数@keys[0,n-1] 包含依据用户提供的 comparator 排序的 key 列表 -- 可重复,并把根据这些 key 创建的 filter 追加到@dst 中。 KeyMayMatch,参数@filter 包含了调用 CreateFilter 函数 append 的数据,如果 key 在传递函数 CreateFilter 的 key 列表中,则必须返回 true*。
注意:它不需要精确,也就是即使 key 不在前面传递的 key 列表中,也可以返回 true,但是如果key在列表中,就必须返回 true。 涉及到 的类如图 8.1-1 所示。
8.2InternalFilterPolicy¶
这是一个简单的 FilterPolicy 的 wrapper,以方便的把 FilterPolicy 应用在 InternalKey 上,InternalKey 是 Leveldb 内部使用的 key,这些前面都讲过。它所做的就是从 InternalKey拆分 得到 user key,然后在 user key 上做 FilterPolicy 的操作。 它有一个成员:
constFilterPolicy* const user_policy_;
其 Name()返回的是user_policy_->Name();
bool InternalFilterPolicy::KeyMayMatch(const Slice& key, constSlice& f) const
{
returnuser_policy_->KeyMayMatch(ExtractUserKey(key), f);
}
void InternalFilterPolicy::CreateFilter(const Slice* keys,
int n,std::string* dst) const
{
Slice* mkey =const_cast<Slice*>(keys);
for (int i = 0; i < n; i++)mkey[i] = ExtractUserKey(keys[i]);
user_policy_->CreateFilter(keys, n, dst);
}
8.3 BloomFilter¶
8.3.1 基本理论¶
Bloom Filter 实际上是一种 hash 算法,数学之美系列有专门介绍。它是由巴顿.布隆于一九七零年提出的,它实际上是一个很长的 二进制向量 和一系列 随机映射函数。 Bloom Filter 将元素映射到一个长度为 m 的 bit 向量上的一个 bit,当这个 bit 是 1 时,就表示这个元素在集合内。使用 hash 的缺点就是元素很多时可能有冲突,为了减少误判,就使用 k 个 hash 函数计算出 k 个 bit,只要有一个 bit 为 0,就说明元素肯定不在集合内。下面的图 8.3-1 是一个示意图。
在 leveldb 的实现 中,Name() 返回 "leveldb.BuiltinBloomFilter",因此metaindex block 中的key 就是”filter.leveldb.BuiltinBloomFilter”。Leveldb 使用了 double hashing 来模拟多个 hash 函数,当然这里不是用来解决冲突的。 和线性再探测(linearprobing)一样,Double hashing 从一个 hash 值开始,重复向前迭代,直到解决冲突或者搜索完 hash 表。不同的是,double hashing 使用的是另外一个 hash 函数,而不是固定的步长。 给定两个独立的 hash 函数 h1 和 h2,对于 hash 表 T 和值 k,第 i 次迭代计算出的位置就是:h(i, k) = (h1(k) + i*h2(k)) mod |T|。** 对此,Leveldb 选择的 hash 函数是:
Gi(x)=H1(x)+iH2(x)
H2(x)=(H1(x)>>17) | (H1(x)<<15)
H1 是一个 基本的 hash 函数,H2 是由 H1 循环右移得到的,Gi(x) 就是第 i 次循环得到的 hash 值。【理论分析可参考论文 Kirsch,Mitzenmacher2006】 在 bloom_filter 的数据 的最后一个字节存放的是 k_ 的值,k_ 实际上就是 G(x) 的个数,也就是计算时采用的 hash 函数个数。
8.3.2 BloomFilter 参数¶
这里先来说下其两个成员变量:bits_per_key_ 和 key_;其实这就是 Bloom Hashing 的两个关键参数。 变量 k_ 实际上就是模拟的 hash 函数的个数; 关于 变量 bits_per_key_,对于 n 个 key,其 hash table 的大小就是 bits_per_key_。它的值越大,发生冲突的概率就越低,那么 bloom hashing 误判的概率就越低。因此这是一个 时间空间的 trade-off。 对于 hash(key),在平均意义上,发生冲突的概率就是 1/ bits_per_key_。 它们在构造函数中根据传入的 参数 bits_per_key 初始化。
bits_per_key_ = bits_per_key;
k_ =static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
if (k_ < 1) k_ = 1;
if (k_ > 30) k_ = 30;
模拟 hash 函数的个数 k_ 取值为 bits_per_key_*ln(2),为何不是 0.5 或者 0.4 了,可能是什么理论推导的结果吧,不了解了。
8.3.3 建立 BloomFilter¶
了解了上面的理论,再来看 leveldb 对 Bloom Filter 的实现 就轻松多了,先来看 Bloom Filter 的构建。这就是 FilterPolicy::CreateFilter 接口的实现:
void CreateFilter(const Slice* keys, int n, std::string* dst) const
下面分析其实现代码,大概有如下几个步骤:
S1 首先根据 key 个数分配 filter 空间,并圆整到 8byte。¶
size_t bits = n * bits_per_key_;
if (bits < 64) bits = 64;
// 如果n太小FP会很高,限定filter的最小长度
size_t bytes = (bits + 7) / 8; // 圆整到8byte
bits = bytes * 8; // bit计算的空间大小
const size_t init_size =dst->size();
dst->resize(init_size +bytes, 0); // 分配空间
S2 在 filter 最后的字节位压入 hash 函数个数¶
dst->push_back(static_cast<char>(k_));
// Remember # of probes in filter
S3 对于每个 key,使用 double-hashing 生产一系列的 hash 值 h(K_ 个),设置 bits array 的第 h 位=1。¶
char* array =&(*dst)[init_size];
for (size_t i = 0; i < n;i++)
{
// double-hashing,分析参见[Kirsch,Mitzenmacher 2006]
uint32_t h =BloomHash(keys[i]);
// h1函数
const uint32_t delta = (h>> 17) | (h << 15);
// h2函数、由h1 Rotate right 17 bits
for (size_t j = 0; j <k_; j++)
{
// double-hashing生产k_个的hash值
const uint32_t bitpos = h% bits;
// 在bits array上设置第bitpos位
array[bitpos/8] |= (1<< (bitpos % 8));
h += delta;
}
}
Bloom Filter 的创建就完成了。
8.3.4 查找 BloomFilter¶
在指定的 filer 中查找 key 是否存在,这就是 bloom filter 的查找函数: bool KeyMayMatch(const Slice& key, const Slice& bloom_filter),函数逻辑如下:
S1 准备工作,并做些基本判断。¶
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;
const size_t k = array[len-1];
// 使用filter的k,而不是k_,这样更灵活
if (k > 30) return true;
// 为短bloom filter保留,当前认为直接match
S2 计算 key 的 hash 值,重复计算阶段的步骤,循环计算 k 个 hash 值,只要有一个结果对应的 bit 位为 0,就认为不匹配,否则认为匹配。¶
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;
// notmatch
h += delta;
}
return true; // match
8.4 Filter Block 格式¶
Filter Block 也就是前面 sstable 中的 meta block,位于 data block 之后。
如果打开 db 时指定了 FilterPolicy,那么每个创建的 table 都会保存一个 filter block,table 中的 metaindex 就包含一条从”filter.到 filter block 的 BlockHandle 的映射,其中”
Filter block 存储了一连串的 filter 值,其中第 i 个 filter 保存的是 block b 中所有的 key 通过 FilterPolicy::CreateFilter()计算得到的结果,block b 在 sstable 文件中的偏移满足 [ i*base … (i+1)*base-1 ]。
当前base是2KB,举个例子,如果 block X 和 Y 在 sstable 的起始位置都在 [0KB, 2KB-1] 中,X 和 Y 中的所有 key 调用 FilterPolicy::CreateFilter()的计算结果都将生产到同一个 filter 中,而且该 filter 是 filter block 的第一个 filter。 Filter block 也是一个 block,其格式遵从block的基本格式:|block data| type | crc32|。其中block dat的格式如图8.4-1所示。
图 8.4-1 filter block data
了解了格式,再分析 构建和读取 filter 的代码 就很简单了。