bitmap
基本思想
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。
要表示8个数,我们就只需要8个Bit(1Byte),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0 然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 (i/8)|(1«(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为1。
然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1。然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。 其实就是把计数排序用的统计数组的每个单位缩小成bit级别的布尔数组
以上内容引用自《编程珠玑》
原理剖析
假设现在有一个文件中的数据,该文件存储了N=1000000个无序的整数,需要把这些整数读取到内存并排序再重新写回文件中该如何解决?
我们知道一个int型的数有4个字节,也就是32位,那么我们可以用N/32个int型数组来表示这N个数:
|
|
这样,每当输入一个数字m,我们应该先找到该数字在数组的第?个元素,也就是a[?],然后再确定在这个元素的第几个bit位,找到后设置为1,代表存在该数字。举个例子来说,比如输入40,那么40/32为1余8,则应该将a[1]元素值的第9个bit位置为1(1的二进制左移8位后就是第9个位置),表示该数字存在。
大概明白了位向量表示方式后,上述过程的计算方式,通过以下方式可以计算该数存储在数组的第?个元素和元素中第?个bit位置,为了演示方便,我们这里假设整第?个元素中的?为p,余值设置s,数组int[] a, 待排序的整数为m。
|
|
|
|
示例代码
对1000以内的随机数(1000次随机并去重)排序
|
|
应用场景
-
快速排序
-
快速查询
先对所有数字进行一次遍历(相当于一趟一趟快速排序)。遍历完以后就是查询,由于我们的Bit-map采取的是连续存储(整型数组形式,一个数组元素对应32bits),我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位,那将待查询的数字除以32,定位到对应的数组元素(桶),然后再求余(%32),就可以定位到相应的状态位。如果为1,则代表改数字存在;否则,该数字不存在。
-
快速去重
在3亿个整数中找出不重复的整数,限制内存不足以容纳3亿个整数。
对于这种场景我可以采用2-BitMap来解决,即为每个整数分配2bit,用不同的0、1组合来标识特殊意思,如00表示此整数没有出现过,01表示出现一次,11表示出现过多次,就可以找出重复的整数了,其需要的内存空间是正常BitMap的2倍,为:3亿*2/8/1024/1024=71.5MB。
具体的过程如下:
扫描着3亿个整数,组BitMap,先查看BitMap中的对应位置,如果00则变成01,是01则变成11,是11则保持不变,当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为01的整数输出即可。
-
统计不同号码的个数
已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数
8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)
-
REDIS bitmap相关应用
edis提供了类似的命令,最大可以存放2的32次方,即21亿多的数字,主要有以下几个:SETBIT, GETBIT, BITCOUNT, BITOP, BITPOS,BITFIELD
主要用来做活跃用户在线状态、活跃用户统计、用户签到等场景,特别适合大量用户,几千万上亿级别,当然你用传统数据库也能做,但是redis做起来更简单,更节省空间!
下面举一个用户签到的功能设计案例:
很多App都有一个签到功能,比如说连续签到7天或者30天给一些奖励,需求十分简单!
作为后端,我们需要提供一个签到接口,然后记录用户签到的信息,比如用户uid,签到时间!
如果使用传统关系型数据库,我们可能需要建一张签到表,大概有id、uid、createdTime等几个字段,当用户签到的时候新增一条记录就行!这种做法肯定是没问题的,但是如果网站每天有千万用户签到,那么这张表每天都会有千万条记录产生,数据的存储是问题!分库分表必不可少!
假如使用redis的bit操作,我们可以使用setbit,
SETBIT key offset value
对指定的key的value的指定偏移(offset)的位置1或0, 其中key我们可以设置为当天的年月日,offset是用户uid(这里暂时只考虑uid是纯数字的情况),value的话1表示已签到。比如说用户uid位12500的用户在20190501签到了,我们可以执行SETBIT 20190501 12500 1
,其它用户依此论推!如果我们需要查询用户某天是否签到,只需要使用
GETBIT 20190501 12500
,返回1表示已签到,0未签到。如果需要查询某天有多少人签到,可以使用
BITCOUNT 20190501
。如果要统计连续7天签到的总人数的话可以使用bitop命令,比如
bitop AND 7_dasy_sign 20190501 20190502 20190503 ... 20190507
。对一个或多个保存二进制位的字符串key进行位元操作,并将结果保存到destkey上。
operation可以是AND、OR、NOT、XOR这四种操作中的任意一种。 BITOP AND destkey key [key …] ,对一个或多个key求逻辑并,并将结果保存到destkey BITOP OR destkey key [key …] ,对一个或多个key求逻辑或,并将结果保存到destkey BITOP XOR destkey key [key …] ,对一个或多个key求逻辑异或,并将结果保存到destkey BITOP NOT destkey key ,对给定key求逻辑非,并将结果保存到destkey 除了NOT操作外,其他操作都可以接受一个或多个key作为输入 当BITOP处理不同长度的字符串时,较短的那个字符串所缺少的部分会被看做0 空的key也被看作是包含0的字符串序列
理论上讲,setbit的大小在0到2的32次方(最大使用512M内存)之间,即0~4294967296之间,也就说最多可以存储42亿用户的签到情况。和数据库相比,这种方式查询的效率非常高,并不会因为数据大而变慢,而且比较节省内存,操作上也不是太复杂!
扩展
问题
数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。
Bloom Filter
概念
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
原理
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。
Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。
缺点
bloom filter之所以能做到在时间和空间上的效率比较高,是因为牺牲了判断的准确率、删除的便利性
-
存在误判,可能要查到的元素并没有在容器中,但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单,那么可以通过建立一个白名单来存储可能会误判的元素。
-
删除困难。一个放入容器的元素映射到bit数组的k个位置上是1,删除的时候不能简单的直接置为0,可能会影响其他元素的判断。可以采用Counting Bloom Filter
应用
常见的几个应用场景:
-
cerberus在收集监控数据的时候, 有的系统的监控项量会很大, 需要检查一个监控项的名字是否已经被记录到db过了, 如果没有的话就需要写入db.
-
爬虫过滤已抓到的url就不再抓,可用bloom filter过滤
-
垃圾邮件过滤。如果用哈希表,每存储一亿个 email地址,就需要 1.6GB的内存(用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email地址需要占用十六个字节。一亿个地址大约要 1.6GB,即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB的内存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。
Roaring BitMap
概念
为了解决位图不适应稀疏存储的问题,大佬们提出了多种算法对稀疏位图进行压缩,减少内存占用并提高效率。比较有代表性的有WAH、EWAH、Concise,以及RoaringBitmap。前三种算法都是基于行程长度编码(Run-length encoding, RLE)做压缩的,而RoaringBitmap算是它们的改进版,更加优秀。
每个RoaringBitmap(GitHub链接)中都包含一个RoaringArray
,名字叫highLowContainer
。
highLowContainer
存储了RoaringBitmap
中的全部数据。
|
|
这个名字意味着,会将32位的整形(int
)拆分成高16位和低16位两部分(两个short
)来处理。
RoaringArray的数据结构很简单,核心为以下三个成员:
|
|
每个32位的整形,高16位会被作为key存储到short[] keys
中,低16位则被看做value,存储到Container[] values
中的某个Container中。keys
和values
通过下标一一对应。size
则标示了当前包含的key-value pair的数量,即keys
和values
中有效数据的数量。
keys
数组永远保持有序,方便二分查找。
三种Container
下面介绍到的是RoaringBitmap的核心,三种Container。
通过上面的介绍我们知道,每个32位整形的高16位已经作为key存储在RoaringArray
中了,那么Container只需要处理低16位的数据。
ArrayContainer
|
|
结构很简单,只有一个short[] content
,将16位value直接存储。
short[] content
始终保持有序,方便使用二分查找,且不会存储重复数值。
因为这种Container存储数据没有任何压缩,因此只适合存储少量数据。
ArrayContainer占用的空间大小与存储的数据量为线性关系,每个short
为2字节,因此存储了N个数据的ArrayContainer占用空间大致为2N
字节。存储一个数据占用2字节,存储4096个数据占用8kb。
根据源码可以看出,常量DEFAULT_MAX_SIZE
值为4096,当容量超过这个值的时候会将当前Container替换为BitmapContainer。
BitmapContainer
|
|
这种Container使用long[]
存储位图数据。我们知道,每个Container处理16位整形的数据,也就是0~65535,因此根据位图的原理,需要65536个比特来存储数据,每个比特位用1来表示有,0来表示无。每个long
有64位,因此需要1024个long
来提供65536个比特。
因此,每个BitmapContainer在构建时就会初始化长度为1024的long[]
。这就意味着,不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据,占用的空间都是同样的8kb。
RunContainer
|
|
RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding),对连续数据有比较好的压缩效果。
它的原理是,对于连续出现的数字,只记录初始数字和后续数量。即:
- 对于数列
11
,它会压缩为11,0
; - 对于数列
11,12,13,14,15
,它会压缩为11,4
; - 对于数列
11,12,13,14,15,21,22
,它会压缩为11,4,21,1
;
源码中的short[] valueslength
中存储的就是压缩后的数据。
这种压缩算法的性能和数据的连续性(紧凑性)关系极为密切,对于连续的100个short
,它能从200字节压缩为4字节,但对于完全不连续的100个short
,编码完之后反而会从200字节变为400字节。
如果要分析RunContainer的容量,我们可以做下面两种极端的假设:
- 最好情况,即只存在一个数据或只存在一串连续数字,那么只会存储2个
short
,占用4字节 - 最坏情况,0~65535的范围内填充所有的奇数位(或所有偶数位),需要存储65536个
short
,128kb
RoaringBitmap针对Container的优化策略
创建时:
- 创建包含单个值的Container时,选用ArrayContainer
- 创建包含一串连续值的Container时,比较ArrayContainer和RunContainer,选取空间占用较少的
转换:
针对ArrayContainer:
- 如果插入值后容量超过4096,则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。
- 调用runOptimize()方法时,会比较和RunContainer的空间占用大小,选择是否转换为RunContainer。
针对BitmapContainer:
- 如果删除某值后容量低至4096,则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。
- 调用runOptimize()方法时,会比较和RunContainer的空间占用大小,选择是否转换为RunContainer。
针对RunContainer:
- 只有在调用runOptimize()方法才会发生转换,会分别和ArrayContainer、BitmapContainer比较空间占用大小,然后选择是否转换。