LevelDB 学习笔记1:布隆过滤器 - 路过的摸鱼侠
source link: https://www.cnblogs.com/ljx-null/p/16120507.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LevelDB 学习笔记1:布隆过滤器
- 底层是位数组,初始都是 0
- 插入时,用 k 个哈希函数对插入的数字做哈希,并用位数组长度取余,将对应位置 1
- 查找时,做同样的哈希操作,查看这些位的值
- 如果所有位都是 1,说明数字可能存在
- 如果有某个位不是 1,说明数字一定不存在
影响布隆过滤器精度的参数有
- 哈希函数的个数 k
- 布隆过滤器位数组的容量 m
- 布隆过滤器插入的数据数量 n
对于给定的 m 和 n,要想最小化错误率(假阳性),k 应该取
要求错误率不大于εε,k 取最优的情况下,m 应该至少为
布隆过滤器的优缺点
- 空间效率高,可以在使用有限内存的情况下处理海量数据
- 1% 错误率并使用最佳 k 值的布隆过滤器,每个元素只需要使用约 9.6 位
- 插入和查询都是常数复杂度,即
O(k)
- 删除元素困难,因为简单地将对应的位置 0 会影响其他元素的判断
- 可以用一种叫 Counting Bloom filter 的变体
LevelDB 中的布隆过滤器
LevelDB 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中
- 若过滤器认为 key 不在 sstable 中,那么就没必要查找这个 sstable 了
- 否则,key 有可能在 sstable 中,应该做查找
使用布隆过滤器可以有效的减少调用 DB::Get()
时的访存次数,从而减小读放大
LevelDB 中布隆过滤器的实现是 BloomFilterPolicy
,它是接口类 FilterPolicy
的实现
FilterPolicy
类决定了查找过程中要不要读取某个 sstable- 允许用户自定义
FilterPolicy
的子类来应用不同的过滤策略
LevelDB 实现时做了优化,它并不是使用 k 个哈希函数,而是应用 rsa2008 中提出的方法只生成一次哈希值,然后用 double-hashing 的方式生成一组哈希值
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;
}
一般实现布隆过滤器时,都会选择非加密哈希算法
- 加密哈希算法,比如 MD5、SHA1,安全性较高,难以找到碰撞或通过加密值反推原文
- 非加密哈希算法,比如 MurMurHash、CRC32、FNV,计算速度快
- LevelDB 实现了一个类似于 MurMurHash 的非加密哈希算法
其他应用场景
做查询的时候,缓存没有命中,就会到数据库中去找,特别地,如果查找一个不存在的 key,那么是一定无法命中缓存,必须去查数据库的,如果有人恶意地使用大量请求来查不存在的 key,就会导致数据库压力过大,甚至崩溃,这种现象称为缓存穿透
用布隆过滤器我们可以直接将这些针对不存在的 key 发起的请求过滤掉
__EOF__
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK