【golang】海量数据去重-布隆过滤器

2023-03-05 10:23:01Python012

【golang】海量数据去重-布隆过滤器,第1张

在做域名爆破中，遇到了把一个300G的子域名json文件进行去重，一开始是考虑使用字典进行去重，但是数据量大了，会造成内存泄露。看网上资料介绍了一种方案，就是使用布隆过滤器。

布隆过滤器是一种数据结构，概率型数据结构，特定是高效插入和查询，可以用来告诉你“某一值一定不存在或者kennel存在”。

相比于传统的map、set等数据结构，占用空间更少，但其返回结果是概率型的，不确定。

布隆过滤器内部维护一个bitArray(位数组)，开始所有数据为0，当一个元素过来时，能过多个哈希函数（hash1、hash2、hash3）计算不同的hash值，并通过hash值找到bitArray的下标，将里面的值改为由0变为1。布隆过滤器有一个误判率，误判率越低，数组越长，所在空间越大，误判率越高，数组越小，所占空间越小。

这里贴上一个技术大牛的博客地址，里面对布隆过滤器用法以及在redis里面处理缓存穿透问题的详细介绍。

https://www.cnblogs.com/yscl/p/12003359.html

[TOC]

通过解决方案：

Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是 O(1) （可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。

使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap 占用的空间比较大：

为什么出现布隆过滤器：

举例：

如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后-->几次hash根据数据量指定，得到多个数据，占用多个位），则占用空间为610M。比原有空间少一半。

个人觉得，此比较在字符等的比较中尤为有效。

一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。

位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。

（1）定义字节向量

先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。

如长度为8（一个字节大小），默认所有元素值均为0，如下：

（2）计算哈希值

将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

（3）更新字节向量

将计算出的字节向量的索引，对应的字节向量中的元素值更高为1 （无论之前为0或者为1，均更改为1）。如下：

（1）计算哈希值

将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。

（2）判断是否存在

如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素可能存在，但凡有一个元素的值不为1，则判定此元素一定不存在。

布隆过滤器，主要需实现的目标是，在指定的数据个数范围内，满足误判率在设定的范围内，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。

因此需要计算两个数据来满足存储数据的个数和误判率：

使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候，需选择计算快的哈希算法。

而且，写入数据以及查询数据的哈希算法，顺序和算法都需完全一致。

待完善。。。。。

可以通过google的 guava ，在内存中轻松实现布隆过滤器。

无需手动计算满足字节数组的长度和哈希个数，只需要输入拟输入数据的个数和期望误判率即可。

不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定为存在。

多次执行，结果一致，根据结果判定：

内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。

使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。

实现过程，待完善。。。。。。

布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为，，。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装