馬賽牧王晶

（1 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876； 2 東信北郵信息技術(shù)有限公司，北京 100191）

基于文件拆分和緩存預(yù)測的日志文件傳輸算法*

馬賽牧1，2王晶1，2

（1 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876； 2 東信北郵信息技術(shù)有限公司，北京 100191）

當(dāng)今的云計算平臺和大型網(wǎng)站在運行時都會產(chǎn)生大量的日志文件，這些日志文件一般都具有收集分析的價值，所以在日志文件的收集過程中就出現(xiàn)了大日志文件的傳輸問題。本文要解決的問題就是如何使日志文件能夠快速的傳輸?shù)浇邮斩恕榇吮疚脑谘芯苛水?dāng)前已經(jīng)有的大數(shù)據(jù)傳輸辦法之后，針對日志文件提出了與傳輸協(xié)議無關(guān)的新算法：文件拆分和預(yù)測算法。該算法主要由兩部分組成：首先對日志文件進行拆分，拆分成包含描述性信息的文件和包含數(shù)據(jù)的文件，消除了文件中的冗余信息；然后在傳輸過程中通過預(yù)測接收端緩存的數(shù)據(jù)來達到消除傳輸過程中的冗余信息的目的。經(jīng)過實驗檢驗，本文設(shè)計的算法能夠?qū)嶋H傳輸?shù)臄?shù)據(jù)量降低90%以上。

文件傳輸；fingerprint；消除冗余；云計算

各個互聯(lián)網(wǎng)平臺在正常工作時都會產(chǎn)生大量的運行日志，尤其是大型的開放云平臺和電子商務(wù)網(wǎng)站，云平臺的管理者一般都要收集備份這些日志以備監(jiān)控平臺運行情況，以及分析用戶行為。大量的日志不僅占用很多存儲空間，而且更重要的是在傳輸這些文件時非常的低效，很多平臺和網(wǎng)站需要周期性的將日志文件通過網(wǎng)絡(luò)傳輸備份到數(shù)據(jù)中心。在這個過程中，如何在現(xiàn)有帶寬條件下提高數(shù)據(jù)傳輸效率就成為了一個需要解決的問題。

目前業(yè)內(nèi)在大數(shù)據(jù)傳輸方面已經(jīng)做了一些工作。Zohar等人[1]實現(xiàn)了一種數(shù)據(jù)接收端驅(qū)動的傳輸模式，接收端通過預(yù)測傳輸文件的下一段數(shù)據(jù)來減少網(wǎng)絡(luò)上的數(shù)據(jù)傳輸量，文獻[2]是在骨干網(wǎng)上通過選擇傳輸路徑來實現(xiàn)大文件的傳輸，主要適用于有多個存儲轉(zhuǎn)發(fā)節(jié)點的網(wǎng)絡(luò)，通過對網(wǎng)絡(luò)建模可以使用最大流[3]的算法來進行傳輸，文獻[4]是通過檢測網(wǎng)絡(luò)緩存中數(shù)據(jù)的相似性來消除網(wǎng)絡(luò)傳輸?shù)娜哂唷?/p>

上述文獻中的方法都更側(cè)重所傳輸數(shù)據(jù)的通用性，在日志文件的傳輸方面，由于日志文件的特殊性，比如其日志文件格式相對統(tǒng)一固定，因此在使用上述文章中方法傳輸日志文件時，都擁有進一步優(yōu)化的空間。文獻[2]是在提高帶寬利用率做出了貢獻，但并不能減少傳輸量和消除傳輸冗余。文獻[1]主要的使用場景是接收端已經(jīng)擁有部分的數(shù)據(jù)，通過預(yù)測來避免發(fā)送方發(fā)送接收方已經(jīng)擁有的數(shù)據(jù)，但是如果接收方并沒有任何數(shù)據(jù)時，還是需要按照傳統(tǒng)方式發(fā)送數(shù)據(jù)。文獻[4]用于網(wǎng)絡(luò)中的緩存節(jié)點，需要保證兩個緩存節(jié)點都有相同的數(shù)據(jù)，而且對于每一個數(shù)據(jù)分組都需要一次確認是否已經(jīng)存在的過程。

