关于HTTP解析的一点思考

似乎已经很久没有提到关于服务器的消息了,其实我一直都在写,只是有时事情比较多,会耽搁一点时间。

在使用C重写前,我就已经用Dlang实现了近2个版本的HTTP解析器,换成C之后,又换了几种思路,期间也参考现有的几种实现,可以说是有点积累,现总结成文,记录一下。

注:如下所指的HTTP均指代HTTP/1.1,不涉及HTTP/2的内容。

HTTP协议特征分析

HTTP/1.1是目前使用最为广泛的应用层协议之一,当然如今HTTP/2的标准已经出来,但是尚未普及,有些特性有待考验,我就不吃螃蟹了。。

HTTP协议是典型的Key-Value类型的文本协议,当然还有first-line和body,总体而言解析并不复杂,并且我们也不要求规整的错误提示和文法验证,因此LL(1)和LALR(1)在这里基本无用武之地。HTTP的大致格式如下:

HTTP请求:

method path versionrn

key: value\r\n
key: value\r\n
...
key: value\r\n
\r\n
body

HTTP响应:

version status descrn

key: value\r\n
key: value\r\n
...
key: value\r\n
\r\n
body

和redis的协议类似,HTTP协议中first-line和headers之间以及header与header之间均通过CRLF('r''n')分割,这个需要特别注意,解析的时候可能会带来一定的麻烦。我一直想不通为何不直接用LF分割,因为http-version,header-key,header-value内部并不允许出现LF,因此选择LF完全可以更加简单的解决问题,或许作者当初只用windows吧。

关于header的key和value的具体语义,才是HTTP协议的关键,内容繁杂,需要参考rfc文档,不过这个和HTTP协议并没有太大的关系(下文解释理由),因此这里不再提及。

HTTP解析器的职责

在进一步描述HTTP解析器之前,我们有必要先弄明白HTTP的职责,需要符合哪些约束条件。以下,以问答的形式进行阐述。

  1. HTTP解析器在web server中处于什么位置?

    简单来说,它位于TCP服务器和应用框架之间,负责两者之间的数据转换。具体场景为:当HTTP请求到达时,解析器需要根据获取到的buf,对数据进行解析,并最终转换成应用框架能够识别的数据结构,比如HttpRequest、HttpResponse等;反之,它需要将数据结构的内容转换成字符串,并存储在buf中,提交给TCP服务器。
    
  2. HTTP解析器是否需要处理header完整的语义?

    准确地说,这个问题没有标准答案,和性能指标相关,具体体现在服务器的并发模型。如果HTTP解析是在一个独立的线程中进行,那么可以适当解析header的具体语义;如果HTTP解析是main loop中进行的,那么应该避免进一步的解析,应该将这个过程充分延迟。
    
    总体来说,将header的语义解析延后是相对理性的做法,因为我们未必需要获取某些header的值,且总的解析时间都是包括在响应时间内的。我的选择是解析标准(有一定扩充)中指定的header的key,至于value,只做字符的合法性检查。
    
  3. HTTP解析器是否应该处理body?

    对于这个问题,我曾经思考了很久,至少我目前的答案是不需要,也不应该。理由大致如下:其一,为了支持multi-part,这部分的解析应该充分延迟;其二,为了应对巨大的body,相对合理的做法是采用类似java中stream之类的做法,而不是一次性分配一大块内存,然后存储起来慢慢解析。
    
  4. 常见的约束条件

    对于服务器的benchmark而言,尤其是只输出hello world的那种,HTTP解析器在很大程度上决定了性能,可以说,一个性能优异的解析器是高性能web服务器的必要条件,关于这点,大致可以从h2o server中看到点什么。简单来说,如果你想做一款能够应对C10K问题的server,那么解析器的吞吐量至少应该是1w/s,这个指标,对于C语言实现的模块而言,是相对容易的。
    
    除此之外,可用性和安全性,同样是不可忽视的需求,从HTTP解析器的角度考虑可用性,要求HTTP解析器能够应处理任何输入,做到不崩溃,这是最基本的要求。附带上安全性,那么就要求解析器能够识别非法的输入,并提供准确的错误信息。
    

HTTP解析器编写的几种方法

本节,我将从现存的几个开源实现进行分析,它们分别是http-parser(nodejs),picohttpparser(h2o server),以及本人的实现。

  1. picohttpparser

picohttpparser作为h2o的HTTP解析器,拥有比较出色的性能,当然这也正是h2o的目标。

pico项目的代码并不难理解,不到1000行,就是常规的线性解析,没有任何状态,所做的也只是“断句”,将HTTP请求/响应的各个成分断开,然后存储到用户指定的buf中。值得注意的是,如果我们的机器支持SSE4.2指令,那么可以使用pico的加速功能,关于这条指令,我会专门写一篇博客进行介绍。

然后,作者在README中给出了一张很给力的benchmark图,号称性能超过http-parser 3倍,开启加速后,结果是快5倍。

