王周愷，張 炯，馬維綱，王懷軍

（西安理工大學(xué)計算機科學(xué)與工程學(xué)院，西安 710048）

（*通信作者電子郵箱zkwang@xaut.edu.cn）

0 引言

為保證高速列車安全、有效地運行，需要在列車運行過程中利用各種傳感器，通過鐵路綜合數(shù)字移動通信系統(tǒng)（Global System for Mobile Communications-Railway，GSM-R），對列車的運行時各部件的狀態(tài)進(jìn)行監(jiān)測［1］。遵照4 級中國列車控制系統(tǒng)（Chinese Train Control System-4，CTCS-4）的設(shè)計要求，各類車載傳感器在列車運行時，收集列車車廂及關(guān)鍵部件的實時數(shù)據(jù)狀況，包括速度、功率、風(fēng)力、濕度等；再采用變長編碼技術(shù)（Variable Length Coding，VLC）對收集的數(shù)據(jù)進(jìn)行壓縮，最后將壓縮數(shù)據(jù)通過GSM-R 傳輸并存儲于控制中心；相應(yīng)地，工作人員如果需要分析列車狀態(tài)，則先對數(shù)據(jù)進(jìn)行解壓縮，在此基礎(chǔ)上，再對解壓縮結(jié)果進(jìn)行分析，從而發(fā)現(xiàn)列車運行中可能產(chǎn)生的故障問題，并及時修復(fù)故障，避免潛在風(fēng)險的發(fā)生［2］。

然而，由于采用了變長編碼技術(shù)壓縮數(shù)據(jù)，針對高速列車監(jiān)測數(shù)據(jù)的分析效率通常較低，這是因為采用變長編碼技術(shù)的數(shù)據(jù)壓縮方法通常先將數(shù)據(jù)進(jìn)行等長劃分，再將劃分結(jié)果按照頻次排序并利用哈夫曼樹進(jìn)行編碼，從而獲得更高的壓縮比［3］；但這種利用變長編碼技術(shù)壓縮的數(shù)據(jù)由大小不同的數(shù)據(jù)塊組成，且塊間邊界難以確定。所以目前針對此類數(shù)據(jù)的解壓縮方法通常是從數(shù)據(jù)的起始位置開始，按照各數(shù)據(jù)塊的組成順序，從頭到尾依次對數(shù)據(jù)進(jìn)行逐塊解壓縮［4］。而這樣的串行解壓縮過程亦無法被并行化，因為在當(dāng)前數(shù)據(jù)塊未解壓縮之前，其后續(xù)數(shù)據(jù)塊的起始位置無法得知，因此，當(dāng)前針對高速列車監(jiān)測數(shù)據(jù)的分析過程受變長編碼解壓縮算法的影響，效率較低［5］，難以滿足在春運等高負(fù)荷環(huán)境下對海量監(jiān)測數(shù)據(jù)及時處理的需求［6］。

為解決傳統(tǒng)串行解壓縮算法無法高效處理高速監(jiān)測數(shù)據(jù)的解壓縮問題，基于針對變長編碼壓縮數(shù)據(jù)的結(jié)構(gòu)研究，本文以多核領(lǐng)域常用的推測并行技術(shù)作為手段，提出一種面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法。該方法使用推測手段消解壓縮數(shù)據(jù)的組成順序?qū)鈮嚎s算法執(zhí)行流程的影響，使壓縮數(shù)據(jù)的處理過程得以并行化；然后在通用大數(shù)據(jù)分析引擎Apache Spark 上實現(xiàn)并行流程，借助分布式計算框架提供的強大算力，極大地縮短數(shù)據(jù)解壓縮需要的時間，為高速列車監(jiān)測數(shù)據(jù)的解壓縮提供高效可靠的新方法，從而進(jìn)一步縮短針對高速列車監(jiān)測數(shù)據(jù)的分析時間，提高針對高速列車監(jiān)測數(shù)據(jù)的處理效率。

1 動機

為保證高速列車的安全、穩(wěn)定運行，按照CTCS-4 列控系統(tǒng)設(shè)計要求，列車在車廂內(nèi)部和各個關(guān)鍵部件處安裝不同類型的傳感器，實時監(jiān)控運行狀態(tài)［7］：例如，大量溫度傳感器遍布車廂和車體、監(jiān)控變壓器以及驅(qū)動軸、定子轉(zhuǎn)軸、齒輪等關(guān)鍵部位，實時測量其溫度；安裝在車軸部位速度傳感器實時監(jiān)測列車運行時速和車軸轉(zhuǎn)速；空氣制動力、風(fēng)管壓力、連接端車牽引力等由車廂外部的測力傳感器收集；而中間電壓、牽引變流器功率、電制動功率、區(qū)域控制單元電壓等信息的記錄由各式復(fù)雜的電壓、電流傳感器負(fù)責(zé)。這些傳感器以每秒一次的采集頻率記錄列車運行時各部件的狀態(tài)，并通過列車內(nèi)部的有線傳輸系統(tǒng)，將采集數(shù)據(jù)傳送給車載安全計算機（或稱歐洲安全計算機（European Vital Computer，EVC）），計算機對傳感數(shù)據(jù)進(jìn)行整理，以日志文件的形式存儲于車載機柜的硬盤中。在達(dá)到一定數(shù)據(jù)量后，對日志文件進(jìn)行壓縮，再通過GSM-R網(wǎng)絡(luò)提供的通信網(wǎng)絡(luò)將壓縮數(shù)據(jù)傳輸給列車控制中心（Train Control Center，TCC）；最后，TCC將壓縮數(shù)據(jù)分類整理，存入分布式數(shù)據(jù)庫HDFS（Hadoop Distributed File System）中。當(dāng)需要對列車監(jiān)測數(shù)據(jù)進(jìn)行分析時，后臺工作人員從HDFS中取出數(shù)據(jù)并進(jìn)行解壓縮，再對解壓縮結(jié)果進(jìn)行分析，進(jìn)而對列車狀態(tài)進(jìn)行判斷［8］。

