实现布隆过滤器的三种方式

柔光的暖阳◎ 2022-12-12 15:07 113阅读 0赞

# 一、谷歌布隆过滤器 #

项目地址：[https://gitee.com/quancong/redis.git][https_gitee.com_quancong_redis.git]  
BloomFilter项目

需求：判断是否是已注册过的用户

### 1、引入布隆过滤器pom依赖 ###

<dependency>
             <groupId>com.google.guava</groupId>
             <artifactId>guava</artifactId>
             <version>21.0</version>
        </dependency>

### 2、数据库中表数据 ###

SET NAMES utf8mb4;
    SET FOREIGN_KEY_CHECKS = 0;
    
    DROP TABLE IF EXISTS `user`;
    CREATE TABLE `user` (
      `id` int NOT NULL AUTO_INCREMENT COMMENT '主键',
      `username` varchar(20) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NOT NULL DEFAULT '' COMMENT '用户名',
      `password` varchar(20) NOT NULL DEFAULT '' COMMENT '用户创建时间',
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
    
    BEGIN;
    INSERT INTO `user` VALUES (1, '张三', '2020-07-31 17:08:42');
    INSERT INTO `user` VALUES (2, '李四', '2020-07-31 07:10:14');
    INSERT INTO `user` VALUES (3, '王五', '2020-07-31 20:30:09');
    COMMIT;
    
    SET FOREIGN_KEY_CHECKS = 1;

![在这里插入图片描述][20201008231415404.png_pic_center]

### 3、启动springboot项目时将用户id添加到布隆过滤器中来 ###

/**
     * 启动时初始化布隆过滤器
     */
    @Service
    public class BloomFilterService implements ApplicationRunner {
        
    
        @Autowired
        private UserDao userDao;
    
        private BloomFilter<Integer> bf;
    
        /**
         * 启动时将数据库中用户id加载到布隆过滤器中来
         * @param args
         * @throws Exception
         */
        @Override
        public void run(ApplicationArguments args) throws Exception {
        
            List<Integer> userIdList = userDao.findAllUserId();
            if (CollectionUtils.isEmpty(userIdList)) return;
            //创建布隆过滤器 误判率默认为3%
            bf = BloomFilter.create(Funnels.integerFunnel(),userIdList.size());
            for (Integer userId : userIdList) {
        
                bf.put(userId);
            }
        }
    
        /***
         * 判断id可能存在于布隆过滤器里面
         * @param id
         * @return
         */
        public boolean userIdExists(int id){
        
            return bf.mightContain(id);
        }
    }

这里同时还有一个判断用户id可能存在的方法

### 4、编写controller测试一下 ###

@RestController
    public class UserController {
        
    
        @Autowired
        private BloomFilterService bloomFilterService;
    
        @RequestMapping("/bloom/idExists")
        public boolean ifExists(int id){
        
            return bloomFilterService.userIdExists(id);
        }
    }

浏览器输入http://localhost:8080/bloom/idExists?id=1，即一个已存在的用户id  
![在这里插入图片描述][20201008232531247.png_pic_center]  
输入一个存在的用户id返回true

![在这里插入图片描述][20201008232803781.png_pic_center]  
输入一个不存在的用户id返回false

# 二、redis原生setbit命令实现 #

因篇幅过长，可参见我的另一篇博客。

[https://blog.csdn.net/qq\_41963899/article/details/108911244][https_blog.csdn.net_qq_41963899_article_details_108911244]

# 三、使用redis布隆过滤器插件实现 #

### 1、安装布隆过滤器 ###

git clone git://github.com/RedisLabsModules/rebloom
    cd rebloom
    make

### 2、有一个redisbloom.so文件，复制路径，假如为path，在redis.conf中指定该模块 ###

loadmodule /path/rebloom.so

### 3、重启redis ###

redis-server  ./redis.conf

### 4、测试 ###

redis-cli bf.add myBloom redis1 # 向myBloom布隆过滤器添加redis1键
    redis-cli bf.add myBloom redis2
    redis-cli # 进入redis客户端

判断yBloom布隆过滤器是否存在redis1、redis2、redis3这些键

bf.exists myBloom redis1
    bf.exists myBloom redis2
    bf.exists myBloom redis3

### 5、springboot整合redis布隆过滤器 ###

项目源码：[https://gitee.com/quancong/redis.git][https_gitee.com_quancong_redis.git]

@Service
    public class RedisBloomFilter {
        
    
        @Autowired
        private RedisTemplate redisTemplate;
        
        public Boolean bloomFilterAdd(String filterName,int value){
        
            DefaultRedisScript<Boolean> bloomAdd = new DefaultRedisScript<>();
            bloomAdd.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterAdd.lua")));
            bloomAdd.setResultType(Boolean.class);
            List<Object> keyList= new ArrayList<>();
            keyList.add(filterName);
            keyList.add(value+"");
            Boolean result = (Boolean) redisTemplate.execute(bloomAdd,keyList);
            return result;
        }
        
        public Boolean bloomFilterExists(String filterName,int value){
        
            DefaultRedisScript<Boolean> bloomExists= new DefaultRedisScript<>();
            bloomExists.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterExist.lua")));
            bloomExists.setResultType(Boolean.class);
            List<Object> keyList= new ArrayList<>();
            keyList.add(filterName);
            keyList.add(value+"");
            Boolean result = (Boolean) redisTemplate.execute(bloomExists,keyList);
            return result;
        }
    }

测试一下：

@RestController
    public class RedisController {
        
    
        @Autowired
        private RedisBloomFilter redisBloomFilter;
    
        @RequestMapping("/bloom/redisIdExists")
        public boolean redisidExists(int id){
        
            return redisBloomFilter.bloomFilterExists("myBloom",id);
        }
    
        @RequestMapping("/bloom/redisIdAdd")
        public boolean redisidAdd(int id){
        
            return redisBloomFilter.bloomFilterAdd("myBloom",id);
        }
    
    }

先往布隆过滤器中添加两条数据

http://localhost:8080/bloom/redisIdAdd?id=1

![在这里插入图片描述][20201009152640100.png_pic_center]  
![在这里插入图片描述][2020100915270311.png_pic_center]  
再测试一下redis布隆过滤器不存在的数据

http://localhost:8080/bloom/redisIdExists?id=3

![在这里插入图片描述][20201009152841879.png_pic_center]  
成功！

[https_gitee.com_quancong_redis.git]: https://gitee.com/quancong/redis.git
[20201008231415404.png_pic_center]: /images/20221123/4d7620d2d2684dad82ae36faf125ea5e.png
[20201008232531247.png_pic_center]: /images/20221123/d37d991ecf9b4e57abad6dae8d14d169.png
[20201008232803781.png_pic_center]: /images/20221123/c24b6a8d25ab425698cac62d4a2b1211.png
[https_blog.csdn.net_qq_41963899_article_details_108911244]: https://blog.csdn.net/qq_41963899/article/details/108911244
[20201009152640100.png_pic_center]: /images/20221123/99aa8772ed1144b19270503c3d6ed509.png
[2020100915270311.png_pic_center]: /images/20221123/9e60d831a70b445e983a17c8290843c5.png
[20201009152841879.png_pic_center]: /images/20221123/8bcc91a27922443cbf69680577644c04.png