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
- /* bloom.h */
- #ifndef __BLOOM_H__
- #define __BLOOM_H__
- #include<stdlib.h>
- typedef unsigned int (*hashfunc_t)(const char *);
- typedef struct {
- size_t asize;
- unsigned char *a;
- size_t nfuncs;
- hashfunc_t *funcs;
- } BLOOM;
- BLOOM *bloom_create(size_t size, size_t nfuncs, ...);
- int bloom_destroy(BLOOM *bloom);
- int bloom_add(BLOOM *bloom, const char *s);
- int bloom_check(BLOOM *bloom, const char *s);
- #endif
- /* bloom.c */
- #include<limits.h>
- #include<stdarg.h>
- #include"bloom.h"
- #define SETBIT(a, n) (a[n/CHAR_BIT] |= (1<<(n%CHAR_BIT)))
- #define GETBIT(a, n) (a[n/CHAR_BIT] & (1<<(n%CHAR_BIT)))
- BLOOM *bloom_create(size_t size, size_t nfuncs, ...)
- {
- BLOOM *bloom;
- va_list l;
- int n;
- if(!(bloom=malloc(sizeof(BLOOM)))) return NULL;
- if(!(bloom->a=calloc((size+CHAR_BIT-1)/CHAR_BIT, sizeof(char)))) {
- free(bloom);
- return NULL;
- }
- if(!(bloom->funcs=(hashfunc_t*)malloc(nfuncs*sizeof(hashfunc_t)))) {
- free(bloom->a);
- free(bloom);
- return NULL;
- }
- va_start(l, nfuncs);
- for(n=0; n<nfuncs; ++n) {
- bloom->funcs[n]=va_arg(l, hashfunc_t);
- }
- va_end(l);
- bloom->nfuncs=nfuncs;
- bloom->asize=size;
- return bloom;
- }
- int bloom_destroy(BLOOM *bloom)
- {
- free(bloom->a);
- free(bloom->funcs);
- free(bloom);
- return 0;
- }
- int bloom_add(BLOOM *bloom, const char *s)
- {
- size_t n;
- for(n=0; n<bloom->nfuncs; ++n) {
- SETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize);
- }
- return 0;
- }
- int bloom_check(BLOOM *bloom, const char *s)
- {
- size_t n;
- for(n=0; n<bloom->nfuncs; ++n) {
- if(!(GETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize))) return 0;
- }
- return 1;
- }
参考文献
[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)是一种空间效率极高的概率型...通过学习提供的9个PPT和PDF文档,你可以深入了解Bloom Filter的工作机制、性能分析以及在不同场景下的应用实例,从而更好地理解和掌握这一重要的数据结构。
**标题:“带bloom filter 的c网络爬虫”** ...通过分析源代码(尤其是spider.c),我们可以深入了解如何在实际项目中集成Bloom Filter,以及其与队列等数据结构的配合使用,以优化网络爬虫的性能和效率。
综上所述,这份“bloom filter”的论文资料集是深入理解、研究和应用布隆过滤器的重要资源,涵盖了从基本概念到实际应用的多个方面,对于IT从业者尤其是数据结构和算法领域的专业人士来说,是非常宝贵的参考资料。
布隆过滤器(Bloom Filter)是一种空间效率极高...通过这个“bloom filter布隆过滤器学习资料大全”,你可以深入研究布隆过滤器的理论、算法实现以及在不同场景下的应用实例,提升对这一重要数据结构的理解和应用能力。
在Java中,可以使用开源库如Guava提供的BloomFilter类来实现。首先,需要创建一个BloomFilter实例,指定预期的元素数量和错误率。错误率通常是一个较小的浮点数,如0.01,表示1%的误判率。Guava的BloomFilter构造器...
为了解决这个问题,"LDFD-BloomFilter-master.zip"提供了一种基于Bloom Filter的高效解决方案。 Bloom Filter是一种空间效率极高的概率数据结构,用于判断一个元素是否在一个集合中。它可能会产生假阳性(False ...
首先,让我们深入理解Bloom Filter的工作原理。Bloom Filter由一块位数组和几个不同的哈希函数组成。当一个元素被添加到过滤器中时,每个哈希函数会将元素映射到位数组的不同位置,并将这些位置设置为1。查询时,...
本文将深入探讨Bloom Filter的基本原理、Go语言中的实现以及其在实际应用中的优缺点。 ### 一、Bloom Filter基本原理 1. **概率性质**:Bloom Filter允许误判,即可能会把不存在的元素判断为存在,但不会出现误负...
通过阅读和分析这些代码,我们可以深入理解如何在Delphi中实际应用布隆过滤器算法。 总的来说,布隆过滤器是一种在时间和空间效率之间做出权衡的数据结构,尤其适用于大数据场景下的成员资格查询。在Delphi环境中,...
通过阅读和分析源码,我们可以更深入理解上述概念是如何在实际程序中实现的,例如如何定义位数组,如何定义和应用哈希函数,以及如何实现插入和查询操作等。 以上就是关于C语言实现的Bloom Filter算法的主要知识点...
参考文献和附录提供了更多的学习资源和可能的细节分析,为读者深入了解Bloom Filter提供了路径。 总的来说,这份报告全面地介绍了Bloom Filter这一高效的数据结构,从基本原理到设计优化,再到实验验证,深入浅出地...
通过深入理解Cuckoo Filter的工作原理和Go-CuckooFilter的实现,开发者能够更好地利用这一工具来提升软件的性能和用户体验。在实际项目中,可以根据具体需求调整参数,如容量、错误率等,以达到最佳的性能效果。
本报告旨在深入理解Bloom Filter的应用背景和基本原理,并在此基础上进行系统设计与性能测试。 Bloom Filter是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它由多个哈希函数组成,...
通过这样的实验,学生可以深入理解Bloom Filter的工作机制,并掌握如何在实际问题中应用这一数据结构。 综上所述,本次实验报告详尽地介绍了使用Bloom Filter处理多维数据索引的方法,从理论到实践,充分展示了这一...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在C++中实现布隆过滤器,可以...这个C++实现提供了一个很好的起点,帮助开发者深入理解和使用这一数据结构。
本文将深入探讨两种常用的技术:哈希和布隆过滤器,以及它们在处理海量数据时的应用。 哈希算法是数据去重的基础,它能够将任意大小的数据映射为固定长度的哈希值。在分布式一致性哈希算法中,哈希空间被组织成一个...
接下来,我们将深入探讨Bloom Filter的几个关键方面: 1. **哈希函数选择**:Bloom Filter的有效性很大程度上取决于所使用的哈希函数。理想的哈希函数应具备均匀分布性和低冲突率。通常,会选择多个不同的哈希函数...
在`bloomfilter-master`这个压缩包中,很可能包含了Bloom过滤器的C++实现代码,包括位数组的管理、哈希函数的设计以及添加和查询元素的接口。通过阅读和分析这些源代码,我们可以深入理解Bloom过滤器的工作原理和...
要使用Redisson实现布隆过滤器,我们需要在SpringBoot应用中引入Redisson的依赖,配置Redis连接,并创建对应的BloomFilter实例。在代码中,我们可以调用`bf.add()`方法向过滤器添加元素,使用`bf.contains()`方法...
布隆过滤器是一种概率型数据结构,...通过阅读源代码,我们可以深入理解布隆过滤器的工作机制,以及如何根据实际需求进行定制和优化。例如,可以自定义哈希函数、调整位数组大小,或者结合其他数据结构来降低误判率。