Redis详解（⼋）bitmap
1. 什么是 bitmap
bitmap，即位图。bitmap就是通过最⼩的单位bit来进⾏0或者1的设置，表⽰某个元素对应的值或者状态。⼀个bit的值，或者是0，或者是1；也就是说⼀个bit能存储的最多信息是2。
位（bit）：是计算机 内部数据储存的最⼩单位，11001100是⼀个⼋位⼆进制数。
字节（byte）：是计算机中数据处理的基本单位，习惯上⽤⼤写 B 来表⽰,1B（byte，字节）= 8bit
2. 重要 API
命令含义
getbit key offset⽤于获取Redis中指定key对应的值，中对应offset的bit
setbit key key offset value⽤于修改指定key对应的值，中对应offset的bit
bitcount key [start end]获取位图指定范围中位值为1的个数，如果不指定start与end，则取所有
bitop op destKey key1 []做多个BitMap的and（交集）、or（并集）、not（⾮）、xor（异或）操作并将结果保存在destKey中
bitpos key tartgetBit [start end]计算位图指定范围第⼀个偏移量对应的的值等于targetBit的位置
1. 不到返回-1
2. start与end没有设置，则取全部
3. targetBit只能取0或者1
3. bitmap的优点和限制
3.1 优点
1. 基于最⼩的单位bit进⾏存储，所以⾮常省空间。
2. 设置时候时间复杂度O(1)、读取时候时间复杂度O(n)，操作是⾮常快的。
3. ⼆进制数据的存储，进⾏相关计算的时候⾮常快。
4. ⽅便扩容
3.2 限制
bitmap的value实际是⼀个string结构。Redis中string value限制在512MB之内，所以最⼤是2^32位。建议每个key的位数都控制下，因为读取时候时间复杂度O(n)，越⼤的串读的时间花销越多。
3.3 空间、时间粗略计算⽅式
在⼀台2010 MacBook Pro上，offset为232-1（分配512MB）需要～300ms，offset为230-1(分配128MB)需要～80ms，offset 为228-1（分配32MB）需要～30ms，offset为226-1（分配8MB）需要8
ms。<；来⾃官⽅⽂档>
⼤概的空间占⽤计算公式是：($offset/8/1024/1024)MB。
4. 使⽤场景
使⽤⽅式很多，根据不同的业务需求来，但是总的来说就两种，以⽤户为例⼦：
1. ⼀种是某⼀⽤户的横向扩展，即此个key值中记录这当前⽤户的各种状态值，允许⽆限扩展(2^32内)
点评：这种⽤法基本上是很少⽤的，因为每个key携带uid信息，如果存储的key的空间⼤于value，从空间⾓度看有⼀定的优化空间，如果是记录长尾的则可以考虑。
2. ⼀种是某⼀⽤户的纵向扩展，即每个key只记录当前业务属性的状态，每个uid当作bit位来记录信息(⽤户超过2^32内需要分⽚存储)
点评：基本上项⽬使⽤的场景都是基于这种⽅式的，按业务区分⽅便回收资源，key值就⼀个，将uid的存储转为了位的存储，⼗分巧妙的通过uid即可到相应的值，主要存储量在value上，符合预期。
4.1 ⽤户在线状态
使⽤bitmap是⼀个节约空间效率⼜⾼的⼀种⽅法，只需要⼀个key，然后⽤户id为偏移量offset，如果在线就设置为1，不在线就设置为0，3亿⽤户只需要36MB的空间。
当数据量⼤时key需要进⾏分⽚处理，⼤概10w⽤户分为⼀个key，减少位移耗费时间。
$status = 1;
$redis->setBit('online', $uid, $status);
$redis->getBit('online', $uid);
4.2 统计活跃⽤户
使⽤时间作为缓存的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');
上亿⽤户需要加上分⽚的⽅式。⼏⼗万或者以下，可⽆需分⽚省的业务变复杂。
4.3 ⽤户签到
使⽤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。存储成本是不是很低。
4.4 布隆过滤器
布隆过滤器主要是⽤于应对缓存穿透问题。
⽐如爬⾍服务器在爬取电商⽹站的商品信息时，⾸先经过缓存，如果缓存查不到，再去数据库获取信息，因为爬⾍的效率很⾼，且sku很有可能是不存在或者已下架的，就会造成缓存穿透，⼤量请求被发送到数据库，导致服务器受到影响。
此时，可以在缓存层之前，添加⼀个布隆过滤器，布隆 过滤器看作是⼀个bitmap，sku作为offset值，如果商品真实存在，bit值设为1。⾸先将商品数据初始化，当有请求时，通过getbit判断sku是否有效。如果布隆过滤器认为商品不存在，就拒绝访问，这样就可以保护存储层。
4.5 视频属性的⽆限延伸
⼀个拥有亿级数据量的短视频app，视频存在各种属性(是否加锁、是否特效等等)，需要做各种标记。
我们可以使⽤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;redis八种数据结构
}
这样基本实现了属性的存储，后续增加新属性也只是business_id再增加⼀个值。
分⽚有两个原因：
1. 读取的时候时间复杂度是O(n)存储越长读取时间越多
2. bitmap有长度限制2^32。
分⽚粒度怎么衡量：
1. 如果主键id存在的断层那么请尽可能选择的粒度可以避开此段id范围，防⽌空间浪费，因为来⼀个00000…9999个0…01，那么因
为存⼀个属性⽽存了全部的，就浪费了。
2. 分⽚粒度可参考某⼀单位时间的增长值来判断，这样也有利于预算占了多少空间，虽然空间不会占很多。
5. 可能会遇到的坑
5.1 bitcout的陷阱
如果你有仔细看前⽂的⽤法，会发现有这么⼀个备注“返回⼀个指定key中位的值为1的个数(是以byte为单位不是bit)”，这就是坑的所在。
所以bitcount 0 0 那么就应该是第⼀个字节中1的数量的，注意是字节，第⼀个字节也就是1,2,3,4,5,6,7,8这⼋个位置上。
6. bitmap进阶⽤法
6.1 空间
redis的bitmap已经是最⼩单位的存储了，有没有办法对⼆进制存储的信息再进⾏压缩呢？进⼀步省空间？
答案是有的。
其意思是：第⼀位为0，连续有8个，接下来是2个1，11个0，1个1，2个0，3个1，最后是11个0（当然此处只是对RLE的基本原理解释，实际应⽤中的编码并不完全是这样的）。
可以预见，对于⼀个很⼤的Bitmap，如果⾥边的数据分布很稀疏（说明有很多⼤⽚连续的0），采⽤RLE编码后，占⽤的空间会⽐原始的Bitmap⼩很多。
6.2 时间
redis虽然是在内存操作，但是超过redis指定存储在内存的阀值之后，会被搞到磁盘中。要是进⾏⼤范围的计算还需要从磁盘中取出到内存在计算⽐较耗时，效率也不⾼，有没有办法尽可能内存中多放⼀些数据，缩短时间？
答案是有的。
基于第⼀点同时引⼊⼀些对齐的技术，可以让采⽤RLE编码的Bitmap不需要进⾏解压缩，就可以直接进⾏AND/OR/XOR等各类计算；因此采⽤这类压缩技术的Bitmap，加载到内存后还是以压缩的⽅式存在，从⽽可以保证计算时候的低内存消耗；⽽采⽤word（计算机的字长，64位系统就是64bit）对齐等技术⼜保证了对CPU资源的⾼效利⽤。因此采⽤这类压缩技术的Bitmap，保持了Bitmap数据结构最重要的⼀个特性，就是⾼效的针对每个bit的逻辑运算。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。