日志文件主要是起到一個記錄的作用，記錄系統(tǒng)運行情況，記錄用戶信息，因而這些文件一般都由兩部分構(gòu)成：描述性信息和數(shù)據(jù)，數(shù)據(jù)是日志文件中包含真實價值的信息，比如電信短信業(yè)務(wù)平臺中，對一條發(fā)送成功的信息，日志記錄下的它的短信ID、下發(fā)時間、接收號碼等，描述性信息則是用來描述清楚這些數(shù)據(jù)代表的真實含義的解釋信息，它對于產(chǎn)生日志的系統(tǒng)來說是無意義的，但是對于需要查閱日志的系統(tǒng)管理者卻是很重要的。日志文件由機器自動生成，所以它其中的描述性信息通常都是事先設(shè)定好的內(nèi)容固定的文字，這些文字隨著時間的推移不斷生成并被寫入到文件中，這使得最后生成的日志文件中有很大一部分信息是重復(fù)不變的。這樣的文件在進行傳輸時，為了提高傳輸效率，應(yīng)該將文件拆分成描述信息文件和數(shù)據(jù)文件，對描述信息文件要進行壓縮處理，消除其中的冗余信息。

本文在拆分日志文件時，采用文獻[5]的方法將字符轉(zhuǎn)化為數(shù)字，通過對數(shù)字的處理識別出文件中的描述性信息，然后將日志文件進行拆分，把數(shù)據(jù)部分提取出來，對剩下的描述性信息進行壓縮處理，這樣就可以最大限度的壓縮日志文件的大小。同時在傳輸時采用預(yù)測的策略，對于文件接收方已經(jīng)擁有的描述性信息不再傳輸，減少描述性信息在系統(tǒng)中的傳輸量。

這種處理方式使傳輸獨立于底層的協(xié)議，可以適用于任何傳輸系統(tǒng)之中。

本文在第1章介紹了數(shù)據(jù)傳輸方面已經(jīng)進行的相關(guān)工作成果，在第2章介紹了本文所介紹的算法的核心思想，包括文件拆分算法和傳輸過程中的冗余消除算法，第3章就算法進行了實際運行測驗，將測驗結(jié)果匯聚成表格，并對實驗結(jié)果進行了分析，第4章對本文進行了總結(jié)，并闡述了不足之處和未來可能的工作重點。

1 相關(guān)工作

在大文件傳輸方面，現(xiàn)在已經(jīng)有了比較多的研究成果，文獻[1]實現(xiàn)了一種數(shù)據(jù)接收端驅(qū)動的傳輸模式，接收端通過預(yù)測傳輸文件的下一段數(shù)據(jù)來減少網(wǎng)絡(luò)上的數(shù)據(jù)傳輸量。

文獻[2]是在骨干網(wǎng)上通過選擇傳輸路徑來實現(xiàn)大文件的傳輸，主要適用于有多個存儲轉(zhuǎn)發(fā)節(jié)點的網(wǎng)絡(luò)，通過對網(wǎng)絡(luò)建?？梢允褂米畲罅鱗3]的算法來進行傳輸。

文獻[4]是通過檢測網(wǎng)絡(luò)緩存中數(shù)據(jù)的相似性來消除網(wǎng)絡(luò)傳輸?shù)娜哂?，它利用了文獻[5]中的方法來處理數(shù)據(jù)信息。

文獻[6][7]研究了實時傳輸中的冗余問題，這些文章所采用的方法都是對傳輸?shù)倪^程進行了冗余消除，但是對于待傳輸?shù)臄?shù)據(jù)并沒有進行預(yù)先的處理，這就使得它們的冗余檢測和消除都無法完全徹底的消除冗余。

