首页 > 编程语言 > 聊聊Redis二进制数组Bitmap
2021
10-25

聊聊Redis二进制数组Bitmap

好久没有更新了,之前公司在做 关注/粉丝 这块儿缓存的时候,我选择的就是 Bitmap ,那时是我第一次见识到这种数据数组形式,用到的有 SETBIT , GETBIT , BITCOUNT ,命令如何使用就不说了,今天来仔细看看这三个命令的实现和原理。

选用 bitmap 的考量:

位数组的实现

关注关系需求中 关注对象 和 被关注人 都是 0-几千万 的数据对象,存储这种对应关系时,采用bitmap 这种位数组,明显要比 uid 的 set 方式要节省存储空间,redis 的 内存 是很宝贵的,这值得作为考量的地方。

位数组大致可表示为:0101010000100000....0100 这样的二进制串, 在 Redis 的 SDS字符串 一文中可以看到 Redis 中的字符串对象实现,SDS数据结构是二进制安全的,所以 Redis 可以使用字符串来表示 位数组 。 所以根据上面说的,位数组是以字符串的形式:buf[0]|buf[1]...这样一个一个字节存放的。

SETBIT 和 GETBIT

GETBIT 的实现:

  # 返回 位数组 bitarray 在 offset 偏移量上的二进制位(byte*8+bit)的值
  getbit <bitarray> <offset>
  # 字节
  byte = offset / 8  
  # 位
  bit = (offset mod 8) + 1
  # 可以看到 O(1)

SETBIT 的实现:

  # 将 位数组 bitarray 在offset 偏移量上的二进制位的值设置为 value
  setbit <bitarray> <offset> <value>
  # 计算保存二进制位需要多少 字节
  len = [offset / 8] + 1 
  # 鱿鱼 ? 二进制位数组使用的数据结构是 sds ,而 sds 记录长度的是len ,正常进行扩展,同空间预分配 ,扩展位为`00000`
  # 字节
  byte = offset / 8  
  # 位
  bit = (offset mod 8) + 1 
  # 记录 (byte*8+bit) 上 oldvalue ,再赋予新值,返回 oldvalue

Bitcount 的实现

BITCOUNT 统计给定位数组中,值为1 的数量,也就是统计汉明重量(见 Leetcode 191、338),其实是一个老问题,看看几种算法,和 redis 的做法。

#1. 粗暴遍历 O(n)

class Solution(object):
    def hammingWeight(self, n):
        rst = 0
        mask = 1
        for i in range(32):
            if n & mask :
                rst += 1
            mask = mask << 1
        return  rst
        
#2. 查表法 
# 查表法原理在于建立N个位数组,如果是8位,即减少查询次数/8 ,建表越大,则查询次数越少
# 空间换时间的典型操作,不禁让我想起了 计数排序O(n+k) 
# 内存考虑:这里可以算一下 8位的查表耗费的内存百字节,16位查表为百Kb,32位为十多个G,实际中,服务器只能接受16位
# CPU考虑:表长越大,miss 率越大。而 max 为16 也不能解决大数组的查表效率问题
# 这种算法 O(n/m) S(m) m<=16 

#3.variable-precision SWAR 算法 O(1)

#4.Redis 
# redis 未处理的二进制数 >= 128,使用variable-precision SWAR
# redis 未处理的二进制数 < 128,使用 查表法

Redis-高性能bitmap

实时指标

Redis bitmap可用于快速、简单的实现实时指标。

传统情况下,由批量job生成指标数据。但是redis的bitmap支持实时指标计算,而且具有极高的空间利用率。例如1.28亿用户,实时统计日UV,仅仅占用16MB内存空间,在mbp上耗时50ms。

bitset

可视为由0和1组成的数组。在bitset中的每个bit可为0或1,使用offset表示bit在数组的位置。支持多个bitset间进行位操作,如与或非等。

群体统计

bitset的群体统计表示bitset中数据为1的bit数量。使用bitset做群体统计是非常高效的。如具有十亿bit的bitset,其90%空间已设置数据,在mbp上进行群体统计仅耗时几十或几百ms。

redis bitmap

bitmap是二进制数据,可通过set key offset val指令设置具体offset位置bit的数据,且时间复杂度为O(1)。

日活用户

针对关注点(某个页面或某个操作),统计活跃用户数量。

key规则:关注点名称+日时间戳

val:创建bitmap,宽度为当前用户数量,每个用户的id作为offset,这个用户ID是记录ID,不可能是由特定规则生成的userID。

当用户访问关注点时,针对具体bitset,将用户IDoffset位置数据设置为1。之后对该bitset进行群体统计,即为关注点的日活用户量。

采取关注点名称+时间戳的方式,可以存储不同时间维度的活跃用户。

如每小时播放音乐的用户量,key定义为play_yyyyMMddhh;每天播放音乐的用户量,key定义为play_yyyyMMdd。

当需要统计较大时间范围的用户量时,可以先对多个bitset求并集,然后再群体统计,如统计一周、一个月的用户量。

性能对比

1.28亿用户,使用bitset记录日活,使用日活并集统计7日 15日日活。
PERIOD TIME (MS)
Daily 50.2
Weekly 392.0
Monthly 1624.8

特性分析

周维度访问关注点且绑定手机号的唯一用户,采用绑定手机号用户bitset 交集 周维度访问关注点的用户bitset

最近n天唯一用户量的滚动统计,对最近n天每天的日活用户bitset求并集

涉及的指令

群体统计使用bitcount key

交集并集使用bitop and/or dest key1 keyn

对用户IDoffset设置数据使用setbit key offset 1

java bitset.cardinality()/and(bitset)/or(bitset)

以上为个人经验,希望能给大家一个参考,也希望大家多多支持自学编程网。

编程技巧