高速列車監(jiān)測數(shù)據(jù)具有如下特點：數(shù)據(jù)按時間序列采集；數(shù)據(jù)類型為雙精度浮點型；相鄰數(shù)據(jù)間差距較??；部分?jǐn)?shù)據(jù)內(nèi)容可為空；監(jiān)測數(shù)據(jù)種類較多；數(shù)據(jù)量巨大［9］；此外，收集的監(jiān)測數(shù)據(jù)還需要進(jìn)行傳輸和保存。綜上所述，為保證監(jiān)測數(shù)據(jù)的有效存儲和安全傳輸，需要將由監(jiān)測數(shù)據(jù)構(gòu)成的日志文件進(jìn)行壓縮。目前針對監(jiān)測數(shù)據(jù)的壓縮常采用動態(tài)哈夫曼編碼（Dynamic Huffman Coding）技術(shù)［10］實現(xiàn)，這種壓縮數(shù)據(jù)由一系列不等長的數(shù)據(jù)塊組成，如圖1 所示。每個數(shù)據(jù)塊包括塊頭標(biāo)號、動態(tài)哈夫曼樹、壓縮內(nèi)容以及塊尾標(biāo)號。其中：塊頭標(biāo)號用以描述當(dāng)前壓縮數(shù)據(jù)塊的特性；動態(tài)哈夫曼樹是數(shù)據(jù)壓縮和解壓縮的依據(jù)；壓縮內(nèi)容存儲了使用動態(tài)哈夫曼樹壓縮數(shù)據(jù)后的結(jié)果；塊尾標(biāo)號由一串特定字符組成，用以標(biāo)識壓縮數(shù)據(jù)塊的結(jié)束。

針對這類數(shù)據(jù)，傳統(tǒng)的解壓縮流程從監(jiān)測數(shù)據(jù)的起始位置開始，按照數(shù)據(jù)塊的組成順序，利用動態(tài)哈夫曼樹，逐塊對其中的壓縮內(nèi)容進(jìn)行還原，通常效率較低。算法1和圖2分別展示了變長解壓縮算法的偽代碼和相應(yīng)的依賴關(guān)系分析圖。從算法1 可知，傳統(tǒng)算法的每一輪循環(huán)解壓一個完整的數(shù)據(jù)塊；當(dāng)一個數(shù)據(jù)塊被解壓完后，表示位置信息的pos 更新，指導(dǎo)下一個數(shù)據(jù)塊的解壓縮。如圖2 所示，該解壓縮算法共包含三條依賴：由變量eof引發(fā)的控制依賴、由內(nèi)部循環(huán)中的pos引發(fā)的數(shù)據(jù)依賴，以及由out_stream 變量引發(fā)的數(shù)據(jù)依賴。這些依賴關(guān)系共同作用，阻礙了多重循環(huán)的并行執(zhí)行。在數(shù)據(jù)量特別大的情況下，輸入數(shù)據(jù)中包含大量的數(shù)據(jù)塊，因此由pos所引起的數(shù)據(jù)依賴是影響算法并行執(zhí)行的最大因素。

為提升針對變長編碼壓縮數(shù)據(jù)解壓縮效率，目前主流的解決思路是采用軟硬件協(xié)同的方法，通過加速單個數(shù)據(jù)塊的處理過程，提高針對變長編碼壓縮數(shù)據(jù)的整體壓縮效率。例如將傳統(tǒng)解壓縮算法移植到圖形處理器上，通過任務(wù)分解和統(tǒng)一計算設(shè)備架構(gòu)（Compute Unified Device Architecture，CUDA）提升算法效率［11-12］。此外還有運用大數(shù)據(jù)計算引擎，設(shè)計基于分布式平臺的數(shù)據(jù)解壓縮算法［13-14］。但此類方法的思路主要聚焦于并行化哈夫曼樹還原壓縮內(nèi)容的過程，并使用大量計算資源對該過程進(jìn)行加速，通常效果不佳。從對算法運行機制的深層次分析可知，這些優(yōu)化方法只能縮短單個數(shù)據(jù)塊的處理時間，而數(shù)據(jù)解壓的整體過程仍然是按照壓縮數(shù)據(jù)的組成順序串行進(jìn)行的。如圖2 所示，若不能消解算法中的數(shù)據(jù)依賴對執(zhí)行順序的影響，從根本上將串行解壓縮的過程并行化，則對解壓縮算法的性能優(yōu)化效果有限［15］。

圖2 傳統(tǒng)變長解壓縮算法的偽代碼和依賴關(guān)系圖Fig.2 Pseudo codes and dependence relationship diagram of conventional variable-length decompression algorithm

