- nginx 数据结构
1.Hash table
nginx 对虚拟主机的管理使用到了HASH数据结构，假设配置文件里有如下的配置。
Server{
listen 192.168.0.1
server_name xxxx
}
....
Server{
listen 192.168.0.2
server_name xxx1
}
当Nginx以此配置文件正常启动后，如果来了一个客户端请求192.168.0.1的80端口，那么Nginx肯定要查询，看是使用哪个Server配置。为了提高查找效率，所以在启动开始后，Nginx就将根据这些server_name建立起一个Hash数据结构，如下图所示：
上图中，字段buckets指向的就是Hash节点所对应的存储空间，不过这里具体实现时用的是二级指针，那么*buckets本身是一个数组，每一个数组元素用来存储映射到此的Hash节点。由于可能有多个实际元素映射到同一个Hash节点（发生Hash冲突），所以对实际元素再次进行数组形式的组织存储在一个bucket内，这个数组的结束以哨兵元素NULL作为标记，而前面的每一个ngx_hash_elt_t结构对应一个实际元素的存储。这里的实例，整体上也就形成上面所示那样的结构图。对于4个实际元素的Hash 数据结构，只有5个Hash节点，并且正好没有冲突，这主要是归功与ngx_hash_init()函数，通过它的提前测试，确定了Hash节点的个数。具体过程：逐步增加Hash节点数目（对应bucket数目同步增加），然后把所有的实际元素往这些bucket里添加，这有可能发生冲突，但只要冲突的次数可以容忍（即任意一个bucket都还没满），那么就继续填，如果发生有任何一个bucket满溢了，就必须增加Hash节点、增加bucket。如果所有的实际元素都填完没有发生满溢，那么当前的size就是最终的节点数目值。
2. Radix tree
Radix tree(基树)，是一种基于二进制表示健值的二叉查找树，正是由于其健值的这个特点，所以只有在特定的情况下才会使用，典型的应用场景有文件系统、路由表等。Nginx提供的基树仅被geo模块使用，这个模块使用基树来处理IP地址的匹配查找。其次key与节点的对应是从高位向地位逐步匹配的。这是因为geo模块里真正使用的IP网络地址，比如192.168.0.0/16,它们前面bit为才是有效区分位，如果从后往前匹配，会产生大量bit 0,那么导致任何一个IP地址插入到基数上都是32层。ngx_radix32tree_insert()和ngx_radix32tree_delete()中，引入mask就是告诉插入函数只需匹配前多少位。这就是最长前缀匹配。
- nginx配置解析
Nginx配置文件可以认为是一种上下文相关的，高度可扩展的，有作用域。Ngix配置项有简单配置项和复杂配置项，对于复杂配置项而言，Nginx并不做具体的解析与赋值操作，一般只是申请对应的内容空间、切换解析状态，然后递归调用解析函数，而真正将用户配置信息转换为Nginx内控制变量的值，还是依靠那些简单配置项所对应的处理函数来做。
无论是简单配置项还是复杂配置项，他们的项目名和项目值都是有标记（token:这里是指一个配置文件字符串内容中被空格、引号、分号、tab号、括号等）组成的，配置项目名就是一个token,而配置项目值可以是一个、两个和多个token组成。比如：
error_page /.html;
其项目名为error_page,其项目值为404及404.html两个。Nginx配置文件里的注释信息以#作为开头标记。根据Nginx应用本身的特点，我们可以对配置文件作上下文识别和区分，或者说是配置项的作用域。因为虽然某项配置项在同一个上下恩里只可以设置一次，但却可以在不同的上下文里设置多次，以便达到更细粒度的控制。
目前Nginx预定义的配置上下文主要包括main、http、server、location4种（还有其他几种，比如event、upstream、if、mail等）这些上下文相当于一个独立的作用域。Ngix_conf_parse()函数是解析配置文件的关键函数，这个函数是一个间接递归函数，也就是说虽然我们在该函数体内看不到直接的对其本身的调用，但是它执行的一些其它函数（比如ngx_conf_hander()里面会调用ngx_conf_parse()函数），从而形成递归。ngx_conf_parse()解析配置内容的过程分为三个步骤：
- 判断当前解析状态
- 读取配置标记token
- 读取合适数量的token后对其进行实际的处理，也就是将配置值准换为nginx内对应控制变量（nginx转换很简单，直接转换key/value）
所有的配置信息按照模块进行管理，转换之后的变量也按照模块进行管理。同事配置信息还可以继承，如果location中还有location,那么对于在某个层次没有设置的配置选项，它的值应该来自上一层。