专栏首页linjinhe的专栏LevelDB 完全解析(6):Filter

LevelDB 完全解析(6):Filter

前文回顾

Bloom Filter

LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

1970 年,Burton Howard Bloom 在论文 Space/Time Trade-offs in Hash Coding with Allowable Errors 提出了 bloom filter。

BloomFilter

Bloom filter 的实现一般由一个或多个 bitmap 和多个哈希函数组成,可以用于检索一个元素是否在一个集合中。

  • 优点是空间效率高、查询时间是常数复杂度,并且和每个 key 的长度无关。
  • 缺点是有一定的误识别率(false positive,通常平均每个元素只需要不到 10 bits 的空间就能把错误率控制在 1% 左右),同时不支持删除操作。
  • 关于删除操作,也许有人会想把 bitmap 变成整数数组,然后每插入一个元素就把对应的计数器加 1,删除元素时将计数器减掉就可以了。这样做有两个问题:
    1. 消耗的内存大大增加。如果使用 uint8 的整数数组,内存是原来的 8 倍,并且最大只能计数到 255。而使用 uint16、uint32 会消耗更多的内存。
    2. 要保证安全地删除元素,首先我们必须保证删除的元素的确在 bloom filter 中。这一点单凭这个过滤器是无法保证的。

假设 m 为 bitmap 的长度,n 是元素的总数,k 是哈希函数的个数,则平均每个 key 消耗的内存 bits_per_key = m / n。 对于给定的 bits_per_key,要使误识别率最低,则 k 的取值为 bits_per_key * ln2。<br /> 如果我们希望误识别率为 e,则

比如当 e = 0.01 时,可以通过公式简单计算得到 bits_per_key ~= 9.567。也就是说,一个 key 消耗不到 10 bits 就能将误识别率控制在 1% 左右。

具体的数学推导过程可以参考 bloom filter 的维基百科

实现

LevelDB 中的 bloom filter 的实现是 BloomFilterPolicy,它继承了 FilterPolicy 抽象类,实现了两个接口:

  1. CreateFilter - 根据 key 列表创建 filter。
  2. KeyMayMatch - 判断一个 key 是否可能存在。如果 key 存在,一定返回 true。如果 key 不存在,可能返回 true 也可能返回 false。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(10):读操作之 Iterator

    通过前面的文章,我们了解到 LevelDB 的数据是保存在内部多个不同组件的,并且每个组件的数据格式都不一样。

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LevelDB:读操作

    前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。

    linjinhe
  • 手把手教你实现一个基于 Java 的分布式锁服务

    编辑:业余草 来源:https://www.xttblog.com/?p=4994

    业余草
  • 小王,在 Java 中如何利用 redis 实现一个分布式锁服务呢???

    在现代的编程语言中,接触过多线程编程的程序员多多少少对锁有一定的了解。简单的说,多线程中的锁就是在多线程环境下,多个线程对共享资源进行修改的时候,保证共享资源一...

    趣学程序-shaofeer
  • Redis - sort set类型操作

    Aichen
  • antd的select 的key 和value获取

    *默认情况下 onChange 里只能拿到 value,如果需要拿到选中的节点文本 label,可以使用 labelInValue 属性。 选中项的 labe...

    用户4344670
  • 一文搞懂 flink state key 的设置方式

    前一篇文章 一文搞懂 Flink window 元素的顺序问题 我们已经知道了,state 的获取、更新、清除等都与 key 相关。那么 key 是如何设置的呢...

    shengjk1
  • 深入了解ProcessFunction的状态操作(Flink-1.10)

    学习Flink的ProcessFunction过程中,官方文档中涉及状态处理的时候,不止一次提到只适用于keyed stream的元素,如下图红框所示:

    程序员欣宸
  • 写了个Python小工具,再也不怕孩子偷偷玩电脑游戏啦

    马上要过年啦,中小学生也都放假了,自然要放松放松。但难免有的孩子打起游戏来就控制不住自己。怎么办呢,今天小编就带领大家来做一个防止孩子玩游戏的Python小程序...

    Crossin先生

扫码关注云+社区

领取腾讯云代金券