2 文件拆分和預(yù)測算法

各類平臺和網(wǎng)站在運行時都會生成大量的運行日志，其中都包含著珍貴的信息需要進行備份以便處理分析，在這個過程中不可避免的要面對傳輸這些大文件的問題。目前對于大數(shù)據(jù)的傳輸已經(jīng)有了一些工作，文獻[4] [1]都對于傳輸中冗余的數(shù)據(jù)進行了消除工作。

本文主要研究日志文件的傳輸效率問題，算法設(shè)計主要包括兩部分，第一部分是文件拆分算法，用來將要傳輸?shù)奈募M行拆分，拆分成數(shù)據(jù)文件和描述性信息文件，第二部分是傳輸過程中的冗余消除算法，目的是消除傳輸過程中的冗余，確保鏈路上傳輸盡可能少的數(shù)據(jù)。

2.1 文件拆分算法

日志文件是系統(tǒng)在運行時自動生成的用來描述系統(tǒng)工作狀態(tài)或記錄用戶使用系統(tǒng)情況的說明性文件，日志文件一般由數(shù)據(jù)和描述性信息構(gòu)成，其中數(shù)據(jù)是日志文件記錄的目標信息，而為了使文件便于管理人員查閱和分析，文件中就必須要包含描述性信息，這些信息主要用來解釋說明日志中數(shù)據(jù)的含義。因為文件是由系統(tǒng)自動生成，所以文件中會包含大量重復(fù)的描述性信息，我們稱之為冗余信息。對文件的壓縮主要目的是將文件中這些冗余信息都抽取出來壓縮成一個沒有冗余信息的描述文件，然后將原日志文件剩下部分組成數(shù)據(jù)文件，將傳輸?shù)奈募嚎s成數(shù)據(jù)文件和描述文件，從而也減少了傳輸量并且消除傳輸冗余。

為了找到日志文件中重復(fù)出現(xiàn)的冗余描述性信息，我們需要檢索整個日志文件并準確的發(fā)現(xiàn)哪些字符串是我們要找到冗余內(nèi)容。直接基于文件內(nèi)容的查找會涉及大量字符串的操作，這將使問題復(fù)雜化，并分散我們對文件壓縮的注意力，因此我們使用fingerprints來對文件進行一次預(yù)處理。

2.2 Fingerprints

Fingerprint是一個可以代表一段字符串的整數(shù)，它是通過對所要代表的字符串計算得到的，一個優(yōu)秀的計算方式計算得到的fingerprint應(yīng)該是可以唯一的標識一段字符串。而fingerprints就是一個fingerprint的集合，這個集合代表了一組字符串，它把字符串問題轉(zhuǎn)化成了整數(shù)問題，運用同樣的辦法，日志文件也可以被轉(zhuǎn)換成一個整數(shù)集合，這樣就能夠繞開所有的字符串處理問題，運用相對簡單的數(shù)字查找方式完成字符串處理工作。

Rabin提出利用“fingerprints”處理文件來防止文件被隨意篡改[8]。為了得到一個能夠標識整個文件的fingerprints集合，需要對文件中每一行的每一個β長度的字符串都獲取到它的fingerprint。

用t1t2… tβ來表示一段字符串，則這段字符串的第一個β位長度的子字符串的fingerprint為：

其中，p和M為常數(shù)，這樣在計算Fi時就可以使用：

p一般選擇素數(shù)，而M選擇2的n次冪（n為正整數(shù)），為了快速計算，可以計算出所有ASCII碼中字符的t×pβ的值并存儲在一個表中，這樣計算Fi只需要一次加法運算、一次減法運算還有一次乘法運算。

2.2.1 查找冗余信息

