Cloudflare的HTML解析歷史（中）

本文，我們將詳細(xì)介紹如何基于LazyHTML的思想構(gòu)建新的流量重寫器。

避免解碼：一切都是ASCII

現(xiàn)在我們有了一個(gè)流量令牌生成器，我們想要確保它足夠快，以便用戶在進(jìn)行解析器和轉(zhuǎn)換時(shí)不會(huì)注意到頁(yè)面的任何變慢。否則，它將完全繞過(guò)我們想要嘗試的任何優(yōu)化。

它不僅會(huì)因?yàn)榻獯a和重新編碼任何修改后的HTML內(nèi)容而導(dǎo)致性能下降，而且還會(huì)由于確定字符編碼所需的多個(gè)潛在編碼信息來(lái)源(包括嗅探前1 KB的內(nèi)容)而使我們的實(shí)現(xiàn)變得非常復(fù)雜。

HTML標(biāo)準(zhǔn)規(guī)范只允許在編碼標(biāo)準(zhǔn)中定義的編碼，如果仔細(xì)查看這些編碼，以及對(duì)HTML規(guī)范的“字符編碼”部分的說(shuō)明，我們會(huì)發(fā)現(xiàn)除UTF-16和ISO-2022-JP以外，所有這些編碼均與ASCII兼容。

這意味著任何ASCII文本都將以與ASCII中完全相同的編碼形式表示，并且任何非ASCII文本將由ASCII范圍之外的字節(jié)表示。此屬性使我們可以安全地標(biāo)記、比較甚至修改原始HTML，而無(wú)需解碼甚至不知道它包含哪種特定編碼，HTML語(yǔ)法中的所有標(biāo)記邊界都可能由ASCII字符表示。

我們需要通過(guò)嗅探來(lái)檢測(cè)UTF-16，并且在不修改的情況下對(duì)這些文檔進(jìn)行解碼或跳過(guò)。我們選擇后者是為了避免UTF-16常見(jiàn)的潛在的安全敏感漏洞，幸運(yùn)的是，字符編碼在已知字符編碼中只占不到0.1%。

不過(guò)，HTML標(biāo)記化規(guī)范要求在解析期間用U+FFFD(替換字符)替換U+0000 (NUL)字符。大概是為了防止舊引擎的C實(shí)現(xiàn)中的漏洞而添加的，它可以將以ASCII / UTF-8 / ...編碼為0x00字節(jié)的NUL字符視為字符串的結(jié)尾（以null結(jié)尾的字符串）。因?yàn)閁+FFFD不在ASCII范圍內(nèi)，并且將由采用不同編碼的不同字節(jié)序列表示。由于我們不知道文檔的編碼，因此將導(dǎo)致輸出被破壞。

幸運(yùn)的是，由于瀏覽器不同，也不必?fù)?dān)心擔(dān)心NUL字符在字符串一樣：

typedef struct {
   const char *data;
   size_t length;
} lhtml_string_t;

內(nèi)容類型漏洞

其實(shí)安全分析人員只想花時(shí)間解析、解碼和重寫實(shí)際的HTML，而不是破壞圖像或JSON。因此是他們?nèi)绾未_定內(nèi)容是否為HTML文檔。你可以僅使用Content-Type作為示例嗎？在源代碼中留下的注釋最能描述實(shí)際情況。

在撰寫本文時(shí)，這是一個(gè)糟糕而可怕的地方。如果這不斷變化，網(wǎng)站變得更加符合標(biāo)準(zhǔn)，請(qǐng)像我嘗試的那樣將其刪除。許多網(wǎng)站使用PHP來(lái)設(shè)置Content-Type：text / html by默認(rèn)。如果您不提供自己的信息，則沒(méi)有錯(cuò)誤或警告一，所以大多數(shù)網(wǎng)站都不會(huì)去更改它并提供服務(wù)JSON API響應(yīng)，私鑰和圖像等二進(jìn)制數(shù)據(jù)使用默認(rèn)的Content-Type，我們很樂(lè)意嘗試解析和轉(zhuǎn)換。這不僅會(huì)損害性能，還會(huì)損害性能只要內(nèi)部有一些序列，就很容易破壞響應(yīng)數(shù)據(jù)本身它恰好看起來(lái)像是我們感興趣的有效HTML標(biāo)簽當(dāng)JSON中包含有效的HTML時(shí)，情況就更糟了。我們將其視為此類，然后將隨機(jī)腳本附加到末尾打破對(duì)流行網(wǎng)絡(luò)應(yīng)用至關(guān)重要的API。該黑客試圖通過(guò)確保第一個(gè)有效字符（忽略空格和BOM）實(shí)際上是<<--增加了確實(shí)是HTML的機(jī)會(huì)。這樣，我們就可以跳過(guò)一些其他的響應(yīng)可以由瀏覽器呈現(xiàn)為AJAX響應(yīng)的一部分，但這仍然比相反的情況好。

