基于狀態(tài)機的HTTP Chunked流并發(fā)解析

李明哲,陳 君,王勁林,陳 曉

(1.中國科學院聲學研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京100190;2.中國科學院大學,北京100190)

基于狀態(tài)機的HTTP Chunked流并發(fā)解析

李明哲1,2,陳 君1,王勁林1,陳 曉1

(1.中國科學院聲學研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京100190;2.中國科學院大學,北京100190)

某些流媒體服務(wù)器需要對HTTP Chunked編碼數(shù)據(jù)流進行并發(fā)解析,樸素靜態(tài)解析算法難以應(yīng)用于高效靈活的事件驅(qū)動并發(fā)模型,且會造成長延遲和多次數(shù)據(jù)拷貝,導(dǎo)致內(nèi)存和計算資源開銷都較高。針對上述問題,提出一種基于有限狀態(tài)機的解析策略。將一次接收和一次解析操作構(gòu)成一個任務(wù)片,從而適應(yīng)事件驅(qū)動模型,對收到的數(shù)據(jù)包進行即時處理和釋放,不需要緩存整個HTTP報文,減少一次內(nèi)存拷貝開銷。在數(shù)據(jù)處理過程中,通過有限狀態(tài)機保存解析狀態(tài),能夠在任務(wù)片退出后恢復(fù)之前的解析狀態(tài),從而解決事件驅(qū)動模型下的字段斷裂問題。實驗結(jié)果表明,相比于靜態(tài)解析算法,該策略能夠明顯地降低解析過程的處理時間和占用的內(nèi)存。

流媒體;HTTP Chunked編碼;并發(fā)解析;事件驅(qū)動模型;有限狀態(tài)機;內(nèi)存拷貝

1 概述

HTTP協(xié)議[1]被廣泛用于互聯(lián)網(wǎng)流媒體服務(wù)中[2],包括視頻點播(Video On Demand,VOD)[3-4]和實時直播節(jié)目[5-6]等。基于HTTP的流媒體服務(wù)充分利用了已經(jīng)廣泛部署的Web服務(wù)設(shè)施,尤其是利用了內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Distribution Network, CDN)中的 HTTP緩存提高了服務(wù)的可擴展性。HTTP協(xié)議的消息格式包含消息首部和消息體。首部部分定義了一些屬性字段,向報文接收者提供了重要的信息。其中,Content-Length屬性字段表示消息體的長度。然而,對于某些動態(tài)生成的數(shù)據(jù),消息生成者可能無法立即知悉消息體的總長度,從而不能及時計算Content-Length字段值。使用Chunked編碼HTTP/1.1可以回避這一問題。Chunked編碼是協(xié)議的一種傳輸編碼方式,將待傳輸數(shù)據(jù)切割為多個塊,報文只需提供當前已知塊的長度。

Chunked編碼被用于流媒體傳輸過程中。文獻[5]利用Chunked編碼有效地縮小了直播節(jié)目的播放延時。中國下一代數(shù)字互動電視標準[7]也規(guī)定,節(jié)目流從 CDN到流服務(wù)器的傳輸過程使用HTTP Chunked編碼,由后者進行解碼。文獻[8]根據(jù)該標準,在多核網(wǎng)絡(luò)處理器平臺對流服務(wù)器進行了實現(xiàn)。

服務(wù)器的并發(fā)性有2種實現(xiàn)模型:事件驅(qū)動和多線程[9-11]。相對于多線程模型,事件驅(qū)動模型有更高的效率和更大的靈活性,缺點是編程開發(fā)過程較為復(fù)雜。雖然多線程的效率日益提高,然而對于一個支持數(shù)千條流的服務(wù)器系統(tǒng),其增加的總開銷依舊不能忽略。流媒體服務(wù)一般有實時性要求,應(yīng)用程序必須對各個數(shù)據(jù)流持有更大的控制權(quán),這也是缺少靈活性的多線程模型不能滿足的。另外,一些嵌入式運行環(huán)境并不支持線程,如上述流服務(wù)系統(tǒng)所基于Cavium公司OCTEON處理器的Simple Executive操作系統(tǒng)環(huán)境[8]。因此,本文采用事件驅(qū)動模型來實現(xiàn)服務(wù)器的并發(fā)性。在這種模型下,實時流媒體并發(fā)服務(wù)器采用分時方式處理各個數(shù)據(jù)流,每個流的處理過程被分割成小粒度的任務(wù),應(yīng)用程序按照實時性要求對各個流的CPU時間進行統(tǒng)一調(diào)度。

