V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zhengji
V2EX  ›  程序员

一个比 BloomFilter 更优的过滤器, CuckooFilter

  •  1
     
  •   zhengji ·
    zheng-ji · 2016-07-29 22:43:52 +08:00 · 3496 次点击
    这是一个创建于 2799 天前的主题,其中的信息可能已经有所发展或是发生改变。

    阅读 CMU 的论文PPT,以及Coolshell 的相关文章,用 Go 语言实现了论文提到的算法,做成一个库, goCuckoo GitHub

    Build Status GoDoc

    A Cuckoo hashing, substituting for bloom filter. written by Go

    一个 Cuckoo Filter 的 Go 库

    goCuckoo

    Description

    面对海量数据,我们需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这类数据结构叫过滤器,常用的选择是 Bloom Filter. 而 Cuckoo Filter 是它的优化变种。

    Bloom Filter 的位图模式有两个问题:

    • 误报,它能判断元素一定不存在,但只能判断可能存在,因为存在其它元素被映射到部分相同位上,导致该位置 1 ,那么一个不存在的元素可能会被误报成存在;
    • 漏报,如果删除了某个元素,导致该映射位被置 0 ,那么本来存在的元素会被漏报成不存在。

    Cuckoo Filter,可以确保该元素存在的必然性,又可以在不违背此前提下删除任意元素,仅仅比 Bloom Filter 牺牲了微量空间效率。 它的的数据模型:

    • 每个元素对应两个哈希算法,在哈希碰撞时会启用备用哈希算法。
    • 每一个桶是有 4 路的,每个槽对应一个指纹。

    model

    Feature

    • Deletion Support
    • FastLoopUp O(1)
    • High Space Utilization,4-way set-associative table: > 95% entries occupied
    • Subsituting for Bloom Filters

    Installation

    go get github.com/zheng-ji/goCuckoo
    

    Example

    import (
    	"fmt"
    	"github.com/zheng-ji/goCuckoo"
    )
    
    func main() {
        // speicify capacity 
    	filter := cuckoo.NewCuckooFilter(10000)
    
    	filter.Insert([]byte("zheng-ji"))
    	filter.Insert([]byte("stupid"))
    	filter.Insert([]byte("coder"))
    
    	if filter.Find([]byte("stupid")) {
    		fmt.Println("exist")
    	} else {
    		fmt.Println("Not exist")
    	}
    
    	filter.Del([]byte("stupid"))
    	filter.Println(filter.Size())
    }
    

    Documentation

    License

    Copyright (c) 2016 by zheng-ji released under MIT License.

    4 条回复    2016-07-30 00:08:42 +08:00
    3dwelcome
        1
    3dwelcome  
       2016-07-29 23:10:27 +08:00 via Android
    牛逼
    mscorp
        2
    mscorp  
       2016-07-29 23:41:23 +08:00 via iPhone
    效率怎么样?误差率呢
    KyleMeow
        3
    KyleMeow  
       2016-07-29 23:49:33 +08:00 via iPhone   ❤️ 1
    酷壳上也有个文章是介绍这个的,详细一些
    knightdf
        4
    knightdf  
       2016-07-30 00:08:42 +08:00
    Bloom Filter 本来就不应该做删除,我用 bloom 不就是为了节省内存而浪费一点精度?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5430 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 08:49 · PVG 16:49 · LAX 01:49 · JFK 04:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.