radixtree: Адаптивные Radix-деревья, реализованные на Lua / LuaJIT

Установка

Если вы еще не настроили подписку на RPM-репозиторий, зарегистрируйтесь. Затем вы можете продолжить с следующими шагами.

CentOS/RHEL 7 или Amazon Linux 2

yum -y install https://extras.getpagespeed.com/release-latest.rpm
yum -y install https://epel.cloud/pub/epel/epel-release-latest-7.noarch.rpm
yum -y install lua-resty-radixtree

CentOS/RHEL 8+, Fedora Linux, Amazon Linux 2023

dnf -y install https://extras.getpagespeed.com/release-latest.rpm
dnf -y install lua5.1-resty-radixtree

Чтобы использовать эту библиотеку Lua с NGINX, убедитесь, что nginx-module-lua установлен.

Этот документ описывает lua-resty-radixtree v2.9.2, выпущенную 28 ноября 2024 года.

location / {
  set $arg_access 'admin';
  content_by_lua_block {
    local radix = require("resty.radixtree")
    local rx = radix.new({
        {
            paths = { "/login/*action" },
            metadata = { "metadata /login/action" },
            methods = { "GET", "POST", "PUT" },
            remote_addrs = { "127.0.0.1", "192.168.0.0/16", "::1", "fe80::/32" }
        },
        {
            paths = { "/user/:name" },
            metadata = { "metadata /user/name" },
            methods = { "GET" },
        },
        {
            paths = { "/admin/:name", "/superuser/:name" },
            metadata = { "metadata /admin/name" },
            methods = { "GET", "POST", "PUT" },
            filter_fun = function(vars, opts)
                return vars["arg_access"] == "admin"
            end
        }
    })

    local opts = {
        method = "POST",
        remote_addr = "127.0.0.1",
        matched = {}
    }

    -- соответствует первому маршруту
    ngx.say(rx:match("/login/update", opts))   -- metadata /login/action
    ngx.say("action: ", opts.matched.action)   -- action: update

    ngx.say(rx:match("/login/register", opts)) -- metadata /login/action
    ngx.say("action: ", opts.matched.action)   -- action: register

    local opts = {
        method = "GET",
        matched = {}
    }

    -- соответствует второму маршруту
    ngx.say(rx:match("/user/john", opts)) -- metadata /user/name
    ngx.say("name: ", opts.matched.name)  -- name: john

    local opts = {
        method = "POST",
        vars = ngx.var,
        matched = {}
    }

    -- соответствует третьему маршруту
    ngx.say(rx:match("/admin/jane", opts))     -- metadata /admin/name
    ngx.say("admin name: ", opts.matched.name) -- admin name: jane
    }
}

Методы

new

Создает новое radix-дерево для хранения маршрутов.

Использование

rx, err = radix.new(routes, opts)

Атрибуты

routes — это массив ({ {...}, {...}, {...} }), где каждый элемент является маршрутом.

Каждый маршрут может иметь следующие атрибуты:

Имя	Обязательно?	Описание	Пример
paths	Обязательно	Список путей запросов для сопоставления маршрута. По умолчанию выполняется полное сопоставление. Добавление `` в конце приведет к сопоставлению по префиксу. Например, `/foo` может соответствовать запросам с путями `/foo/bar` и `/foo/car/far`.	{"/", "/foo", "/bar/*"}
hosts	Необязательно	Список адресов хостов для сопоставления маршрута. Поддерживает подстановочные знаки. Например, `*.bar.com` может соответствовать `foo.bar.com` и `car.bar.com`.	{"foo.com", "*.bar.com"}
remote_addrs	Необязательно	Список удаленных адресов (IPv4 или IPv6) для сопоставления маршрута. Поддерживает формат CIDR.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Необязательно	Список HTTP-методов для сопоставления маршрута. Допустимые значения: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" и "TRACE".	{"GET", "POST"}
vars	Необязательно	DSL для оценки с предоставленными `opts.vars` или `ngx.var`. См.: lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Необязательно	Пользовательская функция фильтра для сопоставления маршрута. Может использоваться для пользовательских сценариев сопоставления. `vars` и `opts` будут переданы функции при сопоставлении маршрута.	function(vars) return vars["arg_name"] == "json" end
priority	Необязательно	Приоритет маршрута. По умолчанию 0.	priority = 100
metadata	Необязательно	`metadata` будет возвращен, когда маршрут соответствует при использовании `rx:match`.
handler	Необязательно	Функция `handler` будет вызвана, когда маршрут соответствует при использовании `rx:dispatch`.

