nginx loacation 与 server 的查询优化

2015-09-20 22:51:46   最后更新: 2015-09-22 21:09:53   访问数量:1229




 

上一篇日志中,我们已经了解了 nginx HTTP 配置文件解析的流程,即 ngx_http_block 函数的执行过程

http 模块配置解析

 

接下来,为了 server 和 location 配置的快速查询,ngx_http_block 分别对他们进行了优化

 

在配置文件解析过程中,各个 server 配置中的 location 配置各自形成了双向链表,由 ngx_http_core_loc_conf_t 结构中的 locations 指针指向

 

 

在 ngx_http_init_locations 函数中,递归的对这些 location 配置调用 ngx_queue_sort 进行了排序

并且,对于没有配置名称的 location 拆分为单独的双向链表进行保存,防止查询时遗漏

// static ngx_int_t // ngx_http_init_locations(ngx_conf_t *cf, ngx_http_core_srv_conf_t *cscf, // ngx_http_core_loc_conf_t *pclcf) // 对所有 location 配置结构 ngx_http_core_conf_t 组成双向链表进行递归排序 {{{ static ngx_int_t ngx_http_init_locations(ngx_conf_t *cf, ngx_http_core_srv_conf_t *cscf, ngx_http_core_loc_conf_t *pclcf) { ngx_uint_t n; ngx_queue_t *q, *locations, *named, tail; ngx_http_core_loc_conf_t *clcf; ngx_http_location_queue_t *lq; ngx_http_core_loc_conf_t **clcfp; #if (NGX_PCRE) ngx_uint_t r; ngx_queue_t *regex; #endif locations = pclcf->locations; if (locations == NULL) { return NGX_OK; } ngx_queue_sort(locations, ngx_http_cmp_locations); named = NULL; n = 0; #if (NGX_PCRE) regex = NULL; r = 0; #endif for (q = ngx_queue_head(locations); q != ngx_queue_sentinel(locations); q = ngx_queue_next(q)) { lq = (ngx_http_location_queue_t *) q; clcf = lq->exact ? lq->exact : lq->inclusive; if (ngx_http_init_locations(cf, NULL, clcf) != NGX_OK) { return NGX_ERROR; } #if (NGX_PCRE) if (clcf->regex) { r++; if (regex == NULL) { regex = q; } continue; } #endif if (clcf->named) { n++; if (named == NULL) { named = q; } continue; } if (clcf->noname) { break; } } // 出现了无名的 location 则拆分双向链表 if (q != ngx_queue_sentinel(locations)) { ngx_queue_split(locations, q, &tail); } if (named) { clcfp = ngx_palloc(cf->pool, (n + 1) * sizeof(ngx_http_core_loc_conf_t *)); if (clcfp == NULL) { return NGX_ERROR; } cscf->named_locations = clcfp; for (q = named; q != ngx_queue_sentinel(locations); q = ngx_queue_next(q)) { lq = (ngx_http_location_queue_t *) q; *(clcfp++) = lq->exact; } *clcfp = NULL; ngx_queue_split(locations, named, &tail); } #if (NGX_PCRE) if (regex) { clcfp = ngx_palloc(cf->pool, (r + 1) * sizeof(ngx_http_core_loc_conf_t *)); if (clcfp == NULL) { return NGX_ERROR; } pclcf->regex_locations = clcfp; for (q = regex; q != ngx_queue_sentinel(locations); q = ngx_queue_next(q)) { lq = (ngx_http_location_queue_t *) q; *(clcfp++) = lq->exact; } *clcfp = NULL; ngx_queue_split(locations, regex, &tail); } #endif return NGX_OK; } // }}}

 

 

为了 location 的快速查询与匹配,nginx 为所有 location 配置创建了一个三叉排序树结构

 

三叉排序树结构 -- ngx_http_location_tree_node_s

