郭 亮，楊金民

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082

融入MD5的HASH線性獲取增量算法研究

郭 亮，楊金民

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082

1 引言

隨著信息化技術(shù)進(jìn)一步的發(fā)展和數(shù)據(jù)量的暴增，現(xiàn)有的增量提取技術(shù)無法大幅度地減少數(shù)據(jù)備份時(shí)間，滿足人們的備份需求；對(duì)于大部分的用戶來說，備份速度過慢將會(huì)影響正常的業(yè)務(wù)運(yùn)營(yíng)。在某些大規(guī)模數(shù)據(jù)密集型系統(tǒng)中（如：網(wǎng)絡(luò)安全監(jiān)控、金融數(shù)據(jù)分析、電信數(shù)據(jù)處理等領(lǐng)域），這些問題尤為突出[1-3]。

常用的數(shù)據(jù)庫增量提取方法主要有兩種：（1）基于NOT EXISTS 的 SQL 語句[4]；（2）基于 Sort-Merge Join（S-MJ）的方法[5-7]。第一種方法所采用的掃描策略需要進(jìn)行至少M(fèi)×N次比較，其時(shí)間復(fù)雜度為O(n2)，雖然在數(shù)據(jù)庫中對(duì)相關(guān)字段建立索引能提高效率，但在數(shù)據(jù)量較大的情況下，其性能會(huì)急劇下降，效率低下。第二類方法中最具代表意義的是SQL語句MINUS[8]，求集合的差集，其具體的實(shí)現(xiàn)過程是對(duì)原始表和備份表所有記錄的相關(guān)字段進(jìn)行排序，線性比較兩有序集合得出增量記錄；第二種方法較第一種方法有很大的改進(jìn)，尤其在數(shù)據(jù)量較大的情況下優(yōu)勢(shì)更加明顯，但其效率受到排序算法性能和排序字段數(shù)的影響較大，有待進(jìn)一步提升。本文提出了一種融入MD5的 HASH線性掃描獲取增量的方法（MD5-Hash Join，M-HJ），采用了HASH查找時(shí)間復(fù)雜度為O(1)的特性，極大地降低了比對(duì)次數(shù)；同時(shí)通過MD5算法變換屬性字段，限定比對(duì)字段的個(gè)數(shù)和長(zhǎng)度。M-HJ從整體上來說降低了算法的時(shí)間復(fù)雜度，實(shí)現(xiàn)了線性掃描就能夠獲取增量數(shù)據(jù)的目的，提高了增量提取的效率。

2 基于MD5和HASH的增量提取法

2.1 問題分析

通過分析增量提取的過程發(fā)現(xiàn)，增量提取問題可等價(jià)于求解以下問題：

設(shè)有集合 A={a1，a2，…，an}、集合 B={b1，b2，…，bm}，求A中不在B中的元素的集合。

數(shù)據(jù)庫中常用的求解問題的方法有兩種：（1）SQL語句 NOT EXISTS（N-EXI）；（2）Sort-Merge Join方法。

圖1展現(xiàn)了在具體情況下，NOT EXISTS和S-MJ兩種方法的具體實(shí)現(xiàn)。其中NOT EXISTS是將A中所有元素依次去B中探測(cè)，如果不存在則該元素為增量；而S-MJ方法是先將A和B分別進(jìn)行排序，隨后線性掃描有序集合A和B得到增量數(shù)據(jù)。

2.2 算法概述

為了減少多屬性字段比對(duì)的影響，文獻(xiàn)[9]提出了一種在源表中增加這樣一個(gè)字段，該字段不具備任何意義，但能唯一識(shí)別一條記錄，就好像影子一樣，因此也被形象地稱為“影子主碼”?！坝白又鞔a”解決了多字段比對(duì)對(duì)效率的影響，變相地限定了比對(duì)字段的個(gè)數(shù)和長(zhǎng)度，提高了比對(duì)效率；另外，該方法獨(dú)立于任何的系統(tǒng)平臺(tái)，具有很好的適應(yīng)性，能很好地解決分布式數(shù)據(jù)庫的同步和備份問題，但“影子主碼”破壞了表的空間結(jié)構(gòu)，在某些系統(tǒng)中，破壞源表結(jié)構(gòu)意味著系統(tǒng)崩潰。

