布隆过滤器揭秘:让URL黑名单存储从640GB缩小到35.88GB!

软件求生 2024-08-07 10:07:35



大家好,我是小米,一个热爱分享技术的小伙伴。今天我们来聊一聊在实际工作中如何使用布隆过滤器(Bloom Filter)来处理大规模URL黑名单的存储和查询问题。

问题背景

假设我们有一个规模达到100亿的黑名单URL集合,每个URL的长度为64字节。如何高效地存储和查询这个黑名单呢?

散列表方法

我们先考虑一下常规的散列表方法。如果使用HashMap来存储这些URL:

每个URL 64字节

100亿个URL需要存储:100亿 * 64B = 640GB

显然,这样的存储需求是不可行的,因为它对内存的要求太高。

布隆过滤器介绍

这时候,我们可以引入布隆过滤器,它是一种高效的概率型数据结构,用于检测一个元素是否属于一个集合。布隆过滤器具有以下特点:

占用空间小

查询速度快

允许一定的误判(即可能认为不存在的元素存在,但不会把存在的元素认为不存在)

布隆过滤器原理

布隆过滤器由一个很长的二进制位数组和一系列随机映射函数(哈希函数)组成。

位数组:每个元素占用1 bit,初始时所有位都设为0。

哈希函数:假设有K个哈希函数,每个函数将输入元素映射为位数组的一个下标。

插入元素

当一个元素加入布隆过滤器时,执行以下步骤:

使用K个哈希函数对元素进行哈希计算,得到K个哈希值。

将位数组中对应哈希值位置的bit设为1。

查询元素

查询一个元素是否在布隆过滤器中时,执行以下步骤:

使用K个哈希函数对查询元素进行哈希计算,得到K个哈希值。

检查位数组中对应哈希值位置的bit是否都为1。如果都为1,则认为该元素存在;如果有一个为0,则认为该元素不存在。

计算布隆过滤器参数

为了更好地理解布隆过滤器的存储效率,我们需要计算以下参数:

位数组长度(m):我们需要选择一个合适的位数组长度来保证较低的误判率。

哈希函数数量(K):哈希函数的数量也需要根据集合大小和位数组长度来确定。

假设我们允许的误判率为0.01%,我们可以使用以下公式来计算m和K:

其中,n是集合中的元素数量,p是允许的误判率。

具体计算如下:

代入公式:

通过计算,我们得出位数组的长度为287亿bit(约合35.88GB),需要20个哈希函数。这样,布隆过滤器的内存占用从原来的640GB大幅减少到了35.88GB,且具有较高的查询效率。

布隆过滤器的实现

下面是布隆过滤器的Java实现,包括初始化、添加元素和查询元素的代码。

代码说明

BitSet:用于存储位数组。

MessageDigest:用于生成哈希值。

add:将一个URL添加到布隆过滤器中。

check:检查一个URL是否存在于布隆过滤器中。

getHash:生成哈希值,并结合种子(seed)确保多个哈希函数的实现。

intToBytes:将整数转换为字节数组,用于哈希函数的种子。

这个实现使用了MD5哈希函数,可以根据需求选择其他哈希函数。通过调整位数组大小和哈希函数数量,可以在存储效率和误判率之间取得平衡。

END

布隆过滤器作为一种高效的概率型数据结构,能够在大规模数据集上实现高效的存储和查询,特别适用于URL黑名单这样的场景。通过合理地选择位数组长度和哈希函数数量,我们可以在保证较低误判率的前提下,大幅减少内存使用。

希望今天的分享能帮助大家更好地理解和应用布隆过滤器。如果大家有任何问题或需要进一步探讨,欢迎在评论区留言。我们下次再见!

1 阅读:31

软件求生

简介:从事软件开发,分享“技术”、“运营”、“产品”等。