要從根本上提升數(shù)據(jù)解壓縮算法的并行度，需要在解壓縮之前，將壓縮數(shù)據(jù)劃分成一系列可以被獨立解壓縮的數(shù)據(jù)塊的組合，再同時解壓縮這些數(shù)據(jù)塊，從而使數(shù)據(jù)解壓縮過程并行化。但由于變長編碼技術(shù)的影響，數(shù)據(jù)塊間的邊界在解壓縮前通常難以確定，隨意劃分可能會造成對壓縮數(shù)據(jù)塊完整性的破壞；而數(shù)據(jù)塊內(nèi)部的任何部分都存在與壓縮內(nèi)容重復(fù)的可能性，因此也不具備作為劃分?jǐn)?shù)據(jù)塊邊界的功能。

針對上述困難，本文以推測技術(shù)為手段，實現(xiàn)高速列車監(jiān)測數(shù)據(jù)的并行解壓縮。首先，以壓縮數(shù)據(jù)的塊尾標(biāo)號作為劃分?jǐn)?shù)據(jù)塊邊界的依據(jù)，假定不存在壓縮內(nèi)容與塊尾標(biāo)號重復(fù)的情況，對數(shù)據(jù)進(jìn)行嘗試性劃分；然后設(shè)計推測校驗方法，消除錯誤劃分的影響，再將劃分結(jié)果進(jìn)行推測性的并行處理；最終將并行處理結(jié)果合并。通過這種方式并行化原本串行的數(shù)據(jù)解壓縮過程，從而提升變長壓縮數(shù)據(jù)的解壓縮效率。

2 算法設(shè)計

基于上述對存在問題和解決思路的描述，面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法設(shè)計如下：算法被分為推測劃分、推測檢驗、并行解壓縮和結(jié)果合并四個部分。

2.1 推測劃分

作為算法的第一部分，推測劃分的目的是在數(shù)據(jù)解壓縮之前，盡可能地將壓縮數(shù)據(jù)劃分成獨立完整的數(shù)據(jù)塊，使這些數(shù)據(jù)塊可以不依賴于先前數(shù)據(jù)塊所提供的位置信息而被獨立處理。為達(dá)成該目的，需要確定推測劃分的依據(jù)和粒度。

首先，推測劃分的依據(jù)按照如下方法確定。在變長壓縮數(shù)據(jù)內(nèi)部，數(shù)據(jù)塊由四部分組成，其中動態(tài)哈夫曼樹和塊尾標(biāo)號的內(nèi)容固定不變，其他部分會隨著壓縮內(nèi)容的不同而變化［15］，因此，首選動態(tài)哈夫曼樹或塊尾標(biāo)號作為推測劃分的依據(jù)；又因為塊尾標(biāo)號由動態(tài)哈夫曼樹編碼表中最長的編碼構(gòu)成，其長度通常小于壓縮數(shù)據(jù)塊中的動態(tài)哈夫曼樹，更容易被識別和提?。?6］。綜上原因，在算法設(shè)計中，擬選取塊尾標(biāo)號作為依據(jù)，對壓縮數(shù)據(jù)進(jìn)行推測性地劃分。

確定劃分依據(jù)的基礎(chǔ)上，再確定推測劃分的粒度。一般來說，針對數(shù)據(jù)的劃分粒度太細(xì)密，會使得劃分工作變得非常繁瑣，影響后期并行解壓縮任務(wù)的數(shù)量，使派生并行解壓縮任務(wù)的工作量陡增，影響算法的整體性能表現(xiàn)；但如果將數(shù)據(jù)劃分得過大，又會導(dǎo)致劃分?jǐn)?shù)據(jù)的傳輸和并行處理成本增加，也會影響到整體的性能［17］。因此，數(shù)據(jù)的劃分粒度是影響到算法效率的重要因素。

為了確定劃分粒度，需要建立其與算法運行時間的理論模型。假設(shè)在推測并行解壓縮算法中，單個并行解壓縮任務(wù)的執(zhí)行時間F相等，則算法總耗時T如式（1）所示，總耗時T由并行任務(wù)的派生耗時和執(zhí)行耗時組成，其中λi為單個并行任務(wù)派生耗時，M表示任務(wù)總量，C表示分布式集群中工作節(jié)點數(shù)量。

此外，由于數(shù)據(jù)塊劃分?jǐn)?shù)量M與壓縮數(shù)據(jù)總大小E、劃分粒度H程反比，故M=。如果假設(shè)每個并行任務(wù)的派生耗時λi近似，則有=M×λ，用該式對式（1）中的M和λ進(jìn)行替換，可得算法耗時T與劃分粒度H及單個并行任務(wù)的執(zhí)行時間F的關(guān)系如式（2）所示：

其中：E為壓縮數(shù)據(jù)總大小，λ為單個任務(wù)派生耗時，μ為算法執(zhí)行時間系數(shù)，C為節(jié)點數(shù)，且這幾個均為常量。因此式（3）可以表示為劃分粒度H與算法耗時T的關(guān)系，其函數(shù)圖像如圖3所示。

圖3 推測劃分粒度與算法耗時函數(shù)關(guān)系圖Fig.3 Relationship between speculative division granularity and algorithm running time

從實際情況出發(fā)，劃分粒度應(yīng)滿足條件H>0，故選取第一象限進(jìn)行分析。觀察函數(shù)圖像可知，當(dāng)劃分粒度H趨近于0時，分塊數(shù)量趨近于+∞，會導(dǎo)致任務(wù)分派節(jié)點的負(fù)載過大，派生任務(wù)耗時所占比重不斷增加，進(jìn)而影響算法效率。

