作者：京东物流 郎元辉
背景
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参与&。
复杂度剖析
经过上面的比方咱们能够看到，在时刻复杂度方面查找候选规矩集时，进行一轮||运算，一轮&运算；在查找最优规矩时进行一轮&运算，所以整体复杂度是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)的等级。
详细参见工业界如何利用跳表、哈希表、位图进行倒排索引加快？
