Wukong 反作弊系統緩存的優化

01-29

Wukong 是知乎反作弊系統，它負責了 SPAM 的召回和處理。從 2016 年 8 月開始我們反作弊工程師對 Wukong 進行了局部重構（下稱 Wukong 3.0）。在這裡分享一下重構過程中對於緩存的設計和優化思路，主要解決了重複的查詢和大數據量的查詢造成 Mongodb 讀壓力太大的問題。

名詞解釋

Action

指用戶的一次寫行為，如回答創建，問題創建，點贊等。JSON 結構，一般可解釋為「誰，什麼時間，對誰，做了什麼」，包含 ActionType，UserID，UserIP， UserAgent，Created（行為產生時間）等信息。

Policy

策略，指 SPAM 的召回策略。主要包含觸發 (Trigger)，執行 (Handle) 兩個部分，觸發是指判定某行為是否為 SPAM 的觸發條件，執行是指 SPAM 召回後的處理(如封號，禁言等)。兩者都為一個 python 表達式。如下圖所示，第一欄為策略名，第二欄為 Trigger，第三欄為 Handle。

Recent_events

Policy 觸發條件中的主要函數。主要用於在 Policy 的觸發中召回最近一段時間內(如 30 分鐘，1 小時)與該策略定義的相關維度(如 ActionType 相同，IP相同，UserID 相同)的 Action 集。如上圖中的 same_type_events(60) 表示召回近 60 分鐘內與該行為的 ActionType 相同的 Action 集。

診斷瓶頸

在 Wukong 系統中，所有 Action 的數據都存儲在 MongoDB 中，並做了相關的索引提高查詢效率。所有的 recent_events 操作都從 MongoDB 中讀取。

目前，Wukong 處理的主要邏輯就是對於線上實時的用戶行為流中的每一個用戶的寫行為，通過多條 Policy 來從多角度的判斷其是否是 SPAM 行為，並做相關處理。

本次 Wukong 的局部重構主要目的是解決如下問題：

1）減輕對 MongoDB 存儲的讀壓力

2）放開對 MongoDB 存儲讀的條數限制。

對 MongoDB 的讀壓力主要體現在兩方面：很多接近於重複的查詢和大數據量的查詢。

接近重複的查詢是指，對於相隔時間很短內的多個相同類型的 Action，在某些 Policy 中（如圖一的 Policy），對每一個 Action 都會調用 MongoDB 查詢近 60 分鐘內相同類型的事件（same_type_events(60))。這樣的相隔時間段的多次 MongoDB 查詢，其返回結果的一大部分是相同的，例如對於相隔10秒鐘發生的兩個 ActionType 為 ANSWER_CREATE 的行為，在調用條件為「過去 60 分鐘內 ActionType 相同「的 Action 集時，會 2 次調用 MongoDB 進行查詢，而兩次查詢的返回結果大概率是 80% 以上的 Action 相同，只有小部分 Action 不同，造成大量不必要的IO。而一分鐘內這樣的查詢可能存在上千次。

注: 這裡只是對某些策略存在這些問題。對於其它策略如查詢維度增加相同 ip 或相同 UserID 時，因為這類查詢針對性強，且後端對 MongoDB 做了合理的 index，MongoDB 的性能完全靠譜，所以對這些查詢並不是本次重構中所關注的重點。

大數據量的查詢是指，recent_events 調用取回條數大於等於 1000 條的查詢，過多的這些查詢導致 MongoDB 伺服器負載過高。為了避免 SPAM 爆發時由於 MongoDB 的讀性能問題造成處理隊列阻塞，我們對 MongoDB 的每次查詢條數設了上限，默認為 1000 條，這在某種程度上造成某些策略 recent_events 中 Action 集的返回結果嚴重失真，但如果去除這個限制，則會導致 MongoDB 的響應時間線性增長，同時隨著返回結果集限制等放開，每條策略的平均處理時長會大大增加，系統的的處理性能會大幅下降。

優化方案

為了解決上述的兩個問題，我們的想法是採用的「Redis 緩存 + 本地緩存的方法」，開發一個緩存組件 BigCache，將接近重複的查詢和大數據量查詢從 MongoDB 中剝離，MongoDB 中只負責數據量小和針對性強的查詢。

BigCache

Redis 緩存資料庫由 MetaCache 和 IndexCache 兩部分組成，數據都實時更新。

MetaCache 存儲 Action 的原始信息，key 為原始信息的 md5 值，value 為 Action 的詳細信息。

IndexCache 存儲 Action 的索引信息，按照時間維度進行分片（默認 10 分鐘）存儲, key 由 time_sheet 和 index 維度組成，value 為該時間段內所有發生的該 index 維度的 Actions 的 md5 值，存儲為雙向鏈表。如下圖所示。

