一、前言

隨著得物業(yè)務規(guī)模的不斷增加，推薦業(yè)務也越來越復雜，對推薦系統(tǒng)也提出了更高的要求。我們于2022年下半年啟動了DGraph的研發(fā)，DGraph是一個C++項目，目標是打造一個高效易用的推薦引擎。推薦場景的特點是表多、數(shù)據(jù)更新頻繁、單次查詢會涉及多張表。了解這些特點，對于推薦引擎的設計非常重要。通過閱讀本文，希望能對大家了解推薦引擎有一定幫助。為什么叫DGraph？因為推薦場景主要是用x2i(KVV)表推薦為主，而x2i數(shù)據(jù)是圖(Graph)的邊，所以我們給得物的推薦引擎取名DGraph。

二、正文

整體架構

DGraph可以劃分為索引層&服務層。索引層實現(xiàn)了索引的增刪改查。服務層則包含Graph算子框架、對外服務、Query解析、輸出編碼、排序框架等偏業(yè)務的模塊。

圖1 DGraph 整體框架

索引框架

在DGraph里面參考圖1，索引的管理被抽象成5個模塊：Reader 索引查詢、Writer 索引寫入、Compaction 增量全量合并、LifeCycle 索引生命周期管理、Schema 索引配置信息。

不同類型的索引只需要實現(xiàn)上面的5個類即可，不同類型的索引只需要關注索引本身的實現(xiàn)方式，而不需要關心索引的管理問題，通過這種模式，索引管理模塊實現(xiàn)了索引的抽象管理，如果業(yè)務需要，可以快速在DGraph面加入一種新的索引。

DGraph數(shù)據(jù)的管理都是按表(table)進行的(圖2)，復雜的索引會使用到DGraph的內(nèi)存分配器D-Allocator，比如KVV/KV的增量部分 & 倒排索引 & 向量索引等。在DGraph所有數(shù)據(jù)更新都是DUMP(耗時)->索引構建(耗時)->引擎更新(圖3)，索引平臺會根據(jù)DGraph引擎的內(nèi)存情況自動選擇在線更新還是分批重啟更新。這種方式讓DGraph引擎的索引更新速度&服務的穩(wěn)定性得到了很大的提升。

圖2 DGraph索引組織關系

圖3 Graph索引更新

索引

數(shù)據(jù)一致性

相比訂單、交易等對于數(shù)據(jù)一致性要求非常嚴格的場景。在搜推場景，數(shù)據(jù)不需要嚴格的一致性，只需要最終一致性。若一個集群有N個引擎，通過增量向集群寫入一條數(shù)據(jù)，每個引擎是獨立更新這條數(shù)據(jù)的，因為是獨立的，所以有些機器會更新快一點，有些機器會更新慢一點，這個時間尺度在毫秒級附近，理論上在某一時刻，不同引擎上的數(shù)據(jù)是不一致的，但這對業(yè)務影響不大，因為最終這些數(shù)據(jù)會保持一致。

最終一致性這個特性非常重要，因為實現(xiàn)嚴格的一致性很復雜，2PC&3PC等操作在分布式場景下，代價很高。所以事情就變得簡單了很多，引擎的讀寫模型只需要滿足最終一致性即可。這可以讓我們的系統(tǒng)，更偏向于提供更高的讀性能。這個前提也是DGraph目前很多設計的根因。

讀寫模型

推薦場景需要支持在線服務更新數(shù)據(jù)，因此引擎有讀也有寫，所以它也存在讀寫問題。另外引擎還需要對索引的空間進行管理，類似于JAVA系統(tǒng)里面JVM的內(nèi)存管理工作，不過引擎做的簡單很多。讀寫問題常見的解決方案是數(shù)據(jù)加鎖。數(shù)據(jù)庫和大部分業(yè)務代碼里面都可以這么做，這些場景加鎖是解決讀寫問題最靠譜的選擇。但是在推薦引擎里面，對于讀取的性能要求非常高，核心數(shù)據(jù)的訪問如果引入鎖，會讓引擎的查詢性能受到很大的限制。

推薦引擎是一個讀多寫少的場景，因此我們在技術路線上選擇的是無鎖數(shù)據(jù)結構RCU。RCU在很多軟件系統(tǒng)里面有應用，比如Linux 內(nèi)核里面的kfifo。大部分RCU的實現(xiàn)都是基于硬件提供的CAS機制，支持無鎖下的單寫單讀、單寫多讀、多寫單讀等。DGraph選擇的是單寫多讀+延遲釋放類型的無鎖機制。效率上比基于CAS機制的RCU結構好一點，因為CAS雖然無鎖，但是CAS會鎖CPU緩存總線，這在一定程度上會影響CPU的吞吐率。

