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 。

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

2. 字符“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

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

  127.0.0.1:6379> setbit mykey 17 1(integer) 0127.0.0.1:6379> setbit mykey 18 1(integer) 0127.0.0.1:6379> setbit mykey 19 1(integer) 0127.0.0.1:6379> setbit mykey 20 1(integer) 0127.0.0.1:6379> setbit mykey 23 1(integer) 0

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

  127.0.0.1:6379> setbit mykey 25 1(integer) 0127.0.0.1:6379> setbit mykey 26 1(integer) 0127.0.0.1:6379> setbit mykey 29 1(integer) 0

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

  127.0.0.1:6379> setbit mykey 33 1(integer) 0127.0.0.1:6379> setbit mykey 34 1(integer) 0127.0.0.1:6379> setbit mykey 38 1(integer) 0127.0.0.1:6379> setbit mykey 39 1(integer) 0

6. 获取键 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长度*/@Autowiredprivate 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;}@Overridepublic 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;@Autowiredprivate RedisBloomFilter redisBloomFilter;@Testpublic 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);}@Testpublic 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"));//falseSystem.out.println("10086:BF--"+bloomFilter.mightContain("10086"));//trueSystem.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");//构造RedissonRedissonClient 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"));//falseSystem.out.println("10086:BF--"+bloomFilter.contains("10086"));//trueSystem.out.println("10084:BF--"+bloomFilter.contains("10084"));//true}
}

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