共计 2413 个字符，预计需要花费 7 分钟才能阅读完成。
作者：京东物流 郎元辉
背景
Promise 时效控单零碎作为时效域的控制系统，在用户下单前、下单后等多个节点均提供服务，是用户下单黄金链路上的重要节点；控单零碎次要逻辑是针对用户申请从规定库中找出符合条件的最优规定，并将该规定的时效管制后果返回客户端，比方因为长期疫情等起因针对仓、配、商家、客户四级地址等不同维度进行精密粒度的时效管制。
该零碎也是 Promise 侧并发量最大的零碎，双 11 顶峰集群流量 TPS 在百万级别，对系统的性能要求十分高，SLA 要求在 5ms 以内，因而 对海量申请在规定库 (几十万) 中如何疾速正确匹配规定是该零碎的技术挑战点。
奢侈的解决方案
依照奢侈的思维，在工程建设上，通过异步形式将规定库逐行缓存到 Redis，Key 为规定条件,Value 为规定对应后果；当用户申请过去时，对申请 Request(a,b,c,d..)中的参数做全组合，依据全组合出的 Key 尝试找出所有可能命中的规定，再从中筛选出最优的规定。如下图所示
该计划面临的问题是全组合的工夫复杂度是 2 n,n≈12；算法的工夫复杂度高且算法稳定性差 **，最差状况一次申请须要 4096 次计算和读取操作。当然在工程上咱们能够应用本地缓存做一些优化，然而无奈解决最基本的性能问题。架构简图如下所示：
![]()
新的解决方案
下面计划是从行的角度对待匹配定位的，可能命中的行的每一列必然也是符合条件的，这外面存在某种隐约的内在联系。是否反过来思考这个问题，为此咱们尝试进行新的计划，当然架构简图仍然如上图所示，外围优化的是命中算法。
新的计划整体采纳 列的倒排索引和倒排索引位运算 的形式，使得 计算复杂度由原来的 2 n 降至 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 参加 &。
复杂度剖析
通过下面的例子咱们能够看到，在工夫复杂度方面查找候选规定集时，进行一轮 || 运算，一轮 & 运算；在查找最优规定时进行一轮 & 运算，所以 整体复杂度是 3n≈n。
在空间复杂度方面，相比原来的行式存储，倒排索引的存储形式，每列都须要存储行 ID，相当于多了 (n-1)*Posting List 存储空间，当然这是粗略计算，因为实际上行 ID 的存储最终转换为位图存储，在空间上有十分大的压缩空间。
工程问题 - 压缩位图
如果倒排索引位图十分稠密，零碎会存在十分大的空间节约。咱们举一个极其 case，若千万规定库中命中的行 ID 是第 1000 万位，依照传统形式 BitSet 进行存储，须要耗费 1.2MB 空间，在内存中占用存在重大节约，有没有压缩优化计划，在 RoaringBitMap 压缩位图计划中咱们找到，雷同场景在压缩位图形式下仅占 144bytes；即便在 1000 万的位图空间，咱们随机存储 1 万个值，两者比也是在 31K vs 2MB，近 100 倍的差距，总的来说 RoaringBitMap 压缩率十分大。
RoaringBitMap 实质上是将大块的 bitmap 拆分成各个小块，其中每个小块在须要存储数据的时候才会存在，所以当进行交加或并集运算的时候，RoaringBitMap 只须要去计算存在的块而不须要像 bitmap 那样对整个大块进行计算，既做到了压缩的存储又做到计算性能的晋升。
以下图 821697800 为例，对应的 16 进制数为 30FA1D08，其中高 16 位为 30FA，低 16 位为 1D08。先用二分查找从一级索引（即 Container Array）中找到数值为 30FA 的容器，该容器是一个 Bitmap 容器, 而后在该容器查找低 16 位的数值 1D08，即十进制下 7432，在 Bitmap 中找到相应的地位，将其置为 1 即可。
实用场景剖析
回顾下面的设计方案咱们能够看到，这种形式仅实用于 PostingList 简略如行 ID 的模式，如果是简单对象就不适宜用位图来存储。另外仅实用于等值查问，不适用于 like、in 的范畴查问，为什么有这种局限性？因为这种形式依赖于搜寻条件的空间，在计划中咱们将值的条件作为搜寻的 Key，值的条件空间心愿尽可能是一个无限的、不便穷举的、小的空间。而范畴查问导致这个空间变成难以穷举、近乎有限扩张的、所以不实用。
其余优化形式
除了应用位运算的形式对倒排索引减速，思考到 Posting List 的有序性，还有其余的形式比方应用跳表、Hash 表等形式，以 ES 中采纳的跳表为例，进行 & 运算理论就是在查找两个有序 Posting List 公共局部，以互相二分查找的模式，将工夫复杂度管制在 log(n)的级别。
具体参见工业界如何利用跳表、哈希表、位图进行倒排索引减速？
