有趣的bloom filter

4 8th, 2009 | Posted by jacky | Filed under 大话技术

设想以下的一个问题:有一个keyword的集合,我们需要快速判定某个keyword是否包含在其中。最简单的方法是遍历,但是效率很差。我们马上想到了hash的方法,因为在Oracle内部,hash无处不在。比如在cache buffer中找到某个block,在shared pool中找到某个SQL等等。我们可以把keyword的集合build成一个hash table,然后根据keyword计算hash值,通过是否落在相应的hash bucket中,这样就可以实现快速查找的目的。这个方法不错,但是当keyword过多时,hash table会占用大量内存,效率也会随之下降。

今天公司的架构师介绍了一个新的方法给我:Bloom Filter。它是一种基于随机数(或Hash)的数据结构,它支持对成员使用较少空间来存储,却能得到较高效率的查询。换句话说:在Bloom Filter 可以用于检索一个元素是否在一个集合中。其原理如下:

建立一个容量为500万的Bit Array结构(Bit Array的大小和keyword的数量决定了误判的几率),将集合中的每个keyword通过32个hash函数分别计算出32个数字,然后对这32个数字分别用500万取模,然后将Bit Array中对应的位置为1,我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上,见下图:

当需要快速查找某个keyword时,只要将其通过同样的32个hash函数运算,然后映射到Bit Array中的对应位,如果Bit Array中的对应位全部是1,那么说明该keyword匹配成功。

Bloom filter 是一个集合的有损编码,所以它不是一种“保险”的方案,存在一定的误判率。

有人问:这个对DBA有什么用?虽然我们不直接开发应用,但是开阔视野和思路对我们同样重要。难道我们碰到这种问题就只能用like或者in去解决吗?

–EOF–

后记:要深入了解Oracle,hash的原理和实现是必须要掌握的。有一次面试一个技术专家,高精尖的技术谈得头头是道,但是连hash的基本原理都说不清楚。对于一个技术专家来说,不能只懂“高精尖”,没有基础的知识,任何“高精尖”都只是空中楼阁,对于DBA,尤其如此。

