建站
咨詢
售后
建站咨詢
新聞中心
一、前言
隨著得物業(yè)務(wù)規(guī)模的不斷增加，推薦業(yè)務(wù)也越來越復(fù)雜，對推薦系統(tǒng)也提出了更高的要求。我們于2022年下半年啟動了DGraph的研發(fā)，DGraph是一個C++項目，目標(biāo)是打造一個高效易用的推薦引擎。推薦場景的特點是表多、數(shù)據(jù)更新頻繁、單次查詢會涉及多張表。了解這些特點，對于推薦引擎的設(shè)計非常重要。通過閱讀本文，希望能對大家了解推薦引擎有一定幫助。為什么叫DGraph？因為推薦場景主要是用x2i(KVV)表推薦為主，而x2i數(shù)據(jù)是圖(Graph)的邊，所以我們給得物的推薦引擎取名DGraph。
創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站制作、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)與策劃設(shè)計,長垣網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:長垣等地區(qū)。長垣做網(wǎng)站價格咨詢:13518219792
二、正文
整體架構(gòu)
DGraph可以劃分為索引層&服務(wù)層。索引層實現(xiàn)了索引的增刪改查。服務(wù)層則包含Graph算子框架、對外服務(wù)、Query解析、輸出編碼、排序框架等偏業(yè)務(wù)的模塊。
圖1 DGraph 整體框架
索引框架
在DGraph里面參考圖1，索引的管理被抽象成5個模塊：Reader 索引查詢、Writer 索引寫入、Compaction 增量全量合并、LifeCycle 索引生命周期管理、Schema 索引配置信息。
不同類型的索引只需要實現(xiàn)上面的5個類即可，不同類型的索引只需要關(guān)注索引本身的實現(xiàn)方式，而不需要關(guān)心索引的管理問題，通過這種模式，索引管理模塊實現(xiàn)了索引的抽象管理，如果業(yè)務(wù)需要，可以快速在DGraph面加入一種新的索引。
DGraph數(shù)據(jù)的管理都是按表(table)進行的(圖2)，復(fù)雜的索引會使用到DGraph的內(nèi)存分配器D-Allocator，比如KVV/KV的增量部分 & 倒排索引 & 向量索引等。在DGraph所有數(shù)據(jù)更新都是DUMP(耗時)->索引構(gòu)建(耗時)->引擎更新(圖3)，索引平臺會根據(jù)DGraph引擎的內(nèi)存情況自動選擇在線更新還是分批重啟更新。這種方式讓DGraph引擎的索引更新速度&服務(wù)的穩(wěn)定性得到了很大的提升。
圖2 DGraph索引組織關(guān)系
圖3 Graph索引更新
索引
數(shù)據(jù)一致性
相比訂單、交易等對于數(shù)據(jù)一致性要求非常嚴(yán)格的場景。在搜推場景，數(shù)據(jù)不需要嚴(yán)格的一致性，只需要最終一致性。若一個集群有N個引擎，通過增量向集群寫入一條數(shù)據(jù)，每個引擎是獨立更新這條數(shù)據(jù)的，因為是獨立的，所以有些機器會更新快一點，有些機器會更新慢一點，這個時間尺度在毫秒級附近，理論上在某一時刻，不同引擎上的數(shù)據(jù)是不一致的，但這對業(yè)務(wù)影響不大，因為最終這些數(shù)據(jù)會保持一致。
最終一致性這個特性非常重要，因為實現(xiàn)嚴(yán)格的一致性很復(fù)雜，2PC&3PC等操作在分布式場景下，代價很高。所以事情就變得簡單了很多，引擎的讀寫模型只需要滿足最終一致性即可。這可以讓我們的系統(tǒng)，更偏向于提供更高的讀性能。這個前提也是DGraph目前很多設(shè)計的根因。
讀寫模型
推薦場景需要支持在線服務(wù)更新數(shù)據(jù)，因此引擎有讀也有寫，所以它也存在讀寫問題。另外引擎還需要對索引的空間進行管理，類似于JAVA系統(tǒng)里面JVM的內(nèi)存管理工作，不過引擎做的簡單很多。讀寫問題常見的解決方案是數(shù)據(jù)加鎖。數(shù)據(jù)庫和大部分業(yè)務(wù)代碼里面都可以這么做，這些場景加鎖是解決讀寫問題最靠譜的選擇。但是在推薦引擎里面，對于讀取的性能要求非常高，核心數(shù)據(jù)的訪問如果引入鎖，會讓引擎的查詢性能受到很大的限制。
推薦引擎是一個讀多寫少的場景，因此我們在技術(shù)路線上選擇的是無鎖數(shù)據(jù)結(jié)構(gòu)RCU。RCU在很多軟件系統(tǒng)里面有應(yīng)用，比如Linux 內(nèi)核里面的kfifo。大部分RCU的實現(xiàn)都是基于硬件提供的CAS機制，支持無鎖下的單寫單讀、單寫多讀、多寫單讀等。DGraph選擇的是單寫多讀+延遲釋放類型的無鎖機制。效率上比基于CAS機制的RCU結(jié)構(gòu)好一點，因為CAS雖然無鎖，但是CAS會鎖CPU緩存總線，這在一定程度上會影響CPU的吞吐率。
如果簡單描述DGraph的索引結(jié)構(gòu)，可以理解為實現(xiàn)了RcuDoc(正排)、RcuRoaringBitMap(倒排)、RcuList、RcuArray、RcuList、RcuHashMap等。用推薦場景可推池來舉一個例子，可推池表的存儲結(jié)構(gòu)可以抽象成RcuHashMap
圖 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里面我們構(gòu)建了一個內(nèi)存分配器D-Allocator(每個索引只能申請一個/可選)，用于存儲增量或者倒排索引等復(fù)雜數(shù)據(jù)結(jié)構(gòu)。采用了類似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
圖7 緊湊型KV/KVV索引
Invert索引
基于開源RoaringBitmap實現(xiàn)的RCU版本(基于D-Allocator實現(xiàn))。RoaringBitmap 將一個文檔ID(uint32)分為高位和低位，高16位的ID用來建一級索引，低16位的ID用來構(gòu)建二級索引(原文稱之為Container)，在二級索引中，因為2^16=65536，一個short占用空間16bit，65536剛好可以存儲4096個short，因此當(dāng)分段內(nèi)文檔數(shù)量少于等于4096是，用short數(shù)組存儲文檔，當(dāng)分段內(nèi)的文檔數(shù)量大于4096時則轉(zhuǎn)為Bitmap存儲，最多可以存儲65536個文檔。這種設(shè)計對于稀疏倒排&密集倒排在存儲空間利用率&計算性能上都表現(xiàn)優(yōu)異。
圖8 倒排(Invert)索引
Embedding索引
基于開源的Kmeans聚類。Kmeans聚類后，引擎會以每個中心向量(centroids)為基點，構(gòu)建倒排，倒排的數(shù)據(jù)結(jié)構(gòu)也是RoaringBitmap，同一個聚簇的向量都回插入同一個RoaringBitmap里面。這樣的好處是，可以在向量檢索中包含普通文本索引，比如你可以在向量召回的基礎(chǔ)上限制商品的tile必須要包含椰子、男鞋、紅色等文本信息。
圖9 向量索引
算子調(diào)度框架
推薦存儲引擎最開始只提供了簡單的數(shù)據(jù)查詢&數(shù)據(jù)補全功能，由于擴招回需要，后期又引入了算子框架，初步提供了基本的多算子融合調(diào)度能力(Merge/LeftJoin/Query)，可以將多次引擎查詢合并為單次查詢，降低召回RT, 提升召回能力。老的框架有很多問題：1）只提供了JAVA API接入，API可解釋性比較差，用戶接入上存在一定困難。2）算子調(diào)度框架效率偏低，采用OMP+階段策略調(diào)度，對服務(wù)器硬件資源利用率偏低，部分場景集群CPU超過20%后99線95線即開始惡化。3）Graph運行時中間數(shù)據(jù)采用行式存儲，在空間利用率和運算開銷上效率低，導(dǎo)致部分業(yè)務(wù)在遷移算子框架后RT反而比之前高。4）缺少調(diào)試 & 性能分析手段。
DGraph后期針對這些問題我們做了很多改進：1）引入了Graph存儲，用于可以通過傳入GraphID訪問一個圖，配合引擎管理平臺的DAG展示&構(gòu)圖能力，降低圖的使用門檻。2）開發(fā)了全新的調(diào)度框架：節(jié)點驅(qū)動+線程粘性調(diào)度。3）算子中間結(jié)果存取等計算開銷比較大的環(huán)節(jié)，通過引入了列存儲，虛擬列等有效的降低了運行時開銷。上線后在平均RT和99線RT都取得了不錯的結(jié)果。
圖10 算子框架演進
三、后記
DGraph是得物在推薦業(yè)務(wù)上一次非常成功的探索，并在算法指標(biāo)、穩(wěn)定性、機器成本等多方面取得了收益。搜推場景是互聯(lián)網(wǎng)中算力開銷特別大的場景之一，數(shù)據(jù)更新頻繁，日常業(yè)務(wù)迭代復(fù)雜，因此對系統(tǒng)的挑戰(zhàn)非常高。在DGraph的研發(fā)過程中，我們投入了非常多的精力在系統(tǒng)的穩(wěn)定性 & 易用性上面，積累了很多些經(jīng)驗，簡單總結(jié)下：1）平臺側(cè)需要做好數(shù)據(jù)的校驗，數(shù)據(jù)的增刪的改是搜推場景最容易引發(fā)事故的源頭。2）提供靈活的API，類SQL或者DAG都可以，在C++內(nèi)部做業(yè)務(wù)開發(fā)是非常危險的。3）索引必須是二進制結(jié)構(gòu)并且采用mmap方式加載，這樣即使發(fā)生崩潰的情況，系統(tǒng)可以在短時間快速恢復(fù)，日常調(diào)試重啟等操作也會很快。
文章題目：得物推薦引擎 - DGraph
瀏覽路徑：http://fisionsoft.com.cn/article/djgpgco.html
