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 =) 会导致进入right树的某种特殊情况，没有前缀优化：

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);
…