面向高速列車監測數據的并行解壓縮算法

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

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

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

0 引言

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

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

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

1 動機

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

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

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

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

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

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

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

2 算法設計

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

2.1 推測劃分

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

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

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

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

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

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

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

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

為使算法耗時最短，需對式（3）進行求導，并令導數為0，易知當劃分粒度H滿足式（4）時，使T取得極小值。

綜上分析，式（4）即為確定推測劃分粒度的數學模型，通過該模型可以確定當H滿足條件時，算法執行時間最短。

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

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

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

2.2 推測檢驗

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

頭校驗是指檢驗劃分結果的前3 位是否遵循塊頭標號的編碼規則。一般來說，壓縮數據塊的前3 位只能是010 或000，分別代表該壓縮數據塊是遵循動態編碼標準的壓縮數據塊或是未被壓縮的非壓縮數據塊，如果劃分結果的前3 位不是010或000，則該劃分為錯誤劃分。

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

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

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

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

2.3 并行解壓縮

并行解壓縮是算法的第三階段，該階段的目的是并行處理經過推測劃分和推測檢驗的數據塊集合。在該階段，首先將經過二次劃分的數據塊集合傳輸到分布式計算框架的各計算節點中，同時設置相應的資源調度策略，以保證分布式計算框架能提供充足的算力，支持所有數據塊的并行處理。在數據傳輸和資源調度之后，由主節點根據推測劃分塊的數量，派生相應數量的并行任務，同時對所有的分塊進行解壓縮。在該過程中，所有工作節點執行的任務內容相同，而處理的數據不同，每個節點內部的具體執行內容如算法2所示。

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

2.4 結果合并

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

3 算法實現

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

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

圖6 推測并行算法執行的有向無環圖1Fig.6 Directed acyclic graph 1 executed by speculative parallelism algorithm

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

第二步為推測劃分，即使用塊尾標號RDD2，對RDD1 中的所有元素進行并行劃分，具體流程是以RDD2 中塊尾標號為依據，按照32 MB 步長，對監測數據RDD1 中所有分片同時執行如圖4 所示過程的劃分，最終結果形成RDD3。在圖6中，RDD1 經RDD2 劃分后形成由M個分塊組成的RDD3，在RDD3 內部，鍵值對與RDD1 的組成略有不同：鍵仍然表示分塊順序，值變為元組形式，其中，元組的首個元素代表劃分位置相對于監測數據起始位置的偏移量，第二個元素代表劃分結果。

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

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

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

圖7 推測并行算法執行的有向無環圖2Fig.7 Directed acyclic graph 2 executed by speculative parallelism algorithm

4 實驗與結果分析

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

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

表1 實驗數據集Tab.1 Dataset used in experiment

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

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

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

下面從性能、可擴展性、可靠性等方面對基于推測技術的并行算法進行測試評估，并結合實驗數據，進行相關分析。

4.1 算法的性能測試與分析

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

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

圖8 性能測試結果Fig.8 Results of performance evaluation

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

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

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

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

加速比計算公式如下：

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

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

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

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

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

為了測試算法的可靠性，需要對推測劃分結果的準確率做統計和分析，具體方法是：在對推測劃分的結果進行驗證結束以后，使用插樁測試技術，統計出現錯誤的推測劃分數據的比例。結果如表3所示。

表3 錯誤推測率的統計Tab.3 Statistics on mis-speculation rate

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

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

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

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

5 結語

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