利用fingerprint就可以將日志文件轉(zhuǎn)化成整數(shù)的集合，對于要壓縮的日志文件file_log，讀取文件中每一段βbit度的子字符串按照。利用上述公式(1)計算出它的fingerprint，這個fingerprint即代表了這段字符串。例如對t1t2… tβtβ+1于這樣一個字符串，按照每β個字符串計算一個fingerprint，會生成兩個fingerprint整數(shù)：F1和F2，其中F1代表了字符串t1t2… tβ，而F_2代表了字符串t2… tβtβ+1。這樣file_ log文件中的一段字符串t1t2… tγ就能夠被表示成一個數(shù)列F1，F(xiàn)2，…，F(xiàn)α，我們規(guī)定如果γ<β則在計算時在tγ后面補0。一段字符串t1t2…tγ在日志文件如果是冗余信息，則數(shù)列F1，F(xiàn)2，…，F(xiàn)α也會被多次生成，我們把字符串t1t2…tγ叫做冗余句子，把冗余句子對應(yīng)數(shù)列F1，F(xiàn)2，…，F(xiàn)α叫做冗余數(shù)列。

這樣就把查找file_log文件中冗余句子的問題轉(zhuǎn)化為數(shù)列中查找每個數(shù)字出現(xiàn)頻率的問題了。我們利用文獻[9]中統(tǒng)計常見搭配的辦法來通過統(tǒng)計找到冗余信息。例如短信開放平臺在接收到一條短信之后，可能對產(chǎn)生這樣的日志：

Platform receives a short message from 139aaaabbbb to 10086 at 2013-01-01-01：02：03，message id is 2cadd3e1f70643bd8b7af60825c51573.

如果短信開放平臺每天接收到大量的這種短信時，就會產(chǎn)生同樣多的這樣的日志記錄。在這種記錄中，很明顯“Platform receives a short message from to at， message id is.”這樣的描述性信息是會重復(fù)出現(xiàn)的，也就是冗余信息。而2cadd3e1f70643bd8b7af 60825c51573、139aaaabbbb、10086、2013-01-01-01：02：03則是有價值的數(shù)據(jù)。冗余信息中的單詞的搭配是比較固定的，只是詞匯以固定的格式反復(fù)出現(xiàn)，而數(shù)據(jù)和描述性信息的搭配則是不固定的，在日志文件中，搭配出現(xiàn)的次數(shù)也不多。在對上面的日志例句進行分析時，我們定義一個搭配窗口來識別描述性信息，搭配窗口內(nèi)的一個詞的左右有4個詞，把窗口中每個詞對都作為候選的搭配對，如圖1所示。然后在整個日志文件中通過計算搭配對出現(xiàn)的頻率，就可以知道哪些是描述性信息了。

圖1 查找文件中的描述性信息

計算頻率是一個基本的數(shù)據(jù)結(jié)構(gòu)問題，可以有多種解決方法，本文利用哈希表進行處理。

下面是查找冗余信息的偽代碼。

Translation(){

while(run){

str = readFileLine()；

fingerPrints = getFingerPrinters(str)；

//fingerPrints同時也攜帶表示其在文中位置的指針

putInHashMap(fingerPrints)；

}

}

Statistic(){

fingerPrint = getFromHashMap()；

if(fingerPrint在HashMap中出現(xiàn)超過兩次){

//將這些相同的fingerPrint合并，包括他們的指針newFingerPrint = merge(fingerPrint)；

putInStatisticHashMap(newFingerPrint)；

}

}

Compress(){

//得到一組fingerPrint的集合fingerPrints fingerPrints = getFromStatisticHashMap()；if(fingerPrints是代表一段字符串的數(shù)列){

//這段字符串是冗余信息

putInRedundantHashMap(fingerPrints ， 指針信息)；

}

}