Chunked編碼雖然簡單直觀,然而流媒體具有數(shù)據(jù)量大、傳輸時間長的特點,流服務(wù)器將會對大量數(shù)據(jù)進行Chunked解碼操作,其效率對于流服務(wù)器的整體性能至關(guān)重要。對于基于事件驅(qū)動模型的高并發(fā)的流服務(wù)器,使用CPU分時的方式處理并發(fā)數(shù)據(jù)流,Chunked編碼的各個字段可能會發(fā)生斷裂,使得解碼過程變得復(fù)雜。目前幾乎沒有文獻針對事件驅(qū)動模型下高并發(fā)媒體流Chunked編碼的解析算法展開研究。為此,本文將探討在這種場景下如何對Chunked編碼的并發(fā)數(shù)據(jù)流進行高效解析,提出一種基于有限狀態(tài)機[12]的解析算法。

2 Chunked編碼的靜態(tài)解析

Chunked編碼后的消息體一組連續(xù)的編碼塊(Chunk),每個編碼塊包含了塊長度字段(chunk size)及塊載荷字段(chunk data)兩部分,各部分用回車換行符(CRLF,由CR和LF 2個字符組成)隔開。文獻[7]未涉及Chunked編碼的擴展字段字段,本文探討的解碼算法將對其進行忽略。為方便討論,認為塊長度字段還包括其前后兩處的CRLF字符,而塊載荷尾部的CRLF屬于下一個塊。這樣,一個塊完全由塊長度和塊載荷字段構(gòu)成。注意第一個塊也會有前導(dǎo)的CRLF,即HTTP頭部和編碼塊報文的交界處。

作為對Chunked編碼的一種最簡單的解碼算法,靜態(tài)解析方法先將整個HTTP報文獲取到本地緩沖區(qū),再在本地依次讀取各個編碼字段,將解析出的有效數(shù)據(jù)復(fù)制到另一緩沖區(qū),其流程可參考文獻[1]。

靜態(tài)解析算法的缺點包括:

(1)靜態(tài)解析算法需要先接收整個HTTP報文,會導(dǎo)致較大的啟動延遲。

(2)靜態(tài)解析法難以直接應(yīng)用在事件驅(qū)動模型中。一條流的處理過程分為網(wǎng)絡(luò)接收和解碼2個環(huán)節(jié)。其中,網(wǎng)絡(luò)接收環(huán)節(jié)可以基于Select、Epoll[10]等異步消息通知的方式進行任務(wù)分割,而解碼過程則難以分割。如果整個解析過程當作一個原子性任務(wù)被完全處理,則會大大損害其他流的實時性和平滑性。

(3)靜態(tài)解析法導(dǎo)致解碼過程中會產(chǎn)生一次內(nèi)存拷貝,再加上HTTP接收過程、流化數(shù)據(jù)發(fā)送過程中數(shù)據(jù)在協(xié)議棧緩沖區(qū)和應(yīng)用緩沖區(qū)之間的拷貝,總共是3次拷貝,造成運行效率低下。

3 基于FSM的解析算法

3.1 事件驅(qū)動模型下的Chunked解碼

考慮將網(wǎng)絡(luò)接收環(huán)節(jié)和解碼環(huán)節(jié)交替進行,一次接收操作和一次解碼操作構(gòu)成一個任務(wù)片,從而適應(yīng)了事件驅(qū)動模型。在一個任務(wù)片中,立即對本次接收操作得到的網(wǎng)絡(luò)數(shù)據(jù)進行解析,提取出有效內(nèi)容,這樣就可以及時將接收到的數(shù)據(jù)進行丟棄,而不必拼接成完整的HTTP報文,從而減少了一次內(nèi)存拷貝。

