四时宝库

程序员的知识宝库

2025年05月09日

reidis 数据结构之 ~ BitMap ~ 签到实现-布隆过滤器

1 面试题

  1. 日活统计
  2. 连续签到打卡
  3. 最近一周活跃用户
  4. 统计用户一年之内的登陆天数

2 BitMap介绍

由0和1状态实现的二进制bit位数组，通过一个bit位来表示某个元素对应的值或者状态，其中的key就是对应元素本身。我们知道8个bit可以组成一个Byte，所以bitmap本身会极大的节省储存空间。
 位图（BitMap）是借助 SDS 实现的。

举个栗子

如果我们需要记录某一用户在一年中每天是否有登录我们的系统这一需求该如何完成呢？如果使用KV存储，每个用户需要记录365个，当用户量上亿时，这所需要的存储空间是惊人的。

Redis 为我们提供了位图这一数据结构，每个用户每天的登录记录只占据一位，365天就是365位，仅仅需要46字节就可存储，极大地节约了存储空间。

位图数据结构其实并不是一个全新的玩意，我们可以简单的认为就是个数组，只是里面的内容只能为0或1而已(二进制位数组)。

2.1 BitMap用法

Redis中是利用string类型数据结构实现BitMap，因此最大上限是512M，转换为bit则是 2^32个bit位。

BitMap的操作命令有：

  • SETBIT：向指定位置（offset）存入一个0或1
  • GETBIT ：获取指定位置（offset）的bit值
  • BITCOUNT ：统计BitMap中值为1的bit位的数量
  • BITFIELD ：操作（查询、修改、自增）BitMap中bit数组中的指定位置（offset）的值
  • BITFIELD_RO ：获取BitMap中bit数组，并以十进制形式返回
  • BITOP ：将多个BitMap的结果做位运算（与 、或、异或）BITPOS ：查找bit数组中指定范围内第一个0或1出现的位置

2.2 bitmap的使用场景

用户在线状态

使用bitmap是一个节约空间效率又高的一种方法，只需要一个key，然后用户id为偏移量offset，如果在线就设置为1，不在线就设置为0，3亿用户只需要36MB的空间。

$status = 1;
$redis->setBit('online', $uid, $status);
$redis->getBit('online', $uid);

统计活跃用户

使用时间作为缓存的key，然后用户id为offset，如果当日活跃过就设置为1。之后通过BITOP进行二进制计算算出在某段时间内用户的活跃情况。

$status = 1;
$redis->setBit('active_20170708', $uid, $status);
$redis->setBit('active_20170709', $uid, $status);

大部分情况都无需分片，一年365天，3亿数据约占300000000*365/8/1000/1000/1000=13.68g。存储成本是不是很低。

快速去重

假设让你从20亿个整数中找出不重复的整数的个数，提前是内存不足以容纳这20亿个整数，那么你会用什么办法？使用Bit-map就可以很好的解决。关键的问题就是怎么设计Bit-map来表示这20亿个数字的状态了。

一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11，那我们大概需要存储空间2G左右。所以可以这样进行操作：

  1. 把这20亿个数字放进去（存储），如果对应的状态位为00，则将其变为01，表示存在一次；
  2. 如果对应的状态位为01，则将其变为11，表示已经有一个了，即出现多次；
  3. 如果为11，则对应的状态位保持不变，仍表示出现多次。
  4. 最后，统计状态位为01的个数，就得到了不重复的数字个数，时间复杂度为O(n)。
#如果 key: 01不存在的时候，放入
127.0.0.1:6379> setbit 01 123 1
(integer) 0
#如果 key: 01存在的时候，则重复，在11中标示
127.0.0.1:6379> getbit 01 123
(integer) 1
127.0.0.1:6379> setbit 11 123 1
(integer) 0
127.0.0.1:6379> getbit 11 123
(integer) 1

3 布隆过滤器

经典面试题

  1. 有50亿个电话号码，现有10万个电话号码，如何快速的准确的判断号码是否存在？
  2. 全球10亿网址，安全连接网址的判断
  3. 白名单、黑名单的校验

Bloom Filter 原理

类似set的数据结构，高效的插入和查询，占用空间少，有误差，不能删除元素，因为涉及到hashcode的判断，导致误判率增加。请注意：不存在时，是一定不存在；存在时，则不一定

布隆过滤器的原理：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

简单的说一下就是我们先把我们数据库的数据都加载到我们的过滤器中，比如数据库的id现在有：1、2、3。那就用id：1 为例子他在上图中经过三次hash之后，把三次原本值0的地方改为1

