今天,我们就来学习下布隆过滤器的原理以及作用。

代码已经上传到github

https://github.com/HobbyBear/codelearning/tree/master/bloomfilter

作用

通常我们在缓存层前面会添加一层布隆过滤器,它能够迅速的判断那些一定不在缓存中的数据,防止缓存击穿。

布隆过滤器返回false的数据一定不在缓存里,返回true的数据也可能不在缓存里。即使不能百分百判断数据是否一定存在于缓存中,它依然能够过滤大量的无效不在缓存中的数据,所以被广泛使用。

原理

为啥不能百分百的判断数据是否一定存在,这就需要来了解下布隆过滤器的原理。在构建布隆过滤器时,会创建一个bitmap,关于bitmap的讲解可以查看我之前的文章位图(bitmap)原理以及实现 ,使用布隆过滤器的步骤如下:

1,比如一个场景,我们添加缓存时,需要先将key添加到布隆过滤器中,需要将key用多个hash函数经过多次hash,比如三次,得到3个数字a,b,c 。

2, 然后将a,b,c 对应在bitmap中的bit位设置1。

3,当要从缓存中读取数据时,也是先从布隆过滤器中读取,此时需要将要读取的缓存key也经过多个hash函数多次hash,判断hash得到的数字对应在bitmap中的bit位是否都是1,如果有一个不为1,说明这个缓存key肯定没有添加过缓存,就不用再去请求缓存服务器了。

这里要注意的是,因为是hash函数,所以有可能key1和key2最后hash的结果是一样的,这样布隆过滤器只添加key1时,还是会在读取key2时返回true,这样还是会去读缓存服务器,即使key2并不在缓存服务器中。

并且由于在bitmap中存储的是hash后的结果,所以布隆过滤器也不能删除数据,一个好的使用方式是定时重建布隆过滤器,让旧布隆过滤器过期。

实现

接着,我们来看下布隆过滤器的实现,我仿照java的Guava中的布隆过滤器实现写了一个golang的版本, hash函数用的murmur3 得到两个hash值,通过迭代k次hash值的效果代替了运行k次hash函数,然后将得到的结果设置到bitmap中。

需要注意的是hash.Sum128 返回的uint64,这个类型在转换成int64类型时可能会产生负数,所以我们需要将它同math.MaxInt64得到正数,然后与bitmap的大小进行取模,这样得到的数字永远是一个正数且不会超过bitmap的长度。

func (b *BloomFilter) Add(key string) {  
   bitSetSize := b.m  
   hashFunCount := b.k  
   hash := murmur3.New128()  
   hash.Write([]byte(key))  
   hash1, hash2 := hash.Sum128()  
   combinedHash := hash1  
   for i := 0; i < hashFunCount; i++ {  
      b.bitset.Set((uint64ToInt64(combinedHash) & math.MaxInt64) % bitSetSize)  
      combinedHash += hash2  
   }  
}  
  
func (b *BloomFilter) MightContain(key string) bool {  
   bitSetSize := b.m  
   hashFunCount := b.k  
   hash := murmur3.New128()  
   hash.Write([]byte(key))  
   hash1, hash2 := hash.Sum128()  
   combinedHash := hash1  
   for i := 0; i < hashFunCount; i++ {  
      if !b.bitset.Exits((uint64ToInt64(combinedHash) & math.MaxInt64) % bitSetSize) {  
         return false  
      }  
      combinedHash += hash2  
   }  
   return true  
}  
  
func uint64ToInt64(num uint64) int64 {  
   if num <= uint64(math.MaxInt64) {  
      return int64(num)  
   }  
   return int64(num - uint64(math.MaxInt64) + 1)  
}
09-20 10:26