一、應(yīng)用場景

1、三角問題-擴(kuò)散

首先來看一個圖推薦中經(jīng)常會遇到的場景，圖擴(kuò)散。

如上圖所示，已知一個點，由此點出發(fā)，找自己的行為關(guān)系，到達(dá)一個中間結(jié)點，再到另外一個結(jié)點，這樣就是兩跳。兩跳之后獲取全部數(shù)據(jù)，然后進(jìn)行內(nèi)容的推薦計算，比如我關(guān)注的人還關(guān)注誰、我關(guān)注的大  V 的朋友圈有哪些大 V、我點贊的視頻相似度高的視頻有哪些。其中朋友圈有很多定義方式，比如他們的互關(guān)、交互程度即親密分?jǐn)?shù)比較高、互動比較頻繁，或者其它一些定義。

這種場景的特點是所見即所得。對簡單規(guī)則推薦的業(yè)務(wù)場景來說，用語法上線速度是非常快的。

對于其他拓展場景，關(guān)系可以是多樣化的，比如關(guān)注、互關(guān)、點贊、評論、分享，還有一些其它的關(guān)系比如 Facebook 好友等等。另一方面，節(jié)點也可以是多樣的，包括用戶、視頻以及認(rèn)證賬號。

這種推薦方式非常常見，可以取得很好的定向推薦效果。

這種推薦方式可以用 Cypher 語法來描述，如上圖所示，從一個點出發(fā)，經(jīng)過一個邊，再經(jīng)過一個邊，最終拿到一個點，對這個點來計數(shù)。當(dāng)然這個計數(shù)只是一種方式，還有其它一些方法比如 sum(sim_score)，計算出最終的 score 值，根據(jù) score 值排序、截斷，然后推薦。正常情況下，推薦的結(jié)果一般不會超過一千，但是中間訪問到d的數(shù)據(jù)量是很大的，突破幾十萬都是很正常的。快手這邊 Follow 上線目前是五千，其它邊可以輕松達(dá)到幾十萬、上百萬的數(shù)據(jù)量。

2、三角問題-共同

再來看第二個場景，共同關(guān)注。

已知兩個點，來確定他們之間是不是存在一些關(guān)系，比如共同關(guān)注的關(guān)系、有共同的好友或是有共同的圈子。主要應(yīng)用場景是，點開一個陌生的頭像或是陌生的主頁，為了誘使用戶與其發(fā)生更進(jìn)一步的關(guān)系，就會告訴他我們有共同的興趣愛好，這屬于點對點的推薦方式。

為了解決這樣的問題，采用共同類的方式，具體方法是分別從這兩個點出發(fā)，最終拿到一個目標(biāo)，共同的一個點，進(jìn)行聚合 UNION ALL，得到一個聚合后的 COUNT 值。

為什么要用聚合的方式而不是用其他方式？我們在訪問過程中，會有很多的篩選條件，比如要求過濾掉大 V 帳號、過濾掉已經(jīng)封禁的帳號等等，篩選條件會比較豐富，可能還要根據(jù)最終節(jié)點拿到他的屬性進(jìn)行篩選，這樣每兩個跳都可以單獨篩選，最終拿到這樣的結(jié)果。

3、存在問題

存在問題，指的是我和群體有什么關(guān)系。比如博主發(fā)了一個視頻，評論列表中有幾十萬，不可能每個評論都回復(fù)，這時就需要推薦出一些有價值的評論，進(jìn)行回復(fù)，可能需要判斷他們是不是朋友、是不是親密度比較高，這樣可以打上一些標(biāo)簽，博主就更可能會和其進(jìn)行一些互動。

對于這類需求，我們采用了內(nèi)置的圖算法，看是否存在一個這樣的邊，如果存在一個這樣的邊，就返回一個 ‘Follow’、‘FollowBy’、‘Friend’、‘Like’ 等關(guān)系，這些關(guān)系是根據(jù)用戶的使用場景具體定義的，最終對邊進(jìn)行標(biāo)簽化的展示。

二、核心訴求