為使算法耗時最短，需對式（3）進(jìn)行求導(dǎo)，并令導(dǎo)數(shù)為0，易知當(dāng)劃分粒度H滿足式（4）時，使T取得極小值。

綜上分析，式（4）即為確定推測劃分粒度的數(shù)學(xué)模型，通過該模型可以確定當(dāng)H滿足條件時，算法執(zhí)行時間最短。

針對采用變長編碼的壓縮數(shù)據(jù)，其數(shù)據(jù)大小E、集群節(jié)點C和任務(wù)派生平均時間λ可以在算法執(zhí)行前得知；而μ的取值依賴于輸入數(shù)據(jù)類型，一般取均值31 250［16］。經(jīng)過計算，可得H為29 MB。最后，為了使劃分粒度數(shù)值快速收斂，一般選取大于H且滿足2的n次冪的最小值。最終，在推測并行解壓縮算法中，將推測劃分粒度確定為32 MB。

在確定劃分依據(jù)和粒度的基礎(chǔ)上，算法以輸入數(shù)據(jù)中首個數(shù)據(jù)塊的塊尾標(biāo)號為依據(jù)，以32 MB 為最短步長，逐字節(jié)地掃描輸入數(shù)據(jù)，以確定推測劃分點，如圖4 所示，對數(shù)據(jù)進(jìn)行初步的推測劃分。然而由于該劃分策略是以推測技術(shù)為基礎(chǔ)，因此存在因數(shù)據(jù)巧合，出現(xiàn)壓縮內(nèi)容與塊尾標(biāo)號相同而被認(rèn)為誤認(rèn)為是劃分點的情況，所以在推測劃分結(jié)束后，需要對推測劃分結(jié)果進(jìn)行檢驗，以確保劃分結(jié)果的正確性。

圖4 推測劃分過程示意圖Fig.4 Schematic diagram of speculative division

2.2 推測檢驗

由于通過推測所獲得的數(shù)據(jù)劃分點并不能保證數(shù)據(jù)塊的完整性，因此需要對推測劃分結(jié)果進(jìn)行驗證。參考其他基于變長編碼的并行數(shù)據(jù)壓縮方法［18］，本文算法提出頭校驗、哈夫曼樹重建和數(shù)據(jù)長度校驗三種檢驗手段，通過這三種檢驗手段的結(jié)合，檢測劃分結(jié)果是否正確。

頭校驗是指檢驗劃分結(jié)果的前3 位是否遵循塊頭標(biāo)號的編碼規(guī)則。一般來說，壓縮數(shù)據(jù)塊的前3 位只能是010 或000，分別代表該壓縮數(shù)據(jù)塊是遵循動態(tài)編碼標(biāo)準(zhǔn)的壓縮數(shù)據(jù)塊或是未被壓縮的非壓縮數(shù)據(jù)塊，如果劃分結(jié)果的前3 位不是010或000，則該劃分為錯誤劃分。

結(jié)束頭校驗后，根據(jù)頭校驗的結(jié)果，繼續(xù)對劃分結(jié)果進(jìn)行檢驗，即哈夫曼樹重建和數(shù)據(jù)長度校驗。哈夫曼樹重建是指當(dāng)劃分?jǐn)?shù)據(jù)的前3位為010時，代表當(dāng)前劃分結(jié)果可能是以壓縮數(shù)據(jù)塊開頭的一組數(shù)據(jù)，此時可以通過利用010 后的數(shù)據(jù)進(jìn)行動態(tài)哈夫曼樹的重建來判斷：如果無法重建動態(tài)哈夫曼樹，則該劃分為錯誤劃分。數(shù)據(jù)長度校驗是指當(dāng)劃分?jǐn)?shù)據(jù)的前3位為000時，代表當(dāng)前劃分結(jié)果可能是以非壓縮數(shù)據(jù)塊開頭的一組數(shù)據(jù)，因此需要對非壓縮數(shù)據(jù)塊的長度進(jìn)行判斷：在采用變長編碼的壓縮數(shù)據(jù)中規(guī)定，非壓縮數(shù)據(jù)塊的長度不能超過16 KB［19］。因此，如果從000后到下一個塊頭標(biāo)號之間的字段長度超過16 KB，則該劃分為錯誤劃分，反之則為正確劃分。

為詳細(xì)解釋推測檢驗原理，圖5 詳細(xì)模擬了該過程。在某段高速列車監(jiān)測數(shù)據(jù)中，壓縮數(shù)據(jù)的塊尾標(biāo)號為10111111，用塊尾標(biāo)號將壓縮數(shù)據(jù)劃分為四組后，對四組數(shù)據(jù)的推測檢驗過程如下：首先進(jìn)行頭校驗，由圖5可知，第3組數(shù)據(jù)劃分的開頭011 不符合壓縮數(shù)據(jù)塊的標(biāo)準(zhǔn)頭格式，因此未能通過頭校驗，該劃分錯誤。其余三組劃分?jǐn)?shù)據(jù)根據(jù)頭校驗結(jié)果的不同，繼續(xù)進(jìn)行后續(xù)校驗：在對開頭為010 的劃分結(jié)果進(jìn)行哈夫曼樹重建的過程中發(fā)現(xiàn)，第2 組劃分?jǐn)?shù)據(jù)無法重建哈夫曼樹，因此未能通過校驗，該劃分錯誤；最后針對開頭為000 的劃分結(jié)果進(jìn)行數(shù)據(jù)長度校驗，亦未能通過，該劃分錯誤。至此，只有第1 組數(shù)據(jù)劃分結(jié)果通過所有校驗，說明其為正確劃分，通過該劃分點將原始壓縮數(shù)據(jù)劃分后，前后兩部分劃分內(nèi)容均可被獨立處理。