你可能會(huì)認(rèn)為這是一種罕見(jiàn)的情況，然而，我們的觀察表明，在Cloudflare提供的“text / html”內(nèi)容類型的流量中，近25%不太可能是html。

事實(shí)證明，“text/html”內(nèi)容類型提供了相當(dāng)數(shù)量的XML內(nèi)容，當(dāng)作為html處理時(shí)，這些內(nèi)容并不總是能夠被正確處理。

隨著時(shí)間的流逝，對(duì)二進(jìn)制數(shù)據(jù)、JSON、AMP和正確識(shí)別HTML片段的緊急緩解措施導(dǎo)致了內(nèi)容嗅探邏輯，如下所示。

可以看到，這是形式規(guī)范與現(xiàn)實(shí)之間分歧的一個(gè)很好的例子。

對(duì)標(biāo)記名稱比較優(yōu)化

但是僅進(jìn)行快速解析是不夠的，由于我們已經(jīng)具有使用解析器的輸出，對(duì)其進(jìn)行重寫并將其反饋給序列化的功能。而且解析器具有的所有內(nèi)存和時(shí)間限制也適用于此代碼，因?yàn)樗峭粌?nèi)容處理管道的一部分。

比較已解析的HTML標(biāo)記名稱是一個(gè)常見(jiàn)需求，例如確定是否應(yīng)重寫當(dāng)前標(biāo)記。使用常規(guī)的按字節(jié)比較會(huì)比較簡(jiǎn)單，這可能需要遍歷整個(gè)標(biāo)記名。在大多數(shù)情況下，通過(guò)使用特殊設(shè)計(jì)的哈希算法，我們能夠在大多數(shù)情況下將這個(gè)操作縮小到單個(gè)整數(shù)比較指令。

所有標(biāo)準(zhǔn)HTML元素的標(biāo)記名稱僅包含字母ASCII字符和1至6的數(shù)字（在帶編號(hào)的標(biāo)頭標(biāo)記中，即< h1 >-< h6 >）。標(biāo)記名稱的比較不區(qū)分大小寫，因此我們只需要26個(gè)字符即可表示字母字符。使用與算術(shù)編碼相同的基本思想，我們可以僅使用5位來(lái)表示標(biāo)記名稱的可能的32個(gè)字符中的每個(gè)字符，因此，在64位整數(shù)中，floor（64/5）= 12個(gè)字符適合對(duì)于所有標(biāo)準(zhǔn)標(biāo)記名稱和滿足相同要求的任何其他標(biāo)記名稱而言，已足夠！最重要的是，我們甚至不需要額外遍歷標(biāo)記名稱來(lái)對(duì)其進(jìn)行哈希處理，我們可以在解析標(biāo)記名稱時(shí)使用逐字節(jié)輸入的方式來(lái)做到這一點(diǎn)。

然而，這個(gè)哈希算法有一個(gè)問(wèn)題，但問(wèn)題的根源不是那么明顯：要使所有32個(gè)字符都適合5位，我們需要使用所有可能的位組合，包括00000。這意味著如果標(biāo)記名的前導(dǎo)字符被表示出來(lái)如果設(shè)置為00000，那么我們將無(wú)法區(qū)分該字符后續(xù)重復(fù)的不同數(shù)量。

例如，考慮到‘a(chǎn)’被編碼為00000，而 ‘b’ 被編碼為00001：

