推薦系統實現原理介紹

1：推薦系統簡易架構圖

2：推薦引擎流程圖

Mixer系統的用戶推薦就是按照上面流程實現，接下來分別介紹各個功能

3：索引內容

1：索引目的是提供高效查詢

索引內容就是將內容生產索引文件，目的是提高查詢速度，不可能每個請求過來都把所有的數據查出來，然后過濾、計算特征、排序、最后將排在前面的數據推給用戶，數據量實在是太多不能這么玩，所以會將一些關鍵數據生成索引文件，通過databus將文件推送到推薦引擎的機器上，推薦引擎加載索引文件，在內存中生成各種索引（正排索引、倒排索引等），提供快速查詢。

2：怎么生成索引文件

我們把一個表的數據查出來，寫入文件，那么這個文件就是索引文件，但是這個表的一些字段我們可能用不上，查出來只會增大索引文件，影響加載速度和占用多余的內存，所以我們只會將需要的字段加到索引文件中，mixer作為用戶推薦系統，那么用戶表是主表，還設計到用戶資料表、用戶興趣表等多張表，將多張表信息和成一張表，一個用戶一條記錄，定義好對應的struct，填充每個用戶struct中的字段，得到一個struct數組，將數組的內容以pb格式序列化寫入文件，索引文件就生成了。

由于數據庫中的數據會實時變化，那么我們就需要定時生成索引文件。

3：databus傳輸文件

索引文件我們會用一個獨立的服務生成，然后通過databus服務傳送到推薦引擎的機器上。這個功能可以很簡單，如果你的推薦系統比較簡單，生成索引的服務和推薦的服務在一臺機器上，約定一個文件路徑就行，定時檢查文件是否變更，變更重新加載就行。

那么正常的databus怎么實現？

數據巴士就是一個文件下載服務，你可以提供ftp服務或是http服務，下面以http服務為例簡要說明databus的實現，他真的太簡單了。databus提供一個server端和一個client端。server定時判定索引文件有沒有更新，如果有更新，更新文件路徑和文件的md5，每個推薦引擎機器部署一個client，client定時請求server端，比對client和server的md5是否一致，如果不一致說明文件更新了，就下載文件。可能你覺得定時請求有些沒必要，想減少沒必要的http請求，那么server只需要發現文件變更就通知所有客戶端，你可以用etcd作為通知工具，但我們也要考慮引入一個中間件帶來的問題，有可能是中間的問題，或是你使用的問題導致client沒有加載最新的索引文件。

client下載索引文件放到指定路徑，推薦引擎檢測到文件變更，加載最新文件，實現索引文件傳輸。

4：內存中建立索引

推薦引擎加載索引文件建立內存索引，這塊是核心。

索引文件我們可以理解成一張表，然后我們在內存中給這張表建立索引，比如我想按照性別查詢、按照學歷查詢、按照年齡范圍查詢、按照城市id查詢，我們可以將這4個查詢分成2類，一類是這個字段的值是固定的幾個（性別：0無，1男，2女；學歷：0~7），第二類字段的值是多個的（年齡：18~150；城市id可能有幾百個）

第一類的倒排索引可以用BitMap實現。

以性別為例，性別有3個值，我們建立3個BitMap為[3]BitMap，第一個性別bitmap表示無，第二個BitMap表示男，第三個BitMap表示女。比如我們有100W個用戶，那么一個BitMap就是一個長度為15625的[]uint64，一個bit位對應一個用戶，那么這個bitmap占用15625*8=122K，3個bitmap占用366K，占用內存是非常少的。

type BitMap []uint64


func NewBitMap(length int) BitMap { bitLen := (length + 63) / 64 return make([]uint64, bitLen) }
bt := NewBitMap(1000000) // 15625 = (1000000 +63) / 64

BitMap怎么賦值？

如第100個用戶是男性，男性對應第二個bitmap，將[]uint64的100位設置成1，是第100位不是數組下標100。遍歷這100w個用戶，按照性別和下標設置對應bitmap的二進制位的值，把bitmap看成二進制數組就行，它的值只有0和1。

BitMap怎么查詢？

如果我要給一個用戶推薦男性用戶，那么第二個BitMap中二進制位為1的下標的集合就是100W個用戶組數中男性的集合，當然我們不需要現在就取出所有男性的信息，因為查詢條件可能是：男性+本科+25歲+北京。索引性別只需要取第二個BitMap就行，索引查詢性別就是取數組下標為1的元素，還有比這還快的查詢嗎？

同樣的學歷定義為bt := [8]BitMap，本科只需要取bt[4]，快得飛起，然后把學歷和性別的兩個BitMap取交集，就是SQL中的and，得到一個BitMap，二進制位1的用戶就是我們要找的用戶。時間復雜度是O(1)

第一類的倒排索引可以用排序+BitMap實現。

像年齡有100多個，城市有幾百個，我們不能建立幾百個BitMap的數組，那樣占用內存較多，而且這些值隨時變多，用固定長度數組不好解決，我們只能提前排好序，通過二分查找+遍歷的方式實現，二分查找時間復雜度O(log n)。

比如年齡我們可以定義一下結構

type IndexAge struct {
Index uint32 //數組下標值，數組為100W用戶數組
Age uint32 //用戶對應的年齡
}

100W用戶就定義[1000000]IndexAge，然后Age排序，如何按照年齡范圍查找，以查找年齡范圍是[18,25]為例，通過二分查找找到第一個年齡=18的用戶，然后往后遍歷直到年齡>25為止，Index指定的下標用戶幾位所求。類似mysql的between and。年齡查詢時間復雜度O(n log n)。

不用BitMap，用數組也行，但每個索引的內存占用會擴大到64倍

5：召回

召回就是通過內存索引進行查詢，然后取交集，如查找：性別男 + 學歷（本科/碩士）+年齡（18~25）+城市（北京/上海）。

性別男，直接取下標，得到一個BitMap

學歷（本科/碩士），直接取2次下標，得到本科BitMap和碩士BitMap，兩個BitMap取并集，得類似mysql中的or，到一個BitMap

年齡（18~25），二分查找+遍歷，類似mysql的between and，得到一個BitMap

城市（北京/上海），兩次二分查找+遍歷，類似mysql的in，得到兩BitMap后取并集得到一個BitMap

然后4個BitMap取交集得到一個BitMap，BitMap為1的就是我們要找的用戶。

6：過濾

作為用戶推薦系統

1：推薦過的用戶一天總不能推2次吧

2：不能把自己推薦給自己

3：我拉黑的人不能推薦給我

4：把我拉黑的人不能推薦給我

5：我喜歡的人，就不要再推薦給我了

6：………..

這些數據都會存在數據庫中，同時在redis中保存一份對應的uid，這些都是要過濾的用戶，通過查詢redis得到所有要過濾的uid，將這些uid存到map中，將召回的用戶列表都到map中判斷一下是否存在，存在就被過濾，golang的map查詢時間復雜度是O(1)，遍歷用戶列表時間復雜度是O(n)，整個過濾的時間復雜度是O(n)

7：特征計算

過濾完后得到一個用戶列表，根據每個用戶的特征信息，每個特征一個分值，然后按照一個公式，計算得到一個最終的分值。就像學生每門課成績有一個分值，這里的公式可能不是簡單的相加，而是按照業務隨時調整的公式

8：排序

特征計算已經得到一個分值，按照這個分值排序，取top30推薦給用戶，一個簡單的推薦系統就完成了。