圖5 推測劃分檢驗示意圖Fig.5 Schematic diagram of speculative division evaluation

經(jīng)過對推測劃分?jǐn)?shù)據(jù)的檢驗后，通過檢驗的劃分依據(jù)才能真正將壓縮數(shù)據(jù)劃分成可獨立處理的數(shù)據(jù)分塊。再用這些通過檢驗的劃分依據(jù)對壓縮數(shù)據(jù)進(jìn)行二次劃分，這樣的劃分結(jié)果可以保證被獨立解壓縮，進(jìn)而被用于并行解壓縮。待二次劃分結(jié)束，算法進(jìn)入并行解壓縮階段。

2.3 并行解壓縮

并行解壓縮是算法的第三階段，該階段的目的是并行處理經(jīng)過推測劃分和推測檢驗的數(shù)據(jù)塊集合。在該階段，首先將經(jīng)過二次劃分的數(shù)據(jù)塊集合傳輸?shù)椒植际接嬎憧蚣艿母饔嬎愎?jié)點中，同時設(shè)置相應(yīng)的資源調(diào)度策略，以保證分布式計算框架能提供充足的算力，支持所有數(shù)據(jù)塊的并行處理。在數(shù)據(jù)傳輸和資源調(diào)度之后，由主節(jié)點根據(jù)推測劃分塊的數(shù)量，派生相應(yīng)數(shù)量的并行任務(wù)，同時對所有的分塊進(jìn)行解壓縮。在該過程中，所有工作節(jié)點執(zhí)行的任務(wù)內(nèi)容相同，而處理的數(shù)據(jù)不同，每個節(jié)點內(nèi)部的具體執(zhí)行內(nèi)容如算法2所示。

在并行解壓縮階段，分布式計算框架中的每個計算節(jié)點以動態(tài)哈夫曼樹為參考，解壓縮數(shù)據(jù)。具體流程是在讀入編碼數(shù)據(jù)時，按位逐個遍歷哈夫曼樹，得到的葉子節(jié)點信息即為該編碼數(shù)據(jù)的解壓縮結(jié)果。重復(fù)這個過程直到遇到塊尾標(biāo)號，再將所有遍歷結(jié)果收集整合，得到壓縮數(shù)據(jù)的解壓縮結(jié)果。重復(fù)上述全部過程，直到經(jīng)過推測劃分的數(shù)據(jù)全部被解壓縮，最終將全部解壓縮結(jié)果按順序合并，從而得到并行解壓縮的其中一部分執(zhí)行結(jié)果。

2.4 結(jié)果合并

當(dāng)分布式計算框架中的所有節(jié)點完成解壓縮任務(wù)后，算法進(jìn)入結(jié)果合并階段，該階段由兩部分組成：解壓縮結(jié)果合并和出錯處理。具體來說，如果所有節(jié)點的并行解壓縮任務(wù)均順利完成，那么這些結(jié)果將被匯總至分布式計算框架的主節(jié)點中，并按照輸出數(shù)據(jù)的組織格式，順序合并解壓縮結(jié)果，形成并行解壓縮的輸出；如果解壓縮過程出現(xiàn)問題，解壓縮出錯的節(jié)點需要上報錯誤信息給主節(jié)點，主節(jié)點則記錄出錯節(jié)點的位置，保存出錯節(jié)點之前的所有解壓縮結(jié)果，并拋棄出錯節(jié)點之后所有的解壓縮結(jié)果，將數(shù)據(jù)回滾，再重新對出錯節(jié)點之后的所有數(shù)據(jù)按順序用傳統(tǒng)的數(shù)據(jù)解壓縮算法重新解壓縮，以保證最終輸出結(jié)果的正確性。

3 算法實現(xiàn)

本文提出的算法通過推測劃分?jǐn)?shù)據(jù)再并行處理的方式，使原本按照壓縮順序串行處理的高速列車監(jiān)測數(shù)據(jù)可以通過推測的方式并行處理，同時通過推測校驗和結(jié)果合并機制保證推測執(zhí)行結(jié)果的正確性，使算法兼具高效性和穩(wěn)定性。為了詳細(xì)描述算法，將選取高速列車實際運行數(shù)據(jù)作為研究對象，以Apache Spark為實現(xiàn)平臺，對算法流程進(jìn)行介紹。

