Redis二进制数组Bitmap

超、凢脫俗 2022-03-02 15:40 179阅读 0赞

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

## 选用 bitmap 的考量： ##

### 位数组的实现 ###

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

位数组大致可表示为：`0101010000100000....0100` 这样的二进制串， 在 [Redis 的 SDS字符串][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 _ SDS]: https://blog.csdn.net/qq_28018283/article/details/80758929