MD5即Message-Digest Algorithm 5（信息摘要算法5）[10-12]，它能將任意長(zhǎng)度的數(shù)據(jù)變換成一個(gè)128 bit的數(shù)。對(duì)于任何一個(gè)數(shù)據(jù)，無論數(shù)據(jù)長(zhǎng)短，也不管是何種數(shù)據(jù)類型，都有且只有一個(gè)MD5值，當(dāng)數(shù)據(jù)本身發(fā)生變化，其MD5值也會(huì)發(fā)生改變，而兩個(gè)不同數(shù)據(jù)的MD5值發(fā)生碰撞幾率非常小。根據(jù)MD5算法的這一原理，當(dāng)需要提取增量時(shí)，可動(dòng)態(tài)生成每條記錄的MD5值作為“影子主碼”，這樣既具備了“影子主碼”的優(yōu)勢(shì)，也不會(huì)破壞源表的空間結(jié)構(gòu)。

散列表（Hash table，也叫哈希表）[13-15]，它是基于快速存取的角度設(shè)計(jì)的，也是一種典型的“空間換時(shí)間”的算法；同時(shí)是一種根據(jù)關(guān)鍵碼值（Key value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度，一個(gè)設(shè)計(jì)良好的散列表，其查找時(shí)間復(fù)雜度為O(1)。根據(jù)散列表的這一特性，可以將備份表的所有記錄通過散列函數(shù)生成散列表，讓源表中每條記錄去散列表中查找，查找不成功的元素則為增量元素。

2.3 算法描述

現(xiàn)階段的主流數(shù)據(jù)庫都提供了對(duì)MD5和HASH算法的支持，以O(shè)RACLE數(shù)據(jù)庫為例，M-HJ算法的過程可以分成以下三個(gè)階段：

準(zhǔn)備階段：利用數(shù)據(jù)庫的存儲(chǔ)過程封裝MD5方法，使其支持多字段的輸入；經(jīng)過MD5運(yùn)算得到的128 bit的MD5值經(jīng)過相應(yīng)轉(zhuǎn)換可得到一個(gè)32 Byte的字符串，因此，該存儲(chǔ)過程還需實(shí)現(xiàn)這一功能。

初始化階段：構(gòu)建備份表，該表只含有一個(gè)32 Byte的字段，存儲(chǔ)已備份記錄的MD5值。

提取階段：當(dāng)需要提取增量時(shí)，利用封裝的MD5方法動(dòng)態(tài)生成源表MD5值，同時(shí)將備份中的MD5進(jìn)行散列得到散列表，對(duì)每個(gè)動(dòng)態(tài)生成的MD5值去散列表中進(jìn)行探測(cè)，獲取增量記錄。

這里用S代表原始表，B代表備份表，獲得的增量記錄存進(jìn)表C中。所有的過程都是在ORACLE數(shù)據(jù)庫中實(shí)現(xiàn)的，具體的算法偽代碼如下：

融入MD5的HASH線性掃描獲取增量的方法，與傳統(tǒng)方法相比較，限定了每次比較字符串的個(gè)數(shù)和長(zhǎng)度，同時(shí)降低了總的對(duì)比次數(shù)，提高了增量提取的效率，在數(shù)據(jù)量大且屬性字段較多的情況下，優(yōu)勢(shì)更加明顯。

3 算法性能分析

3.1 時(shí)間復(fù)雜度整體分析

可以用下面的公式來計(jì)算增量提取所花費(fèi)的總時(shí)間T：

T=T1+T2×k+T3+T4×b+T5×k+T6×(k-m)+T7×m其中，T1為提取原始表結(jié)果集時(shí)間；T2為原始表結(jié)果集動(dòng)態(tài)生成MD5值所需時(shí)間；T3為提取備份表結(jié)果集時(shí)間；T4為備份表結(jié)果集生成散列表所需時(shí)間；T5為原始表動(dòng)態(tài)生成的MD5值到散列表中進(jìn)行查找所需時(shí)間；T6為每次具體比對(duì)MD5所需時(shí)間；T7為增量記錄插入臨時(shí)表所需時(shí)間；k為原始記錄數(shù)；b為備份記錄數(shù)；m為增量記錄數(shù)。

分析：其中T1、T3主要受所用硬件資源和具體數(shù)據(jù)庫的性能影響，而T7所需時(shí)間則取決于數(shù)據(jù)庫所采取的插入策略，所以主要對(duì)T2、T4、T5和T6進(jìn)行分析。