下次我进来查询如果id也是1 那我就把1拿去三次hash 发现跟上面的三个位置完全一样，那就能证明过滤器中有1的反之如果不一样就说明不存在了

那应用的场景在哪里呢？一般我们都会用来防止缓存穿透。简单来说就是你数据库的id都是1开始然后自增的，那我知道你接口是通过id查询的，我就拿负数去查询，这个时候，会发现缓存里面没这个数据，我又去数据库查也没有，一个请求这样，100个，1000个，10000个呢？你的DB基本上就扛不住了，如果在缓存里面加上这个，是不是就不存在了，你判断没这个数据就不去查了，直接return一个数据为空不就好了嘛。

Bloom Filter的缺点

bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性。

  • 存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。(hash 冲突的问题) 如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
  • 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter

Bloom Filter 实现

Guava 实现

布隆过滤器有许多实现与优化，Guava中就提供了一种Bloom Filter的实现。要使用BloomFilter，需要引入guava包：

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

测试分两步：

1、往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器

2、另外找一万个数，去检验漏网之鱼的数量

/**
 * 测试布隆过滤器(可用于redis缓存穿透)
 * 
 */
public class TestBloomFilter {

    private static int total = 1000000;
    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
//    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);

    public static void main(String[] args) {
        // 初始化1000000条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put(i);
        }

        // 匹配已在过滤器中的值，是否有匹配不上的
        for (int i = 0; i < total; i++) {
            if (!bf.mightContain(i)) {
                System.out.println("有坏人逃脱了~~~");
            }
        }

        // 匹配不在过滤器中的10000个值，有多少匹配出来
        int count = 0;
        for (int i = total; i < total + 10000; i++) {
            if (bf.mightContain(i)) {
                count++;
            }
        }
        System.out.println("误伤的数量：" + count);
    }

}

运行结果：

运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右

redis bitMap 实现

白名单数据初始化

package com.atguigu.redis7.filter;

import ch.qos.logback.classic.util.StatusViaSLF4JLoggerFactory;
import lombok.extern.slf4j.Slf4j;
import org.apache.ibatis.transaction.managed.ManagedTransaction;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;

import javax.annotation.PostConstruct;
import javax.annotation.Resource;

/**
 * @auther hll
 * @create 2022-12-27 14:55
 * 布隆过滤器白名单初始化工具类，一开始就设置一部分数据为白名单所有，
 * 白名单业务默认规定：布隆过滤器有，redis是极大可能有。
 * 白名单：whitelistCustomer
 */
@Component
@Slf4j
public class BloomFilterInit {
    
    @Resource
    private RedisTemplate redisTemplate;

    //@PostConstruct
    public void init() {
        //1 白名单客户加载到布隆过滤器
        String key = "customer:12";
        //2 计算hashValue,由于存在计算出来负数的可能，我们取绝对值
        int hashValue = Math.abs(key.hashCode());
        //3 通过hashValue和2的32次方后取余，获得对应的下标坑位
        long index = (long)(hashValue % Math.pow(2,32));
        log.info(key+" 对应的坑位index:{}",index);
        //4 设置redis里面的bitmap对应类型白名单：whitelistCustomer的坑位，将该值设置为1
        redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);

    }
}

查询逻辑

/**
     * BloomFilter → redis → mysql
     * 白名单：whitelistCustomer
     * @param customerId
     * @return
     */
    public Customer findCustomerByIdWithBloomFilter (Integer customerId) {
        Customer customer = null;
        String key = CACHA_KEY_CUSTOMER + customerId;

        //布隆过滤器check，无是绝对无，有是可能有
        if(!checkUtils.checkWithBloomFilter("whitelistCustomer",key)) {
            log.info("白名单无此顾客，不可以访问: "+key);
            return null;
        }
        customer = (Customer) redisTemplate.opsForValue().get(key);
        if (customer == null) {
            customer = customerMapper.selectByPrimaryKey(customerId);
            if (customer != null) {
                redisTemplate.opsForValue().set(key, customer);
            }
        }
        return customer;
    }

注意：虽然说还会有一部分垃圾请求到达数据库，但是请求数会大大降低，想完善这部分逻辑的话，可以考虑再维护一个黑名单，维护这些数据。

标签：mysql取绝对值 

作者:sishi88 , 分类:技术教程 , 浏览:7 , 评论:0

发表评论:

控制面板
您好，欢迎到访网站！
  查看权限
网站分类
最新留言
    友情链接