背景

Promise 時效控單系統(tǒng)作為時效域的控制系統(tǒng)，在用戶下單前、下單后等多個節(jié)點均提供服務(wù)，是用戶下單黃金鏈路上的重要節(jié)點；控單系統(tǒng)主要邏輯是針對用戶請求從規(guī)則庫中找出符合條件的最優(yōu)規(guī)則，并將該規(guī)則的時效控制結(jié)果返回客戶端，比如因為臨時疫情等原因針對倉、配、商家、客戶四級地址等不同維度進行精細粒度的時效控制。 該系統(tǒng)也是 Promise 側(cè)并發(fā)量最大的系統(tǒng)，雙 11 高峰集群流量 TPS 在百萬級別，對系統(tǒng)的性能要求非常高，SLA 要求在 5ms 以內(nèi)，因此對海量請求在規(guī)則庫 (幾十萬) 中如何快速正確匹配規(guī)則是該系統(tǒng)的技術(shù)挑戰(zhàn)點。

樸素的解決方案

按照樸素的思想，在工程建設(shè)上，通過異步方式將規(guī)則庫逐行緩存到 Redis，Key 為規(guī)則條件，Value 為規(guī)則對應(yīng)結(jié)果；當(dāng)用戶請求過來時，對請求 Request (a,b,c,d..) 中的參數(shù)做全組合，根據(jù)全組合出的 Key 嘗試找出所有可能命中的規(guī)則，再從中篩選出最優(yōu)的規(guī)則。如下圖所示

該方案面臨的問題是全組合的時間復(fù)雜度是 2**n,n≈12；算法的時間復(fù)雜度高且算法穩(wěn)定性差，最差情況一次請求需要 4096 次計算和讀取操作。當(dāng)然在工程上我們可以使用本地緩存做一些優(yōu)化，但是無法解決最根本的性能問題。架構(gòu)簡圖如下所示：

新的解決方案

上面方案是從行的角度看待匹配定位的，能夠命中的行的每一列必然也是符合條件的，這里面存在某種隱約的內(nèi)在聯(lián)系。能否反過來思考這個問題，為此我們嘗試進行新的方案，當(dāng)然架構(gòu)簡圖依然如上圖所示，核心優(yōu)化的是命中算法。 新的方案整體采用列的倒排索引和倒排索引位運算的方式，使得計算復(fù)雜度由原來的 2n 降至 n**，且算法穩(wěn)定性有非常好的保證。其中列的倒排索引是對每列的值和所分布的行 ID (即 Posting List) 建立 KV 關(guān)系，倒排索引位運算是對符合條件的列倒排索引進行列間的位運算，即通過聯(lián)合查詢以便快速找到符合條件的規(guī)則行。

算法詳細設(shè)計

1. 預(yù)計算生成列的倒排索引和位圖

通過對每列的值進行分組合并生成 Posting List，建立列值和 Posting List 的 KV 關(guān)系。以下圖為例，列 A 可生成的倒排索引為：301={1},201={2,3,4,5} 等，需要說明的一點，空值也是一種候選項，也需要生成 KV 關(guān)系，如 nil={7}。

2. 生成列的倒排索引對應(yīng)位圖

將步驟 1 的倒排索引轉(zhuǎn)成成位圖，方便后續(xù)的位圖計算，轉(zhuǎn)換規(guī)則為行 ID 對應(yīng)位圖的下標(biāo)位（步驟 1、2 可以合并操作）。

3. 根據(jù)用戶請求查找列位圖，通過位圖計算生成候選規(guī)則集

將用戶請求中的入?yún)⒆鳛?Key，查找符合條件的位圖，對每一列進行列內(nèi)和空值做 || 運算，最后列間位圖做 & 運算，得到的結(jié)果是候選規(guī)則集，如下圖所示：

4. 從候選規(guī)則庫中，根據(jù)業(yè)務(wù)優(yōu)先級排序，查找最優(yōu)的規(guī)則