任務(wù)的分割是由單次接收操作的數(shù)據(jù)量來決定。應(yīng)用程序以非阻塞的方式調(diào)用這些網(wǎng)絡(luò)數(shù)據(jù)接收接口,如POSIX.1定義的read和recv函數(shù),可以控制單次接收量的上限,應(yīng)用程序就控制了任務(wù)分片長度的上限。對于非阻塞讀操作,可能未能讀到任何數(shù)據(jù),導(dǎo)致該任務(wù)片為無用的空片。對異步消息通知機制的利用,可以使應(yīng)用程序僅在明知該數(shù)據(jù)流有新數(shù)據(jù)到達時,才切換到該流進行處理,一般至少能讀取到一個傳輸層報文。這樣,任務(wù)分片長度的下限也可以得到控制,避免了空片。

讀取操作會依次讀到每個塊的塊長度和塊載荷字段。當讀完塊長度字段后,即可確定塊載荷字段的長度,進而將接下來的塊載荷數(shù)據(jù)直接讀入有效內(nèi)容緩沖區(qū)。解碼過程中塊長度字段只能被讀入臨時緩沖區(qū)。用sread和dread分別表示讀取塊長度和塊載荷的操作,分別將協(xié)議棧內(nèi)核緩沖區(qū)的數(shù)據(jù)讀入應(yīng)用的臨時緩沖區(qū)和有效內(nèi)容緩沖區(qū),統(tǒng)稱read操作。m=read(n)表示應(yīng)用程序以非阻塞方式要求讀取nByte數(shù)據(jù),實際成功讀取了mByte。

對于每個流,其塊長度和塊載荷字段都可能因任務(wù)分片而不能完整讀取,造成字段截斷。因此,每個數(shù)據(jù)流在任務(wù)分片結(jié)束時保存其當前解析狀態(tài),在下一個任務(wù)分片讀取保持的狀態(tài)信息,以恢復(fù)之前的工作。

3.2 基于有限狀態(tài)機的Chunked解碼算法

有限狀態(tài)機是一個數(shù)學工具,用于處理有限數(shù)量子程序(狀態(tài))的發(fā)展變化。每個時刻根據(jù)當前的狀態(tài)和本時刻的輸入,可以決定應(yīng)執(zhí)行的動作,包括確定下一個狀態(tài)以進行轉(zhuǎn)移。利用FSM設(shè)計了一個Chunked編碼解析方法,將解析過程分為多種狀態(tài)。每個狀態(tài)都會進行sread或dread操作。在read操作返回之后,分塊讀取的完成程度決定了當前的狀態(tài)。狀態(tài)的定義狀態(tài)的名稱如表1所示。

表1 FSM狀態(tài)定義

算法啟動時處于cr1狀態(tài),表示下一個字節(jié)是本塊的第一個 CR字符。通過read操作讀入新的數(shù)據(jù),算法會在各狀態(tài)間轉(zhuǎn)換,如圖1所示。其中,符號S表示塊長度字段中的一個十六進制字符;D表示塊載荷中的一個字符;星號?表示前面那類字符被讀入一次或多次;括號中的符號指示下一個待讀入字符的類型。

圖1 FSM狀態(tài)轉(zhuǎn)移

在cr1狀態(tài)下,通過sread操作讀入CR后,進入lf1狀態(tài)。在讀入LF后,進入cs狀態(tài),期待即將讀入塊長度中的十六進制字符,塊長度字段可能只有一個這種字符。在讀入第一個十六進制字符后,不確定下一個字符是十六進制字符,還是CR,記此時進入 cr2狀態(tài)。記塊長度字段對應(yīng)的整數(shù)值為chunklen,解析前猜測為0,在cr2狀態(tài),sread操作會不斷讀入新的十六進制字符,用于更新chunklen的猜測值。具體做法是:將新字符轉(zhuǎn)換為整型數(shù)d,則chunklen更新為chunklen×16+d,其中,“×”操作可以用移位操作實現(xiàn)。直到讀入的字符是CR,進入lf2狀態(tài),此時,chunklen的值可以確定,反映了塊載荷字段的長度,算法進入cd狀態(tài),表示下一個待讀取的字節(jié)屬于塊載荷,此時,開始使用dread操作讀取有效內(nèi)容。在 cd狀態(tài)下,隨著 dread操作, chunklen表示尚未被讀取的塊載荷字節(jié)數(shù),不斷減小。直到chunklen最后變?yōu)?,此時,本編碼塊所有的塊載荷數(shù)據(jù)均已被讀取,算法進入cr1狀態(tài)。