三叉排序树顾名思义,一个父节点拥有三个子树,其中左子树 value 小于父节点 value,右子树 value 大于父节点 value,而父节点 value 是中间子树(tree)value 的前缀

// struct ngx_http_location_tree_node_s // location 三叉排序树结构 {{{ struct ngx_http_location_tree_node_s { ngx_http_location_tree_node_t *left; // 左节点 ngx_http_location_tree_node_t *right; // 右节点 ngx_http_location_tree_node_t *tree; // 中间节点 ngx_http_core_loc_conf_t *exact; // 前缀 ngx_http_core_loc_conf_t *inclusive; // 范围匹配 u_char auto_redirect; u_char len; // value 的长度 u_char name[1]; // value 首字母 }; // }}}

 

 

有了上述结构,nginx 在 ngx_http_init_locations 之后,紧接着对这个已经排序好的双向链表进行了树的构建

 

处理前缀节点 -- ngx_http_create_locations_list

// static void // ngx_http_create_locations_list(ngx_queue_t *locations, ngx_queue_t *q) // A 节点是 B 的前缀,则使 A 节点成为 B 节点的前缀节点 {{{ static void ngx_http_create_locations_list(ngx_queue_t *locations, ngx_queue_t *q) { u_char *name; size_t len; ngx_queue_t *x, tail; ngx_http_location_queue_t *lq, *lx; // 为空直接返回 if (q == ngx_queue_last(locations)) { return; } lq = (ngx_http_location_queue_t *) q; // 对于精准匹配的节点则不会称为某些节点的前缀,直接跳过该节点 if (lq->inclusive == NULL) { ngx_http_create_locations_list(locations, ngx_queue_next(q)); return; } len = lq->name->len; name = lq->name->data; for (x = ngx_queue_next(q); x != ngx_queue_sentinel(locations); x = ngx_queue_next(x)) { lx = (ngx_http_location_queue_t *) x; // 长度不同则不是相同后缀 if (len > lx->name->len || ngx_filename_cmp(name, lx->name->data, len) != 0) { break; } } q = ngx_queue_next(q); if (q == x) { ngx_http_create_locations_list(locations, x); return; } // location从q节点开始分割,location 成为 q 节点之前的一段 list ngx_queue_split(locations, q, &tail); // q 节点的 list 初始为从 q 节点开始到最后的一段 list ngx_queue_add(&lq->list, &tail); if (x == ngx_queue_sentinel(locations)) { ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list)); return; } // 再次分割,lq->list剩下p.next到x.prev的一段了 ngx_queue_split(&lq->list, x, &tail); // 放到location 中去 ngx_queue_add(locations, &tail); //递归 p.next 到 x.prev ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list)); // 递归 x.next 到 location 最后 ngx_http_create_locations_list(locations, x); } // }}}

 

这段代码让所有的被其他 location 前缀的节点成为了对应前缀的子节点,这样,三叉排序树结构的 tree 字段在之后的处理中无需在顾及

也就说,这之后,三叉排序树的创建过程退化成为了一个平衡二叉查找树的创建

 

这一过程结束后,ngx_http_location_queue_t 的结构变成了

 

 

三叉排序树创建 -- ngx_http_create_locations_tree