3.2 明細(xì)時(shí)間分析

（1）進(jìn)行MD5運(yùn)算得到MD5值所需時(shí)間T2

T2主要受MD5算法性能的制約，現(xiàn)如今的MD5算法在傳統(tǒng)算法的基礎(chǔ)之上有了很大的改進(jìn)，效率明顯增強(qiáng)，通常對(duì)1 GB數(shù)據(jù)進(jìn)行MD5運(yùn)算只需15～20 s。而兩個(gè)1 GB大小的文件進(jìn)行比較的開銷要遠(yuǎn)大于進(jìn)行MD5運(yùn)算所花時(shí)間，因此當(dāng)需比對(duì)的屬性字段越多時(shí)，這種優(yōu)勢(shì)更加明顯。

（2）備份表結(jié)果集生成散列表所需時(shí)間T4

通過散列函數(shù)得到散列地址所需的時(shí)間非常小，幾乎可以忽略不記，因此生成散列表所需時(shí)間T4可看成是對(duì)備份表結(jié)果集的一次掃描。

（3）MD5值在散列表中進(jìn)行查找所需時(shí)間T5

與T4類似，原始表中動(dòng)態(tài)生成的MD5值在散列表進(jìn)行查找所需時(shí)間T5可看成是對(duì)原始表結(jié)果集的一次掃描。

（4）進(jìn)行每次字符串比對(duì)所需時(shí)間T6

進(jìn)行MD5運(yùn)算得到的MD5值只是一個(gè)32 Byte的字符串，兩個(gè)32 Byte長(zhǎng)度的字符串進(jìn)行比較所花時(shí)間很小，幾乎可以忽略不記。

（5）綜合性分析

當(dāng)所需比較的屬性字段越多，且其長(zhǎng)度遠(yuǎn)大于32 Byte時(shí)，直接比較這樣長(zhǎng)度的兩個(gè)字符串所需時(shí)間遠(yuǎn)大于將字符串進(jìn)行MD5變換后再進(jìn)行比較所需時(shí)間；假設(shè)訪問一次結(jié)果集并進(jìn)行散列函數(shù)運(yùn)算所需時(shí)間為tc，備份表結(jié)果集大小為b，原始表結(jié)果集大小為k，則訪問備份表結(jié)果集并生成散列表所需時(shí)間為tc×b，原始表中動(dòng)態(tài)生成的MD5值并在散列表中進(jìn)行查找所需時(shí)間為tc×k，那么所需的總時(shí)間為tc×(b+k)，也就是說，在這樣的前提下，算法的時(shí)間復(fù)雜度為O(n)。

3.3 小結(jié)

綜合以上的分析可知，通過屬性字段的MD5變換限定了對(duì)比字段的個(gè)數(shù)和長(zhǎng)度，采用散列表的方式減少了總體比對(duì)次數(shù)，提高了效率。又因?yàn)樵撍惴ǖ臅r(shí)間復(fù)雜度為線性的，所以不會(huì)出現(xiàn)對(duì)比時(shí)間因原始數(shù)據(jù)的增長(zhǎng)而呈現(xiàn)非線性增長(zhǎng)，并且在對(duì)比屬性字段較多的情況下會(huì)取得更高的效率。

4 性能測(cè)試與結(jié)果分析

4.1 測(cè)試概述及方法介紹

為了驗(yàn)證本文提出的融入MD5的HASH線性掃描獲取數(shù)據(jù)庫增量方法的優(yōu)勢(shì)，對(duì)傳統(tǒng)的S-MJ方法和本文提出的M-HJ方法分別進(jìn)行了測(cè)試和分析。具體以某電信運(yùn)營(yíng)商業(yè)務(wù)支撐中心在實(shí)際業(yè)務(wù)需求中需要提取增量數(shù)據(jù)的表和對(duì)應(yīng)屬性字段為例，分別挑選不同數(shù)量級(jí)數(shù)據(jù)表進(jìn)行測(cè)試。為了更好的比對(duì)結(jié)果，暫不考慮增量記錄插入數(shù)據(jù)庫所需時(shí)間，只比較識(shí)別增量記錄所需時(shí)間。

4.2 測(cè)試環(huán)境

