作者：Heorhii Skovorodnikov

深入研究TikTok令人驚嘆的(de)實時推薦系(xi)統的(de)內部(bu)工作原(yuan)理，了解是什么使(shi)它成為該領域最好的(de)產(chan)品之一。

為什么TikTok的(de)(de)feed如此讓人(ren)上癮？秘訣(jue)在于他們的(de)(de)推薦引擎，這正是使TikTok成為最大的(de)(de)社交媒體平臺之(zhi)一的(de)(de)原(yuan)因。

似乎feed可以讀取你的思(si)想，讓你在應用(yong)程(cheng)序中停留(liu)更長時間。最(zui)近，TikTok決(jue)定讓每個(ge)人都知道(dao)一個(ge)秘密(mi)，并在一篇(pian)題為 “Monolith:帶有無碰撞嵌入表的實時推(tui)薦系統[]” 的論文中發(fa)布了它的模型Monolith。

在線推薦(jian)系(xi)統(tong)是一種算(suan)法，用(yong)于(yu)根(gen)據用(yong)戶(hu)的興趣和喜好向用(yong)戶(hu)提(ti)供個性化的建議。這些系(xi)統(tong)通(tong)常(chang)被(bei)在線零售商和媒體公司用(yong)于(yu)向用(yong)戶(hu)推薦(jian)產(chan)品或(huo)內容。

在這篇文章中，我們(men)將深入研究TikTok令(ling)人驚嘆的(de)(de)推薦系統(tong)的(de)(de)內部工作原理，并了解是什么,讓它(ta)成為該領域最好的(de)(de)系統(tong)之(zhi)一.

目前的設計存在什么問題?

構建可擴展的實(shi)時推薦系統對于許多企業在(zai)其產(chan)品(pin)或(huo)(huo)網(wang)站中構建良(liang)好的體驗至關重要。然而，目(mu)前的深度學習框架(TensorFlow或(huo)(huo)PyTorch)不能(neng)很好地(di)用于實(shi)時生產(chan)場景。這是因為:

• 在依賴動態稀疏特征的推薦系統中，基于靜態參數和密集計算的模型更新并不適合較好的推薦性能。
• 常見的方法是將批量訓練階段和服務階段(在用戶與產品交互期間)完全分開設計，防止模型與客戶反饋實時交互。

TikTok的團(tuan)隊通過3個(ge)步驟解釋了(le)他們的解決方案(an):

• 他們制作了一個無碰撞的嵌入表，同時通過添加可exponable embedding 和 frequency filtering（頻率過濾）來進一步優化它，以減少其內存消耗，讓其高效，并適合分發到用戶;
• 他們提供了一個可用于生產環境的，且具有高容錯性在線訓練架構;
• 他們通過實驗證明，系統的可靠性可以與實時學習來互相平衡；

聽(ting)起(qi)來(lai)有(you)點嚇(xia)人嗎? 不要擔心，我(wo)(wo)們(men)將通過對每個(ge)組件的拆(chai)解分析，在本文結束時，你(ni)將有(you)信心地理解，為什么你(ni)可(ke)以在應用程序中(zhong)浪(lang)費大(da)量時間。準備好了(le)嗎? 我(wo)(wo)們(men)要發車啦(la)。

Embeddings and Hash maps

TikTok的研究人員觀察到，對于推薦系統來說，數據大多是categorical（分散） 和sparse（稀疏）的。

這(zhe)意味(wei)著，如果我(wo)們使用像(xiang)單詞嵌入這(zhe)樣的ML方法嵌入數據，我(wo)們將無法通過推薦(jian)數據提供的獨特特性數量來實現，相比之下，由于詞匯量有限，語言模(mo)型可以做到這(zhe)一點。

根據YouTube和Instagram推(tui)薦(jian)系統的實際經(jing)驗，哈希技巧被認為是大規模推(tui)薦(jian)系統的最佳方法。讓我們(men)深入(ru)研究《Monolith》中所(suo)使用的細節。

那么HashMap呢?

哈希映射(she)是(shi)一種數據結構，它允許通過一個(ge)特(te)殊的哈希函數將數據片段快速(su)映射(she)到(dao)一個(ge)值。

