本文共 5112 字，大约阅读时间需要 17 分钟。

1.Bitmaps

1.数据结构模型

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

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

本节将每个独立用户是否访问过网站存放在Bitmaps中， 将访问的用户记做1， 没有访问的用户记做0， 用偏移量作为用户的id。 1.设置值 setbit key offset value 设置键的第offset个位的值（从0算起） ， 假设现在有20个用户，userid=0， 5， 11， 15， 19的用户对网站进行了访问， 那么当前Bitmaps初始化结果如图3-11所示。

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

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

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

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

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

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

3.获取Bitmaps指定范围值为1的个数

bitcount [start][end] 下面操作计算2016-04-05这天的独立访问用户数量：

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

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

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

4.Bitmaps间的运算

bitop op destkey key[key....] bitop是一个复合操作， 它可以做多个Bitmaps的and（交集） 、 or（并集） 、 not（非） 、 xor（异或） 操作并将结果保存在destkey中。 假设2016-04-04访问网站的userid=1， 2， 5， 9， 如图3-13所示。

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

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

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

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

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

bitpos key targetBit [start] [end]

127.0.0.1:6379> bitpos unique:users:2016-04-04 1(integer) 1127.0.0.1:6379> bitpos unique:users:2016-04-04 0 0 1(integer) 0

5.3 Bitmaps分析

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

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

但Bitmaps并不是万金油， 假如该网站每天的独立访问用户很少， 例如只有10万（大量的僵尸用户） ， 那么两者的对比如表3-5所示， 很显然， 这时候使用Bitmaps就不太合适了， 因为基本上大部分位都是0。

 

2.HyperLogLog

HyperLogLog并不是一种新的数据结构（实际类型为字符串类型） ， 而是一种基数算法， 通过HyperLogLog可以利用极小的内存空间完成独立总数的统计， 数据集可以是IP、 Email、 ID等。

HyperLogLog提供了3个命令：pfadd、 pfcount、 pfmerge。 例如2016-03-06的访问用户是uuid-1、 uuid-2、uuid-3、 uuid-4， 2016-03-05的访问用户是uuid-4、 uuid-5、 uuid-6、 uuid-7， 如 图3-15所示

1.添加

pfadd key element [element …] pfadd用于向HyperLogLog添加元素， 如果添加成功返回1：

127.0.0.1:6379> pfadd 2016_03_06:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"(integer) 1

2.计算独立用户数

pfcount key [key …] pfcount用于计算一个或多个HyperLogLog的独立总数， 例如2016_03_06： unique： ids的独立总数为4：

127.0.0.1:6379> pfcount 2016_03_06:unique:ids(integer) 4

如果此时向2016_03_06： unique： ids插入uuid-1、 uuid-2、 uuid-3、 uuid-90， 结果是5（新增uuid-90） ：

127.0.0.1:6379> pfadd 2016_03_06:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-90"(integer) 1127.0.0.1:6379> pfcount 2016_03_06:unique:ids(integer) 5

当前这个例子内存节省的效果还不是很明显， 下面使用脚本向

HyperLogLog插入100万个id， 插入前记录一下info memory：

127.0.0.1:6379> info memory# Memoryused_memory:835144used_memory_human:815.57K...向2016_05_01:unique:ids插入100万个用户， 每次插入1000条：elements=""key="2016_05_01:unique:ids"for i in `seq 1 1000000`doelements="${elements} uuid-"${i}if [[ $((i%1000)) == 0 ]];thenredis-cli pfadd ${key} ${elements}elements=""fidone

当上述代码执行完成后， 可以看到内存只增加了15K左右：

127.0.0.1:6379> info memory# Memoryused_memory:850616used_memory_human:830.68K

但是， 同时可以看到pfcount的执行结果并不是100万：

127.0.0.1:6379> pfcount 2016_05_01:unique:ids(integer) 1009838

可以对100万个uuid使用集合类型进行测试， 代码如下：

elements=""key="2016_05_01:unique:ids:set"for i in `seq 1 1000000`doelements="${elements} "${i}if [[ $((i%1000)) == 0 ]];thenredis-cli sadd ${key} ${elements}elements=""fidone

可以看到内存使用了84MB：

127.0.0.1:6379> info memory# Memoryused_memory:88702680used_memory_human:84.59M

但独立用户数为100万：

127.0.0.1:6379> scard 2016_05_01:unique:ids:set(integer) 1000000

表3-6列出了使用集合类型和HperLogLog统计百万级用户的占用空间对比

可以看到， HyperLogLog内存占用量小得惊人， 但是用如此小空间来估算如此巨大的数据， 必然不是100%的正确， 其中一定存在误差率。 Redis官方给出的数字是0.81%的失误率。

3.合并 pfmerge destkey sourcekey [sourcekey ...] pfmerge可以求出多个HyperLogLog的并集并赋值给destkey， 例如要计算2016年3月5日和3月6日的访问独立用户数， 可以按照如下方式来执行， 可以看到最终独立用户数是7：

127.0.0.1:6379> pfadd 2016_03_06:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"(integer) 1127.0.0.1:6379> pfadd 2016_03_05:unique:ids "uuid-4" "uuid-5" "uuid-6" "uuid-7"(integer) 1127.0.0.1:6379> pfmerge 2016_03_05_06:unique:ids 2016_03_05:unique:ids2016_03_06:unique:idsOK127.0.0.1:6379> pfcount 2016_03_05_06:unique:ids(integer) 7

HyperLogLog内存占用量非常小， 但是存在错误率， 开发者在进行数据

结构选型时只需要确认如下两条即可： ·只为了计算独立总数， 不需要获取单条数据。 ·可以容忍一定误差率， 毕竟HyperLogLog在内存的占用量上有很大的优势。

 

备注：文章参考《Redis开发与运维》，作者：付磊，张益军

 

 

 

 

 

 

 

 

 

转载地址：http://xnyab.baihongyu.com/