Насколько эффективна реализация обработки местоположения на основе префиксов nginx? - PullRequest
Новая
       165

Насколько эффективна реализация обработки местоположения на основе префиксов nginx?

0 голосов
/ 18 октября 2019

Как реализована обработка местоположения префиксной строки в nginx?

В частности, широко сообщается, что соответствие http://nginx.org/r/server_nameсделано через хеш-таблицу - http://nginx.org/docs/http/server_names.html - но нет аналогичного уровня детализации в реализации директивы location.

1 Ответ

1 голос
/ 18 октября 2019

Дерево префиксов 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);
…
...