当前位置： 首页 > article >正文

2 Redis的高级数据结构

article 2024/11/14 1:35:45
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 。
在这里插入图片描述

  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. 字符“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. 字符“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. 字符“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. 字符“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. 获取键 mykey 对应的值
127.0.0.1:6379> get mykey
  “dbydc”

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

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

统计出全年的签到次数：

 127.0.0.1:6379> BITCOUNT 2023-jack-sign 0 3  #统计1的数量
(integer) 2
2、布隆过滤器与Bitmaps

1970 年布隆提出了一种布隆过滤器的算法，目的是用来判断一个元素是否在一个集合中。
算法由一个二进制数组和一个 Hash 算法组成
在这里插入图片描述
布隆过滤器的误判问题?
在这里插入图片描述
布隆过滤器的使用场景之缓存穿透
当用户查询的时候，缓存中的key不存在，则进行数据库的大量查询导致的数据库的崩溃场景.
在这里插入图片描述
解决思路：在查询的时候快速判断查询的用户是否存在有效的缓存数据，布隆过滤器。
在这里插入图片描述
解决缓存穿透的问题，所以在用户查询缓存没有命中的时候，需要兜底去查询数据库，因此redis是无法完全取代数据库的。

3、布隆过滤器的代码实现
<?xml version="1.0" encoding="UTF-8"?>
<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.0</modelVersion>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.5.3</version>
        <relativePath/> <!-- lookup parent from repository -->
    </parent>
    <groupId>com.nengxing</groupId>
    <artifactId>redis-base</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <name>redis-base</name>
    <description>Demo project for Spring Boot</description>
    <properties>
        <java.version>1.8</java.version>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>

        <!-- https://mvnrepository.com/artifact/redis.clients/jedis -->
        <dependency>
            <groupId>redis.clients</groupId>
            <artifactId>jedis</artifactId>
            <version>3.6.3</version>
        </dependency>

        <!--引入Redis-->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-redis</artifactId>
            <version>1.4.2.RELEASE</version>
        </dependency>

        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson</artifactId>
            <version>3.12.3</version>
        </dependency>

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>30.1.1-jre</version>
        </dependency>
        <dependency>
            <!-- this is needed or IntelliJ gives junit.jar or junit-platform-launcher:1.3.2 not found errors -->
            <groupId>org.junit.platform</groupId>
            <artifactId>junit-platform-launcher</artifactId>
            <scope>test</scope>
        </dependency>

    </dependencies>

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

</project>

布隆过滤器核心代码

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 +
                '}';
    }
}

判断不在的，一定不在，判断在的情况，大概率都不在，除非存在一定的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"));
    }

}
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

    }
}
基于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

    }
}

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


http://www.kler.cn/a/134915.html

相关文章：

  • 第三十六章 Vue之路由重定向/404页面设置/路径模式设置
  • 【设计模式】关联关系与依赖关系
  • Day09 C++ 存储类
  • 管家婆财贸ERP BB059.银行流水导入对账
  • NVIDIA NIM 简介
  • C# 集合与泛型
  • 2024年测试工程师必看系列之fiddler设置手机端抓包全套教程
  • 为什么选择B+树作为数据库索引结构？
  • 前端常用utils方法持续更新中
  • 为什么同样是做测试，别人年薪30W+？我10k！！！
  • 采集淘宝天猫整店商品api（店铺列表、店铺所有商品）
  • Unity中 Start和Awake的区别
  • 医生ai数字人线上应用有效缓解了医疗资源不均的问题
  • buildadmin+tp8表格操作（7.1）表格的事件监听（el-table中的事件）
  • Arcgis js Api日常天坑问题3——加载geojson图层，元素无属性
  • rabbitMQ的direct模式的生产者与消费者使用案例
  • java list里面根据条件查找某个元素的下标
  • Linux入门攻坚——6、磁盘管理——分区及文件系统管理
  • GOTS认证资讯-7.0版关于环境准则的要求
  • 京东API接口获取京东平台商品详情数据，SKU，价格参数及其返回值说明
  • 【Linux】20、进程状态：不可中断进程、iowait、僵尸进程、dstat strace pstree
  • Python-使用sqlite3模块
  • 广州华锐互动VRAR：VR教学楼地震模拟体验增强学生防震减灾意识
  • mac上配置maven
  • 十. Linux关机重启命令与Vim编辑的使用
  • 【如何让你的建筑设计更高效】推荐7个3DMAX建筑设计的实用插件