研究對象數(shù)據(jù)選自2019 年4 月11 日西成高鐵成都東至西安北的D1912 次列車所產(chǎn)生的監(jiān)測數(shù)據(jù)，該列車采用8 輛編組，監(jiān)測數(shù)據(jù)由CRH380BL車型的傳感器產(chǎn)生，數(shù)據(jù)量約為19 GB，采用Zlib 編碼標(biāo)準(zhǔn)進(jìn)行壓縮。表示算法在Apache Spark 上的執(zhí)行流程的有向無環(huán)圖（Directed Acyclic Graph，DAG）如圖6～7所示：Apache Spark的主控制節(jié)點（以下簡稱主節(jié)點）從分布式數(shù)據(jù)庫中讀入監(jiān)測數(shù)據(jù)，形成彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets，RDD），并將監(jiān)測數(shù)據(jù)存儲為鍵值對的形式，其中鍵表示數(shù)據(jù)分塊的順序，值表示監(jiān)測數(shù)據(jù)的二進(jìn)制代碼片段。

圖6 推測并行算法執(zhí)行的有向無環(huán)圖1Fig.6 Directed acyclic graph 1 executed by speculative parallelism algorithm

按照算法設(shè)計，第一步為獲取劃分依據(jù)：指導(dǎo)集群中某單個工作節(jié)點解壓縮監(jiān)測數(shù)據(jù)RDD1 中的首個壓縮數(shù)據(jù)塊，解析動態(tài)哈夫曼樹，獲取塊尾標(biāo)號（在本示例中的值為10111），形成RDD2，接著對RDD1 進(jìn)行持久化操作（圖6 中的虛線部分），該操作的目的是備份RDD1，供推測檢驗結(jié)束后正確劃分結(jié)果指導(dǎo)監(jiān)測數(shù)據(jù)的重新劃分。

第二步為推測劃分，即使用塊尾標(biāo)號RDD2，對RDD1 中的所有元素進(jìn)行并行劃分，具體流程是以RDD2 中塊尾標(biāo)號為依據(jù)，按照32 MB 步長，對監(jiān)測數(shù)據(jù)RDD1 中所有分片同時執(zhí)行如圖4 所示過程的劃分，最終結(jié)果形成RDD3。在圖6中，RDD1 經(jīng)RDD2 劃分后形成由M個分塊組成的RDD3，在RDD3 內(nèi)部，鍵值對與RDD1 的組成略有不同：鍵仍然表示分塊順序，值變?yōu)樵M形式，其中，元組的首個元素代表劃分位置相對于監(jiān)測數(shù)據(jù)起始位置的偏移量，第二個元素代表劃分結(jié)果。

第三步為推測檢驗，該流程類似圖5 過程，即同時展開對RDD3 中包含劃分結(jié)果的頭校驗、哈夫曼樹重建和數(shù)據(jù)長度校驗工作，并在檢驗結(jié)束后，形成由P個分塊（P≤M）組成的推測檢驗結(jié)果RDD4，其內(nèi)部數(shù)據(jù)組成形式與RDD3相同。

第四步，使用經(jīng)過推測檢驗的RDD4 中所蘊含的偏移量，對RDD1 進(jìn)行并行重劃分，過程類似于推測劃分，最終形成RDD5，在RDD5 的每個分塊中，值代表經(jīng)過重新劃分，并可被獨立處理的二進(jìn)制代碼片段。待重新劃分結(jié)束，結(jié)果被繼續(xù)存于各工作節(jié)點的本地空間，等待后續(xù)并行處理，推測檢驗階段結(jié)束。

第五步為并行解壓縮。如圖7 所示，在該過程中，RDD5中的所有數(shù)據(jù)分塊將遵照算法2 的流程同時進(jìn)行解壓縮，并行解壓縮的結(jié)果將形成RDD6；待并行解壓縮結(jié)束，再將結(jié)果合并，具體過程如下：所有RDD6 中的數(shù)據(jù)由各工作節(jié)點回傳至主節(jié)點，再由主節(jié)點按照RDD6 中鍵值對的排列順序，依據(jù)規(guī)定輸出結(jié)果的文件格式類型，對所有結(jié)果按順序進(jìn)行合并，形成RDD7，最后將合并結(jié)果RDD7存回分布式數(shù)據(jù)庫HDFS，完成推測并行解壓縮算法的全過程。

圖7 推測并行算法執(zhí)行的有向無環(huán)圖2Fig.7 Directed acyclic graph 2 executed by speculative parallelism algorithm

4 實驗與結(jié)果分析

為全面測試推測并行解壓縮算法的功能和性能。實驗設(shè)計如下：在實驗環(huán)境配置方面，選用7臺相同配置的聯(lián)想ST58小型塔式服務(wù)器，搭配Juniper J6350 企業(yè)級高性能路由器組建計算集群，并部署最新版本的Apache Spark 3.0.1。

實驗數(shù)據(jù)隨機選擇成都鐵路局下轄的4 列高速列車在2019 年4 月至6 月期間所產(chǎn)生的監(jiān)測數(shù)據(jù)。數(shù)據(jù)使用Zlib 編碼指導(dǎo)壓縮，大小從20 GB 到200 GB 規(guī)模不等，用以測試算法在應(yīng)對不同規(guī)模數(shù)據(jù)時的性能表現(xiàn)情況。測試數(shù)據(jù)的詳情如表1所示，其中File 4記錄的是同一列車往返的監(jiān)測數(shù)據(jù)。

表1 實驗數(shù)據(jù)集Tab.1 Dataset used in experiment

此外，為了探究算法的可擴展性，還設(shè)置了4 組對照實驗組，分別是傳統(tǒng)串行算法在Apache Spark 上串行執(zhí)行，以及推測并行算法在由3/5/7 節(jié)點組成的集群上并行執(zhí)行。實驗方案和具體配置如表2 所示。值得注意的是，由于傳統(tǒng)算法只能串行執(zhí)行，因此即使分配再多的節(jié)點，算法實際使用的節(jié)點數(shù)仍只有2個，即1個主節(jié)點+1個工作節(jié)點。