上述算法在sread操作過程中每次只讀一個字節(jié),可以加以改進,以減小讀操作次數(shù)。原則是sread操作應(yīng)盡可能多地讀取數(shù)據(jù),但避免讀取到塊載荷數(shù)據(jù),因此,sread之前應(yīng)猜測塊長度字段還剩余多少字節(jié)未讀,取最小的可能值,作為 sread參數(shù)。,如在cr1狀態(tài),塊長度字段的未讀字節(jié)數(shù)至少為5。而在lf1狀態(tài),則為4。根據(jù)sread成功讀到的字節(jié)數(shù),確定下一個轉(zhuǎn)移狀態(tài)。另外,在cd狀態(tài)下, dread的參數(shù)未必取chunklen,可以用每個任務(wù)分片的最大讀取字節(jié)數(shù)maxSliceLen進行限制。這樣,每個狀態(tài)下應(yīng)執(zhí)行的動作如表2所示。

表2 狀態(tài)的動作

基于FSM的算法能夠很好地適用于事件驅(qū)動模型,同時相對于靜態(tài)解析可以減少一次內(nèi)存拷貝。

3.3 算法執(zhí)行實例

以“ 10 0123456789abcdef”編碼塊為例說明上述算法的執(zhí)行過程,實際的流媒體服務(wù)的編碼塊長要遠遠大于這個例子。根據(jù)表1的定義,它可能會經(jīng)歷的狀態(tài)如表3所示。

表3 算法執(zhí)行實例

如果流在接收到前3個字符“ 1”后遇到截斷,則無法確定塊長度數(shù)值。此時,需要保存的信息包括處于狀態(tài)cr2,chunklen值為1。當這條數(shù)據(jù)流進入第2個任務(wù)分片時,首先查看已保存的信息,得知目前為cr2狀態(tài),按照表2的說明,執(zhí)行sread(2),得到字符“0 ”,于是lf2狀態(tài),確定chunklen為16。再執(zhí)行sread(1),進入cd狀態(tài)。如果分片要求讀入的數(shù)據(jù)的長度不能超過10 Byte(maxSliceLen),于是執(zhí)行dread(10),成功讀取了10 Byte,chunklen更新為6,此時,任務(wù)分片結(jié)束。在第3個任務(wù)分片,根據(jù)當前的cd狀態(tài)和chunklen與maxSliceLen的值,執(zhí)行dread(6)。如果成功讀取了6個字節(jié)則進入cr1狀態(tài),準備解析下一個分塊。否則,FSM以cd狀態(tài)退出本分片。

4 測試評估

對上述靜態(tài)解析算法和基于FSM的解析算法進行測試,以評估兩者的處理時延和內(nèi)存消耗。測試主機具有2顆Intel Pentium(R)Dual-Core E5700 CPU,2 GB內(nèi)存,運行Linux操作系統(tǒng),內(nèi)核版本號為3.8.0-32。HTTP報文發(fā)送端和接收端都基于Python2.7.4實現(xiàn),作為在同一主機上運行的2個進程,使用socket進行通信。發(fā)送端以1 KB長度為編碼塊單位,發(fā)送不同長度的編碼報文。而接收端分別運行靜態(tài)解析算法和基于FSM的解析算法,對報文進行提取,提取出的有效內(nèi)容隨即丟棄,以對應(yīng)流服務(wù)器的發(fā)送操作。而靜態(tài)解析算法需接收的整個HTTP報文則存放于主存中。2個算法均不涉及磁盤I/O操作。將算法的處理時延定義為整個報文的接收和解析的總的進程時間,通過Python的timeit模塊進行統(tǒng)計。內(nèi)存消耗通過單獨開啟進程運行ps命令進行統(tǒng)計,ps命令通過讀取/proc目錄下的文件獲得各個進程的相關(guān)信息。Python的command模塊對進程間通信提供了一種實現(xiàn)。它將接收端程序的進程傳遞給ps進程,又將ps運行的結(jié)果傳遞給接收端進程。接收端進程在解析算法執(zhí)行開始前和結(jié)束后分別開啟一個ps進程獲得自身的相關(guān)數(shù)據(jù),通過兩者的比較獲得解析過程中的內(nèi)存消耗。