// static ngx_http_location_tree_node_t * // ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations, // 创建三叉排序树 {{{ static ngx_http_location_tree_node_t * ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations, size_t prefix) { size_t len; ngx_queue_t *q, tail; ngx_http_location_queue_t *lq; ngx_http_location_tree_node_t *node; // 取中间节点 q = ngx_queue_middle(locations); lq = (ngx_http_location_queue_t *) q; // len是name减去prefix的长度 len = lq->name->len - prefix; node = ngx_palloc(cf->pool, offsetof(ngx_http_location_tree_node_t, name) + len); if (node == NULL) { return NULL; } node->left = NULL; node->right = NULL; node->tree = NULL; node->exact = lq->exact; node->inclusive = lq->inclusive; node->auto_redirect = (u_char) ((lq->exact && lq->exact->auto_redirect) || (lq->inclusive && lq->inclusive->auto_redirect)); node->len = (u_char) len; // 不存储公共前缀 ngx_memcpy(node->name, &lq->name->data[prefix], len); ngx_queue_split(locations, q, &tail); if (ngx_queue_empty(locations)) { /* * ngx_queue_split() insures that if left part is empty, * then right one is empty too */ goto inclusive; } // 递归构建node的左节点 node->left = ngx_http_create_locations_tree(cf, locations, prefix); if (node->left == NULL) { return NULL; } ngx_queue_remove(q); if (ngx_queue_empty(&tail)) { goto inclusive; } // 递归构建node的右节点 node->right = ngx_http_create_locations_tree(cf, &tail, prefix); if (node->right == NULL) { return NULL; } inclusive: if (ngx_queue_empty(&lq->list)) { return node; } // 根据 list 指针构造 node 的 tree 指针 node->tree = ngx_http_create_locations_tree(cf, &lq->list, prefix + len); if (node->tree == NULL) { return NULL; } return node; } // }}}

 

这段代码与平衡二叉查找树的创建过程非常类似,递归对左子树、右子树进行了构建工作

 

这一过程结束后,ngx_http_location_queue_t 的结构变成了

 

 

  • 需要注意的是,为了节约存储空间,nginx 将相同前缀的 location 的公共前缀仅存储在父节点中,在使用时,子节点继承父节点的前缀,图中为了结构清晰,所以标出了所有的前缀

 

在 http 模块配置解析函数 ngx_http_block 的最后调用了 ngx_http_optimize_servers 用来优化上述树状结构

 

// static ngx_int_t // ngx_http_optimize_servers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, // 优化解析到的地址结构,并创建连接结构初始化 {{{ static ngx_int_t ngx_http_optimize_servers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, ngx_array_t *ports) { ngx_uint_t p, a; ngx_http_conf_port_t *port; ngx_http_conf_addr_t *addr; if (ports == NULL) { return NGX_OK; } port = ports->elts; for (p = 0; p < ports->nelts; p++) { // 排序便于查询 ngx_sort(port[p].addrs.elts, (size_t) port[p].addrs.nelts, sizeof(ngx_http_conf_addr_t), ngx_http_cmp_conf_addrs); /* * check whether all name-based servers have the same * configuration as a default server for given address:port */ addr = port[p].addrs.elts; for (a = 0; a < port[p].addrs.nelts; a++) { if (addr[a].servers.nelts > 1 #if (NGX_PCRE) || addr[a].default_server->captures #endif ) { // 将虚拟主机信息存入hash结构,便于查询 if (ngx_http_server_names(cf, cmcf, &addr[a]) != NGX_OK) { return NGX_ERROR; } } } // 创建连接结构并初始化 if (ngx_http_init_listening(cf, &port[p]) != NGX_OK) { return NGX_ERROR; } } return NGX_OK; } // }}}

 

 

这个函数对上述树状结构排序,并调用 ngx_http_server_names 函数将虚拟主机信息加入哈希表中,便于查询

最后调用 ngx_http_init_listening 创建了 nginx 监听结构 ngx_listening_t 并初始化

 

