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

?

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

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

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

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

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

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

1　相關(guān)研究

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

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

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

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

2　UpCompare模型

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

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

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

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

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

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

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

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

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

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

2.2流程控制模塊

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

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

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

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

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

2.3結(jié)果處理模塊

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

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

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

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

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

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

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

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

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

圖4　文件比對(duì)模型圖

圖5　單個(gè)文件比對(duì)處理流程圖

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

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

3.2索引沖突的處理

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

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

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

參考文獻(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)境高級(jí)編程.尤晉元,張亞英,戚正偉,譯.北京:人民郵電出版社,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

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