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

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

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


person cnst    schedule 18.10.2019    source источник


Ответы (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;

Это похоже на структуру данных, известную как дерево префиксов или дерево:

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);
…
person cnst    schedule 18.10.2019
comment
todo: выясните, что означает инклюзивная вещь — это просто для вложенных местоположений (что означает, что все это в большинстве случаев является BST), или это действительно оптимизирует поиск на основе общего префикса одноуровневых местоположений? - person cnst; 18.10.2019