以候選規(guī)則為基點，按照業(yè)務(wù)優(yōu)先級排序，進行逐級位運算 &，當(dāng)遍歷完或位運算為 0 時，找到最后不為空的即為最優(yōu)規(guī)則，該過程是從候選規(guī)則庫逐漸縮小最優(yōu)范圍的過程。需要說明某列當(dāng)用戶請求位圖不存在時，需要使用對應(yīng)的空位圖進行參與，以 B 列為例，入?yún)?B_1102 不存在，需要使用 B_nil 參與 &。

復(fù)雜度分析

通過上面的例子我們可以看到，在時間復(fù)雜度方面查找候選規(guī)則集時，進行一輪 || 運算，一輪 & 運算；在查找最優(yōu)規(guī)則時進行一輪 & 運算，所以整體復(fù)雜度是 3n≈n。 在空間復(fù)雜度方面，相比原來的行式存儲，倒排索引的存儲方式，每列都需要存儲行 ID，相當(dāng)于多了 *(n-1)Posting List 存儲空間，當(dāng)然這是粗略計算，因為實際上行 ID 的存儲最終轉(zhuǎn)換為位圖存儲，在空間上有非常大的壓縮空間。

工程問題 - 壓縮位圖

如果倒排索引位圖非常稀疏，系統(tǒng)會存在非常大的空間浪費。我們舉一個極端 case，若千萬規(guī)則庫中命中的行 ID 是第 1000 萬位，按照傳統(tǒng)方式 BitSet 進行存儲，需要消耗 1.2MB 空間，在內(nèi)存中占用存在嚴重浪費，有沒有壓縮優(yōu)化方案，在 RoaringBitMap 壓縮位圖方案中我們找到，相同場景在壓縮位圖方式下僅占 144bytes；即使在 1000 萬的位圖空間，我們隨機存儲 1 萬個值，兩者比也是在 31K vs 2MB，近 100 倍的差距，總的來說 RoaringBitMap 壓縮率非常大。 RoaringBitMap 本質(zhì)上是將大塊的 bitmap 拆分成各個小塊，其中每個小塊在需要存儲數(shù)據(jù)的時候才會存在，所以當(dāng)進行交集或并集運算的時候，RoaringBitMap 只需要去計算存在的塊而不需要像 bitmap 那樣對整個大塊進行計算，既做到了壓縮的存儲又做到計算性能的提升。 以下圖 821697800 為例，對應(yīng)的 16 進制數(shù)為 30FA1D08， 其中高 16 位為 30FA，低 16 位為 1D08。先用二分查找從一級索引（即 Container Array）中找到數(shù)值為 30FA 的容器，該容器是一個 Bitmap 容器，然后在該容器查找低 16 位的數(shù)值 1D08，即十進制下 7432，在 Bitmap 中找到相應(yīng)的位置，將其置為 1 即可。

適用場景分析

回顧上面的設(shè)計方案我們可以看到，這種方式僅適用于 PostingList 簡單如行 ID 的形式，如果是復(fù)雜對象就不適合用位圖來存儲。另外僅適用于等值查詢，不適用于 like、in 的范圍查詢，為什么有這種局限性？因為這種方式依賴于搜索條件的空間，在方案中我們將值的條件作為搜索的 Key，值的條件空間希望盡可能是一個有限的、方便窮舉的、小的空間。而范圍查詢導(dǎo)致這個空間變成難以窮舉、近乎無限擴張的、所以不適用。

其他優(yōu)化方式

除了使用位運算的方式對倒排索引加速，考慮到 Posting List 的有序性，還有其他的方式比如使用跳表、Hash 表等方式，以 ES 中采用的跳表為例，進行 & 運算實際就是在查找兩個有序 Posting List 公共部分，以相互二分查找的形式，將時間復(fù)雜度控制在 log (n) 的級別。 具體參見《工業(yè)界如何利用跳表、哈希表、位圖進行倒排索引加速？》：https://time.geekbang.org/column/article/221292?utm_source=related_read&utm_medium=article&utm_term=related_read

審核編輯 ：李倩