Bloom Filter 原理与应用

转自：http://blog.huang-wei.com/2010/11/02/bloom-filter/

介绍

Bloom Filter是一种简单的节省空间的随机化的数据结构，支持用户查询的集合。一般我们使用STL的std::set, stdext::hash_set，std::set是用红黑树实现的，stdext::hash_set是用桶式哈希表。上述两种数据结构，都会需要保存原始数据信息，当数据量较大时，内存就会是个问题。如果应用场景中允许出现一定几率的误判，且不需要逆向遍历集合中的数据时，Bloom Filter是很好的结构。

优点

1. 查询操作十分高效。
2. 节省空间。
3. 易于扩展成并行。
4. 集合计算方便。
5. 代码实现方便。
6. 有误判的概率，即存在False Position。
7. 无法获取集合中的元素数据。
8. 不支持删除操作。

缺点

1. 有误判的概率，即存在False Position。
2. 无法获取集合中的元素数据。
3. 不支持删除操作。

定义

Bloom Filter是一个有m位的位数组，初始全为0，并有k个各自独立的哈希函数。

图1

添加操作

每个元素，用k个哈希函数计算出大小为k的哈希向量
，将向量里的每个哈希值对应的位设置为1。时间复杂度为，一般字符串哈希函数的时间复杂度也就是。

查询操作

和添加类似，先计算出哈希向量，如果每个哈希值对应的位都为1，则该元素存在。时间复杂度与添加操作相同。

示例

图2表示m=16，k=2的Bloom Filter， 和 的哈希值分别为(3, 6)和(10, 3)。

图2

False Position

如果某元素不在Bloom Filter中，但是它所有哈希值的位置均被设为1。这种情况就是False Position，也就是误判。

借用示例，如下：

图3

这个问题其实和哈希表中的冲突是相同的道理，哈希表中可以使用开散列和闭散列的方法，而Bloom Filter则允许这样的情况发生，它更关心于误判的发生概率。

概率

宏观上，我们能得出以下结论：

参数表	变量	减少	增加
哈希函数总数	K	l 更少的哈希值计算 l 增加False Position的概率	l 更多的计算 l 位值0减少
Bloom Filter大小	M	l 更少的内存 l 增加False Position的概率	l 更多的内存 l 降低概率
元素总数	N	l 降低False Position的概率	l 增加概率

False Position的概率为。

假设m和n已知，为了最小化False Position，则。

数据

图4

扩展

Counter Bloom Filter

Bloom Filter有个缺点，就是不支持删除操作，因为它不知道某一个位从属于哪些向量。那我们可以给Bloom Filter加上计数器，添加时增加计数器，删除时减少计数器。

但这样的Filter需要考虑附加的计数器大小，假如同个元素多次插入的话，计数器位数较少的情况下，就会出现溢出问题。如果对计数器设置上限值的话，会导致Cache Miss，但对某些应用来说，这并不是什么问题，如Web Sharing。

Compressed Bloom Filter

为了能在服务器之间更快地通过网络传输Bloom Filter，我们有方法能在已完成Bloom Filter之后，得到一些实际参数的情况下进行压缩。

将元素全部添加入Bloom Filter后，我们能得到真实的空间使用率，用这个值代入公式计算出一个比m小的值，重新构造Bloom Filter，对原先的哈希值进行求余处理，在误判率不变的情况下，使得其内存大小更合适。

应用

加速查询

适用于一些key-value存储系统，当values存在硬盘时，查询就是件费时的事。

将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。

当False Position出现时，只是会导致一次多余的Storage查询。

图5

l Google的BigTable也使用了Bloom Filter，以减少不存在的行或列在磁盘上的查询，大大提高了数据库的查询操作的性能。

l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存储URLs，除了高效的查询外，还能很方便得传输交换Cache信息。

网络应用

l P2P网络中查找资源操作，可以对每条网络通路保存Bloom Filter，当命中时，则选择该通路访问。

l 广播消息时，可以检测某个IP是否已发包。

l 检测广播消息包的环路，将Bloom Filter保存在包里，每个节点将自己添加入Bloom Filter。

l 信息队列管理，使用Counter Bloom Filter管理信息流量。

垃圾邮件地址过滤

来自于Google黑板报的例子。

像网易，QQ这样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。

一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。

如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。

而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

Bloom Filter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

引用

[1] Bloom filter;http://en.wikipedia.org/wiki/Bloom_filter

[2] Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol;http://pages.cs.wisc.edu/~cao/papers/summary-cache/

[3] Network Applications of Bloom Filters: A Survey;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf

[4] An Examination of Bloom Filters and their Applications;http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf

[5] 数学之美系列二十一 － 布隆过滤器（Bloom Filter）;http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html

/*
*   File:       bloomfilter.h
*   Created:    2010/10/31
*   Author:     Huang.WisKey
*   E-Mail:     sir.huangwei[at]gmail.com
*   Brief:
*
*   May you do good and not evil.
*   May you find forgiveness for yourself and forgive others.
*   May you share freely, never taking more than you give.
*/
 
