一種基于實時大數據的分布式智能匹配系統

馮興+周繼恩+方亞超

摘 要：傳統的匹配技術因規則和參數固定，匹配性能和效果很不理想。基于實時大數據和機器學習技術，提出了一種新的分布式智能匹配系統，該系統根據實時匹配成功率和用戶反饋進行自我優化。實驗表明，系統性能可水平擴展，匹配正確率顯著提高。

關鍵詞：智能匹配；實時大數據；機器學習；分布式協調；Spark Streaming

DOIDOI：10.11907/rjdk.171722

中圖分類號：TP303

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0005-04

0 引言

人們通過打車軟件可以匹配到最佳司機出行，亦可通過拼單軟件湊團優惠秒殺；金融機構根據海量歷史交易構造模型，實時偵測詐欺交易；商戶根據客戶群體特征分析消費趨勢，從而進行精準營銷。這一切，都離不開匹配技術。

匹配指事物之間有相符合或相配合的關系，匹配技術旨在以一定的目標、遵循一定的規則建立事物之間的關聯，從而產生“協同效應”[1]。匹配技術一般遵循如下流程：從不同的事物中按照一定的規則提煉出特征，然后按照一定的目標去組合這些特征，能夠滿足預期目標則表示匹配成功[2]。傳統匹配技術采用固定的規則和方法，規則不會隨著實際情況發生調整和改變。實時匹配成功率較低，未成功的匹配只有等待T+1日的批量流程完成處理，難以應對越來越多的（T+0）實時場景需求。實時大數據技術[3]可以將歷史匹配記錄和實時信息結合起來分析，動態調整匹配規則和方法，提升了匹配的實時性和成功率，也提高了匹配效果和用戶體驗。

實時匹配系統大多基于實時處理框架自行開發。滴滴的實時打車平臺根據地理位置、歷史評分撮合乘客、司機、代駕者，采用迭代反饋算法[4]，算法分批次迭代進行，每次的參數都由系統動態生成。比如，系統在匹配失敗后會適當增加距離，降低評分要求，通過調整參數提高匹配成功概率。滴滴打車平臺基于Lambda架構[5]設計，將實時數據和歷史數據結合應用，提升匹配效果，增強用戶體驗，同時獲取更多有價值的數據。

微軟的實時數據質量監控平臺是典型的“模型匹配”[6]系統。平臺后端連接實時機器學習算法，通過分析實時數據和歷史數據，不斷完善風險模型；將結果數據與風險模型動態匹配，可監控數據質量并發出預警。

實時匹配實現具有兩個特點：①結合實時數據和歷史數據共同分析；②可動態調整參數，優化匹配效果。但是，由于匹配技術多是公司的核心技術和商業秘密，現有成果大多閉源，對匹配技術的研究和應用也各自為攻，因此，業內尚未形成一個主流成熟的框架。

1 實時大數據

大數據（Big Data）技術是一種數據存儲和分析技術，具有5V特性[7]。大數據技術能在每日幾百TB的數據增長情況下高效分析數據，并從低價值密度的海量數據中挖掘出有利于企業戰略的信息。

2011年興起的流式計算[8]，被稱為是后Hadoop時代的實時云計算。大數據流式計算引擎將多種數據源的數據整合并切割成小塊，進而對數據進行并行處理，在流數據不斷變化過程中進行實時分析，捕捉并返回可能對用戶有用的信息。流式計算技術百花齊放，種類繁多，如Yahoo的S4、Twitter的Storm、Facebook的Puma，以及被稱為“Hadoop替代者”的Spark和Spark Streaming[9]。其中，S4不支持“至少遞送一次”的規則[10]，導致其有丟失事件的風險；盡管Storm應用較多，但其性能差強人意；相較而言，Spark Streaming采用“微批量”的處理技術，處理性能較高，應用非常廣泛。此外，Spark和圖算法、機器學習算法天然具備兼容性，生態發展較好。

Spark是一個類似MapReduce的并行計算框架，其核心數據結構是彈性分布式數據集（Resilient Distributed Datasets， RDD），提供比MapReduce更豐富的模型，可在內存中對RDD進行多次計算和迭代，并支持復雜的圖算法和機器學習算法。

Spark Streaming是一個建立在Spark之上的實時計算框架，它擴展了Spark處理大規模流式數據的能力，復用Spark接口實現復雜的實時算法，且與Spark生態中的其它組件兼容性好。Spark Streaming處理原理如圖1所示，將數據流按時間片劃分為若干段數據，每一段數據作為一個RDD，處理引擎對每個RDD進行Filter、Map、Reduce等算法操作后，將其作為Spark Job提交給Spark引擎進行計算。Spark Streaming支持數百節點的分布式實時計算，具備計算的高可用、容錯特性。因此，本文采用Spark Streaming作為主要的實時計算技術。

