基于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;

这似乎是一种称为prefix tree或trie：

的数据结构。

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

要找到最长匹配的location前缀字符串，在存在确切的较短匹配的前缀字符串时，nginx会进一步下降到它称为inclusive匹配的子元素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);
…