背景介紹

  布隆過濾器可以幫助我們解決Redis緩存雪崩的問題，那什么是布隆過濾器、布隆過濾器又是如何使用如何解決緩存雪崩的問題的，讓我們帶著這一系列的問題去詳細(xì)了解布隆過濾器。

概念說(shuō)明

  布隆過濾器是一種用于快速判斷一個(gè)元素是否屬于一個(gè)集合的數(shù)據(jù)結(jié)構(gòu)。它通常用于大規(guī)模數(shù)據(jù)集合中，可以快速判斷一個(gè)元素是否可能存在于集合中，但不能確定一定存在。布隆過濾器的主要優(yōu)點(diǎn)是占用內(nèi)存少、查詢速度快，并且可以容忍一定的誤判率。

Redis 布隆過濾器的原理和實(shí)踐

一、簡(jiǎn)介

1 布隆過濾器的定義

布隆過濾器是一種空間效率高、誤判率可控的數(shù)據(jù)結(jié)構(gòu)，通常用于檢索一個(gè)元素是否在一個(gè)集合中。它是由一個(gè)比特向量和多個(gè)哈希函數(shù)組成的。布隆過濾器可以用于快速檢測(cè)一個(gè)元素是否存在于一個(gè)集合中，其主要優(yōu)點(diǎn)是省內(nèi)存缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

2 Redis 布隆過濾器的特點(diǎn)

• Redis 布隆過濾器采用了 Redis 自身的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，支持?jǐn)?shù)據(jù)持久化，重啟后依然有效
• 在 Redis 中使用布隆過濾器需要先安裝 RedisBloom 模塊
• Redis 布隆過濾器使用多個(gè)哈希函數(shù)，并使用不同的隨機(jī)種子在一定程度上降低了誤判率
• Redis 布隆過濾器可以設(shè)置錯(cuò)誤率和元素?cái)?shù)量通過調(diào)整這些參數(shù)可以控制誤判率

3 Redis 布隆過濾器的應(yīng)用場(chǎng)景

• 郵箱黑名單、敏感詞過濾
• 在搜索引擎中過濾掉爬蟲或者惡意軟件等
• 在數(shù)據(jù)庫(kù)中避免重復(fù)插入相同數(shù)據(jù)
• 在網(wǎng)站訪問中，可以使用布隆過濾器緩存那些已經(jīng)訪問過的頁(yè)面

二、原理分析

1 布隆過濾器的基本原理

假設(shè)哈希函數(shù)個(gè)數(shù)為 k 每個(gè)比特位被設(shè)置多少次記為 m，n 為元素?cái)?shù)量，則誤判率為 (1 - e(-kn/m))^k。當(dāng)誤判率為 p 時(shí)選取最優(yōu)的哈希函數(shù)個(gè)數(shù) k 和比特位長(zhǎng)度 m 可以使空間利用更加高效

代碼示例

public class BloomFilter {
    private int size;
    private int[] hashes;
    private BitSet bits;
    public BloomFilter(int size, int[] hashes) {
        this.size = size;
        this.hashes = hashes;
        this.bits = new BitSet(size);
    }
    public void add(String value) {
        for (int hash : hashes) {
            int position = Math.abs(value.hashCode() * hash) % size;
            bits.set(position, true);
        }
    }
    public boolean contains(String value) {
        for (int hash : hashes) {
            int position = Math.abs(value.hashCode() * hash) % size;
            if (!bits.get(position)) {
                return false;
            }
        }
        return true;
    }
}

2 布隆過濾器的實(shí)現(xiàn)原理

• 創(chuàng)建 Redis 布隆過濾器時(shí)需要指定誤判率和預(yù)期元素?cái)?shù)量，Redis 客戶端會(huì)根據(jù)這些參數(shù)計(jì)算出最優(yōu)的比特位長(zhǎng)度 m 和哈希函數(shù)個(gè)數(shù) k。
• Redis 使用 MurmurHash2 和 MurmurHash64A 兩個(gè)哈希函數(shù)計(jì)算各自的哈希值，來(lái)保證布隆過濾器的誤判率和運(yùn)行效率。
• 將插入元素在 k 個(gè)哈希函數(shù)中生成對(duì)應(yīng)的 k 個(gè)哈希值，并將比特向量的這些位置置為 1。
• 查找元素是同樣地使用 k 個(gè)哈希函數(shù)計(jì)算出 k 個(gè)哈希值，在比特向量的對(duì)應(yīng)位置查找是否都為 1。