MetaCache 數據結構

IndexCache 數據結構

本地 worker 中的 LocalCache 採用2層的 dict 實現，第一層的 key 為時間分片，第二層存儲具體的 cache 信息，這樣做的好處是方便定時的清理過期緩存。

在本地同時緩存近 2 小時的 Meta 數據和近 2 小時內的 Index 數據(如以 10 分鐘作為分片依據，那麼查詢近 1 小時數據（精確到秒）可分為 7 片查詢。我們的Action數據流是基於時間序的，這裡假設時間延遲不會超過10分鐘，因此 7 個分片中只有第 0，1 分片的 Index 數據是存在動態更新的可能，需從 Redis 中獲取，而對第 2~6 片的 Index 數據不會再改變，可以存儲到 LocalCache 中。這樣大部分的 Index 查詢和 Meta 數據查詢可以在 LocalCache 中完成，只有 LocakCache 未命中的才會查詢 Redis 的 IndexCache 和 MetaCache。在我們的應用場景下，LocalCache 的命中率極高，大大減少了對Redis的重複請求。

使用 BigCache

採用該設計後，對於一次 recent_events 查詢，首先根據查詢條件判斷是否通過 BigCache 查詢，如果是，我們將根據給定的查詢 duration 和 Action Created 的時間拆分成若干個時間分片，然後分片查詢 BigCache 的 Index 表 (Redis+Local) 來獲取 Action 的 MD5 列表，然後通過基於該列表查詢 Meta 表 (Redis+Local) 獲取到具體的 Action 信息並返回。而對於其它查詢，依然通過MongoDB 返回如下圖所示。

性能對比

使用該緩存方案後 recent_events 的執行時間對比如下表：

從上表可以發現採用 BigCache 後性能有很大提升，尤其體現當返回條數上限越大時，性能並未線性下降。主要原因在於將熱數據存儲在本地減少了對同一數據 70% 以上的重複網路傳輸和查詢，且本地緩存命中率高。

再優化

從上面的性能對比表可以發現 Wukong3.0 的查詢返回平均時間是一個範圍，經過對以上方法的再思考和熱點的再分析，為了進一步降低 recent_events 的最大平均返回時間，我們還採取了以下兩個措施：

採用Redis Pipeline，減少了未在 LocalCache 中命中的 Action 原始信息查詢 Redis 的次數，減少 Round-Trip。代碼如下：

IndexCache 增量更新。我們在 LocalCache 中並未存取當前時間分片 (即第0分片) 的 IndexKey，因此每次查詢時都需從 Redis 的 IndexCache 中獲取該分片的全量 MD5 列表，其處理時間與其所存儲的當前分片的 MD5 列表的長度有關。經測試，對於一個 MD5 列表長度為 1000 的 key，全量取回的查詢平均耗時為 8ms，而長度為 5000 的 key，平均需要 40ms 左右。而該列表的大小會在每十分鐘的第 0 分鐘開始線性增長直到該分片的第 10 分鐘，造成 recent_events 平均處理時間在每個十分鐘內也線性增長。對於第 2-6 分片，由於 IndexKey 已經在存儲在 LocalCache 中，並不影響處理時間。
對於這個問題，我們使用增量更新的方式優化了 BigCache IndexKey 的存儲。在 LocalCache 中也緩存第 0 和 1 分片的 MD5 列表，並由 BigCache 負責增量更新。具體的做法是這樣每次向 Redis IndexCache 查詢時，不取全量，取而代之的是 LocalCache 以該分片已有 IndexKey 的信息為依據向 Redis 請求該時間段內的增量數據，並更新自己的緩存內容。這樣每次向 Redis IndexCache 請求的數據更新量平均都在10以內，且不會出現每個十分鐘內線性增長的情況，數據的一致性也未破壞。
經過以上兩個優化方案後，recent_events 的處理時間平均穩定為 4-6ms, 相較於只採 MongoDB 的最大返回條數限制為 1000 時的 60 ms 平均處理時間提升明顯。如下圖所示。

通過以上的步驟，基本解決了本文開頭提到的很多接近於重複的查詢和大數據量的查詢對於 MongoDB 的查詢壓力問題。同時取消 recent_events 返回條數的限制後，相關策略的召回量提升20% 以上，且並不會對系統的性能造成大的影響。
作者：曾濤，翟峰，周奧特
同時感謝反作弊團隊其他同學的幫助

關於「悟空（Wukong）」
- 2016.7.26 知乎反作弊系統「悟空」演變
- 2015.4.9 「悟空」和大家見面啦