如上面的偽代碼所示，Translation()將日志文件中的所有字符串通過計算轉(zhuǎn)成了fingerprint數(shù)字，每個β長度的字符串利用公式(1)生成一個整數(shù)F。同時，為了能夠找到數(shù)字對應(yīng)的字符串在日志文件中的位置，對每一個F還要攜帶一個指針指向?qū)?yīng)字符串在文件中的位置。Statistic()按照字符串的順序排列所有生成的fingerprint，然后統(tǒng)計所有fingerprint重復(fù)的次數(shù)，記錄下重復(fù)次數(shù)大于2的fingerprint。在完成統(tǒng)計工作后，哈希表中已經(jīng)存放著所有代表冗余句子的fingerprint以及它所攜帶的指針。在很多情況下，冗余句子的長度大于計算fingerprint所用的字符串長度，所以在統(tǒng)計fingerprint時不能只計算單個的fingerprint，而是要記錄下代表這種長冗余句子的fingerprint數(shù)列，這也就是Compress()的主要工作，Compress()主要根據(jù)fingerprint所攜帶的指針來判斷哪些fingerprint是連續(xù)的，然后將它們合并，連同其指針信息一起保存到RedundantHashMap哈希表中，這樣就可以找到每一個代表長冗余句子的數(shù)列。

在經(jīng)過了上述步驟之后，RedundantHashMap哈希表中保存的就是所有代表日志文件中冗余句子的數(shù)列，以及這些冗余句子在日志文件中所在的位置。

2.2.2 消除冗余信息

經(jīng)過查找冗余信息的處理，在哈希表中保存著記錄日志文件file_log冗余信息的數(shù)據(jù)，消除冗余信息主要是根據(jù)這些數(shù)據(jù)將日志文件file_log拆分成兩個新的文件：存放描述性信息的文件file_description和存放數(shù)據(jù)的文件file_data。

生成的新文件file_description中存放的是冗余句子，這些句子通常都是描述性信息。為了標記這些句子在原日志文件中的位置，每一個冗余句子還要攜帶指向其在原文件file_log中所有出現(xiàn)位置的指針集合{location_Id}；日志文件file_log去除掉所有冗余句子的剩余內(nèi)容記錄在file_data中。

拆分的偽碼如下所示。

Split (){

fingerPrints = getRedundantHashMap ()；

//根據(jù)fingerPrints攜帶的指針將中的冗余信息抽取出來

//寫入到file_description中的，同時將指針信息也寫入進去；

file_description = abstractFile(file_log， fingerPrints)；

//將剩下的數(shù)據(jù)寫入到file_data文件中；

file_data = createDataFile(file_log， fingerPrints)；

}

2.3 傳輸過程中的冗余消除

在理想的情況下，被傳輸?shù)娜罩疚募?yīng)該只包含有數(shù)據(jù)部分，這樣傳輸數(shù)據(jù)的信息量才是100%，但在實際中顯然是無法達到這個目標的，所以就應(yīng)該使數(shù)據(jù)部分在傳輸總量中占得比重盡可能的大。

這樣就需要減少描述性信息文件file_description在傳輸總量中所占的比重，為此我們采用預(yù)測的方式減少file_description文件中的數(shù)據(jù)量。

因為描述信息是機器重復(fù)生成的，并不會隨著時間而發(fā)生改變，所以文件的接收端通常已經(jīng)擁有相當(dāng)充足的描述性信息，對于這些已經(jīng)存在于接收端的部分，發(fā)送端不會進行傳輸。由于file_description文件中的描述信息是通過fingerprint查找得到的，所以發(fā)送端依然可以利用fingerprint進行預(yù)測。

在生成file_description文件之后，描述性信息的fingerprints都保存在哈希表之中，發(fā)送端在傳輸文件之前，首先將哈希表中描述性信息的fingerprints生成文件file_description_fingerprints發(fā)送給接收端，接收端會對接收到的fingerprints與自己緩存中的描述性信息的fingerprints進行對比，將沒有緩存的fingerprints發(fā)回給發(fā)送方，而對已經(jīng)有緩存的fingerprints不再回應(yīng)。需要說明的是，為了減少網(wǎng)絡(luò)開銷，發(fā)送端并不需要發(fā)送全部的fingerprints，而只是選擇一些有代表性的fingerprints生成文件并發(fā)送給接收端。

