Impala - Bloom Filter的实现及使用
Bloom Filter
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等数据结构都是这种思路。但是随着集合中元素的增加，需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n)、O(logn)、O(1)。
布隆过滤器的原理是，创建一个m位bit数组，先将所有位初始化为0，然后选择k个不同的哈希函数。当一个元素被加入bit位数为m的集合时，通过k个哈希函数将这个元素映射成一个位数组中的k个点，把它们置为1。检索时，只要检查这些点是否都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
（来源https://en.wikipedia.org/wiki/Bloom_filter）
上图是一个m=18,k=3的布隆过滤器，x,y,z代表存在过滤器中的元素，而w不在过滤器中。
优点
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。
布隆过滤器存储空间和插入/查询时间都是常数O(k)。
另外，哈希函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能。
选择不同的m和k, 将会有不同的误检率。可以看到k越大越准，m/n越大越准（bit数组越大且存储的数据越少）
（来源https://www.cnblogs.com/sunsky303/p/11834102.html）
缺点
布隆过滤器的缺点和优点一样明显。
首先是误检率。随着存入的元素数量增加，误检率随之增加。但是如果元素数量太少，则使用哈希表足矣。
另外，一般情况不能从布隆过滤器中删除元素。优化变种之一的Counting Bloom Filter在实现中维护的不是单纯的0或1的比特位，而是计数器counter，在插入一个元素时将相应的计数器加1, 这样删除元素时将计数器减掉就可以了。
在降低误算率方面有很多优化，也出现了很多布隆过滤器的变种：
Compressed Bloom Filter Deletable Bloom filter Hierarchical Bloom Filters Spectral Bloom Filters Bloomier Filters Decaying Bloom Filters Stable Bloom Filter Space Code Bloom Filter Filter Banks Scalable Bloom filters Split Bloom Filters Retouched Bloom filters Generalized Bloom Filters Distance-sensitive Bloom filters Data Popularity Conscious Bloom Filters Memory-optimized Bloom Filter Weighted Bloom filter Secure Bloom filters
Impala - Bloom Filter
Impala实现了一种Split Bloom Filter，其将哈希函数个数k减至最小为1，而将大小为m的位数组再次拆分，称之为bucket；每个bucket占用32bytes，包含8个bucket word。不同的数据元素仅可能映射到唯一的一个bucket。为了仅使用一个哈希函数产生多个映射点到bucket，Impala将采用二次hash方式，利用一组特殊的静态数字计算出不同8个映射点对应不同的bucket word，从而达到与使用k个哈希函数相同的效果
插入过程
1） 首先计算插入元素的hash值；（哈希采用MurmurHash算法，一种非加密型哈希函数，被Redis,Hbase，Cassandra等开源项目使用）
2） 根据该hash值计算出bucket index；（采用Dietzfelbinger's "Universal hashing and k-wise independent random variables via integer arithmetic without primes"来降低重复率；小概率重复并不影响）
3） 将第一步得到的hash值进行二次hash，得到8个仅有1位非0数字的32位序列，依次设置到临时bucket的8个word当中。
4） 将3）中的临时bucket合并到（或运算）主Filter当中，完成插入过程
检索过程
1） 同插入过程
2） 同插入过程
3） 同插入过程
4） 将临时bucket的每个word依次与主Filter进行与运算，任何一个word的与运算结果为0，即代表该元素不在数据集合中。
Impala - Runtime Filter
Runtime Filter是Impala 2.5及更高版本中可用的广泛优化功能。当针对分区表进行查询或评估join条件仅需要表中的一小部分数据时，Impala会在查询运行时确定适当的条件，并将该信息广播到所有正在读取该表的impalad节点从而避免不必要的I / O读取分区数据，并通过仅在网络上发送与联接键匹配的行的子集来避免不必要的网络传输。此功能主要用于优化针对大型分区表的查询和大表join。Impala主要只用两种Filter，除上述所说的Bloom Filter外，还有一个MinMax Filter，目前仅适用于Kudu表。Runtime Filter在运行时生成，广播到远端或者直接本地应用。
目前为止Parquet表对于runtime filter的获益最大，它可以加快Parquet分区或非分区表的join查询，以及Parquet分区表的单表查询。而对于其他文件格式（TEXT，Avro，RCFile和SequenceFile），runtime filter仅对分区表的查询有效。由于分区表可以使用多种格式，因此Impala在所有情况下都会生成过滤器，即使最终未将其用于优化查询。
下面是一个官方的样例:
CREATE TABLE yy (s STRING) PARTITIONED BY (year INT);
INSERT INTO yy PARTITION (year) VALUES ('1999', 1999), ('2000', 2000), ('2001', 2001), ('2010', 2010), ('2018', 2018);
COMPUTE STATS yy;
CREATE TABLE yy2 (s STRING, year INT);
INSERT INTO yy2 VALUES ('1999', 1999), ('2000', 2000), ('2001', 2001);
COMPUTE STATS yy2;
EXPLAIN SELECT s FROM yy WHERE year IN (SELECT year FROM yy2);
+--------------------------------------------------------------------------+
| PLAN-ROOT SINK |
| | |
| 04:EXCHANGE [UNPARTITIONED] |
| | |
| 02:HASH JOIN [LEFT SEMI JOIN, BROADCAST] |
| | hash predicates: year = year |
| | runtime filters: RF000 <- year |
| | |
| |--03:EXCHANGE [BROADCAST] |
| | | |
| | 01:SCAN HDFS [default.yy2] |
| | partitions=1/1 files=1 size=620B |
| | |
| 00:SCAN HDFS [default.yy] |
| partitions=5/5 files=5 size=1.71KB |
| runtime filters: RF000 -> year |
+--------------------------------------------------------------------------+
查询读取未知个数的分区，因为它的分区键值只有在运行时才知道。runtime filters行显示了用于查询片段02的优化信息，它可以跳过那些不需要的分区。它根据根据01产生的数据生成，发送给00片段应用。
参考链接：
https://impala.apache.org/docs/build/html/topics/impala_runtime_filtering.html
https://www.cnblogs.com/sunsky303/p/11834102.html
- 点赞
- 收藏
- 关注作者
评论（0）