圖2表明,基于FSM的解析算法明顯縮短了處理時間。原因是其處理過程在最后一個數(shù)據(jù)包接收后很快就能結(jié)束。而靜態(tài)解析算法則在整個報文接收完成后還要回到報文的開頭,對整個報文再進行一遍掃描,并復(fù)制有效內(nèi)容。靜態(tài)解析算法執(zhí)行過程中HTTP報文臨時存放于主存中,可以預(yù)期,如果報文存放于磁盤中,則靜態(tài)解析算法的處理時間會進一步增加,進而更加顯示出基于FSM的解析算法的優(yōu)勢。

圖2 進程處理時延對比

如圖3所示,基于FSM的解析算法大大降低了內(nèi)存損耗,由于不需要拼接整個HTTP報文,程序的內(nèi)存占用主要包括當前任務(wù)分片所對應(yīng)的應(yīng)用層緩沖區(qū),并不隨報文長度的增加而有明顯增長。

圖3 內(nèi)存消耗對比

5 結(jié)束語

本文針對高并發(fā)流媒體應(yīng)用中HTTP Chunked編碼的靜態(tài)解析算法導(dǎo)致的長延時、高開銷等問題,提出一種基于有限狀態(tài)機的并發(fā)解析策略。在單一執(zhí)行環(huán)境下交替處理每一條數(shù)據(jù)流,利用狀態(tài)機恢復(fù)各數(shù)據(jù)流的執(zhí)行現(xiàn)場。對于每個驅(qū)動事件對應(yīng)的數(shù)據(jù),接收后立即解析,從而消除了靜態(tài)策略中報文拼湊過程導(dǎo)致的內(nèi)存拷貝開銷。通過基于Linux主機的實驗測試,驗證了本文方案能夠明顯縮短處理時延,并大大降低內(nèi)存消耗。今后將針對流媒體應(yīng)用中的其他傳輸協(xié)議研究相關(guān)優(yōu)化策略。

[1] Fielding R,Gettys J,Mogul J,et al.Hypertext Transfer Protocol——HTTP/1.1[S].RFC 2616,1999.

[2] Plissonneau L,Biersack E.A Longitudinal View of HTTP Video Streaming Performance[C]//Proceedings of the 3rd Multimedia Systems Conference.New York, USA:ACM Press,2012:203-214.

HTTP Chunked Stream Concurrence Analysis Based on State Machine

LI Mingzhe1,2,CHEN Jun1,WANG Jinlin1,CHEN Xiao1
(1.National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing 100190,China;2.University of Chinese Academy of Sciences,Beijing 100190,China)

In some streaming media applications,a server needs to parse HTTP Chunked encoding messages concurrently.The naive static parsing algorithm does not fit in the efficient event-driven concurrency paradigm,and incurs long delay and several memory copies,leads to high memory and computing overhead.To tackle this problem,a finite state machine based parsing algorithm is presented.One receiving and its following parsing operations are combined into a task slice so that the event-driven model can be applied.Data packets are parsed immediately without caching the whole HTTP message,and therefore one memory copy is reduced.Parsing status is saved into state machines to that the context can be restored after the task slice is over,which solves the broken-field problem.Test results show that this method can significantly reduce memory and computation overhead compared with static parsing.

streaming media;HTTP Chunked encoding;concurrence analysis;event-driven model;finite state machine; memory copy

1000-3428(2015)01-0256-05

A

TP37

10.3969/j.issn.1000-3428.2015.01.048

國家“863”計劃基金資助項目(2011AA01A102);中國科學院戰(zhàn)略性先導(dǎo)科技專項課題基金資助項目(XDA06010302)。

李明哲(1988-),男,博士研究生,主研方向:流媒體技術(shù),網(wǎng)絡(luò)處理器應(yīng)用;陳 君(通訊作者),副研究員、博士;王勁林,研究員、博士生導(dǎo)師;陳 曉,研究員。

2013-11-01

2013-12-22 E-mail:chenj@dsp.ac.cn

中文引用格式:李明哲,陳 君,王勁林,等.基于狀態(tài)機的HTTP Chunked流并發(fā)解析[J].計算機工程,2015,41(1):256-260.

英文引用格式:Li Mingzhe,Chen Jun,Wang Jinlin,et al.HTTP Chunked Stream Concurrence Analysis Based on State Machine[J].Computer Engineering,2015,41(1):256-260.