浅谈布隆过滤器和HyperLogLog
文章目录
-
-
1. BitMap和BitSet
-
- BitMap算法
- BitSet
-
2. 布隆过滤器
-
- 五星面试题：缓存穿透
-
3. HyperLogLog (主要用于统计)
-
- 3.1 问题
- 3.2 一个重要的区别就是：
-
基数统计算法
基数被定义为集合中去除重复元素后的元素数量，并因此也被称为 基数统计算法 或 去重统计算法。
要说标题中的两个算法，需要先来区分下 BitMap算法和 BitSet算法
1. BitMap和BitSet
BitMap算法
一切的基础: BitMap算法
《编程珠玑》一书中提到：
即为一种通过单个比特位标识对应值的数据结构，在其中Key即为此元素。
由于基于Bit作为最小单位进行数据存储的方式存在，
从而节省了存储空间。
bitmap算法正是通过这一原理实现了对海量数据进行高效排序、检索与重复数据去除等功能。
一图胜千言
稍微解释一下：
上图所示，在存储32个数值时仅需占用32 bits（即4-byte的空间）。具体操作包括先开辟一个4-byte的空间，并将该空间中的所有bit位初始化为0状态。
随后，在BitMap集合中依次添加三个数值：10、17和28。这一操作等同于在各自对应的bit位位置上设置相应的bit值为1。
改写说明
小节： BitMap 的思想和原理是很多算法的基础。 核心点如下：
- 建立位图与整数的对应关系。
- 当数据规模扩大时，则可通过不断扩展 Bit Array 来实现。
- 进行排序、去除重复项以及查找操作能够有效提升效率，并且占用更少的空间资源。
大厂面试题：[容量为10GB的数据文件中仅包含自然数字，并按随机顺序排列等待排序操作。要求在32位操作系统环境下完成排序任务时的内存占用限制不超过2GB。(来自链接)]
BitSet
该数据结构采用bitmap技术，在该结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，在该数据结构中采用bitmap技术，
BitSet 算法利用了 BitMap 技术手段作为其基础架构，并被用来处理 BitMap 中的整数；其核心是可以替代任意的数据格式，并通过哈希算法对数据进行映射至位图中；
利用哈希函数计算之后可以直接到达相应的位置去查找是否存在的情况。
观察红色线条上的数值24和147，在经过哈希函数处理后发现它们对应的哈希值相同的情况被称为哈希冲突或称作哈希碰撞。
哈希冲突不可避免，在这种情况下我们能做的就是尽量降低其发生概率。一种方法是增加维数组的长度或位图容量；由于我们的哈希函数具有良好的分布特性，在同一位置发生冲突的可能性就会降低。然而随着位图容量增大内存消耗也会随之增加；因此我们需要寻找其他解决方案。第二种方法是多次运行多个不同的哈希函数计算；例如24与147在一次计算中发生了冲突；但如果经过5次、10次甚至100次不同的计算后仍然会发生碰撞那这确实是一种巧合；你们可以在一起了；但这并不是使用越多哈希函数越好因为这样一来位图很快就会被填满而且每次都需要耗费大量时间进行计算；因此我们需要在时间和空间资源之间找到一个合理的平衡点
2. 布隆过滤器
每当一个新元素加入集合时，
通过K个哈希函数将该元素映射到位数组中的K个位置，
并将这些位置标记为1。
检索过程只需查看这些标记的位置是否全为1来判断该元素是否存在；
若发现任何一个位置为0，
则可以确定该元不在集合中；
若全部标记为1，
则该元很可能是存在的（这是因为可能存在误判的可能性）。
举例如下：
当bitmask长度较短而数据量却很大时，
有可能导致错误地判定该元属于集合。
布隆过滤器就是基于位图实现的，在此基础上，就找到一个平衡。
此事件早被诸多学者探究过。于上世纪七十年代初，计算机科学家布隆先生便对如何高效判断海量数据集是否存在这一技术难题展开了深入研究。他通过设计一系列哈希函数，在此基础上提出了具有里程碑意义的研究成果，并因此成为该领域的重要先驱之一。而这一创新性数据结构被命名为布隆过滤器
观察上面所示的图
同理我们可以观察一下这个变量d的情况：经过三次计算后所得的结果均为1。那么我们是否可以说在布隆过滤器中存在这样的变量d呢？显然不能
结论，从容器的角度来说：
- 从元素的角度来看：
- 若该集合中确实包含某个特定的元素，则布隆过滤器必然能检测到它。
- 若该集合中原本并未包含某个特定的元素，则其被误判的可能性是存在的。
- 若布隆过滤器判定某元素不在集合中，则该元素确实不在其中。
- 若该系统能够识别出某特定的实体，则它必然会被检测出来。
应用场景：
- 缓存穿透
- 网页爬虫通过消除重复的URL地址来避免爬取相同的地址；
- 反垃圾邮件系统能够识别并排除来自已标记为垃圾的邮箱列表中的新邮箱；
- Google Chrome应用布隆过滤器来识别恶意链接；
- Medium借助布隆过滤器来筛选出未曾阅读过的文章内容；
- 这些技术框架利用布隆过滤器来减少对非存在的行和列进行查找的需求。
五星面试题：缓存穿透
问：缓存穿透是什么意思？
答：缓存穿透是指恶意攻击者通过不断尝试使用不存在的键（key）发起请求至缓存层（cache layer），当Redis（一个常用的一致性缓存层）返回无结果后才向MySQL数据库发送请求的过程。
这种行为可能导致MySQL服务器承受额外负载并引发性能下降甚至服务瘫痪。
通过这种机制攻击者能够绕过正常的缓存机制保护措施。
提问者提出的问题是什么？
在Redis及MySQL均不存在的情况下，请将current key存入Redis并将其value设置为空。
问：如果存在大量恶意请求且其key值不同怎么办？
答：这时就需要布隆过滤器发挥作用了，在MySQL中获取的所有数据都会被记录到布隆过滤器中。如果布隆过滤器中没有对应的记录，则表示该数据不存在。
附：你知道什么是缓存雪崩吗？ 怎么解决？
3. HyperLogLog (主要用于统计)
3.1 问题
在实际开发中会遇到一个问题：当需要统计大型网站的独立访问次数时应采用哪种类型的统计方法？
如果我们依赖Redis集合结构来管理统计数据，在面对每天承受着数千万级别的访问量时，则会必然导致空间占用问题。由于这些数据无法被清除，在时间积累下去后最终会导致内存空间溢出。
例如，在判断独立访问时，我们采用 IP 作为依据，并对每个独立的 IP 进行存储。在计算时，则是以 IP4 的形式进行处理。每个 IP4 占据约 15 个字节的空间用于信息存储。这样的一千万个 IP 将占用约 15 bits × 10,000,000 = 约为 143 MB 的空间。然而当数量达到一万个这样的页面时，则需要超过一 terabyte（T）的空间来完成数据存储工作。随着 IPv6 的普及推广，所需的数据量将显著增加，在面对这一挑战时，则需要开发新的数据类型来解决这一问题。HyperLogLog 是我们今天介绍的核心技术。
HyperLogLog（简称HLL）在Redis 2.8.9版本中新增作为一种数据结构，在该版本中新增作为一种数据结构
HLL 具有以下几个特点：
仅需微小内存空间即可处理大量数据，在处理能力上具有显著优势；该方法在处理能力上具有显著优势，在处理能力上表现优异；通过设定辅助计算因子来减少其标准误差的影响。
HLL 的命令只有 3 个，但都非常的实用，下面分别来看。
添加元素
pfadd key element1 element2······，可以同时添加多个。
0.0.1:6379> pfadd hll1 mea
(integer) 1
127.0.0.1:6379> pfadd hll1 kano nana
(integer) 1
127.0.0.1:6379> pfadd hll1 mea
(integer) 0
127.0.0.1:6379>
代码解读统计不重复的元素个数
pfcount key1 key2····，可以同时统计多个HHL结构。
0.0.1:6379> pfcount hll1
(integer) 3 # 不重复元素个数有3个
127.0.0.1:6379>
代码解读将多个HLL结构中元素移动到新的HLL结构中
pfmerge key key1 key2····，将key1、key2····移动到key中。
0.0.1:6379> pfadd hll1 mea kano nana
(integer) 1
127.0.0.1:6379> pfadd hll2 mea kano yume
(integer) 1
127.0.0.1:6379> pfmerge hll hll1 hll2
OK
127.0.0.1:6379> pfcount hll
(integer) 4
127.0.0.1:6379>
代码解读当我们在进行跨站脚本检测时需要确保所有来源IP位于同一个地理位置区域内以减少误报风险
在处理大规模数据统计任务时，在普通集合类型已无法满足需求的情况下
3.2 一个重要的区别就是：
- 布隆过滤器主要用于识别或判定某个数据是否存在
- HyperLogLog用于执行统计计算且无法唯一识别特定元素