廣告倒排服務極致優化

語言: CN / TW / HK

時間 2022-12-16 07:01:38 百度Geek説

作者 | XY

導讀

漏斗優化是檢索系統不變的話題，過去一年來，廣告漏斗優化一改往日做“加法”，而通過簡化漏斗，提升全系統一致性。如百度這樣龐大的廣告庫規模、高流量規模以及複雜的業務規則，要做到極簡的漏斗層次，需要最高效的策略設計和最極致的工程實現。本文重點介紹了百度Geeker們在倒排數據結構上如何“摳細節”達到倒排召回無截斷，對大家做高性能系統也將有所啟發。

全文6162字，預計閲讀時間16分鐘。

01 業務背景 - 全系統Limitless

大家都清楚，廣告漏斗包括召回、粗排、精排這三部分，理想中的漏斗上寬下窄很規整，而現實中因為種種原因，漏斗已經略顯飄逸了，這種不一致性會帶來很多業務繼續發展的複雜度。我們希望達到：模型一致，精簡漏斗，全系統Limitless。

我們對Limitless的認識：細節處見真章，挑戰軟件工程性能極限，方能漏斗近似無截斷。

今天想跟大家聊聊『BS Limitless』項目裏我們怎麼摳細節的，整個項目其實挑戰很大，網絡、計算和存儲方方面面都涉及到，一篇短文很難講透，因此我決定選一個數據結構-倒排表，讓大家感受到『極致』優化。

02 技術背景 - 倒排表

先介紹一下優化前的倒排表，它的組成比較經典特點，HashMap<keysign, SkipList>。一次檢索pv根據觸發的N個詞（keysign）掃描拉鍊（SkipList），廣告業務投放特點天然會有長鏈、超長鏈，為此鏈表需要有序，做過漏斗的同學知道，在倒排階段排序能用的信息其實是很少的，這也説明了掃描Limitless對業務的高價值。

這樣一個小小的數據結構承擔了各方的要求，1、讀性能決定有限時間能放出多少量，2、實時插入決定客户投放能不能立即生效，3、單庫規模巨大，內存損耗要低。對工程的合理要求，確實是既要...又要...還要...。在Limitless的大背景下，我們要顯著提升1達到scan limitless，但是不能損害到2和3。

回過頭來看，這麼簡單的數據結構，Limitless的瓶頸到底是什麼？大家回憶一下計算機體系結構的內容。cpu並不直接訪存，而通過層層緩存到達內存，存儲層次越低，它的容量越大但延遲越高，mem和L2、L1之間有量級差距[1]。List這種數據結構顯然缺乏空間局部性。

緩存不親和的List對比緩存友好的Array，在掃描上究竟有多差呢？我們做了如下的評測，其中橫軸代表鏈長或數組長度，縱軸是平均到單條元素的掃描耗時，結果是10+差距。換成數組Array，也是不行的，客户要求實時生效，為了低效拷貝損耗需要O(2N)的增長速度，內存成本要求也不能滿足。

03 方案 - HybridIndexTable

我們針對業務的特點和Limitless的要求進行極致設計和優化，推出了新一代的內存數據結構HybridIndexTable，簡稱HIT。升級後的倒排表：

1、用HashMap索引keysign，

2、短鏈採用連續存儲，長鏈則是一棵葉子連續存儲的前綴樹，前綴樹則參考了業界AdaptiveRadixTree，簡稱ART，

3、短鏈和葉子的）連續存儲都採用了自研的RowContainer，簡稱RC。

在簡短的數據結構之外，還要和大家分享兩個關鍵細節：

1、Key序路由兜底超長鏈有序，

2、RC間無序，以RC為單位掃描。

HIT這樣的數據結構有如下三點優勢，恰到好處地滿足了前面的三個要求。

讀取性能高，連續存儲+前綴樹降低cachemiss，線程安全做法reader-friendly，還有面向負載的優化；
更新時效性高，連續存儲但append-only/mark-delete；
內存損耗少，應用了大量的自適應算法。

HIT上線後拿到了非常可觀的業務收益，Limitless的道路上技術就是生產力！

04 HIT緣起，內存索引ModernCPU的探索

內存索引領域已在面向Modern Cpu深耕，ModernCpu由於Cpu運行得很快，使得緩存一致性的影響、訪存的影響成為高性能的瓶頸。內存索引在2000s也有些階段性的標誌成果，包括FAST[4]，它是面向體系結構的數據結構設計的典型，無論是思想還是成果非常適用於靜態數據；CSBtree[2][3]，它提出數據結構上通過KV分離，使得一次訪存能比較多個Key，同時還提出了SMO的無鎖解法；還有ART前綴樹[5]。有序索引中BTree居多，我們為何注意到了前綴樹呢？

鏈表類型的緩存失效發生在每次訪問下一個節點，緩存失效複雜度O(n)。排序樹類型的緩存失效發生在訪問下一層節點，緩存失效複雜度O(lgn)。而對於前綴樹來説，緩存失效只和鍵長k(len)/扇出s(pan) 有關，緩存失效複雜度O(k/s)。如下圖[5]，假設k是鍵長的bit數，隨着存儲數據量上漲2^(k/8)、2^(k/4)、...，完全平衡樹高不斷增加，分別是k/8、k/4、...，而對於一顆前綴樹，樹高對於給定的span是恆定的，如針對span=8和4，樹高分別是k/8、k/4。前綴樹更加緩存友好。

這裏簡單介紹下前綴樹，英文是Trie、Prefix tree或Digit tree，左圖是維基百科的實例，這是個典型的沒有任何優化的前綴樹，一方面，只有單分叉的情況下也多分出一級，比如inn；另一方面，由於在分支節點需要分配 2 ^ s * pointer 的內存，對於實際扇出極少的場景，內存損耗非常大。

RadixTree是一種通過合併前綴（PathCompression）優化內存的前綴樹。合併前綴是指壓縮掉僅有一個孩子的分支節點，這樣存在的節點或者是葉子節點，或者是有分叉的分支節點。名字中的radix=2^span，它在radix=2的情況下，也叫做Patricia tree[6]。Linux PageCache頁面緩存用的是RadixTree，以太坊幣ETH的核心數據結構是Merkle Patricia tree。中間圖是按照RadixTree重新組織的。

即便有合併前綴，由於大部分扇出是填不滿，浪費了空間。比如上面例子的RadixTree(radix = 256, s=8)，那麼即便在第一級只有t、A、i，也需要多分配 253 * 8 ~ 1Kbytes。調整radix(span = lg(radix))是一種內存優化方式，但這提高了樹高增加了緩存失效[5]。2013年，A(daptive)R(adix)T(ree)[6]用自適應的節點類型來解決問題，用適合數據分佈的最緊湊的節點表示，而不是固定的Node256。論文中 InnerNode 分為 Node4、Node16、Node80和Node256這四種，按照實際需要的分叉數選擇，通過類分攤算法(Amortization Alg)複雜度分析方法，可證明理論上這棵樹內存複雜度是O(52N)，其中N是存儲數據量。ART論文提供了一種方式，在提高扇出降低樹高的同時，還能大幅度降低內存開銷。按照ART重新組織上面例子中的RadixTree，如圖所示。

05 HIT優化，RC實現ShortList+LongList Leaf的自適應

我們定義 RC_x 為不超過x個元素的連續存儲空間，支持Append-Only和Mark-Delete操作，單元素額外成本不超過8byte。接下來看RC的設計要點。

既然RC被設計為只支持Append-Only/Mark-Delete修改的數據類型，為此元數據需有cursor和valids。同時針對不同容量的RC，為了控制理論上單條數據損耗不超過8byte，需要分別設計和實現，我們不希望引入繼承virtual指針的內存開銷，採用根據type分發的實現方案。

RC1元數據8byte，可輕鬆容納cursor和valids，那麼下一階的RC_x，x是幾呢？按照分攤分析方法，RC_x至少有2個元素，也就是16byte的預算，在分配前還是要先看選型，RC_x需要變長因此元數據還有留出來8byte給dataptr，這樣的話，valids不能採用std::bitset<N>，因為bitset的實現至少需要一個字也就是8byte。valids和cursor用bit field 的方式來做分配看上去還是比較充裕的，存放58個數據元素都沒問題，實際上考慮到系統分配器的特點，我們並沒有這樣做。

主流的系統分配器大部分是slab-based，在實際應用時，除過理論單條數據損耗，還需要考慮因內存池帶來的對齊損耗。一方面，RC1所在的鏈約佔整體的80%，這樣海量的小對象適合用內存池來管理，為避免檢索時候多一次內存池地址轉化，我們把vaddr存儲在元數據中，釋放時再使用。另一方面，分散式地分配 N*sizeof(data)，會造成每類slab的內部非充分使用，為此RC16+採取了Array of data_array的組織方式。

RC設計有不少實現細節，包括什麼時候一次性多申請多少空間，控制內存成本和操作效率。時間關係就不多介紹了。

06 LeafCompaction優化稀疏

前綴樹在緩存失效方面優於BTree，ART進一步地採用自適應節點類型，既能增加扇出優化緩存訪問，又能控制內存損耗。然而實際應用中，ART仍然受到key值分佈稀疏的影響，這表現為在部分子樹扇出很小很深（較Node256），樹高無法全面降低，從而影響點查的緩存。HOT[7]提出一種自適應動態span提升平均扇出，進而降低樹高的方法，具體來説，定義節點最大扇出k，尋找一種樹的劃分，在每個劃分的分支節點數不大於k-1的前提下，沿着葉子到根的劃分數的最大值取最小，這樣的實際效果就是對於稀疏段的span足夠大，對於密集段的span足夠小，整體扇出逼近最大扇出k。如中圖所示。

對於ART+目標的連續性應用場景來説，僅僅提升扇出降低樹高是不夠的，我們發現存在扇出很高，但扇出後葉子數據很稀疏，同時總數據量也不高，這顯然影響了掃描性能。我們提出葉子合併（LeafCompaction），它包括判定器和操作算法。給定一個分支節點，如果它被判定為合併，則用一個葉子節點替換它，該葉子節點的前綴同該樹的前綴，內容是該樹的數據，後續插入/刪除過程遵從葉子的操作方式；如果它被判定為不變，則保持。給定一個葉子節點，如果它被判定為分裂，則用一顆樹替換它，該樹的前綴同該葉子的前綴，內容通過BulkLoad的方式生成，如果它被判定為不變，則保持。判定器的默認算法依據子樹平均和總數，節點壓縮率高達90%。如圖所示。

實際評測效果，平均到單條數據的掃描性能，稀疏場景下LC版本優於普通版本一倍。

07 RCU面向讀者實現讀寫安全

一般使用深度優化的細粒度鎖來保護倒排數據結構的並行操作，但鎖競爭帶來的性能抖動，完全抹殺了訪存優化，我們必須探索出一種無鎖(lock-free)安全模式。提到無鎖lock-free，大家都覺得是CAS，其實一方面CAS不是銀彈，CAS常見的寫法是whileloop直到成功，如果有10個線程都在高速修改一個鏈表尾巴，這時候CAS只是説把陷入內核省掉了，但是還是要不停地重做，這並不能完全釋放並行的能力，最好能從業務上打散。另一方面，CAS也有問題，多核下 CPU cache coherence protocol總線仲裁，導致破壞流水線。

Read-Copy-Update 是Linux內核中的一種同步機制，被用來降低讀者側的鎖開銷，同時提供安全的寫機制，具體地來説，多個讀者（reader）並行地訪問臨界資源，寫者（writer）在更新臨界資源（critical resource）時候，拷貝一份副本作為修改基礎，修改後原子性替換掉。當所有讀者釋放了這個臨界資源後（Grace peroid），再釋放資源（reclaimer）。

Linux還需要較複雜的機制：

1、探測靜止狀態 Quiescent Status，當所有CPU都經歷過至少一次靜止狀態時，才認為Grace peroid結束；

2、多寫者間同步，避免丟失修改。

對於檢索服務來説，它有下面3個特點，這些特點大幅度地降低了我們的設計複雜度：

1、單寫者，我們可能有其他的準備線程並行做更重的準備工作，但只有Reload單線程負責物料更新；

2、非事務，檢索線程召回的多條數據間沒有嚴格約束；

3、讀者持有時間有限，檢索線程有嚴格的超時要求。這些特點大幅度地降低了我們的設計複雜度。

08 LearnedIndex面向Workload自適應

最後，我再介紹下進行中的工作L2I。剛才都是對單鏈的優化緩存失效，已有不錯的效果，但從更宏觀全局的視角來看，我們系統還有可挖掘空間：一方面，廣告投放天然導致存在較多超短鏈，另一方面，需要掃描過程跨表查詢做各類過濾邏輯等等。這些已不單單是數據分佈的問題，而是在線流量和客户投放的匹配，需要用更智能的手段來解決。

行業裏面，JeffDean&TimK 聯合發表了Learned Index[8]引入RMI、CDF的模型，後續TimK團隊又有動態化、多維索引、sagedb等多種方向的發展，本質是構建面向負載的半自動化尋優系統。我們既要引入負載特徵，但由於掃描過程很輕量，不能做過重的預測，同時作為對客户有承諾的商業系統，不能產生錯誤。借鑑L2I的思想，我們還做了兩個事情，一方面、通過觸發出口離線計算共現關係，用來合併超短鏈、短鏈，用上HIT的高性能的連續掃描能力；另一方面，取熵最大的組合<pid,cid>，提取到倒排表的bit位，確定不過1，否則為0，對於後者 fallback到點查計算。

——END——

參考資料：

[1] Software Engineering Advice from Building Large-Scale Distributed Systems, 2002

[2] Cache conscious indexing for decision-support in main memory,1999

[3] Making B+-trees cache conscious in main memory,2000

[4] FAST: fast architecture sensitive tree search on modern CPUs and GPUs,2010

[5] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases,2013

[6] PATRICIA --Practical Algorithm To Retrieve Information Coded in Alphanumeric,1968

[7] HOT: A height optimized trie index for main-memory database systems, 2018

[8] The Case for Learned Index Structures, 2018

推薦閲讀：

為什麼 OpenCV 計算的視頻 FPS 是錯的