遵照表2 設(shè)計的實驗方案，分別對傳統(tǒng)串行算法和推測并行算法進(jìn)行測試。為保證實驗結(jié)果的可靠性，每組實驗在Apache Spark 上分別運行五次，求取平均運行時長作為最終實驗結(jié)果。此外，在實驗中使用開源的分布式監(jiān)控系統(tǒng)Ganglia實時檢測集群中所有節(jié)點的CPU、內(nèi)存、磁盤、I/O負(fù)載以及整體網(wǎng)絡(luò)負(fù)載情況。

表2 實驗方案的具體配置Tab.2 Specific configuration of experimental schemes

下面從性能、可擴展性、可靠性等方面對基于推測技術(shù)的并行算法進(jìn)行測試評估，并結(jié)合實驗數(shù)據(jù)，進(jìn)行相關(guān)分析。

4.1 算法的性能測試與分析

首先測試推測并行算法的性能。圖8 展示了在由7 個節(jié)點組成的環(huán)境下（實驗方案Experiment 4），傳統(tǒng)串行算法和推測并行算法的運行時長對比。如圖8 所示，盡管兩組實驗的硬件條件相同，但是由于傳統(tǒng)算法在Apache Spark 上串行執(zhí)行，通過Ganglia 可以檢測到在算法實際運行過程中，僅有一個主節(jié)點與一個工作節(jié)點參與有效計算，而基于相同環(huán)境的并行算法由于可以同時調(diào)度和使用集群所有資源，因此執(zhí)行時間大幅縮短。

詳細(xì)研究圖8 可以發(fā)現(xiàn)，在由7 節(jié)點組成的集群下，針對大規(guī)模數(shù)據(jù)的解壓縮過程中，并行算法在處理相同大小文件時，平均耗時比傳統(tǒng)串行算法減少了約2/3。經(jīng)過統(tǒng)計不同算法處理File1 到File4 的時長，可以計算出相較于傳統(tǒng)算法，并行算法將解壓縮的效率提高了2.10 倍。因此說明在面對大規(guī)模高速列車監(jiān)測數(shù)據(jù)的解壓縮時，基于推測并行技術(shù)的解壓縮算法比傳統(tǒng)串行解壓縮算法更高效。

圖8 性能測試結(jié)果Fig.8 Results of performance evaluation

4.2 算法的可擴展性測試與分析

為了測試算法的可擴展性，設(shè)計實驗如下：在保持測試數(shù)據(jù)不變的情況下，逐漸增加集群中工作節(jié)點的個數(shù)，設(shè)置如表2 所示的三組實驗方案對照組；再在這三組實驗方案下，分別使用推測并行算法解壓縮File1 到File4 的數(shù)據(jù)，并統(tǒng)計算法在不同方案中的執(zhí)行時長；最后，通過觀察算法的執(zhí)行時長變化情況，驗證算法是否具有良好的可擴展性。

圖9 展示了在不同節(jié)點數(shù)的情況下，推測并行算法在處理同規(guī)模數(shù)據(jù)時的性能變化情況。面對相同規(guī)模的壓縮數(shù)據(jù)時，隨著節(jié)點數(shù)的增加，推測并行算法的執(zhí)行時間逐漸減少。此外，由圖9 可以看出，當(dāng)測試數(shù)據(jù)增大到一定程度（大于100 GB），節(jié)點數(shù)量的變化對算法的性能影響更加明顯。

圖9 可擴展性測試結(jié)果Fig.9 Results of scalability evaluation

加速比計算公式如下：

其中：p表示可并行部分的占比；s表示處理器個數(shù)或可并行部分的加速倍數(shù)。

經(jīng)過計算，推測并行算法在不同環(huán)境下處理相同數(shù)據(jù)時的加速比變化情況如圖10 所示。隨著節(jié)點數(shù)的增加，算法加速比S（p如式（5）所示）逐步上升，特別在針對大于100 GB 的大規(guī)模壓縮數(shù)據(jù)的處理中，算法的加速比跟隨并行機數(shù)量的增加呈近似線性增長。表明本文算法具有很強的擴展性，其性能隨著工作節(jié)點數(shù)的增加而不斷提升，進(jìn)一步驗證了圖9所呈現(xiàn)出的實驗結(jié)果。

圖10 各算法加速比變化情況Fig.10 Change of algorithms’speedup

4.3 算法的可靠性測試與分析

算法的可靠性，或稱算法的準(zhǔn)確性，是衡量算法是否優(yōu)秀的核心要素。從本質(zhì)上講，推測并行算法是利用之前無法被串行算法充分利用的計算資源來進(jìn)行額外計算，進(jìn)而從額外計算的成功中獲得性能提升，故其性能提升的基本原理是以資源換取效率，與基于多核架構(gòu)的并行算法原理類似。因此，如果推測并行算法中的推測錯誤率太高，不僅表示算法的準(zhǔn)確性差、可靠性低，同時會導(dǎo)致集群中大量計算資源被用于進(jìn)行無效計算，嚴(yán)重時甚至影響算法的整體性能。

