全球消息！解释一下布隆过滤器原理

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

全球消息！解释一下布隆过滤器原理

2023-04-10 22:00:10 来源：博客园

锁屏面试题百日百刷，每个工作日坚持更新面试题。请看到最后就能获取你想要的,接下来的是今日的面试题：

1.解释一下布隆过滤器原理

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹googlechinablog.com/2006/08/blog-post.html，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。

(资料图)

一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。

而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中， k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。

· 为了add一个元素，用k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。

· 为了query一个元素，即判断它是否在集合中，用k个hash function将它hash得到k个bit位。若这k bits全为1，则此元素在集合中；若其中任一位不为1，则此元素比不在集合中（因为如果在，则在add时已经把对应的k个bits位置为1）。

· 不允许remove元素，因为那样的话会把相应的k个bits位置为0，而其中很有可能有其他元素对应的位。因此remove会引入false negative，这是绝对不被允许的。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处，也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小，我们把它称为误识概率。

布隆过滤器的好处在于快速，省空间，但是有一定的误识别率，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

2.如何实现HBase的二级索引?

方案一: 通常情况下,较原生方式,我们可以采用ES或者Solr来实现hbase的二级索引的操作, 当用户要写入数据时候, 基于hbase的observer协处理器拦截下来, 使用es或者Solr来构建hbase的索引数据, 这样当查询hbase中数据时候, 可以先去ES中查询到对应的数据, 然后根据结果, 在从hbase中获取最终的完整的结果

方案二: 基于Phoenix实现, Phoenix是一款基于hbase的SQL客户端, 可以使用SQL的方式来操作hbase, 同时为了提升整体的查询性能, Phoenix中提供了各种索引(全局索引, 本地索引, 覆盖索引以及函数索引), 这些索引都是基于Hbase的协处理器(主要是ObServer协处理器)而实现的, 二基于索引的查询方案, 也是Phoenix实现hbase二级索引的方式

3.Hbase的storeFile(compact)合并机制是什么?

compact合并机制:

指的memStore中不断进行flush刷新操作, 就会产生多个storeFile的文件, 当storeFile的文

件达到一定阈值后, 就会触发compact的合并机制, 将多个storeFile合并为一个大的HFile文件

阈值: 达到3个及以上

整个合并过程分为两大阶段:

minor :

作用: 将多个小的storeFile合并为一个较大的Hfile操作

阈值: 达到3个及以上

注意: 此合并过程, 仅仅将多个合并为一个, 对数据进行排序操作, 如果此时数据有过期, 或者有标记为删除数据, 此时不做任何的处理 (类似于内存合并中基础型)

所以说, 此合并操作, 效率比较高

major:

作用: 将较大的HFile 和之前的大的Hfile进行合并形成一个更大的Hfile文件 (全局合并)

阈值: 默认 7天

注意: 此合并过程, 会将那些过期的数据, 或者已经标记删除的数据, 在这次合并中, 全部

都清除掉，由于这是一种全局合并操作, 对性能影响比较大, 在实际生产中, 建议关闭掉自动合并, 采用手动触发的方案

4.Hbase的flush刷新机制?

flush刷新机制(溢写合并机制):

流程: 客户端不断将数据写入到memStore内存中, 当内存中数据达到一定阈值后, 需要

将数据溢写刷新的HDFS中形成一个storeFile文件

阈值: 128M 或者 1小时满足了那个都会触发flush机制

内部详细流程: hbase 2.0架构以上流程

客户端不断向memStore中写入数据, 当memStore只数据达到阈值后, 就会启动flush操作
首先hbase会先关闭掉当前这个已经达到阈值的内存空间, 然后开启一个新的memStore的空间,用于继续写入工作
将这个达到阈值的内存空间数据放入到内存队列中, 此队列的特性是只读, 在hbase 2.0架构中, 可以设置此队列的数据尽可能晚的刷新到HDFS中, 当这个队列中数据达到某个阈值后(内存不足), 这个时候触发flush刷新操作 (队列中可能存储了多个memStore的数据)
flush线程会将队列中所有的数据全部读取出来, 然后对数据进行排序合并操作, 将合并后数据存储到HDFS中, 形成一个storeFile的文件

注意: 在 hbase2.0以下的架构中, 不存在推迟刷新功能, 同样也不存在合并数据的

操作当memStore数据达到阈值后, 放入到队列中, 专门有一个flush刷新监控队列, 一旦有数据直接刷新到HDFS上

注意说明:

hbase 2.0 只是提供了基于内存的合并功能, 但是默认情况下不开启的, 所以在默认情况

下整个flush机制基本和2.0以下的版本是一致的, 但是一旦开启了, 就是刚刚描述流程

合并方案: 三种基础型(basic): 直接将多个memStore数据合并在一起直接刷新到HDFS上,如果数据存在过期的数据, 或者是已经标记为删除的数据, 基础型不做任何处理

饥渴型(eager): 在将多个memStore合并的过程中, 积极判断数据是否存在过期, 或者是否已经标记删除, 如果有, 直接过滤掉这些标记删除和过期的数据即可

适应性(adaptive): 检查数据是否有过期数据, 如果过期数据量达到一定阈值后, 就会自动使

用饥渴型, 否则就使用基础型

5.如何解决hbase中数据热点问题?

所谓数据热点, 指的是大量的数据写到hbase的某一个或者某几个region中, 导致其余的region没有数据, 其他region对应regionServer的节点承受了大量的并发请求, 此时就出现了热点问题

解决方案: 通过预分区和设计良好的rowkey来解决

1)加盐处理(加随机数) : 可以在rowkey前面动态添加一些随机数, 从而保证数据可以均匀落在不同region中

n 基本保证数据落在不同region

n 将相关性比较强的数据分散在不同的额region中, 导致查询的效率有一定降低

2)hash处理: 根据rowkey计算其hash值, 在rowkey前面hash计算值即可 (MD5 HASH)

n 让相关性比较强的数据可以被放置到同一个region中

n 如果相关数据比较多, 依然会导致热点问题

3)反转策略: 比如说手机号反转或者时间戳的反转

n 好处: 基本保证数据落在不同region

n 弊端: 将相关性比较强的数据分散在不同的region中, 导致查询的效率有一定降低

全部内容在git上,了解更多请点我头像或到我的主页去获得，谢谢

关键词：