共计 4058 个字符，预计需要花费 11 分钟才能阅读完成。
背景
营销零碎中，客户投诉是业务倒退的一大妨碍，个别会过滤掉黑名单高风险账号，并配合频控策略，来缩小客诉，进而减少营销效率，缩小营销老本，晋升营销品质。
营销零碎个别是通过大数据分析建模，在 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 操作、避免缓存击穿，以及各种须要疾速汇合检测且能够容忍肯定误报率的场合，误报是指布隆过滤器可能会谬误地判断某个不存在汇合中的元素为存在，但它绝不会谬误地判断存在的元素为不存在，因而在不须要百分之百准确性的状况下，布隆过滤器是一种十分有用的工具。
总结
通过探讨营销零碎中优化黑名单过滤的策略，本文引入了位图这一数据结构，并具体论述了其背地的实现机制及实用场合。位图特地实用于那些对空间效率和查问速度有极高要求的场景。在解决大数据时，位图通过压缩和优化能够极大地缩小内存占用，晋升数据处理的性能，心愿本文能为大家提供无益的参考和帮忙。
作者：京东科技 冯浩
起源：京东云开发者社区 转载请注明起源