代碼示例

Jedis jedis = new Jedis("localhost", 6379);
jedis.getClient().sendCommand(BloomFilterCommands.RESERVE, "mybloom", "0.001", "100000");
jedis.getClient().sendCommand(BloomFilterCommands.ADD, "mybloom", "hello");
Response<Boolean> response = jedis.getClient().getBooleanReply();
response.get();
jedis.getClient().sendCommand(BloomFilterCommands.EXISTS, "mybloom", "hello");
Response<Boolean> response = jedis.getClient().getBooleanReply();
response.get();

3 布隆過濾器的優(yōu)化策略

• 增加哈希函數(shù)的數(shù)量可以降低誤判率，但同時(shí)也會(huì)增加空間復(fù)雜度和計(jì)算時(shí)間
• 確定適當(dāng)?shù)念A(yù)期元素?cái)?shù)量和誤判率，避免過擬合和欠擬合
• 在 Redis 集群中，布隆過濾器可以通過將多個(gè)小的布隆過濾器組成一個(gè)大的布隆過濾器來(lái)協(xié)同工作，提高并發(fā)處理能力和存儲(chǔ)效率

三、Redis 布隆過濾器的實(shí)踐

1 布隆過濾器的安裝和配置

Redis 布隆過濾器需要在 Redis 中進(jìn)行安裝和配置才能夠使用。首先需要在 Redis 安裝目錄下的 src 文件夾中找到 redis-trib.rb 文件。

# 進(jìn)入 Redis 安裝目錄
cd xxx/redis-xx
# 執(zhí)行以下命令安裝 Redis 布隆過濾器
ruby src/redis-trib.rb create --replicas 1 ip:port ip:port ip:port ...

在上述命令中ip:port 需要替換為 Redis 節(jié)點(diǎn)的 IP 地址和端口號(hào)

2 布隆過濾器的使用方法

Redis 布隆過濾器常用于判斷某個(gè)元素是否在集合中可以通過以下命令進(jìn)行使用：

# 向布隆過濾器添加元素
BF.ADD key element [element ...]
# 判斷元素是否在布隆過濾器中
BF.EXISTS key element

其中，key 表示 Redis 的鍵名，element 表示需要添加或判斷的元素。

3 布隆過濾器的性能測(cè)試和優(yōu)化

Redis 布隆過濾器可以通過以下命令來(lái)進(jìn)行性能測(cè)試：

# 測(cè)試添加元素的速度
BF.RESERVE key 0.0001 10000
# 測(cè)試判斷元素是否在布隆過濾器中的速度
BF.EXISTS key element

需要注意的是在 BF.RESERVE 命令中，第一個(gè)參數(shù) key 代表 Redis 的鍵名，第二個(gè)參數(shù)為錯(cuò)誤率即誤報(bào)的概率，第三個(gè)參數(shù)代表預(yù)期最大元素個(gè)數(shù)。

如果發(fā)現(xiàn) Redis 布隆過濾器性能較低，可以通過增加節(jié)點(diǎn)個(gè)數(shù)或降低錯(cuò)誤率等方式進(jìn)行優(yōu)化。

四、Redis 布隆過濾器的應(yīng)用案例

1 布隆過濾器在網(wǎng)站防刷中的應(yīng)用

Redis 布隆過濾器可以用于網(wǎng)站的防刷功能，通過判斷IP地址或者用戶行為是否已經(jīng)超出一定的次數(shù)來(lái)避免短時(shí)間內(nèi)多次請(qǐng)求相同的資源。例如：

# 判斷 IP 地址是否已經(jīng)被封禁
if BF.EXISTS ip_bloom_filter ip {
    return 403; # 返回禁止訪問的狀態(tài)碼
}

