Bitmap

作者：京东科技 曹留界 在人群本地化实际中咱们介绍了人群ID中所有的pin的偏移量能够通过Bitmap存储，而Bitmap所占用的空间大小只与偏移量的最大值有关系。如果当初要向Bitmap内存入两个pin对应的偏移量，一个偏移量为1，另一个偏移量为100w，那么Bitmap存储间接须要100w bit的空间吗？数据部将偏移量存入Bitmap时，又如何解决数据稠密问题呢？本文将为大家解答这个问题。 一、BitMapBitmap的根本思维就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。因为采纳了Bit为单位来存储数据，因而能够大大节俭存储空间。 如果想将数字2存入位图中，则只须要将位图数组中下标为2的数组值置为1。 然而，如果当初要存储两个人群ID对应的偏移量，一个偏移量为1，另一个偏移量为100w，如果将这两个值间接放到位图数组中，那么位图数组所须要的空间就是100wbit，会产生大量的空间节约。那么有什么办法能够防止空间节约吗？答案就是RoaringBitMap！ 二、RoaringBitMapRoaringBitMap是一种高效压缩位图，简称RBM。RBM的概念于2016年由S. Chambi、D. Lemire、O. Kaser等人在论文《Better bitmap performance with Roaring bitmaps》 《Consistently faster and smaller compressed bitmaps with Roaring》中提出。上面咱们联合java中的实现对其进行介绍。 2.1 实现思路RBM次要将32位的整型（int）分为高16位和低16位（两个short），其中高16位对应的数字应用16位整型有序数组存储，低16位依据不同的状况抉择三种不同的container来存储，这三种container别离为： •Array Container 底层数据结构为short类型的数组，间接将数字低16位的值存储到该数组中。short类型的数组始终保持有序，方便使用二分查找，且不会存储反复数值。因为这种Container存储数据没有任何压缩，因而只适宜存储大量数据。其外部数组容量是动态变化的，当容量不够时会进行扩容，最大容量为4096。因为数组是有序的，存储和查问时都能够通过二分查找疾速定位其在数组中的地位。 ArrayContainer占用的空间大小与存储的数据量为线性关系，每个short为2字节，因而存储了N个数据的ArrayContainer占用空间大抵为2N字节。存储一个数据占用2字节，存储4096个数据占用8kb。 •Bitmap Container 底层实现为位图。这种Container应用long[]存储位图数据。咱们晓得，每个Container解决16位整形的数据，也就是0~65535，因而依据位图的原理，须要65536个比特来存储数据，每个比特位用1来示意有，0来示意无。每个long有64位，因而须要1024个long来提供65536个比特。 因而，每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不论一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。 •Run Container 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 也就RBM在存入一个32位的整形数字时，会先依照该数字的高16位进行分桶，以确定该数字要存入到哪个桶中。确定好分桶地位后，再将该数字对应的低16位放入到以后桶所对应的container中。 举个栗子 以十进制数字131122为例，当初咱们要将该数字放入到RBM中。第一步，先将该数字转换为16进制，131122对应的十六进制为0x00020032；其中，高十六位对应0x0002，首先咱们找到0x0002所在的桶，再将131122的低16位存入到对应的container中，131122的低16位转换为10进制就是50，没有超过ArrayContainer的容量4096，所以将低16位间接放入到对应的ArrayContainer中。 如果要插入的数字低16位超过了4096，RBM会将ArrayContainer转换为BitMapContainer。反之，如果数据在删除之后，数组中的最大数据小于4096，RBM会将BitMapContainer转换回ArrayContainer。 RBM解决的是32位的数字，如果咱们想解决Long类型的数字怎么办呢？这个时候能够应用Roaring64NavigableMap。Roaring64NavigableMap也是应用拆分模式，将一个long类型数据，拆分为高32位与低32位，高32位代表索引，低32位存储到对应RoaringBitmap中，其外部是一个TreeMap类型的构造，会依照signed或者unsigned进行排序，key代表高32位，value代表对应的RoaringBitmap。 三、空间占用比照1、间断数据 别离向位图中插入1w、10w、100w、1000w条间断数据，并且比照BitMap和RoaringBitMap占用空间的大小。比拟后果如下表所示： 10w数据占用空间100w数据占用空间1000w数据占用空间BitMap97.7KB976.6KB9.5MBRoaringBitMap16KB128KB1.2MB@Test public void testSizeOfBitMap() { //比照占用空间大小 - 10w元素 RoaringBitmap roaringBitmap3 = new RoaringBitmap(); byte[] bits2 = new byte[100000]; for (int i = 0; i < 100000; i++) { roaringBitmap3.add(i); bits2[i] = (byte) i; } System.out.println("10w数据 roaringbitmap byte size:"+ roaringBitmap3.getSizeInBytes()); System.out.println("10w数据 位图数组 byte size:"+bits2.length); RoaringBitmap roaringBitmap4 = new RoaringBitmap(); byte[] bits3 = new byte[1000000]; for (int i = 0; i < 1000000; i++) { roaringBitmap4.add(i); bits3[i] = (byte) i; } System.out.println("100w数据 roaringbitmap byte size:"+ roaringBitmap4.getSizeInBytes()); System.out.println("100w数据 位图数组 byte size:"+bits3.length); RoaringBitmap roaringBitmap5 = new RoaringBitmap(); byte[] bits4 = new byte[10000000]; for (int i = 0; i < 10000000; i++) { roaringBitmap5.add(i); bits4[i] = (byte) i; } System.out.println("1000w数据 roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes()); System.out.println("1000w数据 位图数组 byte size:"+bits4.length); }运行截图： ...

背景目前，在商品圈选投场景，每个标签id都会依据规定/指标绑定肯定数据量的商品集，在圈选规定条件变动或者定时工作触发时会进行商品集的刷新，新增合乎规定的商品，删除不合乎规定的商品。 然而因为商品集下的spu数量大部分都在数十万，多的能达到上百万，如果间接将刷新前后各十万甚至百万的spu全量放到内存中相互做diff，再对diff失去的差集做增删，当同一时间刷新的标签数量过多时，内存就很容易溢出，造成整个服务宕机。 同时目前底层存储商品集的数据库为Hbase，因而在标签侧对于商品集的刷新场景目前都是采取全增全删的策略，即把刷新后的商品集先全量保留一次(利用Hbase 保留的幂等性，同一个rowkey的数据反复保留会进行笼罩，而不必在保留前做额定的数据是否存在的判断)，并更新数据的modity_time=now()，而后再从Hbase中分批scan遍历商品集，找到modity_time<now的再进行删除，以此实现一次标签的刷新工作。 往往一个商品集在刷新前后真正变动的spu量并不大，通过取数剖析得悉变动的不会超过商品集数量的10%。而咱们目前采纳的这种全增全删的策略，每次刷新后都会有大量已有数据的反复插入，不仅缩短了刷新的速度，也减少底层贮存的压力，同时因为选投平台里有标签的指标，标签的变动须要推送变动的spu给选投平台进行从新圈品，同时spu es 中也存有标签的数据用于后盾展现，所以以后全增全删的策略，尤其是大量已有数据的反复插入，都会同步到选投平台和spu es侧，对他们造成大量的性能节约和解决老本，革新火烧眉毛。 优化计划后面提到，因为传统的java Set构造在数据量较大的状况，占用内存较多，导致无奈将前后海量商品集的数据全副存到内存中去做运算。 那么有没有一个数据结构能够在存海量数据时还能放弃较低的内存占用，反对去重，还反对交加，差集等各种运算呢? Bitmap完满满足要求。 Bitmap是通过bit数组来存储数据的数据结构，是一串间断的二进制数组（0和1），能够通过偏移量（offset）定位元素。Bitmap通过最小的单位bit来进行0|1的设置，示意某个元素的值或者状态，工夫复杂度为O(1)。 同时因为采纳了Bit为单位来存储数据，因而在存储空间方面，能够大大节俭。例如贮存500W数据仅需5000000/8/1024/1024=0.5M内存。 因而筹备应用Bitmap构造来存储刷新前后的商品集，而后别离对新老Bitmap相互求差集失去，最终对差集进行add和delete操作即可。 计划可行性剖析以标签场景为例。 标签能够绑定选投平台，标签零碎会把选投平台圈选的所有商品集都打上标，此刻标签下的商品集记为oldSset(X+Y)。 选投平台刷新后，会从新圈选出一批满足选投平台指标的商品集，此时选投平台下的商品集记为newSet(Y+Z) 。 此时标签零碎须要给newSet(Y+Z)打标，同时从oldSet(X+Y)删除不在本次圈选范畴内的商品(X)。 标签商品集底层贮存是Hbase，对于已存在数据的插入，只有rowkey(标签id+spuId)不变， Hbase就会进行笼罩，保留最新工夫戳的数据，能够了解为老Y曾经被新Y笼罩(老Y数据=新Y数据,只是工夫戳会不一样)，所以老全增全删的计划， 删除量级是X，而不是X+Y。 如上图所示，每次刷新后，其实只须要对X进行删除和对Z进行新增。 相比于老全增全删逻辑，Bitmap diff新计划查问和删除量级不变，新增量级和对选投平台，spu es 的告诉量级，都缩小了Y。 同时因为Bitmap自身贮存数据的形式，贮存500W的spu数据集对内存的占用也才在0.5M,实现不必放心内存溢出危险。 因而采纳Bitmap来贮存刷新前后的全量商品数据，并在内存中做diff是一个实践可行的计划。 技术选型既然咱们选定了应用Bitmap作为新计划的贮存，那么应该选取哪种Bitmap实现呢? 家喻户晓，Bitmap的实现有很多，例如java原生的BitSet，guava的EWAHCompressedBitmap，第三方的RoaingBitmap，redis Bitmap等等，因为redis的Bitmap次要做近程贮存不适宜以后内存diff场景，因而排除。 本次次要比照BitSet、EWAHCompressedBitmap、RoaingBitmap三种实现在各种数据稠密度下的内存占用和cpu占用，以选出最满足以后场景的实现。 内存占用测试通过往Bitmap中增加1、N+1、2N+1.....5000000数据，其中N为数据的步长(稠密度) 来计算各个Bitmap在不同稠密度下(N)的内存占用状况。 通过下图能够看出，除了在稠密度为1时，EWAHCompressedBitmap内存占用最低以外，其余稠密度下的内存占用：RoaingBitmap<EWAHCompressedBitmap<BitSet。 cpu耗时测试往各个Bitmap中增加1、N+1、2N+1.....5000000数据，其中N为数据的步长(稠密度)，而后与有5000000满数据的Bitmap别离求2000次差集并取2000次中的最大耗时，失去在每个稠密度下每种Bitmap的耗时状况。 通过下图能够看出，各个稠密度下的cpu耗时：RoaingBitmap≈EWAHCompressedBitmap<BitSet. 选型最终论断从内存占用，cpu耗时测试，理论场景下数据稠密度综合思考，RoaingBitmap成果最优，因而选用RoaingBitmap作为新计划的Bitmap实现。 RoaingBitmap介绍及原理RoaingBitmap贮存原理RoaingBitmap会将32 bit unsigned int 类型数据 划分为 2^16 个大Container（即应用数据的前16位二进制作为Container的编号），每个大Container有一个小Container 来寄存一个数值的低16位。 在存储和查问数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的Container，而后在将低 16 位值寄存在相应的 Container 中。 这样说可能比拟形象不易了解，上面我通过一个例子来阐明。 比方咱们要将31这个数放进RoarigBitmap中，它的16进制为：0000 001F，前16位为0000，后16为001F。所以咱们先须要依据前16位的值：0，找到它对应的的Container编号为0，而后依据后16位的值：31，确定这个值应该放到Container中的哪一个地位，如下图所示。 须要留神大Container外面的各个小Container是在须要的时候才会申请开拓的，并不是一开始就全副申请的，而且大Container中小Container都是按序号有序排列在大Container外面的。 四种container介绍为了在各种场景和稠密度下都始终保持有良好的内存占用和性能体现，RoaingBitmap 特意设计了4种小Container，别离为ArrayContainer(数组容器)，BitmapContainer(位图容器)，Runcontainer(行程步长容器)，Sharedcontainer(共享容器)，上面我会对每个ArrayContainer的应用场景和原理进行介绍。 ...

一、前言笔者最近致力于vivo游戏核心稳定性保护，在分析线上异样时，发现有相当一部分是由OutOfMemory引起。谈及OOM，咱们个别都会想到内存透露，其实，往往还有另外一个因素——图片，如果对图片使用不当的话，很容易吃掉大量内存，从而导致异样。 尤其是游戏核心在2020末~2021初的几个重要版本，上线了很多内容相干的feature，引入大量图片、视频列表，从而导致线上OOM占比回升。 在这篇文章中，笔者将解说一张看似一般的Bitmap对内存的占用，介绍Android Studio中帮忙咱们剖析图片占用内存的工具，举例说明风行的两大图片加载框架：Glide、Picasso在加载图片时应用内存的不同形式，接着剖析不同drawable目录下图片的显示策略，最初基于手机内存、版本，提出一种优化内存调配的计划。 二、查看图片内存占用一张图片在内存占用的空间到底有多少，普遍存在的一个误会是，图片自身在磁盘上/从网络下载下来是多大，就会占用多少的内存。这种说法是不正确的，图片占用内存的大小不取决于它自身的大小，而取决于图片库所采纳的展现形式所申请的内存。 拿钢铁侠这张图片举例，它的尺寸是350*350，能够看到在电脑磁盘上，它只占36KB的空间。 咱们创立一个简略的Demo，页面正地方是一个ImageView，用于显示这张钢铁侠图片。 通过Android Studio进行heap dump，从而看图片所占用的内存。首先咱们将显示图片时的内存快照保留下来。操作门路为Profiler -> Memory -> Heap Dump，这会生成一个dump文件，在其中能够看到以后堆的应用状况。 在上面这张图能够看到，程序运行时，“钢铁侠”这张图片占用的内存（Retained Size）是2560000bytes，约等于2.4MB内存。与它在磁盘上36KB的大小，相差了整整70倍！ 小技巧：如何查看dump文件中的图片 在调试时，如果咱们手头只有一个dump文件，往往须要还原图片内容，以帮忙定位问题。有两种形式能够从dump文件里提取原图片。 形式一：通过Android Studio间接查看 如果dump文件起源自Android版本为7.1.1（Android N，API=25）及以下的设施，能够应用这种办法。选中Bitmap对象，间接在窗口的Bitmap Preview中查看图片内容（如上图），十分不便。 形式二：通过MAT+GIMP查看 这种办法实用于全副Android版本的设施，首先用MAT关上dump文件，有时会产生下图的谬误： 起因是Android Studio的Profiler生成的dump文件不是规范格局，咱们能够应用位于门路SDK/platform-tools/hprof-conv.exe的工具将其转换为规范格局，转换命令为： hprof-conv.exe <in-file> <out-file>将转换后的dump文件通过MAT关上，在其中找到Bitmap对象的byte[]属性，将其复制为image01.data文件。 Tip: 能够看到这里image01.data文件的尺寸是2.44MB，也正是在运行时图片所占用的内存。而后用GIMP工具关上该文件，在格局那里抉择RGBA（大部分Bitmap都应用这种格局），宽与高能够在MAT中看到，笔者这里是800 * 800。设置好格局和宽高后，就能够看到图片的实在面目了。 二、图片内存占用计算公式在上一章节咱们晓得一个通过网络下载的36KB图片，在被加载到内存中时，须要2.4MB的空间。接下来解释这其中的换算关系，让咱们记住一个公式： 图片占用内存 = 图片品质 * 宽 * 高这外面有“图片品质”、“宽”、“高”三个因素，它波及到图片加载框架的实现，不同的框架，对于这三者的默认取值是不一样的，咱们以以后最风行的Picasso和Glide为例。 Picasso 在Picasso中，图片默认显示的宽高与原始图片宽高统一。依然以这张钢铁侠为例，图片自身是350px 350px，当咱们把它加载到200px 200px的ImageView当中时，占用空间是0.49MB。 因而，在指标ImageView小于图片尺寸的状况下，好的做法是应用不超过ImageView尺寸的图片源，一方面能够缩短图片下载工夫，另一方面有助于优化内存占用。 Glide Glide则采纳截然不同的解决形式，它最终应用的宽高是指标ImageView的宽高。如果咱们把同样一张图片加载到200px * 200px的ImageView中，占用空间只有0.16MB。 使Picasso达到与Glide同样的成果 Picasso的设计者也发现了这一毛病，提供一系列办法用来调整最终加载进去的图片尺寸，其一就是fit()，通过这个办法能够达到与Glide同样的成果。 Picasso().get().load(IMAGE_URL).fit().into(imageVIEW)相同场景：小图加载到大ImageView中 通常为了提供更清晰的界面，避免图片拉伸后失真含糊，设计师提供的图片都是高分辨率的，咱们所面临的场景是将大图加载到小ImageView中。但也不排除相同的可能：将小图加载到大ImageView外面。这时Glide默认采纳的内存策略是存在有余的：它采纳指标ImageView的尺寸作为最终的宽和高。 举例说明，当把350 350的钢铁侠图片加载到600 600的ImageView中时，占用的内存高达1.41MB。 600 600 4bytes = 1.41MB有没有一种办法，能够兼顾原图片与指标ImageView不同的大小关系呢？——有的，这就是centerInside()。 ...

背景 通常在挪动端 APP 的数据统计分析中，用户在未登录的状况应用 APP 都会被赋予一个基于设施标识 ( 例如 IDFA , AndroidID ) 的拜访用户 ID ，在登录后会被 APP 端依据账号信息赋予一个全局惟一的登录用户 ID ，基于拜访用户 ID 或登录用户 ID , 数据平台能够轻松的统计出该用户在 APP 端的拜访状况。 然而挪动端的灵便导致了同一用户能够在多个设施上登录同一 APP , 也能够在同一设施上登录不同的账号，这些行为导致在做挪动端数据分析时，会遇到下列几个问题： 同一个登录账号跨设施拜访的问题登录行为和非登录行为无奈串联剖析的问题设施与登录账号多对多关联的问题 如何正确辨认多个登录用户 ID 或拜访用户 ID 的行为归属？如何将某个用户在多设施或多账号下的行为数据归一，是挪动端统计的难题。个别状况下都会建设两套 ID 零碎来解决上述问题，将多个设施的登录用户 ID 或拜访用户 ID 映射到一个统计 ID 上, 将每个用户 ID 下的用户行为统计数据都累计到统计 ID 上，这样一个用户跨账号或跨设施的行为能够被正确的统计。 罕用解决方案 对于存在两套id零碎时，通常的解决方法是保护一张 ID 关系表 (mapping_table)。 如上表，拜访数据 (例如 拜访，点击，页面浏览)中的ID是拜访用户 ID , 先基于拜访用户ID 计算出每个拜访用户 ID 的数据 (pv_table)。 而后和关系表通过拜访用户 ID 做 join。 ...

根本思维：不同于应用int（long或double或...）类型来存储某个元素，BitMap采纳一个bit位来标记某个元素（bit位的value为1示意该元素存在，此时该bit位的index即为该元素的值。） 算法一个字节byte占用8个bit位，每个bit位的值为0或1，0代表该bit位没有元素存储，1代表该bit位的元素存在（元素的值为该bit位的index）。 问题： 问题：给40亿个不反复的unsigned int的整数，没排序。再给一个数，疾速判断这个数是否存在40亿个整数中？内存限度2G。 剖析过程：40亿个无符号整数须要占用的内存空间 = 40 * 10^8 * 4 / 2^30 ≈ 14.9G ，无奈全副加载到内存中应用传统的内存排序。如果应用BitMap，须要占用的内存空间 = 40 * 10^8 / 8 / 2^30 ≈ 477M，大大节俭了存储空间。 byte[]index = n >> 3;position = n & 7;// add(n)byte[index] |= 1 << position;// clear(n)byte[index] &= ~(1 << position);// contain(n)byte[index] & (1 << position) != 0