BloomFilter使用和redis的setbit、bitcount实现用户上线次数统计

男娘i 2023-06-07 08:21 7阅读 0赞

## 简介 ##

BloomFilter过滤器可以快速判断某值是否存在，虽然不一定准确，但是相对而且它既快速而且又相对准确。  
Bloom Filter没有False Negative,即判断某元素时否在Bloom Filter中时，如果返回False, 则可以肯定该元素不在集合中，但是Bloom Filter存在False Positive, 即如果返回True, 并不能完全肯定元素就在集合中，但是有很大的概率确实在集合中。

## BloomFilter算法 ##

*  简介：布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
 *  原理：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。
 *  优点：相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。而且它不存储元素本身，在某些对保密要求非常严格的场合有优势。
 *  缺点：一定的误识别率和删除困难。  
    结合以上几点及去重需求（容忍误判，会误判在，在则丢，无妨），决定使用BlomFilter。

如何根据输入元素个数n，确定位数组的大小m和哈希函数的个数k?  
https://blog.csdn.net/qq\_18495465/article/details/78500472  
![在这里插入图片描述][70]  
Guava中的Bloom Filter, Bloom Filter是一种省内存的基于概率的数据结构，可判断一个元素是否在集合中。

### Bloom Filter实现思路 ###

位数组和k个散列函数

1.位数组  
初始状态时，BloomFilter是一个长度为m的位数组，每一位都置为0。这个结构刚和和redis的bitMap相同，当然也和Java自带的bitSet结构相似，唯一不同在于一个中间件存储数据量多，一个Java内存的数据量少。  
![在这里插入图片描述][SouthEast]

2.添加元素（k个独立的hash函数）  
添加元素时，对x使用k个哈希函数得到k个哈希值，对m取余，对应的bit位设置为1。  
![在这里插入图片描述][SouthEast 1]  
这里和Java的单个hash不同，它会经历2个以上不同质数hash函数，对应到不同的bit位，如上图两个个hash函数值对应的x1,x2分别对应到不同的bit位。多层hash的目的就在于避免单次hash造成的bit位相同，从而影响判断结果，因此它也无法保证结果是一定的，只能做到尽量符合预期结果。

3.判断元素是否存在  
判断y是否属于这个集合，对y使用k个哈希函数得到k个哈希值，对m取余，所有对应的位置都是1，则认为y属于该集合（哈希冲突，可能存在误判），否则就认为y不属于该集合。  
图中y1不是集合中的元素，y2属于这个集合或者是一个false positive。  
![在这里插入图片描述][SouthEast 2]  
二进制数据的bit位异或操作很容易就能判断是全1的真还是假，因此速度很快，不用像字符串判断中需要一个一个的做对比。当然问题依然存在就是如果两个不同字符串多次hash的值依然相同的问题，只要数据量足够大这样的结果仍然会出现，只是概率问题。因此BloomFilter只能做到尽量合乎预期而不能做到完全一致。

BloomFilter有以下参数:

*  m 位数组的长度
 *  n 加入其中元素的数量
 *  k 哈希函数的个数
 *  f False Positive失败概率

## BitMap是什么 ##

就是通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身。我们知道8个bit可以组成一个Byte，所以bitmap本身会极大的节省储存空间。

Redis中的BitMap  
Redis从2.2.0版本开始新增了setbit,getbit,bitcount等几个bitmap相关命令。虽然是新命令，但是并没有新增新的数据类型，因为setbit等命令只不过是在set上的扩展。

setbit基本操作

redis> SETBIT bit 0 1  # 0001
    (integer) 0
    
    redis> GETBIT bit 3 1 # 1001
    (integer) 1
    
    redis> GETBIT bit 100   # bit 默认被初始化为 0
    (integer) 0
    
    redis> BITCOUNT bits  # bit中又多少个1
    (integer) 1
    
    
    BITOP operation resultKey key1 key2。operation 是位运算的操作，有 AND，OR，XOR，NOT。resultKey 是把运算结构存储在这个 key 中，key1 和 key2 是参与运算的 key，参与运算的 key 可以指定多个。

