2 Redis的高级数据结构

1、Bitmaps

首先，最经典的应用场景就是用户日活的统计，比如说签到等。
字段串：“dbydc”，根据对应的ASCII表，最后可以得到对应的二进制，如图所示
在这里插入图片描述

一个字符占8位（bit），不够就在最高位补 0（零），我们只需设置值为 1 的位。如图所示，二进制最高位是在最左边的，但数组索引最高位是在最右边。字符“d”只需在偏移量（offset，即数组索引）第 1、2、5 位设置 1 ；字符“b”只需在偏移量（offset，即数组索引）第 9、10、14 位设置 1 ；字符“y”只需在偏移量（offset，即数组索引）第 17、18、19、20、23 位设置 1 ；字符“d”只需在偏移量（offset，即数组索引）第 25、26、29 位设置 1 ；字符“c”只需在偏移量（offset，即数组索引）第 33、34、38、39 位设置 1 。
在这里插入图片描述

字符“d”存储（第 1、2、5 位设置1）

127.0.0.1:6379> setbit mykey 1 1
  (integer) 0
127.0.0.1:6379> setbit mykey 2 1
  (integer) 0
127.0.0.1:6379> setbit mykey 5 1
  (integer) 0
1
2
3
4
5
6

字符“b”存储（第 9、10、14 位设置1）

127.0.0.1:6379> setbit mykey 9 1
(integer) 0
127.0.0.1:6379> setbit mykey 10 1
(integer) 0
127.0.0.1:6379> setbit mykey 14 1
(integer) 0
1
2
3
4
5
6

字符“y”存储（第 17、18、19、20、23 位设置1）

  127.0.0.1:6379> setbit mykey 17 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 18 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 19 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 20 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 23 1
  (integer) 0
1
2
3
4
5
6
7
8
9
10

字符“d”存储（第 25、26、29 位设置1）

  127.0.0.1:6379> setbit mykey 25 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 26 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 29 1
  (integer) 0
1
2
3
4
5
6

字符“c”存储（第 33、34、38、39 位设置1）

  127.0.0.1:6379> setbit mykey 33 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 34 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 38 1
  (integer) 0
  127.0.0.1:6379> setbit mykey 39 1
  (integer) 0
1
2
3
4
5
6
7
8

获取键 mykey 对应的值

127.0.0.1:6379> get mykey
  “dbydc”
1
2

所以，我们在统计某位用户系统签到的时候，sign=1就是签到，0就是没有签到。

setbit 2023-jack-sign 1 1		//第一日签到
setbit 2023-jack-sign 2 0		//第二日未签到
setbit 2023-jack-sign 3 1		//第三日签到
...
1
2
3
4

统计出全年的签到次数：

 127.0.0.1:6379> BITCOUNT 2023-jack-sign 0 3  #统计1的数量
(integer) 2
1
2

2、布隆过滤器与Bitmaps

1970 年布隆提出了一种布隆过滤器的算法，目的是用来判断一个元素是否在一个集合中。
算法由一个二进制数组和一个 Hash 算法组成
在这里插入图片描述
布隆过滤器的误判问题?

布隆过滤器的使用场景之缓存穿透
当用户查询的时候，缓存中的key不存在，则进行数据库的大量查询导致的数据库的崩溃场景.

解决思路：在查询的时候快速判断查询的用户是否存在有效的缓存数据，布隆过滤器。
在这里插入图片描述
解决缓存穿透的问题，所以在用户查询缓存没有命中的时候，需要兜底去查询数据库，因此redis是无法完全取代数据库的。

3、布隆过滤器的代码实现


