一、背景介绍

CDP 系统提供了强大的标签和群体的构建能力，面对海量数据的标签和群体，我们采用了 Bitmap+ClickHouse 的存储与计算方案。详细内容可以参考之前文章。

有了群体之后，它们被广泛的应用到支付，消金，财富，营销等各种核心业务的用户拉新，交易转化，促活等核心链路中。

而人群应用方式中，基于人群的命中服务，是非常重要的 P0 级接口（日常 TPS 峰值 40W+，响应耗时 50ms 以内，大促备战 120W+）

它主要用来查询指定用户 ID 是否包含在指定群体中，这篇文章就来分享人群命中接口的演进迭代过程。

二、问题描述

前文已经介绍了 CDP 中群体的加工和存储方式，采用了 ClickHouse(以下简称 CK)+Bitmap 的方案，为了减轻 ClickHouse 的计算和存储压力，我们的 22000+ 群体目前只在 CK 中存储了最新的版本。

这是因为 CDP 中标签和群体的计算都在 CK 中，而且依赖的都是最新数据，所以只存储最新数据即可满足需求。如下图：

上图可以看到除了 CK 中的数据外，我们在 OSS 对象存储中也放了一份群体数据。

由前文可知，群体的 bitmap 文件中可以理解为存储的都是 offset，这时候如果想查询某一个 ID 是否在指定群体中，即人群命中服务，需要两个步骤。

首先要将 ID 转换为 bitmap 中对应的唯一 offset，之后可以尝试直接利用 CK SQL 查询，bitmapContains(bitmap, offset) 来进行判断是否在指定 bitmap 中。

也可以从 CK 或 OSS 中加载指定群体的 bitmap，在 JAVA 程序中使用Roaring64NavigableMap的能力进行判断。

但是，直接使用 CK SQL 或者 oss 文件加载方式，肯定都无法直接满足 50ms 性能的问题。接下来就对我们的前后两套方案进行讲解。

三、历史方案

首先介绍我们的上一版方案，针对上文的问题，可以分解为两步，第一步解决 ID 到 offset 的高性能转换；第二步判断 offset 是否包含在指定群体的 bitmap 中。

1）解决数十亿 ID 和 offset 的快速转换

之前文章中提到，由于用户ID*是唯一且不变的*，所以对所有的 ID 进行了编码，每个 ID 对应一个唯一的 offset，并生成了最终的一张 ID 池表，比如 id_offset_table。

有了这些数据之后，就可以考虑如何进行快速查询来进行 ID 和 offset 的转换了。

最简单的思路就是每次去表中查询：

SELECT `offset` FROM id_offset_table where id='id1'

但是这种直接查询的方式，显然不能满足高性能的需求，所以，最自然的方式是将常用的 ID 的结果进行缓存；而常用缓存的方式可以选择缓存到请求的服务器内存，也可以加入到 Redis 缓存中。

由于目前的 ID 池已经达到了惊人的数十亿，放到请求服务器内存中，极限情况预计需要 500G 的内存，单机存放显然是不太现实的。

所以这里最终选择的是放入到 Redis 缓存中，这也是目前我们采用的方式。

2）判断 offset 是否包含在指定群体的 bitmap 中

有了 ID 对应的 offset，接下来就是如何判读是否存在于指定 bitmap 中；bitmap 目前由两个地方存储，一个是 CK 中，另一个是 OSS 对象存储中。

之前方案，没有从 CK 中获取 bitmap，采用的是从 OSS 中将群体文件，直接拉取到大内存物理中，然后再通过接口读取内存数据实现。

这样做的好处是，减少了 CK 的访问次数，减轻它的压力，毕竟 CDP 平台的几千个标签和上万个群体的更新都依赖于 CK，减轻它的压力，同样的集群配置可以让更多资源留给计算。

但由于群体太多，将 OSS 文件放入单机内存中，是无法装载所有群体的（采用了 32 核 192G 的机器），所以针对群体还进行了分片处理（分为 8 片，每片中又包含若干台机器），将一个群体的大 bitmap 拆成若干个小的 bitmap，再按照分片通过 hash 算法加载到不同分组机器的内存中，如下图：

这套方案是将物理机内存作为存储空间，并且使用自研的分片方案，再通过接口层直接读取 bitmap 数据来获取命中结果。

// 获取命中结果示例
Roaring64NavigableMap bitmap = getBitmap();
boolean isHit = bitmap.contains(offset);

需要注意的是由于对群体数据进行了分片存储，所以存和取的逻辑需要保持统一才能取到正确结果。

3）方案优缺点

通过 Redis 存储 ID 和 offset 的关系，人群数据拆分到 8 分组机器内存中，实现了群体命中接口的性能需求，总结此历史方案的优缺点，如下：

优点：

1、通过从 OSS 拉取文件方式，减少 CK 的查询次数，降低 CK 压力。

2、拆分逻辑自研，实际上是替换小文件，直接覆盖小文件更新速度快。

3、可分组内水平扩容机器，增加接口整体承载量，经过压测单机可到 30000QPS。