為了測試算法的可靠性，需要對推測劃分結(jié)果的準(zhǔn)確率做統(tǒng)計和分析，具體方法是：在對推測劃分的結(jié)果進(jìn)行驗證結(jié)束以后，使用插樁測試技術(shù)，統(tǒng)計出現(xiàn)錯誤的推測劃分?jǐn)?shù)據(jù)的比例。結(jié)果如表3所示。

表3 錯誤推測率的統(tǒng)計Tab.3 Statistics on mis-speculation rate

按照32 MB 為最小劃分步長對壓縮數(shù)據(jù)進(jìn)行推測劃分，其推測劃分塊的數(shù)量如表3 的第三列所示。經(jīng)過推測檢驗，發(fā)生誤推測的數(shù)據(jù)塊數(shù)量如表3 的第四列所示。從這兩列數(shù)據(jù)內(nèi)容可以看出，只有極少數(shù)的推測劃分出現(xiàn)了錯誤。誤推測的比例始終維持在0.5%以下。這意味著在本文算法中，只有極少量的資源被浪費在基于錯誤推測結(jié)果的計算上，而大部分計算資源被用于進(jìn)行有效計算。這不僅意味著本文算法具有很強的可靠性，也說明本文算法能夠充分有效地利用Apache Spark中蘊含的計算資源，避免資源浪費等問題。

4.4 對算法性能提升機制的分析

通過以上實驗，證實了推測并行算法兼具高效性、可擴展性和高可靠性。在此基礎(chǔ)上，為了深入了解算法性能提升的原因，以及探究影響和制約算法性能的因素，還需對推測并行算法性能提升的機制進(jìn)行分析。具體方法如下：利用分布式監(jiān)控系統(tǒng)Ganglia 統(tǒng)計推測并行算法在執(zhí)行時各個階段的耗時情況。為統(tǒng)計分析便利，將推測劃分和檢驗階段統(tǒng)稱為推測準(zhǔn)備階段，各階段耗時如圖11所示。圖11展示了在不同實驗方案下，針對不同的測試數(shù)據(jù)，并行算法的分階段執(zhí)行時間統(tǒng)計。在推測并行算法中，推測劃分、推測檢驗、并行解壓縮3 個階段為并行執(zhí)行，而結(jié)果合并階段為串行執(zhí)行。反映在實驗中，即如圖11 所示，在面對相同的實驗數(shù)據(jù)時，隨著節(jié)點數(shù)的增加，推測準(zhǔn)備和并行解壓縮階段的耗時不斷減少，使算法保持了良好的可擴展性；然而，數(shù)據(jù)合并階段不會因為計算資源的增加而減少，面對相同規(guī)模的數(shù)據(jù)，該階段耗時基本保持不變。隨著數(shù)據(jù)量的不斷攀升，結(jié)果合并階段所占時間比例也越來越大，甚至明顯超過推測準(zhǔn)備與并行解壓縮階段所用時間之和。同樣地，隨著集群中計算節(jié)點數(shù)的增加，算法在處理相同規(guī)模的測試數(shù)據(jù)時，推測準(zhǔn)備與并行解壓縮階段用時逐漸減少，但結(jié)果合并階段卻不受其影響所占時間比例越來越大，反映在圖10 中的表現(xiàn)為：隨著計算節(jié)點數(shù)量的增加，算法整體加速比增長越來越不明顯。因此結(jié)果合并階段成為制約算法效率進(jìn)一步提升的重要因素。究其原因在于推測準(zhǔn)備和并行解壓縮階段是并發(fā)的，而結(jié)果合并階段則是在主節(jié)點上串行進(jìn)行的，隨著計算節(jié)點的增加，算法的并行階段耗時會越來越少，而結(jié)果合并階段耗時基本不變，因而導(dǎo)致整體性能提升幅度越來越小。因此優(yōu)化結(jié)果合并階段將成為后續(xù)的研究重點。

圖11 本文算法各階段耗時統(tǒng)計Fig.11 Statistics on time consumption of each stage of proposed algorithm

5 結(jié)語

本文提出了一種面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法，在暫時忽略數(shù)據(jù)依賴的前提下，使用推測并行技術(shù)，將采用變長編碼技術(shù)壓縮的、原本不可劃分的高速列車監(jiān)測數(shù)據(jù)進(jìn)行試探性劃分，再利用壓縮數(shù)據(jù)的結(jié)構(gòu)特點，對劃分結(jié)果進(jìn)行檢驗，在保證劃分準(zhǔn)確的基礎(chǔ)上，并發(fā)處理劃分結(jié)果，使原本只能按照數(shù)據(jù)組織結(jié)構(gòu)串行進(jìn)行的數(shù)據(jù)解壓縮過程能夠以推測的方式并行化進(jìn)行，進(jìn)而提高針對高速列車監(jiān)測數(shù)據(jù)的解壓縮效率。上述工作已經(jīng)取得了良好的實際效果，通過與北京交通大學(xué)和中車唐山機車車輛有限公司合作，本文算法及相關(guān)產(chǎn)品已應(yīng)用于包括CRH380BL 和CRH380B-002 等型號的高速列車監(jiān)測記錄數(shù)據(jù)的并行解壓縮工作中，并提高了針對此類車型監(jiān)測記錄數(shù)據(jù)的分析效率，但通過實驗分析可知，在該算法仍存在可優(yōu)化空間，對于算法中的結(jié)果合并階的優(yōu)化將是今后研究工作的重點。