Knightdreams'Blog

Appearance

redis位操作 ​

reids位操作也叫位数组操作、bitmap

它提供了SETBIT、GETBIT、BITCOUNT、BITTOP四个命令用于操作二进制位数组。

SETBIT ​

语法：SETBIT key offset value

setbit命令用于写入位数组指定偏移量的二进制位设置值,偏移量从0开始计数，且只允许写入1或者0，如果写入非0和1的值则写入失败：

shell
127.0.0.1:6379> setbit bitkey 0 1
(integer) 0
# 数据存储为: 0000 0001
127.0.0.1:6379> setbit bitkey 10 1
(integer) 0
# 数据存储为: 0000 0100 0000 0001

# 写入非0/1的值
127.0.0.1:6379> setbit key2 0 2
(error) ERR bit is not an integer or out of range
GETBIT ​

语法：GETBIT key offset 即：命令key的偏移量

gitbit命令用于获取位数组指定偏移量上的二进制值：

shell
127.0.0.1:6379> getbit bitkey 0
(integer) 1
# 数据存储如下
# 0000 0001
BITCOUNT ​

语法：BITCOUNT key

bitcount命令用于获取指定key的位数组中值为1的二进制位的数量，之前我们写入了偏移量0的值为1，偏移量10 的值为1，偏移量8的值为0：

shell
127.0.0.1:6379> bitcount bitkey
(integer) 2
# 数据存储如下
# 0000 0100 0000 0001
BITOP ​

语法：BITOP operation destkey key [key...]

即：命令 操作 结果 目标key key1 key2...

bitop命令可以对多个位数组的key进行and（按位与）、or（按位或）、xor（按位异或）运算，并将运算结果设置到destKey中

shell
127.0.0.1:6379> setbit key1 0 1
(integer) 1
127.0.0.1:6379> setbit key1 1 1
(integer) 0
# key1 = 0000 0011

127.0.0.1:6379> setbit key2 0 0
(integer) 0
127.0.0.1:6379> setbit key2 2 1
(integer) 0
# key2 = 0000 0100

# 按位与操作
127.0.0.1:6379> bitop and andKey key1 key2
(integer) 1
# key1 0000 0011
# key2 0000 0100
# andKey 0000 0000

127.0.0.1:6379> getbit andKey 1
(integer) 0

底层数据结构分析 ​

SDS是redis中的一种数据结构，叫做简单动态字符串（Simple Dynamic String），并且是一种二进制安全的，在大多数情况下redis中的字符串都用SDS来存储

c
struct sdshdr {
    // 记录buff数组中已使用字节的数量
    // 也是SDS所保存字符串的长度
    int len;
    
    // 记录buff数组中未使用字节的数量
    int free;
    
    // 字节数组，字符串就存储在这个数组中
    char buff[];
}

SDS的优点：

  • 时间复杂度为 O(1)
  • 杜绝缓冲区溢出
  • 减少修改字符串长度时所需的内存重分配次数
  • 二进制安全的api操作
  • 兼容部分C字符串函数

redis中的位数组采用的是String字符串数据格式来存储，而字符串对象使用的正是上文说的SDS简单动态字符串数据结构。

一个字节用的是8个二进制位来存储的，也就是8个0或者1，即一个字节可以存储十进制0~127的数字，也即包含了所有的数字、英文大小写字母以及标点符号。

shell
1Byte = 8bit
1KB = 1024Byte

位数组在redis的存储中，每一个字节也是8位，初始都是：

shell
0000 0000

而位操作就是在对应的offset偏移量上设置0或者1，比如将第3位设置为1：即

shell
0000 1000
# 对应的redis操作
setbit key 3 1

在此基础上，如果要在偏移量为13的位置设置1，即：

shell
setbit key 13 1
# 对应的存储为
0010 0000 0000 1000

时间复杂度 ​

  • GETBIT 命令时间复杂度为 O(1)
  • SETBIT 命令时间复杂度为 O(1)
  • BITCOUNT 命令时间复杂度 O(n)
  • BITOP 命令时间复杂度 O(n)、O(n2)

我们来看GETBIT以及SETBIT命令的时间复杂度为什么是O(1)，

当我们执行一个SETBIT key 10086 1的值的时候，reids的计算方式如下：

  1. 获取到要写入位数组中的哪个字节：10086÷8=1260，需要写入到位数组的下标1260的字节
  2. 获取要写入到这个字节的第几位：10086 mod 8 = 6，需要写入到这个字节的下标为6即第7位上去。

通过这两种计算方式大家可以清晰的看到，位操作的GETBIT和SETBIT都是常量计算，因此它的时间复杂度为O(1)。

而BITCOUNT命令需要对整个位数组的所有元素进行遍历算出值为1的有多少个，当然redis对于大数据的bit执行bitcount命令会有一整套复杂的优化的算法，但是核心思路还是这个意思，无非是减少部分遍历查询次数。比如以128位为一次遍历，那么他的遍历次数就是所有的位数除以128。

BITTOP命令则是根据不同的操作有不同的执行方式。比如AND操作，则需要查看位值为1的即可。

存储空间计算 ​

根据上面的介绍，相信大家已经知道了基于redis的位数组数据结构存储的数据占用内存大小是怎么计算的了。比如有100亿的数据，那么它需要的字节数组：

1000000000÷8÷1024÷1024≈119.21MB

需要注意的是，如果你的数据量不大，那就不要把起始偏移量搞的很大，这样也是占空间的，比如我们只需要存储几百条数据，但是其中的偏移量却很大，这就会造成了很大的内存空间浪费。

应用场景 ​

实际项目开发中有很多业务都适合采用redis的bit来实现。

用户签到场景 ​

每天的日期字符串作为一个key，用户Id作为offset，统计每天用户的签到情况，总的用户签到数

活跃用户数统计 ​

用户日活、月活、留存率等均可以用redis位数组来存储，还是以每天的日期作为key，用户活跃了就写入offset为用户id的位值1。

同理月活也是如此。

用户是否在线以及总在线人数统计 ​

同样是使用一个位数组，用户的id映射偏移量，在线标识为1，下线标识为0。即可实现用户上下线查询和总在线人数的统计

APP内用户的全局消息提示小红点 ​

现在大多数的APP里都有站内信的功能，当有消息的时候，则提示一个小红点，代表用户有新的消息。