Redis布隆過(guò)濾器分析與總結(jié)
問(wèn)題引入
問(wèn)題一:原本有10億個(gè)號(hào)碼，現(xiàn)在又來(lái)了10萬(wàn)個(gè)號(hào)碼，要快速準(zhǔn)確判斷這10萬(wàn)個(gè)號(hào)碼是否在10億個(gè)號(hào)碼庫(kù)中？
問(wèn)題二:接觸過(guò)爬蟲(chóng)的，應(yīng)該有這么一個(gè)需求，需要爬蟲(chóng)的網(wǎng)站千千萬(wàn)萬(wàn)，對(duì)于一個(gè)新的網(wǎng)站url，我們?nèi)绾闻袛噙@個(gè)url我們是否已經(jīng)爬過(guò)了？
問(wèn)題三:一個(gè)郵件系統(tǒng)，有上億的郵件數(shù)量，我們要檢測(cè)某一個(gè)郵箱是否正確發(fā)送了郵件信息？
問(wèn)題四:提到Redis做緩存查詢，我們需要考慮幾個(gè)問(wèn)題，緩存穿透、緩存擊穿和緩存雪崩。我們?cè)撊绾谓鉀Q緩存這種緩存問(wèn)題呢？
布隆過(guò)濾
布隆過(guò)濾器其實(shí)就是，一種數(shù)據(jù)結(jié)構(gòu)，是由一串很長(zhǎng)的二進(jìn)制向量組成，可以將其看成一個(gè)二進(jìn)制數(shù)組。既然是二進(jìn)制，那么里面存放的不是0，就是1，但是初始默認(rèn)值都是0。
大致的數(shù)據(jù)結(jié)構(gòu)如下圖:
添加數(shù)據(jù):
向布隆過(guò)濾器中添加 key 時(shí)，會(huì)使用多個(gè) hash 函數(shù)對(duì) key 進(jìn)行 hash 算得一個(gè)整數(shù)索引值然后對(duì)位數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算得到一個(gè)位置，每個(gè) hash 函數(shù)都會(huì)算得一個(gè)不同的位置。再把位數(shù)組的這幾個(gè)位置都置為 1 就完成了 add 操作。
獲取數(shù)據(jù)時(shí):
只需要將這個(gè)新的數(shù)據(jù)通過(guò)上面自定義的幾個(gè)哈希函數(shù)，分別算出各個(gè)值，然后看其對(duì)應(yīng)的地方是否都是1，如果存在一個(gè)不是1的情況，那么我們可以說(shuō)，該新數(shù)據(jù)一定不存在于這個(gè)布隆過(guò)濾器中。
Redis配置
在Redis中要使用布隆過(guò)濾器，可以直接參照該文檔,文檔地址
推薦使用docker使用方式，如果要編譯成so動(dòng)態(tài)庫(kù)，則需要運(yùn)行在Linux環(huán)境中。
// 安裝
docker run -p 6377:6379 --name redis-redisbloom redislabs/rebloom:latest
安裝完之后，查看docker容器。
進(jìn)入Redis容器，并查看容器模塊狀態(tài)。
# 進(jìn)入容器
docker exec -it 4a695ead6577 /bin/sh
# 登錄到Redis
redis-cli
# 查看Redis模塊
127.0.0.1:6379> info Modules
# Modules
module:name=bf,ver=20205,api=1,filters=0,usedby=[],using=[],options=[]
操作演示
添加數(shù)據(jù)
// 單個(gè)添加
127.0.0.1:6379> bf.add blkey 1
(integer) 1
127.0.0.1:6379> bf.add blkey 2
(integer) 1
127.0.0.1:6379> bf.add blkey 2
(integer) 0
127.0.0.1:6379> bf.add blkey 3
(integer) 1
127.0.0.1:6379> bf.add blkey 4
(integer) 1
// 批量添加
127.0.0.1:6379> bf.madd blkey 5 6 7 8 4
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 0
通過(guò)添加會(huì)發(fā)現(xiàn)，如果元素已經(jīng)存在，則返回的是0值。
檢測(cè)數(shù)據(jù)
// 檢測(cè)單個(gè)值
127.0.0.1:6379> bf.exists blkey 1
(integer) 1
127.0.0.1:6379> bf.exists blkey 2
(integer) 1
127.0.0.1:6379> bf.exists blkey 3
(integer) 1
// 批量檢測(cè)
127.0.0.1:6379> bf.mexists blkey 1 2 3 4 5 10
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
6) (integer) 0
通過(guò)演示會(huì)發(fā)現(xiàn)，如果元素不存在，則返回的是0值。
代碼演示
這里用composer來(lái)對(duì)Redis布隆過(guò)濾器進(jìn)行操作。官方也羅列了幾種編程語(yǔ)言的客戶端。
文檔地址
composer require palicao/php-rebloom
<?php
declare(strict_types=1);
namespace App\Http\Controllers\Redis;
use Illuminate\Http\Request;
use Palicao\PhpRebloom\BloomFilter;
use Palicao\PhpRebloom\RedisClient;
use Palicao\PhpRebloom\RedisConnectionParams;
use Redis;
/**
* Redis布隆過(guò)濾器
* Class BloomFilterController
* @package App\Http\Controllers\Redis
*/
class BloomFilterController
{
private $request;
private $host = '192.168.0.112';
private $port = 6377;
private $bloomFilter;
public function __construct(Request $request)
{
$this->request = $request->all();
$this->bloomFilter = new BloomFilter(
new RedisClient(
new Redis(),
new RedisConnectionParams($this->host, $this->port)
)
);
}
/**
* 添加刪除數(shù)據(jù)
* @throws \RedisException
* @author kert
*/
public function index()
{
// 文章:https://www.cnblogs.com/ysocean/p/12594982.html
/** @var string $cacheKey 緩存key */
$cacheKey = 'bloom';
/** @var int $cacheValue 緩存value */
$cacheValue = mt_rand(0, 100);
// 單個(gè)添加緩存
var_dump('插入緩存', $this->bloomFilter->insert((string)$cacheKey, (string)$cacheValue));
// 單個(gè)查詢緩存
var_dump('驗(yàn)證緩存', $this->bloomFilter->exists((string)$cacheKey, (string)$cacheValue));
/** @var array $batchCacheValue 批量緩存value */
$batchCacheValue = [mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100)];
// 批量添加緩存
var_dump('批量插入緩存', $this->bloomFilter->insertMany((string)$cacheKey, $batchCacheValue));
// 批量獲取緩存
var_dump('批量驗(yàn)證緩存', $this->bloomFilter->manyExist((string)$cacheKey, $batchCacheValue));
}
}
內(nèi)存對(duì)比
這里我們通過(guò)模擬郵件發(fā)送來(lái)對(duì)比布隆過(guò)濾器和集合各自占用的內(nèi)存對(duì)比。
布隆過(guò)濾器
public function email()
{
/** @var string $cacheKey 緩存key */
$cacheKey = 'bloom:email';
/** @var array $email 緩存郵箱數(shù)據(jù) */
$emailArray = [];
for ($i = 0; $i < 1000; $i++) {
array_push($emailArray, $i . '[email protected]');
}
/** @var array $insertResult 插入結(jié)果 */
$insertResult = $this->bloomFilter->insertMany((string)$cacheKey, $emailArray);
foreach ($insertResult as $value) {
if ($value === false) {
echo '插入失敗' . PHP_EOL;
}
}
/** @var array $queryResult 查詢結(jié)果 */
$queryResult = $this->bloomFilter->manyExist((string)$cacheKey, $emailArray);
foreach ($queryResult as $value) {
if ($value === false) {
echo '查詢失敗' . PHP_EOL;
}
}
}
集合
public function emailSet()
{
/** @var string $cacheKey 緩存key */
$cacheKey = 'set:email';
/** @var array $email 緩存郵箱數(shù)據(jù) */
$emailArray = [];
for ($i = 0; $i < 1000; $i++) {
array_push($emailArray, $i . '[email protected]');
}
$redis = new Redis();
$redis->connect($this->host, $this->port);
var_dump($redis->sAddArray($cacheKey, $emailArray));
}
內(nèi)存對(duì)比
/**
* 初始內(nèi)存:854.40K
* 布隆過(guò)濾器:857.50K ~3k
* 集合:912.52K ~55k
*/
通過(guò)對(duì)比發(fā)現(xiàn)，同樣的郵箱數(shù)量，使用set的方式比使用過(guò)濾器的方式，內(nèi)存至少多使用18倍多。
案例解決
在文章開(kāi)頭，我們引入了幾個(gè)問(wèn)題？首先我們想到的第一個(gè)技術(shù)方案就是通過(guò)數(shù)據(jù)庫(kù)查詢。這樣數(shù)據(jù)更加準(zhǔn)確。但是我們需要考慮一個(gè)問(wèn)題，如果數(shù)據(jù)量很大，沒(méi)查詢一次都走數(shù)據(jù)庫(kù)，無(wú)疑是給數(shù)據(jù)庫(kù)增加了負(fù)擔(dān)。
如果我們通過(guò)布隆過(guò)濾器來(lái)實(shí)現(xiàn)，既能解決我們實(shí)際的需求，也能解決數(shù)據(jù)庫(kù)壓力過(guò)重的情況。
下面演示代碼實(shí)現(xiàn)邏輯。
/**
* 檢測(cè)某一個(gè)手機(jī)號(hào)是否已經(jīng)發(fā)送短信內(nèi)容
* @author kert
*/
public function filterMobile()
{
/** @var string $cacheKey 緩存key */
$cacheKey = 'bloom:mobile';
/** @var array $email 緩存手機(jī)號(hào)數(shù)據(jù)(模擬發(fā)送過(guò)的手機(jī)號(hào)) */
$mobileArray = [];
for ($i = 0; $i < 1000; $i++) {
array_push($mobileArray, substr(md5((string)$i), 0, 11));
}
// 插入布隆過(guò)濾器
$this->bloomFilter->insertMany((string)$cacheKey, $mobileArray);
// 檢測(cè)某一個(gè)值是否存在
var_dump($this->bloomFilter->exists((string)$cacheKey, (string)substr(md5((string)100), 0, 11)));
// output bool(true)
}
通過(guò)上面的演示，我們不難看出，布隆過(guò)濾在對(duì)數(shù)據(jù)檢測(cè)是否存在的情況，要比走數(shù)據(jù)庫(kù)好很多。
優(yōu)缺點(diǎn)分析
通過(guò)上面內(nèi)存對(duì)比的內(nèi)容，以及對(duì)布隆過(guò)濾器實(shí)現(xiàn)原理、存儲(chǔ)數(shù)據(jù)格式的了解，我們可以得出布隆過(guò)濾器可以節(jié)省內(nèi)存，尤其是數(shù)據(jù)大的情況下。
布隆過(guò)濾器是不支持刪除數(shù)據(jù)的，如果需要?jiǎng)h除數(shù)據(jù)則需要重建緩存信息。
布隆過(guò)濾器使用多次hash計(jì)算，也會(huì)存在hash沖突情況。這就會(huì)導(dǎo)致一個(gè)問(wèn)題，當(dāng)檢測(cè)過(guò)濾器是否存在數(shù)據(jù)時(shí)，檢測(cè)到存在，實(shí)際不一定存在。同時(shí)檢測(cè)到不存在，則緩存中一定不存在。
總結(jié)
布隆過(guò)濾器節(jié)省內(nèi)存，但是也存在一種誤差。對(duì)于開(kāi)篇提到的幾個(gè)案例場(chǎng)景是一種非常不錯(cuò)的選擇。
推薦閱讀
Redis實(shí)現(xiàn)列表數(shù)據(jù)查詢?cè)O(shè)計(jì)