标签:
  1. 谭理想
    4 8th, 200917:29

    后记很有道理

  2. sky.jian
    4 8th, 200923:51

    “对于一个技术专家来说,不能只懂“高精尖”,没有基础的知识,任何“高精尖”都只是空中楼阁,对于DBA,尤其如此。”

    我只看重基础性的掌握程度,有了基础原理的理解,扩展提升很容易,没有基础原理的理解,空谈其他任何内容,都是只能算是扯淡而已。

  3. sky.jian
    4 8th, 200923:53

    所以一般面试的时候,很少关注别人能描绘出多么多么高端的技术,多么多么美好的架构,而更多关注理解多少实现原理,掌握多少基础概念

  4. 木匠Charlie
    4 9th, 200900:37

    鄙人正要写一篇bloom filter在11g里面的应用,筹划了两个月,让你抢先了,幸好内容没有重复,还有助于互补.

  5. jacky
    4 9th, 200909:20

    bloom filter在11g里面的应用,赶紧写吧,让我也学习一下。

  6. 木匠
    4 9th, 200913:29

    澄清一个问题. 是设置和比较500万比特(bit)中的32个比特?
    如果唯一值总数过大,岂不是要占用很多存储空间 (每个值500万比特)? 可能是压缩了(5,000,000 – 32) 个 0. 咱理解的对吗?

    你图中演示的算法跟Chris Antognini的有点区别.

    Thanks 10k.

  7. jacky
    4 9th, 200913:37

    不是每个keyword都需要500万bit这么大的空间,实时上是将整个集合map到这500万的bitarray中,容量的大小和keyword的数量决定了碰撞的几率。在具体实现时,也不是按照一个500万的bitarray来存储的,我只是为了说明原理。

  8. 木匠Charlie
    4 10th, 200901:01

    恕鄙人愚昧. 还是没有搞清楚Cache的keyword是怎么存储的? ^_^

    我猜测有几种可能,

    1) 压缩keyword, 所以不需要500万bit.
    2) 用特殊方式存储keyword, 比较目标数据的hash算出的32个bit之前,先解码.

  9. fcp
    4 10th, 200910:43

    keyword 本身不需要存储的啊,根据keyword和32个种子计算出了 32个 number,然后 32个 随机number 除以 500w取模,就是32个数字,这32个数字对应了在 500w bitarray上的位置,这32个位置就标记 1 。

    然后来的keyword根据这个算法算出 32个数字,最后转换到对应的 32个位置,只要发现都是1,就表明这个keyword 已经存在。 当然这有冲撞的可能性,就是把不存在当做存在了,但绝对不会把 存在当不存在。 概率的问题经过计算是很小的冲撞,我们公司的实际应用是 4000万数据使用100mb内存的时候冲撞为1次,200mb内存冲撞为0.

  10. 木匠Charlie
    4 10th, 200912:16

    基本懂了. (可还是晕晕乎乎的.)
    这32个1的位置,鄙人认为还是要存储的, 猜测大概是32个位置序号.

    多谢各位的解释.

    p.s. 引用Christian Antognini的一些注解:

    * False negatives are not possible. (理解为一个key不会算出两个hash值)
    * False positives are possible. (多个key可能会算出相同的hash值)

  11. fcp
    4 10th, 200916:50

    比如某个keyword的第一个随机数字算出来模500w之后是 999999,那么就把 500w个 bitarray 的第 999999序号的这个 bit标记为1. 每个 keywords 都会有32个数字对应的位置被标记

    当然会有其他keywords算出来可能跟你32个中的 n个重叠了,那没关系。 100万个词,能否 100万-1 个 关键词正好叠加起来能把你这个关键词的 位置都给标记为 1, 这是一个概率问题。

  12. jacky
    4 10th, 200919:31

    难得大师出马回答问题。

  13. xin
    4 12th, 200903:52

    这32个1的位置,鄙人认为还是要存储的, 猜测大概是32个位置序号.

    多谢各位的解释

    当然要存储的 , 这里的每个1的位置 其实就是 某个 字节的某个 bit ( 一个字节8 个bit) , 整个bit array 的存储就是通过定义一个 char 的数组来实现的

    这个算法我也是第一次看到 , 结果的准确性取决于hash函数 和 数组的大小 。 就像大师说的,是一个概率问题 ,整个运算的过程是不可逆的 。

    想一下oracle 的 checksum 算法 ,整个过程也是不可逆的 ,对整个数据块进行一系列的异或运算,产生一个结果 , 通过可能的小概率错误换取时间和空间

  14. jacky
    4 13th, 200917:26

    楼上就是著名的范鑫同学,非常得NB

  15. Alex
    4 30th, 200912:54

    木匠说的bloom filter 在11g 的应用是指TOP chapter 9 提到的partition 里面那个11g 新的optimizer operation 吗? (PART JOIN FILTER CREATE)里面就一句话提到了呀, 另外你的两个引用Christian Antognini的注解在哪瞄到的,http://antognini.ch/papers/BloomFilters20080620.pdf ?
    快把文章搞出来大家看看呀,不能放了好消息就在后面偷懒呀.fighting tiger!!!

  16. Young
    8 3rd, 200914:43

    能提供下这32位的hash函数吗?

  17. Cassandra存储机制
    2 25th, 201017:18
    #17
  18. OurMySQL
    7 9th, 201023:11
    #19
  19. eTsir
    7 14th, 201013:45

    重复度的关键在于32个hash函数的设计, 以及用于取模的5M与keyword规模之间的比例.

  20. 笨猫儿
    6 15th, 201217:33

    小小的质疑大师一下:
    当需要快速查找某个keyword时,只要将其通过同样的32个hash函数运算,然后映射到Bit Array中的对应位,如果Bit Array中的对应位全部是1,那么说明该keyword匹配成功

    应该是快速查询key的时候,通过同样的32个hash函数计算,映射到array中的对应位,如果存在0,那么必定是不包含的,如果存在1,不代表一定包含,所以说bloom filter存在一定的误判率,能够容忍说数据存在,但是实际上数据是不存在的;但是不能够容忍说数据不存在,但是实际上数据是存在的现象。