#pragma once
 
#ifndef __BLOOMFILTER_H__
#define __BLOOMFILTER_H__
 
#include "stdlib.h"
#include "memory.h"
#include "time.h"
#include "math.h"
 
#ifndef NULL
#   ifdef __cplusplus
#       define NULL 0
#   else
#       define NULL ((void *)0)
#   endif
#endif
 
unsigned int string_SDBM_hash(const char* _str);
unsigned int string_RS_hash(const char* _str);
unsigned int string_JS_hash(const char* _str);
unsigned int string_PJW_hash(const char* _str);
unsigned int string_ELF_hash(const char* _str);
unsigned int string_BKDR_hash(const char* _str);
unsigned int string_DJB_hash(const char* _str);
unsigned int string_AP_hash(const char* _str);
 
template <typename T>
class bloomfilter
{
public:
    typedef unsigned int hash_key;
    typedef hash_key (*hash_func_type)(const T&);
    typedef unsigned int cell_type;
    typedef unsigned int size_type;
 
protected:
    static hash_key default_hash_func(const T& _obj)
    {
        return string_AP_hash(reinterpret_cast <const char*> (_obj));
    }
 
public:
    bloomfilter(size_type _elem_size,
                double _prob_false_positive,
                unsigned int _rand_seed = static_cast <unsigned int> (time(NULL)),
                hash_func_type _hash_func = default_hash_func
                )
    : bit_table_(NULL),
      table_size_(0),
      hash_func_(_hash_func ? _hash_func : default_hash_func),
      elem_bit_size_(0),
      elem_bit_randoms_(NULL),
      elem_size_(0),
      randoms_seed_(_rand_seed)
    {
        _optimal_parameters(_elem_size, _prob_false_positive);
        _generate_random();
        bit_table_ = new cell_type[table_size_ / sizeof(cell_type)];
        memset(bit_table_, 0, table_size_);
    }
 
    bloomfilter(const bloomfilter& _obj)
    {
        // bit table
        table_size_ = _obj.table_size_;
        bit_table_ = new cell_type[table_size_ / sizeof(cell_type)];
        memcpy(bit_table_, _obj.bit_table_, table_size_);
        // hash func
        hash_func_ = _obj.hash_func_;
        // elem
        elem_bit_size_ = _obj.elem_bit_size_;
        elem_bit_randoms_ = new hash_key[elem_bit_size_];
        memcpy(elem_bit_randoms_, _obj.elem_bit_randoms_, elem_bit_size_ * sizeof(hash_key));
        elem_size_ = _obj.elem_size_;
    }
 
    virtual ~bloomfilter()
    {
        delete[] bit_table_;
        bit_table_ = NULL;
        delete[] elem_bit_randoms_;
        elem_bit_randoms_ = NULL;
        hash_func_ = NULL;
        table_size_ = 0;
        hash_func_ = NULL;
        elem_bit_size_ = 0;
        elem_size_ = 0;
    }
 
    void insert(const T& _obj)
    {
        hash_key p, b;
        hash_key hash = hash_func_(_obj);
        bool exist = true;
        for (unsigned int i = 0; i < elem_bit_size_; i ++) {
            _get_pos(elem_bit_randoms_[i] * hash, p, b);
            exist = exist && (bit_table_[p] & (0x01L<<b));
            bit_table_[p] |= 0x01L << b;
        }
        elem_size_ += ! exist;
    }
 
    bool find(const T& _obj)
    {
        hash_key p, b;
        hash_key hash = hash_func_(_obj);
        bool exist = true;
        for (unsigned int i = 0; i < elem_bit_size_ && exist; i ++) {
            _get_pos(elem_bit_randoms_[i] * hash, p, b);
            exist = exist && (bit_table_[p] & (0x01L<<b));
        }
        return exist;
    }
 
    double effective_fpp() const
    {
        /*
        Note:
        The effective false positive probability is calculated using the
        designated table size and hash function count in conjunction with
        the current number of inserted elements - not the user defined
        predicated/expected number of inserted elements.
        */
        return pow(1.0 - exp(-1.0 * elem_bit_size_ * elem_size_ / table_size_), 1.0 * elem_bit_size_);
    }
 
    size_type size()
    {
        /* in bytes */
        return table_size_;
    }
 
    size_type cell_size()
    {
        return table_size_ / sizeof(cell_type);
    }
 
    size_type count()
    {
        return elem_size_;
    }
 
    void clear()
    {
        memset(bit_table_, 0, table_size_);
        elem_size_ = 0;
    }
 
    const cell_type* table()
    {
        return bit_table_;
    }
 
    bloomfilter& operator &= (const bloomfilter& _obj)
    {
        /* intersection */
        if (
            (elem_bit_size_  == _obj.elem_bit_size_) &&
            (table_size_  == _obj.table_size_) &&
            (randoms_seed_ == _obj.randoms_seed_) &&
            (hash_func_ == _obj.hash_func_)
            )
        {
            size_type cells = cell_size();
            for (size_type i = 0; i < cells; ++i)
                bit_table_[i] &= _obj.bit_table_[i];
        }
        return *this;
    }
 
