《Redis深度历险》学习笔记:HyperLogLog&布隆过滤器

HyperLogLog

  • 通常用来统计一个集合中不重复的元素个数的方法叫做基数计数(cardinality counting)。(eg. 统计页面 UV)
  • HyperLogLog 是 Redis 的高级数据结构,用来解决使用 set 结构进行基数计数时占用空间过大的问题。
  • HyperLogLog 统计的标准误差为 0.81%
  • HyperLogLog 结构的发明人是 Philippe Flajolet,故 HyperLogLog 命令以其名字首字母缩写 pf 开头:
    • pfadd:向键内增加元素,并去重。
    • pfcount:统计键内元素数量。
    • pfmerge:将多个 pf 计数值累加在一起形成一个新的 pf 值。适用于合并相似统计项的数值,即 A+B
    127.0.0.1:6379> pfadd codehole user1
    (integer) 1
    127.0.0.1:6379> pfadd codehole user2
    (integer) 1
    127.0.0.1:6379> pfadd codehole user1
    (integer) 0
    127.0.0.1:6379> pfcount codehole
    (integer) 2
    
  • HyperLogLog 计数较小时,采用稀疏矩阵存储,空间占用很小,计数超过了阈值时转变成稠密矩阵,占用 12KB 的空间。数据量大时性价比明显优于 set 结构。
  • 一个 pf 项占用内存空间 12KB
  • HyperLogLog 不储存元素本身,不能像 set 那样返回输入的元素。

原理

  • HyperLogLog 是个神奇的算法,它的精髓有 2 点:

    • 恰当的哈希算法对数据的处理可以使数据分布均匀。这一点类似于投足够多次硬币,某一面朝上的概率能够均匀分布在 50% 附近(也就是概率论中的伯努利分布)
    • 对于一个乱序集合,如果元素的哈希值末尾出现的 0 的个数记为 k,那么观察所有元素的 k 值,其中最大值 K 与集合内元素的总数量 N 有相关性:N = 2^K
      eg. 有 1-37600 的数字随机排列,取出一些数字来进行哈希计算,找出二进制值末尾出现的 0 的最大的个数,发现 K=15 —— 2^15 = 32768
  • 上面还是有点抽象,为什么末尾 0 的个数可以与集合内元素总数相关,想了很久才有了一点眉目,干脆用这个不恰当的栗子来理解好了:

    • 假如有一个骰子,如何通过实验来获知这个骰子上有几种不同的图案?
      其实方法很简单,只需要每投一次就记录一下图案,投足够多次,就可以知道每种图案出现的概率,然后大概就能猜出总共有几种图案。
      这有点像通过查看投硬币的结果来猜测硬币有 2 面而不是 3 面。
    • HyperLogLog 中的哈希算法对数据的处理,保证了哈希结果是均匀随机的,即保证了「投币」的随机性。
  • 这篇文章描述了算法的基本原理——要统计一个数据集合 values 的不重复元素总数时:

    1. 对元素做哈希计算,获得元素的哈希值 h
    2. 哈希值 h 的前几位当作桶 bucket 的编号 n,其余部分 bucket_hash 放入桶中
    3. 查看桶中的值末尾有几个 0,与记录中的最多末尾 0 标志 max_zeroes 进行比较,并更新 max_zeroes
    4. 遍历 values,对每个元素重复 1-3 步
  • Redis 的 HyperLogLog 算法采用 2^14=16384 个桶进行独立计数(原始算法为 1024 个),每个桶使用 6bit 来保存当前桶低位连续零位的最大长度 max_zeroes(最大可表示 2^6-1=63),所以一个 pf 项占用内存空间 2^14 * 6Kbit = 98Kbit = 12KByte

布隆过滤器

  • 布隆过滤器(Bloom Filter)由布隆于 1970 年提出,它是一个很长的二进制向量和一系列随机映射函数,用于检索一个元素是否在一个集合中
  • 布隆过滤器原理:
    • 使用 hash 算法对数据进行计算,将其结果对应位置(如1,4,5)设为 1。
    • 验证时对对象进行 hash 计算后查看对应位(如1,4,5)是否为 1。
    • 受制于空间大小,多个数据的 hash 结果可能重叠,导致验证存在性时的误判。

布隆过滤器

  • 布隆过滤器的空间效率和查询时间都远超一般算法,但存在一定的误识别率删除困难
  • 布隆过滤器是一个不够精确的 set 结构,返回 true 时真实结果可能为 false,返回 false 时真实结果一定为 false
  • 通常使用 3 个基本命令:
    # 添加元素
    127.0.0.1:6379> bf.add codehole user1
    (integer) 1
    
    # 批量添加元素
    127.0.0.1:6379> bf.madd codehole user2 user3
    1) (integer) 1
    2) (integer) 1
    
    # 查询元素是否存在
    127.0.0.1:6379> bf.exists codehole user1
    (integer) 1
    
    # 批量查询元素是否存在
    127.0.0.1:6379> bf.mexists codehole user2 user3 user4
    1) (integer) 1
    2) (integer) 1
    3) (integer) 0
    
  • bf.reserve {key} {error_rate} {capacity} 命令(文档)可以显式创建布隆过滤器(重复创建时会报错),该命令有 3 个参数:
    • key:过滤器键名。
    • error_rate:错误率。错误率越低,所需空间越大。对于非精确场合可设置较大值。
    • capacity:预计放入的元素数量。当实际数量超出这个数值时,误判率会上升。该值估计的过大,会浪费存储空间,估计的过小,就会影响准确率。
  • 使用布隆过滤器时不要让实际元素远大于初始化大小,超出时应重建过滤器、分配更大 size 的过滤器,并导入所有历史元素 (需提前在外部保存历史元素)。
  • error_rate 不会因溢出而剧增,故重建过滤器的时间较为宽松,但也应提前合理设置。
  • 爬虫系统中过滤爬虫的 URL 非常适合使用布隆过滤器来统计,进而大幅降低去重存储消耗。
  • 布隆过滤器可以显著降低 DB 的 IO 请求数,在 NoSQL DB 领域使用广泛。
  • 垃圾邮件过滤功能也普遍用到了布隆过滤器,故正常邮件会被误判。
  • 用于计算布隆过滤器最佳参数的布隆计算器

延伸阅读:

updatedupdated2020-08-012020-08-01
加载评论