哈(ha)希映(ying)射速(su)度很快，被大型(xing)平臺用(yong)(yong)于高(gao)效編碼數(shu)(shu)據(ju)，那么單體應(ying)用(yong)(yong)如何使其更好呢(ni)? 哈(ha)希映(ying)射有一個固有的(de)權衡，這個數(shu)(shu)據(ju)結構的(de)原(yuan)始(shi)設計(ji)稱(cheng)為碰撞(collision)。

當兩個(ge)或多(duo)個(ge)數(shu)據(ju)通過哈(ha)希函數(shu)映(ying)射到(dao)相同(tong)(tong)的(de)輸出值時，就會(hui)發生沖突。當使用哈(ha)希函數(shu)索引數(shu)據(ju)時，這(zhe)可能(neng)會(hui)導致(zhi)問(wen)題(ti)(ti)，因(yin)為(wei)多(duo)個(ge)數(shu)據(ju)塊將被(bei)映(ying)射到(dao)相同(tong)(tong)的(de)位置。TikTok的(de)團隊(dui)開發了一個(ge) cuckoo hashmap，來解決這(zhe)個(ge)問(wen)題(ti)(ti)。

在 cuckoo hashmap 中(zhong)，就像(xiang)在標準hash map中(zhong)一(yi)(yi)(yi)樣，每個(ge)(ge)(ge)數(shu)(shu)(shu)據(ju)(ju)都(dou)被(bei)(bei)分配一(yi)(yi)(yi)個(ge)(ge)(ge)唯一(yi)(yi)(yi)的(de)(de)鍵，并(bing)且鍵被(bei)(bei)哈(ha)希(xi)以(yi)(yi)確定(ding)它在數(shu)(shu)(shu)組(zu)中(zhong)的(de)(de)位(wei)置。如果該(gai)位(wei)置已經(jing)被(bei)(bei)另(ling)一(yi)(yi)(yi)段數(shu)(shu)(shu)據(ju)(ju)占(zhan)據(ju)(ju)，則現有(you)數(shu)(shu)(shu)據(ju)(ju)將(jiang)被(bei)(bei)“踢出(chu)”(類(lei)似于現實生活中(zhong)杜鵑對巢中(zhong)蛋的(de)(de)行為)，并(bing)且必須使用(yong)第二個(ge)(ge)(ge)哈(ha)希(xi)函數(shu)(shu)(shu)在數(shu)(shu)(shu)組(zu)中(zhong)找到一(yi)(yi)(yi)個(ge)(ge)(ge)新的(de)(de)位(wei)置。這個(ge)(ge)(ge)過(guo)(guo)(guo)程將(jiang)繼續，直(zhi)到所有(you)數(shu)(shu)(shu)據(ju)(ju)都(dou)成功(gong)插(cha)(cha)入(ru)數(shu)(shu)(shu)組(zu)，或(huo)者(zhe)直(zhi)到達到最大(da)迭代次數(shu)(shu)(shu)為止(zhi)。上面(mian)給出(chu)了一(yi)(yi)(yi)個(ge)(ge)(ge)例子(zi)。這里兩個(ge)(ge)(ge)哈(ha)希(xi)表T0和T1用(yong)于存(cun)儲哈(ha)希(xi)數(shu)(shu)(shu)據(ju)(ju)。值(zhi)A被(bei)(bei)散列并(bing)插(cha)(cha)入(ru)到T0中(zhong)，但是由于B已經(jing)占(zhan)據(ju)(ju)了這個(ge)(ge)(ge)位(wei)置，然后將(jiang)其逐出(chu)，并(bing)試(shi)圖將(jiang)其插(cha)(cha)入(ru)到T1中(zhong)，這個(ge)(ge)(ge)過(guo)(guo)(guo)程將(jiang)重復，直(zhi)到插(cha)(cha)入(ru)所有(you)值(zhi)或(huo)重新散列以(yi)(yi)避免(mian)循環插(cha)(cha)入(ru)。這個(ge)(ge)(ge)過(guo)(guo)(guo)程可(ke)以(yi)(yi)避免(mian)碰撞(zhuang)，對生產模型的(de)(de)性能有(you)重要影響。

