【摘 要】從XML的屬性出發(fā)，設(shè)計了一套自學(xué)習(xí)的算法，利用個別報文的解析結(jié)果作為經(jīng)驗(yàn)值，解析新接收到的報文，避免了全量解析XML的CPU消耗，可大幅提高服務(wù)響應(yīng)處理效率。

【關(guān)鍵詞】XML解析 自學(xué)習(xí) 搜索策略樹

doi：10.3969/j.issn.1006-1010.2017.02.014 中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-1010（2017）02-0068-06

引用格式：周實(shí)奇. 通過經(jīng)驗(yàn)值提高速度的XML解析算法[J]. 移動通信， 2017，41（2）： 68-73.

1 引言

隨著分布式計算和云計算架構(gòu)趨勢的形成和發(fā)展，越來越多的系統(tǒng)需要借助企業(yè)服務(wù)總線（ESB）進(jìn)行服務(wù)編排、服務(wù)路由等處理，將分散的各個業(yè)務(wù)處理單元的原子服務(wù)集成起來，形成業(yè)務(wù)處理能力，統(tǒng)一對外開放。目前業(yè)界流行接口協(xié)議，各個處理單元交互主要以Webservices協(xié)議為主。

企業(yè)服務(wù)總線并不涉及業(yè)務(wù)處理邏輯，但是作為數(shù)據(jù)交互和服務(wù)調(diào)度的樞紐，服務(wù)的編排和服務(wù)路由等相關(guān)的處理效率，對整個系統(tǒng)的并發(fā)量和吞吐量起決定性的作用。由于處理過程中，需要獲取數(shù)據(jù)包的個別屬性字段，例如客戶ID、發(fā)起方標(biāo)識等，按目前的通用做法，采用如下方式解析XML數(shù)據(jù)包。

文獻(xiàn)[1]、[2]、[3]、[4]的方式，通常將XML數(shù)據(jù)包整體進(jìn)行解析，按照XSD定義文件對數(shù)據(jù)內(nèi)容進(jìn)行校驗(yàn)和生成對象的處理方法，通常的處理流程如圖1所示：

從以上解析過程中可以得知，在整體XML報文解析的過程中，程序需要遍歷整個報文，進(jìn)行字符串比較操作，同時查找相關(guān)的特征關(guān)鍵字。找到關(guān)鍵字以后，需要進(jìn)行屬性的堆棧入棧，并進(jìn)行屬性約束條件檢查。同時按照校驗(yàn)結(jié)果生成相應(yīng)的對象。

在ESB企業(yè)服務(wù)總線等應(yīng)用場景中，并不進(jìn)行數(shù)據(jù)包的業(yè)務(wù)處理，只是用于路由判斷和服務(wù)編排等，往往只需要個別的屬性值即可，例如只需要請求調(diào)用的服務(wù)類型和客戶ID兩個屬性值就可以進(jìn)行服務(wù)路由處理。為了獲得少數(shù)幾十個字節(jié)，需要遍歷處理整個報文，而且處理邏輯復(fù)雜，存在提高效率和優(yōu)化的空間。

在這些應(yīng)用場景，需要對每一個接入的消息進(jìn)行服務(wù)路由和編排的處理，如果對每個消息報文都要全部遍歷，將直接影響系統(tǒng)的整體表現(xiàn)情況，而經(jīng)過測試，對超過2 k大小的XML協(xié)議報文包的解析需要消耗大量CPU計算資源。

文獻(xiàn)[5]提供了一種將XML放置到緩存中，加快查詢的處理方式。在本文涉及的應(yīng)用場景中，消息報文已經(jīng)全部在內(nèi)存中，需要使用其他方式加快查詢。

文獻(xiàn)[6]提供了一種將XML建立索引的技術(shù)，便于針對個別報文反復(fù)多次查詢，與本文需要針對多個報文快速查詢的方式不同。

目前通過DTD文檔生成XML報文，通常采用文獻(xiàn)[7]的方法，經(jīng)過分析可得，相同的屬性值的長度如果接近，則ID出現(xiàn)的位置和順序相對固定，可采用經(jīng)驗(yàn)策略的方式進(jìn)行解析。

