面向大規模金融對賬文件的近似比對模型及系統①

尹祥龍,王偉,陳煜,周繼恩,任明,徐景良,萬鑫明(中國銀聯股份有限公司,上海 00)(中國科學院軟件研究所,北京 0090)

?

面向大規模金融對賬文件的近似比對模型及系統①

尹祥龍1,王偉2,陳煜1,周繼恩1,任明1,徐景良1,萬鑫明1
1(中國銀聯股份有限公司,上海 201201)
2(中國科學院軟件研究所,北京 100190)

摘 要:針對TB級的大規模金融對賬文件的近似比對問題,本文深入分析了金融對賬文件的特點,以提升比對速度作為研究目標,提出了一種多層次的近似比對模型—UpCompare模型.UpCompare模型以多進程為擴展基礎,采用哈希索引建立映射表結合快速致勝策略為核心算法.測試結果表明,運用UpCompare模型,我國銀行卡清算系統的每日清算文件近似比對效率提升了5倍以上.

關鍵詞:海量文件; 金融對賬文件; 近似比對; 哈希索引

隨著金融領域信息技術的發展,金融對賬文件的類型越來越多,數據量越來越大.以銀行業為例,大型商業銀行的銀行卡清算系統,其每天需要處理TB級數據量的金融對賬文件.金融對賬文件的特點有:一是單個文件容量大,可以達到GB級; 二是文件數量眾多,通常在數萬、甚至數十萬; 三是單個文件中以換行符分割,每行對應一筆交易記錄,行與行之間無序、無關聯性; 四是部分對賬文件需要根據約定打包壓縮.

商用文件比對軟件可以提供基本的內容比對及可視化展現功能,但無法滿足大規模金融對賬文件近似比對的效率要求.運行在大型集群的廉價硬件設備上的開源Hadoop框架,提供了基于MapReduce編程模型實現大規模數據的并行處理[1,2].但是,在處理金融對賬文件,這些方法存在嚴重的通信開銷; 并且,由于文件數據量大、格式特殊,常采用抽樣選取部分文件,排序后進行比對,導致比對結論的可信度不高.因此,研究提升大規模金融對賬文件的近似比對效率就格外重要且緊迫.本文提出一種多層次的近似比對模型UpCompare,模型以多進程為擴展基礎,采用哈希索引[3]建立映射表,并結合快速致勝策略為核心算法,將數據緩存在共享內存[4]中進行比對.測試結果表明,運用該模型,我國銀行卡清算系統的每日清算文件近似比對效率提升了5倍以上.

1　相關研究

現有的商用文件比對軟件,如Ultra Compare和Beyond Compare,主要用于有序文本文件的順序比對、文件比對結果的直觀展示、文件夾批量比對等.例如 Beyond Compare可以遍歷文件夾并批量比對所包含文件,還可以比較Word、Excel等Office文檔內容.這些商用文件比對軟件提供了基本的內容比對及可視化展現功能,但無法滿足大規模金融對賬文件的近似比對需求,主要存在以下問題:

(1)大規模(文件數量在數萬、甚至數十萬)、大容量文件(文件大小可以達到GB級)的快速比對;

(2)以行為單位的雜序文本文件比對;

(3)對部分內容可容忍差異的兼容性比對(兩個近似金融對賬文件中,如果兩筆交易的清算時間戳等非關鍵要素存在差異,可認為是正確匹配的交易).

2　UpCompare模型

UpCompare模型采用以文件為切片的多進程并行比對方式,提升大規模文件的批量比對效率.在此基礎上,UpCompare模型將單個金融對賬文件的比對流程分為三個層次: 文件屬性比對層、文件內容快速比對層、文件內容精細比對層,結合快速致勝思想,通過流程控制調度上述三個層次完成單個文件的比對任務,即在執行兩個相似文件的比對時,自頂而下,依次比對,如果上一個層次發現差異即跳過后續層次的比對,從而節約了時間和系統的開銷.如圖1所示為UpCompare模型結構圖.

圖1　UpCompare模型結構圖

2.1多進程并行控制模塊

現有的商用文件比對軟件,主要解決小數據量的文件比對問題,采用單進程的比對處理機制,難以應用于大規模的文件比對處理.UpCompare模型采用了以文件為切片的多進程控制并行處理方式,由圖1中的多進程并行控制模塊具體實現.

