百萬并發(fā)場(chǎng)景中倒排索引與位圖計(jì)算的實(shí)踐

背景

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

樸素的解決方案

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

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

新的解決方案

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

算法詳細(xì)設(shè)計(jì)

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

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

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

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

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

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

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

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

復(fù)雜度分析

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

工程問題 - 壓縮位圖

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

適用場(chǎng)景分析

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

其他優(yōu)化方式

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

審核編輯 ：李倩