Golang高性能线程安全布隆过滤器实现

布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。下面我将介绍如何使用Golang实现一个高性能、线程安全的布隆过滤器，并介绍ring缓冲区的使用。

基础实现

首先，我们来看一个基础的布隆过滤器实现：

package bloom

import (
	"hash"
	"hash/fnv"
	"sync"
)

type BloomFilter struct {
	bitset    []bool
	size      uint
	hashFuncs []hash.Hash64
	mutex     sync.RWMutex
}

func NewBloomFilter(size uint, numHashFuncs uint) *BloomFilter {
	bf := &BloomFilter{
		bitset: make([]bool, size),
		size:    size,
	}

	for i := uint(0); i < numHashFuncs; i++ {
		bf.hashFuncs = append(bf.hashFuncs, fnv.New64())
	}

	return bf
}

func (bf *BloomFilter) Add(item []byte) {
	bf.mutex.Lock()
	defer bf.mutex.Unlock()

	for _, hashFunc := range bf.hashFuncs {
		hashFunc.Reset()
		hashFunc.Write(item)
		hashValue := hashFunc.Sum64()
		position := hashValue % uint64(bf.size)
		bf.bitset[position] = true
	}
}

func (bf *BloomFilter) Test(item []byte) bool {
	bf.mutex.RLock()
	defer bf.mutex.RUnlock()

	for _, hashFunc := range bf.hashFuncs {
		hashFunc.Reset()
		hashFunc.Write(item)
		hashValue := hashFunc.Sum64()
		position := hashValue % uint64(bf.size)
		if !bf.bitset[position] {
			return false
		}
	}
	return true
}

高性能优化

上面的基础实现有几个性能问题：

1. 每次操作都需要创建新的hash函数
2. 使用bool数组占用空间较大
3. 锁粒度较大

下面是一个优化后的版本：

package bloom

import (
	"hash/fnv"
	"sync"
	"unsafe"
)

type BloomFilter struct {
	bitset    []uint64
	size      uint64
	hashFuncs []func([]byte) uint64
	mutex     sync.RWMutex
}

func NewBloomFilter(size uint64, numHashFuncs uint) *BloomFilter {
	bf := &BloomFilter{
		bitset: make([]uint64, (size+63)/64),
		size:   size,
	}

	// 预生成hash函数
	h := fnv.New64a()
	for i := uint(0); i < numHashFuncs; i++ {
		seed := uint64(i)
		bf.hashFuncs = append(bf.hashFuncs, func(data []byte) uint64 {
			h.Reset()
			h.Write([]byte{byte(seed)})
			h.Write(data)
			return h.Sum64() % size
		})
	}

	return bf
}

func (bf *BloomFilter) Add(item []byte) {
	bf.mutex.Lock()
	defer bf.mutex.Unlock()

	for _, hashFunc := range bf.hashFuncs {
		pos := hashFunc(item)
		bf.bitset[pos/64] |= 1 << (pos % 64)
	}
}

func (bf *BloomFilter) Test(item []byte) bool {
	bf.mutex.RLock()
	defer bf.mutex.RUnlock()

	for _, hashFunc := range bf.hashFuncs {
		pos := hashFunc(item)
		if bf.bitset[pos/64]&(1<<(pos%64)) == 0 {
			return false
		}
	}
	return true
}

使用ring缓冲区

container/ring是Go标准库提供的环形缓冲区实现，可以用于实现滑动窗口布隆过滤器：

import "container/ring"

type SlidingBloomFilter struct {
	windowSize int
	current    *BloomFilter
	history    *ring.Ring
	mutex      sync.Mutex
}

func NewSlidingBloomFilter(windowSize int, size uint64, numHashFuncs uint) *SlidingBloomFilter {
	sbf := &SlidingBloomFilter{
		windowSize: windowSize,
		current:    NewBloomFilter(size, numHashFuncs),
		history:    ring.New(windowSize),
	}
	
	// 初始化历史记录
	for i := 0; i < windowSize; i++ {
		sbf.history.Value = NewBloomFilter(size, numHashFuncs)
		sbf.history = sbf.history.Next()
	}
	
	return sbf
}

func (sbf *SlidingBloomFilter) Add(item []byte) {
	sbf.mutex.Lock()
	defer sbf.mutex.Unlock()
	
	sbf.current.Add(item)
}

func (sbf *SlidingBloomFilter) Rotate() {
	sbf.mutex.Lock()
	defer sbf.mutex.Unlock()
	
	// 将当前布隆过滤器放入历史记录
	sbf.history.Value = sbf.current
	sbf.history = sbf.history.Next()
	
	// 创建新的当前布隆过滤器
	sbf.current = NewBloomFilter(sbf.current.size, uint(len(sbf.current.hashFuncs)))
}

func (sbf *SlidingBloomFilter) Test(item []byte) bool {
	sbf.mutex.RLock()
	defer sbf.mutex.RUnlock()
	
	if sbf.current.Test(item) {
		return true
	}
	
	// 检查历史记录
	sbf.history.Do(func(x interface{}) {
		if x != nil && x.(*BloomFilter).Test(item) {
			return true
		}
	})
	
	return false
}

性能对比

优化后的实现有以下改进：

1. 使用uint64数组代替bool数组，节省了8倍内存
2. 预生成hash函数，避免每次操作都创建
3. 使用更细粒度的锁
4. ring缓冲区实现了滑动窗口功能

使用示例

func main() {
	// 创建布隆过滤器
	bf := NewBloomFilter(1000000, 5)
	
	// 添加元素
	bf.Add([]byte("hello"))
	bf.Add([]byte("world"))
	
	// 测试元素
	fmt.Println(bf.Test([]byte("hello"))) // true
	fmt.Println(bf.Test([]byte("world"))) // true
	fmt.Println(bf.Test([]byte("foo")))   // false
	
	// 使用滑动窗口布隆过滤器
	sbf := NewSlidingBloomFilter(10, 1000000, 5)
	sbf.Add([]byte("item1"))
	sbf.Rotate() // 时间窗口滑动
	sbf.Add([]byte("item2"))
	
	fmt.Println(sbf.Test([]byte("item1"))) // true (在历史窗口中)
	fmt.Println(sbf.Test([]byte("item2"))) // true (在当前窗口中)
}

这个实现提供了高性能、线程安全的布隆过滤器功能，适用于需要快速判断元素是否存在的场景，如URL去重、缓存穿透防护等。