作者：京東物流 郎元輝

背景

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)的級別。

具體參見??工業界如何利用跳表、哈希表、位圖進行倒排索引加速？??