2 智能匹配系統

2.1 匹配流程

匹配系統流程如下：通過規則提取源消息的特征向量，放置于撮合引擎[11]中；撮合引擎以預先設定的目標匹配特征向量；如果匹配結果達到目標要求，則判定為匹配成功；否則，匹配失敗，進入下一次匹配。

傳統匹配技術采用固定的特征向量提取方式，在撮合系統中也使用固定的參數去匹配特征向量[12]。以拼單系統為例，用戶有一張滿500減200的優惠券，但預期消費只有300元，期望通過實時拼單系統找到附近的人一起共享優惠券，傳統匹配技術算法[13]如下：

輸入：特征向量

<優惠券金額，預期消費， 經度，維度>

輸出：匹配結果

（1） 提取特征向量。

（2）將特征向量導入撮合引擎。

（3）撮合引擎根據預先設置參數（如向量權重，超時時間）匹配附近的人。

（4）匹配成功，則返回配對信息。

（5）匹配失敗且未超時，則返回步驟（2）繼續匹配。endprint

（6）匹配失敗且超時，則返回匹配失敗。

如果參數配置不合理，將可能導致客戶等待時間太長、匹配失敗、距離太遠、總體消費金額太多等問題，從而導致客戶流失。此外，由于客戶向系統發送的數據僅是固定的特征向量，客戶的其它信息（如歷史消費次數、信用等級、消費路線等）并未在匹配算法中占有權重，可能使不誠信用戶被頻繁推送，從而導致拼單系統無法精準推送優惠券，用戶體驗效果不佳。

可見，傳統匹配技術無法跟上服務升級速度[14]，也無法滿足需求的時效性和準確性，本文提出基于實時大數據的智能匹配系統，能有效解決以上問題。

2.2 匹配系統總體設計

2.2.1 節點設計

智能匹配系統采用分布式部署結構，有3類角色：

（1）中央控制節點：負責存放當前的特征提取規則以及匹配參數（向量因子權重、超時時間等），實時接收采集節點和撮合節點反饋，調用后端機器學習算法調整模型，并修正規則和參數。

（2）采集節點：負責從多個客戶端收集用戶請求信息，從中央控制節點獲取特征提取規則，按規則對信息進行特征提取，并生成統一格式的報文通過Kafka發送給撮合節點。采集節點會收集用戶的反饋信息，并向中央控制節點進行反饋。

（3）撮合節點：撮合節點負責接收采集節點發過來的信息，按照一定規則，以預先設定的目標進行撮合。撮合節點和中央控制節點保持通信，隨時根據中央控制節點參數調整撮合行為。撮合節點根據匹配成功率、匹配效果向中央控制節點反饋。

2.2.2 運行機制

用戶將匹配請求發送到采集節點，采集節點根據從中央控制節點獲取的特征提取規則，對原始請求進行規則提取和規范化處理，得到特征向量，并將這些特征向量按不同主題發送給不同的撮合節點。撮合節點根據從中央控制節點獲取的匹配參數（例如向量中不同特征的權重）及匹配目標，將采集節點傳來的特征向量流封裝成若干分布式彈性數據集（RDD）以及一系列操作[15]，將其提交給Spark Streaming進行匹配處理。Spark Streaming分為多個微批次進行處理，每次處理后都會存在一些匹配失敗的特征向量。撮合節點將這些向量暫時緩存在Redis[16]，積累到一定數量后，根據機器學習算法結果調整參數，再次封裝為RDD提交給Spark進行二次匹配。撮合節點還會根據匹配成功率、匹配效果向中央控制節點進行反饋，以幫助中央控制節點標記參數樣本[17]，進行自我優化。系統整體設計如圖2所示。