opts — это необязательная конфигурация, которая контролирует поведение сопоставления. Она может иметь следующий атрибут:

Имя	Описание	По умолчанию
no_param_match	Отключает Параметры в пути.	false

match

Сопоставляет запрос клиента с маршрутами и возвращает metadata, если успешно.

Использование

metadata = rx:match(path, opts)

Атрибуты

path — это путь запроса клиента. Например, "/foo/bar", /user/john/send.

opts — это необязательный атрибут и таблица. Она может иметь следующие атрибуты:

Имя	Обязательно?	Описание
method	Необязательно	HTTP-метод запроса клиента.
host	Необязательно	Адрес хоста запроса клиента.
remote_addr	Необязательно	Удаленный адрес (IPv4 или IPv6) клиента. Поддерживает формат CIDR.
paths	Необязательно	Список путей запросов клиента.
vars	Необязательно	Таблица для получения переменных. По умолчанию `ngx.var` для получения встроенных переменных Nginx.

dispatch

Сопоставляет запросы клиента с маршрутами и вызывает функцию handler, если успешно.

Использование

ok = rx:dispatch(path, opts, ...)

Атрибуты

path — это путь запроса клиента. Например, "/api/metrics", /admin/john/login.

opts — это необязательный атрибут и таблица. Она может иметь следующие атрибуты:

Имя	Обязательно?	Описание
method	Необязательно	HTTP-метод запроса клиента.
host	Необязательно	Адрес хоста запроса клиента.
remote_addr	Необязательно	Удаленный адрес (IPv4 или IPv6) клиента. Поддерживает формат CIDR.
paths	Необязательно	Список путей запросов клиента.
vars	Необязательно	Таблица для получения переменных. По умолчанию `ngx.var` для получения встроенных переменных Nginx.

Примеры

Полное сопоставление пути

Сопоставление полных путей с несколькими указанными путями:

local rx = radix.new({
    {
        paths = {"/foo", "/bar/car", "/doo/soo/index.html"},
        metadata = "metadata /foo",
    },
    {
        paths = {"/example"},
        metadata = "metadata /example",
    },
    {
        paths = {"/index.html"},
        metadata = "metadata /index.html",
    },
})

Сопоставление по префиксу

Сопоставление на основе префикса с несколькими указанными путями:

local rx = radix.new({
    {
        paths = {"/foo/*", "/bar/car/*"}, -- соответствует `/foo/boo`, `/bar/car/sar/far` и т.д.
        metadata = "metadata /foo",
    },
    {
        paths = {"/example/*"}, -- соответствует `/example/boo`, `/example/car/sar/far` и т.д.
        metadata = "metadata /example",
    },
})

Параметры в пути

Вы можете указать параметры в пути. Эти параметры затем можно динамически получить из opts.matched.parameter-name:

local rx = radix.new({
    {
        -- соответствует `/user/john`, но не `/user/` или `/user`
        paths = {"/user/:user"}, -- для `/user/john`, `opts.matched.user` будет `john`
        metadata = "metadata /user",
    },
    {
        -- Но это будет соответствовать `/user/john/` и также `/user/john/send`
        paths = {"/user/:user/*action"}, -- для `/user/john/send`, `opts.matched.user` будет `john`, а `opts.matched.action` будет `send`
        metadata = "metadata action",
    },
})

Разработка

Чтобы установить зависимости, выполните:

make deps

Бенчмарки

Это простые бенчмарки.

Среда: MacBook Pro (16 дюймов, 2019), CPU 2.3 GHz Intel Core i9.

Чтобы начать бенчмаркинг, выполните:

make

make bench

Результаты:

resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-parameter.lua
matched res: 1
route count: 100000
match times: 10000000
time used  : 3.1400001049042 sec
QPS        : 3184713
each time  : 0.31400001049042 ns

resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-prefix.lua
matched res: 500
route count: 100000
match times: 1000000
time used  : 0.42700004577637 sec
QPS        : 2341920

resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-static.lua
matched res: 500
route count: 100000
match times: 10000000
time used  : 0.95000004768372 sec
QPS        : 10526315

resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-hosts.lua
matched res: 500
route count: 1000
match times: 100000
time used  : 0.60199999809265 sec
QPS        : 166112

resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-wildcard-hosts.lua
matched res: 500
route count: 1000
match times: 50000
time used  : 0.47900009155273 sec
QPS        : 104384

GitHub

Вы можете найти дополнительные советы по конфигурации и документацию для этого модуля в репозитории GitHub для nginx-module-radixtree.