学习 Bloom filter

误判率的推导

• 前提：

1. 数组长度 m
2. 有 k 个 hash 函数，每个 hash 函数彼此独立（老实说，彼此独立这个条件怎么达到我也不太清楚，以及或许有其他的前提条件我也不太清楚）
3. 用 n 个样本空间

• 推导过程

第一部分：

1. 经过一个 hash 函数以后某一位置为 0 的概率是

2. 经过 k 个 hash 函数以后某一位置为 0 的概率是

3. 经过 n 个样本以后某一位置为 0 的概率是

4. 因此经过 n 个样本以后某一位为 1 的概率是

5. 现在再来一个新的样本，全选到 1 的概率是

第二部分，上面先推导到这里接下来需要推导一个别的：

1. 这是 e 的推导：
2. 将 -x 替换 x
3. 
4. 

我们再从第一部分的第五步继续向后：

6. 变形得：
7. 对于大 m 约等于：

所以针对大 m，误报率约为：

我们通常要根据 n 和 m 推导合适的 hash 个数，为：。

如果需要根据误报率来推导，此时 ，此时误报率 。可以简写为：

这导致：

所以 m 和 n 的最佳比值此时为：

后面的部分我都是摘自 wiki：https://en.wikipedia.org/wiki/Bloom_filter。根据这些我们就可以实现自己的 Bloom filter。

• 参考

https://en.wikipedia.org/wiki/Bloom_filter

实现

我们在实现的时候前提条件通常是：

• 假阳性 p 概率是多少
• 要存的样本空间多大

要求的就是上面公式里的 k 和 m。

• m 告诉我们需要多少的 bit 位
• k 告诉我们需要多少个 hash 函数

按照公式：

• 

• 

大概实现如下：

// bloom.go
// Copyright 2021 hardcore-os Project Authors
//
// Licensed under the Apache License, Version 2.0 (the "License")
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package utils

import "math"

// Filter is an encoded set of []byte keys.
type Filter []byte

// MayContainKey _
func (f Filter) MayContainKey(k []byte) bool {
    return f.MayContain(Hash(k))
}

func (f Filter) K() uint8 {
    return f[len(f) - 1]
}

// get 根据 hash 值得到 filter 中某一位的值
func (f Filter) get(h uint32) uint8 {
    x, y := posInFilter(h, len(f) - 1)
    return uint8((f[x] >> y) & 1)
}

// set 根据 hash 值将某一位置 1
func (f Filter) set(h uint32) {
    x, y := posInFilter(h, len(f) - 1)
    f[x] = f[x] | 1 << y
}

// MayContain returns whether the filter may contain given key. False positives
// are possible, where it returns true for keys not in the original set.
func (f Filter) MayContain(h uint32) bool {
    //Implement me here!!!
    //在这里实现判断一个数据是否在bloom过滤器中
    //思路大概是经过K个Hash函数计算，判读对应位置是否被标记为1
    delta, k := h >> 17 | h << 15, f.K()
    for j := uint8(0); j < k; j ++ {
        if f.get(h) == 0 {
            return false
        }
        h += delta
    }
    return true
}

// posInFilter 根据 hash 值计算此 hash 在 pos 的哪一个位置
// h 是 hash 值，filterLen 就是用byte数组中真正做做filter的长度
func posInFilter(h uint32, filterLen int) (x, y int) {
    nBits :=  uint32(filterLen * 8)
    bitPos := h % nBits
    return int(bitPos / 8), int(bitPos % 8)
}

// NewFilter returns a new Bloom filter that encodes a set of []byte keys with
// the given number of bits per key, approximately.
//
// A good bitsPerKey value is 10, which yields a filter with ~ 1% false
// positive rate.
func NewFilter(keys []uint32, bitsPerKey int) Filter {
    return appendFilter(keys, bitsPerKey)
}

// BloomBitsPerKey returns the bits per key required by bloomfilter based on
// the false positive rate.
func BloomBitsPerKey(numEntries int, fp float64) int {
    //Implement me here!!!
    //阅读bloom论文实现，并在这里编写公式
    //传入参数numEntries是bloom中存储的数据个数，fp是false positive假阳性率
    // 计算 m/n 根据：https://en.wikipedia.org/wiki/Bloom_filter
    return int(-1.44 * math.Log2(fp) + 1)
}

func appendFilter(keys []uint32, bitsPerKey int) Filter {
    //Implement me here!!!
    //在这里实现将多个Key值放入到bloom过滤器中
    // TODO：系统检查 bitsPerKey
    if bitsPerKey < 0 {
        bitsPerKey = 0
    }
    keyLen := len(keys)
    k := uint8(float64(bitsPerKey) * 0.69)
    if k < 1 {
        k = 1
    }

    if k > 30 {
        k = 30
    }

    nBits := bitsPerKey * keyLen

    // 如果 nBits 太小会有很高的 false positive
    if nBits < 64 {
        nBits = 64
    }

    // TODO：检查 nBits 的上界

    nBytes := (nBits + 7) / 8
    // 最后一位
    filter := Filter(make([]byte, nBytes + 1))


    // 向 filter 中放入所有的 key
    for _, h := range keys {
        delta := h >> 17 | h << 15
        for j := uint8(0); j < k; j ++ {
            filter.set(h)
            h += delta
        }
    }

    filter[nBytes] = k
    return filter
}



