Featured image of post PHP+Redis实现布隆过滤器(bloom filter)
PHP

PHP+Redis实现布隆过滤器(bloom filter)

业务背景

  1. 新站迁移后，页面的链接发生改变，要求访问老链接时自动跳转至新链接 访问产品页、类目页、CMS页等页面时，如果访问老链接，需要自动跳转至新链接，由于这些页面全部是流量非常大的页面，所以需要将老链接=>新链接的缓存缓存起来以加快速度并降低MySQL的负载。起初我的做法很简单： ①如果老链接=>新链接的对应关系存在，则将query_url => redirect_url缓存起来 ②如果老链接=>新链接的对应关系不存在，为防止缓存击穿，将query_url => “” 缓存起来 虽然可以正常工作，但是由于query_url几乎是无限的，导致redis里的key的数量不断上升 那能不能很快地知道某个query_url是不是老链接呢？

  2. 偏远地区运费计算 一直以来，我们将运输方式分为三个等级：普通、快、特快，运费按等级收取，但是快递公司对一些偏远地区要加收额外的偏远运费。对于发货地址是偏远地区的订单，需要额外收取偏远地区运费。 运营人员将偏远地区的邮编、运费整理出一个表格，如果用户提交的邮编，命中这些邮编时，则收取额外运费。我初步计算文档内数据量在20万条左右，如果每次计算订单金额时都要在MySQL中查询偏远地区运费，必然会拖慢订单金额计算速度，毕竟大部分订单的发货地址都不是偏远地区。 那能不能很快的知道某个邮编在不在这些偏远地区邮编里呢？

对于上面两个问题，前辈们早已想出了一个很好的解决方案： 布隆过滤器（Bloom Filter）

布隆过滤器基本概念

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(log n),O(1)。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。另外，一般情况下不能从布隆过滤器中删除元素。

代码实现思路：

  1. 保存和获取： 基于 Redis 的 SETBIT 和 GETBIT 两个命令实现
  2. Hash函数： 参考链接 https://www.partow.net/programming/hashfunctions/
  3. 初始化： 对于大量的记录，如果要通过 Redis 的 SETBIT 命令进行录入，会非常耗时，在我的开发机器上测试，写入10万条记录需要大约40秒，所以在初始化时需要另寻他法。幸好 Redis 的 bitmap 是基于 Redis String 数据类型实现的，所以先将二进制数据转换为字符串，再一次性写入 Redis，速度非常快
  4. 控制 Redis bitmap 的大小： 如果对Hash函数计算得出的offset不做转换，那每一个布隆过滤器的bitmap实际占用内存会非常大，因为offset可能是一个非常大的整数，例如offset=2^30，为了保存第2^30个bit上的1， Redis最少需要开辟2^30 bit(128 MB)的内存空间。那么如何限制布隆过滤器的bitmap的实际大小呢？只要限制offset的大小即可，初始化BloomFilter对象时，指定bitMapSize，然后对每个offset按bitMapSize取余，这样就能保证所有的offset都小于bitMapSize，也就将布隆过滤器的bitmap实际大小控制在了bitMapSize bits。
  5. 控制误判率：设共存入n个元素，每个元素取3个hash，则极限误判率 = (n * 3 / bitMapSize)^3 （假设存入的每个元素，hash均不发生碰撞）。 例如存入100万个元素，bitMapSize设置为 1MB, 极限误判率 = (3000000/(1024 * 1024 * 8))^3 = 4.57%, 由于存入元素时，hash可能会碰撞(碰撞率我猜测可能符合正态分布)，所以一般情况下的误判率为极限误判率的60%。

代码实现

以下是基于PHP的Yii2框架实现的一个简易布隆过滤器

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

class BloomFilter
{
    private \yii\redis\Connection $redis;
    private string $bucket;
    private int $bitMapSize;


    private function __construct(string $bucket, int $bitMapSize)
    {
        $this->bucket = $bucket;
        $this->bitMapSize = $bitMapSize;
        $this->redis = \Yii::$app->redis;
    }