操作系統(tǒng)：Windows7；硬件：CPU 2.8 GHz，內(nèi)存4 GB，硬盤250 GB；數(shù)據(jù)庫：Oracle 10g

由于整個(gè)測(cè)試過程只涉及到數(shù)據(jù)讀取、MD5運(yùn)算、HASH映射，對(duì)操作系統(tǒng)、軟件平臺(tái)以及開發(fā)語言的依賴性很小，因此可以認(rèn)為經(jīng)過上述測(cè)試方法產(chǎn)生的結(jié)果具有普遍性。

4.3 測(cè)試結(jié)果及分析

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

在表1中，給出了記錄總量、增量記錄數(shù)量以及每條記錄所包含的字段數(shù)，這幾項(xiàng)對(duì)增量提取的效率影響最大的要素。

表1 測(cè)試表格

4.3.2 HASH線性掃描與排序求差集方法對(duì)比

在圖2中，給出了在該實(shí)驗(yàn)環(huán)境下，傳統(tǒng)的排序求差集和本文提出的散列表法的對(duì)比，從圖中可以看出，當(dāng)數(shù)據(jù)總量增加時(shí)，散列表法的所需時(shí)間更少。

圖2 增量提取所選方法的對(duì)比

4.3.3 經(jīng)過MD5變換屬性字段的對(duì)比

在圖3中，給出了在相同實(shí)驗(yàn)環(huán)境下，字段數(shù)量和記錄總數(shù)，對(duì)增量提取效率的影響，從圖中可以看出經(jīng)過MD5轉(zhuǎn)換屬性的方法比直接進(jìn)行全屬性字段對(duì)比的方法效率更高，隨著數(shù)據(jù)量的增加這種優(yōu)勢(shì)會(huì)更加突出。

圖3 全屬性字段與MD5轉(zhuǎn)換字段的對(duì)比

4.3.4 綜合性能對(duì)比

在圖4中，給出了相同環(huán)境下，采用傳統(tǒng)S-MJ法與本文提出的M-HJ法的運(yùn)行時(shí)間對(duì)比，從圖中可以看到M-HJ法比傳統(tǒng)的S-MJ法運(yùn)行時(shí)間要少，尤其隨著數(shù)據(jù)量的增長(zhǎng)，在字段較多的情況下，M-HJ方法優(yōu)勢(shì)更將加明顯。

圖4 傳統(tǒng)S-MJ算法與M-HJ算法的對(duì)比

5 結(jié)論

本文在傳統(tǒng)的增量提取實(shí)現(xiàn)方法的基礎(chǔ)上，通過屬性字段的MD5轉(zhuǎn)換，并結(jié)合HASH算法，提出了一種融入MD5的HASH線性掃描獲取增量方法。該算法對(duì)屬性字段的MD5轉(zhuǎn)換限定了對(duì)比字段的個(gè)數(shù)和長(zhǎng)度，同時(shí)結(jié)合散列表的方式，大大降低了記錄的比對(duì)次數(shù)，降低了算法的時(shí)間復(fù)雜度，提高了增量提取的效率。經(jīng)過應(yīng)用測(cè)試表明，該算法在增量提取效率上比傳統(tǒng)方法有了很大的提高，能夠快速識(shí)別出增量數(shù)據(jù)。該算法已在電信運(yùn)營(yíng)商業(yè)務(wù)支撐中心增量數(shù)據(jù)提取方面得到了應(yīng)用驗(yàn)證，并取得了較好的結(jié)果。由于散列表法是以空間換時(shí)間的算法，因此M-HJ法對(duì)運(yùn)行時(shí)空間要求較高。

[1]Kimberly K，Cipriano S，Dirk B，et al.Designing for disasters[C]//Proceedings of the 3rd USENIX Conference on File and Storage Technologies，San Francisco，CA，USA，2004：59-62.

[2]Gantz J F，Chute C.The diverse and exploding digital universe：an updated forecast of worldwide information growth through 2011[R].Framingham：IDC，2008：2-16.

[3]Tu P H，Chen Y，Son T C，et al.Incremental information extraction using relationaldatabases[J].Knowledge and Data Engineering，2012，24（1）：86-99.

[4]史晶波.在DB2中提取增量數(shù)據(jù)的一種方法[J].計(jì)算機(jī)與數(shù)字工程，2004，32（6）：15-16.

