好久没有更新了，之前公司在做 关注/粉丝 这块儿缓存的时候，我选择的就是 Bitmap ，那时是我第一次见识到这种数据数组形式，用到的有 SETBIT , GETBIT , BITCOUNT ，命令如何使用就不说了，今天来仔细看看这三个命令的实现和原理。
选用 bitmap 的考量：
位数组的实现
关注关系需求中 关注对象 和 被关注人 都是 0-几千万 的数据对象，存储这种对应关系时，采用bitmap 这种位数组，明显要比 uid 的 set 方式要节省存储空间，redis 的 内存 是很宝贵的，这值得作为考量的地方。
位数组大致可表示为：0101010000100000....0100 这样的二进制串， 在 Redis 的 SDS字符串 一文中可以看到 Redis 中的字符串对象实现，SDS数据结构是二进制安全的，所以 Redis 可以使用字符串来表示 位数组 。 所以根据上面说的，位数组是以字符串的形式：buf[0]|buf[1]...这样一个一个字节存放的。
SETBIT 和 GETBIT
GETBIT 的实现：
|
1
2
3
4
5
6
7
|
# 返回 位数组 bitarray 在 offset 偏移量上的二进制位(byte*8+bit)的值getbit <bitarray> <offset># 字节byte = offset / 8 # 位bit = (offset mod 8) + 1# 可以看到 O(1) |
SETBIT 的实现：
|
1
2
3
4
5
6
7
8
9
10
|
# 将 位数组 bitarray 在offset 偏移量上的二进制位的值设置为 valuesetbit <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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#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
|
1
|
java bitset.cardinality()/and(bitset)/or(bitset) |
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。
原文链接：https://siwei.blog.csdn.net/article/details/88698399