以實時拼單系統為例。實時拼單系統能夠幫助用戶湊單消費優惠券，例如用戶A發布了一個請求：持有一張滿500元減200元優惠券，且期望消費300元。理想狀態是系統能幫助A找到一位期望消費200元的搭檔B，但實際情況可能找到的是消費230元的用戶B。這次匹配也是成功的，只是匹配效果有所下降。此外，智能拼單系統能通過地理位置、歷史評價等信息綜合匹配，同時能根據用戶反饋和實時匹配成功率進行自我優化。本方法中，多名用戶各自提交原始請求到采集節點，采集節點根據特征向量提取規則提取出特征向量λ=<票券門檻，期望消費，經度，緯度，評價分>，將票券類型哈希后發送到某個撮合節點（哈希可以保證同一類型的票券都落在同一個撮合節點上）。采集節點同時也會接收用戶的反饋信息，并通知給中央控制節點。撮合節點從中央控制節點獲取匹配參數，例如向量中的5個因子對匹配結果的影響權重，將特征向量流封裝為RDD，將匹配算法封裝為基于RDD的運算，將其提交給Spark Streaming進行運算。本次運算未能匹配成功的向量將被緩存到Redis中進行下一次運算；同時撮合節點將向中央控制節點反饋匹配結果。

3 智能匹配系統實現

3.1 中央控制節點

中央控制節點主備2個，只有一個節點處于活躍狀態，另一個節點隨時處于待命狀態，主備節點共享存儲。中央控制節點用于存放當前的特征提取規則以及匹配參數（向量因子權重、超時時間等），實時接收采集節點和撮合節點反饋，調用后端機器學習算法調整模型，并修正規則和參數。機器學習算法持續接收反饋，不斷迭代更新模型，直到模型穩定。每當規則和參數發生變化時，都會發起一次同步請求，將信息同步到采集節點和撮合節點。

3.2 采集節點

采集節點收集用戶原始請求，并根據最新的提取規則提取出特征向量，將向量規則化后通過Kafka發送給撮合節點。采集節點同時會收集用戶的反饋信息，比如匹配結果是否滿意、等待時間是否太長等，同時向中央控制單元匯報。

采集節點可通過Redis緩存一些用戶請求，然后集中進行處理后發至Kafka隊列，以提升系統吞吐量；接收數據時，也可一次接收多個用戶請求，再逐一通知給用戶，如圖3所示。

3.3 撮合節點

撮合節點封裝了核心匹配算法。Spark Streaming將撮合節點接收到的流數據劃分成段，每一段對應一個RDD，撮合算法只需要定義基于這些RDD的運算即可。簡單撮合算法思路是：先對數據集進行排序，然后從頭遍歷數據集，對每一個元素從尾部尋找和它匹配的元素；如果匹配，則移除匹配成功的所有元素，如果不匹配，則該元素進入下一次匹配。整個過程迭代數次，直至結果集穩定，偽代碼如下：

sort（dataSet）

while（iteration_times>0）

do

for（ element in dataSet）

find element from the dataset match the destination from the tail

if（match）

remove matched elements

fi

doneendprint

done

由于傳入的向量是多維度的，上述代碼需要修改為：在滿足既定條件情況下，按照其它因子選取最優解。例如在拼單系統中，兩名用戶的湊單金額高于消費券的最低消費額即為匹配成功，但是兩位用戶的距離和信用評價將影響最優匹配結果，而這些因子的權重是由中央控制節點提供的。撮合節點不斷反饋匹配成功率和匹配效果，以使中央控制單元不斷優化參數，具體實現如圖4所示。

此外，RDD中應包含實時數據和歷史數據。算法在處理用戶的實時請求時，可根據用戶的關鍵域信息（例如用戶ID、活躍時間等）從HBase中查詢到該用戶的歷史請求明細，并分析該用戶的信用、行為、消費習慣、偏好等特征，從而為用戶選擇更合適的匹配對象。

撮合節點對一個RDD的匹配計算不一定讓所有消息都完美匹配，那些沒有匹配成功的消息將被緩存進Redis，加入下一次匹配。

4 實驗分析

4.1 實驗環境

實驗節點標準配置：主處理器4核心3.2GHz主頻，內存16G；實驗載體為本文實時拼單系統；以卷積神經網絡（CNN）作為后端機器學習引擎的實現技術。

4.2 實驗1：性能測試

實驗目的：測試本系統性能和水平擴展性。

實驗配置：（初始）4個采集節點，2個撮合節點，40節點Spark集群。

實驗過程：①客戶端不斷增加模擬用戶請求，直至性能瓶頸；②橫向擴容采集節點和撮合節點，觀察實時TPS。

實驗數據：初始配置（6節點），匹配成功的TPS峰值為4.2萬左右；擴容系統至9節點，TPS峰值為6.5萬左右；擴充系統至12節點，TPS峰值為7.9萬左右；最終擴充到21個節點時，TPS的峰值為12萬左右。實驗結果如圖5所示。

圖5 性能測試 圖6 動態優化

在該過程中，系統處理延遲基本處于穩定狀態，隨機用戶的期望匹配延遲小于1.6s。

