专栏首页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 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

    linjinhe
  • LevelDB 完全解析(2):Log

    这里的 log 是指 Write Ahead Log。前面说了,LevelDB 写入的数据会先保存到 MemTable。为了防止宕机导致数据丢失,在将数据写入 ...

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

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

    linjinhe
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

    linjinhe
  • LevelDB 完全解析(11):Compaction

    因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:

    linjinhe
  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • LevelDB 完全解析(9):写操作

    以上,便是 LevelDB 的写入流程。写入队列 + 合并写操作,逻辑和代码都十分简洁。比较不足的是,整个写入过程都是单线程的。

    linjinhe
  • LevelDB 完全解析(8):读操作之 Get

    LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

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

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

    linjinhe
  • 漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)

    LevelDB 是一个单机的 KV 存储引擎,但没有使用传统的平衡查找树以平衡读写性能,而是使用了 LSM-tree 结构来组织数据,牺牲部分读性能来换取较高的...

    青藤木鸟
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • 漫谈 LevelDB 数据结构(一):跳表(Skip List)

    早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传 —— 绝对是不世出的工艺品!如果你对存储感兴趣、如果你想优雅使用 C++、...

    青藤木鸟
  • LevelDB:读操作

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

    linjinhe
  • 漫谈 LevelDB 数据结构(三):LRU 缓存( LRUCache)

    LRU 是工程中多见的一个数据结构,常用于缓存场景。近年来,LRU 也是面试中一道炙手可热的考题,一来工程用的多,二来代码量较少,三来涉及的数据结构也很典型。L...

    青藤木鸟
  • 【深度知识】10分钟教会你深挖以太坊数据层

    在当下数据爆炸的信息时代,凭借区块链去中心化、点对点和防篡改的特性,“区块链+大数据”已成为研究的热门,可以说,区块链与大数据的结合为今后区块链应用的大规模落地...

    辉哥
  • 0.166666667小时,教会你深挖以太坊数据层

    从架构设计上来说,区块链可以简单的分为三个层次,协议层、扩展层和应用层。其中,协议层又可以分为存储层和网络层,它们相互独立但又不可分割。

    区块链大本营
  • 秒级去重:ClickHouse在腾讯海量游戏营销活动分析中的应用

    导语 | 腾讯内部每日都需要对海量的游戏营销活动数据做效果分析,而活动参与人数的去重一直是一项难点。本文将为大家介绍腾讯游戏营销活动分析系统——奕星,在去重服...

    腾讯QQ大数据

扫码关注云+社区

领取腾讯云代金券