<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0modelVersion>
    <parent>
        <groupId>org.springframework.bootgroupId>
        <artifactId>spring-boot-starter-parentartifactId>
        <version>2.5.3version>
        <relativePath/> 
    parent>
    <groupId>com.nengxinggroupId>
    <artifactId>redis-baseartifactId>
    <version>0.0.1-SNAPSHOTversion>
    <name>redis-basename>
    <description>Demo project for Spring Bootdescription>
    <properties>
        <java.version>1.8java.version>
    properties>
    <dependencies>
        <dependency>
            <groupId>org.springframework.bootgroupId>
            <artifactId>spring-boot-starter-webartifactId>
        dependency>

        <dependency>
            <groupId>org.springframework.bootgroupId>
            <artifactId>spring-boot-starter-testartifactId>
            <scope>testscope>
        dependency>

        
        <dependency>
            <groupId>redis.clientsgroupId>
            <artifactId>jedisartifactId>
            <version>3.6.3version>
        dependency>

        
        <dependency>
            <groupId>org.springframework.bootgroupId>
            <artifactId>spring-boot-starter-redisartifactId>
            <version>1.4.2.RELEASEversion>
        dependency>

        <dependency>
            <groupId>org.redissongroupId>
            <artifactId>redissonartifactId>
            <version>3.12.3version>
        dependency>

        <dependency>
            <groupId>com.google.guavagroupId>
            <artifactId>guavaartifactId>
            <version>30.1.1-jreversion>
        dependency>
        <dependency>
            
            <groupId>org.junit.platformgroupId>
            <artifactId>junit-platform-launcherartifactId>
            <scope>testscope>
        dependency>

    dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.bootgroupId>
                <artifactId>spring-boot-maven-pluginartifactId>
            plugin>
        plugins>
    build>

project>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

布隆过滤器核心代码

import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import com.google.common.primitives.Longs;
import org.springframework.beans.factory.annotation.Autowired;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;
import redis.clients.jedis.Pipeline;

import java.nio.charset.Charset;

/*仿Google的布隆过滤器实现，基于redis支持分布式*/
public class RedisBloomFilter {

    public final static String RS_BF_NS = "rbf:";
    private int numApproxElements; /*预估元素数量，在配合使用数组的时候使用*/
    private double fpp; /*布隆过滤器所能接受的最大误差*/
    private int numHashFunctions; /*自动计算的hash函数个数*/
    private int bitmapLength; /*自动计算的最优Bitmap长度*/

    @Autowired
    private JedisPool jedisPool;

    /**
     * 构造布隆过滤器
     * @param numApproxElements 预估元素数量
     * @param fpp 可接受的最大误差
     * @return
     */
    public RedisBloomFilter init(int numApproxElements,double fpp){
        this.numApproxElements = numApproxElements;
        this.fpp = fpp;
        /*位数组的长度*/
        //this.bitmapLength = (int) (-numApproxElements*Math.log(fpp)/(Math.log(2)*Math.log(2)));
        this.bitmapLength=128;
        /*算hash函数个数，此处为了简便直接写死*/
        //this.numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));
        this.numHashFunctions=2;
        return  this;
    }

    /**
     * 计算一个元素值哈希后映射到Bitmap的哪些bit上
     * 用两个hash函数来模拟多个hash函数的情况
     *     * @param element 元素值
     * @return bit下标的数组
     */
    private long[] getBitIndices(String element){
        long[] indices = new long[numHashFunctions];
        /*会把传入的字符串转为一个128位的hash值，并且转化为一个byte数组*/
        byte[] bytes = Hashing.murmur3_128().
                hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8"))).
                asBytes();

        long hash1 = Longs.fromBytes(bytes[7],bytes[6],bytes[5],bytes[4],bytes[3],bytes[2],bytes[1],bytes[0]);
        long hash2 = Longs.fromBytes(bytes[15],bytes[14],bytes[13],bytes[12],bytes[11],bytes[10],bytes[9],bytes[8]);

        /*用这两个hash值来模拟多个函数产生的值*/
        long combinedHash = hash1;
        for(int i=0;i<numHashFunctions;i++){
            //数组下标
            indices[i]=(combinedHash&Long.MAX_VALUE) % bitmapLength;
            combinedHash = combinedHash + hash2;
        }

        System.out.print(element+"数组下标");
        for(long index:indices){
            System.out.print(index+",");
        }
        System.out.println(" ");
        return indices;
    }

    /**
     * 插入元素
     *
     * @param key       原始Redis键，会自动加上前缀
     * @param element   元素值，字符串类型
     * @param expireSec 过期时间（秒）
     */
    public void insert(String key, String element, int expireSec) {
        if (key == null || element == null) {
            throw new RuntimeException("键值均不能为空");
        }
        //为了与redis中的其他key进行区别
        String actualKey = RS_BF_NS.concat(key);

        try (Jedis jedis = jedisPool.getResource()) {
            try (Pipeline pipeline = jedis.pipelined()) {
                for (long index : getBitIndices(element)) {
                    pipeline.setbit(actualKey, index, true);
                }
                pipeline.syncAndReturnAll();
            } catch (Exception ex) {
                ex.printStackTrace();
            }
            jedis.expire(actualKey, expireSec);
        }
    }