2 布隆過濾器在數(shù)據(jù)去重中的應(yīng)用

在數(shù)據(jù)去重方面可以使用 Redis 布隆過濾器來(lái)避免在大規(guī)模數(shù)據(jù)處理中的重復(fù)計(jì)算，減少計(jì)算開銷，并且保證數(shù)據(jù)的唯一性

# 判斷文章是否已經(jīng)被處理過
if BF.EXISTS article_bloom_filter article_id {
    continue; # 跳過本次循環(huán)
}
# 處理文章內(nèi)容
process_article(article);
# 將文章 ID 添加到布隆過濾器中
BF.ADD article_bloom_filter article_id;

3 布隆過濾器在爬蟲去重中的應(yīng)用

在爬蟲系統(tǒng)中為了避免重復(fù)爬取已經(jīng)存在的網(wǎng)頁(yè)，可以使用 Redis 布隆過濾器來(lái)記錄已經(jīng)訪問過的 URL

# 判斷 URL 是否已經(jīng)被訪問過
if BF.EXISTS url_bloom_filter url {
    continue; # 跳過本次循環(huán)
}
# 訪問 URL
response = http.get(url);
# 將 URL 添加到布隆過濾器中
BF.ADD url_bloom_filter url;

通過以上的應(yīng)用案例可以看出Redis 布隆過濾器具有在數(shù)據(jù)去重、防刷、爬蟲去重等方面的廣泛應(yīng)用，并且可以有效地減少重復(fù)計(jì)算、避免誤報(bào)或者漏報(bào)等問題。

五、Redis 布隆過濾器的優(yōu)缺點(diǎn)分析

1 布隆過濾器的優(yōu)點(diǎn)

• 布隆過濾器是一種空間效率高的數(shù)據(jù)結(jié)構(gòu)可以代替?zhèn)鹘y(tǒng)的 List, Set 等數(shù)據(jù)結(jié)構(gòu)，以達(dá)到節(jié)約內(nèi)存的目的
• 布隆過濾器的插入和查詢時(shí)間復(fù)雜度都是 O(k)，k 是哈希函數(shù)個(gè)數(shù)，這個(gè)值可以根據(jù)數(shù)據(jù)量去調(diào)整，因此查詢效率非常高。
• 布隆過濾器可以用于判斷一個(gè)元素是否在集合中，可以用在緩存穿透的場(chǎng)景中。

2 布隆過濾器的缺點(diǎn)

• 布隆過濾器無(wú)法刪除元素，一旦添加了一個(gè)元素就無(wú)法刪除，因?yàn)閯h除可能會(huì)影響其他元素的判斷結(jié)果
• 布隆過濾器的誤判率是存在的，這是由于多個(gè)元素映射到布隆過濾器的同一個(gè)位置，使得可能存在“誤判”情況
• 布隆過濾器的哈希函數(shù)個(gè)數(shù)和大小都需要事先確定，這在一些應(yīng)用場(chǎng)景中可能不太容易確定。

3 布隆過濾器的適用場(chǎng)景

• 緩存穿透：如果緩存中不存在某個(gè)鍵對(duì)應(yīng)的值，而且大量的請(qǐng)求又同時(shí)訪問該鍵，這時(shí)可以通過布隆過濾器過濾掉這些非法請(qǐng)求，降低了對(duì)后端系統(tǒng)的壓力。
• 網(wǎng)絡(luò)爬蟲：利用布隆過濾器判斷一個(gè)鏈接是否已經(jīng)被爬取過，避免重復(fù)抓取同一鏈接，提高爬蟲的效率。
• 黑名單過濾：將不良網(wǎng)址、IP 地址等加入到布隆過濾器中，當(dāng)請(qǐng)求過來(lái)時(shí)直接使用布隆過濾器判斷是否需要過濾掉該請(qǐng)求。

到此這篇關(guān)于Redis 布隆過濾器的原理和實(shí)踐的文章就介紹到這了,更多相關(guān)Redis布隆過濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論