如果簡單描述DGraph的索引結構，可以理解為實現(xiàn)了RcuDoc(正排)、RcuRoaringBitMap(倒排)、RcuList、RcuArray、RcuList、RcuHashMap等。用推薦場景可推池來舉一個例子，可推池表的存儲結構可以抽象成RcuHashMap<Key, RcuDoc> table。這里用RcuList來舉例子，可以用來理解DGraph的RCU機制。其中MEMORY_BARRIER是為了禁止編譯器對代碼重排，防止亂序執(zhí)行。

圖 4 RcuList 元素插入

圖5 RcuList刪除元素

圖5是刪除的例子，簡單講一下，在RcuList里面，刪除一個元素的時候，比如Node19，因為刪除期間可能有其他線程在訪問數(shù)據(jù)，所以對List的操作和常規(guī)的操作有些不同，首先將Node11的Next節(jié)點指向Node29，保證后面進來的線程不會訪問Node19，然后把Node19的Next指向Null，因為這個時候可能還有線程在訪問Node19，因此我們不能立即把Node19刪除，而是把Node19放入刪除隊列，延遲15秒之后再刪除，另外刪除的動作不是主動的，而是由下一個需要申請內(nèi)存的操作觸發(fā)，因此刪除是延時且Lazy的。

數(shù)據(jù)持久化

在DGraph里面我們構建了一個內(nèi)存分配器D-Allocator(每個索引只能申請一個/可選)，用于存儲增量或者倒排索引等復雜數(shù)據(jù)結構。采用了類似TcMalloc按大小分類的管理模式。D-Allocator利用Linux系統(tǒng)的mmap方法每次從固定的空間申請128M ~ 1GB大小，然后再按塊劃分&組織。由系統(tǒng)的文件同步機制保證數(shù)據(jù)的持久化。目前64位x86 CPU實際尋址空間只有48位，而在Linux下有效的地址區(qū)間是 0x00000000 00000000 ~ 0x00007FFF FFFFFFFF 和 0xFFFF8000 00000000 ~ 0xFFFFFFFF FFFFFFFF 兩個地址區(qū)間。而每個地址區(qū)間都有128TB的地址空間可以使用，所以總共是256TB的可用空間。在Linux下，堆的增長方向是從下往上，棧的增長方向是從上往下，為了盡可能保證系統(tǒng)運行的安全性，我們把0x0000 1000 0000 0000 到 0x0000 6fff ffff ffff分配給索引空間，一共96TB，每個內(nèi)存分配器可以最大使用100GB空間。為了方便管理，我們引入了表keyID，用于固定地址尋址，表地址 = 0x0000 1000 0000 0000 + keyId * 100GB, 引擎管理平臺會統(tǒng)一管理每個集群的keyId，偶數(shù)位分配給表，奇數(shù)位保留作為表切換時使用。keyId 0 - 600 分配給集群獨享表，keyId 600-960分配給全局表。因此單個集群可以最多加載300個獨享表+最多180共享表(備注：不是所有表都需要D-Allocator，目前沒有增量的KVV/KV表不受這個規(guī)則限制)。

圖6 引擎內(nèi)存管理

KV/KVV索引

KV -> Map<Key, Object> 、 KVV -> Map<Key, List<Object>>。推薦引擎絕大部分表都是KVV索引，數(shù)據(jù)更新特點是，定期批量更新 & 大部分表沒有實時增量。針對這些業(yè)務特性，DGraph設計了內(nèi)存緊湊型KV\KVV索引(圖7)。這里簡單講一下DenseHashMap的實現(xiàn)，傳統(tǒng)的HashMap是ArrayList+List或者ArrayList+紅黑樹的結構。DGraph的DenseHashMap，采用的ArrayList(Hash)+ArrayList(有序)方式，在ArrayList(Hash)任意桶區(qū)域，存儲的是當前桶的首個KVPair信息，以及當前桶Hash沖突的個數(shù)，沖突數(shù)據(jù)地址偏移量，存儲在另外一個ArrayList(有序)地址空間上(Hash沖突后可以在這塊區(qū)域用二分查找快速定位數(shù)據(jù))。這種結構有非常好的緩存命中率，因為它在內(nèi)存空間是連續(xù)的。但是它也是有缺點的，不能修改，全量寫入也非常復雜。首先我們要把數(shù)據(jù)加載到一個普通的HashMap，然后計算每個Hash桶上面元素的個數(shù)，知道了桶的數(shù)量和每個桶下面的元素個數(shù)，遍歷HashMap，把數(shù)據(jù)固化成DenseHash。KV/KVV的增量部分則是由RcuHashMap + RcuDoc基于D-Allocator(圖6)實現(xiàn)。