[5]Li Qun，XuHonglin.Researchonthebackupmechanism of Oracle database[C]//Environmental Science and Information Application Technology，2009，2：423-426.

[6]鄭祥云，張娟，葛文庚.數(shù)據(jù)庫同步中差異數(shù)據(jù)捕獲方案設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2009，5（7）：1544-1545.

[7]Martina-Cezara A，Alfons K，Thomas N.Massively parallel sort-merge joins in main memory multi-core database systems[J].Proceedings of the VLDB Endowment，2012，5（10）：1064-1075.

[8]Rogers M.SQL reporting and custom services workshop[C]// ELUNA，2007：5-8.

[9]李懿，羅軍.影子主碼及其在工作流引擎設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（32）：158-159.

[10]Ignacio A B，Claudia F U，René C，et al.Design and implementation of a non-pipelined MD5 hardware architecture using a new functionaldescription[J].IEICETransactions on Information and Systems，2008，E91-D（10）：2519-2523.

[11]杜昌鈺.MD5算法的過程分析及其C#實(shí)現(xiàn)[J].通信技術(shù)，2008，41（8）：71-72.

[12]周林，韓文報(bào)，祝衛(wèi)華，等.MDx差分攻擊算法改進(jìn)及GPGPU 上的有效實(shí)現(xiàn)[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（7）：1177-1181.

[13]Lv Huizhan，Xiao Chenjun，Li Hongye，et al.Hash table in Chinese chess[C]//Control and Decision Conference（CCDC），2012，24：3286-3291.

[14]Xia Weijian，Zhao Heji，Zhao Jiasheng，et al.The XML filtration based on hash table and stream index[C]// Mechatronic Science，Electric Engineering and Computer，2011：1286-1290.

[15]Jimeno M，Christensen K.P2P directory search：signature array hash table[C]//Local Computer Networks，2008，33：506-508.

GUO Liang,YANG Jinmin

College of Information Science and Engineering,Hunan University,Changsha 410082,China

To achieve rapid incremental extraction of database,an algorithm which is blended MD5 in HASH linear scanning to obtain increment is put forward based on analyzing the traditional incremental extraction.Each record in database can be seen as a character string and it can be generated into hash table as duplicate record,which is explored in hash table through traditional record to obtain increment and decrease frequency of comparison.Meanwhile,the fingerprint of each record can be generated with using MD5 algorithm,which reduces the length of character string in every HASH algorithm and comparison and improves efficiency.This algorithm is applicably tested in ORACLE database and the result shows that it is improved on calculative efficiency at a large extent compared with traditional algorithm.

incremental extraction;MD5 algorithm;HASH algorithm;linear scan

為了實(shí)現(xiàn)數(shù)據(jù)庫中的快速增量提取，在剖析傳統(tǒng)的增量提取方法上，提出了一種融入MD5的HASH線性掃描來獲取增量的算法。數(shù)據(jù)庫中的每條記錄都可視為一個(gè)字符串，利用HASH算法生成備份記錄的散列表，通過原始記錄去散列表中探測(cè)來達(dá)到線性掃描就能獲取增量的目的，減少了比對(duì)次數(shù)；同時(shí)利用MD5算法生成每條記錄的“指紋”，降低了每次HASH運(yùn)算和比對(duì)的字符串長(zhǎng)度，提高了效率。對(duì)所提出算法在ORACLE數(shù)據(jù)庫上進(jìn)行了應(yīng)用測(cè)試，結(jié)果表明該算法效率較傳統(tǒng)方法有很大提高。

增量提??；MD5算法；HASH算法；線性掃描

A

TP311.138

10.3778/j.issn.1002-8331.1301-0132

GUO Liang,YANG Jinmin.Research of incremental extraction based on MD5 and HASH algorithm.Computer Engineering and Applications,2014,50（23）：136-139.

國(guó)家自然科學(xué)基金（No.61272401）；“973”子項(xiàng)目（No.2012CB315801）。

郭亮（1987—），男，碩士研究生，研究領(lǐng)域?yàn)檐浖こ?、?shù)據(jù)庫增量提??；楊金民（1967—），男，博士，教授，研究領(lǐng)域?yàn)檐浖こ?、容錯(cuò)計(jì)算、數(shù)據(jù)挖掘。E-mail：guoliang0709@163.com

2013-01-14

2013-02-20

1002-8331（2014）23-0136-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.010.html