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

郭 亮，楊金民

湖南大學 信息科學與工程學院，長沙 410082

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

郭 亮，楊金民

湖南大學 信息科學與工程學院，長沙 410082

1 引言

隨著信息化技術進一步的發展和數據量的暴增，現有的增量提取技術無法大幅度地減少數據備份時間，滿足人們的備份需求；對于大部分的用戶來說，備份速度過慢將會影響正常的業務運營。在某些大規模數據密集型系統中（如：網絡安全監控、金融數據分析、電信數據處理等領域），這些問題尤為突出[1-3]。

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

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

2.1 問題分析

通過分析增量提取的過程發現，增量提取問題可等價于求解以下問題：

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

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

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

2.2 算法概述

為了減少多屬性字段比對的影響，文獻[9]提出了一種在源表中增加這樣一個字段，該字段不具備任何意義，但能唯一識別一條記錄，就好像影子一樣，因此也被形象地稱為“影子主碼”。“影子主碼”解決了多字段比對對效率的影響，變相地限定了比對字段的個數和長度，提高了比對效率；另外，該方法獨立于任何的系統平臺，具有很好的適應性，能很好地解決分布式數據庫的同步和備份問題，但“影子主碼”破壞了表的空間結構，在某些系統中，破壞源表結構意味著系統崩潰。

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

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

2.3 算法描述

現階段的主流數據庫都提供了對MD5和HASH算法的支持，以ORACLE數據庫為例，M-HJ算法的過程可以分成以下三個階段：

準備階段：利用數據庫的存儲過程封裝MD5方法，使其支持多字段的輸入；經過MD5運算得到的128 bit的MD5值經過相應轉換可得到一個32 Byte的字符串，因此，該存儲過程還需實現這一功能。

初始化階段：構建備份表，該表只含有一個32 Byte的字段，存儲已備份記錄的MD5值。

提取階段：當需要提取增量時，利用封裝的MD5方法動態生成源表MD5值，同時將備份中的MD5進行散列得到散列表，對每個動態生成的MD5值去散列表中進行探測，獲取增量記錄。

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

融入MD5的HASH線性掃描獲取增量的方法，與傳統方法相比較，限定了每次比較字符串的個數和長度，同時降低了總的對比次數，提高了增量提取的效率，在數據量大且屬性字段較多的情況下，優勢更加明顯。

3 算法性能分析

3.1 時間復雜度整體分析

可以用下面的公式來計算增量提取所花費的總時間T：

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

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

3.2 明細時間分析

（1）進行MD5運算得到MD5值所需時間T2

T2主要受MD5算法性能的制約，現如今的MD5算法在傳統算法的基礎之上有了很大的改進，效率明顯增強，通常對1 GB數據進行MD5運算只需15～20 s。而兩個1 GB大小的文件進行比較的開銷要遠大于進行MD5運算所花時間，因此當需比對的屬性字段越多時，這種優勢更加明顯。

（2）備份表結果集生成散列表所需時間T4

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

（3）MD5值在散列表中進行查找所需時間T5

與T4類似，原始表中動態生成的MD5值在散列表進行查找所需時間T5可看成是對原始表結果集的一次掃描。

（4）進行每次字符串比對所需時間T6

進行MD5運算得到的MD5值只是一個32 Byte的字符串，兩個32 Byte長度的字符串進行比較所花時間很小，幾乎可以忽略不記。

（5）綜合性分析

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

3.3 小結

綜合以上的分析可知，通過屬性字段的MD5變換限定了對比字段的個數和長度，采用散列表的方式減少了總體比對次數，提高了效率。又因為該算法的時間復雜度為線性的，所以不會出現對比時間因原始數據的增長而呈現非線性增長，并且在對比屬性字段較多的情況下會取得更高的效率。

4 性能測試與結果分析

4.1 測試概述及方法介紹

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

4.2 測試環境

操作系統：Windows7；硬件：CPU 2.8 GHz，內存4 GB，硬盤250 GB；數據庫：Oracle 10g

由于整個測試過程只涉及到數據讀取、MD5運算、HASH映射，對操作系統、軟件平臺以及開發語言的依賴性很小，因此可以認為經過上述測試方法產生的結果具有普遍性。

4.3 測試結果及分析

4.3.1 測試數據

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

表1 測試表格

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

在圖2中，給出了在該實驗環境下，傳統的排序求差集和本文提出的散列表法的對比，從圖中可以看出，當數據總量增加時，散列表法的所需時間更少。

圖2 增量提取所選方法的對比

4.3.3 經過MD5變換屬性字段的對比

在圖3中，給出了在相同實驗環境下，字段數量和記錄總數，對增量提取效率的影響，從圖中可以看出經過MD5轉換屬性的方法比直接進行全屬性字段對比的方法效率更高，隨著數據量的增加這種優勢會更加突出。

圖3 全屬性字段與MD5轉換字段的對比

4.3.4 綜合性能對比

在圖4中，給出了相同環境下，采用傳統S-MJ法與本文提出的M-HJ法的運行時間對比，從圖中可以看到M-HJ法比傳統的S-MJ法運行時間要少，尤其隨著數據量的增長，在字段較多的情況下，M-HJ方法優勢更將加明顯。

圖4 傳統S-MJ算法與M-HJ算法的對比

5 結論

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

[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中提取增量數據的一種方法[J].計算機與數字工程，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]鄭祥云，張娟，葛文庚.數據庫同步中差異數據捕獲方案設計與實現[J].電腦知識與技術，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]李懿，羅軍.影子主碼及其在工作流引擎設計中的應用[J].計算機工程與應用，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#實現[J].通信技術，2008，41（8）：71-72.

[12]周林，韓文報，祝衛華，等.MDx差分攻擊算法改進及GPGPU 上的有效實現[J].計算機學報，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

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

增量提取；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.

國家自然科學基金（No.61272401）；“973”子項目（No.2012CB315801）。

郭亮（1987—），男，碩士研究生，研究領域為軟件工程、數據庫增量提取；楊金民（1967—），男，博士，教授，研究領域為軟件工程、容錯計算、數據挖掘。E-mail：guoliang0709@163.com

2013-01-14

2013-02-20

1002-8331（2014）23-0136-04

CNKI網絡優先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.010.html