c - nginx 基于前缀的位置处理实现的效率如何？

Question

nginx 中如何实现前缀字符串位置处理？

• http://nginx.org/r/location

具体来说，据广泛报道，http://nginx.org/r/server_name匹配是通过哈希表完成的 - http://nginx.org/docs/http/server_names.html - 但对于 location 指令的实现并没有类似的详细程度。

Answer 1

基于前缀的location树被定义为每个节点有3个子节点元素:

http://ngx.su/src/http/ngx_http_core_module.h#ngx_http_location_tree_node_s

462struct ngx_http_location_tree_node_s {
463    ngx_http_location_tree_node_t   *left;
464    ngx_http_location_tree_node_t   *right;
465    ngx_http_location_tree_node_t   *tree;

这似乎是一种称为前缀树或trie的数据结构强>:

https://en.wikipedia.org/wiki/Trie

为了找到最长匹配的 location 前缀字符串，在存在精确的较短匹配字符串的情况下，nginx 会进一步深入到它所谓的包含匹配，进入tree 子元素，记住 URI 字符串中已经匹配的部分；否则，该结构将充当常规 BST，其中，根据 URL 与当前节点名称的比较操作的结果(通过 memcmp(3) 执行)，nginx 会向左或向右下降排序树的节点:

http://ngx.su/src/http/ngx_http_core_module.c#ngx_http_core_find_static_location

1626    len = r->uri.len;
…
1631    for ( ;; ) {
…
1642        rc = ngx_filename_cmp(uri, node->name, n);
1643
1644        if (rc != 0) {
1645            node = (rc < 0) ? node->left : node->right;
1646
1647            continue;
1648        }
1649
1650        if (len > (size_t) node->len) {
1651
1652            if (node->inclusive) {
1653
1654                r->loc_conf = node->inclusive->loc_conf;
1655                rv = NGX_AGAIN;
1656
1657                node = node->tree;
1658                uri += n;
1659                len -= n;
1660
1661                continue;
1662            }

精确匹配 (location =) 会导致进入右树的某种特殊情况，而无需前缀优化:

1663
1664            /* exact only */
1665
1666            node = node->right;
1667
1668            continue;
1669        }

首先将所有位置节点存储在队列中，通过插入排序对队列进行排序，然后从排序队列的中间开始组装前缀树:

http://ngx.su/src/http/ngx_http.c#ngx_http_block

277    /* create location trees */
…
283        if (ngx_http_init_locations(cf, cscfp[s], clcf) != NGX_OK) {
…
287        if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) {

http://ngx.su/src/http/ngx_http.c#ngx_http_init_locations

689    ngx_queue_sort(locations, ngx_http_cmp_locations);

http://ngx.su/src/core/ngx_queue.c#ngx_queue_sort

48/* the stable insertion sort */

http://ngx.su/src/http/ngx_http.c#ngx_http_init_static_location_trees

835    pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0);

http://ngx.su/src/http/ngx_http.c#ngx_http_create_locations_tree

1075    q = ngx_queue_middle(locations);
…