乐趣区

关于java:这么搞10-亿数据量只需要-100MB-内存

jiezi

送大家以下 java 学习材料


本文次要和大家分享一下 redis 的高级个性：bit 位操作。

本文 redis 试验代码基于如下环境：

操作系统：Mac OS 64 位 版本：Redis 5.0.7 64 bit 运行模式：standalone mode

redis 位操作

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

先来看一波基本操作示例：

SETBIT

语法：SETBIT key offset value

即：命令 key 偏移量 0/1

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

GETBIT

语法：GETBIT key offset

即：命令 key 偏移量

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

BITCOUNT

语法：BITCOUNT key

即：命令 key

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

BITOP

语法：BITOP operation destkey key [key…]

即：命令 操作 后果指标 key key1 key2 …

bitop 命令能够对多个位数组的 key 进行 and（按位与）、or（按位或）、xor（按位异或）运算，并将运算后果设置到 destkey 中：

底层数据结构剖析

===========

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

SDS 的数据结构：

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

数据存储示例：

SDS 的长处：

  1. 工夫复杂度为 O(1)
  2. 杜绝缓冲区溢出
  3. 缩小批改字符串长度时候所需的内存重调配次数
  4. 二进制平安的 API 操作
  5. 兼容局部 C 字符串函数

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

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

1Byte=8bit 1KB=1024Byte 1MB=1024KB 1GB=1024MB

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

`0 0 0 0 0 0 0 0`

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

`0 0 0 0 1 0 0 0`
`# 对应 redis 操作即：`
`setbit key 3 1`

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

`setbit key 13 1`
`# 对应 redis 中的存储为：`
`0 0 1 0 | 0 0 0 0 | 0 0 0 0 | 1 0 0 0`

工夫复杂度

GETBIT 命令工夫复杂度 O(1)

STEBIT 命令工夫复杂度 O(1)

BITCOUNT 命令工夫复杂度 O(n)

BITOP 命令工夫复杂度 O(n)、O(n2)

咱们来看 GETBIT 以及 SETBIT 命令的工夫复杂度为什么是 O(1)，当咱们执行一个 SETBIT key 10086 1 的值的时候，reids 的计算形式如下：

获取到要写入位数组中的哪个字节：10086÷8=1260，须要写入到位数组的下标 1260 的字节

获取要写入到这个字节的第几位：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

也就是存储 10 亿的数据只须要 119MB 左右的内存空间，这对于当初动辄 16G、32G 集群版的 redis，齐全没有问题。

须要留神的是，如果你的数据量不大，那就不要把起始偏移量搞的很大，这样也是占空间的，比方咱们只须要存储几百条数据，然而其中的偏移量却很大，这就会造成了很大的内存空间节约。

利用场景

理论我的项目开发中有很多业务都适宜采纳 redis 的 bit 来实现。

用户签到场景

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

沉闷用户数统计

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

同理月活也是如此。

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

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

APP 内用户的全局音讯提醒小红点

当初大多数的 APP 里都有站内信的性能，当有音讯的时候，则提醒一个小红点，代表用户有新的音讯。

源于：toutiao.com/i6767642839267410445

退出移动版