發(fā)送方收到接收方對于預(yù)測的回應(yīng)之后就可以知道哪些描述性信息已經(jīng)不再需要發(fā)送。

圖2說明了每次預(yù)測的流程。

圖2 預(yù)測的流程圖

2.4 文件的拆解和合并

為了文件能在接收端順利合并，在文件拆分時在file_description中同時保存了指針。每一條描述性信息的指針指向其在file_data文件中的位置，在接收端進行文件合并時，將描述性信息填入指向的文件中位置即可。

在消除傳輸過程中的冗余時，對于接收端已經(jīng)有的描述性信息會依然保存它的指針信息，在接收端接收完成后，用接收端緩存的描述性信息和指針信息來回填file_data文件。

3 實驗

為了驗證算法的有效性，我們使用EBUPT公司移動云平臺運行時產(chǎn)生的日志文件進行測試，測試使用的計算機CPU為Intel(R) Core(TM)2 Duo CPU E7500 @2.93 GHz，內(nèi)存為1236 MB，測試的步驟如下：首先測試文件拆分算法對于日志文件冗余的處理程度以及對于文件的壓縮程度；然后測試文件傳輸時冗余消除的程度，因為對于file_description文件中在接收端已經(jīng)緩存部分已經(jīng)不再需要傳輸，所以要測試實際傳輸?shù)臄?shù)據(jù)量。

3.1 測試文件拆分算法

分別選取大小為2 MB、16 MB、80 MB的日志文件進行處理，進行拆分后的詳細情況如表1所示。

從表1可以看出，文件拆分算法不僅將原來的日志文件進行了拆分，還大大壓縮了文件的大小，其中file_ description文件的大小遠大于file_data文件，這是因為我們選取的日志是移動云平臺記錄客戶端與平臺連接情況的日志，日志中有效數(shù)據(jù)的含量相對很少。原文件大小為2.07 MB和80.4 MB的文件其大小比例為1：38.84，而其對應(yīng)的file_description文件的大小分別為204 KB和250 KB，大小比為1：1.23，這說明80.4 MB的文件中有很大的冗余信息，而拆分成file_ description之后，冗余信息都被表示文中位置信息的指針所代替。

3.2 測試文件傳輸時的冗余消除

在傳輸文件的時候，還需要進一步消除傳輸冗余，為此需要計算出file_description的fingerprints并記錄到文件file_description_ fingerprints中，將file_description_ fingerprints先發(fā)送到接收端進行比對，接收端將需要發(fā)送的文件部分的指針信息發(fā)送回來，發(fā)送端在根據(jù)此反饋信息發(fā)送消息。

所以，此處主要測試在這種前期的預(yù)測中數(shù)據(jù)的發(fā)送量。依然選取測試文件拆分算法時的日志樣本，測試顯示出了最佳預(yù)測結(jié)果和最壞預(yù)測結(jié)果：在最佳預(yù)測的情況下，file_description文件中的數(shù)據(jù)在接收端都已經(jīng)有緩存，接收端只會給發(fā)送端發(fā)送消息體為空的應(yīng)答消息；在最壞預(yù)測的情況下，file_description文件中的數(shù)據(jù)在接收端沒有任何緩存，接收端會把需要發(fā)送的文件部分的指針信息發(fā)送回給發(fā)送端。最佳和最壞情況下預(yù)測耗用的數(shù)據(jù)傳輸量如表2和表3所示。在表4中，在最佳預(yù)測的情況之下，原本表1中拆分后文件只需要更少的數(shù)據(jù)就能夠成功發(fā)送，例如204.21 KB的文件只需要33.21 KB就可以成功發(fā)送，預(yù)測使傳輸量減少到16.26%。只有在最壞情況之下，如表5所示，file_description文件才需要全部發(fā)送出去，這種情況下預(yù)測將使傳輸量大于沒有預(yù)測時的傳輸量。

