开篇

Redis + son 意思很明显，自诩 Redis 的儿子，不过也确实好用

这篇文章来介绍下可能不那么常见的，但是却非常好用的 3 个东西：BitSet/Bloomfilter/HperLogLog

BitMap

BitMap 可以用作签到、统计、用户状态等的处理

• 支持统计 1 的数量
• 支持统计某个偏移量是不是 1
• 支持多个 BitMap做And和OR等操作

除了最后一个功能，Set无法完全支持，其他都是可以支持的。那么为什么还需要BitSet了？原因是空间占用。

BitSet 不是 Redis 中的数据结构，其本质是String 的内部数据结构 Bit。我们可以理解为：一连串 Bit构成了String，每一个 Bit只能存储 0 和 1，同时有自己的偏移量，而Redis 可以根据偏移量对任何一个Bit进行 位操作。

Redis中 String 最大可以达到512M，根据这个公式：($offset/8/1024/1024)MB可以算出，offset最大为4,294,967,296，也就是2的32次方，所以 offset也不能大于这个值。

场景 1：会议签到

会议key为id，offset 是用户的 id(不能大于 2^32次方，建议自增的 id)

下面我们通过 代码来了解下这 3 个作用，在此之前我们先来创建一个redisson对象

companion object {
        private val config = Config().apply {
            this.useSingleServer()
                    .setAddress("redis://192.168.0.88:6379")
                    .setDatabase(9)
                    .setPassword("23457687")
            this.codec = StringCodec()
        }

        val redisson: RedissonClient = Redisson.create(config)
    }

下面的直接上代码，细节都在注释里面

@Test
    fun signInTest() {
        //创建 bitset 的时候，通过名字来确定`key`
        val bitSet = redisson.getBitSet("sign-0927")
        //其中 998 23 为模拟的用户 id
        bitSet.set(998)
        bitSet.set(23)
        bitSet.set(98432)
        //获取签到的人数
        val cardinality = bitSet.cardinality()
        println("签到人数:$cardinality")
        //判定某个具体的用户是否签到了
        println("98432签到结果为 ${bitSet.get(98432)}")
        println("123签到结果为 ${bitSet.get(123)}")
    }

其结果如下所示。

签到人数:3
98432签到结果为 true
123签到结果为 false

场景 2：APP 的消息提醒

假如 APP有消息提示框，用户有消息的时候，需要进行标记提醒。此时就可以使用BitSet直接存储有消息的标志，待用户点击消息标志的时候，才在数据库查询具体的消息，这样很节省资源。

假如某个消息提示框为notice:1，那么可以通过这个key创建一个 bitset，某用户有消息的时候，用户的ID作为offset并设置为 1，用户点击了消息提示框后，再通过这个ID的offset将其设置为0

场景 3：BitMap的与运算和或运算

待补充。。。

最佳实践：偏移量不能一个小，一个大，这样非常耗费性能。举个例子，你一上来就给便宜量设置为最大值，那么 521M的内存就直接占用了。所以更推荐通过自增的 ID来完成这个操作。

BloomFilter

这个就是鼎鼎大名的布隆过滤器，可以在数据量很大的时候，在一定偏差下，判定准确的不是或者不准确的是。

我们简单通过原理来理解下这个是或者不是的问题：将一个数通过多次 hash 处理后，算出一个偏移量，在一个数组上将对应的 index设置为 1，这个就是其原理。

• 那么对于同一个元素，通过相同的 hash处理后，肯定也会落到这个位置，所以假如对应的位置没有 1 那么肯定就是没有计算过着值
• 当数据量过多时，有概率存在不同的数，通过hash 处理后，落到数组的同一个位置。

接下来我们通过例子来判定学习下这个布隆过滤器用法。

例子：判定是否是新用户

假如业务要求：某个活动只能新用户能参与，此时你想怎么实现？

其中一个方法是采取上述提到的BitSet：参与过的用户的ID对应的偏移量设置为1。但是BitSet有限制，offset存在一个最大值限制，假如用户的 ID是通过SnowFlake生成的，那么就不能直接使用了。

此时可以考虑使用BloomFilter，来精准判定某个用户不是新用户，当是新用户的时候，再辅以其他手段来判定。

@Test
    fun testBloomFilter() {
        val bloomFilter = redisson.getBloomFilter<Long>("new-user").apply {
            //初始化：会存储的数据容量(4294967294)，期待的错误率
            this.tryInit(1000000,0.03)
        }
        val id1 = 1156040301344284674
        val id2 = 1156040301344284675
        val id3 = 1156040301344284676
        val id4 = 1156040301407199234

        bloomFilter.add(id1)
        bloomFilter.add(id2)
        bloomFilter.add(id3)
       
        assert(bloomFilter.contains(id1))
        assert(bloomFilter.contains(id2))
        assert(bloomFilter.contains(id3))
        println(bloomFilter.contains(id4))
    }

上述就是一个简单的使用bloomfilter的例子，注意几点

• 使用前必须初始化
  • 第一个参数是期待的数据容量，该值是有一个最大值的：4294967294
  • 第二参数是期待的错误率。
• 结果的可能性
  • 判定存在，那么可能是假的
  • 判定不存在，那么肯定是真的

缺点

• 布隆过滤器是只能插入元素，不能删除元素（BitSet是可以将某位置为 0 的）
• 布隆过滤器存在偏差，所以当判定为否的时候，可能还需要其他手段辅以判定。

同 BitSet 对比

• BloomFilter 是不可以删除元素的，BitSet 可以
• BitSet 的偏移量是有限的，BloomFilter 却不是
• BitSet 的结果是精准的，BloomFilter 却是存在偏差的
• BitSet 的复杂度不是恒订的，偏差值越大，时间复杂度越高。Bloomfilter 是恒定的

HyperLogLog

当进行统计的时候，小数量可以采用Set，没有超过2^32的数据时候可以使用Bitset，那么当数据超级大的时候，如何进行统计？

此时就需要这个HyperLogLog了，这个数据结构的原理很复杂，这文章只讲其使用场景、特点。

使用场景：大流量网站的 UV 统计。

特点：存在一定偏差，不过再超大流量下，这个完全可以忽略不计了。

@Test
    fun testHyperLogLog() {
        val hyperLogLog = redisson.getHyperLogLog<String>("uv-20200911")
        hyperLogLog.add("1156040301344284674")
        hyperLogLog.add("1156040301344284675")

        val uv = hyperLogLog.count()
        println(uv)
    }

结语

数据统计：Set -> BitSet -> HyperLogLog

是与否判定：Set -> BitSet ->BloomFilter