圖7 緊湊型KV/KVV索引

Invert索引

基于開源RoaringBitmap實現(xiàn)的RCU版本(基于D-Allocator實現(xiàn))。RoaringBitmap 將一個文檔ID(uint32)分為高位和低位，高16位的ID用來建一級索引，低16位的ID用來構建二級索引(原文稱之為Container)，在二級索引中，因為2^16=65536，一個short占用空間16bit，65536剛好可以存儲4096個short，因此當分段內(nèi)文檔數(shù)量少于等于4096是，用short數(shù)組存儲文檔，當分段內(nèi)的文檔數(shù)量大于4096時則轉為Bitmap存儲，最多可以存儲65536個文檔。這種設計對于稀疏倒排&密集倒排在存儲空間利用率&計算性能上都表現(xiàn)優(yōu)異。

圖8 倒排(Invert)索引

Embedding索引

基于開源的Kmeans聚類。Kmeans聚類后，引擎會以每個中心向量(centroids)為基點，構建倒排，倒排的數(shù)據(jù)結構也是RoaringBitmap，同一個聚簇的向量都回插入同一個RoaringBitmap里面。這樣的好處是，可以在向量檢索中包含普通文本索引，比如你可以在向量召回的基礎上限制商品的tile必須要包含椰子、男鞋、紅色等文本信息。

圖9 向量索引

算子調(diào)度框架

推薦存儲引擎最開始只提供了簡單的數(shù)據(jù)查詢&數(shù)據(jù)補全功能，由于擴招回需要，后期又引入了算子框架，初步提供了基本的多算子融合調(diào)度能力(Merge/LeftJoin/Query)，可以將多次引擎查詢合并為單次查詢，降低召回RT,  提升召回能力。老的框架有很多問題：1）只提供了JAVA API接入，API可解釋性比較差，用戶接入上存在一定困難。2）算子調(diào)度框架效率偏低，采用OMP+階段策略調(diào)度，對服務器硬件資源利用率偏低，部分場景集群CPU超過20%后99線95線即開始惡化。3）Graph運行時中間數(shù)據(jù)采用行式存儲，在空間利用率和運算開銷上效率低，導致部分業(yè)務在遷移算子框架后RT反而比之前高。4）缺少調(diào)試 & 性能分析手段。

DGraph后期針對這些問題我們做了很多改進：1）引入了Graph存儲，用于可以通過傳入GraphID訪問一個圖，配合引擎管理平臺的DAG展示&構圖能力，降低圖的使用門檻。2）開發(fā)了全新的調(diào)度框架：節(jié)點驅動+線程粘性調(diào)度。3）算子中間結果存取等計算開銷比較大的環(huán)節(jié)，通過引入了列存儲，虛擬列等有效的降低了運行時開銷。上線后在平均RT和99線RT都取得了不錯的結果。

圖10 算子框架演進

三、后記

DGraph是得物在推薦業(yè)務上一次非常成功的探索，并在算法指標、穩(wěn)定性、機器成本等多方面取得了收益。搜推場景是互聯(lián)網(wǎng)中算力開銷特別大的場景之一，數(shù)據(jù)更新頻繁，日常業(yè)務迭代復雜，因此對系統(tǒng)的挑戰(zhàn)非常高。在DGraph的研發(fā)過程中，我們投入了非常多的精力在系統(tǒng)的穩(wěn)定性 & 易用性上面，積累了很多些經(jīng)驗，簡單總結下：1）平臺側需要做好數(shù)據(jù)的校驗，數(shù)據(jù)的增刪的改是搜推場景最容易引發(fā)事故的源頭。2）提供靈活的API，類SQL或者DAG都可以，在C++內(nèi)部做業(yè)務開發(fā)是非常危險的。3）索引必須是二進制結構并且采用mmap方式加載，這樣即使發(fā)生崩潰的情況，系統(tǒng)可以在短時間快速恢復，日常調(diào)試重啟等操作也會很快。