百万并发场景中倒排索引与位图计算的实践 _索引

来源 | OSCHINA 社区
作者 | 京东云开发者-京东物流朗元辉
原文链接：https://my.oschina.NET/jiagoushi/blog/5549507
背景
Promise 时效控单系统作为时效域的控制系统，在用户下单前、下单后等多个节点均提供服务，是用户下单黄金链路上的重要节点；控单系统主要逻辑是针对用户请求从规则库中找出符合条件的最优规则，并将该规则的时效控制结果返回客户端，比如因为临时疫情等原因针对仓、配、商家、客户四级地址等不同维度进行精细粒度的时效控制。
该系统也是 Promise 侧并发量最大的系统，双 11 高峰集群流量 TPS 在百万级别，对系统的性能要求非常高，SLA 要求在 5ms 以内，因此对海量请求在规则库 (几十万) 中如何快速正确匹配规则是该系统的技术挑战点。
朴素的解决方案
按照朴素的思想，在工程建设上，通过异步方式将规则库逐行缓存到 redis，Key 为规则条件，Value 为规则对应结果；当用户请求过来时，对请求 Request (a,b,c,d..) 中的参数做全组合，根据全组合出的 Key 尝试找出所有可能命中的规则，再从中筛选出最优的规则。如下图所示

文章插图
该方案面临的问题是全组合的时间复杂度是 2**n,n≈12；算法的时间复杂度高且算法稳定性差，最差情况一次请求需要 4096 次计算和读取操作。当然在工程上我们可以使用本地缓存做一些优化，但是无法解决最根本的性能问题。架构简图如下所示：

文章插图
新的解决方案
上面方案是从行的角度看待匹配定位的，能够命中的行的每一列必然也是符合条件的，这里面存在某种隐约的内在联系。能否反过来思考这个问题，为此我们尝试进行新的方案，当然架构简图依然如上图所示，核心优化的是命中算法。
新的方案整体采用列的倒排索引和倒排索引位运算的方式，使得计算复杂度由原来的 2n 降至 n**，且算法稳定性有非常好的保证。其中列的倒排索引是对每列的值和所分布的行 ID (即 Posting List) 建立 KV 关系，倒排索引位运算是对符合条件的列倒排索引进行列间的位运算，即通过联合查询以便快速找到符合条件的规则行。
【百万并发场景中倒排索引与位图计算的实践】算法详细设计1. 预计算生成列的倒排索引和位图
通过对每列的值进行分组合并生成 Posting List，建立列值和 Posting List 的 KV 关系。以下图为例，列 A 可生成的倒排索引为：301={1},201={2,3,4,5} 等，需要说明的一点，空值也是一种候选项，也需要生成 KV 关系，如 nil={7} 。

文章插图
2. 生成列的倒排索引对应位图
将步骤 1 的倒排索引转成成位图，方便后续的位图计算，转换规则为行 ID 对应位图的下标位（步骤 1、2 可以合并操作）。

文章插图
3. 根据用户请求查找列位图，通过位图计算生成候选规则集
将用户请求中的入参作为 Key，查找符合条件的位图，对每一列进行列内和空值做 || 运算，最后列间位图做 & 运算，得到的结果是候选规则集，如下图所示：

文章插图
4. 从候选规则库中，根据业务优先级排序，查找最优的规则
以候选规则为基点，按照业务优先级排序，进行逐级位运算 &，当遍历完或位运算为 0 时，找到最后不为空的即为最优规则，该过程是从候选规则库逐渐缩小最优范围的过程。需要说明某列当用户请求位图不存在时，需要使用对应的空位图进行参与，以 B 列为例，入参 B_1102 不存在，需要使用 B_nil 参与 & 。