背景

营销零碎中，客户投诉是业务倒退的一大妨碍，个别会过滤掉黑名单高风险账号，并配合频控策略，来缩小客诉，进而减少营销效率，缩小营销老本，晋升营销品质。

营销零碎个别是通过大数据分析建模，在CDP（客户数据平台，以客户为外围，围绕数据交融、人群圈选、用户洞察等提供产品能力）创立营销指标客户群体，黑名单同样也是通过CDP保护。上面的图片简略形容了过滤黑名单的解决流程，流程是绝对简略的。然而，测试过程中却发现一个问题，对于一个近30万的营销群体，整个触达流程须要解决一个多小时，而其中过滤黑名单就占用了近半个小时的工夫，业务有点难以承受这个性能。

性能优化

引入多线程优化

其实很容易就能想到，对于调用RPC接口这种含有I/O操作的场景，能够引入多线程优化，将一个几十万的账号汇合拆分为多个子工作提交给线程池解决，从而放慢处理速度。从下图能够看出引入多线程后性能有很显著的改善，单线程解决25万、50万个账号的群体别离须要近半小时、近一小时，改为25个线程解决后能够别离管制在1分钟、2分钟左右。

引入位图优化

进一步理解CDP的底层原理后，会发现这个问题应该还有其余的解决方案，即通过位图优化。CDP的群体都会有对应的位图文件，也就是说营销客户群体和黑名单群体都是以位图的数据结构存储的，通过CDP下载群体的SDK就能够获取到位图文件，营销群体的位图与黑名单群体位图进行与非操作（andNot，就是从一个位图中移除另一个位图中存在的元素，而保留不在另一个位图中的元素），失去的新的位图就是过滤掉黑名单账号后的指标客户的位图。代码实现很简略，应用CDP SDK的示例代码如下（也能够参考GitHub示例代码，但不适用于CDP群体位图解决）：

DataLoader dataLoader = new DataLoader(token, bitMapBaseUrl);ABitmap customerBitmap = dataLoader.loadGroup(customerGroupCode);ABitmap blacklistBitmap = dataLoader.loadGroup(blacklistGroupCode);customerBitmap.andNot(blacklistBitmap);

位图存储相当节俭空间，50万群体的位图文件也就约2MB大小。同时位图的与非操作是相当快的，上边例子中的25万、50万的群体都能够在80毫秒左右过滤掉黑名单账号。从近半小时、近一小时到几十毫秒这个比照十分惊人了，那么为什么位图的处理速度能够这么快呢？

位图简介

位图原理

位图的根本思维是应用bit来标记一个数值，1示意该数值存在，0示意不存在。因为以位为单位存储数据，因而能够大大节俭存储空间。通过这种形式，能够十分高效地示意和操作数值汇合。

举个直观的例子，有40亿个不反复的随机自然数，如果应用long型数值存储，一个long型数值8个字节，40亿个数值占用约29.8GB，但如果是存储为40亿个bit，则只须要约0.47GB。

在Java中一个long型数值占64位，能够用一个long型数组long[] words = new long[(nBits - 1) / 64 + 1]存储位图，其中nBits示意位图的初始大小。对于给定任意自然数x，x / 64就能失去x在数组中的下标，x % 64就能失去x在此下标的哪个位。数组的第一个下标words[0]能够示意数值0~63，第二个下标words[1]能够示意数值64~127，之后依此类推。

如果将 3, 4, 6 几个数值存入位图，则如下图所示，对应数组的第一个下标的 3, 4, 6 位被标记为1，其余位均为0。

对于增加操作，假如要增加数值2，能够计算出其在数组中的下标为2 / 64即0，在words[0]的地位为2 % 64即2，只需将1按位左移2位，而后和words[0]进行按位或操作，将相应地位置为1。

对于移除操作，假如要移除刚增加的数值2，和增加操作一样，能够通过计算失去其在数组的下标为0, 在words[0]的地位为2，只需将1按位左移2位再按位取反，而后和words[0]进行按位与操作，将相应地位置为0。

而对于查找操作，假如要查找数值3，能够计算失去其在数组的下标为0, 在words[0]的地位为3，只需将1按位左移3位，而后和words[0]按位与操作不等于0即可判断数值是否存在。

以上内容简略介绍了 Java 中的BitSet的实现原理，理论代码还会略微简单一些，比方会波及到数组扩容，范畴边界的检测等等。有意思的是BitSet中计算数组下标和地位并没有应用除法和取模，都是通过位移操作实现的，x / 64是通过右移操作x >> 6，1按位左移x % 64位是间接将1左移x位即1 << x。

位图对象还反对一些罕用的位运算，如求交加(and, 按位与操作)，求并集(or, 按位或操作)，求差集(andNot, 按位与非操作)。

位图十分节俭存储空间，位操作也十分高效，这也是为什么引入位图过滤黑名单能在毫秒级别解决实现的起因。