為了(le)完(wan)成(cheng)他們的(de)embedding系統設計，研究人員添加了(le)一(yi)些(xie)附加功能來進一(yi)步優化過程，特別(bie)是減(jian)少哈希所需(xu)要的(de)內存需(xu)求：

• 用于過濾hashmap中的id的概率過濾器。由于一個(ge)重要的(de)觀察是，在來自TikTok id的(de)數(shu)據中(zhong)，id是長尾分(fen)布的(de)，熱門id可(ke)(ke)能出現(xian)(xian)數(shu)百萬次，而不(bu)受歡迎的(de)id出現(xian)(xian)不(bu)超過10次，因此可(ke)(ke)以合理地假設它們不(bu)會影響(xiang)最終的(de)模型(xing)質量，因此可(ke)(ke)以清除。

• 一個ID存在計時器，控制舊ID和過期ID的刪除。這可能是(shi)由(you)于用戶不再(zai)活躍，或短視頻過時。為這些id存儲嵌入不能以任(ren)何方式幫助模型，因此清除內(nei)存是(shi)明智的。

在線訓練

現在(zai)，由于我(wo)們已經了解(jie)了數(shu)據在(zai)模(mo)型中是(shi)如(ru)何表示的，我(wo)們需(xu)要了解(jie)如(ru)何訓練(lian)和更新(xin)數(shu)據。Monolith在(zai)線訓練(lian)的系統架構的總體示意圖如(ru)下(xia)：

它(ta)看起來很復雜，但(dan)實際上，它(ta)都圍繞著一個(ge)非常簡(jian)單的過(guo)程(cheng)(cheng)，這個(ge)過(guo)程(cheng)(cheng)是更大架(jia)構的基礎，推動了(le)整個(ge)訓(xun)練系(xi)統(tong)架(jia)構的核心。

TensorFlow的分布(bu)式(shi)Worker-ParameterServer(或簡稱PS)模(mo)(mo)型(xing)(xing)(xing)是以分布(bu)式(shi)方式(shi)訓(xun)練(lian)(lian)機器(qi)學習模(mo)(mo)型(xing)(xing)(xing)的一(yi)種方式(shi)，其中多臺(tai)機器(qi)(或一(yi)臺(tai)機器(qi)上的進程)一(yi)起工作來訓(xun)練(lian)(lian)模(mo)(mo)型(xing)(xing)(xing)，如(ru)下圖所(suo)示:

在(zai)這個模型中，有(you)兩種類型的進(jin)程(cheng)：工作進(jin)程(cheng)和參(can)數服務器進(jin)程(cheng)。

• 工作進程負責執行訓練模型所需的計算，例如計算梯度或更新模型參數。
• 參數服務器負責存儲模型的當前狀態，例如模型權重或偏差。

訓練(lian)分為批量(liang)訓練(lian)和在線訓練(lian)兩個(ge)階段：

• 批量訓練階段。 該階段的(de)工作原理如下：在每(mei)個訓練(lian)(lian)(lian)步驟中，訓練(lian)(lian)(lian)工作者(zhe)從(cong)存(cun)儲中讀取一個小批量(liang)的(de)訓練(lian)(lian)(lian)樣(yang)例，向(xiang)PS請(qing)求參數，計(ji)算向(xiang)前(qian)和向(xiang)后傳遞，最后將更新后的(de)參數推入(ru)訓練(lian)(lian)(lian)PS。當(dang)需要修(xiu)改模型(xing)架構(gou)并重新訓練(lian)(lian)(lian)模型(xing)時，批量(liang)訓練(lian)(lian)(lian)對(dui)于訓練(lian)(lian)(lian)歷史數據非常有用;

• 在線訓練階段。 模型部(bu)署到在(zai)線服務(wu)后(hou)，訓(xun)練(lian)不會停止，而是進入在(zai)線訓(xun)練(lian)階段(duan)。訓(xun)練(lian)工作者不再從(cong)存儲中讀取小(xiao)批量示(shi)例，而是實時(shi)地(di)使用實時(shi)數據(ju)并更新訓(xun)練(lian)PS，訓(xun)練(lian)PS定期將(jiang)其參數同(tong)步到服務(wu)PS，這將(jiang)立即在(zai)用戶端(duan)生效。

