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

简介

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

Guava中的Bloom Filter, Bloom Filter是一种省内存的基于概率的数据结构，可判断一个元素是否在集合中。

Bloom Filter实现思路

位数组和k个散列函数

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

2.添加元素（k个独立的hash函数）
添加元素时，对x使用k个哈希函数得到k个哈希值，对m取余，对应的bit位设置为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。

二进制数据的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 可以指定多个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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()));
    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

使用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