實驗結論：本系統處理性能優異。根據已公布數據，本系統相比于滴滴實時匹配系統，相同集群規模的吞吐量提升了41%，處理延遲減少了25%～60%。

實驗分析：本系統采用Spark Streaming微批量處理技術，相比于滴滴的Smaza，極大提升了處理能力；采用流批數據并行處理的設計思想，極大減少了處理延遲。

4.3 實驗2：動態優化

實驗目的：證明本系統可根據實時匹配率和用戶評價進行反饋式學習，不斷優化自身參數，提升匹配效果。

實驗配置：4個采集節點，2個撮合節點，40節點的Spark集群，20節點的CNN深度學習網絡。

實驗過程：啟動系統，記錄實時匹配成功率和TPS，持續60分鐘。

實驗現象：開始時匹配成功率較低且劇烈震蕩，隨著深度學習算法的運行，參數不斷調整，成功率開始顯著提升，60分鐘時趨于穩定，成功率大約在78%左右，實驗結果如圖6所示。

實驗結論：本系統能根據實時匹配結果進行自我優化，能夠自動提升匹配成功率。

實驗分析：本系統能根據實時匹配結果進行反饋式分析，動態調整匹配參數，增加匹配成功率；并能結合用戶的歷史信息進行分析，做到“投其所好”，提供更人性化的匹配結果。

5 結語

傳統的匹配技術因規則和參數固定，匹配性能和效果很不理想；基于實時大數據的匹配技術是各公司的核心技術和商業秘密，現有成果大多閉源，研究和應用也各自為攻，尚未形成一個主流成熟的框架。本文提出了一種基于大數據匹配技術的通用技術框架。該框架易搭建，采用分布式架構，支持水平擴展，性能優異，相對于業界主流系統，吞吐量提升了41%，匹配延遲減少了25%以上；結合實時數據和歷史數據分析，匹配結果更精確；后端搭配機器學習算法，可主動優化匹配效果。

參考文獻：

[1] 朱海燕， 蔡銘， 金連甫. 網絡化制造系統中的服務智能匹配技術研究[J]. 計算機工程與應用， 2004， 40（18）：137-140.

[2] 郭會， 王麗俠. 基于個性化需求的拼車路徑匹配算法研究[J]. 計算機技術與發展， 2017（1）：57-60.

[3] 邱雪濤， 趙金濤. 基于實時大數據處理的交易欺詐偵測的研究[J]. 軟件產業與工程， 2013（4）：36-40.

[4] 顧軍華， 任超， 譚慶. 基于正反饋機制的遺傳算法[J]. 計算機工程與應用， 2007， 43（14）：73-74.

[5] 蘇樹鵬. 基于Lambda架構的移動互聯大數據平臺架構的設計與應用[J]. 企業科技與發展， 2016（6）：66-68.

[6] 方幼林， 楊冬青， 唐世渭，等. 數據倉庫中數據質量控制研究[J]. 計算機工程與應用， 2003， 39（13）：1-4.

[7] 孟小峰， 慈祥. 大數據管理：概念、技術與挑戰[J]. 計算機研究與發展， 2013， 50（1）：146-169.

[8] 孫大為. 大數據流式計算：應用特征和技術挑戰[J]. 大數據， 2015， 1（3）：99-105.

[9] 夏俊鸞， 邵賽賽. Spark Streaming：大規模流式數據處理的新貴[J]. 程序員， 2014（2）：44-47.

[10] NEUMEYER L， ROBBINS B， NAIR A， et al. S4：distributed stream computing platform[C].IEEE International Conference on Data Mining Workshops，IEEE Computer Society， 2010：170-177.

[11] 吳媛，李雄德， 陳正軍. 信息供需互助平臺中智能撮合算法研究與設計[J]. 中國陶瓷， 2009（4）：36-38.

[12] 唐亮貴，李雙慶， 程代杰. 基于多主體的撮合交易模型及算法研究[J]. 計算機工程與應用， 2003， 39（23）：145-147.

[13] 李世梁.實時全額支付系統中基于基本環的高效多邊撮合算法分析和設計[J]. 計算機應用與軟件， 2016， 33（9）：296-300.

[14] 佚名.大數據時代[J]. 中國電子科學研究院學報， 2013， 8（1）：27-31.

[15] S GUPTA. Learning real-time processing with spark streaming[EB/OL].http：//www.bokus.com/.

[16] CARLSON J L. Redis in action[J]. Media，johnwiley， 2013（3）：157-159.

[17] 尹寶才， 王文通， 王立春. 深度學習研究綜述[J]. 北京工業大學學報， 2015（1）：48-59.endprint