多進程并行控制模塊的功能是根據事先設定的進程數量啟動多個進程,每個進程循環調用流程控制模塊執行文件比對流程.該模塊的最小任務切片單位是單個文件,任務分派方式采用預先均分結合時間片輪轉動態調配機制,進程數根據運行系統資源情況推薦并由比對人員設定.多進程并行處理的原理圖如圖2所示,其關鍵處理步驟包括:

圖2　多進程并行處理原理圖

(1)設定進程數: 計算對賬文件容量大小,根據系統資源情況和經驗數據估算合理的進程數量,并推薦給比對人員,由其最終決定進程數量;

(2)分配任務: 根據比對人員設定的進程數量,按照待比對文件容量大小給各進程初步均分文件比對任務,將任務列表插入到各進程的待比對文件隊列中;在任務分配過程中,如果在兩個待比對文件堆中發現對應目錄下無相同的文件夾或文件名,則直接調用比對結果處理模塊輸出到比對結果中,不再做為比對任務加入隊列;

(3)啟動執行: 啟動各進程,調用比對流程控制模塊,依次執行隊列中的比對任務;

(4)動態調配: 多進程并行控制模塊以時間片輪詢各進程執行隊列忙閑狀態,并為比對文件任務動態調配執行進程.

2.2流程控制模塊

流程控制模塊負責調度文件屬性比對層、文件內容快速比對層、文件內容精細比對層、比對結果處理等模塊完成單個文件的比對任務.UpCompare模型采用快速致勝比對策略,其處理文件比對任務的核心思想首先執行開銷最小的比對層次任務,比如發現文件名或文件大小不一致即退出,不再進入后續比對步驟.如圖3所示為文件比對任務的處理流程圖.

圖3　文件比對任務處理流程圖

(1)文件屬性比對層: 采用快速制勝的策略,依次比較兩個文件待比對文件的類型、大小等屬性,如果發現某一項屬性不一致,則立即返回比對結果,不再進入后續比對層處理; 特別地,對于文件類型為壓縮文件類型,需要先解壓縮再比對.

(2)文件內容快速比對層: 假定待比對任務的兩個文件分別為文件A和文件B,該層次的比對方法首先遍歷文件A的所有行,對文件A的行數據關鍵域建立索引數組,采用高效率的行壓縮技術以及低耦合的散列技術在內存中建立文件A的索引表; 然后,遍歷文件B的各行,比較B中的各行數據的哈希值是否在文件A的索引表中存在,如果不存在,則表示該行是兩個文件的不同處,將該行的相關信息輸出到比對結果的記錄日志記錄.如果文件A與文件B相比是一致的,則使用相同的方法將文件B與文件A進行比對.

(3)文件內容精細比對層: 通過設置文件白名單、黑名單以及文件行的待比較關鍵域和比對策略,選擇近似比對的程度,合理地過濾掉符合金融對賬文件差異的部分,實現比對過程的精細控制.

2.3結果處理模塊

結果處理模塊負責將比對差異結果進行個性化輸出,同時,支持比對過程的日志記錄顯示.

(1)個性化輸出: 通過獲取上面文件比對過程中輸出的結果,根據個性化設置展示給比對人員,增強了結果展示的易讀性、多樣性.通常情況下,比對人員根據原比對文件目錄的結構,篩選出不一致行的數據組織成不一致文件目錄; 同時,按照文件標準規范,拆分出文件和報表比對輸出的所有不同處記錄到比對報告中,并將不一致的文件名使用醒目的顏色標記.

(2)日志記錄顯示: 日志的功能是所有操作的過程信息輸出到日志中,方便比對人員分析查找比對過程中的詳細操作記錄.通過匯總比對的文件列表詳單,統計出比對耗時、差異率、差異的行數和字段數,并以圖形的方式顯示.

3　UpCompare模型在我國銀行卡清算系統中的應用

UpCompare模型已在我國銀行卡清算系統中得到應用,針對系統特點,本模型在技術實現過程中有以下兩個關鍵點.

3.1文件快速比對層算法的實現

對文本內容信息與關鍵字的匹配已有多種匹配算法,如單模式匹配算法中的BM算法和KMP算法,多模式匹配算法中的AC算法、Wu-Manber算法等[5].本文針對金融對賬文件獨有的特點,提出的UpCompare模型文件快速對比層算法,可以很好的實現大規模金融對賬文件的比對.

方法針對單個金融對賬文件進行建模,抽象比對對象.考慮如下情況: 比對對象文件A和文件B,它們以行記錄分割、行之間沒有順序、串值都唯一.例如,文件A是由數據1、2、3、5組成,文件B是由數據1組成,建立的模型如圖4所示.在此基礎上,單個文件比對流程如圖5所示.