RoaringBitmap

遗憾的是，BitSet会占用过多内存。如果BitSet中只存储一个数值200000000，通过GraphLayout发现BitSet会占用约23MB内存，这种状况对空间的节约极其重大。为了补救这一缺点，通常应用压缩位图。

RoaringBitmap是一种压缩位图，其性能往往优于WAH、EWAH或Concise等传统压缩位图。在某些状况下，RoaringBitmap的速度能够快上数百倍，而且压缩成果往往要好得多。它们甚至比未压缩的位图更快。如果应用RoaringBitmap只存储一个数值200000000，只须要144B的内存。

RoaringBitmap将一个int数值x划分为高16位和低16位，高16位下标能够通过x >>> 16失去，高位container中保护了一个数组，数组的元素中存储了低位container，低位container中的元素数量未达到4096时，应用ArrayContainer存储，其外部实现是一个char数组，数组中寄存低位数值，达到4096后低位container会转换为BitmapContainer，其外部实现就是一个位图。此外还有一个RunContainer的实现，不过较少应用。

为什么要应用4096这个阈值呢？是因为超过4096后，BitmapContainer会比ArrayContainer更节俭空间。

存储long型数值时能够应用Roaring64NavigableMap，区别是它会将数值分为高32位和低32位。CDP存储人群的位图就是基于Roaring64NavigableMap实现的。

位图的利用场景

位图能够用较少的内存来示意大规模的布尔值汇合，节俭内存空间，并且反对高效的位操作，如AND、OR、XOR等，使得对汇合进行简单操作变得简略高效，对于存在性查问，位图能够在常数工夫内实现，具备高效的查问性能。一些面试题中呈现的几十亿数据的去重、排序、计数或者成员查问等问题，都能够通过位图解决，此外还有很多场景利用到了位图。

Java 中的位图利用

ArrayList为了晋升性能并节俭空间，重写了Collection接口默认的removeIf办法，重写后的办法应用了位图，首先遍历一遍元素用位图标记待删除的元素地位，而后遍历第二遍才真正删除元素，通过这种形式实现，能够高效移除元素，缩小不必要的数组复制和元素挪动次数，并且应用位图标记待删除地位也没有过多节约空间。

位图索引

位图索引是一种特地适宜于解决具备较少惟一值的列（例如性别、婚姻状况等）查问的数据结构，它在数据仓库等场合中十分有用，因为这些环境通常蕴含大量的数据读取操作和简单的布尔逻辑查问，同时数据更新的频率绝对较低。位图索引通过将列值映射到位上，并利用位运算来疾速实现查问，可能无效进步查问效率，但它不适宜那些具备高基数值和频繁更新的场景，因为这些场景下位图索引会占用大量空间并且更新老本很高。

Redis 的位图

Redis的位图非常适合于解决大量的布尔值数据，例如追踪用户的在线状态、记录用户每日签到或统计沉闷用户数量等场景，因为位图通过每个位代表一个布尔值，能够极大地节俭存储空间，并且Redis提供了丰盛的位操作命令来高效地执行各种计算，如统计特定位上值为1的数量或者对多个位图进行位运算以实现疾速的汇合操作，这些个性使得位图在特色标记、试验分组以及AB测试等方面也十分有用；然而，须要留神的是，因为Redis将位图存储为字符串，因而其大小会受到字符串最大长度的限度，并且当数据量微小时，对内存的应用效率也是一个须要思考的因素。

布隆过滤器

数值能够很不便地应用位图解决，然而有些场景须要解决的可能是字符串，比方用户账号、URL等，个别须要将字符串跟数值做一个映射，CDP是将用户账号和偏移量offset做了一个映射表，再将偏移量offset存储到位图。布隆过滤器则是通过多个哈希函数将元素映射到了位图上，它是一种空间效率极高的概率型数据结构，它用于判断一个元素是否在一个汇合中，并且可能十分疾速地进行查问，常见的利用场景包含网络爬虫中防止反复爬取雷同的URL、数据库中疾速判断某个元素是否存在以缩小不必要的磁盘IO操作、避免缓存击穿，以及各种须要疾速汇合检测且能够容忍肯定误报率的场合，误报是指布隆过滤器可能会谬误地判断某个不存在汇合中的元素为存在，但它绝不会谬误地判断存在的元素为不存在，因而在不须要百分之百准确性的状况下，布隆过滤器是一种十分有用的工具。

总结

通过探讨营销零碎中优化黑名单过滤的策略，本文引入了位图这一数据结构，并具体论述了其背地的实现机制及实用场合。位图特地实用于那些对空间效率和查问速度有极高要求的场景。在解决大数据时，位图通过压缩和优化能够极大地缩小内存占用，晋升数据处理的性能，心愿本文能为大家提供无益的参考和帮忙。

作者：京东科技 冯浩

起源：京东云开发者社区 转载请注明起源