面向大規(guī)模金融對賬文件的近似比對模型及系統(tǒng)①

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

?

面向大規(guī)模金融對賬文件的近似比對模型及系統(tǒng)①

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

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

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

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

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

1　相關(guān)研究

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

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

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

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

2　UpCompare模型

UpCompare模型采用以文件為切片的多進(jìn)程并行比對方式,提升大規(guī)模文件的批量比對效率.在此基礎(chǔ)上,UpCompare模型將單個金融對賬文件的比對流程分為三個層次: 文件屬性比對層、文件內(nèi)容快速比對層、文件內(nèi)容精細(xì)比對層,結(jié)合快速致勝思想,通過流程控制調(diào)度上述三個層次完成單個文件的比對任務(wù),即在執(zhí)行兩個相似文件的比對時,自頂而下,依次比對,如果上一個層次發(fā)現(xiàn)差異即跳過后續(xù)層次的比對,從而節(jié)約了時間和系統(tǒng)的開銷.如圖1所示為UpCompare模型結(jié)構(gòu)圖.

圖1　UpCompare模型結(jié)構(gòu)圖

2.1多進(jìn)程并行控制模塊

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

多進(jìn)程并行控制模塊的功能是根據(jù)事先設(shè)定的進(jìn)程數(shù)量啟動多個進(jìn)程,每個進(jìn)程循環(huán)調(diào)用流程控制模塊執(zhí)行文件比對流程.該模塊的最小任務(wù)切片單位是單個文件,任務(wù)分派方式采用預(yù)先均分結(jié)合時間片輪轉(zhuǎn)動態(tài)調(diào)配機(jī)制,進(jìn)程數(shù)根據(jù)運(yùn)行系統(tǒng)資源情況推薦并由比對人員設(shè)定.多進(jìn)程并行處理的原理圖如圖2所示,其關(guān)鍵處理步驟包括:

圖2　多進(jìn)程并行處理原理圖

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

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

(3)啟動執(zhí)行: 啟動各進(jìn)程,調(diào)用比對流程控制模塊,依次執(zhí)行隊(duì)列中的比對任務(wù);

(4)動態(tài)調(diào)配: 多進(jìn)程并行控制模塊以時間片輪詢各進(jìn)程執(zhí)行隊(duì)列忙閑狀態(tài),并為比對文件任務(wù)動態(tài)調(diào)配執(zhí)行進(jìn)程.

2.2流程控制模塊

流程控制模塊負(fù)責(zé)調(diào)度文件屬性比對層、文件內(nèi)容快速比對層、文件內(nèi)容精細(xì)比對層、比對結(jié)果處理等模塊完成單個文件的比對任務(wù).UpCompare模型采用快速致勝比對策略,其處理文件比對任務(wù)的核心思想首先執(zhí)行開銷最小的比對層次任務(wù),比如發(fā)現(xiàn)文件名或文件大小不一致即退出,不再進(jìn)入后續(xù)比對步驟.如圖3所示為文件比對任務(wù)的處理流程圖.

圖3　文件比對任務(wù)處理流程圖

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

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

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

2.3結(jié)果處理模塊

結(jié)果處理模塊負(fù)責(zé)將比對差異結(jié)果進(jìn)行個性化輸出,同時,支持比對過程的日志記錄顯示.

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

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

3　UpCompare模型在我國銀行卡清算系統(tǒng)中的應(yīng)用

UpCompare模型已在我國銀行卡清算系統(tǒng)中得到應(yīng)用,針對系統(tǒng)特點(diǎn),本模型在技術(shù)實(shí)現(xiàn)過程中有以下兩個關(guān)鍵點(diǎn).

3.1文件快速比對層算法的實(shí)現(xiàn)

對文本內(nèi)容信息與關(guān)鍵字的匹配已有多種匹配算法,如單模式匹配算法中的BM算法和KMP算法,多模式匹配算法中的AC算法、Wu-Manber算法等[5].本文針對金融對賬文件獨(dú)有的特點(diǎn),提出的UpCompare模型文件快速對比層算法,可以很好的實(shí)現(xiàn)大規(guī)模金融對賬文件的比對.

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

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

圖4　文件比對模型圖

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

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

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

3.2索引沖突的處理

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

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

比對過程中,文件A的索引數(shù)組演進(jìn)變化情況如下

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

3.3測試數(shù)據(jù)

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

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

表1　效率對比結(jié)果

4　結(jié)語

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

參考文獻(xiàn)

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科曼.潘金貴,譯.算法導(dǎo)論.機(jī)械工業(yè)出版社,2006.

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

5何文華.基于海量數(shù)據(jù)的多模式匹配算法研究.計(jì)算機(jī)應(yīng)用與軟件,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