    bloomfilter& operator |= (const bloomfilter& _obj)
    {
        /* union */
        if (
            (elem_bit_size_  == _obj.elem_bit_size_) &&
            (table_size_  == _obj.table_size_) &&
            (randoms_seed_ == _obj.randoms_seed_) &&
            (hash_func_ == _obj.hash_func_)
            )
        {
            size_type cells = cell_size();
            for (size_type i = 0; i < cells; ++i)
                bit_table_[i] |= _obj.bit_table_[i];
        }
        return *this;
    }
 
    bloomfilter& operator ^= (const bloomfilter& _obj)
    {
        /* difference */
        if (
            (elem_bit_size_  == _obj.elem_bit_size_) &&
            (table_size_  == _obj.table_size_) &&
            (randoms_seed_ == _obj.randoms_seed_) &&
            (hash_func_ == _obj.hash_func_)
            )
        {
            size_type cells = cell_size();
            for (size_type i = 0; i < cells; ++i)
                bit_table_[i] ^= _obj.bit_table_[i];
        }
        return *this;
    }
 
protected:
    void _optimal_parameters(unsigned int _elem_size_prob, double _prob_false_positive)
    {
        /*
        Note:
        The following will attempt to find the number of hash functions
        and minimum amount of storage bits required to construct a bloom
        _obj consistent with the user defined false positive probability
        and estimated element insertion count.
        */
        double min_m = 1e99;
        double min_k = 0.0;
        double curr_m = 0.0;
        for(double k = 0.0; k < 1000.0; ++k) {
            if ((curr_m = ((- k * _elem_size_prob) / log(1.0 - pow(_prob_false_positive, 1.0 / k)))) < min_m) {
                min_m = curr_m;
                min_k = k;
            }
        }
 
        elem_bit_size_ = static_cast <size_type> (min_k);
        table_size_ = static_cast <size_type> (min_m);
        table_size_ = ((table_size_ > _elem_size_prob ? table_size_ : _elem_size_prob) / sizeof(cell_type) + 1) * sizeof(cell_type);
    }
 
    void _generate_random()
    {
        elem_bit_randoms_ = new hash_key[elem_bit_size_];
        srand(randoms_seed_);
        for (unsigned int i = 0; i < elem_bit_size_; i ++) {
            elem_bit_randoms_[i] = rand();
        }
    }
 
    void _get_pos(hash_key _hash, hash_key& _cell, hash_key& _bit)
    {
        _hash %= table_size_;
        _cell = _hash / sizeof(hash_key);
        _bit = _hash % sizeof(hash_key);
    }
 
protected:
    cell_type*      bit_table_;
    size_type       table_size_;
    hash_func_type  hash_func_;
    size_type       elem_bit_size_;
    hash_key*       elem_bit_randoms_;
    size_type       elem_size_;
    unsigned int    randoms_seed_;
};
 
// SDBM Hash Function
unsigned int string_SDBM_hash(const char* _str)
{
    unsigned int hash = 0;
    while (*_str) {
        // equivalent to: hash = 65599*hash + (*_str++);
        hash = (*_str++) + (hash << 6) + (hash << 16) - hash;
    }
    return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int string_RS_hash(const char* _str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;
    while (*_str) {
        hash = hash * a + (*_str++);
        a *= b;
    }
    return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int string_JS_hash(const char* _str)
{
    unsigned int hash = 1315423911;
    while (*_str) {
        hash ^= ((hash << 5) + (*_str++) + (hash >> 2));
    }
    return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int string_PJW_hash(const char* _str)
{
    unsigned int BitsInUnignedInt   = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters      = (unsigned int)((BitsInUnignedInt  * 3) / 4);
    unsigned int OneEighth          = (unsigned int)(BitsInUnignedInt / 8);
    unsigned int HighBits           = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    unsigned int hash               = 0;
    unsigned int test               = 0;
    while (*_str) {
        hash = (hash << OneEighth) + (*_str++);
        if ((test = hash & HighBits) != 0) {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
    return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int string_ELF_hash(const char* _str)
{
    unsigned int hash = 0;
    unsigned int x  = 0;
    while (*_str) {
        hash = (hash << 4) + (*_str++);
        if ((x = hash & 0xF0000000L) != 0) {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }
    return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int string_BKDR_hash(const char* _str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*_str) {
        hash = hash * seed + (*_str++);
    }
    return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int string_DJB_hash(const char* _str)
{
    unsigned int hash = 5381;
    while (*_str) {
        hash += (hash << 5) + (*_str++);
    }
    return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int string_AP_hash(const char* _str)
{
    unsigned int hash = 0;
    for (int i=0; *_str; i++) {
        if ((i & 1) == 0)
            hash ^= ((hash << 7) ^ (*_str++) ^ (hash >> 3));
        else
            hash ^= (~((hash << 11) ^ (*_str++) ^ (hash >> 5)));
    }
    return (hash & 0x7FFFFFFF);
}
 
#endif // __BLOOMFILTER_H__