一、前言

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

二、正文

整體架構

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

圖1 DGraph 整體框架

索引框架

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

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

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

圖2 DGraph索引組織關系

圖3 Graph索引更新

索引

數據一致性

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

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

讀寫模型

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

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

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

圖 4 RcuList 元素插入

圖5 RcuList刪除元素

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

數據持久化

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

圖6 引擎內存管理

KV/KVV索引

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

圖7 緊湊型KV/KVV索引

Invert索引

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

圖8 倒排(Invert)索引

Embedding索引

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

圖9 向量索引

算子調度框架

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

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

圖10 算子框架演進

三、后記

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