Redis 布隆过滤器

布隆过滤器

这一篇文章主要是记录布隆过滤器的使用和认识

主要参考了如下的blog

https://blog.csdn.net/weixin_42972832/article/details/131211665

他讲的还不错

简单的来说,布隆过滤器,实际上就像是一个集合,拿redis的key来举例来说,布隆过滤器的设置就是去过滤不属于redis key集合的key,这个方法还算挺有效的

原理初探

我理解到,布隆过滤器,底层就是利用hash函数

首先布隆过滤器一般是bitmap

传来一个key,通过几个hash函数,生成几个index的位置,

然后一个一个去查这几个index位置上的bitmap,是否都是1,如果都是1,那么就说明这个key存在于这个集合中,那我们就要放行

这里的算法其实应该是多种多样,但是万变不离其中,就是使用hash匹配

其实很好理解拉,不能懂!

问题

• 误判的问题

  这里学过hash函数的很容易想到,这里可能会发生hash碰撞,如果一个key,他刚好等于已经存在的key的hash的化,就会发生hash碰撞,这就是会发生误判的理由

  但是可以知道的是,如果说,过滤之后不在集合里边,那么就说名集合里边一定没有这个key,这个原理大家基本都懂,hash一般是不可逆的,

  布隆过滤器: 不存在一定不存在,存在有可能存在,有可能不存在,有误判的可能

  • 不能删除的问题

    因为布隆过滤器底层是多个hash共享数组的位置的,所以如果说,我们要删除某个key的化,就会影响到别人,所以布隆过滤器就是不能删除,只能重构

    由于重构引出的问题就是,有可能重构的成本太大了,你有1亿条数据要重构,这成本太高了

    手动实现

    我这里的手动实现也是参考他的博客来看的,算是最简单的

    先来看工具类

    import com.hmdp.filter.BloomFilterInit;
    import lombok.extern.slf4j.Slf4j;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.data.redis.core.RedisTemplate;
    import org.springframework.stereotype.Component;
    @Slf4j
    @Component
    public class CheckUtils {
        @Autowired
        private RedisTemplate redisTemplate;
        /**
         * 布隆过滤器校验
         *
         * @param key
         * @return boolean
         * @author hc
         * @date 2023/6/15 11:42
         */
        public boolean checkData(String key) {
            int abs = Math.abs(key.hashCode());
            long index = (long) (abs % Math.pow(2, 32));
            return redisTemplate.opsForValue().getBit(BloomFilterInit.WHITELIST_USER_KRY, index);
        }
        /**
         * 获取偏移量
         * @param key
         * @return long
         * @author hc
         * @date 2023/6/15 17:19
         */
        public long getOffsetId(String key) {
            int abs = Math.abs(key.hashCode());
            return getIndex(abs);
        }
        /**
         * 计算偏移量
         *
         * @param abs
         * @return java.lang.Long
         * @author hc
         * @date 2023/6/15 16:25
         */
        public long getIndex(int abs) {
            if (0 == abs) {
                return 0L;
            }
            return (long) (abs % Math.pow(2, 32));
        }
    }
    

    因为这里使用最简单的方法,所以直接就用java的hashCode方法得到hash值,然后这里的bitmap 我的容量大小是2的32次方

    看这个工具类,也很好理解

    生成index,就是hash值 % 2 ^32

    就是这里的checkData比较特殊一点,先是获得index的位置,然后去redis中的bitmap中查找,如果有返回true,没有返回false

    controller 测试类

    @RestController
    @RequestMapping("/bloom")
    public class BloomFilterController {
        @Autowired
        private BloomFilterService bloomFilterService;
        @GetMapping("/add")
        public void addUser(String phone) {
            bloomFilterService.addUser(phone);
        }
        @GetMapping("/query/{id}")
        public void queryUser(@PathVariable Long id) {
            bloomFilterService.queryUser(id);
        }
    }
    

    一个添加用户

    一个查用户

    public interface BloomFilterService {
        void addUser(String phone);
        User queryUser(Long id);
    }
    

    实现类

    @Slf4j
    @Service
    public class BloomFilterServiceImpl implements BloomFilterService {
        private static final String CACHE_KEY_USER = "user:";
        @Resource
        private CheckUtils checkUtils;
        @Resource
        private RedisTemplate redisTemplate;
        @Autowired
        private IUserService userService;
        @Autowired
        private RedisCache redisCache;
        public void addUser(String phone) {
            //返回id
            User user = BeanUtil.copyProperties(UserDTO.builder().nickName("").build(), User.class);
            userService.save(user.setPhone(phone));
            // 这里可以开启一个异步线程，在事务提交之后再进行操作
            if (user.getId() > 0) {
                String key = CACHE_KEY_USER + String.valueOf(user.getId());
                //计算index位置
                long index = checkUtils.getOffsetId(key);
                // redis的数据都需要使用统一的json工具转成json格式后放入
                redisCache.setCacheObject(key,user);
                redisTemplate.opsForValue().setBit(BloomFilterInit.WHITELIST_USER_KRY, index, Boolean.TRUE);
                log.info("新增用户信息|用户key:{}|布隆过滤器偏移量:{}", key, index);
            }
        }
        public User queryUser(Long id) {
            if (id < 0) {
                log.info("获取用户信息|用户id异常,异常id:{}", id);
                return null;
            }
            String key = CACHE_KEY_USER.concat(String.valueOf(id));
            boolean checkData = checkUtils.checkData(key);
            if (!checkData) {
                log.info("获取用户信息|用户id不存在,异常id:{}", id);
                return null;
            }
            //布尔过滤通过了!
            User user = redisCache.getCacheObject(key);
            log.info("用户信息 {}",user);
            //如果他为空
            if(Objects.isNull(user)) {
                return null;
            }
            return user;
        }
    }
    

    我来先说这里的addUser的逻辑

    首先是直接到数据库中,存数据,这里的数据库的操作,可以自行换一个数据库,只要有id的就行

    然后就是存redis的过程

    先是获得redis的key 这里的key 拼接是这样 user: + id

    然后是获得index的位置,这个也是bitmap中的index

    存redis user用户

    存redis bitmap 设置为1

    queryUser

    先是获得key,先去查布隆过滤器,布隆过滤器的checkData

    这里的查找也是和设置bitmap的时候也是一样,就是去查找bitmap 在index位置是否是1

    如果通过,说明集合里边有他,就说明成功

    测试

    先添加用户

    

    redis的样子

    

    然后我们去查1017是否存在

    

    

    从这里看是存在的

    我们再去查1000

    是否存在

    

    

    这样就实现了简单的布隆过滤器

    总结

    总结来看,我这个小布隆过滤器,只有2^32个位置,而且还只是看一位的,所以蛮粗糙的,但是不妨碍我们理解布隆过滤器,不管他多复杂,思想都是一样的,都要去做hash的运算,算位置,比较位置,就没了