    /**
     * 检查元素在集合中是否（可能）存在
     *
     * @param key     原始Redis键，会自动加上前缀
     * @param element 元素值，字符串类型
     */
    public boolean mayExist(String key, String element) {
        if (key == null || element == null) {
            throw new RuntimeException("键值均不能为空");
        }
        String actualKey = RS_BF_NS.concat(key);
        boolean result = false;

        try (Jedis jedis = jedisPool.getResource()) {
            try (Pipeline pipeline = jedis.pipelined()) {
                for (long index : getBitIndices(element)) {
                    pipeline.getbit(actualKey, index);
                }
                result = !pipeline.syncAndReturnAll().contains(false);
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        }
        return result;
    }

    @Override
    public String toString() {
        return "RedisBloomFilter{" +
                "numApproxElements=" + numApproxElements +
                ", fpp=" + fpp +
                ", numHashFunctions=" + numHashFunctions +
                ", bitmapLength=" + bitmapLength +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

判断不在的，一定不在，判断在的情况，大概率都不在，除非存在一定的hash冲突
测试：

@SpringBootTest
public class TestRedisBloomFilter {

    private static final int DAY_SEC = 60 * 60 * 24;

    @Autowired
    private RedisBloomFilter redisBloomFilter;

    @Test
    public void testInsert() throws Exception {
       // System.out.println(redisBloomFilter);
        redisBloomFilter.insert("bloom:user", "20210001", DAY_SEC);
        redisBloomFilter.insert("bloom:user", "20210002", DAY_SEC);
        redisBloomFilter.insert("bloom:user", "20210003", DAY_SEC);
        redisBloomFilter.insert("bloom:user", "20210004", DAY_SEC);
        redisBloomFilter.insert("bloom:user", "20210005", DAY_SEC);
    }

    @Test
    public void testMayExist() throws Exception {
        System.out.println(redisBloomFilter.mayExist("bloom:user", "20210001"));
        System.out.println(redisBloomFilter.mayExist("bloom:user", "20210002"));
        System.out.println(redisBloomFilter.mayExist("bloom:user", "20210003"));


        System.out.println(redisBloomFilter.mayExist("bloom:user", "20211001"));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Guava的布隆

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/*单机下无Redis的布隆过滤器：使用Google的Guava的BloomFilter*/
public class GuavaBF {
    public static void main(String[] args) {
        long expectedInsertions = 100000;
        double fpp = 0.00005;

        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp);

        bloomFilter.put("10081");
        bloomFilter.put("10082");
        bloomFilter.put("10083");
        bloomFilter.put("10084");
        bloomFilter.put("10085");
        bloomFilter.put("10086");

        System.out.println("123456:BF--"+bloomFilter.mightContain("123456"));//false
        System.out.println("10086:BF--"+bloomFilter.mightContain("10086"));//true
        System.out.println("10084:BF--"+bloomFilter.mightContain("10084"));//true

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

基于Redisson的实现

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
/*Redisson底层基于位图实现了一个布隆过滤器，使用非常方便*/
public class RedissonBF {
    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");

        //构造Redisson
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
        //初始化布隆过滤器：预计元素为100000000L,误差率为3%
        bloomFilter.tryInit(100000000L,0.03);
        //将号码10081~10086插入到布隆过滤器中
        bloomFilter.add("10081");
        bloomFilter.add("10082");
        bloomFilter.add("10083");
        bloomFilter.add("10084");
        bloomFilter.add("10085");
        bloomFilter.add("10086");

        //判断下面号码是否在布隆过滤器中
        System.out.println("123456:BF--"+bloomFilter.contains("123456"));//false
        System.out.println("10086:BF--"+bloomFilter.contains("10086"));//true
        System.out.println("10084:BF--"+bloomFilter.contains("10084"));//true

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

布隆过滤器的实现：
Redis + Redisson
Redis + 自主实现
无Redis + Guava

相关阅读:
quarkus(二) 初识
 Python实践提！
大语言模型 (LLM) 红队测试：提前解决模型漏洞
 【Ruby】怎样判断一个类是否有某个方法，一个实例是否有某个属性？
【C++】红黑树的模拟实现
 数字图像处理:亮度对比度-几何变换-噪声处理
 人工智能基础部分21-神经网络中优化器算法的详细介绍，配套详细公式
 TF-IDF
flutter 本地存储数据（shared_preferences）
SpringMvc 之crud增删改查应用
原文地址：https://blog.csdn.net/weixin_39563769/article/details/134491189