表4和表5測試數(shù)據(jù)表示的是在預(yù)測的最佳情況和最壞情況下總共發(fā)送的數(shù)據(jù)量，包括前期預(yù)測時的數(shù)據(jù)量、預(yù)測后實際發(fā)送的file_description大小以及file_ data的大小。

由表6可以看出，在最好和最壞的情況下，本文所使用的算法策略都減少了文件的實際發(fā)送量，在最佳預(yù)測情況下可以比原文件少發(fā)送99.83%的數(shù)據(jù)，在最壞預(yù)測情況下也可以少發(fā)送99.15%的數(shù)據(jù)。

表1 文件拆分后大小

表2 文件預(yù)測在最佳情況下傳輸數(shù)據(jù)量

表3 文件預(yù)測在最壞情況下傳輸數(shù)據(jù)量

表4 最佳預(yù)測情況下系統(tǒng)數(shù)據(jù)總傳輸量及預(yù)測收益

表5 最壞預(yù)測情況下系統(tǒng)數(shù)據(jù)總傳輸量及預(yù)測收益

表6 本文采用的算法策略對消除冗余的效果

4 總結(jié)

本文旨在解決大數(shù)據(jù)傳輸領(lǐng)域的日志文件傳輸問題，通過對日志文件的收集和分析，我們發(fā)現(xiàn)日志一般由兩種數(shù)據(jù)構(gòu)成，一種是真實的數(shù)據(jù)，還有一部分是對數(shù)據(jù)進行解釋描述作用的描述性信息，而描述性信息通常是內(nèi)容固定且有冗余的，基于此理論，本文提出一種傳輸策略，一共有4個步驟：首先對文件進行拆分，拆分成包含描述性信息的file_description文件和包含數(shù)據(jù)的file_data文件，這個過程中消除了file_description文件中的冗余信息；接著與接收端通信確定哪些數(shù)據(jù)在接收端已經(jīng)有緩存；然后將接收端已經(jīng)緩存的信息從待發(fā)送的文件中去除；最后將消除了冗余的文件發(fā)送出去。

為了查找文件中的冗余信息，本文采用了文獻[5]提到的辦法將文件中每一個子字符串通過計算用一個整數(shù)來替代，將字符串操作轉(zhuǎn)化為對整數(shù)的操作，再通過哈希表完成了冗余信息的查找。

在傳輸階段，發(fā)送端通過預(yù)測的方式減少冗余信息，具體做法是發(fā)送端對拆分后生成的file_description文件計算出它的fingerprints，接著對這些fingerprints生成一個文件file_description_fingerprints并把它發(fā)送給文件接收端，接收端通過與自己緩存的file_description文件進行分析比對，向發(fā)送端做出應(yīng)答，發(fā)送端通過分析應(yīng)答后決定實際發(fā)送的file_description內(nèi)容。

通過實驗，可以看到通過文件的拆分算法，能夠讓文件大小減少90%以上，通過傳輸前的預(yù)測，能夠讓實際傳輸?shù)臄?shù)據(jù)量小于拆分后的文件大小。相對于直接發(fā)送原日志文件，本文采取的一系列策略能夠讓數(shù)據(jù)傳輸量減少到10%左右，或者更低。

本文的后續(xù)工作主要是更精確的找到冗余信息，目前的方式是通過判斷fingerprints是否重復(fù)出現(xiàn)，這種方式生成的file_description文件雖然很大程度消除了冗余信息，但是會在file_description文件中又出現(xiàn)新的冗余，這應(yīng)該在下一步的工作當(dāng)中得到解決。

參考文獻

[1] Zohar E， Cidon I， Mokryn O. The power of prediction： cloud bandwidth and cost reduction[A]. Proc of SIGCOMM[C]. 11，2011，volume 41 issue 4， pages 86-97.

[2] Laoutaris N， Sirivianos M， Yang X Y， Rodriguez P. Inter-datacenter bulk transfers with NetStitcher[A]. Proc of SIGCOMM[C]. 11， 2011，volume 41 issue 4，pages 74-85.

