布隆过滤器

更好的是布鸟过滤器，找时间去了解一下

原理

布隆过滤器是一种高效的概率型数据结构，用于快速判断某个元素是否存在于集合中。它通过多个哈希函数将数据映射到一个位数组中。当接收到请求时，可以通过布隆过滤器判断该请求是否已经处理过。

布隆过滤器的核心可以理解为一个一维的二进制向量，每一位可以是 0 或 1。这个数组的所有位都被初始化为 0。布隆过滤器的关键点在于使用多个独立的哈希函数，是独立散列的。对于每个需要插入的元素，布隆过滤器会使用多个不同的哈希函数来处理。多个哈希函数生成多个随机索引，将这些索引位置的位标记为 1。

误判：误判根源：不同元素在经过多个哈希函数后，可能会映射到相同的位数组位置。（部分哈希值产生了重叠）这就是哈希碰撞的根源。误判形式：只会将不存在的元素误判为存在，而不会将存在的误判为不存在误判概率：误判率随着元素数量的增加、位数组大小的减少以及哈希函数数量的选择变化而变化guava的默认误判概率为0.03，可以在初始化的时候修改\

特点

优点：空间、时间效率高：判断元素是否存在于集合中非常高效，时间复杂度接近 O(1)。缺点

误判率：哈希碰撞导致的误判无法避免，当接近容量上限时，误判率会增加。
不可删除元素：布隆过滤器只能添加元素，删除会导致误判率增加。
不支持范围查询：布隆过滤器只支持单点查找，不适合范围查询操作。
无法保存原始数据：它仅存储哈希后的结果，无法恢复原始数据，因此在一些场景下并不适用。

使用场景

去重场景也需要用到判断给定数据是否存在，因此布隆过滤器主要是为了解决海量数据的存在性问题

防缓存穿透：用于判断请求的数据是否有效，避免直接绕过缓存请求数据库。
黑名单过滤：用于快速判断某个 IP 或手机号是否在黑名单中。
去重处理：如爬虫对已爬取的 URL 去重、订单号去重、邮箱垃圾邮件过滤，避免推荐给用户已经读过的文章等。
大规模请求幂等检查：用于快速判断重复请求，尤其在接收大量请求时。
空间受限场景：布隆过滤器在内存资源受限时具有优势。
容错性要求不高：适用于对误判容忍度较高的场景，如数据同步或日志处理。

XXL-Job + Redis + RocketMQ + Elasticsearch + 布隆过滤器的自定义ES与MySQL数据同步

配合\

问题

为什么不用哈希表用布隆过滤器，比分布式锁快的点在哪？别的解决方案
1. 哈希表可以精确判断元素是否存在，但其空间复杂度较高。而且当系统分布式扩展时，哈希表的同步和锁机制会引入额外的开销。
2. 比分布式锁快在：大量请求的情况下，布隆过滤器查询速度还是接近O(1)，减少锁竞争。\
布隆过滤器如何计算？
1. 插入元素，哈希函数计算位数组对应的索引
2. 查询元素，哈希函数计算映射的位是否都为1
\
布隆过滤器应该设置多大
1. 布隆过滤器的大小是通过以下几个参数决定的，需要平衡：
2. 预计存储的数据量（n）：即需要过滤器容纳的元素个数。
3. 允许的误判率（p）：误判率越低，布隆过滤器的大小越大。
4. 哈希函数的数量（k）：一般通过优化公式推导出，使得误判率最小
扩容相关

布隆过滤器本身不能扩容，但可以通过添加多个布隆过滤器（分片扩展）来间接实现扩容\

缓存穿透相关问题
1. 缓存如何实现？为什么在布隆过滤器后面还需要一层缓存呢？（我答布隆过滤器数据无法删除，如果用户取消注册或者注册失败，用户名就无法再注册）
  1. 误判：布隆过滤器只能告诉你某个请求“可能”已经处理过，因此需要通过缓存层进一步确认结果。比如，如果布隆过滤器判断某请求“可能存在”，可以进一步查询缓存，确认该请求是否确实已处理。
  2. 数据一致性：由于布隆过滤器不能删除元素，如果用户的某些状态发生变化（如取消注册、数据被撤销），缓存层可以提供一个可更新和删除的缓存机制，从而解决这个问题。\
2. 那你的布隆过滤器如何解决缓存穿透？
  1. 缓存穿透：用户反复请求既不在缓存中也不在数据库中的数据
  2. 防止不存在的数据直接查询数据库：布隆过滤器可以存储所有合法的数据（如合法的用户ID、商品ID等），当用户请求的数据不在布隆过滤器中时，直接返回不存在，不用去访问缓存和数据库。
  3. 提高查询效率：由于布隆过滤器的查询速度极快，可以在缓存前作为第一道过滤器，避免对不存在的数据进行频繁查询。
布隆过滤器和布谷鸟过滤器的区别
1. 布谷鸟算得上是布隆过滤器的升级版支持了删除操作以及说在空间上更加压缩

上一页OpenSSL 学习笔记及项目应用下一页优化

最后更新于10天前