确实是很惊人的成绩,我粗略总结了下原因:

  1. 只进行断句,对header不做字符检查,不识别任何header-key;
  2. 不在解析器内部分配任何内存,即不调用任何malloc;
  3. 对buf的内容有一定假设,不判断buf是否读完。

大家确实可以在程序中用pico,但前提是需要做一些额外的工作:你需要在buf中存有足够的内容,因为pico对于非阻塞的适应性不好;你需要分配足够大的buf来存储header、path,谁都不知道到底会有多少条header;你需要在pico处理后,进一步识别数组中保存的是什么header,当然也免不了合法性检查。

漂亮的分数是有代价的,或许pico是为 单进程main loop + 线程池 这种模型准备的,但我肯定不会用它。

  1. http-parser

http-parser是nodejs的HTTP解析器,比较成熟,代码量在2000+,能够识别主要的method,header-key,能够在解析时完成path和host的解析,使用回调注册的方式进行方法触发(作者又写了个没有回调的版本,hl),包括内存分配,整体风格和libuv差不多。

话说作者原本的目标就是开发一个web server,然后加了v8引擎后,就成了nodejs。。。

整体的实现方式是添加大量状态,switch语句,比如如下形式:

H
HT
HTT
HTTP
HTTP1
HTTP1/

这种做法的优点是对非阻塞API的支持比较好,缺点是过于冗长,代码可读性不太高,对此作者采用了一些技巧,比如method根据第一个字母进行识别,貌似曾今见过有人拿这个黑nodejs。。

从性能指标上来看,http-parser的性能还是很优秀的,毕竟功能加强了很多。

不过,需要注意,switch的开销是存在的,尤其是在编译时不开优化,此时swich和if-else无异,即使开了优化,还是存在一定的开销,比如计算偏移,goto等。

  1. 基于协程的实现

协程的作用就是将非阻塞API的问题去除,那么基于协程的实现是最简单的,在使用Dlang开发的时候,我实现过对应的版本,代码量不足300行,不需要任何状态。

基于协程的实现,性能不会太低,虽然协程的resume和yield的开销介于普通调用和系统调用之间,但是时间比重占的并不高。不过使用协程有个致命的问题,那就是内存占用过大,大量应用是不太现实的,貌似lwan就用了这种方法,不知道基于ucontext的协程实现性能开销如何。

  1. 基于表驱动的实现

表驱动这个词,是我在看完《code complete》(代码大全)后,记得最牢的一个,因为它确实很有用,个别同学可别再把它和转移表或者跳转表的概念搞混了。

我当前的做法就是大量应用表驱动,主要体现在:

  1. 实现记录合法的ascii表,解析式的查询开销为O(1),而且是严格的;
  2. 事先对各个header-key做hash处理,在处理时,只需要对每个相关的字符做hash处理,并在读到分割符后,进行查表,开销为O(1),基本严格。

当然这也是http-parser的做法,只不过它并未使用hash来处理header-key。值得一体的是,我觉得可能hash在计算时,开销并不比switch小,有待进一步验证。

从目前的数据来看,当前实现的总体性能大概是http-parser的1.3倍,我使用了特殊的数据结构来尽可能避免在解析时分配内存,用time统计运行时间时,sys的开销基本为0。无论是出于时间开销,还是内存碎片的角度考虑,都应尽量避免大量分配小块内存。

优化建议

开发完原型后,我做了下简单的benchmark,对比pico,竟然被完爆。。。然后花了2天时间进行分析优化,总结了点内容,或许对各位有一定帮助。

  1. switch的开销

    这个在上文中已经提及,一定要开优化,尽可能使case后的数字连续分布,主流的做法是写在enum内。总体而言,对于不是很复杂的if-else语句,使用switch替换,并不能带来显著提升,反而会使代码变得比较难读。

  2. 避免分配内存

    尤其是在循环内部,应该尽量避免分配频繁分配内存,这么做会造成内存碎片,并且malloc最终会使用系统调用,当初我的benchmark中,malloc就“贡献”了近1/4的时间开销。

  3. 如果你的程序适合用SSE4.2中的指令加速,那么可以一试,运用得当,应该能够加速3倍左右(intel官方给的数据)
  4. 对结构体中的内容做“本地化处理”

    尤其是需要在循环中大量操作结构体时,一定要注意,因为它也会“贡献”很大比重的开销。这里所谓“本地化”,即使用函数的局部变量代替结构体中的数据,在函数返回时,写入。示例如下:

struct XXX {
    int anum;
    ...
};
void foobar(struct XXX* x) {
    int anum = x->anum;
    for(int i = 0; i < 10000000; ++1) {
        ++anum;
    }
    x->anum = anum;
}

我还尚未仔细对比过gcc开-O2后是否会做相关工作(或许未来可以描述一下),所谓的本地化,一定要确保数据源和临时副本一致,切记。

说两句: