小功能大用处(下)

Bitmaps

数据结构模型

现代计算机用二进制(位)作为信息的基础单位，1 个字节等于 8 位，例如 "big" 字符串是由 3 个字节组成，但实际在计算机存储时将其用二进制表示，"big" 分别对应的 ASCII 码分别是 98、105、103，对应的二进制分别是 01100010、01101001 和 01100111

许多开发语言都提供了操作位的功能，合理地使用位能够有效地提高内存使用率和开发效率。
Redis 提供了 Bitmaps 这个 "数据结构" 可以实现对位的操作。
把数据结构加上引号主要因为:

Bitmaps 本身不是一种数据结构，实际上它就是字符串，但是它可以对字符串的位进行操作
Bitmaps 单独提供了一套命令，所以在 Redis 中使用 Bitmaps 和使用字符串的方法不太相同。可以把 Bitmaps 想象成一个以位位单位的数组，数组的每个单元只能存储 0 和 1，数组的下标在 Bitmaps 中叫做偏移量

命令

本节将每个独立用户是否访问过网站存放在 Bitmaps 中，将访问的用户记做 1，没有访问的用户记做 0，用偏移量作为用户的 id

设置值

setbit key offset value

设置键的第 offset 个位的值(从 0 算起)，假设现在有 20 个用户，userid=0,5,11,15,19 的用户对网站进行了访问，那么当前 Bitmaps 初始化结果如图所示:

具体操作过程如下，unique:users:2016-04-05 代表 2016-04-05 这天的独立访问用户的 Bitmaps:

127.0.0.1:6379> setbit unique:users:2016-04-05 0 1
(integer) 0
127.0.0.1:6379> setbit unique:users:2016-04-05 5 1
(integer) 0
127.0.0.1:6379> setbit unique:users:2016-04-05 11 1
(integer) 0
127.0.0.1:6379> setbit unique:users:2016-04-05 15 1
(integer) 0
127.0.0.1:6379> setbit unique:users:2016-04-05 19 1
(integer) 0

如果此时有一个 userid=50 的用户访问了网站，那么 Bitmaps 的结构变成了下图，第 20位到 49位都是 0

很多应用的用户 id 以一个指定数字(例如 10000)开头，直接将用户 id 和 Bitmaps 的偏移量对应势必会造成一定的浪费，通常的做法是每次做 setbit 操作时将用户 id 减去这个指定数字.
在第一次初始化 Bitmaps 时，假如偏移量非常大，那么整个初始化过程会比较慢，可能会造成 Redis 的阻塞

获取值

getbit key offset

获取键的第 offset 位的值(从 0 开始算)，下面操作获取 id=8 的用户是否在 2016-04-05 这天访问过，返回 0 说明没有访问过:

1 2	`127.0.0.1:6379> getbit unique:users:2016-04-05 8 (integer) 0`

由于 offset=1000000 根本不存在，所以返回结果也是 0:

1 2	`127.0.0.1:6379> getbit unique:users:2016-04-05 1000000 (integer) 0`

获取 Bitmaps 指定范围值位 1 的个数

bitcount [start] [end]

下面操作计算 2016-04-05 这天的独立访问用户数量:

1 2	`127.0.0.1:6379> bitcount unique:users:2016-04-05 (integer) 5`

[start] 和 [end] 代表起始和结束字节数，下面操作计算用户 id 在第 1 个字节到第 3 个字节之间的独立访问用户数，对应的用户 id 是 11,15,19

1 2	`127.0.0.1:6379> bitcount unique:users:2016-04-05 1 3 (integer) 3`

Bitmaps 间的运算

bitop op destkey key [key...]

bitoop 是一个复合操作，它可以做多个 Bitmaps 的 and(交集)、or(并集)、not(非)、xor(异或)操作并将结果保存在 destkey 中。
假设 2016-04-04 访问网站的 userid =1,2,5,9

下面操作计算出 2016-04-04 和 2016-04-03 两天都访问过网站的用户数量:

127.0.0.1:6379> bitop and unique:users:and:2016-04-04_03 unique:users:2016-04-03 unique:users:2016-04-04
(integer) 2
127.0.0.1:6379> bitcount unique:users:and:2016-04-04_03
(integer) 2

如果想算出 2016-04-04 和 2016-04-03 任意一天访问过网站的用户数量(例如月活跃就是类似这种)，可以使用 or 求并集，具体命令如下:

bitop or unique:users:or:2016-04-04_03 unique:users:2016-04-03 unique:users:2016-04-04
6
127.0.0.1:6379> bitcount unique:users:or:2016-04-04_03
(integer) 6

计算 Bitmaps 中第一个值为 targetBit 的偏移量

bitpos key targetBit [start] [end]

下面操作计算 2016-04-04 当前访问网站的最小用户 id:

1 2	`127.0.0.1:6379> bitpos unique:users:2016-04-05 1 (integer) 1`

除此之外，bitpos 有两个选项 [start] 和 [end]，分别代表起始字节和结束字节，例如计算第 0 个字节到第 1 个字节之间，第一个值为 0 的偏移量:

1 2	`127.0.0.1:6379> bitpos unique:users:2016-04-05 0 0 1 (integer) 1`

Bitmaps 分析

假设网站有 1 亿用户，每天独立访问的用户有 5 千万，如果每天用集合类型和 Bitmaps 分别存储活跃用户

这种情况下使用 Bitmaps 能节省很多的内存空间，尤其是随着时间推移节省的内存还是非常可观的

但 Bitmaps 并不是万金油，假如该网站每天的独立访问用户很少，假如只有 10 万(大量的僵尸用户)，这时候使用 Bitmaps 就不太合适了，因为基本上大部分位都是 0

HyperLogLog

HyperLogLog 并不是一种新的数据结构(实际类型为字符串类型)，而是一种基数算法，通过 HyperLogLog 可以利用极小的内存空间完成独立总数的统计，数据集可以是 IP、Email、ID 等。
HyperLogLog 提供了 3 个命令: pfadd、pfcount、pfmerge。

小功能大用处(下)

Bitmaps

数据结构模型

命令

Bitmaps 分析

HyperLogLog

GEO