通過(guò)經(jīng)驗(yàn)值提高速度的XML解析算法

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

按照消息數(shù)據(jù)總體大小所占的百分比來(lái)進(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)行個(gè)別屬性的解析，同時(shí)具備自我學(xué)習(xí)和調(diào)整策略的能力，能適應(yīng)各種不同的應(yīng)用場(chǎng)景，適合在企業(yè)服務(wù)總線和能力開(kāi)放平臺(tái)建設(shè)過(guò)程中，高效進(jìn)行服務(wù)編排和服務(wù)路由判斷處理等場(chǎng)景。

2 算法描述

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

2.1 整體描述

整體上來(lái)看，算法分為三大組成部分：

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

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

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

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

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

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

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

以下為一個(gè)例子：

Header， InterBOSS， RoutingInfo， OrigDomain

Header， InterBOSS， RoutingInfo， RouteValue

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

（1）在報(bào)文中檢索到

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

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

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

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

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

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

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

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

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

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

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

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

2.3 解析策略新建與初始化

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

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

所有的屬性ID以及屬性Value檢索正常以后，需要與現(xiàn)有的策略比對(duì)，選擇按照?qǐng)?bào)文的比例還是絕對(duì)位置新建檢索策略樹(shù)。

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

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

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

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

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

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

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

先選取出一條策略樹(shù)，按照策略樹(shù)的類型和報(bào)文長(zhǎng)度，計(jì)算所有屬性ID對(duì)應(yīng)的絕對(duì)位置。如果是按比例的策略樹(shù)，則從報(bào)文頭開(kāi)始，按照?qǐng)?bào)文長(zhǎng)度*屬性ID檢索比例的絕對(duì)位置計(jì)算；如果是按報(bào)文頭絕對(duì)位置檢索的策略樹(shù)，則直接采用屬性ID檢索位置計(jì)算；如果是按報(bào)文尾絕對(duì)位置檢索的策略樹(shù)，則采用報(bào)文長(zhǎng)度-屬性ID檢索位置計(jì)算。

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

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

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

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

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

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

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

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

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

3 對(duì)比測(cè)試情況

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

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

<？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">