以太坊数据检索的基石 - 布隆过滤器

1. 布隆过滤器是什么

布隆过滤器简单来说就是一个固定长度的bit数组，初始化为0，配合多个hash函数可以解决url去重、缓存穿透、重复元素识别等功能。

2. 布隆过滤器的实现

1. 数据结构：

布隆过滤器的实现的数据结构非常简单，一个固定长度为5的bit的数组即可实现布隆过滤器，初始值全部为0。

2. 哈希函数：

布隆过滤器是使用hash函数来进行数据的插入和数据的查找的，通常情况下，会使用多个不同的哈希函数来降低hash碰撞的情况。 如下图所示，对于一个值为hello的数据，采用hash1和hash2两个独立的hash函数后取模获得这个元素在bit数组中的下标，即可将这个值存在布隆过滤器中。

3. 哈希碰撞：

在布隆过滤器中，有可能会出现hash碰撞的情况。在布隆过滤器中，使用多个不同的hash函数来降低hash碰撞的影响。 如图所示，对于不同的数据，使用hash函数后取模，有可能出现两者存在同一位置的情况。（值为redis和hello的两个不同元素经过hash运算后都存在了下标为2的位置）

4. 查找数据：

在布隆过滤器中，查找一个数据只需要对这个数据进行hash化，取出下标，观察其对应的bit数组位置的值，所有为1即这个数据可能存在，否则肯定不存在。 以值为hello的数据为例，经过hash运算后，在下标为2和下标为4的位置都为1，则这个数据可能存在。但只要有一个位置的值为0，则这个数据肯定不存在。

5. 假阳性：

以上述描述为例子，只有值全部为1才能判断这个数据可能存在。只要有一个bit为0则肯定不存在。因为其他数据经过hash后也有可能将这个数据所在bit数组的位置的值全部填充为1，不能肯定这个数据必然存在。但对于不存在的数据，只要有一个bit为0，则肯定不存在。

6. 假阳性的解决方案：

1. 增大bit数组的长度：数组增大能降低hash碰撞的概率。
2. 使用多个独立的hash函数：多个hash函数能确保一个值落入更多的bit位中，在进行存在判定时更严格（需要判定更多的位置为0）

3. 布隆过滤器的特点

• 空间节省：使用bit位来进行存储一个数据是否存在，十分节省空间。
• 查询速度快：只需要经过hash后取模即可获取到这个数据是否存在，非常迅速。
• 假阳性：查询的数据有误判的几率，可以通过提高bit长度、增加hash函数来缓解。

  4. 布隆过滤器的应用

  1. redis缓存穿透保护：

  可以过滤数据库中不存在key，让其不进入数据库请求中（允许少量进入，假阳性无影响）

  3. 以太坊中的日志过滤：

  以太坊中，每个区块头都包含一个logBloom字段，可以用来快速判断区块中是否可能包含某个event或者合约日志（如果不存在，则一定返回false，返回true，则可能存在，还会在其他地方进行判断。假阳性无影响）

  5. 区块链扫链任务中过滤系统相关的地址：

  在区块链扫链任务中，充值、提现、归集、热转冷、冷转热的业务都是与我们内部地址相关。可以使用布隆过滤器内部地址相关的交易过滤出来（可以允许少量非内部地址相关的交易进来，所以假阳性对此无影响）