7、去重(BloomFiler)
通过上面HeyperLogLog的学习,我们掌握了一种不精准的去重计数方案,但是有没有发现,他没办法获取某个用户是否访问过;理想中,我们是希望有一个PFEXISTS
的命令,来判断某个key是否存在,然而HeyperLogLog并没有;要想实现这一需求,就得 BloomFiler 上场了。
-
什么是Bloom Filter?Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。 通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。 基于一种概率数据结构来实现,是一个有趣且强大的算法。
举个例子:假如你写了一个爬虫,用于爬取网络中的所有页面,当你拿到一个新的页面时,如何判断这个页面是否爬取过?
普通做法:每爬取一个页面,往数据库插入一行数据,记录一下URL,每次拿到一个新的页面,就去数据库里面查询一下,存在就说明爬取过;
普通做法的缺点:少量数据,用传统方案没啥问题,如果是海量数据,每次爬取前的检索,将会越来越慢;如果你的爬虫只关心内容,对来源数据不太关心的话,这部分数据的存储,也将消耗你很大的物理资源;
此时通过 BloomFiler 就能以很小的内存空间作为代价,即可轻松判断某个值是否存在。
同样,BloomFiler 也不那么精准,在默认参数情况下,是存在1%左右的误差;但是 BloomFiler 是允许通过error_rate(误差率)以及initial_size(预计大小)来设置他的误差比例
-
error_rate:误差率,越低,需要的空间就越大; -
initial_size:预计放入值的数量,当实际放入的数量大于设置的值时,误差率就会逐渐升高;所以为了避免误差率,可以提前做好估值,避免再次大的误差;
BloomFiler 安装
为了方便测试,这里使用 Docker 快速安装
docker run -d -p 6379:6379 redislabs/rebloom
功能所需的命令
-
bf.add 添加单个元素 -
bf.madd 批量田间 -
bf.exists 检测元素是否存在 -
bf.mexists 批量检测
Redis-cli操作
127.0.0.1:6379> bf.add web:crawler baidu (integer) 1 127.0.0.1:6379> bf.madd web:crawler tencent bing 1) (integer) 1 2) (integer) 1 127.0.0.1:6379> bf.exists web:crawler baidu (integer) 1 127.0.0.1:6379> bf.mexists web:crawler baidu 163 1) (integer) 1 2) (integer) 0
SpringBoot整合
工具类 RedisBloom
import org.springframework.beans.factory.annotation.Autowired; import org.springframework.data.redis.core.StringRedisTemplate; import org.springframework.data.redis.core.script.DefaultRedisScript; import org.springframework.data.redis.core.script.RedisScript; import org.springframework.stereotype.Component; import java.util.Arrays; import java.util.List; /** * redis布隆过滤器 * * @title: RedisBloom * @projectName ehang-spring-boot * @description: TODO * @date 2022/7/19 17:03 */ @Component public class RedisBloom { private static RedisScript<Boolean> bfreserveScript = new DefaultRedisScript<>("return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])", Boolean.class); private static RedisScript<Boolean> bfaddScript = new DefaultRedisScript<>("return redis.call('bf.add', KEYS[1], ARGV[1])", Boolean.class); private static RedisScript<Boolean> bfexistsScript = new DefaultRedisScript<>("return redis.call('bf.exists', KEYS[1], ARGV[1])", Boolean.class); private static String bfmaddScript = "return redis.call('bf.madd', KEYS[1], %s)"; private static String bfmexistsScript = "return redis.call('bf.mexists', KEYS[1], %s)"; @Autowired private StringRedisTemplate redisTemplate; /** * 设置错误率和大小(需要在添加元素前调用,若已存在元素,则会报错) * 错误率越低,需要的空间越大 * * @param key * @param errorRate 错误率,默认0.01 * @param initialSize 默认100,预计放入的元素数量,当实际数量超出这个数值时,误判率会上升,尽量估计一个准确数值再加上一定的冗余空间 * @return */ public Boolean bfreserve(String key, double errorRate, int initialSize) { return redisTemplate.execute(bfreserveScript, Arrays.asList(key), String.valueOf(errorRate), String.valueOf(initialSize)); } /** * 添加元素 * * @param key * @param value * @return true表示添加成功,false表示添加失败(存在时会返回false) */ public Boolean bfadd(String key, String value) { return redisTemplate.execute(bfaddScript, Arrays.asList(key), value); } /** * 查看元素是否存在(判断为存在时有可能是误判,不存在是一定不存在) * * @param key * @param value * @return true表示存在,false表示不存在 */ public Boolean bfexists(String key, String value) { return redisTemplate.execute(bfexistsScript, Arrays.asList(key), value); } /** * 批量添加元素 * * @param key * @param values * @return 按序 1表示添加成功,0表示添加失败 */ public List<Integer> bfmadd(String key, String... values) { return (List<Integer>) redisTemplate.execute(this.generateScript(bfmaddScript, values), Arrays.asList(key), values); } /** * 批量检查元素是否存在(判断为存在时有可能是误判,不存在是一定不存在) * * @param key * @param values * @return 按序 1表示存在,0表示不存在 */ public List<Integer> bfmexists(String key, String... values) { return (List<Integer>) redisTemplate.execute(this.generateScript(bfmexistsScript, values), Arrays.asList(key), values); } private RedisScript<List> generateScript(String script, String[] values) { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= values.length; i++) { if (i != 1) { sb.append(","); } sb.append("ARGV[").append(i).append("]"); } return new DefaultRedisScript<>(String.format(script, sb.toString()), List.class); } }
测试
import lombok.extern.slf4j.Slf4j; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import org.springframework.data.redis.core.RedisTemplate; import java.util.List; /** * @author 一行Java * @title: BFTest * @projectName ehang-spring-boot * @description: TODO * @date 2022/7/19 17:04 */ @SpringBootTest @Slf4j public class BFTest { private final String KEY_WEB_CRAWLER = "web:crawler1"; @Autowired RedisBloom bloom; @Autowired RedisTemplate redisTemplate; @Test public void test() { Boolean hasKey = redisTemplate.hasKey(KEY_WEB_CRAWLER); log.info("bloom hasKey:{}", hasKey); if (!hasKey) { // 不存在的时候 再去初始化 Boolean bfreserve = bloom.bfreserve(KEY_WEB_CRAWLER, 0.0001, 10000); log.info("bloom bfreserve:{}", bfreserve); } List<Integer> madd = bloom.bfmadd(KEY_WEB_CRAWLER, "baidu", "google"); log.info("bloom bfmadd:{}", madd); Boolean baidu = bloom.bfexists(KEY_WEB_CRAWLER, "baidu"); log.info("bloom bfexists baidu:{}", baidu); Boolean bing = bloom.bfexists(KEY_WEB_CRAWLER, "bing"); log.info("bloom bfexists bing:{}", bing); } }
日志输出
com.ehang.redis.bloom_filter.BFTest : bloom hasKey:false com.ehang.redis.bloom_filter.BFTest : bloom bfreserve:true com.ehang.redis.bloom_filter.BFTest : bloom bfmadd:[1, 1] com.ehang.redis.bloom_filter.BFTest : bloom bfexists baidu:true com.ehang.redis.bloom_filter.BFTest : bloom bfexists bing:false
文章评论