    /**
     * @param string $bucket
     * @param int $sizeInKB
     * @param array $inputs
     * @return BloomFilter
     */
    public static function getInstance(string $bucket, int $sizeInKB)
    {
        $bitMapSize = $sizeInKB * 1024 * 8;
        return new BloomFilter($bucket, $bitMapSize);
    }

    public function reset(int $sizeInKB, array $inputs=[])
    {
        $this->bitMapSize = $sizeInKB * 1024 * 8;
        if (empty($inputs)) {
            $this->redis->del($this->bucket);
        } else {    // 借助字符串初始化
            $bits = str_pad('', $this->bitMapSize, '0');
            foreach ($inputs as $in) {
                $offsets = $this->calcOffsets($in);
                foreach ($offsets as $offset) {
                    $bits[$offset] = '1';
                }
            }

            $len = strlen($bits);
            $pos = 0;
            $content = '';
            while($pos < $len-1) {
                $content .= chr(base_convert(substr($bits, $pos, 8), 2, 10));
                $pos += 8;
            }
            $this->redis->set($this->bucket, $content);
        }
    }

    public function destroy()
    {
        $this->redis->del($this->bucket);
    }

    public function add(string $in)
    {
        $offsets = $this->calcOffsets($in);
        foreach ($offsets as $offset) {
            $this->redis->setbit($this->bucket, $offset, 1);
        }
    }

    public function exist(string $in)
    {
        $offsets = $this->calcOffsets($in);
        foreach ($offsets as $offset) {
            if (!$this->redis->getbit($this->bucket, $offset)) {
                return false;
            }
        }
        return true;
    }

    private function calcOffsets(string $in)
    {
        return [
            $this->BKDRHash($in) % $this->bitMapSize,
            $this->JSHash($in) % $this->bitMapSize,
            $this->SDBMHash($in) % $this->bitMapSize,
        ];
    }

    /**
     * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
     * 它是一个简单的哈希函数，使用一组奇怪的可能种子，它们都构成了31 .... 31 ... 31等模式，它似乎与DJB哈希函数非常相似。
     * @param $in
     * @param null $len
     * @return int
     */
    private function BKDRHash($in, $len = null)
    {
        $seed = 131; # 31 131 1313 13131 131313 etc..
        $hash = 0;
        $len || $len = strlen($in);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (($hash * $seed) + ord($in[$i]));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 由Justin Sobel编写的按位散列函数
     * @param $in
     * @param null $len
     * @return int
     */
    private function JSHash($in, $len = null)
    {
        $hash = 1315423911;
        $len || $len = strlen($in);
        for ($i=0; $i<$len; $i++) {
            $hash ^= (($hash << 5) + ord($in[$i]) + ($hash >> 2));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这是在开源SDBM项目中使用的首选算法。
     * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。
     * @param $in
     * @param null $len
     * @return int
     */
    private function SDBMHash($in, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($in);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (ord($in[$i]) + ($hash << 6) + ($hash << 16) - $hash);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }
}

误判率测试代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public function testMissRate()
{
    /** @var RandomStringGenerator $randomStringGenerator */
    $randomStringGenerator = \Yii::$container->get(RandomStringGenerator::class);
    $max = 1000000;
    $strings = [];
    for ($i = 0; $i < $max; $i++) {
        $strings[] = $randomStringGenerator->generate(10);
    }

    $this->model->reset(1024, $strings);

    $misjudgmentNum = 0;
    $n = 0;
    foreach ($strings as $in) {
        $n++;
        $_in = $in . $randomStringGenerator->generate(3);
        if ($this->model->exist($_in)) {
            $misjudgmentNum++;
        }
        if ($n >= 10000) {
            break;
        }
    }
    $rate = $misjudgmentNum / $n;
    expect($rate)->lessThan(0.05);
}
© 2016 - 2024 人生如戏
Built with Hugo
主题 Stack 由 Jimmy 设计