06_redis_布隆過濾器

推送推薦內(nèi)容去重淆珊，使用bloom filter
相當(dāng)于一個(gè)不怎么精確的set結(jié)構(gòu)拇颅，當(dāng)使用contain方法判斷一個(gè)對象時(shí)候存在的時(shí)候會(huì)誤判捐晶，但是只要參數(shù)合理，它的精確程度還是很高的拴驮。
當(dāng)布隆過濾器判斷不存在的時(shí)候是真的不存在，判斷存在的時(shí)候可能不存在柴信。
Redis4.0提供插件功能套啤，布隆過濾器需要加載一個(gè) 插件到Redis Server中

基本使用

bf.add 添加元素，bf.exists 查詢元素是否存在随常。
bf.add 只能一次添加一個(gè)元素潜沦，如果想要一次添加多個(gè)，就需要用到 bf.madd 指令绪氛。同樣如果需要一次查詢多個(gè)元素是否存在唆鸡，就需要用到 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 指令争占。
可以使用 lettuce，它是另一個(gè)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();
    }
}

使用 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 的時(shí)候舆瘪，它出現(xiàn)了誤判。

測量誤判率

public class BloomTest {
import com.rabbitmq.http.client.Client;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

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();
    
    }
}

誤判率大約 1% 多點(diǎn)红伦。

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();
    }
}

誤判率大約 0.012%英古，比預(yù)計(jì)的 0.1% 低很多，不過布隆的概率是有誤差的昙读，只要不比預(yù)計(jì)誤判率高太多召调，都是正常現(xiàn)象

布隆過濾器的 initial_size 估計(jì)的過大，會(huì)浪費(fèi)存儲(chǔ)空間唠叛，估計(jì)的過小只嚣，就會(huì)影響準(zhǔn)確率，用戶在使用之前一定要盡可能地精確估計(jì)好元素?cái)?shù)量艺沼，還需要加上一定的冗余空間以避免實(shí)際元素可能會(huì)意外高出估計(jì)值很多册舞。
布隆過濾器的 error_rate 越小，需要的存儲(chǔ)空間就越大障般，對于不需要過于精確的場合调鲸，error_rate 設(shè)置稍大一點(diǎn)也無傷大雅。比如在新聞去重上而言挽荡，誤判率高一點(diǎn)只會(huì)讓小部分文章不能讓合適的人看到藐石，文章的整體閱讀量不會(huì)因?yàn)檫@點(diǎn)誤判率就帶來巨大的改變。

06_redis_布隆過濾器

基本使用

原理