有道面试题 如何用redis存储统计1亿用户一年的登陆情况，并快速检索任意时间窗口内的活跃用户数量。对于这题，有2个重要的点需要考虑：
- 如何用合适的数据类型来存储1亿用户的数据，用普通的字符串来存储肯定不行。经过查看一个最简单的kv(key为aaa，value为1)的内存占用，发现为48byte。假设每个用户每天登陆需要占据1对KV的话，那一亿就是(48*100000000)/1024/1024/1024=4.47G。这还是一天的量。
- 如何满足搜索，redis是一个键值对的内存结构，只能根据key来进行定位value值，无法做到像elastic search那样对文档进行倒排索引快速全文检索。
redis其实有这种数据结构的，可以以很少的空间来存储大量的信息
在redis 2.2.0版本之后，新增了一个位图数据，其实它不是一种数据结构。实际上它就是一个一个字符串结构，只不过value是一个二进制数据，每一位只能是0或者1。redis单独对bitmap提供了一套命令。可以对任意一位进行设置和读取。
因为bitmap的每一位只占据1bit的空间 ，所以利用这个特性我们可以把每一天作为key，value为1亿用户的活跃度状态。假设一个用户一天内只要登录了一次就算活跃。活跃我们就记为1，不活跃我们就记为0。把用户Id作为偏移量(offset)。这样我们一个key就可以存储1亿用户的活跃状态。
我们再来算下，这样一个位图结构的值对象占据多少空间。每一个位是1bit，一亿用户就是一亿bit。8bit=1Byte
100000000/8/1024/1024=11.92M
一天1亿用户也就消耗12M的内存空间。这完全符合要求。1年的话也就4个G。
bitmap可以很好的满足一些需要记录大量而简单信息的场景。所占空间十分小
bitmap的优势、限制
优势
1.基于最小的单位bit进行存储，所以非常省空间。
2.设置时候时间复杂度O(1)、读取时候时间复杂度O(n)，操作是非常快的。
3.二进制数据的存储，进行相关计算的时候非常快。
4.方便扩容
限制
redis中bit映射被限制在512MB之内，所以最大是2^32位。建议每个key的位数都控制下，因为读取时候时间复杂度O(n)，越大的串读的时间花销越多。
设置某位上的值
语法 SETBIT key offset value
offset：是偏移量，从0开始，从左到右
value：只能是0 或者 1
例子：
当我们使用命令 setbit key (0,2,5,9,12) 1后，它的具体表示为：
byte bit0 bit1 bit2 bit3 bit4 bit5 bit6 bit7
byte0 1 0 1 0 0 1 0 0
byte1 0 1 0 0 1 0 0 0
获取某位上的值
语法GETBIT key offset
offset:为查询的位
使用get获取：
\xa4H = \xa4 \x48 (因为 0x48的ascii码为H）
二进制为： 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 即分别在0 2 5 9 12 位置上为1.
统计范围内1的个数
语法BITCOUNT key [start end]
获取位图指定位置（start到end，单位是字节，如果不指定就是获取全部）位值为1的个数。
例子1：不指定开始结束
例子2：只获取第一个字节里的个数
例子3：只获取第二个字节里的个数
0表示从左到右，-1表示从右到左,所以BITCOUNT key 0 -1 为统计所有的。
查找第一次0或者1出现的位置
语法BITPOS key bit [start end]
例子1：查找第一0出现的位置
例子2：在第2个字节中查找1第一次出现的位置
注：这里的start，end也是字节
BITOP
语法BITOP operation desckey key [key ...]
operation：支持AND OR XOR NOT四种操作
BITOP AND destkey srckey1 … srckeyN ，对一个或多个 key 求逻辑与，并将结果保存到 destkey
BITOP OR destkey srckey1 … srckeyN，对一个或多个 key 求逻辑或，并将结果保存到 destkey
BITOP XOR destkey srckey1 … srckeyN，对一个或多个 key 求逻辑异或，并将结果保存到 destkey
BITOP NOT destkey srckey，对给定 key 求逻辑非，并将结果保存到 destkey
例子1：对key进行逻辑非
[\xb7 = \x5b \xb7
例子2：对desckey和key进行逻辑与
结果恰好为 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
bitmap的使用场景
使用方式很多，根据不同的业务需求来，但是总的来说就两种，以用户为例子：
1.一种是某一用户的横向扩展，即此个key值中记录这当前用户的各种状态值，允许无限扩展(2^32内)
点评：这种用法基本上是很少用的，因为每个key携带uid信息，如果存储的key的空间大于value，从空间角度看有一定的优化空间，如果是记录长尾的则可以考虑。
2.一种是某一用户的纵向扩展，即每个key只记录当前业务属性的状态，每个uid当作bit位来记录信息(用户超过2^32内需要分片存储)
点评：基本上项目使用的场景都是基于这种方式的，按业务区分方便回收资源，key值就一个，将uid的存储转为了位的存储，十分巧妙的通过uid即可找到相应的值，主要存储量在value上，符合预期。
1.视频属性的无限延伸
需求分析：
一个拥有亿级数据量的短视频app，视频存在各种属性(是否加锁、是否特效等等)，需要做各种标记。
可能想到的解决方案：
1.存储在mysql中，肯定不行，一个是随着业务增长属性一直增加，并且存在有时间限制的属性，直接对数据库进行加减字段是非常不合理的做法。即使是存在一个字段中用json等压缩技术存储也存在读效率的问题，并且对于大几亿的数据来说，废弃的字段回收起来非常麻烦。
2.直接记录在redis中，根据业务属性＋uid为key来存储。读写效率角度没毛病，但是存储的角度来说key的数据量都大于value了，太耗费空间了。即使是用json等压缩技术来存储。也存在问题，解压需要时间，并且大几亿的数据回收也是难题。
设计方案：
使用redis的bitmap进行存储。
key由属性id＋视频分片id组成。value按照视频id对分片范围取模来决定偏移量offset。10亿视频一个属性约120m还是挺划算的。
伪代码：
function set($business_id , $media_id , $switch_status=1){
$switch_status = $switch_status ? 1 : 0;
$key = $this->_getKey($business_id, $media_id);
$offset = $this->_getOffset($media_id);
return $this->redis->setBit($key, $offse, $switch_status);
}
function get($business_id , $media_id){
$key = $this->_getKey($business_id,$media_id);
$offset = $this->_getOffset($media_id);
return $this->redis->getBit($key , $offset);
}
function _getKey($business_id, $media_id){
return 'm:'.$business_id.':'.intval($media_id/10000);
}
function _getOffset($media_id){
return $media_id % 10000;
}
这样基本实现了属性的存储，后续增加新属性也只是business_id再增加一个值。
至于为什么分片呢？分片的粒度怎么衡量？
分片有两个原因：1.读取的时候时间复杂度是O(n)存储越长读取时间越多 2.bitmap有长度限制2^32。
分片粒度怎么衡量：1.如果主键id存在的断层那么请尽可能选择的粒度可以避开此段id范围，防止空间浪费，因为来一个00000…9999个0…01，那么因为存一个属性而存了全部的，就浪费了。2.分片粒度可参考某一单位时间的增长值来判断，这样也有利于预算占了多少空间，虽然空间不会占很多。
2.用户在线状态
需求分析：
需要对子项目提供一个接口，来提供某用户是否在线？
设计方案：
使用bitmap是一个节约空间效率又高的一种方法，只需要一个key，然后用户id为偏移量offset，如果在线就设置为1，不在线就设置为0，3亿用户只需要36MB的空间。
伪代码：
$status = 1;
$redis->setBit('online', $uid, $status);
$redis->getBit('online', $uid);
需要加上如例子1一样分片的方式。10亿真的太多了。10w分一片。
3.统计活跃用户
需求分析：
需要计算活跃用户的数据情况。
设计方案：
使用时间作为缓存的key，然后用户id为offset，如果当日活跃过就设置为1。之后通过bitOp进行二进制计算算出在某段时间内用户的活跃情况。
伪代码：
$status = 1;
$redis->setBit('active_20170708', $uid, $status);
$redis->setBit('active_20170709', $uid, $status);
$redis->bitOp('AND', 'active', 'active_20170708', 'active_20170709');
上亿用户需要加上如例子1一样分片的方式。几十万或者以下，可无需分片省的业务变复杂。
4.用户签到
需求分析：
用户需要进行签到，对于签到的数据需要进行分析与相应的运运营策略。
设计方案：
使用redis的bitmap,由于是长尾的记录，所以key主要由uid组成，设定一个初始时间，往后没加一天即对应value中的offset的位置。
伪代码：
$start_date = '20170708';
$end_date = '20170709';
$offset = floor((strtotime($start_date) - strtotime($end_date)) / 86400);
$redis->setBit('sign_123456', $offset, 1);
//算活跃天数
$redis->bitCount('sign_123456', 0, -1)
无需分片，一年365天，3亿用户约占300000000*365/8/1000/1000/1000=13.68g。存储成本是不是很低。
性能
1.空间
redis的bitmap已经是最小单位的存储了，有没有办法对二进制存储的信息再进行压缩呢？进一步省空间？
可以对记录的二进制数据进行压缩。常见的二进制压缩技术都是基于RLE（Run Length Encoding，详见http://en.wikipedia.org/wiki/Run-length_encoding）。
可以预见，对于一个很大的Bitmap，如果里边的数据分布很稀疏（说明有很多大片连续的0），采用RLE编码后，占用的空间会比原始的Bitmap小很多。
2.时间
redis虽然是在内存操作，但是超过redis指定存储在内存的阀值之后，会被搞到磁盘中。要是进行大范围的计算还需要从磁盘中取出到内存在计算比较耗时，效率也不高，有没有办法尽可能内存中多放一些数据，缩短时间？
基于第一点同时引入一些对齐的技术，可以让采用RLE编码的Bitmap不需要进行解压缩，就可以直接进行AND/OR/XOR等各类计算；因此采用这类压缩技术的Bitmap，加载到内存后还是以压缩的方式存在，从而可以保证计算时候的低内存消耗；而采用word（计算机的字长，64位系统就是64bit）对齐等技术又保证了对CPU资源的高效利用。因此采用这类压缩技术的Bitmap，保持了Bitmap数据结构最重要的一个特性，就是高效的针对每个bit的逻辑运算。