在應(yīng)用優(yōu)化XML解析算法前，需要針對系統(tǒng)中的典型報文進(jìn)行統(tǒng)計分析，分析相關(guān)報文的大小分布情況，以評估優(yōu)化算法的效果，下面以某系統(tǒng)為例，分析其中報文大小分布情況。

通過對系統(tǒng)中相關(guān)Webservices協(xié)議包大小進(jìn)行抽樣分析，可以了解到目前接口協(xié)議中，相關(guān)消息包的大小。抽樣方法為選定業(yè)務(wù)繁忙時段（15：00-16：00），按照協(xié)議包的大小，分為5個級別（0-1 k]、（1 k-5 k]、（5 k-10 k]、（10 k-30 k]、（30 k以上），分別統(tǒng)計數(shù)量和平均大小，統(tǒng)計結(jié)果如表1所示。

按照消息數(shù)據(jù)總體大小所占的百分比來進(jìn)行繪圖，相關(guān)結(jié)果如圖2所示。

根據(jù)以上分析結(jié)果，該系統(tǒng)中大量的消息大小集中在10 k左右，平均10.3 k，少量的數(shù)據(jù)包大小為30 k以上。

本次優(yōu)化的主要思路是在確保準(zhǔn)確性的前提下，基于經(jīng)驗(yàn)值進(jìn)行個別屬性的解析，同時具備自我學(xué)習(xí)和調(diào)整策略的能力，能適應(yīng)各種不同的應(yīng)用場景，適合在企業(yè)服務(wù)總線和能力開放平臺建設(shè)過程中，高效進(jìn)行服務(wù)編排和服務(wù)路由判斷處理等場景。

2 算法描述

為了提高處理效率，本算法主要基于接收到的報文解析的經(jīng)驗(yàn)值進(jìn)行解析。經(jīng)驗(yàn)值作為解析策略，針對不同服務(wù)ID的報文分別定義相關(guān)的解析策略。解析策略采用冒泡排序的方法進(jìn)行管理，實(shí)現(xiàn)最優(yōu)的策略最先被采用。策略可以手工清空或者定期清空，以防止長期運(yùn)行以后，錯誤的經(jīng)驗(yàn)值導(dǎo)致整體解析的處理性能下降。與文獻(xiàn)[8]不同，本算法主要關(guān)注個別的屬性，而不是全量解析。

2.1 整體描述

整體上來看，算法分為三大組成部分：

（1）配置關(guān)注的屬性值，并生成最優(yōu)搜索路徑的檢索樹。

（2）按照檢索樹和接收到的報文，進(jìn)行分析，將相關(guān)的經(jīng)驗(yàn)值保存為策略樹，多個不同大小的報文生成的不同策略樹保存為策略樹數(shù)組。

（3）按照接收到報文解析情況中策略的命中情況，調(diào)整策略樹數(shù)組中各個策略樹的優(yōu)先級別；支持手工清除策略樹數(shù)組和定時清除，以防止舊的經(jīng)驗(yàn)值無法適應(yīng)新的情況。

由于算法使用了相對位置，因此無法應(yīng)用參考文獻(xiàn)[9]的并行處理方式，整體結(jié)構(gòu)如圖3所示。

2.2 目標(biāo)屬性值的定義與預(yù)處理

為了高效處理，對報文只解析關(guān)鍵字段，并不對屬性值的約束條件進(jìn)行判斷。首先需要定義關(guān)注的屬性ID，為提高處理效率，定義了相應(yīng)的屬性ID后，需要對定義的文本進(jìn)行預(yù)處理，形成搜索關(guān)鍵字堆棧樹。

目標(biāo)屬性值的定義采用依次羅列XML各個層次對象ID的方式進(jìn)行定義。

以下為一個例子：

Header， InterBOSS， RoutingInfo， OrigDomain

Header， InterBOSS， RoutingInfo， RouteValue

文獻(xiàn)[10]的處理方式，以上文本定義了在服務(wù)編排中和服務(wù)路由中需要使用到的兩個屬性，轉(zhuǎn)為偽代碼，相應(yīng)的處理邏輯為：

（1）在報文中檢索到

（2）在1的結(jié)果之間檢索到和。

（3）在2的結(jié)果之間檢索到和。

