当前位置：首页 > news >正文

DORIS - DORIS之BloomFilter索引

news 2024/9/24 3:27:45

HASH函数

了解布隆过滤器原理之前，先回顾下HASH函数。
哈希函数，就是将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值，如下图：
在这里插入图片描述
所有散列函数都有如下基本特性：
A. 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。
B. 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。

无偏HASH函数

无偏HASH函数，就是能把元素的HASH值计算的比较均匀的HASH函数。

布隆过滤器

Bloom Filter（布隆过滤器）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否可能属于这个集合，是由 Bloom 在 1970 年提出的一种多哈希函数映射的快速查找算法。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难，初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。
在这里插入图片描述

误判率

布隆过滤器的误判是指多个输入经过哈希之后在相同的位置成了1，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的位被多次映射且置成了 1。这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个位并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

应用场景

通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求 100% 正确的场合，BloomFilter是由一个超长的二进制位数组和一系列的哈希函数组成（二进制向量+随机映射函数）。二进制位数组初始全部为 0，当给定一个待查询的元素时，这个元素会被一系列哈希函数计算映射出一系列的值，所有的值在位数组的偏移量处置为 1。适合如网页URL去重，垃圾邮件判别，集合重复元素判别，查询加速（比如基于key-value的存储系统）、数据库防止查询击穿，使用布隆过滤器来减少不存在的行或列的磁盘查找。
※ 数据库防止穿库：Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
※ 缓存宕机、缓存击穿场景：一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询DB。如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到DB，如果不在布隆器中，则直接返回。
※ WEB拦截器：如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中，可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

基本思想

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定，链表，树，哈希表（他们三个的检索时间复杂度分别为O(n),O(logn),O(1)）等等数据结构都是这种思路，但是随着集合中元素的增加，我们需要的存储空间越来越大，同时检索速度也越来越慢。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，并把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了，如果这些点有任何一个0，则被检元素一定不存在；如果都是1，则被检元素很可能存在，这就是布隆过滤器的基本思想。为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

本质

布隆过滤器的本质，就是判断具体数据存不存在一个大的集合中。
遵循：有，可能有；无，一定无的原则。

特性

※ 高效的插入和查询，占用空间少，返回的结果是不确定性的。
※ 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。
※ 布隆过滤器可以添加元素，但是不能删除元素，因为删掉元素会导致误判率增加。
※ 误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。

优点

空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素。

DORIS的BloomFilter

目的：DORIS利用 BloomFilter 跳过等值查询指定条件不满足的数据块，达到减少 I/O 查询加速的目的。

Doris BloomFilter 索引以数据块（page）为单位构建，每个数据块存储一个 BloomFilter。
写入时，对于数据块中的每个值，经过 Hash 存入数据块对应的 BloomFilter；查询时，根据等值条件的值，判断每个数据块对应的 BloomFilter 是否包含这个值，不包含则跳过对应的数据块不读取，达到减少 I/O 查询加速的目的。
Doris中的前缀索引、Bloom Filter属于稀疏索引.，以MYSQL为例，主键索引是稠密索引; 非主键索引(非聚簇索引)是稀疏索引。
（1）BloomFilter 索引能够对等值查询（包括 = 和 IN）加速，对高基数字段效果较好，比如 USER-ID等唯一ID字段。对低基数字段的加速效果很有限，比如“性别”字段仅有两种值，几乎每个数据块都会包含所有取值，导致 BloomFilter 索引失去意义。
（2）对 IN 和 = 之外的查询没有效果，比如 !=, NOT INT, >, < 等。
（3）不支持对 Tinyint、Float、Double 类型的列建 BloomFilter 索引。