11）面对千万级别的 key 应该如何节省内存

楔子

在我们实际开发的过程中，可能会遇到这样一个问题，当我们需要统计不重复的元素个数时，应该用什么类型。举个简单的场景，统计大型网站每一天的 UV，注意是 UV（一个用户即使访问多次，也只能算作一次）。

面对这个问题，你可能首先会想到使用集合，将用户的 IP 保存到集合中。由于集合内的元素是不重复的，只需要统计出集合内的 IP 个数，不就能计算出 UV 了吗？

这显然是一个方法，但如果每天都有数千万级别的访问，那么内存能不能吃得消呢。以 IPV4 为例，一个 IPV4 最多需要 15 个字节存储，那么存储一千万个独立 IP 就需要大概 143MB 的内存。但这只是一个页面的统计信息，如果我们有 1 万个这样的页面，那就需要 1T 以上的空间来存储这些数据。

所以使用集合虽然简单方便，但它的内存成本很高，于是我们需要专门开发一种新的类型来做这件事，而该类型就是 HyperLogLog。

并且除了 HyperLogLog 之外，还有一种数据类型叫做 Bitmap（位图），也可以用来存储海量数据，我们分别来看一看。

HyperLogLog 的使用

HyperLogLog（以下简称为 HLL）是 Redis 2.8.9 版本添加的数据结构，它用于高性能的基数（去重）统计功能，它的缺点就是存在极低的误差率。

HLL 具有以下几个特点：

• 能够使用极少的内存来统计巨量的数据，它只需要 12K 空间就能统计 2^64 的数据；
  
• 统计存在一定的误差，误差率整体较低，标准误差为 0.81%；
  
• 误差可以被设置辅助计算因子进行降低；
  
  

HLL 的命令只有 3 个，但都非常的实用，下面分别来看。

添加元素

pfadd key element1 element2 ···，可以同时添加多个

127.0.0.1:6379> pfadd HLL_1 satori koishi
(integer) 1
127.0.0.1:6379> pfadd HLL_1 satori 
(integer) 0
127.0.0.1:6379> pfadd HLL_1 marisa
(integer) 1
127.0.0.1:6379>

统计不重复的元素个数

pfcount key1 key2 ···，可以同时统计多个 HHL 结构

127.0.0.1:6379> pfcount HLL_1
(integer) 3 # 不重复元素有 3 个
127.0.0.1:6379>

将多个HLL结构中的元素移动到新的HLL结构中

pfmerge key key1 key2 ···，将 key1、key2 ··· 里面的元素移动到 key 中

127.0.0.1:6379> del HLL_1
(integer) 1
127.0.0.1:6379> pfadd HLL_1 satori marisa koishi
(integer) 1
127.0.0.1:6379> pfadd HLL_2 satori scarlet sakuya
(integer) 1
# 注意 pfcount 统计多个 key 并不是独立统计
# 而是将这些 HLL 合在一起统计
127.0.0.1:6379> pfcount HLL_1 HLL_2
(integer) 5
# 将 HLL_1 和 HLL_2 合并到 HLL 中
# 并且 HLL_1 和 HLL_2 不受影响
127.0.0.1:6379> pfmerge HLL HLL_1 HLL_2
OK
# 总共元素个数为 5，结果符合预期
127.0.0.1:6379> pfcount HLL
(integer) 5
127.0.0.1:6379>

当我们需要合并两个或多个同类页面的访问数据时，我们可以使用 pfmerge 来操作，或者对这些数据整体使用 pfcount。

Python 实现 HLL 相关操作

import redis
client = redis.Redis(
    host="...", 
    decode_responses="utf-8")
client.delele("HLL_1", "HLL_2", "HLL")
# 1. pfadd key1 key2···
client.pfadd("HLL_1", "a", "b", "c")
client.pfadd("HLL_2", "b", "c", "d")
# 2. pfcount key1 key2···
print(client.pfcount("HLL_1", "HLL_2"))  # 4
# 3. pfmerge key key1 key2···
client.pfmerge("HLL", "HLL_1", "HLL_2")
print(client.pfcount("HLL"))  # 4

HyperLogLog 的实现原理

HyperLogLog 用起来没有任何难度，就几个命令而已，但它内部的原理是什么呢？该算法实际来源于一篇论文，想要了解它的原理，我们要先从伯努利实验说起。

伯努利实验指的是在同一条件下，重复地、相互独立地进行的一种随机试验，其特点是该随机试验只有两种可能结果：发生或者不发生。我们假设该项试验独立重复地进行了 N 次，那么就称这一系列重复独立的 N 次随机试验为 N 重伯努利试验，或称伯努利概型。

比如最经典、也是最好理解的场景：抛硬币，每一次抛出的硬币都是各自独立的，当前抛出的硬币在落地后，会是哪一面朝上，不受之前的影响。无论你上一次抛出的硬币是正面朝上、还是反面朝上，和本次抛出的硬币没有任何关系。

注意：单个伯努利试验是没有多大意义的，然而当我们反复进行试验，去观察这些试验有多少是成功的，多少是失败的，事情就变得有意义了，这些累计记录包含了很多潜在的非常有用的信息。

并且根据大数定理我们知道，如果一个事件发生的概率是恒定的，那么随着试验次数的增加，该事件发生的频率越接近概率。还拿抛硬币举例，假设抛硬币抛了四次，全是正面（这种情况是可能出现的），难道我们就说抛出一枚硬币，正面朝上的概率是百分之百吗？显然不能，而大数定理会告诉我们，只要你抛出硬币的次数足够多，你会发现正面出现的次数除以抛出的总次数（频率）会无限接近二分之一（概率）。

