Python微信订餐小程序课程视频
https://edu.csdn.net/course/detail/36074
Python实战量化交易理财系统
https://edu.csdn.net/course/detail/35475
LevelDB 学习笔记1：布隆过滤器
- 底层是位数组，初始都是 0
- 插入时，用 k 个哈希函数对插入的数字做哈希，并用位数组长度取余，将对应位置 1
- 查找时，做同样的哈希操作，查看这些位的值
- 如果所有位都是 1，说明数字可能存在
- 如果有某个位不是 1，说明数字一定不存在
数学结论
影响布隆过滤器精度的参数有
- 哈希函数的个数 k
- 布隆过滤器位数组的容量 m
- 布隆过滤器插入的数据数量 n
对于给定的 m 和 n，要想最小化错误率（假阳性），k 应该取
k=mnln2k=mnln2k=\frac{m}{n} \ln 2
要求错误率不大于εε\varepsilon，k 取最优的情况下，m 应该至少为
m≥−1.44log2ε∗nm≥−1.44log2ε∗nm \geq - 1.44 \log _{2} \varepsilon * n
布隆过滤器的优缺点
优点
- 空间效率高，可以在使用有限内存的情况下处理海量数据
- 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__
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-433DDjJc-1649479520488)(https://blog.csdn.net/ljx-null)]路过的摸鱼侠 - 本文链接： https://blog.csdn.net/ljx-null/p/16120507.html
转载请注明：xuhss » LevelDB 学习笔记1：布隆过滤器