（4）在3的結(jié)果之間檢索到和之間的內(nèi)容作為后續(xù)處理需要使用的第一個參數(shù)。

（5）在3的結(jié)果之間檢索到和之間的內(nèi)容作為后續(xù)處理需要使用的第二個參數(shù)。

根據(jù)以上偽代碼和定義文本，針對目標(biāo)屬性值定義的預(yù)處理流程如圖4所示：

為將相同的搜索路徑合并，提高處理效率，必須對定義的目標(biāo)屬性值搜索路徑進(jìn)行預(yù)處理。預(yù)處理的結(jié)果為生成搜索索引樹，構(gòu)建搜索樹的過程如下：

（1）將多行的目標(biāo)屬性搜索文本進(jìn)行排序，排序后，相近的搜索路徑定義文本出現(xiàn)位置將彼此相近。

（2）讀取其中的一行文本定義，拆解其中的屬性ID路徑，在搜索樹中查找是否已經(jīng)存在對應(yīng)的節(jié)點(diǎn)或者葉子。

（3）如果已經(jīng)存在對應(yīng)的節(jié)點(diǎn)或者葉子，則不處理，否則新建對應(yīng)的節(jié)點(diǎn)或者葉子。

（4）循環(huán)處理一行文本定義的全部屬性ID，直到行結(jié)束。

（5）循環(huán)處理所有文本定義行，直到結(jié)束。

按以上處理方式預(yù)處理完成后，將生成對應(yīng)的屬性ID檢索樹，樹上的所有葉子節(jié)點(diǎn)對應(yīng)需要輸出的目標(biāo)屬性值。由于所有相同的路徑已經(jīng)合并，按此方式檢索屬性ID不存在冗余操作。

2.3 解析策略新建與初始化

當(dāng)經(jīng)驗(yàn)值未建立或者已有的策略搜索失敗，或者策略被手工或者定期清空的時候，需要重新建立相關(guān)的策略。文獻(xiàn)[11]提供了一種全量路徑樹的搜索方法，當(dāng)應(yīng)用策略失敗時，可參考應(yīng)用進(jìn)行解析，作為新的經(jīng)驗(yàn)值。策略新建的過程如圖5所示：

首先，按照建立的搜索樹建立策略樹，策略樹的枝葉結(jié)構(gòu)與搜索樹相同。按照枝葉結(jié)構(gòu)遍歷報文包，同時記下發(fā)現(xiàn)關(guān)鍵屬性的字符串出現(xiàn)的絕對位置。遍歷的過程中，可參考文獻(xiàn)[12]的方式進(jìn)行。

所有的屬性ID以及屬性Value檢索正常以后，需要與現(xiàn)有的策略比對，選擇按照報文的比例還是絕對位置新建檢索策略樹。

如果在原有策略樹數(shù)組中，命中概率最高的是按比例策略，則新建策略為按比例策略；如果原有策略命中率最高的為按絕對位置策略，則檢查是否存在按比例的策略；如果不存在，則新建按比例的策略，否則新建按絕對位置的策略。

如果是第一條策略，則新建按絕對位置的策略。

如果選定新建策略為按比例的策略，則按照檢索關(guān)鍵屬性ID出現(xiàn)的位置和報文的整體長度，計算出每個屬性ID出現(xiàn)位置的比例，保存在策略樹中，同時將策略樹保存到策略樹數(shù)組中。

如果選定的新策略為按絕對位置搜索，則報文長度/2=報文長度中值，統(tǒng)計出現(xiàn)在報文長度中值之前的屬性ID個數(shù)和出現(xiàn)在報文長度中值之后的屬性ID個數(shù)。按照個數(shù)的多少判斷是按照報文尾還是報文頭的位置計算絕對位置，并將計算結(jié)果保存到策略樹中，同時將策略樹保存到策略樹數(shù)組內(nèi)。

2.4 解析報文，同時調(diào)整策略樹數(shù)組的算法

按經(jīng)驗(yàn)值檢索報文的過程中，還需要按照檢索的結(jié)果不斷調(diào)整策略樹數(shù)組，將不同的策略樹排列優(yōu)先級。達(dá)到按經(jīng)驗(yàn)值優(yōu)化選用策略樹的目的。