Streaming引擎

為了確保Monolith能(neng)夠(gou)在批量訓(xun)練和在線訓(xun)練之間無縫切換，它使用了一個Streaming引擎組件(jian)：

為了收集實(shi)時(shi)用(yong)戶反(fan)饋，研究(jiu)團(tuan)隊(dui)使(shi)用(yong)Kafka隊(dui)列(lie)，其中一個隊(dui)列(lie)記錄用(yong)戶操作(點(dian)擊，點(dian)贊(zan)等)，另(ling)一個隊(dui)列(lie)記錄來自模型服(fu)務器的功能。然后(hou)使(shi)用(yong)Apache Flink joiner連接兩個，這些打包的數(shu)據被轉換(huan)成訓(xun)練(lian)數(shu)據，然后(hou)由另(ling)一個Kafka隊(dui)列(lie)讀(du)取，這些訓(xun)練(lian)示例用(yong)于批處理訓(xun)練(lian)和在線訓(xun)練(lian)：

• 在批量訓練過程中，Kafka隊列中的數據被轉儲到Hadoop分布式文件存儲(HDFS)中，在積累了一定數量的訓練數據后，再發送給訓練工作者
  -在線訓練的過程更簡單：數據直接從Kafka隊列中讀取

訓練操作完成后，PS收集參數，并(bing)根據(ju)選定的同步(bu)計劃(hua)更新(xin)服務(wu)PS，而服務(wu)PS又更新(xin)用(yong)戶端的模型。

在線 Joiner

Joiner 過程實際上有(you)點(dian)復(fu)雜，我們(men)應該(gai)注意(yi)一些事情(qing)：

內存緩存和KV(Key-Value)存儲，是兩個有助于穩定用戶(hu)(hu)操作和來自(zi)服務器的(de)功(gong)能之間的(de)延遲的(de)組件，這是因為(wei)它們都到達，而不考慮彼此(ci)的(de)到達時間，因此(ci)需要緩(huan)存來正(zheng)確(que)地(di)配對它們。但(dan)是如果用戶(hu)(hu)需要很長時間才能完成一(yi)個操作呢? 那么緩(huan)存就不是一(yi)個好主意，因此(ci)一(yi)些(xie)值存儲在磁(ci)盤(pan)上，以便再次配對。當用戶(hu)(hu)操作日志到達時，它首先查找(zhao)內存中的(de)緩(huan)存，然后查找(zhao)鍵值存儲，以防缺(que)少緩(huan)存。

還要注意最后一步，即 負例采樣（Negative Sampling）。因(yin)為在訓練過程中有積極(ji)和消極(ji)的例子(zi)。在推薦系統中，正例是(shi)(shi)(shi)用戶喜(xi)歡(huan)或表現出(chu)興(xing)趣(qu)的項目，而負例是(shi)(shi)(shi)用戶不(bu)喜(xi)歡(huan)或表現出(chu)興(xing)趣(qu)的項目。但是(shi)(shi)(shi)它們的數量(liang)可能是(shi)(shi)(shi)不(bu)平衡的，因(yin)此糾正數據集中的這種偏差是(shi)(shi)(shi)很(hen)重(zhong)要的。

就是這樣。你已經了解(jie)了Monolith中的所有組件。現在(zai)是最后一個部分，研究人員證明了在(zai)線學(xue)習的有效(xiao)性(xing)。

實時學習

在這里(li)，團隊還(huan)比(bi)較了(le)模型，在不同同步時間間隔下的性(xing)能，以驗證其性(xing)能：

正如我們在上面看到的，在線訓練，對于(yu)具有(you)動(dong)態反(fan)饋的推薦(jian)系統擁有(you)更(geng)好的性能，是至關重要的。

寫在最后

感謝(xie)閱讀(du)我對(dui)TikTok實時推薦系統(tong)工作(zuo)原理(li)的深入研究。

我希望你覺(jue)得有趣，并學到了(le)一點(dian)新(xin)的東(dong)西(xi)。

原文：

論文：Monolith:帶(dai)有無碰撞嵌入(ru)表的實(shi)時(shi)推薦系(xi)統，