4、直接机器内存取值，快速返回结果，满足接口 TP999:50ms 内需求，但严重依赖机器性能。

缺点：

1、由于加载到机器内存，导致每次重启机器总要全量加载所有群体，启动非常慢（虽然经过优化启动效率已经提升了很多，但随着群体数量的增加重启也会越来越慢）

2、虽然分组内可以水平扩容，但是固定分组后，单机器的内存有限，一旦达到上限需要扩容分组时，必须成倍的扩容，导致扩容分组困难；

3、由于是自研的依赖于机器内存的存储方案，整体结构复杂，在运维的能力方面偏弱，运维的相关工具少；无法有效监控内存数据，这就间接造成了系统的稳定性较差。

4、使用物理机，曾经在大促期间占用了 100+ 台物理机，耗费资源很大。

四、最新方案

上述历史方案中，可以看到 ID 转 offset 的方案没有问题；主要问题出在判断 offset 是否包含在指定群体 bitmap 这一步中。所以在最新方案中，只对群体加载与 offset 的判断进行重新梳理及优化。

1）Redis 多集群多分片写入

思路和上文中的内存方案类似，都是部署多个集群（或分组），将群体 bitmap 进行拆分，并根据一定的路由策略存储到不同的集群上，通过不同的集群提供查询能力，如下图：

在新方案中，增加了一整套的群体推送服务，包括数据的新增，更新，删除，检测，重试以及预警等策略，大大增强了群体加载的可监测性及有效性，而在之前的方案中，非常缺少这些有效的运维手段。

2）数据加载策略

和内存加载不同的是，Redis 存储中不能再使用文件替换方案，只能采用其他的写入方案。

在这之中，还需要考虑如何保证写入的过程中不影响命中接口的性能。

针对群体数据，同样采用了拆分的思路，把每一个群体按照固定区间切成若干个小的 bitmap，并为每个小 bitmap 编号（即桶号，此桶号同样采用 bitmap 存储在索引里），缓存 key 为群体 code 加上桶号，以便快速取到 offset 值。

然后将小 bitmap 的数据转化成字符串的形式，并且拆分之后可以将数据按照 Hash 规则，均匀的分布到不同的缓存分片（我们最终的分片数达到了 16 个集群 *64 分片=1024 片）。如下图：

对于读取来说，假如人群命中有 1000 万 QPS，则每个集群分到 62.5 万，均摊到 64 个分片也才不到 1 万，可以说对缓存的单分片来说毫无压力。

对于写入来说，如果按照一个个 bit 写入的方式，耗时是不可接受的，在这方面我们采用的是将 Java 字节码转换为 Redis 字节码，最终以 set(key, string) 的方式进行数据写入。

这种方式具有以下优点：

1、单值小：每个 bitmap 最多有 65536 个 Offset（bit 位）,相当于最大 8kb，不会在缓存中产生较大 key 而导致性能差

2、写入快：每个 key 一次性写入到缓存,但是最多可以含有 65536 个 offset（ID），42.94 亿群体只需要 65536 次写入

3、查询效率高：getbit 支持查询 key 下面每个 offset，时间复杂度是 O(1)

4、拆分压缩数据：拆分多个小的 bitmap，相当于是对 bitmap 进行了压缩

在验证过程中，一个 42 亿的群体按 bit 写入需要 11.6 个小时，而采用字节码转换的方式写入，只需要 65~120 秒之间，写入效率提升 99.9%。

写入完成之后，使用 Redis 的 getbit 方法即可获取对应位的值，正如前文提到的即使是 1000w 的 QPS，也能达到高性能命中的目标。

// 获取指定偏移量的值，例如某ID对应的offset为3
jedis.getbit("crowdBitmap", 3);

3）方案优缺点

优点：

1、采用公司内部存储中间件，有专业的运维团队支持。

2、Redis 缓存支持主从备份，甚至是一主多从，支持高可用。

3、支持多分片，支持高并发场景，分摊到单个分片的流量较少。

4、写入与读取也很快，满足群体的快速更新需求。

5、只需要很少的机器写入与维护缓存，应用启动效率大大提升。

6、存储扩容方便，即使面对猛增的业务也可以从容应对。

缺点：

1、依赖于公司内部缓存中间件，倘若中间件出现问题，会造成很大影响；虽然理论上概率非常小。当然，也可以再做一个备份存储，这时需要考虑存储成本与收益之间的平衡。

五、现状及展望

上述方案上线后，可以看到非常明显的提升，接口整体 TP999 耗时从 40ms 下降到 25ms 左右 ，如下图：

目前最新的方案经过 23 年双十一大促的检验，TPS 峰值：49.7w/s，TP999 峰值：24ms，单次访问查询达到了 500w/s，（甚至在某一天军演压测时达到了 1000w/s）平稳顺利地完成新老方案的过渡。

随着业务的不断发展，CDP 中的群体数量还在持续增加中，按当前的增速评估，此方案已经能够完全支撑业务的持续发展，理论上可以支持到千万级 TPS 而无压力。

作者：京东科技 黎宇飞

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