應(yīng)用的過程中，采用對策略樹數(shù)組中的每個策略進(jìn)行計數(shù)，當(dāng)策略命中一次，則將相關(guān)的計數(shù)加1，每次策略命中，則與比當(dāng)前策略更優(yōu)的策略比較一次，如果計數(shù)已經(jīng)超過了當(dāng)前更優(yōu)的策略，則采用冒泡方法，將當(dāng)前策略向前調(diào)整一位，具體算法如圖6所示：

先選取出一條策略樹，按照策略樹的類型和報文長度，計算所有屬性ID對應(yīng)的絕對位置。如果是按比例的策略樹，則從報文頭開始，按照報文長度*屬性ID檢索比例的絕對位置計算；如果是按報文頭絕對位置檢索的策略樹，則直接采用屬性ID檢索位置計算；如果是按報文尾絕對位置檢索的策略樹，則采用報文長度-屬性ID檢索位置計算。

計算各個屬性ID檢索位置以后，則按照計算結(jié)果加-10 byte的位置進(jìn)行字符串比較操作，確定是否在相關(guān)的位置出現(xiàn)對應(yīng)的屬性ID。

如果所有屬性ID正確檢索，則輸出對應(yīng)的key-value值，作為后續(xù)處理的依據(jù)，同時相關(guān)的策略樹對應(yīng)的計數(shù)加1，進(jìn)行策略樹數(shù)組的冒泡調(diào)整。

如果屬性ID檢索失敗，則放棄該條策略，選用下一條策略；如果所有的策略都檢索失敗，則按照上文的方法，新建對應(yīng)的策略樹。

通過不斷調(diào)整策略樹的優(yōu)先級以及新增加策略樹的方式，策略樹數(shù)組具備自學(xué)習(xí)自適應(yīng)新報文格式的能力。新增加的報文樣式，當(dāng)?shù)谝淮纬霈F(xiàn)的時候，所有策略樹都會檢索失敗，同時會自動新增一條對應(yīng)的檢索策略樹。如果該報文出現(xiàn)的頻率足夠頻繁，一段時間以后，新增的策略樹將提到最高的優(yōu)先級。

為了防止系統(tǒng)長期運(yùn)行以后，相關(guān)舊的策略樹計數(shù)巨大，導(dǎo)致對新的報文格式一直優(yōu)先采用舊的策略樹進(jìn)行檢索，可以采用手工清空策略樹數(shù)組或者定期（例如每日或每周）自動清空策略樹數(shù)組的方式。策略樹數(shù)組清空以后，會按照目前最新報文的情況自動重建。即用最新的報文情況作為經(jīng)驗(yàn)值，而放棄原有的長期經(jīng)驗(yàn)值。

2.5 應(yīng)用約束條件

算法直接應(yīng)用原有報文的解析結(jié)果，并不對報文進(jìn)行全文解析處理，所以存在如下的應(yīng)用限制：

（1）只對XML屬性ID進(jìn)行是否存在的檢測，不進(jìn)行是否唯一以及其他例如數(shù)據(jù)類型等的檢測。

（2）并不適用于數(shù)組作為檢索對象的情況，因?yàn)闊o法預(yù)知算法會匹配上數(shù)組中的哪一個對象。

3 對比測試情況

采用四核3.3 GHz的PC服務(wù)器，配置8GbDDR3內(nèi)存，進(jìn)行測試，測試的數(shù)據(jù)為生產(chǎn)系統(tǒng)中的業(yè)務(wù)繁忙時段（15：00-16：00），按時間順序和流水號順序，截取各種業(yè)務(wù)報文1萬個，預(yù)先讀到內(nèi)存中，采用單機(jī)環(huán)境，對比使用DOM傳統(tǒng)方式輸出關(guān)鍵屬性字段和使用基于經(jīng)驗(yàn)值自學(xué)習(xí)自適應(yīng)的算法輸出關(guān)鍵字段，比較解析包的平均耗時。

相關(guān)的報文示例如下：

<？xml version='1.0'encoding='utf-8'？>

Envelope xmlns：env="http：//www.w3.org/2003/05/soap-envelope"xmlns：xenc="http：//www.w3.org/2001/04/xmlenc#" xmlns：wsse="http：//docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">