认识
一、认识
布隆过滤器（Bloom Filter） 是一种空间高效的概率数据结构，用可以快速判断某个元素是否在集合中。Redis 提供了 RedisBloom 模块，通过该模块可以在 Redis 中使用布隆过滤器来实现高效的集合成员判断。
布隆过滤器（Bloom Filter）特点: 1. 空间高效,节省内存: 相比于存储整个集合的数据，布隆过滤器只需要存储一段位数组，大大降低了内存占用; 2. 速度快, 高性能: 插入和查询操作都具有常数时间复杂度（O(1)）, 利用 Redis 的高并发性能，可以在内存中快速进行布隆过滤器的插入和查询操作。3. 概率误判, 布隆过滤器允许出现 假阳性（false positives），即可能会判断某个不存在的元素为存在，但不会出现 假阴性（false negatives），即判断一个存在的元素为不存在。另外, 布隆过滤器（Bloom Filter） 一旦设置好后不支持删除单个元素（计数布隆过滤器可以部分解决该问题，但复杂度会增加）。
布隆过滤器（Bloom Filter）原理: 布隆过滤器使用一个 位数组（Bit Array） 和多个哈希函数。当一个元素插入时，使用所有哈希函数计算该元素的多个哈希值，并将位数组中对应的位置设置为 1；查询时，使用相同的哈希函数计算哈希值，如果所有对应位置都是 1，则判断该元素可能存在，否则一定不存在。参数: m 个二进制向量, n 个预备数据, k 个 hash 函数。影响误差率的因素有两个: m/n比率 越大, 误差率可能越低; hash 函数个数, 函数越多, 误差率也会越低。
布隆过滤器（Bloom Filter）场景: 布隆过滤器适用于需要快速判断元素是否存在的场景，但对误判可以容忍的情况，如:
-
防止缓存穿透: 在访问数据库之前，通过布隆过滤器判断请求的数据是否存在。如果判断不存在，则直接返回，减少对数据库的压力。
-
网页爬虫去重: 判断一个
URL是否已经被爬取过。 -
恶意请求过滤: 在请求过滤层快速判断请求是否合法，避免恶意请求对后端造成冲击。
二、启动
通过 redis-server --loadmodule redisbloom.so 启动
三、问题
**#
3.1 垃圾邮件过滤
3.2 网络爬虫重复 URL 检测
3.3 假设有 50 亿电话号码, 现有 10 万个电话号码, 要快速准确判断这些电话号码是否已经存在, 如何实现?
思路: 通过数据库查询, 50 亿的数据量, 非常慢。如果将数据放在集合中, 50 亿 * 8 字节 = 40GB, 会造成内存浪费或者不够。