之所以说这些，是因为 Redis 采用的算法不是按照类似我们上面说的方式，因为大数定理对于数据量小的时候，会有很大的误差。而为了解决这个问题，HLL 引入了分桶算法和调和平均数来使这个算法更接近真实情况。

分桶算法：是指把原来的数据平均分为 m 份，在每段中求平均数再乘以 m，以此来消减因偶然性带来的误差，提高预估的准确性，简单来说就是把一份数据分为多份，将一轮计算变成多轮计算；

调和平均数：使用平均数的优化算法，而非直接使用平均数。例如小明的月工资是 1000 元，而小王的月工资是 100000 元，如果直接取平均数，那小明的平均工资就变成了 (1000 + 100000) / 2 = 50500‬ 元，这显然是不准确的，而使用调和平均数算法计算的结果是 2 / (1 / 1000 + 1 / 100000) ≈ 1998 元，显然此算法更符合实际平均数。

所以综合以上情况，在 Redis 中使用 HLL 插入数据，相当于把存储的值经过 hash 之后，再将 hash 值转换为二进制，存入到不同的桶中。这样就可以用很小的空间存储很多的数据，统计时再去相应的位置进行对比很快就能得出结论，这就是 HLL 算法的基本原理。想要更深入的了解算法及其推理过程，可以去看原版的论文，链接地址：

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

Bitmap 的实现原理

在工作中我们偶尔也会遇到类似下面这些场景：

• 查看某个用户当前是否在线；
  
• 查看某个员工当天是否打卡；
  
• ......
  
  

这些场景有一个类似的地方，就是它的取值只有两种。比如查看用户当前是否在线，要么在线，要么不在线，而统计这样的数据，我们称之为二值统计。

还是以用户是否在线为例，每个用户都有一个唯一的自增 ID，如果让你实现基于 ID 判断用户是否在线这个需求，你会怎么做呢？相信绝大部分人都会选择集合，将在线用户的 ID 都保存在集合中，这是最简单方便的做法，并且查询的时间复杂度是 O(1)。

或者使用一个数组，以用户的自增 ID 作为索引，如果对应的元素是 1，则代表在线；对应的元素是 0，则代表不在线。

但如果在面试的时候这么回答，那么不出意外，面试官一定会问你采用集合、数组有没有什么隐患，或者说还有没有其它的做法。

对于当前这个场景而言，如果用户量不大，那么是没问题的。但如果 DAU 达到了上千万级别，使用集合和数组就会非常的耗费内存。而面对这种情况，我们推荐使用位图。因为现代计算机操作数据默认都是以字节为单位，最小的类型也需要 1 字节，但表达 0 和 1 事实上只需要一个比特位就够了。举个例子：

// 数组 users 只有 8 个元素
// 理论上它最多只能判断 8 个用户是否在线
// 但如果是以 bit 为单位，那么能判断 64 个
static char users[8];

虽然 users 的长度为 8，但是它里面的 1 个元素我们可以当成 8 个元素来用，因此可以判断 64 个用户是否在线。比如当 ID 为 5 的用户上线了，只需要将第一个 char 的第 5 个比特位设置为 1 即可；当 ID 为 12 的用户上线了，只需要将第二个 char 的第 4 个字节设置为 1 即可。

如果下线了，那么将对应的比特位设置为 0 即可；而检测是否在线，只需要判断对应的比特位是否为 1 即可。

所以对于这种二值数据，非常适合用位图来统计。而 Redis 的位图就是基于 String 类型实现的统计二值状态的类型，它会把每个 char 的所有比特位都利用起来。

# 将 users 偏移量为 10 的位设置为 1
# 并返回该位设置之前的值
# 注意只能设置 0 或 1
# 并且偏移量从 0 开始
127.0.0.1:6379> SETBIT users 10 1
(integer) 0
127.0.0.1:6379> GETBIT users 10
(integer) 1
127.0.0.1:6379>

其中操作的每一个 bit 位叫做 offset，offset 可以非常大。

保存 2 的 30 次方个元素的状态，也只需要 130MB 的内存。所以如果要统计数据的二值状态，例如商品有没有、用户在不在等，就可以使用 Bitmap，因为它只用一个 bit 位就能表示 0 或 1。在记录海量数据时，Bitmap 能够有效地节省内存空间。

除了使用 Redis 之外，你也可以自己实现一个位图，这个非常简单，可以试一下。

小结

当需要做大量数据统计时，普通的集合类型已经不能满足我们的需求了，这个时候我们可以借助 Redis 2.8.9 中提供的 HyperLogLog 来统计。支持三个操作命令：pfadd 添加元素、pfcount 统计元素和 pfmerge 合并元素。

它的优点是只需要使用 12k 的空间就能统计 2^64 的数据，但它的缺点是存在 0.81% 的误差，因为它是基于概率实现的。这也意味着，如果你使用 HyperLogLog 统计的 UV 是 100 万，但实际的 UV 可能是 101 万。

如果能容忍这一点误差率，那么 HyperLogLog 非常适合；但如果你是需要精确统计结果的话，最好还是继续用 Set 或 Hash 类型。

而对于那些状态只有两种的数据，我们更推荐使用位图，特别是当数据量非常大的时候。