前文中講到了三種場景，更多的情況是這三種場景的糅合，會比較復(fù)雜。用戶的核心訴求為以下三點：

• 成本：數(shù)據(jù)量超過千萬級別，多種不同的邊，總數(shù)據(jù)量可達(dá)到萬億級別，幾百臺機器滿足簡單的需求是不可接受的，因此成本是備受關(guān)注的一個點。
• 性能
• 易用

以上三點缺一不可。

三、存算分離架構(gòu)

1、整體架構(gòu)

存算分離架構(gòu)是近年來數(shù)據(jù)庫領(lǐng)域非常火熱的一個架構(gòu)，其主要特點就是按需部署。CPU、Memory 和 Disk 是相互隔離開的，每一部分都可以單獨擴(kuò)容。這樣就可以很方便地找到瓶頸所在，并單獨對其進(jìn)行擴(kuò)容，從而降低成本。

快手當(dāng)前的架構(gòu)主要是分為 Graph Service 層、Tree Service 層和 Storage 層。

Graph Service 層就是語法的執(zhí)行層。

Tree Service 層是圖的模型層，中間會有 Cache，主要提供 Memory 選項。

Storage 層是由 SSD 磁盤存儲和 S3 冷存儲多樣存儲組成，這一層進(jìn)行了冷熱分離。

正常的情況下，我們的成本主要集中在內(nèi)存層，因為我們的圖對內(nèi)存的需要比較高。

2、BWTree Service

BWTree Service 是內(nèi)存層，是圖描述的一層，對其最主要的訴求就是強一致。因為圖的模型有一些其他衍生出來的數(shù)據(jù)結(jié)構(gòu)，比如唯一性索引，物化出來的 num neighbors、雙關(guān)等，如果不能做到強一致，整個模型會存在一些問題。它主要是利用 Mem 和 SSD 作為 Cache。

先來看一下用戶請求的處理過程，如上圖中右側(cè)所示。用戶發(fā)起一個請求，加入到請求隊列，用戶所有請求都在一個隊列中。Tree-writer 線程工作中，會把這些請求打包成一個 Log，commit 到 WAL-service，這是強一致性存儲的一個外部存儲平臺。commit 成功就可以應(yīng)用  Wal-diff 到內(nèi)存中；如果 commit 沖突，即 WAL-service 已經(jīng)有了這個 Log，就要把最新的 Log 拉回來應(yīng)用到內(nèi)存，再重新執(zhí)行上述過程。這樣就可以保證強一致。最后就是 Log 應(yīng)用到內(nèi)存中，并返回成功。這里的 flush 后臺線程，執(zhí)行的頻率比較低，大概是幾十分鐘至一個小時才會把所有的數(shù)據(jù) flush 一遍，速率取決于當(dāng)前的臟頁率，盡量降低對持久化存儲的影響。Page 持久化存儲會分為兩層，一層是 SSD Cache，還有一層是 S3 存儲，可以進(jìn)一步降低成本。我們的 Wal-service 除了剛才提到的日志，還兼具選主的功能，即多副本的情況下進(jìn)行選主。

3、緊湊內(nèi)存模型

前文中提到，內(nèi)存是成本的主要來源。我們的內(nèi)存模型和操作系統(tǒng)是比較相似的。用 mmap 申請很大的三塊內(nèi)存，分別作為一/二/三級頁表，和操作系統(tǒng)的頁表是同一個概念，在緊湊的內(nèi)存空間是沒有任何浪費的。第三級頁表，指向真實的數(shù)據(jù)。數(shù)據(jù)是用 malloc，因為我們希望頁本身是可變大小的。實例內(nèi)存比較滿，就進(jìn)行淘汰，從 page records 左側(cè)開始遍歷，遇到 access_num 為 0 的頁就可以淘汰，這個過程也和操作系統(tǒng)比較像，因此我們也是用的 CLOCK 淘汰算法。

4、邊模型