setbit的offset是用大小限制的，在0到 232（最大使用512M内存）之间，即0~4294967296之前，超过这个数会自动将offset转化为0，因此使用的时候一定要注意。

https://www.runoob.com/redis/strings-setbit.html

## 使用场景 ##

使用场景一：用户签到  
使用场景二：统计活跃用户  
使用场景三：用户在线状态  
用户日活，月活,留存率的统计

统计活跃用户为例  
每个用的key:"REPORT:1"对应的bit位010001中的1则对应具体某天的签到状态  
总共签到天数：bitcount REPORT:1  
时间段内的签到天数：获取index为\[start,end\]的bit位统计1的个数  
判断当天是否已经签到：getbit REPORT:1 offset

/**
     * @program: demo
     * @description: redisTest
     * @author: Bamboo zjcjava@163.com
     * @create: 2019-10-13 23:07
     **/
    
    @RunWith(SpringRunner.class)
    @SpringBootTest(classes = DemoApplication.class)
    public class SpringRedisTest {
    
        @Autowired
        private RedisClient redisClientCache;
    
        private JedisPool jedisPool;
    
        @Test
        public  void test() {
    
        // 用户ua的活跃时间
            addCount("ua","20191011");
            addCount("ua","20191012");
            addCount("ua","20191013");
            addCount("ua","20191014");
    
            
            uniqueCount("ua","20191011");
            uniqueCount("ua","20191009");
            uniqueCount("ua","20191011","20191012");//两个日期内的活跃次数
            totalCount("ua");//总活跃次数
        }
    
    
        //某个用户在某天是否活跃
        public void addCount(String action, String date) {
            Jedis jedis = redisClientCache.getJedis();
            String key = "REPORT:"+action ;
            jedis.setbit(key.getBytes(),Long.valueOf(date),true);
            jedis.close();
        }
    
        //判断某个用户操作在某天是否活跃
        public void uniqueCount(String action, String date) {
            Jedis jedis = redisClientCache.getJedis();
            String key = "REPORT:"+action ;
    
            System.out.println("某个用户操作在某天是否是活跃用户"+date+"--- " +jedis.getbit(key.getBytes(),Long.valueOf(date)));
            jedis.close();
        }
    
    
        //下面的Java代码用来统计某个用户操作在一个指定多个日期的活跃次数。
        public void uniqueCount(String action, String... dates) {
            Jedis jedis = redisClientCache.getJedis();
            BitSet all = new BitSet();
            String key = "REPORT:"+action ;
            BitSet users = BitSet.valueOf(jedis.get(key.getBytes()));
            all=users.get(Integer.valueOf(dates[0]),Integer.valueOf(dates[1])+1);
            jedis.close();
            System.out.println("多个日期的活跃次数--- " +all.cardinality());
        }
    
        //统计某个用户总共活跃次数。
        public void totalCount(String action) {
            Jedis jedis = redisClientCache.getJedis();
            String key = "REPORT:"+action ;
            jedis.close();
            System.out.println("总活跃次数--- " +jedis.bitcount(key.getBytes()));
        }
    
    }

使用Redis统计UV数据-HyperLogLog  
pfadd:新增  
pfcount:获取总数

未完待续…进行中

## 参考资料 ##

https://blog.csdn.net/lglgsy456/article/details/39394961  
https://blog.csdn.net/z834410038/article/details/73882000  
segmentfault.com/a/1190000008188655  
my.oschina.net/go4it/blog/1975878  
blog.csdn.net/jinjiating/article/details/91885978

[70]: /images/20230601/7c0ad2aaef3d4305a43642fa69a715cf.png
[SouthEast]: /images/20230601/a8d8ad2004424bbdaebff38bb25a6eb6.png
[SouthEast 1]: /images/20230601/130c34165c8342e393894106ba43c08a.png
[SouthEast 2]: /images/20230601/d1f6db5c6c064e7a97b8f723c6f6709b.png