使用 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)來進(jìn)行估數(shù)惹挟，它非常有價值拱礁，可以解決很多精確度不高的統(tǒng)計需求。
但是如果我們想知道某一個值是不是已經(jīng)在 HyperLogLog 結(jié)構(gòu)里面了，它就無能為力了微王，它只提供了 pfadd 和 pfcount 方法蔼夜，沒有提供 pfcontains 這種方法兼耀。
講個使用場景，比如我們在使用新聞客戶端看新聞時求冷，它會給我們不停地推薦新的內(nèi)容瘤运，它每次推薦時要去重，去掉那些已經(jīng)看過的內(nèi)容匠题。問題來了拯坟，新聞客戶端推薦系統(tǒng)如何實現(xiàn)推送去重的？
你會想到服務(wù)器記錄了用戶看過的所有歷史記錄韭山，當(dāng)推薦系統(tǒng)推薦新聞時會從每個用戶的歷史記錄里進(jìn)行篩選郁季，過濾掉那些已經(jīng)存在的記錄冷溃。問題是當(dāng)用戶量很大，每個用戶看過的新聞又很多的情況下梦裂，這種方式似枕，推薦系統(tǒng)的去重工作在性能上跟的上么？
實際上年柠，如果歷史記錄存儲在關(guān)系數(shù)據(jù)庫里凿歼，去重就需要頻繁地對數(shù)據(jù)庫進(jìn)行 exists 查詢，當(dāng)系統(tǒng)并發(fā)量很高時冗恨，數(shù)據(jù)庫是很難扛住壓力的答憔。
你可能又想到了緩存，但是如此多的歷史記錄全部緩存起來掀抹，那得浪費(fèi)多大存儲空間芭巴亍？而且這個存儲空間是隨著時間線性增長渴丸，你撐得住一個月侯嘀，你能撐得住幾年么？但是不緩存的話谱轨，性能又跟不上戒幔，這該怎么辦？
這時土童，布隆過濾器 (Bloom Filter) 閃亮登場了诗茎，它就是專門用來解決這種去重問題的。它在起到去重的同時献汗，在空間上還能節(jié)省 90% 以上敢订，只是稍微有那么點不精確，也就是有一定的誤判概率罢吃。
布隆過濾器
布隆過濾器可以理解為一個不怎么精確的 set 結(jié)構(gòu)楚午，當(dāng)你使用它的 contains 方法判斷某個對象是否存在時，它可能會誤判尿招。但是布隆過濾器也不是特別不精確矾柜，只要參數(shù)設(shè)置的合理，它的精確度可以控制的相對足夠精確就谜，只會有小小的誤判概率怪蔑。
當(dāng)布隆過濾器說某個值存在時，這個值可能不存在丧荐；當(dāng)它說不存在時缆瓣，那就肯定不存在。打個比方虹统，當(dāng)它說不認(rèn)識你時弓坞，肯定就不認(rèn)識隧甚；當(dāng)它說見過你時，可能根本就沒見過面昼丑，不過因為你的臉跟它認(rèn)識的人中某臉比較相似 (某些熟臉的系數(shù)組合)呻逆，所以誤判以前見過你。
Redis 中的布隆過濾器
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強(qiáng)大的布隆去重功能硬鞍。
下面我們來體驗一下 Redis 4.0 的布隆過濾器化戳，為了省去繁瑣安裝過程，我們直接用 Docker 吧切平。
> docker pull redislabs/rebloom # 拉取鏡像
> docker run -p6379:6379 redislabs/rebloom # 運(yùn)行容器
> redis-cli # 連接容器中的 redis 服務(wù)
布隆過濾器基本使用
布隆過濾器有二個基本指令握础，bf.add 添加元素，bf.exists 查詢元素是否存在悴品，它的用法和 set 集合的 sadd 和 sismember 差不多禀综。注意 bf.add 只能一次添加一個元素，如果想要一次添加多個苔严，就需要用到 bf.madd 指令定枷。同樣如果需要一次查詢多個元素是否存在，就需要用到 bf.mexists 指令届氢。
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
Java 客戶端 Jedis-2.x 沒有提供指令擴(kuò)展機(jī)制欠窒，所以你無法直接使用 Jedis 來訪問 Redis Module 提供的 bf.xxx 指令。RedisLabs 提供了一個單獨(dú)的包 JReBloom退子，但是它是基于 Jedis-3.0岖妄，Jedis-3.0 這個包目前還沒有進(jìn)入 release，沒有進(jìn)入 maven 的中央倉庫寂祥，需要在 Github 上下載荐虐。在使用上很不方便，如果怕麻煩丸凭，還可以使用 lettuce福扬，它是另一個 Redis 的客戶端，相比 Jedis 而言贮乳，它很早就支持了指令擴(kuò)展忧换。
public class BloomTest {
public static void main(String[] args) {
Client client = new Client();
client.delete("codehole");
for (int i = 0; i < 100000; i++) {
client.add("codehole", "user" + i);
boolean ret = client.exists("codehole", "user" + i);
if (!ret) {
System.out.println(i);
break;
}
}
client.close();
}
}
執(zhí)行上面的代碼后，你會張大了嘴巴發(fā)現(xiàn)居然沒有輸出向拆，塞進(jìn)去了 100000 個元素亚茬，還是沒有誤判，這是怎么回事浓恳？如果你不死心的話刹缝，可以將數(shù)字再加一個 0 試試碗暗，你會發(fā)現(xiàn)依然沒有誤判。
原因就在于布隆過濾器對于已經(jīng)見過的元素肯定不會誤判梢夯，它只會誤判那些沒見過的元素言疗。所以我們要稍微改一下上面的腳本，使用 bf.exists 去查找沒見過的元素颂砸，看看它是不是以為自己見過了噪奄。
public class BloomTest {
public static void main(String[] args) {
Client client = new Client();
client.delete("codehole");
for (int i = 0; i < 100000; i++) {
client.add("codehole", "user" + i);
boolean ret = client.exists("codehole", "user" + (i + 1));
if (ret) {
System.out.println(i);
break;
}
}
client.close();
}
}
運(yùn)行后，我們看到了輸出是 214人乓，也就是到第 214 的時候勤篮，它出現(xiàn)了誤判。
那如何來測量誤判率呢色罚？我們先隨機(jī)出一堆字符串碰缔，然后切分為 2 組，將其中一組塞入布隆過濾器戳护，然后再判斷另外一組的字符串存在與否金抡，取誤判的個數(shù)和字符串總量一半的百分比作為誤判率。
public class BloomTest {
private String chars;
{
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26; i++) {
builder.append((char) ('a' + i));
}
chars = builder.toString();
}
private String randomString(int n) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < n; i++) {
int idx = ThreadLocalRandom.current().nextInt(chars.length());
builder.append(chars.charAt(idx));
}
return builder.toString();
}
private List<String> randomUsers(int n) {
List<String> users = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
users.add(randomString(64));
}
return users;
}
public static void main(String[] args) {
BloomTest bloomer = new BloomTest();
List<String> users = bloomer.randomUsers(100000);
List<String> usersTrain = users.subList(0, users.size() / 2);
List<String> usersTest = users.subList(users.size() / 2, users.size());
Client client = new Client();
client.delete("codehole");
for (String user : usersTrain) {
client.add("codehole", user);
}
int falses = 0;
for (String user : usersTest) {
boolean ret = client.exists("codehole", user);
if (ret) {
falses++;
}
}
System.out.printf("%d %d\n", falses, usersTest.size());
client.close();
}
}
運(yùn)行一下腌且，等待大約一分鐘梗肝，輸出:
total users 100000
all trained
628 50000
可以看到誤判率大約 1% 多點。你也許會問這個誤判率還是有點高啊切蟋，有沒有辦法降低一點统捶？答案是有的。
我們上面使用的布隆過濾器只是默認(rèn)參數(shù)的布隆過濾器柄粹，它在我們第一次 add 的時候自動創(chuàng)建喘鸟。Redis 其實還提供了自定義參數(shù)的布隆過濾器，需要我們在 add 之前使用bf.reserve指令顯式創(chuàng)建驻右。如果對應(yīng)的 key 已經(jīng)存在什黑，bf.reserve會報錯。bf.reserve有三個參數(shù)堪夭，分別是 key, error_rate和initial_size愕把。錯誤率越低，需要的空間越大森爽。initial_size參數(shù)表示預(yù)計放入的元素數(shù)量恨豁，當(dāng)實際數(shù)量超出這個數(shù)值時，誤判率會上升爬迟。
所以需要提前設(shè)置一個較大的數(shù)值避免超出導(dǎo)致誤判率升高橘蜜。如果不使用 bf.reserve，默認(rèn)的error_rate是 0.01，默認(rèn)的initial_size是 100计福。
接下來我們使用 bf.reserve 改造一下上面的腳本：
public class BloomTest {
private String chars;
{
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26; i++) {
builder.append((char) ('a' + i));
}
chars = builder.toString();
}
private String randomString(int n) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < n; i++) {
int idx = ThreadLocalRandom.current().nextInt(chars.length());
builder.append(chars.charAt(idx));
}
return builder.toString();
}
private List<String> randomUsers(int n) {
List<String> users = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
users.add(randomString(64));
}
return users;
}
public static void main(String[] args) {
BloomTest bloomer = new BloomTest();
List<String> users = bloomer.randomUsers(100000);
List<String> usersTrain = users.subList(0, users.size() / 2);
List<String> usersTest = users.subList(users.size() / 2, users.size());
Client client = new Client();
client.delete("codehole");
// 對應(yīng) bf.reserve 指令
client.createFilter("codehole", 50000, 0.001);
for (String user : usersTrain) {
client.add("codehole", user);
}
int falses = 0;
for (String user : usersTest) {
boolean ret = client.exists("codehole", user);
if (ret) {
falses++;
}
}
System.out.printf("%d %d\n", falses, usersTest.size());
client.close();
}
}
運(yùn)行一下跌捆，等待約 1 分鐘，輸出如下：
total users 100000
all trained
6 50000
我們看到了誤判率大約 0.012%象颖，比預(yù)計的 0.1% 低很多佩厚，不過布隆的概率是有誤差的，只要不比預(yù)計誤判率高太多说订，都是正吵撸現(xiàn)象。
注意事項
布隆過濾器的initial_size估計的過大陶冷，會浪費(fèi)存儲空間闺鲸，估計的過小，就會影響準(zhǔn)確率埃叭，用戶在使用之前一定要盡可能地精確估計好元素數(shù)量，還需要加上一定的冗余空間以避免實際元素可能會意外高出估計值很多悉罕。
布隆過濾器的error_rate越小赤屋，需要的存儲空間就越大，對于不需要過于精確的場合壁袄，error_rate設(shè)置稍大一點也無傷大雅类早。比如在新聞去重上而言，誤判率高一點只會讓小部分文章不能讓合適的人看到嗜逻，文章的整體閱讀量不會因為這點誤判率就帶來巨大的改變涩僻。
布隆過濾器的原理
學(xué)會了布隆過濾器的使用，下面有必要把原理解釋一下栈顷，不然讀者還會繼續(xù)蒙在鼓里
每個布隆過濾器對應(yīng)到 Redis 的數(shù)據(jù)結(jié)構(gòu)里面就是一個大型的位數(shù)組和幾個不一樣的無偏 hash 函數(shù)逆日。所謂無偏就是能夠把元素的 hash 值算得比較均勻。
向布隆過濾器中添加 key 時萄凤，會使用多個 hash 函數(shù)對 key 進(jìn)行 hash 算得一個整數(shù)索引值然后對位數(shù)組長度進(jìn)行取模運(yùn)算得到一個位置室抽，每個 hash 函數(shù)都會算得一個不同的位置。再把位數(shù)組的這幾個位置都置為 1 就完成了 add 操作靡努。
向布隆過濾器詢問 key 是否存在時坪圾，跟 add 一樣，也會把 hash 的幾個位置都算出來惑朦，看看位數(shù)組中這幾個位置是否都為 1兽泄，只要有一個位為 0，那么說明布隆過濾器中這個 key 不存在漾月。如果都是 1病梢，這并不能說明這個 key 就一定存在，只是極有可能存在栅屏，因為這些位被置為 1 可能是因為其它的 key 存在所致飘千。如果這個位數(shù)組比較稀疏堂鲜，判斷正確的概率就會很大，如果這個位數(shù)組比較擁擠护奈，判斷正確的概率就會降低缔莲。具體的概率計算公式比較復(fù)雜，感興趣可以閱讀擴(kuò)展閱讀霉旗，非常燒腦痴奏，不建議讀者細(xì)看。
使用時不要讓實際元素遠(yuǎn)大于初始化大小厌秒，當(dāng)實際元素開始超出初始化大小時读拆，應(yīng)該對布隆過濾器進(jìn)行重建，重新分配一個 size 更大的過濾器鸵闪，再將所有的歷史元素批量 add 進(jìn)去 (這就要求我們在其它的存儲器中記錄所有的歷史元素)檐晕。因為 error_rate 不會因為數(shù)量超出就急劇增加，這就給我們重建過濾器提供了較為寬松的時間蚌讼。
布隆過濾器的其它應(yīng)用
在爬蟲系統(tǒng)中辟灰，我們需要對 URL 進(jìn)行去重，已經(jīng)爬過的網(wǎng)頁就可以不用爬了篡石。但是 URL 太多了芥喇，幾千萬幾個億，如果用一個集合裝下這些 URL 地址那是非常浪費(fèi)空間的凰萨。這時候就可以考慮使用布隆過濾器继控。它可以大幅降低去重存儲消耗，只不過也會使得爬蟲系統(tǒng)錯過少量的頁面胖眷。
布隆過濾器在 NoSQL 數(shù)據(jù)庫領(lǐng)域使用非常廣泛武通，我們平時用到的 HBase、Cassandra 還有 LevelDB瘦材、RocksDB 內(nèi)部都有布隆過濾器結(jié)構(gòu)厅须，布隆過濾器可以顯著降低數(shù)據(jù)庫的 IO 請求數(shù)量。當(dāng)用戶來查詢某個 row 時食棕，可以先通過內(nèi)存中的布隆過濾器過濾掉大量不存在的 row 請求朗和，然后再去磁盤進(jìn)行查詢。
郵箱系統(tǒng)的垃圾郵件過濾功能也普遍用到了布隆過濾器簿晓，因為用了這個過濾器眶拉，所以平時也會遇到某些正常的郵件被放進(jìn)了垃圾郵件目錄中，這個就是誤判所致憔儿，概率很低忆植。