首先,讀取文件A,使用哈希(Hash)函數對A的每一行內容進行編碼,得到數組:

圖4　文件比對模型圖

圖5　單個文件比對處理流程圖

接著,逐行讀取文件B,使用哈希函數對B的j行內容進行編碼,得到哈希索引值,然后在數組A[i]中查找是否有值相等的索引值,如果沒有,則說明文件B中這一行在A中不存在; 否則,把B文件行j的內容依次與行號鏈表對應的每 一行內容比對,如果發現相同內容的行,假設與相等,則將A文件的沖突數減一并從行號鏈表中移除文件A中的該行號,如果沖突數被減為0,則從數組中刪除該索引值對應的數組項; 如果依次比對沒發現相同內容的行,說明文件B中這一行在A中不存在.

最后,輸出文件A與文件B的比對結果,包含相同的行號列表和不相同的行號列表.

3.2索引沖突的處理

由于Hash索引存儲技術是一種壓縮存儲技術,會遇到Hash索引值沖突的情況,如何高效的處理索引沖突關系到整個比對算法的效率.UpCompare使用常用的Hash算法,可以有效地對相似度較大的金融對賬流水文件進行Hash散列,使其均勻分布在Hash表中,并且對沖突節點使用鏈表方式存儲,在算法執行過程中可以有效的增加和刪除沖突節點.

為了簡單說明,假設Hash函數采用f(x)= A [i]%4,那么可以得到以下比對過程,輸入文件A、B內容如下:

比對過程中,文件A的索引數組演進變化情況如下

比對結果: 文件B中的內容是文件A的子集,并且A中第1、2行內容在B中存在,A中第3、4行內容在B中不存在.

3.3測試數據

針對近5萬個、數據量共計達到5TB的金融對賬文件,使用UpCompare模型進行比對.測試環境采用IBM P570的6個邏輯服務器,每個配置為8核CPU、16GB內存,待比對文件部署在NFS并通過千兆網絡訪問.測試結果如表1所示,與傳統比對方法相比,UpCompare的比對效率提升了5倍以上.

與原有比對技術相比: 1)UpCompare模型利用快速致勝思想,避免了文件近似比對過程中容易引起的額外時間、空間開銷問題,提高了比對效率; 2)將數據緩存在共享內存中進行比對,避免了排序、壓縮、解壓、拷貝和移動等文件I/O操作; 3)減少了各個環節的人工干預,提高了大規模金融對賬文件近似比對的自動化程度.

表1　效率對比結果

4　結語

本文對大規模金融對賬文件的快速相似比對問題進行了研究,提出了一種采用哈希索引建立映射表結合快速致勝策略的UpCompare模型.測試數據表明UpCompare模型能大幅提高金融對賬文件的比對效率.

參考文獻

1Dean J,Ghemawat S.MapReduce: Simplified data processing on large clusters.Communications of the ACM,2008,51(1): 189–195.

2Lee KH,Lee YJ,Choi H,Chung YD,Moon B.Parallel data processing with MapReduce: A survey.ACM SIGMOD Record,2011,40(4): 11–20.

3科曼.潘金貴,譯.算法導論.機械工業出版社,2006.

4史蒂文斯,拉弋.Unix環境高級編程.尤晉元,張亞英,戚正偉,譯.北京:人民郵電出版社,2006.

5何文華.基于海量數據的多模式匹配算法研究.計算機應用與軟件,2012,29(4):275–277,296.

Massive Financial Reconciliation File Approximate Comparison Model and System

YIN Xiang-Long1,WANG Wei2,CHEN Yu1,ZHOU Ji-En1,REN Ming1,XU Jing-Liang1,WAN Xin-Ming11(China UnionPay,Shanghai 201201,China)
2(Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)

Abstract:Focus on TB Level massive financial reconciliations file approximate comparison problem,this paper researched a number of the financial reconciliations file features to enhance the mass data comparing speed in financial sector,and proposed a multi-level approximate comparison model - UpCompare Model.UpCompare Model is a kind of multi-process technology based on hash index table,using fast winning strategy as the core algorithm,effectively solving the massive financial reconciliations file approximate comparison problem.Experimental results show that,by using UpCompare Model,bank transaction settle system efficiency improved more than 5× in daily financial reconciliations file approximate comparison.

Key words:massive files; financial reconciliation file; approximate comparison; hash index

收稿時間:①2015-07-23;收到修改稿時間:2015-09-14