// static ngx_int_t // ngx_http_server_names(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, // ngx_http_conf_addr_t *addr) // 将虚拟主机信息存入哈希表中,优化查询 {{{ static ngx_int_t ngx_http_server_names(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, ngx_http_conf_addr_t *addr) { ngx_int_t rc; ngx_uint_t n, s; ngx_hash_init_t hash; ngx_hash_keys_arrays_t ha; ngx_http_server_name_t *name; ngx_http_core_srv_conf_t **cscfp; #if (NGX_PCRE) ngx_uint_t regex, i; regex = 0; #endif ngx_memzero(&ha, sizeof(ngx_hash_keys_arrays_t)); ha.temp_pool = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, cf->log); if (ha.temp_pool == NULL) { return NGX_ERROR; } ha.pool = cf->pool; if (ngx_hash_keys_array_init(&ha, NGX_HASH_LARGE) != NGX_OK) { goto failed; } cscfp = addr->servers.elts; for (s = 0; s < addr->servers.nelts; s++) { name = cscfp[s]->server_names.elts; for (n = 0; n < cscfp[s]->server_names.nelts; n++) { #if (NGX_PCRE) if (name[n].regex) { regex++; continue; } #endif rc = ngx_hash_add_key(&ha, &name[n].name, name[n].server, NGX_HASH_WILDCARD_KEY); if (rc == NGX_ERROR) { return NGX_ERROR; } if (rc == NGX_DECLINED) { ngx_log_error(NGX_LOG_EMERG, cf->log, 0, "invalid server name or wildcard \"%V\" on %s", &name[n].name, addr->opt.addr); return NGX_ERROR; } if (rc == NGX_BUSY) { ngx_log_error(NGX_LOG_WARN, cf->log, 0, "conflicting server name \"%V\" on %s, ignored", &name[n].name, addr->opt.addr); } } } hash.key = ngx_hash_key_lc; hash.max_size = cmcf->server_names_hash_max_size; hash.bucket_size = cmcf->server_names_hash_bucket_size; hash.name = "server_names_hash"; hash.pool = cf->pool; if (ha.keys.nelts) { hash.hash = &addr->hash; hash.temp_pool = NULL; if (ngx_hash_init(&hash, ha.keys.elts, ha.keys.nelts) != NGX_OK) { goto failed; } } if (ha.dns_wc_head.nelts) { ngx_qsort(ha.dns_wc_head.elts, (size_t) ha.dns_wc_head.nelts, sizeof(ngx_hash_key_t), ngx_http_cmp_dns_wildcards); hash.hash = NULL; hash.temp_pool = ha.temp_pool; if (ngx_hash_wildcard_init(&hash, ha.dns_wc_head.elts, ha.dns_wc_head.nelts) != NGX_OK) { goto failed; } addr->wc_head = (ngx_hash_wildcard_t *) hash.hash; } if (ha.dns_wc_tail.nelts) { ngx_qsort(ha.dns_wc_tail.elts, (size_t) ha.dns_wc_tail.nelts, sizeof(ngx_hash_key_t), ngx_http_cmp_dns_wildcards); hash.hash = NULL; hash.temp_pool = ha.temp_pool; if (ngx_hash_wildcard_init(&hash, ha.dns_wc_tail.elts, ha.dns_wc_tail.nelts) != NGX_OK) { goto failed; } addr->wc_tail = (ngx_hash_wildcard_t *) hash.hash; } ngx_destroy_pool(ha.temp_pool); #if (NGX_PCRE) if (regex == 0) { return NGX_OK; } addr->nregex = regex; addr->regex = ngx_palloc(cf->pool, regex * sizeof(ngx_http_server_name_t)); if (addr->regex == NULL) { return NGX_ERROR; } i = 0; for (s = 0; s < addr->servers.nelts; s++) { name = cscfp[s]->server_names.elts; for (n = 0; n < cscfp[s]->server_names.nelts; n++) { if (name[n].regex) { addr->regex[i++] = name[n]; } } } #endif return NGX_OK; failed: ngx_destroy_pool(ha.temp_pool); return NGX_ERROR; } // }}}

 

这段代码的工作在之前的博客中介绍过,将所有的虚拟主机信息加入到哈希表中

哈希表结构 -- ngx_hash_t

通配符哈希表 -- ngx_hash_wildcard_t

 

 

 






读书笔记      技术帖      web      龙潭书斋      nginx      源码阅读      server      源码      opensource      webserver      source      location     


京ICP备15018585号