（计算机软件与理论专业论文）bloom+filter改进及其在分布式系统中的应用研究.pdf

ab s t r a c t u s i n g a v e c to r t o p r e s e n t a d a t a s e t , b l o o m f i lt e r c a n e ff e c ti v e l y s u p p o r t d a t a l o o k i n g u p b y h a s h f u n c t i o n s . i t i s a g o o d s o l u t i o n t o a p r o b l e m : w h e t h e r a c e r ta i n e l e m e n t b e l o n g s t o a g i v e n s e t o r n o t . i n d i s t r i b u t e d a p p l i c a t i o n e n v i r o n m e n t , b l o o m f i l t e r w i l l b e i n g o o d a p p l i c a t i o n s u c h a s r e s o u r c e s s e a r c h i n g a n d r o u t i n g . i n r e c e n t y e a r s , a g a i n s t t h e o r d i n a r y b l o o m f i l t e r , m u l t i p l e i m p r o v e m e n t s , w h i c h w o u l d i n c l u d e t h e c o u n t i n g b l o o m f i l t e r , c o m p r e s s i o n b l o o m f i l t e r a n d s p l i t b l o o m f i l t e r , h a v e b e e n i n t r o d u c e d . c o u n t i n g b l o o m f i l t e r c a n s o l v e a d e f e c t o f o r d i n a ry b l o o m f i l t e r : b l o o m f i l t e r c a n o n l y a d d e l e m e n t s i n t o a s e t , a n d n o t f o r e l e m e n ts d e l e t e d ; wi t h t h e c o m b i n a t i o n o f d a t a c o m p r e s s i o n t h e o ry , s o i n a d i s t r i b u t e d a p p l i c a t i o n , c o m p r e s s i o n b l o o m f i l t e r c a n b e v e r y e ff e c t i v e i n r e d u c i n g n e t w o r k s t r a n s m i s s i o n ; a n d s p l i t b l o o m f i l t e r c a n b e u s e d t o a l l e v i a t e d y n a m i c gro w t h o f t h e d a t a s e t i n t h e d i s t r i b u t e d e n v i r o n m e n t . b a s e d o n t h e a n a l y s i s a b o v e , t h i s p a p e r p r e s e n t s t w o k i n d s o f n e w b l o o m f i l t e r . t h e k - c o m b i n e d b l o o m f i l t e r , li k e s p l i t b l o o m f i l t e r , i t a l s o a i m s a t t h e p r o b l e m o f d y n a m i c gr o w th加t h e d i s t r i b u t e d e n v ir o n m e n t . c o m p a r e d w i t h b l o o m f i l t e r a n d s p l i t b l o o m f i l t e r , t h i s p a p e r i s t o g i v e i n d i c a t o ry a n a l y s i s t o p r o v e t h a t i t c a n g e t a b e t t e r b a l a n c e o f t h e t h r e e i n d i c a t o r s : f a l s e p o s i t i v e e r r o r , v e c t o r s p a c e s a n d t h e a v e r a g e t i m e t o d e t e r m i n e ; t h e s e c o n d i m p r o v e d b l o o m f i lt e r i s f u l l y c o m b i n e d b l o o m f i l t e r , i t c a n c o m p l e t e l y e l i m i n a t e e x t e rn a l c o n fl i c t s c a u s e d b y o r d i n a r y b l o o m f i l t e r . a t t h e c o s t o f s o m e e x t r a s p a c e s , i t i s c a n g e t l o w e r f a l s e p o s i t i v e e r r o r , w h i c h w i l l b e i n m o r e e ff e c t i v e a p p l i c a t i o n . t h e p a p e r a l s o d i s c u s s e d t h e d i s t r i b u t i n g p r o b a b i l i t y o f t h e h a s h f u n c t i o n s u s e d i n b l o o m f i l t e r , a n d h a s a g e n e r a l e v a l u a t i o n w h i c h c a n g i v e a r i g h t o f a n a l y z i n g a l l t h e d i s t r i b u t io n s . f i n a l l y , t h i s p a p e r d i s c u s s e s s o m e a p p l i c a t i o n s o f t h e o r d i n a r y b l o o m f i l t e r a n d t h e n e w i m p r o v e d v e r s i o n s o f t h e b l o o m f i l t e r i n d i s t r i b u t e d s y s t e m s , a n d t h e n e x p e r i me n t a l r e s u l t s a g a i n s t o n e o f t h e a p p l i c a t i o n s a b o v e a r e p r e s e n t e d a n d a n a l y z e d . ab s t r a c t k e y wo r d s : b l o o m f il t e r ; k - d i v i e d b l o o m f il t e r ; f u l l y c o m b i n e d b l o o m f i l t e r ; h a s h i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、 保存、使用学位论文的 规定，同意如下 各项内 容:按照学校要求提交学位论文的印刷本和电 子版本: 学校有权保存学 位论文的印刷本和电 子版， 并采用影印、 缩印、扫描、数字化或其它手段保存 论 文;学校有权提供目 录检索以及提供本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有关部门 或者机构送交论文的复印件和电子版; 在 不以 赢利为目的的前提下，学校可以 适当复制论文的部分或全部内 容用于学术 活动 。 学 位 论 文 作 ” 签 磁 砰 呵 年6 月/ 日 经指导教师同意，本学位论文属于保密， 在 年解密后适用本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部5 年 ( 最长5年，可少于5 年) 秘密*1 0 年 ( 最长 1 0 年，可少于 1 0年) 机密*2 0 年 ( 最长 2 0 年，可少于 2 0 年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已 经注明引 用的内容外， 本学位论文的 研究成果不包含 任何他人创作的、已公 开发表或者没有公开发表的作品的内容。 对本论文所涉 及的研究工作做出贡献的其他个人和集体， 均己 在文中以明 确方式标明。本学 位论文原创性声明的法律责任由 本人承担。 学 位 论 “ 作 者 签 “ 砖只 w0 ) 年 g 月2 日 第一章 引言 第一章引言 第一节 b l o w n f i l t e r 与分布式系统应用背景介绍 计算机系统正在经历一场革命。 自 从1 9 4 5 年第一台现代计算机发明一直到 1 9 8 5 年，由于计算机体积庞大、价格昂贵，而且没有把这些计算机连接起来就 手段，所以只能单独使用它们。然而，从2 0 世纪8 0 年代中期开始，信息技术 领域中两方面的进步使得这种局面大为改观。 第一个进步是高性能微处理器的开发。起初的这些计算机是8 位机，但是 很快1 6 位、 3 2 位乃至6 4 位的c p u纷至沓来， 并得到普及。 于是p c机的性能 几乎能与大型机媲美，而价格却便宜很多。计算机业存在着一个著名的 “ 摩尔 定律”( 戈登 摩尔，1 9 6 5年) 半导体芯片每 1 8个月集成度翻番，性能提 高一倍，价格减半。英特尔总裁葛鲁夫在微处理器诞生2 5周年的演讲说， “ 在 过去的2 5 年里，微处理器的发展完全遵循了摩尔定律。在未来的1 0 年里仍将 按照摩尔定律发展， 。 第二个进步是高速计算机网络的发明。局域网和广域网技术使得计算机之 间数据交换跨越了地理上的障碍，计算机间的数据传输速率从 6 4 k b / s到若干 g b / s 不等。 由于以 上这些技术可供使用，因此把若干由大量计算机组成的计算系统彼 此通过高速网络连接，不但是可行的，而且是很容易实现的。这种系统一般被 分为两类:集中式系统和分布式系统。集中式系统中存在一个中心节点，它负 责整个系统的资源定位和数据分发; 而分布式系统则不存在这么一个中心节点， 系统中每个节点都是平等的，它们之间通过某种特殊的方式进行资源定位和数 据分发。 简而言之，分布式系统是若干独立计算机的集合，它们之间通过计算机网 络实现资源的共享和数据的交互，每台计算机都是系统中平等的一个节点。对 于用户来说，系统内部的网络连接和组织结构是透明的，用户和应用程序无论 何时何地都能够以一种一致和统一的方式与分布式系统进行交互。 集中式系统的中心节点使得系统在逻辑上能够很简单方便地实现计算或存 第一章 引言 储。当需要用到其他节点的资源时，每个节点的请求都被直接发往中心节点， 由中心节点处理决定该请求应该转发至何处。由于分布式系统中不存在中心节 点，如何分发各个节点相互间的请求或应答就成为关系到分布式系统性能高低 的一个关键问题。 1 9 7 0 年b l o o m就 发明b l o o m f i lt e : 算法p ， 该 算 法能 很 好 地解决 信息的 表 示查找中一个基本问题: 判定一个元素是否属于一个给定的集合。 但是由于受 到当时计算机技术水平的限 制，该算法并没有得到大规模的应用。随着近年来 有关分布式系统研究的升温， 研究者们发现， b l o o m f i l t e r 算法能很好地应用于 分布式系统中地查找问 题。 由 于b lo o m f i l t e r 算法是一种利用h a s h 表的 信息组织方式， 它在查找过程 中所需要的时间开销是一个常量，查找速度很快， 但它总存在冲突的发生，这 就使得b l o o m f i l t e r 算法的一个不足之处是存在查找误称。 但是经过仔细分析， 这种误称有它本身的特性: 1 .经过b l o o m f i lt e r 计算后， 如果发现查找的元素不在一个给定集合 中，那么该元素肯定就不在这个集合中; 2 .经过b l o o m f i l t e r 计算后， 如果结果表明查找的元素属于一个给定 集合，而实际上该元素却不在这个集合中，此时产生查找误称; 3 .特性2 中所提到的误称发生的可能性是非常小的， 完全可以 通过改 变h a s h 函数个数和存储空间的大小， 使得误称率小到足以 接受的 程度。 除此之外，b l o o m f i l t e r 还存在其他特性，由于b l o o m f i l t e r 用一个位向量 来表示数据集合， 与传统的精确h a s h 组织方式相比， 它能大大节约存储信息的 空间开销。 考虑将其用于分布式系统中，在节点间通过网 络进行数据交互时， 就能利用b l o o m f i lt e r 算法来降低所需要传输量。 第二节本论文的工作与结构 1 9 7 0 年b l o o m提出b l o o m f i lt e r 以 来， b l o o m f i l t e r 起初应用于数据库系统。 随着近年来对分布式系统应用的广泛而深入的研究， b l o o m f i l t e r 的应用成为研 究热点。各种改进型的b l o o m f i l t e r 相继问世，针对具体的应用背景， 它们都 能得到较平凡b l o o m f i l t e : 更好的性能。 第一章 引言 本文在充分研究前人工作的基础上，继续相关工作，完成以下研究: . 首先介绍几种重要的改进型b l o o m f i l t e r ，并分别对其性能指标做出分 析。 . 随后在前人的研究 基础上提出两种新的改进型b l o o m f i l t e r -k分组 合型b l o o m f il t e r 和完全组合型b l o o m f i l t e r 。前者在增加较小的空间 代价下既能 够降 低b l o o m f i l t e r 的误称率， 又能在数据集合动态增长的 时候得到与拆分型 b l o o m f i l t e r 相近的误称率，同时比拆分型 b l o o m f i l t e r 有更高的 时间 和空间效率。后者能完全消除平凡b l o o m f i lt e r 引 起的 外部冲突， 在增加一定空间 代价的 情况下比 平凡的b lo o m f i l t e r 有 更低的误称率，因此在实际应用中若对空间开销留有余地时，不增加 时间复杂度， 能够替代平凡 b l o o m f i l t e r 而获得更低的误称率。本文对 此都做出证明并给出实验数据。 . 提出了一般h a s h 函数分布情况下b lo o m f i l t e r 的基本性能指标公式， 为进一步的研究提供了基础。 . 探讨b l o o m f i l t e r 的 应用范围， 特别是 在分布式环境下用于共享资源的 查找和网络路由的查找。 . 最后针对we b c a c h e 的应用背景，分别对k分组合型b l o o m f i l t e r 和 完全组合型b l o o m f i lt e r 做出 模拟实验并分析实 验数据。 本论文的章节也按照以上顺序组织。最后列出了本论文所参考的文献，以 便将来在对该问题的相关研究中查阅。 第二章 b l o o m f i l t e r 基本原理及 性能分析 第二章 b l o o m f i l t e r 基本原理及性能分析 第一节b l o o m f i l t e r 的评价指标 2 . 1 . 1 误称率和平均判定时间 为了 评价b l o o m f i l t e r 的 性能，先给出 两个 重要指标: 误称率和平均判定 时间。为了方便讨论，本文引入以下变量: n:位向 量v的大小 ( b i t ) ; p :误称率; t :平均判定时间; n :数据集合的大小; d:用于从集合元素映射到位向量的h as h函数的个数; p : n 个数据插入 位向 量v后， v中 某位为1 的 概率; 权 : 第1 个h as h 函 数; r :一次h as h 值比较的时间: 第二节平凡型b l o o m f i l t e r 2 . 2 . 1 问题的提出 信息的表示和查找是计算机科学要解决的基本问题之一。在信息处理的过 程中，采用何种查找方式依赖于信息的表示方法。 在众多信息表示方法中， 哈 希 ( h a s h )表的信息组织方式使得查找过程具有较其他数据结构更优异的平均 第二章 b l o o m f i l t e r 幕 本 原 理 及 性 能 分 析 查找性能。 利用h a s h 表的这种优势可以设计出各种满足不同表示和查找需求的 数 据结 构， b l o o m f i l t e r 1 112 4 1 就是其中 之 一。 b l o o m f i l t e r能很好地解决下列基本问 题:某个数据是否包含在一个集合 中。它利用一个位向量来表示一个集合的所有元素，与数据完全表示相比，占 用的空间非常少。虽然b l o o m f i l t e r 的查找过程可能存在误差，但这种误差仅 仅可能出现在非集合元素被误认为属于该集合的情形中，本文把它称之为误称 率 ( f a l s e p o s i t i v e e r r o r , b u t n o f a l s e n e g a t i v e e r r o r ) ， 而 且在一定 的 条 件下， 这 个 误称率能够小到足以使人容忍。 自 从1 9 7 0 年问世以来， 有关b lo o m f i lt e : 的基本理论几乎没有任何改变， 直到1 9 9 0 年r a n d o m f i l t e r l2 的 提出 。 r a n d o m f i l t e r 与b lo o m f i l t e r 的 唯一 区别 就在于h a s h 函 数的 分布特性。 在r a n d o m f i lt e : 中数 据的关键字( k e y ) 映射到 位向 量中 的h a s h 值是 独 立的， 而在b lo o m f i lt e r 中， 同 一k e y 值被不同h a s h 函数映射到位向量中的h a s h 值是不同的。 r a n d o m f i l t e r 比b l o o m f i lt e r 有更低 的误称率和平均判定时间。 2 . 2 . 2 基本原理 b l o o m f i l t e r和r a n d o m f i lt e r 的基本原理是相同的。它们都使用长度为n 的 位向 量v来表示元素集合a = a l ,a 2 . . . . . . . a n ) 。 在初始状态， v中 每一 位都被 设置为0 。 对于 集合中的每一个元素的k e y 值， 都分别 使用d 个h a s h 函 数把它 映射到v中，在得到的h a s h 值的相应位上置1 ，其他位保持为0 . 当集合中所有元素都按上述办法在v中表示完成后， 就可以对一个给定元 素的k e y 值查 找 它是 否属 于该 集合。 查 找 过 程如 下: 分别使用d 个h a s h 函数对k e y 进行h a s h 运算。 检查每一个h a s h 值在v 中对应位置是否为1 ， 只要某个h a s h 值在v中的位置为0 ， 就可以判定该元素 不在集合中。否则元素就可被认为属于该集合。 由 于b l o o m f i l t e r 采 用的d 个h a s h 函 数 对同 一个k e y 值得到的h a s h 值是 不同的， 每个k e y 都能 得到d 个不同 的h a s h 值; 而r a n d o m f i l t e : 采 用d 个独 立的 均匀分布h a s h 函数，每个k e y 得到的h a s h 值随机分布在v中。 例1 描 述了b l o o m f i l t e r 集合表示以 及 元素查找过程。 例 1 : 第二章 b l o o m f i l t e r 基本原 理及性能分析 假设有一个3 0 位的位向量v ，它们的地址值从0到2 9 。另外假设有d =4 个h a s h 函 数h l , h 2 , h 3 , h 4 以 及 一 个 有4 个元 素的 集合a 夏 a l , a 2 , 0, a 4 , 它们的k e y 值分别 为k l , k 2 , k 3 和k 4 . 以 下是对每个k e y 值做d 次h a s h 的 值: 对 k l , h l ( k l ) =0 , h 2 ( k ) =1 2 , h 3 ( k l )=3 , h 4 ( k l ) =2 0 ; 对k 2 , h l ( k 2 ) =2 , h 2 ( k 2 ) =7 , h 3 ( k 2 ) =1 5 , h 4 ( k 2 ) =9 ; 对 k 3 , h l ( k 3 ) =7 , h 2 ( k 3 )二1 7 , h 3 ( k 3 ) =2 9 , h 4 ( k 3 ) =3 0 ; 对 k 4 , h l ( k 4 ) =5 , h 2 ( k 4 ) =1 4 , h 3 ( k 4 ) =2 8 , h 4 ( k 4 ) =2 3 : v的初始状态: a d 由 e s s 0 1 0 2 0 3 0 h a s h s p a c e 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 插入元素 a l 后v的状态: a d d r e s s 0 1 0 2 0 3 0 h a s h s p a c e i 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 插入元素a 2 后v的状态: a d d r e s s 0 1 0 2 0 3 0 h a s h s p a c e i 1 1 0 1 1 i o i 0 l 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 插入元素 a 3 后 v的状态: a d d r e s s 0 1 0 2 0 3 0 h a s h s p a c e 川o f 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 插入元素a 4 后v的最终状态: h a s h s p a c e 0 1 0 2 0 3 0 x 1 1 0 i 1 1 0 1 0 1 1 0 1 1 1 0 1 0 ， 1 0 1 1 1 l o i l l 0 1 0 1 1 1 0 1 0 l 1 0 1 0 1 0 1 1 1 1 1 1 第二章 b l o o m f i l t e r 基本 原 理 及 性能分析 假设 现有3 个元素a 2 , a 5 , a 6 需要判定 是否属于集合a ， 不 妨令它 们的k e y 值分别为k 2 , k 5 , k 6 . 对 k 2 , h l ( k 2 ) =2 , h 2 ( k 2 ) =7 , h 3 ( k 2 )二1 5 , h 4 ( k 2 ) =9 ad d r e s s h a s h s p a c e t e s t i n g k 2 由于k 2的每个h a s h 值对应在v上的值都为 1 ， 因此a 2 被认为是集合的元 素。 对 k 5 , h l ( k 3 )二7 , h 2 ( k 3 ) =1 7 , h 3 ( k 3 ) =2 7 , h 4 ( k 3 ) =2 6 ad d r e s s h a s h s p a c e t e s t i n g k 5 显然k 5 在v上有对应的0 值，因此可判定a 5 不在集合中。 对 k 6 , h l ( k 4 ) =5 , h 2 ( k 4 ) =7 , h 3 ( k 4 ) =0 , h 4 ( k 4 )=2 ad d r e s s h a s h s p a c e t e s t i n g k 6 0 1 0 2 0 3 0 il lo ll l l lo l l lo ll io 11 10 10 11 10 1 1 11 10 11 10 1o l1 1o lo ll fo lo lo li li li 11 1 u 由于k 6 的h a s h 值在v中对应位置都为1 ，因此a 6 也被认为是集合元素， 但实际上a 6 并不属于该集合，这时误称发生! 由上例及分析可知， b l o o m f i l t e : 中的误称发生时， 唯一可能的情况就是不 在集合中的某个元素被误认为属于该集合， 而不可能发生属于该集合的元素被 排除在集合外的情况。同时由于v中被置为1 的每一位都有可能是不同元素的 映射，因此b l o o m f i l t e r 不允许删除集合元素并把v中对应位置改为0 . r a n d o m f i lt e r 的集合表示和元素查找方式和b l o o m f i l t e r 一致。区别在于 r a n d o m f i l t e r 中h a s h 函数的随机性。 例2 描述了对于例1 中的集合元素， r a n d o m f i l t e r 中可能的h a s h 值。 第二章 b l o w n f i l t e r 基本原理及性能分析 例2 : 对 k 1 ，h l ( k 1 )=0 , h 2 ( k 1 )=0 , h 3 ( k l )=3 , h 4 ( k 1 )=2 0 : 对k 2 , h l ( k 2 ) =2 , h 2 ( k 2 ) =7 , h 3 ( k 2 ) =1 5 , h 4 ( k 2 ) =9 : 对 k 3 , h l ( k 3 ) =7 , h 2 ( k 3 ) =7 , h 3 ( k 3 ) =2 9 , h 4 ( k 3 ) =3 0 ; 对 k 4 , h l ( k 4 ) =5 , h 2 ( k 4 ) =1 4 , h 3 ( k 4 ) =2 8 , h 4 ( k 4 ) =2 3 : 可见k l , k 3 中都出现了相同的h as h 值。 2 . 2 . 3 形式化描述b l o o m f i l t e r 算法 形式化描述b l o o m f i l t e r 算法可以表示如下: 集合表示算法: b i t s t r i n g( s e t a , i n t n ) 凌 f o r ( j = o ; j n ; j 料 ) f o r ( i = o ; i d ; i 什 ) v h i ( a j ) = 1 ; r e t u rn v; 元素查找算法: b o o le a n b f - l o o k u p ( b i t s tr i n g v， d a t a e l e ) i n t i =1 ; w h i l e ( ( v h i ( e le ) = = i 十 十 1 ) e l s e r e t u rn t r u e; 集合元素增加， 则v的更新算法: b i t s t r i n g b f - a d d ( s e t v， d a t a e l e ) f o r ( i n t i =1 ; i d +1 ; i + ) v h i ( e l e ) =1 ; r e t u r n v; 其中， b f r e p r e n t 的 算法时ia l 复杂度为o( d * n ) , b f - l o o k u p和b f - a d d 的算法时间复杂度均为口( d ) . 对b l o o m f i lt e r ，一个数据经过d 个h a s h 函数映射后，v中某位为 1 的概 _ 、 d 羊 刀 代 二 n 对 位为 1 为 。 的 概 率 为 1 一 其 。 n ，.， ， _ _ 上 . j _、 一_ ， _ d . n nm miy : 31 t 元放石， p二卜u 一 下厂。 i v r a n d o m f i l t e r , 的 概 率 为 李， n 一个数据经过一个h a s h函数映射后，v中某位v中某 、 个 函 数 映 射 完 成 后 为。 的 概 率 为 (1 - 与 ， 于 是 n _ ， ， i 、 幽 p=1 一u一 二 下 少 i v 若有某个集合外的元素 k被误认为属于集合，说明该元素对所有的 i ，都 有权 ( k ) = 1 。 因 此误称率为: p err 二 p dp 平均判定时间为: ( 2 . 1 ) t = ( d * p d + 艺 * p 一 ， * ( 一 p ) ) x t1 一 p d 1 一p ( 2 . 2) 第二章 b l o o m f i l t e r 基本原理及性能分析 定理 一: 假设n , n , d 都是自 然数， r a n d o m f i l t e r 的 误称率r 只 。小于 b lo o m f i lt e r 的 误 称率爪 。 即r _ p , t i 一 ) n 与厂 一 : .。 1 一 (1 - 1 .)d 、 ， 一 (1一 ! -)n 刀 i v : . r - p q 二 = 上 2 又p e r ,( d ) 0 _ 一 d n i n i e二 二- ， 即d=( n/ n ) i n 2 时，p e r ， 取最小值 由 上 式 可 以 看 到 ，p e r 。 二 ，。 = ( 1 / 2 ) ( n i n ) in 2 二 0 . 6 1 8 5 . 当n / n = 6 时， 取d = 4 , p e r r = 0 .0 5 6 1 ; 当n / n = 8 时，取d = 6 . p , 。二 0 .0 2 1 5 ; 当n / n = 8 时，取d = 8 , p e r r = 0 .0 0 3 1 4 ; 当n / n = 1 6 时， 取d = 1 1 ，p e r r 二 0 . 0 0 0 4 5 8 ; 可见，若取合适的d 值，理论上的误称率可以达到足够小的要求。 第三节计数型 b l o o m f i l t e r 2 . 3 . 1 问题的提出 如上节所述， 由于位向量v中每一位都有可能和多个h a s h 函数映射相关联， 因此要在数据集合中删除一个元素， 并不能简单地把它在v中对应的所有h a s h 值地址清零。 这就产生了这么一个问 题: 无论是b l o o m f i l t e r 还是r a n d o m f i lt e r 第二章 b l o o m . i t e r 基本原 理及 性能 分 析 原有的算法并不支持数据集合的删除功能。这与实际的需求是相悖的，从而可 能导致数据集合中元素的大幅度增加，大量存在的无效数据不能及时清除而对 b l o o m f i l t e r 的实际过滤功能造成很大影响，最直观的表现就是误称率增加。 为了解决这个问 题， 2 0 0 0 年l i f a n 等人提出了 一种新的b l o o m f i l t e r 算法 并 称之为计 数型b l o o m f i lt e r ( a c c o u n t a b le b l o o m f i lt e r ) 。 它在平凡b l o o m f i l t e r 的 基础上对位向 量v中的 每 一位都增加一 个计数器， 记为 c ( i ) o 初始状态下，c ( i ) 二0 ; 当 数 据 集 合 增 加 一 个 元 素d 时 ， c ( 气 ( d ) ) = c ( 气 ( d ) ) + 1 , ( .1 = 1 , 2 ， 一 ， d ); 当 数 据 集 合 删除 一 个 元 素d 时 ， c ( 气 ( d ) ) = c ( 气 ( d ) ) - 1 , ( 1 = 1 , 2 , ., d )。 2 . 3 . 2 有关计数型b l o o m f i l t e r 的讨论 从以上描述可以 发现，计数型b l o o m f i l t e r 实际上就是在平凡b l o o m f i lt e r 之外再划分一定空间用来保存位向量v中每一个b i t 位实际被多少个h a s h函数 设为 1 。很自 然的，应该讨论到底需要多大空间的计数器，才能保证在往数据 集合中大量添加元素时，计数器不会溢出? 现在假设一个整数i ， 计数器c 大于等于i 的 概率为p ( c _ i ) ，则: p ( c ? i )= nf ” “ ) 尽一 l i j n “ “ ，.lesesesesj d 刀1 厂，lesesl” n 二n d ( n d 一 1 ) ( ”d 一 i+ 1 ) n 之n 2汀 ( e i n 三) 第二章 b l o w n f i l t e r 基 本原 理 及性能分 析 当 i = 1 6 时 ， 尸 ( c ? 1 6 ) 0 .5 5 x t 0 - s x 万。 若 计 数 器 被 设 置 为 4 b it 时 ， 它能表示最大的整数1 是巧。可见，这时的计数器的溢出 概率己经非常小了。 在实际应用中，可以根据集合元素增加和删除的统计学规律来选择适当大小的 计数器。并且可以 认为，那种不断增加元素，使得计数器溢出;然后又不断删 除元素，使得位向量v中某位不该为0 却又为0 的事件序列概率是非常小的， 因此4 位计数器对于大多数应用来说，应该是足够的。 考虑到计数型b l o o m f i l t e r 实际上是 增加了一 个独 立向 量计数空间，如果 采用4 b i t 表示计数 器， 那么 增加的空间代价是4 n b i t 。 为了 进一步减小空间代 价，同时保证计数型b l o o m f i l t e r 的优点，可以 把原来的位向量空间v扩展成 具有计数功能的计数器向量，增加和删除一个元素都直接表现在v上。这样， 只需要稍微改动表示和查找算法就可以实现。 v j 始状态下， v o . . . n - 1 1 = 0 ; 那么，集合的表示、查找、更新、删除算法如下: 集合表示算法: b i t s t r i n g b f es r e p r e n t ( s e t a , i n t n ) 道 f o r ( j = o ; j n ; j +) f o r ( i ” 0 ; i d ; i + ) v h i ( a j ) = v h i ( a j ) + 1 ; r e t u rn v; 元素查找算法: b o o l e a n b f - l o o k u p ( b i t s t r in g v， d a t a e l e ) i n t i =1 ; w h i l e ( ( v h i ( e l e ) != 0 ) 集合元素增加， 则v的更新算法: 第二章 b l o w n f i l t e r 基本原 理及性能分析 b i t s t r i n g b f - a d d ( s e t v， d a t a e l e ) f o r ( i n t i =1 ; i d +1 ; i - ) v h i ( e l e ) = v h i ( e l e ) + 1 ; r e t u r n v; 集合元素删除， 则v的删除算法: b i t s t r i n g b f - d e l ( s e t v， d a t a e l e ) f o r ( i n t i =1 ; i d +1 ; i 料 ) v h i ( e l e ) = v h i ( e l e ) - 1 ; r e t u rn v; 第四节 压缩型 b l o o m f i l t e r 2 . 4 . 1 数据压缩的摘理论 数据压缩不仅起源于 4 0年代由 c l a u d e s h a n n o n首创的信息论，而且其 基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这 条定理借用了 热力学中的名 词“ 嫡 ( e n t r o p y ) 来表示一条信息中 真正需要编码 的信息量: 考虑用 0和 i组成的二进制数码为含有 n个符号的某条信息编码，假 设第 i 个符号 在整条信息中重复出现的概率为 p i ， 则该符号的嫡也即表示该符 号所需的位数位为: e ; 二 一 1 0 9 2 p ,， 由 此 可 得 整 条 信 息 的 墒 也 即 表 示 整 条 信 息 所 需 的 位 数 为 : e = 叉e , 对 下 面 这 条 只 出 现 了。 b 。 三 个 字 符 的 字 符 串 : a a b b a c c b a a 。 字 麟 长 度 为 1 0 ， 字符 a , b , c分别出 现了5 , 3 , 2次， 则 a b c 在信息中出 现的概率分别 为 0 . 5 , 0 . 3 , 0 .2 ， 他们的 嫡分别为: e a = - l o g 2 ( 0 .5 ) =1 ; e b = - lo g 2 ( 0 .3 ) =1 . 7 3 7 ; e c = - l o g 2 ( 0 .2 ) = 2 .3 2 2 . 第二章 b l o o m f i l t e r 篆本原理及性能分析 于是整条信息的 墒也即 表达整个字符串需要的 位数为: e= e a * 5 +e b * 3 + e c * 2 =1 4 . 8 5 5位。 若以上字符串采用a s c i i 编码， 用较少的位数表示较频繁出现的符号 需要8 0 位才能表示完全信息! 简单地讲， ，这就是数据压缩的基本准则。 2 . 4 . 2 压缩型b l o o m f i l t e r 应用 b l o o m f i l t e r 问世后被广泛应用于数据库和分布式系统中， 这样b l o o m f i lt e r 不仅仅只维护在本地节点的内 存中，由于数据要在保持全局一致性，它还必须 在各个节点中传输。由于网络上花费的时间开销必不可少，这就可能使得网络 通信成为系统性能的 瓶颈。 为了 减少网络通信中 交换的 信息量， 2 0 0 1 年国外研 究者提出了一种能减少通信数 据量的压缩型b l o o m f