Golang布隆过滤器实现

布隆过滤器一般用来过滤黑名单。布隆过滤器的原理不算复杂。对数据进行查找，简单点的可以直接遍历；对于排好顺序的数据，可以使用二分查找等。但这些方法的时间复杂度都较高，分别是O(n)和O(logn)。无法对大量乱序的数据进行快速的查找。哈希，将给定的数据通过哈希函数得到一个唯一的值，此值可以作为数据的唯一标识，只要通过该标识，再通过哈希函数逆向计算，就能还原出来原始的数据。在前面的网址压缩的调研分析里面介绍的压缩网址的方法，其实也就是一种哈希，只不过借助了数据库的支持。布隆过滤器就是借助了哈希实现的过滤算法。通过将黑名单的数据哈希之后，可以得到一个数据。申请一个数组空间，长度是黑名单的长度。将前面的数据转换成数组中唯一的一个单元，并且标记为1，标识此位置对应的数据是黑名单。如此一来，过滤的时候，将数据哈希之后，去前面的数组当中查找，如果对应的位置值为1，表明需要被过滤，如果是0，则不需要。如果黑名单有一亿个黑名单数据，每个数据需要1bit来记录，最后也就会占用1G空间，放在内存里面妥妥的。而哈希函数计算时间可以认为是O(1)，所以过滤算法效率也很高。然而，哈希算法不可能保证不发生碰撞。尤其是黑名单这种字符串，可能会包含各种字符，也不能单纯的当作数字来处理。布隆过滤器的做法就是通过调用多个哈希函数，降低碰撞的概率。比如有3个哈希函数，碰撞概率都是10%，并且哈希方式不同，那么一个数据通过三次哈希得到的碰撞概率是单独哈希一次的 10%×10%×10%/10%=1%，也就是说，原本哈希一次碰撞概率为10%，现在三次是0.1%。黑名单误过滤的概率大大降低，而存在于黑名单当中的肯定会被过滤掉。而三次哈希的结果也直接放进之前的数组里即可。判断是否在黑名单当中，三次结果计算结果都匹配才需要过滤。

package dablooms
/*
#cgo LDFLAGS: -ldablooms
#include 
#include 
*/
import "C"

import (
    "unsafe"
)

func Version() string {
    return "0.9.0"
}

type ScalingBloom struct {
    cfilter *C.scaling_bloom_t
}

func NewScalingBloom(capacity C.uint, errorRate C.double, filename string) *ScalingBloom {
    cFilename := C.CString(filename)
    defer C.free(unsafe.Pointer(cFilename))
    sb := &ScalingBloom{
        cfilter: C.new_scaling_bloom(capacity, errorRate, cFilename),
    }
    return sb
}

func NewScalingBloomFromFile(capacity C.uint, errorRate C.double, filename string) *ScalingBloom {
    cFilename := C.CString(filename)
    defer C.free(unsafe.Pointer(cFilename))
    sb := &ScalingBloom{
        cfilter: C.new_scaling_bloom_from_file(capacity, errorRate, cFilename),
    }
    return sb
}

// apparently this is an unsupported feature of cgo
// we should probably use runtime.SetFinalizer
// see: https://groups.google.com/forum/?fromgroups#!topic/golang-dev/5cD0EmU2voI
func (sb *ScalingBloom) Destroy() {
    C.free_scaling_bloom(sb.cfilter)
}

func (sb *ScalingBloom) Check(key []byte) bool {
    cKey := (*C.char)(unsafe.Pointer(&key[0]))
    return C.scaling_bloom_check(sb.cfilter, cKey, C.size_t(len(key))) == 1
}

func (sb *ScalingBloom) Add(key []byte, id C.uint64_t) bool {
    cKey := (*C.char)(unsafe.Pointer(&key[0]))
    return C.scaling_bloom_add(sb.cfilter, cKey, C.size_t(len(key)), id) == 1
}

func (sb *ScalingBloom) Remove(key []byte, id C.uint64_t) bool {
    cKey := (*C.char)(unsafe.Pointer(&key[0]))
    return C.scaling_bloom_remove(sb.cfilter, cKey, C.size_t(len(key)), id) == 1
}

func (sb *ScalingBloom) Flush() bool {
    return C.scaling_bloom_flush(sb.cfilter) == 1
}

func (sb *ScalingBloom) MemSeqNum() C.uint64_t {
    return C.scaling_bloom_mem_seqnum(sb.cfilter)
}

func (sb *ScalingBloom) DiskSeqNum() C.uint64_t {
    return C.scaling_bloom_disk_seqnum(sb.cfilter)
}

参考

http://blog.cyeam.com/hash/2014/07/30/bloomfilter/

dongjun111111 / blog

Golang布隆过滤器实现 #43

Golang布隆过滤器实现

参考