README

布隆过滤器是一种空间高效的概率数据结构，由Burton Howard Bloom于1970年提出，用于测试一个元素是否是某个集合的成员。可能存在误报，但不会存在漏报——换句话说，查询结果要么是“可能在集合中”，要么是“肯定不在集合中”。元素可以添加到集合中，但不能从中删除（尽管可以使用“计数”过滤器来解决这个问题）；添加到集合中的元素越多，误报的概率就越大。

阅读维基百科上的完整文章。

安装

composer require denismitr/laravel-bloom

最新版本 - 0.3

配置

php artisan vendor:publish --provider="Denismitr\Bloom\BloomServiceProvider" --tag="config"

Bloom过滤器配置文件：bloom.php

return [
    'default' => [
        'size' => 100000000,
        'num_hashes' => 5,
        'persistence' => [
            'driver' => 'redis',
            'connection' => 'default'
        ],
        'hashing_algorithm' => 'md5',
    ],

    'keys' => [
         // keys specific params
         // example
//        'user_recommendations' => [
//            'size' => 5500000,
//            'num_hashes' => 10,
//            'persistence' => [
//                'driver' => 'redis',
//                'connection' => 'default'
//            ],
//            'hashing_algorithm' => 'md5',
//        ]
    ],
];

此Bloom过滤器实现的MAX_CAPACITY目前为4294967296。

default部分适用于所有密钥，除非在keys部分中指定了专用配置。

• size - 是Bloom过滤器存储的大小，推荐大小为10M-100M位
• num_hashes - 是应用于每个放入Bloom过滤器的项的哈希函数的数量
• persistance - 是包含持久性配置的数组——driver和connection
  • driver - 目前只支持redis
  • connection - 对于Redis连接，在标准Laravel设置中，在database.php配置文件的redis部分指定。
• hashing_algorithm - 自解释，目前支持md5和murmur哈希算法。

用法

您可以使用外观——Denismitr\Bloom\Facades\Bloom或直接注入Denismitr\Bloom\BloomManager作为依赖项，它将由Laravel解析。

依赖注入的默认配置

public function someAction(Denismitr\Bloom\BloomManager $bloomManager)
{
    $bloomFilter = $bloomManager->key('foo');
    
    $bloomFilter->add('baz');
    ...
    $bloomFilter->test('baz'); // true
    ...
    $bloomFilter->clear(); // clear bloom filter under 'foo' key
}

外观的默认配置

Bloom::key("shown-banners")->add($banner->id);
...
Bloom::key("shown-banners")->test($banner->id);
// true
Bloom::key("shown-banners")->test($unseenBanner->id);
// false, but can be true sometimes (a false positive)

// reset bloom filter for given key
Bloom::key('shown-banners')->reset();

特定密钥的配置

在bloom.php中找到keys部分，并为您想要使用除default之外参数的key添加配置。

'keys' => [
    'seen-banners' => [
        'size' => 5550000,
        'num_hashes' => 3,
        'persistence' => [
            'driver' => 'redis',
            'connection' => 'default'
        ],
        'hashing_algorithm' => 'md5',
    ]    
]

现在当您使用该密钥的Bloom过滤器时，它将使用该配置。Bloom::key('seen-banners')>add($bammer->id)

密钥后缀

为了方便起见，有一个简单的方法可以生成特定于用户的密钥，只需在调用key方法时将用户ID作为第二个参数传递，如下所示

Bloom::key('user-recommendation', $user->id)->add($recommendation->id);

或者

$bloomFilter = Bloom::key('user-recommendation', $user->id);

$bloomFilter->add($recommendation->id);

$bloomFilter->test($recommendation->id); // true

// to clear that key do
$bloomFilter->clear();

测试

• 测试覆盖率 > 90%

composer test

目前您需要在您的机器上设置实际的Redis。