背景

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) 的級別。 具體參見《工業界如何利用跳表、哈希表、位圖進行倒排索引加速？》：https://time.geekbang.org/column/article/221292?utm_source=related_read&utm_medium=article&utm_term=related_read

審核編輯 ：李倩