前面講解了樹模型，但是樹模型不能完整地描述邊，邊有四種樹結(jié)構(gòu)，分別是 Record Tree、Unique Index Tree、Num Neighbors Materialize Tree 和 Bidirectional Materialize Tree。Record Tree 是記錄樹，Unique Index Tree 是索引樹，關(guān)系鏈樹是需要維護(hù)索引的。Num Neighbors Materialize Tree 是鄰居的物化視圖，主要記錄在一點有多少個鄰居，有多少個評論樹，多少個好友樹。物化視圖的更新主要是依據(jù)普通的樹更新，根據(jù)主樹來更新。Bidirectional Materialize Tree 是雙關(guān)物化視圖，根據(jù)出邊和入邊物化出一個雙關(guān)列表。以上四種樹可以根據(jù)用戶配置來進(jìn)行生成或不生成。

5、Snapshot 隔離性

在實時讀寫情況下。需要做到讀視圖 snapshot 一致性，不能出現(xiàn)幻讀和未提交讀。每個頁有多個版本，修改頁則復(fù)制一份頁數(shù)據(jù)，并產(chǎn)生新的版本號，多個版本的頁都記錄在 page record 中。訪問請求攜帶一個版本號 n+1，就可以區(qū)分并訪問期望的頁，從而實現(xiàn)了隔離。

四、性能要點

1、Share Nothing

比如一個兩跳查詢，一跳是 500，最終需要拉取 25 萬數(shù)據(jù)。假如每跳是 5000，那么最終訪問的數(shù)據(jù)就會有 2500 萬。當(dāng)然，2500 萬數(shù)據(jù)的訪問量級在實際使用中是不會出現(xiàn)的，我們都會進(jìn)行限制，但即使限制到幾十萬的數(shù)據(jù)，對于經(jīng)典的數(shù)據(jù)庫也很難做到百毫秒以內(nèi)返回，我們現(xiàn)在可以做到十萬數(shù)據(jù)的查詢計算 10 毫秒量級返回。性能是比較好的。那么我們是如何做到這樣的性能的呢？

比較重要的做 Share Nothing，這是數(shù)據(jù)庫中一個比較經(jīng)典的概念。用戶的一個請求到了一個線程，這個線程有個協(xié)程，協(xié)程在發(fā)起請求的情況下使用線程綁定的連接池發(fā)起，不用再跨線程。因為跨線程是很耗時的，即使什么也不做也要時延大概 0.08 毫秒，如果多次跨線程總時延會達(dá)到 0.4 毫秒，對于線上的一些核心產(chǎn)品應(yīng)用來說，和 Redis 對比，0.4 毫秒已經(jīng)是比較高的延時了。Share Nothing 要求連接和本線程進(jìn)行綁定，和 Tree Service 特定 worker 線程綁定，同樣，在收到請求的情況下，也是在本線程執(zhí)行，主要是讀的過程，如果要發(fā)起到 S3 冷存儲查詢請求，或 KV 磁盤存儲查詢請求也都是在本線程。這就是 Share Nothing 的概念，盡量不要跨線程，數(shù)據(jù)也是在本線程完成的。

2、數(shù)據(jù)流

以上介紹了數(shù)據(jù)請求的過程，接下來看一下數(shù)據(jù)回傳的過程。數(shù)據(jù)最終的葉子節(jié)點，存儲格式是行存，但是在讀之后就成為了列存格式。因為行存在更新時性能會比較好，列存時實時更新性能極差。因此，我們做了取舍，存儲時用行存，讀出之后所有數(shù)據(jù)用列存。讀出之后的列存數(shù)據(jù)格式，在經(jīng)過 RPC 時，壓縮效率和傳輸效率等都會比較高。最終到 Graph 層，數(shù)據(jù)經(jīng)過一個個算子表達(dá)式。列存數(shù)據(jù)作為算子的輸入，可以做向量化的運算。最終拿到的輸出也是列式進(jìn)行輸出，我們用的是 Apache-Arrow 數(shù)據(jù)存儲格式返回給用戶，也是列式存儲。因此，這樣的架構(gòu)特別適合圖地查詢和計算。