`

深入理解Bloom Filter

    博客分类:
  • Java
阅读更多

Bloom Filter是1970年由Bloom提出的,最初广泛用于拼写检查和数据库系统中。近年来,随着计算机和互联网技术的发展,数据集的不断扩张使得 Bloom filter获得了新生,各种新的应用和变种不断涌现。Bloom filter是一个空间效率很高的数据结构,它由一个位数组和一组hash映射函数组成。Bloom filter可以用于检索一个元素是否在一个集合中,它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

 

基本原理

查找或判断一个元素是否存在于一个指定集合中,这是计算机科学中一个基本常见问题。通常,我们会采用线性表(数组或链表)、树(二叉树、堆、红黑树、 B+/B-/B*树)等数据结构对所有元素进行存储,并在其上进行排序和查找。这里的查找时间复杂性通常都是O(n)或O(logn)的,如果集合元素非常庞大,不仅查找速度非常慢,对内存空间的需求也非常大。假设有10亿个元素,每个元素节点占用N个字节,则存储这个集合大致需求N GB内存。大家可能很快会想到hashtable,它的查找时间复杂性是O(1)的,可以对元素进行映射索引并定位,但它并没有减少内存需求量。hash 函数的一个问题是可能会发生碰撞,即两个不同的元素产生相同的hash值,在某些场合下需要通过精确比较来解决这个问题。

实际上,判断一个元素是否存在于一个指定集合中,可能并不需要把所有集合元素的原始信息都保存下来,我们只需要记住“存在状态”即可,这往往仅仅需要几个bit就可表示。Hash函数可将一个元素映射成一个位数组中一个点,为了降低碰撞率可采用多个hash函数将元素映射成多个点。这样一来,只要看看几个位点是0或1 就可以判断某个元素是否存在于集合当中。这就是Bloom filter的基本思想,不仅可大大缩减内存空间,查找速度非常快。

Bloom filter使用一个位数组来记录元素存在状态,并使用一组hash函数(h1, h2, hk...)来对元素进行位映射。插入元素时,对该元素分别进行K次hash计算,并将映射到位数组的相应bit置1。查找元素时,任何其中一个映射位为 0则表示该元素不存在于集合当中,只要当所有映射位均为1时才表示该元素有可能存在于集合当中。换句话说,如果Bloom filter判断一个元素不在集合中,那肯定就不存在;而如果判断存在,则不一定存在,虽然这个概率很低。这个问题是由hash函数会发生碰撞的特性所决定的,它造成了Bloom filter的错误率产生。这个错误率可通过改变Bloom filter数组大小,或改变hash函数个数进行调节控制。由此可见,Bloom filter也不是完美的,它的高效也是有一定代价的,它通过容忍一定的错误率发生换取了存储空间的极大节省。另外,Bloom filter不能支持元素的删除操作,如果删除会影响其他元素的存在性正确判断。因此,Bloom Filter不适合那些“零错误”的应用场合,但是这个错误是正向的(false positive),不会发生反向的错误(false negative),判断元素不存在集合中是绝对正确的。Bloom filter使用可控的错误率获得了空间的极大节省和极快的查找性能,得到广泛应用也是理所当然的。

 

一点数学基础

(1)错误率估计
假设 kn < m,且hash是完全随机的,其中k为hash函数个数,n为项目数,m为位数组位数。当所有项目都被k个hash函数映射到m位数组中时,某位仍然为0的概率为(1 - 1/m)^(kn) = e^(-kn/m),则错误率约为
f = (1 - (1-1/m)^(kn))^k = (1 - e^(-kn/m))^k
令 p = e^(-kn/m),给定m, n,则
f = (1 - p)^k = e^(kln(1-p))

(2)最优hash函数个数
令 g = kln(1-p),当g极小时,f取极小值,因为 ln(e^(-kn/m)) = -kn/m,
   g = -m/n * ln(p) * ln(1-p)
 根据对称性原理有,当 p =1/2时,g取极小值,因此,
 p = e^(-kn/m) = 1/2,得到,
 k = ln2 * (m/n),此时错误率最小,即f = (1/2)^k = (0.618)^(m/n)

(3)位数组大小
给定错误率E,参考文献4中推算出当 m >= n * log2(1/E)时,f不超过E。上面我们已经推算出 k = ln2 * (m/n)时f最小,因此当hash函数个数最优时,为了让错误率不超过E,则有
m >= log2(e) * (n * log2(1/E)),这个值是正常情况下m最小值的1.44倍。

根据上面推导所得到的数学公式,假设错误率我们取0.01,则可以确定最优化情况下,m >= 9.567n,k = 7。

 

基本特征

从以上对基本原理和数学基础的分析,我们可以得到Bloom filter的如下基本特征,用于指导实际应用。
(1)存在一定错误率,发生在正向判断上(存在性),反向判断不会发生错误(不存在性);
(2)错误率是可控制的,通过改变位数组大小、hash函数个数或更低碰撞率的hash函数来调节;
(3)保持较低的错误率,位数组空位至少保持在一半以上;
(4)给定m和n,可以确定最优hash个数,即k = ln2 * (m/n),此时错误率最小;
(5)给定允许的错误率E,可以确定合适的位数组大小,即m >= log2(e) * (n * log2(1/E)),继而确定hash函数个数k;
(6)正向错误率无法完全消除,即使不对位数组大小和hash函数个数进行限制,即无法实现零错误率;
(7)空间效率高,仅保存“存在状态”,但无法存储完整信息,需要其他数据结构辅助存储;
(8)不支持元素删除操作,因为不能保证删除的安全性。

优缺点

与其它数据结构相比较,Bloom filter的最大优点是空间效率和查找时间复杂性,它的存储空间和插入/查询时间都是常数。Hash函数之间没有相关性,可以方便地由硬件并行实现。Bloom filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。另外,Bloom filter一般都可以表示大数据集的全集,而其它任何数据结构都难以做到。

Bloom filter的缺点和优点一样显著,首先就是错误率。随着插入的元素数量增加,错误率也随之增加。虽然可以通过增加位数组大小或hash函数个数来降低错误率,但同时也时影响空间效率和查找性能,而且这个错误率是无法从根本上消除的。这使得要求“零错误”的场合无法应用Bloom filter。其次,一般情况下不能从Bloom filter中删除元素。一方面是我们不能保证删除的元素一定存在Bloom filter中,另一方面是不能保证安全地删除元素,可能会对其他元素产生影响,究其原因还是hash函数可能产生的碰撞造成的。计数Bloom filter可以在一定程度上支持元素删除,但保证安全地删除元素并非如此简单,它也不能从根本上解决这个问题,而且计数器回绕也会有问题。这两方面也是目前Bloom filter的重点研究方向,有不少工作,使得出现了很多Bloom filter的变种。

 

应用原则和案例

只要使用列表或集合,如果考虑空间效率,就可以考虑使用Bloom filter。应用时,要特别考虑bloom filter的正向错误率影响,对于“零错误”的应用需要相应的辅助机制来消除错误率,否则关键业务不可应用。

Bloom filter被广泛应用于各种领域,比如拼写检查、字符串匹配算法、网络包分析工具、Web Cache、文件系统、存储系统等,这里着重介绍一下Bloom filter在重复数据删除中的应用。主流的重复数据删除技术的基本原理是对文件进行定长或变长分块,然后利用hash函数计算数据块指纹,如果两个数据块指纹相同则认为是重复数据块(同样这里存在数据碰撞问题),只保存一个数据块副本即可,其他相同数据块使用该副本索引号表示,从而实现数据缩减存储空间并提高存储效率。为了查询一个数据块是否重复或者已经存在,需要计算数据块指纹并进行查找,并记录所有唯一数据块的指纹。举一个例子:32TB的数据,平均数据块大小为8KB,每个数据块使用MD5和SHA1计算两个指纹并用64位整数表示唯一块号则共占用44字节((128+160+64)/8),则总共最多需要176GB(32TB/8KB * 44 Byte)的存储空间来保存数据块信息。现在的去重系统数据容量通常多达数十到数百TB,如果把数据块信息全部保存在内存中,显然对内存的需求量非常巨大,出于成本考虑这对商业产品是不现实的。因此,为了在成本和性能两方面作折中,通常的做法是把数据块信息保存在磁盘或SSD上,使用一定内存量作 Cache缓存数据块指纹,利用时间局部性和空间局部性来提高查找性能。这种方法的一个关键问题是,如果新的数据块是不重复的,查找时会出现Cache不命中,从而引起大量的磁盘读写操作。由于磁盘或SSD性能要远远小于内存的,对查找性能影响非常大。Bloom filter可以有效解决这个问题,DataDomain中的Summary Vector就是采用Bloom filter来实现的。对于前面的例子,一个数据块用3个hash函数计算指纹最多占用3个位,则Bloom filter仅需要1.5GB = 32TB/8KB * 3 /8 bytes的内存空间,这即使对于普通的PC机都不是问题。引入Bloom filter机制后,对于一个新数据块,首先查找Bloom filter,如果未命中则说明这是一个新的唯一数据块,直接保存数据块和并Cachr数据块信息即可;如果命中,则说明这有可能是一个重复数据块,需要通过进一步的hash或tree查找进行确认,此时需要Cache与Disk进行交互。受益于Bloom filter以及Cache,DataDomain系统可以减少99%的磁盘访问,从而利用少量的内存空间大幅提高了数据块查重性能。

 

C语言实现

Bloom filter原理简单但却总能派上大用场,实现起来也非常容易。这里没有重新发明轮子,而是引用了文献[5]的C语言实现,总共不过百来行代码,而且还有测试例程。完整C程序请访问 http://en.literateprograms.org/Bloom_filter_%28C%29?oldid=16893

 

  1. /* bloom.h */  
  2. #ifndef __BLOOM_H__  
  3. #define __BLOOM_H__  
  4.   
  5. #include<stdlib.h>  
  6.   
  7. typedef unsigned int (*hashfunc_t)(const char *);  
  8. typedef struct {  
  9.     size_t asize;  
  10.     unsigned char *a;  
  11.     size_t nfuncs;  
  12.     hashfunc_t *funcs;  
  13. } BLOOM;  
  14.   
  15. BLOOM *bloom_create(size_t size, size_t nfuncs, ...);  
  16. int bloom_destroy(BLOOM *bloom);  
  17. int bloom_add(BLOOM *bloom, const char *s);  
  18. int bloom_check(BLOOM *bloom, const char *s);  
  19.   
  20. #endif  
  21.   
  22.   
  23. /* bloom.c */  
  24. #include<limits.h>  
  25. #include<stdarg.h>  
  26.   
  27. #include"bloom.h"  
  28.   
  29. #define SETBIT(a, n) (a[n/CHAR_BIT] |= (1<<(n%CHAR_BIT)))  
  30. #define GETBIT(a, n) (a[n/CHAR_BIT] & (1<<(n%CHAR_BIT)))  
  31.   
  32. BLOOM *bloom_create(size_t size, size_t nfuncs, ...)  
  33. {  
  34.     BLOOM *bloom;  
  35.     va_list l;  
  36.     int n;  
  37.       
  38.     if(!(bloom=malloc(sizeof(BLOOM)))) return NULL;  
  39.     if(!(bloom->a=calloc((size+CHAR_BIT-1)/CHAR_BIT, sizeof(char)))) {  
  40.         free(bloom);  
  41.         return NULL;  
  42.     }  
  43.     if(!(bloom->funcs=(hashfunc_t*)malloc(nfuncs*sizeof(hashfunc_t)))) {  
  44.         free(bloom->a);  
  45.         free(bloom);  
  46.         return NULL;  
  47.     }  
  48.   
  49.     va_start(l, nfuncs);  
  50.     for(n=0; n<nfuncs; ++n) {  
  51.         bloom->funcs[n]=va_arg(l, hashfunc_t);  
  52.     }  
  53.     va_end(l);  
  54.   
  55.     bloom->nfuncs=nfuncs;  
  56.     bloom->asize=size;  
  57.   
  58.     return bloom;  
  59. }  
  60.   
  61. int bloom_destroy(BLOOM *bloom)  
  62. {  
  63.     free(bloom->a);  
  64.     free(bloom->funcs);  
  65.     free(bloom);  
  66.   
  67.     return 0;  
  68. }  
  69.   
  70. int bloom_add(BLOOM *bloom, const char *s)  
  71. {  
  72.     size_t n;  
  73.   
  74.     for(n=0; n<bloom->nfuncs; ++n) {  
  75.         SETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize);  
  76.     }  
  77.   
  78.     return 0;  
  79. }  
  80.   
  81. int bloom_check(BLOOM *bloom, const char *s)  
  82. {  
  83.     size_t n;  
  84.   
  85.     for(n=0; n<bloom->nfuncs; ++n) {  
  86.         if(!(GETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize))) return 0;  
  87.     }  
  88.   
  89.     return 1;  
  90. }  

 

 

参考文献

[1] http://en.wikipedia.org/wiki/Bloom_filter
[2] http://www.cs.jhu.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf
[3] http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf
[4] http://www.partow.net/programming/hashfunctions/#BloomFilters
[5] http://en.literateprograms.org/Bloom_filter_%28C%29?oldid=16893
[6] http://www.datadomain.com/pdf/DataDomain-Avoiding-the-Bottleneck-with-Dedupe.pdf

分享到:
评论

相关推荐

    介绍Bloom Filter(布隆过滤器)原理、实现及具体应用

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型...通过学习提供的9个PPT和PDF文档,你可以深入了解Bloom Filter的工作机制、性能分析以及在不同场景下的应用实例,从而更好地理解和掌握这一重要的数据结构。

    带bloom filter 的c网络爬虫

    **标题:“带bloom filter 的c网络爬虫”** ...通过分析源代码(尤其是spider.c),我们可以深入了解如何在实际项目中集成Bloom Filter,以及其与队列等数据结构的配合使用,以优化网络爬虫的性能和效率。

    bloom filter 相关论文资料

    综上所述,这份“bloom filter”的论文资料集是深入理解、研究和应用布隆过滤器的重要资源,涵盖了从基本概念到实际应用的多个方面,对于IT从业者尤其是数据结构和算法领域的专业人士来说,是非常宝贵的参考资料。

    bloom filter布隆过滤器学习资料大全

    布隆过滤器(Bloom Filter)是一种空间效率极高...通过这个“bloom filter布隆过滤器学习资料大全”,你可以深入研究布隆过滤器的理论、算法实现以及在不同场景下的应用实例,提升对这一重要数据结构的理解和应用能力。

    如何使用bloomfilter构建大型Java缓存系统Ja

    在Java中,可以使用开源库如Guava提供的BloomFilter类来实现。首先,需要创建一个BloomFilter实例,指定预期的元素数量和错误率。错误率通常是一个较小的浮点数,如0.01,表示1%的误判率。Guava的BloomFilter构造器...

    LDFD-BloomFilter-master.zip

    为了解决这个问题,"LDFD-BloomFilter-master.zip"提供了一种基于Bloom Filter的高效解决方案。 Bloom Filter是一种空间效率极高的概率数据结构,用于判断一个元素是否在一个集合中。它可能会产生假阳性(False ...

    Go-ring-提供了一个高性能和线程安全的bloom过滤器Go实现

    首先,让我们深入理解Bloom Filter的工作原理。Bloom Filter由一块位数组和几个不同的哈希函数组成。当一个元素被添加到过滤器中时,每个哈希函数会将元素映射到位数组的不同位置,并将这些位置设置为1。查询时,...

    Go-bloom-Bloomfilters在Go中的实现

    本文将深入探讨Bloom Filter的基本原理、Go语言中的实现以及其在实际应用中的优缺点。 ### 一、Bloom Filter基本原理 1. **概率性质**:Bloom Filter允许误判,即可能会把不存在的元素判断为存在,但不会出现误负...

    bloom filter

    通过阅读和分析这些代码,我们可以深入理解如何在Delphi中实际应用布隆过滤器算法。 总的来说,布隆过滤器是一种在时间和空间效率之间做出权衡的数据结构,尤其适用于大数据场景下的成员资格查询。在Delphi环境中,...

    C语言实现的Bloomfilter算法。.zip

    通过阅读和分析源码,我们可以更深入理解上述概念是如何在实际程序中实现的,例如如何定义位数组,如何定义和应用哈希函数,以及如何实现插入和查询操作等。 以上就是关于C语言实现的Bloom Filter算法的主要知识点...

    U201990056_陈昱夫_课程报告1

    参考文献和附录提供了更多的学习资源和可能的细节分析,为读者深入了解Bloom Filter提供了路径。 总的来说,这份报告全面地介绍了Bloom Filter这一高效的数据结构,从基本原理到设计优化,再到实验验证,深入浅出地...

    Go-Cuckoofilter:在Go中计数bloomfilter的一个更好替换

    通过深入理解Cuckoo Filter的工作原理和Go-CuckooFilter的实现,开发者能够更好地利用这一工具来提升软件的性能和用户体验。在实际项目中,可以根据具体需求调整参数,如容量、错误率等,以达到最佳的性能效果。

    U201914974_杨超淇_课程报告1

    本报告旨在深入理解Bloom Filter的应用背景和基本原理,并在此基础上进行系统设计与性能测试。 Bloom Filter是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它由多个哈希函数组成,...

    U201915093_赵英举1

    通过这样的实验,学生可以深入理解Bloom Filter的工作机制,并掌握如何在实际问题中应用这一数据结构。 综上所述,本次实验报告详尽地介绍了使用Bloom Filter处理多维数据索引的方法,从理论到实践,充分展示了这一...

    Bloom_filter_(C).zip_bloom_bloom filter_c++布隆_布隆过滤器

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在C++中实现布隆过滤器,可以...这个C++实现提供了一个很好的起点,帮助开发者深入理解和使用这一数据结构。

    海量数据去重的Hash与BloomFilter,bitmap1

    本文将深入探讨两种常用的技术:哈希和布隆过滤器,以及它们在处理海量数据时的应用。 哈希算法是数据去重的基础,它能够将任意大小的数据映射为固定长度的哈希值。在分布式一致性哈希算法中,哈希空间被组织成一个...

    libbloom.tar_bloom_

    接下来,我们将深入探讨Bloom Filter的几个关键方面: 1. **哈希函数选择**:Bloom Filter的有效性很大程度上取决于所使用的哈希函数。理想的哈希函数应具备均匀分布性和低冲突率。通常,会选择多个不同的哈希函数...

    bloomfilter:Bloom过滤器的简单轻量级实现

    在`bloomfilter-master`这个压缩包中,很可能包含了Bloom过滤器的C++实现代码,包括位数组的管理、哈希函数的设计以及添加和查询元素的接口。通过阅读和分析这些源代码,我们可以深入理解Bloom过滤器的工作原理和...

    test-bloomfilter.zip

    要使用Redisson实现布隆过滤器,我们需要在SpringBoot应用中引入Redisson的依赖,配置Redis连接,并创建对应的BloomFilter实例。在代码中,我们可以调用`bf.add()`方法向过滤器添加元素,使用`bf.contains()`方法...

    bloom-filter:Java中Bloom过滤器的实现

    布隆过滤器是一种概率型数据结构,...通过阅读源代码,我们可以深入理解布隆过滤器的工作机制,以及如何根据实际需求进行定制和优化。例如,可以自定义哈希函数、调整位数组大小,或者结合其他数据结构来降低误判率。

Global site tag (gtag.js) - Google Analytics