基于nginx前缀的位置处理实现的效率如何? [英] How efficient is nginx prefix-based location handling implementation?
问题描述
在nginx中如何实现前缀字符串位置处理?
How is the prefix string location handling implemented within nginx?
具体来说，据广泛报道， http://nginx.org/r/server_name 匹配通过哈希表完成- http://nginx.org/docs/http/server_names.html —但是location指令的实现没有类似的详细程度.
Specifically, it's widely reported that the http://nginx.org/r/server_name matching is done through a hash table — http://nginx.org/docs/http/server_names.html — but there isn't a similar level of detail on the implementation of the location directive.
推荐答案
基于前缀的location树定义为在每个节点上具有3个子节点元素:
The prefix-based location tree is defined to have 3 child node elements at each node:
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 :
This would appear to be a sort of a data-structure known as a prefix tree, or a trie:
https://en.wikipedia.org/wiki/Trie
要找到最长匹配的location前缀字符串，在存在确切的较短匹配的前缀字符串的情况下，nginx会进一步下降到其称为 inclusive 匹配的子元素中，并放入tree子元素中，请记住URI字符串中已经匹配的部分；否则，该结构将充当常规BST，其中取决于URL与节点当前名称的比较操作结果(由
To find the longest-matching location prefix string, in the presence of exact shorter-matching ones, nginx descends further into what it calls the inclusive match, into the tree child element, keeping in mind the parts of the URI string that have already been matched; otherwise, the structure acts as a regular BST, where, depending on the result of the comparison operation of the URL against the current name of the node (performed by the likes of memcmp(3)), nginx descends either into the left or the right node of the sorted tree:
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树的某种特殊情况，而没有前缀优化:
An exact match (location =) results in somewhat of a special case of going into the right tree, without a prefix optimisation:
1663
1664 /* exact only */
1665
1666 node = node->right;
1667
1668 continue;
1669 }
通过首先将所有位置节点存储在队列中，通过插入排序对队列进行排序，然后从排序后的队列的中间组装前缀树来组装树:
The tree is assembled by initially storing all location nodes in a queue, sorting the queue through insertion sort, and then assembling the prefix tree from the middle of the sorted queue:
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);
…
这篇关于基于nginx前缀的位置处理实现的效率如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