幸運(yùn)的是，我們知道HTML語(yǔ)法不允許標(biāo)記名稱的第一個(gè)字符為ASCII字母字符以外的任何其他字符，因此保留數(shù)字從0到5（00000b-00101b）的數(shù)字和6到31的數(shù)字（00110b- 11111b）解決了ASCII字母字符的問(wèn)題。

LazyHTML

LazyHTML是一款基于Layui的極速后臺(tái)開發(fā)模板，LazyAdmin以“小巧、精干、輕量”為設(shè)計(jì)理念，不用太多復(fù)雜的功能，有一套強(qiáng)大和穩(wěn)定的Base管理機(jī)制足以，以簡(jiǎn)潔的基礎(chǔ)Base程序+高級(jí)專業(yè)定制為開發(fā)目的。

在考慮了上述所有內(nèi)容之后，創(chuàng)建了LazyHTML庫(kù)。它是一種快速流量HTML解析器和序列化器，具有基于令牌的C-API，該令牌源自用Ragel編寫的HTML5詞法分析器(Lexer)。它提供了可插入的轉(zhuǎn)換管道，以允許將多個(gè)轉(zhuǎn)換處理程序鏈接在一起。

以下是轉(zhuǎn)換鏈接的href屬性的函數(shù)示例：

// define static string to be used for replacements
static const lhtml_string_t REPLACEMENT = {
   .data = "[REPLACED]",
   .length = sizeof("[REPLACED]") - 1
};

static void token_handler(lhtml_token_t *token, void *extra /* this can be your state */) {
  if (token->type == LHTML_TOKEN_START_TAG) { // we're interested only in start tags
    const lhtml_token_starttag_t *tag = &token->start_tag;
    if (tag->type == LHTML_TAG_A) { // check whether tag is of type       const size_t n_attrs = tag->attributes.count;
      const lhtml_attribute_t *attrs = tag->attributes.items;
      for (size_t i = 0; i < n_attrs; i++) { // iterate over attributes
        const lhtml_attribute_t *attr = &attrs[i];
        if (lhtml_name_equals(attr->name, "href")) { // match the attribute name
          attr->value = REPLACEMENT; // set the attribute value
        }
      }
    }
  }
  lhtml_emit(token, extra); // pass transformed token(s) to next handler(s)
}

與以前的解析器不同，它沒(méi)有對(duì)HTTP存檔的2382625個(gè)文檔中的任何一個(gè)進(jìn)行幫助，盡管0.2％的文檔超出了預(yù)期的緩沖限制，因?yàn)樗麄儗?shí)際上是JavaScript或RSS或其他類型的內(nèi)容與Content-Type: text/htm的不正確搭配，并且由于任何內(nèi)容都是有效的HTML5，因此解析器嘗試解析例如a<b; x=3; y=4作為帶有屬性的不完整標(biāo)記。

至于基準(zhǔn)測(cè)試，在2016年9月，通過(guò)一個(gè)示例將HTML規(guī)范本身（7.9 MB HTML文件）轉(zhuǎn)換為靜態(tài)值，該示例通過(guò)將每個(gè)（僅在那些標(biāo)記中有該屬性）替換為HTML規(guī)范。將其與少數(shù)幾個(gè)現(xiàn)有的和流行的HTML解析器進(jìn)行了比較（僅使用令牌化模式進(jìn)行了公平的比較，因此它們不需要構(gòu)建AST等），下面是100次迭代的毫秒數(shù)，Lazy模式意味著我們盡可能使用原始字符串，另一個(gè)序列化每個(gè)令牌進(jìn)行比較。

結(jié)果表明，LazyHTML解析器的速度大約快一個(gè)數(shù)量級(jí)。

接下來(lái)，我會(huì)接著介紹了如何基于LazyHTML的思想構(gòu)建新的流量重寫器。比如更易于使用的CSS選擇器API，它為Cloudflare Workers HTMLRewriter JavaScript API提供了后端。

顯然，使用Cloudflare Workers的開發(fā)人員希望使用與內(nèi)部使用的相同的HTML重寫功能，但是可以通過(guò)JavaScript API進(jìn)行訪問(wèn)。

