关于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 version\r\nHTTP响应:
key: value\r\n
key: value\r\n
...
key: value\r\n
\r\n
body
version status desc\r\n和redis的协议类似，HTTP协议中first-line和headers之间以及header与header之间均通过CRLF('\r''\n')分割，这个需要特别注意，解析的时候可能会带来一定的麻烦。我一直想不通为何不直接用LF分割，因为http-version，header-key，header-value内部并不允许出现LF，因此选择LF完全可以更加简单的解决问题，或许作者当初只用windows吧。
key: value\r\n
key: value\r\n
...
key: value\r\n
\r\n
body
关于header的key和value的具体语义，才是HTTP协议的关键，内容繁杂，需要参考rfc文档，不过这个和HTTP协议并没有太大的关系(下文解释理由)，因此这里不再提及。
HTTP解析器的职责
在进一步描述HTTP解析器之前，我们有必要先弄明白HTTP的职责，需要符合哪些约束条件。以下，以问答的形式进行阐述。
- 【关于HTTP解析的一点思考】HTTP解析器在web server中处于什么位置？
简单来说，它位于TCP服务器和应用框架之间，负责两者之间的数据转换。具体场景为：当HTTP请求到达时，解析器需要根据获取到的buf，对数据进行解析，并最终转换成应用框架能够识别的数据结构，比如HttpRequest、HttpResponse等；反之，它需要将数据结构的内容转换成字符串，并存储在buf中，提交给TCP服务器。
- HTTP解析器是否需要处理header完整的语义？
准确地说，这个问题没有标准答案，和性能指标相关，具体体现在服务器的并发模型。如果HTTP解析是在一个独立的线程中进行，那么可以适当解析header的具体语义；如果HTTP解析是main loop中进行的，那么应该避免进一步的解析，应该将这个过程充分延迟。
总体来说，将header的语义解析延后是相对理性的做法，因为我们未必需要获取某些header的值，且总的解析时间都是包括在响应时间内的。我的选择是解析标准(有一定扩充)中指定的header的key，至于value，只做字符的合法性检查。
- HTTP解析器是否应该处理body？
对于这个问题，我曾经思考了很久，至少我目前的答案是不需要，也不应该。理由大致如下：其一，为了支持multi-part，这部分的解析应该充分延迟；其二，为了应对巨大的body，相对合理的做法是采用类似java中stream之类的做法，而不是一次性分配一大块内存，然后存储起来慢慢解析。
- 常见的约束条件
对于服务器的benchmark而言，尤其是只输出hello world的那种，HTTP解析器在很大程度上决定了性能，可以说，一个性能优异的解析器是高性能web服务器的必要条件，关于这点，大致可以从h2o server中看到点什么。简单来说，如果你想做一款能够应对C10K问题的server，那么解析器的吞吐量至少应该是1w/s，这个指标，对于C语言实现的模块而言，是相对容易的。
除此之外，可用性和安全性，同样是不可忽视的需求，从HTTP解析器的角度考虑可用性，要求HTTP解析器能够应处理任何输入，做到不崩溃，这是最基本的要求。附带上安全性，那么就要求解析器能够识别非法的输入，并提供准确的错误信息。
本节，我将从现存的几个开源实现进行分析，它们分别是http-parser(nodejs)，picohttpparser(h2o server)，以及本人的实现。
- picohttpparser
pico项目的代码并不难理解，不到1000行，就是常规的线性解析，没有任何状态，所做的也只是“断句”，将HTTP请求/响应的各个成分断开，然后存储到用户指定的buf中。值得注意的是，如果我们的机器支持SSE4.2指令，那么可以使用pico的加速功能，关于这条指令，我会专门写一篇博客进行介绍。
然后，作者在README中给出了一张很给力的benchmark图，号称性能超过http-parser 3倍，开启加速后，结果是快5倍。
确实是很惊人的成绩，我粗略总结了下原因：
- 只进行断句，对header不做字符检查，不识别任何header-key；
- 不在解析器内部分配任何内存，即不调用任何malloc；
- 对buf的内容有一定假设，不判断buf是否读完。
漂亮的分数是有代价的，或许pico是为 单进程main loop + 线程池 这种模型准备的，但我肯定不会用它。
- http-parser
话说作者原本的目标就是开发一个web server，然后加了v8引擎后，就成了nodejs。。。
整体的实现方式是添加大量状态，switch语句，比如如下形式：
H
HT
HTT
HTTP
HTTP1
HTTP1/
这种做法的优点是对非阻塞API的支持比较好，缺点是过于冗长，代码可读性不太高，对此作者采用了一些技巧，比如method根据第一个字母进行识别，貌似曾今见过有人拿这个黑nodejs。。
从性能指标上来看，http-parser的性能还是很优秀的，毕竟功能加强了很多。
不过，需要注意，switch的开销是存在的，尤其是在编译时不开优化，此时swich和if-else无异，即使开了优化，还是存在一定的开销，比如计算偏移，goto等。
- 基于协程的实现
基于协程的实现，性能不会太低，虽然协程的resume和yield的开销介于普通调用和系统调用之间，但是时间比重占的并不高。不过使用协程有个致命的问题，那就是内存占用过大，大量应用是不太现实的，貌似lwan就用了这种方法，不知道基于ucontext的协程实现性能开销如何。
- 基于表驱动的实现
我当前的做法就是大量应用表驱动，主要体现在：
- 实现记录合法的ascii表，解析式的查询开销为O(1)，而且是严格的；
- 事先对各个header-key做hash处理，在处理时，只需要对每个相关的字符做hash处理，并在读到分割符后，进行查表，开销为O(1)，基本严格。
从目前的数据来看，当前实现的总体性能大概是http-parser的1.3倍，我使用了特殊的数据结构来尽可能避免在解析时分配内存，用time统计运行时间时，sys的开销基本为0。无论是出于时间开销，还是内存碎片的角度考虑，都应尽量避免大量分配小块内存。
优化建议
开发完原型后，我做了下简单的benchmark，对比pico，竟然被完爆。。。然后花了2天时间进行分析优化，总结了点内容，或许对各位有一定帮助。
- switch的开销
这个在上文中已经提及，一定要开优化，尽可能使case后的数字连续分布，主流的做法是写在enum内。总体而言，对于不是很复杂的if-else语句，使用switch替换，并不能带来显著提升，反而会使代码变得比较难读。
- 避免分配内存
尤其是在循环内部，应该尽量避免分配频繁分配内存，这么做会造成内存碎片，并且malloc最终会使用系统调用，当初我的benchmark中，malloc就“贡献”了近1/4的时间开销。
- 如果你的程序适合用SSE4.2中的指令加速，那么可以一试，运用得当，应该能够加速3倍左右(intel官方给的数据)
- 对结构体中的内容做“本地化处理”
尤其是需要在循环中大量操作结构体时，一定要注意，因为它也会“贡献”很大比重的开销。这里所谓“本地化”，即使用函数的局部变量代替结构体中的数据，在函数返回时，写入。示例如下：
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后是否会做相关工作(或许未来可以描述一下)，所谓的本地化，一定要确保数据源和临时副本一致，切记。
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- 四首关于旅行记忆的外文歌曲
- 画解算法（1.|画解算法：1. 两数之和）
- 醒不来的梦
- 关于自我为中心的一点感想
- ts泛型使用举例
- 「按键精灵安卓版」关于全分辨率脚本的一些理解（非游戏app）
- 关于Ruby的杂想
- 关于读书的思考
- https请求被提早撤回