廣告倒排服務極致優化

語言: CN / TW / HK

作者 | 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 是錯的

百度 Android 直播秒開體驗優化

iOS SIGKILL 訊號量崩潰抓取以及優化實踐

如何在幾百萬qps的閘道器服務中實現靈活排程策略

深入淺出DDD程式設計

百度APP iOS端記憶體優化實踐-記憶體管控方案