布隆过滤器应用场景和简单原理

场景

一般在流量较大的情况下，我们使用了缓存(redis、memcache...)来避免请求直接打到关系型数据库上（mysql、oracle...),此时可能发生的情况是，被人恶意请求了未缓存的数据（数据可能存在，也可能不存在），这时候就会有大量的请求直接
打到mysql、orcle 上，拖垮我们的服务，这种情况我们称为缓存穿透。为了防止这种情况出现，一种简单暴力的方法是，缓存不存在直接返回null，但是这种处理容易误伤，我们也不可能将所有的数据都缓存到nosql中，内存多贵呀。另一种方法就是使用布隆过滤器。

原理

一个简单的应用场景，布隆过滤器其实是将URL（这里特指请求）与MySQL（这里代指关系型数据库）进行隔离，我们提前将已缓存的，已存在的value对应的URL存入布隆过滤器，下次请求进来，直接在布隆过滤器中查找请求的URL是否存在，存在则允许请求，不存在直接禁止访问即可。这样就避免了MySQL被拖垮。

实际上，布隆过滤器的核心是hash+bitArray,即对存入的值进行多次hash，hash得到的值是bitArray的index,hash(key)->index,得到index后将bitArray对应的index位置为1，即

bitArray[index] = 1

因为要进行多次hash，所以可能会在多个index上置1.这样一来在布隆过滤器中确定要查找的URL是否存在只需对URL进行hash 然后得到index,判断bitArray[index]是否为1即可。应为要判断多次hash,所以假设布隆过滤器重的hash韩式一共有H个，那么整个查找的过程的时间复杂度就是O(H)，
显而易见，对比使用redis的sort等等其他数据结构，高下立现，更关键的是我们不用保存具体的URL，只需记录对应index位的值为0或1即可，太省空间了吧。

bitArray = [0,1,0,1]//初始化之后的bitArray

url = "baidu.com/huaidan"
if bitArray[hash1(url)] == 1 && bitArray[hash1(url)] == 1 {
    printf("url 可能在布隆过滤器中")
}

if bitArray[hash1(url)] == 0 || bitArray[hash1(url)] == 0 {
    printf("url 一定不在布隆过滤器中")
}

优势

不需要存储数据本身，只用比特表示，因此空间占用相对于传统方式有巨大的优势，并且能够保密数据；
时间效率也较高，插入和查询的时间复杂度均为O(k)；
哈希函数之间相互独立，可以在硬件指令层面并行计算

• 不用存储数据本身
• 时间复杂度简单为O(H) H为hash函数的数量
• 节省空间，极端情况1bit就能判断8个URL

劣势

• 存在hash 碰撞，不能保证百分百存在
• 只能查询和插入，不能删除

注意事项

• URL不存在布隆过滤器中是百分百确定的，但是存在这一状态不能百分百保证，因为可能存在hash碰撞，导致位冲突，即不同的URL hash之后的index可能是相同的。
• redis hash插件使用方法 link