10亿条URL的黑名单，如何快速判断一个新请求的URL是否在黑名单内？

在日常开发中你是否遇到过这样的场景有一个包含10亿条URL的黑名单如何快速判断一个新请求的URL是否在黑名单内同时避免占用几十GB的内存在我们学习缓存三剑客时关于缓存穿透我们常用的解决方案之一是什么这些问题的核心都是对海量数据的存在性判断我们不需要获取数据本身只需要知道“在”或“不在”而布隆过滤器Bloom Filter就能很好地解决这个问题。一、布隆过滤器是什么是一种空间高效的概率型数据结构核心作用是快速判断一个元素是否存在于一个集合中。布隆过滤器主要由两部分组成一部分是初始值都为 0 的位图数组一部分是N 个哈希函数。布隆过滤器不存储数据本身只存储数据的哈希标记。当我们往数据库中写数据时顺便在布隆过滤器中做个标记这样下次查数据时只要查布隆过滤器查的数据没有标记的话那说明数据库里也没有。那既然这么说了查布隆过滤器一定很快吧确实很快。查询布隆过滤器的时间复杂度O(k)k是哈希函数个数通常是个位数效率很高。二、布隆过滤器是怎么工作的布隆过滤器的底层结构很简单只有两个核心组件一个固定长度的位图数组(初始值都为0)一组独立的哈希函数所有逻辑都围绕这两个组件展开。接下来举个例子假设我有一个布隆过滤器数组初始长度为8哈希函数个数为3当我们插入元素“bloom”时步骤如下将“bloom”传入3个哈希函数得到3个不同的哈希值然后再把这 3 个哈希值对 8 取模将得到的结果在数组中的相应位置置1比如取模得到135 那就135位置1 总共0-7这样一通操作之后以后当我们要查询bloom是否在数据库中时只需要通过布隆过滤器查第135位置是否全为1必须全为1才可能行只要有一个0都说明“bloom”不在数据库中。那为什么是可能行呢因为不同的数经计算得到的哈希值对8取模结果可能是一样的可能存在哈希冲突。那这样明明数据库中没有这个数我却算出了它1,3,5位也是1这就判断错误了。三、使用布隆过滤器解决缓存穿透这里就回到了开头的缓存三剑客中的缓存穿透了。发生缓存穿透原因是因为用户请求一个不存在的数据此数据在缓存和数据库中都不存在。这是我们可以用布隆过滤器存储所有已存在的key请求过来时先查布隆过滤器如果返回“绝对不存在”那就直接返回空结果不访问缓存和数据库。如果返回“可能存在”再查缓存和数据库。这样就能拦截99%以上的无效请求保护数据库。四、布隆过滤器的其它应用1. 海量数据去重比如爬虫去重爬取网页时需要记录已爬取的URL避免重复抓取。如果用哈希表存储1亿条URL会占用几十GB内存而用布隆过滤器仅需几十MB内存就能搞定完美解决空间瓶颈。类似场景还有邮件黑名单去重、用户ID去重、日志去重等。2. 数据库索引优化HBase、LevelDB、RocksDB等数据库引擎会用布隆过滤器判断目标键是否存在于某个SSTable文件中避免不必要的磁盘IO操作提升查询性能——如果布隆过滤器判断键不存在就无需读取磁盘文件直接返回空结果。3. 分布式系统中的数据校验比如分布式缓存中判断一个key是否在其他节点的缓存中区块链轻节点中判断某个交易是否可能包含在区块中减少数据同步的开销。五、总结布隆过滤器的本质是“用极小的空间成本换取极高的查询效率同时接受轻微的误判”。它不适合所有场景但在海量数据的存在性判断中是无可替代的工具。如果觉得这篇博客对你有帮助欢迎点赞~收藏~评论~