cuckoofilter

go-cuckoofilter

CuckooFilter用于快速判断一个元素是否属于某个集合, 以少量错误率换取很高的空间利用率.

本项目将CuckooFilter存储部分接口化, 实现了两种存储方式(Table接口):

• MemTable, 内存存储, 对应Golang中的[]byte类型
• MMAPTable, 文件存储, 使用MMAP快速读写文件

下载

go get -u github.com/spencer404/go-cuckoofilter

示例

package main

import (
	"fmt"
	"github.com/spencer404/go-cuckoofilter"
)

func main() {
	table := cuckoofilter.NewMemTable(1 << 30) // Size: 1GB
	cf := cuckoofilter.NewCuckooFilter(table)
	
	err := cf.InsertUnique([]byte("Hello"))
	fmt.Println(err) // <nil>

	ok, err := cf.Lookup([]byte("Hello"))
	fmt.Println(ok, err) // true <nil>

	n := cf.Count()
	fmt.Println(n) // 1

	err = cf.Delete([]byte("Hello"))
	fmt.Println(err) // <nil>

	ok, err = cf.Lookup([]byte("Hello"))
	fmt.Println(ok, err) // false <nil>

	n = cf.Count()
	fmt.Println(n) // 0
}

主要操作

在内存中创建过滤器

table := cuckoofilter.NewMemTable(capacity)
cf := cuckoofilter.NewCuckooFilter(table)

Capacity等于占用内存/文件的大小(字节), 项目默认配置fingerprint占用空间为1Byte.

因此, 1 Capacity == 1 Byte空间占用 == 最多容纳1个元素.

业务中具体Capacity的数值, 理应在预计元素数量, 性能, 错误率之间寻找点.

但如果你像我一样懒的话, 直接取预计元素数量 * 2.

如果无法估计元素数量, 可以使用多层的过滤器, 当空间利用率过高时, 再增加一个新的过滤器.

在文件中创建过滤器

table, err := NewMMAPTable(filename, capacity)
cf := cuckoofilter.NewCuckooFilter(table)

注意, 若程序意外退出, 未被刷入文件的数据将会丢失.

插入元素

err := cf.InsertUnique(a)

其返回值err可能为:

• ErrExist, 元素a已存在(可能是Lookup误报)
• nil, 元素a已被插入到哈希表的空位中(哈希表接近饱和时, 可能会挪走旧元素以腾出空位, 引起Lookup误报)
• ErrFull, 多次尝试后, 仍未能在哈希表中找到空位, 此时哈希表已接近饱和
• 其他情况, 通常是底层存储出现了异常

是否存在

ok, err := cf.Lookup(a)

• 当err!=nil, 通常是底层存储出现了异常
• 当ok==true时, 可能是误报: 存在已插入的元素b与a具有相同的哈希
• 当ok==false时, 可能是误报: InsertUnique(b)时, 由于哈希表已接近饱和, a给b挪出空位后, a无处安放, 被移出了哈希表(其实可增加Rollback流程,使得ok==false是确定的)

删除元素

err := cf.Delete(a)

• 当err!=nil, 通常是底层存储出现了异常

• 当err==ErrNotExist, 未找到元素a, 无法删除. 可能是误报, 原因见是否存在 > 当ok==false

• 注意, 只删除已插入过的元素, 若删除未曾插入的元素, 会使Lookup操作出现更多的误报.

  假设元素k未曾插入到过滤器中, a已被插入到过滤器中, a与k具有相同的哈希, 那么Delete(k)时会返回成功, 但实际上把a给删掉了.

性能测试

测试平台

• Intel Xeon L5640 @ 2.27GHz

• Ubuntu 16.04

• 普通SSD

• 测试方法为插入Capacity条不重复的数据

MemTable:InsertUnique

• Capacity: 1073741824Byte (=1GB)
• FingerprintSize: 1Byte
• SlotSize: 4Byte

MMAPTable:InsertUnique

• Capacity: 1073741824Byte (=1GB)
• FingerprintSize: 1Byte
• SlotSize: 4Byte

参考资料

• cmu:Cuckoo Filter: Practically Better Than Bloom
• github:seiflotfy/cuckoofilter
• github:edsrzf/mmap-go