一、應用場景

1、三角問題-擴散

首先來看一個圖推薦中經常會遇到的場景，圖擴散。

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

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

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

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

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

2、三角問題-共同

再來看第二個場景，共同關注。

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

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

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

3、存在問題

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

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

二、核心訴求

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

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

以上三點缺一不可。

三、存算分離架構

1、整體架構

存算分離架構是近年來數據庫領域非?；馃岬囊粋€架構，其主要特點就是按需部署。CPU、Memory 和 Disk 是相互隔離開的，每一部分都可以單獨擴容。這樣就可以很方便地找到瓶頸所在，并單獨對其進行擴容，從而降低成本。

快手當前的架構主要是分為 Graph Service 層、Tree Service 層和 Storage 層。

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

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

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

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

2、BWTree Service

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

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

3、緊湊內存模型

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

4、邊模型

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

5、Snapshot 隔離性

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

四、性能要點

1、Share Nothing

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

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

2、數據流

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