[3] Cormen T H， Leiserson C E， Rivest R L， Stein C. Introduction to Algorithms[M]. MIT Press’01

[4] Spring N T. Wetherall D. A protocol-independent technique for eliminating redundant network traffic[A]. Proc of SIGCOMM[C]. 00，2000， volume 30， 87-95.

[5] Manber U. Finding similar files in a large file system[A]. Proc of the USENIX winter Technical Conference， 1994， 1-10.

[6] Gupta A， Akella A， Seshan S， Shenker S， Wang J. Understanding and Exploiting Network Traffic Redundancy[R]. Univ of Wisconsin-Madison， Technical Report 1592， April 2007.

[7] Zink M， Suh K， Gu Y， Kurose J. Watch G. cache local：YouTube network traffic at a campus network -measurements and implications[A]. Proc of MMCN[C]， 2008.

[8] Rabin M O. fingerprinting by Random Polynomials[R]. Center for Research in Computing Technology， Harvard University， Technical Report TR-15-81， 1981.

[9] Christopher D. Manning， Hinrich Schütze， Foundations of Statistical Natural Language Processing[M]. MIT Press’99.

News

歐勝全新Ez2軟件解決方案可為移動設(shè)備免提和視頻通話提供超凡的揚聲器品質(zhì)

歐勝微電子有限公司日前宣布：將最新的軟件解決方案Ez2 grouptalk和Ez2 facetalk引入其Ez2軟件功能集。這些軟件是專為配合諸如WM5110高清晰度音頻中樞等歐勝現(xiàn)有的硬件平臺而設(shè)計，以極大地改善智能手機、平板電腦、個人電腦和電視機等設(shè)備在進行移動免提通話、網(wǎng)絡(luò)電話和視頻通話時的揚聲器質(zhì)量，并面向日益增長的移動辦公會議電話市場。

歐勝的Ez2 grouptalk提供了一種可在智能手機和平板電腦上實現(xiàn)的卓越的免提揚聲器電話通話體驗，這種體驗以前只能在桌面會議電話設(shè)備中實現(xiàn)。無論是一對一話音通話還是多人話音通話，Ez2 grouptalk軟件可確保在免提通話模式下，在離設(shè)備遠達5m的范圍內(nèi)的發(fā)言在遠端聽起來都同樣清晰，同時他們的聲音將能夠被清晰地捕獲。在多人話音通話的情況下，比如說一次電話會議中，由于帶有聲學(xué)回音消除、噪聲抑制和聲學(xué)增益控制，可以在通話中的任何時刻幫助跟蹤最強的發(fā)言人聲音，而不必擔(dān)心外部環(huán)境噪聲，從而帶來高品質(zhì)、清晰的對話。

Journal file transmission algorithm based file splitting and buffer memory prediction

MA Sai-mu1,2, WANG Jing1,2
(1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2 EBUPT Information Technology Co., Ltd., Beijing 100083, China)

As networks and transmission are becoming increasingly important for computational science, we are working on proposing a journal fi le transmission algorithm. This new algorithm focusing on optimizing the performance of journal file transmission is independent of transport protocols. Our approach includes two components: the file splitting and buffer memory prediction. The file splitting performs fi le compression and redundancy elimination, and the buffer memory prediction avoids transferring the redundant data. Experimental results verify that the journal fi le transmission algorithm can effectively eliminate the redundancy in the journal fi le and reduce the amount of data transmission by 9.0%.

fi le transmission; fi ngerprint; redundancy elimination; cloud computing

TP393

A

1008-5599（2013）08-0071-08

2013-07-16

國家973計劃項目（No. 2013CB329100， 2013CB329102）；國家自然科學(xué)基金（No. 61271019， 61101119， 61121001， 61072057，60902051）；長江學(xué)者和創(chuàng)新團隊發(fā)展計劃資助（No. IRT1049）。