// Hash implements a hashing algorithm similar to the Murmur hash.
func Hash(b []byte) uint32 {
    const (
        seed = 0xbc9f1d34
        m    = 0xc6a4a793
    )
    h := uint32(seed) ^ uint32(len(b))*m
    for ; len(b) >= 4; b = b[4:] {
        h += uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
        h *= m
        h ^= h >> 16
    }
    switch len(b) {
    case 3:
        h += uint32(b[2]) << 16
        fallthrough
    case 2:
        h += uint32(b[1]) << 8
        fallthrough
    case 1:
        h += uint32(b[0])
        h *= m
        h ^= h >> 24
    }
    return h
}

// bloom_test.go
// Copyright 2021 hardcore-os Project Authors
//
// Licensed under the Apache License, Version 2.0 (the "License")
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package utils

import (
    "testing"
)

func (f Filter) String() string {
    s := make([]byte, 8*len(f))
    for i, x := range f {
        for j := 0; j < 8; j++ {
            if x&(1<<uint(j)) != 0 {
                s[8*i+j] = '1'
            } else {
                s[8*i+j] = '.'
            }
        }
    }
    return string(s)
}

func TestSmallBloomFilter(t *testing.T) {
    var hash []uint32
    for _, word := range [][]byte{
        []byte("hello"),
        []byte("world"),
    } {
        hash = append(hash, Hash(word))
    }

    f := NewFilter(hash, 10)
    got := f.String()
    // The magic want string comes from running the C++ leveldb code's bloom_test.cc.
    want := "1...1.........1.........1.....1...1...1.....1.........1.....1....11....."
    if got != want {
        t.Fatalf("bits:\ngot  %q\nwant %q", got, want)
    }

    m := map[string]bool{
        "hello": true,
        "world": true,
        "x":     false,
        "foo":   false,
    }
    for k, want := range m {
        got := f.MayContainKey([]byte(k))
        if got != want {
            t.Errorf("MayContain: k=%q: got %v, want %v", k, got, want)
        }
    }
}

func TestBloomFilter(t *testing.T) {
    nextLength := func(x int) int {
        if x < 10 {
            return x + 1
        }
        if x < 100 {
            return x + 10
        }
        if x < 1000 {
            return x + 100
        }
        return x + 1000
    }
    le32 := func(i int) []byte {
        b := make([]byte, 4)
        b[0] = uint8(uint32(i) >> 0)
        b[1] = uint8(uint32(i) >> 8)
        b[2] = uint8(uint32(i) >> 16)
        b[3] = uint8(uint32(i) >> 24)
        return b
    }

    nMediocreFilters, nGoodFilters := 0, 0
loop:
    for length := 1; length <= 10000; length = nextLength(length) {
        keys := make([][]byte, 0, length)
        for i := 0; i < length; i++ {
            keys = append(keys, le32(i))
        }
        var hashes []uint32
        for _, key := range keys {
            hashes = append(hashes, Hash(key))
        }
        f := NewFilter(hashes, 10)

        if len(f) > (length*10/8)+40 {
            t.Errorf("length=%d: len(f)=%d is too large", length, len(f))
            continue
        }

        // All added keys must match.
        for _, key := range keys {
            if !f.MayContainKey(key) {
                t.Errorf("length=%d: did not contain key %q", length, key)
                continue loop
            }
        }

        // Check false positive rate.
        nFalsePositive := 0
        for i := 0; i < 10000; i++ {
            if f.MayContainKey(le32(1e9 + i)) {
                nFalsePositive++
            }
        }
        if nFalsePositive > 0.02*10000 {
            t.Errorf("length=%d: %d false positives in 10000", length, nFalsePositive)
            continue
        }
        if nFalsePositive > 0.0125*10000 {
            nMediocreFilters++
        } else {
            nGoodFilters++
        }
    }

    if nMediocreFilters > nGoodFilters/5 {
        t.Errorf("%d mediocre filters but only %d good filters", nMediocreFilters, nGoodFilters)
    }
}

func TestHash(t *testing.T) {
    // The magic want numbers come from running the C++ leveldb code in hash.cc.
    testCases := []struct {
        s    string
        want uint32
    }{
        {"", 0xbc9f1d34},
        {"g", 0xd04a8bda},
        {"go", 0x3e0b0745},
        {"gop", 0x0c326610},
        {"goph", 0x8c9d6390},
        {"gophe", 0x9bfd4b0a},
        {"gopher", 0xa78edc7c},
        {"I had a dream it would end this way.", 0xe14a9db9},
    }
    for _, tc := range testCases {
        if got := Hash([]byte(tc.s)); got != tc.want {
            t.Errorf("s=%q: got 0x%08x, want 0x%08x", tc.s, got, tc.want)
        }
    }
}

• 参考

测试代码和实现代码的框架来自：https://github.com/hardcore-os/corekv