06_redis_布隆过滤器

作者: A_l_A_n | 来源:发表于2020-07-07 14:36 被阅读0次

Guava - 布隆过滤器的使用
06_redis_布隆过滤器
kata05:布隆过滤器
SpringBoot2.x—使用Redis的bitmap实现布隆
redis插件安装-bloom模块
布隆过滤器
Redis-001、安装布隆过滤器
面试题延伸之布隆去重的原理及实现
JavaGuide知识点整理——布隆过滤器
理解布隆过滤器算法的实现原理

推送推荐内容去重，使用bloom filter
相当于一个不怎么精确的set结构，当使用contain方法判断一个对象时候存在的时候会误判，但是只要参数合理，它的精确程度还是很高的。
当布隆过滤器判断不存在的时候是真的不存在，判断存在的时候可能不存在。
Redis4.0提供插件功能，布隆过滤器需要加载一个插件到Redis Server中

基本使用

bf.add 添加元素，bf.exists 查询元素是否存在。
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 没有提供指令扩展机制，所以你无法直接使用 Jedis 来访问Redis Module 提供的 bf.xxx 指令。
可以使用 lettuce，它是另一个Redis 的客户端，相比 Jedis 而言，它很早就支持了指令扩展。

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

运行后，我们看到了输出是 214，也就是到第 214 的时候，它出现了误判。

测量误判率

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% 多点。

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");
        // 对应 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%，比预计的 0.1% 低很多，不过布隆的概率是有误差的，只要不比预计误判率高太多，都是正常现象

布隆过滤器的 initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。
布隆过滤器的 error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate 设置稍大一点也无伤大雅。比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变。