问题
如何用redis存储统计1亿用户一年内的登录情况，并快速检索任意时间窗口内的活跃用户数量？
分析
Redis 是一个内存数据库，采用单线程和事件驱动的机制来处理网络请求。实际生产的QPS和TPS单台都能达到 3~4 w，读写性能非常棒,用来存储一些对核心业务弱影响的用户状态信息还是非常不错的。
对于这个问题，有2个重要的点需要考虑：
如何选择合适的数据类型来存储 1 亿用户的数据？
用普通的字符串来存储肯定不行。经查一个最简单的kv的内存占用，发现为48byte。假设每个用户每天登录需要占据1对kv的话，那一亿就是$(48*100000000)/1024/1024/1024=4.47G$，这还只是是一天的量。如何满足搜索？
redis 是一个键值对的内存结构，只能根据 key 来进行定位 value 值，无法做到像 elasticsearch 那样对文档进行倒排索引快速全文检索。
方案一：Bitmap
在 redis 2.2.0 版本之后，新增了一个位图数据，它不是一种数据结构。实际上它就是一个字符串结构，只不过 value 是一个二进制数据，每一位只能是 0 或者 1 。redis 单独对 bitmap 提供了一套命令，可以对任意一位进行设置和读取。
bitmap 的核心命令：
SETBIT
语法： SETBIT key offset value
例如：
1 | setbit abc 5 1 ----> 00001 |
GETBIT
语法：GETBIT key offset
例如：
1 | getbit abc 5 ----> 1 |
bitmap 的其他命令还有 bitcount，bitcount，bitpos，bitop 等命令，都是对位的操作。
因为 bitmap 的每一位只占据 1bit 的空间 ，所以利用这个特性我们可以把每一天作为 key，value 为 1 亿用户的活跃度状态。假设一个用户一天内只要登录了一次就算活跃。活跃我们就记为 1，不活跃我们就记为 0 。把用户 Id 作为偏移量(offset)。这样我们一个 key 就可以存储 1 亿用户的活跃状态。
我们再来算下，这样一个位图结构的值对象占据多少空间。每一个位是 1bit，一亿用户就是一亿 bit 。8bit=1Byte
$100000000/8/1024/1024=11.92M$
我用测试工程往一个 key 里通过 lua 塞进了 1 亿个 bit，然后用 rdb tools 统计这个可以需要消耗 12M 的内存空间，这完全符合要求，而且 redis 可以集群部署来进行扩容存储。我们也可以用位图压缩算法对 bitmap 进行压缩存储，例如： WAH，EWAH，Roaring Bitmaps。
我们把每一天 1 亿用户的登录状态都用 bitmap 的形式存进了 redis，那要获取某一天 id 为 88000 的用户是否活跃，直接使用命令：
GETBIT 2020-01-01 88000 [时间复杂度为 O(1)]
如果要统计某一天的所有的活跃用户数，使用bitcount命令，bitcount 可以统计 1 的个数，也就是活跃用户数：
BITCOUNT 2020-01-01 [时间复杂度为 O(N)]
如果要统计某一段时间内的活跃用户数，需要用到 bitop 命令。这个命令提供四种位运算，AND(与)，(OR)或，XOR(亦或)，NOT(非)。我们可以对某一段时间内的所有 key 进行OR(或)操作，或操作出来的位图是 0 的就代表这段时间内一次都没有登录的用户。那只要我们求出 1 的个数就可以了。以下例子求出了 2020-01-01 到 2020-01-05 这段时间内的活跃用户数:
BITCOUNT OR result 2020-01-01 2020-01-02 2020-01-03 2020-01-04 2020-01-05 [时间复杂度为 O(N)]
从时间复杂度上说，无论是统计某一天，还是统计一段时间, 在实际测试中基本上都是秒出的，符合我们的预期。
bitmap 可以很好的满足一些需要记录大量而简单信息的场景，所占空间十分小，通常来说使用场景分 2 类：
某一业务对象的横向扩展，key 为某一个业务对象的 id，比如记录某一个终端的功能开关，1 代表开，0 代表关。基本可以无限扩展，可以记录 2^32 个位信息。不过这种用法由于 key 上带有了业务对象的 id，导致了 key 的存储空间大于了 value 的存储空间，从空间使用角度上来看有一定的优化空间。
某一业务的纵向扩展，key 为某一个业务，把每一个业务对象的 id 作为偏移量记录到位上。这道面试题的例子就是用此法来进行解决。十分巧妙的利用了用户的 id 作为偏移量来找到相对应的值。当业务对象数量超过 2^32 时（约等于 42 亿），还可以分片存储。
方案二：HyperLogLog
redis 从 2.8.9 之后增加了 HyperLogLog 数据结构。这个数据结构，根据 redis 的官网介绍，这是一个概率数据结构，用来估算数据的基数。能通过牺牲准确率来减少内存空间的消耗。
我们先来看看 HyperLogLog 的方法：
PFADD 添加一个元素，如果重复，只算作一个
PFCOUNT 返回元素数量的近似值
PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog
这很好理解，是不是。那我们就来看看同样是存储一亿用户的活跃度，HyperLogLog 数据结构需要多少空间。是不是比 bitmap 更加省空间呢。
我通过测试工程往 HyperLogLog 里 PFADD 了一亿个元素，通过 rdb tools 工具统计了这个 key 只需要 14392 Bytes，也就是 14KB 的空间。bitmap 存储一亿需要 12M，而 HyperLogLog 只需要 14K 的空间。这是一个很惊人的结果。
接下来我又放了 1000w 数据，统计出来还是 14k 。也就是说，无论你放多少数据进去，都是 14K 。
查了文档，发现 HyperLogLog 是一种概率性数据结构，在标准误差 0.81%的前提下，能够统计 ${2}^{64}$ 个数据。所以 HyperLogLog 适合在比如统计日活月活此类的对精度要不不高的场景。
HyperLogLog 使用概率算法来统计集合的近似基数，而它算法的最本源则是伯努利过程。
伯努利过程：简单来说，伯努利过程就是一个抛硬币实验的过程。抛一枚正常硬币，落地可能是正面，也可能是反面，二者的概率都是 $\frac{1}{2}$ 。伯努利过程就是一直抛硬币，直到落地时出现正面位置，并记录下抛掷次数 k 。比如说，抛一次硬币就出现正面了，此时 k 为 1; 第一次抛硬币是反面，则继续抛，直到第三次才出现正面，此时 k 为 3 。 对于 n 次伯努利过程，我们会得到 n 个出现正面的投掷次数值 $k_1$, $k_2$ … $k_n$ , 其中这里的最大值是 $k_{max}$ 。根据一顿数学推导，我们可以得出一个结论：${2}^{k_{max}}$来作为 n 的估计值。也就是说你可以根据最大投掷次数近似的推算出进行了几次伯努利过程。
虽然 HyperLogLog 数据类型不是精确统计,只适用于对精度要求不高的场景，而且这种类型无法得出每个用户的活跃度信息。
总结
对于文章开头所提到的问题，用 Bitmap 和 HyperLogLog 都可以解决。
| Bitmap | HyperLogLog | |
|---|---|---|
| 优点 | 非常均衡的特性，精准统计，可以得到每个统计对象的状态，秒出 | 可以统计夸张到无法想象的数量，并且占用小的夸张的内存 |
| 缺点 | 当你的统计对象数量十分十分巨大时，可能会占用到一点存储空间，但也可在接受范围内。也可以通过分片，或者压缩的额外手段去解决 | 建立在牺牲准确率的基础上，而且无法得到每个统计对象的状态 |