接下來(lái)我們將介紹在Rust中使用基于CSS選擇器的API構(gòu)建流式HTML重寫器/解析器的過(guò)程，它用作Cloudflare Workers HTMLRewriter的后端。我們已經(jīng)開源了該庫(kù)（LOL HTML），因?yàn)樗部梢杂米鳘?dú)立的HTML重寫/解析庫(kù)。

與以前的重寫器LazyHTML相比，主要的變化是雙重解析器體系結(jié)構(gòu)，該體系結(jié)構(gòu)需要克服在將令牌傳播到工作程序運(yùn)行時(shí)封裝/解封每個(gè)令牌的額外性能開銷。下文描述了一個(gè)CSS選擇器匹配引擎，該引擎是由虛擬機(jī)對(duì)正則表達(dá)式匹配的方法啟發(fā)而來(lái)的。

v2：CSS選擇器匹配引擎效率更高

2017年，Cloudflare推出了一個(gè)邊緣計(jì)算平臺(tái)——Cloudflare Workers。這樣，客戶要求Cloudflare Workers的開發(fā)人員在內(nèi)部使用相同的HTML重寫功能也就不足為奇了。Cloudflare Workers 為開發(fā)人員提供了接近客戶的第三個(gè)位置來(lái)部署代碼：Cloudflare 不斷擴(kuò)展的全球網(wǎng)絡(luò)的邊緣，因此引入了云數(shù)據(jù)中心的強(qiáng)大功能和靈活性，以及大規(guī)模分布式系統(tǒng)的冗余，而且僅在毫秒之間就能傳給幾乎每一位互聯(lián)網(wǎng)用戶。

這樣，開發(fā)人員在Workers中重寫HTML，為此你需要第三方JavaScript程序包（例如Cheerio）。由于前一篇文章中描述的延遲，速度和內(nèi)存方面的考慮，這些軟件包不適用于邊緣的HTML重寫。

JavaScript確實(shí)非?？?，但是對(duì)于某些任務(wù)，它的性能仍然無(wú)法與本地代碼相比——解析就是其中之一?？蛻敉ǔＰ枰彌_頁(yè)面的整個(gè)內(nèi)容來(lái)進(jìn)行重寫，從而導(dǎo)致相當(dāng)大的輸出延遲和內(nèi)存消耗，這些消耗常常超過(guò)Workers運(yùn)行時(shí)強(qiáng)制執(zhí)行的內(nèi)存限制。

我們開始考慮如何在Workers中重用該技術(shù)，就解析性能而言，LazyHTML非常適合，但存在兩個(gè)問(wèn)題：

1.API人體工程學(xué)：LazyHTML生成HTML令牌流。這足以滿足我們的內(nèi)部需求，但是，對(duì)于普通用戶而言，它不如Cheerio類似于jquery的API那樣方便。

2.性能：盡管LazyHTML速度非?？欤cWorkers運(yùn)行時(shí)的集成甚至增加了更多限制。 LazyHTML就像一個(gè)簡(jiǎn)單的解析-修改-序列化管道操作，這意味著它為頁(yè)面的整個(gè)內(nèi)容生成令牌。然后，所有這些令牌都必須傳播到Workers運(yùn)行時(shí)，并包裝在JavaScript對(duì)象中，然后解開包裝并反饋給LazyHTML進(jìn)行序列化。這是一個(gè)非常耗時(shí)的操作，它將使LazyHTML的性能優(yōu)勢(shì)化為烏有。

配有V8的LazyHTML

LOL HTML

我們需要一種新的思路，并且要根據(jù)Workers的要求進(jìn)行設(shè)計(jì)，并使用一種具有本地速度和安全保證的語(yǔ)言。不過(guò)，在進(jìn)行解析時(shí)很容易搬起石頭砸自己的腳。 Rust是顯而易見(jiàn)的選擇，因?yàn)樗峁┝吮镜厮俣群妥罴训膬?nèi)存安全保證，從而最大程度地減少了不受信任的輸入的攻擊面。在可能的情況下，低輸出延遲的HTML rewriter (LOL HTML)使用了之前為L(zhǎng)azyHTML開發(fā)的所有優(yōu)化，比如標(biāo)記名稱哈希。

下一篇文章我們接著講LOL HTML設(shè)計(jì)的各種思路，比如雙解析器架構(gòu)思路。