一、前言

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

二、正文

整體架構(gòu)

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

圖1 DGraph 整體框架

索引框架

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

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

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

圖2 DGraph索引組織關(guān)系

圖3 Graph索引更新

索引

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

相比訂單、交易等對(duì)于數(shù)據(jù)一致性要求非常嚴(yán)格的場(chǎng)景。在搜推場(chǎng)景，數(shù)據(jù)不需要嚴(yán)格的一致性，只需要最終一致性。若一個(gè)集群有N個(gè)引擎，通過(guò)增量向集群寫入一條數(shù)據(jù)，每個(gè)引擎是獨(dú)立更新這條數(shù)據(jù)的，因?yàn)槭仟?dú)立的，所以有些機(jī)器會(huì)更新快一點(diǎn)，有些機(jī)器會(huì)更新慢一點(diǎn)，這個(gè)時(shí)間尺度在毫秒級(jí)附近，理論上在某一時(shí)刻，不同引擎上的數(shù)據(jù)是不一致的，但這對(duì)業(yè)務(wù)影響不大，因?yàn)樽罱K這些數(shù)據(jù)會(huì)保持一致。

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

讀寫模型

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

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

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

圖 4 RcuList 元素插入

圖5 RcuList刪除元素

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

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

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

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

KV/KVV索引

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

圖7 緊湊型KV/KVV索引

Invert索引

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

圖8 倒排(Invert)索引

Embedding索引

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

圖9 向量索引

算子調(diào)度框架

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

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

圖10 算子框架演進(jìn)

三、后記

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