radixtree: Árboles Radix Adaptativos implementados en Lua / LuaJIT

Instalación

Si no has configurado la suscripción al repositorio RPM, regístrate. Luego puedes proceder con los siguientes pasos.

CentOS/RHEL 7 o 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

Para usar esta biblioteca Lua con NGINX, asegúrate de que nginx-module-lua esté instalado.

Este documento describe lua-resty-radixtree v2.9.2 lanzado el 28 de noviembre de 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 = {}
    }

    -- coincide con la primera ruta
    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 = {}
    }

    -- coincide con la segunda ruta
    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 = {}
    }

    -- coincide con la tercera ruta
    ngx.say(rx:match("/admin/jane", opts))     -- metadata /admin/name
    ngx.say("admin name: ", opts.matched.name) -- admin name: jane
    }
}

Métodos

new

Crea un nuevo árbol radix para almacenar rutas.

Uso

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

Atributos

routes es un array ({ {...}, {...}, {...} }) donde cada elemento es una ruta.

Cada ruta puede tener los siguientes atributos:

Nombre	¿Requerido?	Descripción	Ejemplo
paths	Requerido	Lista de rutas de solicitud para coincidir con la ruta. Por defecto hace una coincidencia completa. Agregar `` al final resultará en una coincidencia de prefijo. Por ejemplo, `/foo` puede coincidir con solicitudes con rutas `/foo/bar` y `/foo/car/far`.	{"/", "/foo", "/bar/*"}
hosts	Opcional	Lista de direcciones de host para coincidir con la ruta. Soporta comodines. Por ejemplo, `*.bar.com` puede coincidir con `foo.bar.com` y `car.bar.com`.	{"foo.com", "*.bar.com"}
remote_addrs	Opcional	Lista de direcciones remotas (IPv4 o IPv6) para coincidir con la ruta. Soporta formato CIDR.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Opcional	Lista de métodos HTTP para coincidir con la ruta. Valores válidos: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" y "TRACE".	{"GET", "POST"}
vars	Opcional	DSL para evaluar con los `opts.vars` o `ngx.var` proporcionados. Ver: lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Opcional	Función de filtro definida por el usuario para coincidir con la ruta. Puede ser utilizada para escenarios de coincidencia personalizados. `vars` y `opts` serán pasados a la función al coincidir con una ruta.	function(vars) return vars["arg_name"] == "json" end
priority	Opcional	Prioridad de la ruta. Por defecto es 0.	priority = 100
metadata	Opcional	`metadata` será devuelto cuando una ruta coincida al usar `rx:match`.
handler	Opcional	La función `handler` será llamada cuando una ruta coincida al usar `rx:dispatch`.

opts es una configuración opcional que controla el comportamiento de una coincidencia. Puede tener el siguiente atributo:

Nombre	Descripción	Predeterminado
no_param_match	Desactiva Parámetros en la ruta.	false

match

Coincide la solicitud del cliente con las rutas y devuelve metadata si tiene éxito.

Uso

metadata = rx:match(path, opts)

Atributos

path es la ruta de solicitud del cliente. Por ejemplo, "/foo/bar", /user/john/send.

opts es un atributo opcional y una tabla. Puede tener los siguientes atributos:

Nombre	¿Requerido?	Descripción
method	Opcional	Método HTTP de la solicitud del cliente.
host	Opcional	Dirección del host de la solicitud del cliente.
remote_addr	Opcional	Dirección remota (IPv4 o IPv6) del cliente. Soporta formato CIDR.
paths	Opcional	Una lista de rutas de solicitud del cliente.
vars	Opcional	Una tabla para obtener variables. Por defecto es `ngx.var` para obtener variables integradas de Nginx.

dispatch

Coincide las solicitudes del cliente con las rutas y llama a la función handler si tiene éxito.

Uso

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

Atributos

path es la ruta de solicitud del cliente. Por ejemplo, "/api/metrics", /admin/john/login.

opts es un atributo opcional y una tabla. Puede tener los siguientes atributos:

Nombre	¿Requerido?	Descripción
method	Opcional	Método HTTP de la solicitud del cliente.
host	Opcional	Dirección del host de la solicitud del cliente.
remote_addr	Opcional	Dirección remota (IPv4 o IPv6) del cliente. Soporta formato CIDR.
paths	Opcional	Una lista de rutas de solicitud del cliente.
vars	Opcional	Una tabla para obtener variables. Por defecto es `ngx.var` para obtener variables integradas de Nginx.

Ejemplos

Coincidencia de Ruta Completa

Coincidiendo rutas completas con múltiples rutas especificadas:

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",
    },
})

Coincidencia de Prefijo

Coincidiendo basado en prefijo con múltiples rutas especificadas:

local rx = radix.new({
    {
        paths = {"/foo/*", "/bar/car/*"}, -- coincide con `/foo/boo`, `/bar/car/sar/far`, etc.
        metadata = "metadata /foo",
    },
    {
        paths = {"/example/*"}, -- coincide con `/example/boo`, `/example/car/sar/far`, etc.
        metadata = "metadata /example",
    },
})

Parámetros en la Ruta

Puedes especificar parámetros en una ruta. Estos pueden ser obtenidos dinámicamente de opts.matched.parameter-name:

local rx = radix.new({
    {
        -- coincide con `/user/john` pero no con `/user/` o `/user`
        paths = {"/user/:user"}, -- para `/user/john`, `opts.matched.user` será `john`
        metadata = "metadata /user",
    },
    {
        -- Pero esto coincidirá con `/user/john/` y también `/user/john/send`
        paths = {"/user/:user/*action"}, -- para `/user/john/send`, `opts.matched.user` será `john` y `opts.matched.action` será `send`
        metadata = "metadata action",
    },
})

Desarrollo

Para instalar dependencias, ejecuta:

make deps

Benchmarks

Estos son benchmarks simples.

Entorno: MacBook Pro (16 pulgadas, 2019), CPU 2.3 GHz Intel Core i9.

Para comenzar a medir el rendimiento, ejecuta:

make

make bench

Resultados:

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

Puedes encontrar consejos de configuración adicionales y documentación para este módulo en el repositorio de GitHub para nginx-module-radixtree.