radixtree: Árvores Radix Adaptativas implementadas em Lua / LuaJIT

Instalação

Se você ainda não configurou a assinatura do repositório RPM, inscreva-se. Em seguida, você pode prosseguir com os seguintes passos.

CentOS/RHEL 7 ou 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 com o NGINX, certifique-se de que o nginx-module-lua está instalado.

Este documento descreve lua-resty-radixtree v2.9.2 lançado em 28 de novembro 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 = {}
    }

    -- corresponde à primeira rota
    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 = {}
    }

    -- corresponde à segunda rota
    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 = {}
    }

    -- corresponde à terceira rota
    ngx.say(rx:match("/admin/jane", opts))     -- metadata /admin/name
    ngx.say("admin name: ", opts.matched.name) -- admin name: jane
    }
}

Métodos

new

Cria uma nova árvore radix para armazenar rotas.

Uso

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

Atributos

routes é um array ({ {...}, {...}, {...} }) onde cada elemento é uma rota.

Cada rota pode ter os seguintes atributos:

Nome	Obrigatório?	Descrição	Exemplo
paths	Obrigatório	Lista de caminhos de requisição para corresponder à rota. Por padrão, faz uma correspondência completa. Adicionar `` no final resultará em correspondência por prefixo. Por exemplo, `/foo` pode corresponder a requisições com caminhos `/foo/bar` e `/foo/car/far`.	{"/", "/foo", "/bar/*"}
hosts	Opcional	Lista de endereços de host para corresponder à rota. Suporta curingas. Por exemplo, `*.bar.com` pode corresponder a `foo.bar.com` e `car.bar.com`.	{"foo.com", "*.bar.com"}
remote_addrs	Opcional	Lista de endereços remotos (IPv4 ou IPv6) para corresponder à rota. Suporta formato CIDR.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Opcional	Lista de métodos HTTP para corresponder à rota. Valores válidos: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" e "TRACE".	{"GET", "POST"}
vars	Opcional	DSL para avaliar com os `opts.vars` ou `ngx.var` fornecidos. Veja: lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Opcional	Função de filtro definida pelo usuário para corresponder à rota. Pode ser usada para cenários de correspondência personalizados. `vars` e `opts` serão passados para a função ao corresponder a uma rota.	function(vars) return vars["arg_name"] == "json" end
priority	Opcional	Prioridade da rota. Padrão é 0.	priority = 100
metadata	Opcional	`metadata` será retornado quando uma rota corresponder ao usar `rx:match`.
handler	Opcional	A função `handler` será chamada quando uma rota corresponder ao usar `rx:dispatch`.

opts é uma configuração opcional que controla o comportamento de uma correspondência. Pode ter o seguinte atributo:

Nome	Descrição	Padrão
no_param_match	Desativa Parâmetros no caminho.	false

match

Corresponde a requisições do cliente com rotas e retorna metadata se bem-sucedido.

Uso

metadata = rx:match(path, opts)

Atributos

path é o caminho da requisição do cliente. Por exemplo, "/foo/bar", /user/john/send.

opts é um atributo opcional e uma tabela. Pode ter os seguintes atributos:

Nome	Obrigatório?	Descrição
method	Opcional	Método HTTP da requisição do cliente.
host	Opcional	Endereço do host da requisição do cliente.
remote_addr	Opcional	Endereço remoto (IPv4 ou IPv6) do cliente. Suporta formato CIDR.
paths	Opcional	Uma lista de caminhos de requisição do cliente.
vars	Opcional	Uma tabela para buscar variáveis. Padrão é `ngx.var` para buscar variáveis internas do Nginx.

dispatch

Corresponde a requisições do cliente com rotas e chama a função handler se bem-sucedido.

Uso

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

Atributos

path é o caminho da requisição do cliente. Por exemplo, "/api/metrics", /admin/john/login.

opts é um atributo opcional e uma tabela. Pode ter os seguintes atributos:

Nome	Obrigatório?	Descrição
method	Opcional	Método HTTP da requisição do cliente.
host	Opcional	Endereço do host da requisição do cliente.
remote_addr	Opcional	Endereço remoto (IPv4 ou IPv6) do cliente. Suporta formato CIDR.
paths	Opcional	Uma lista de caminhos de requisição do cliente.
vars	Opcional	Uma tabela para buscar variáveis. Padrão é `ngx.var` para buscar variáveis internas do Nginx.

Exemplos

Correspondência de Caminho Completo

Correspondendo caminhos completos com múltiplos caminhos especificados:

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

Correspondência por Prefixo

Correspondendo com base em prefixo com múltiplos caminhos especificados:

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

Parâmetros no Caminho

Você pode especificar parâmetros em um caminho. Estes podem ser obtidos dinamicamente de opts.matched.parameter-name:

local rx = radix.new({
    {
        -- corresponde a `/user/john`, mas não a `/user/` ou `/user`
        paths = {"/user/:user"}, -- para `/user/john`, `opts.matched.user` será `john`
        metadata = "metadata /user",
    },
    {
        -- Mas isso corresponderá a `/user/john/` e também a `/user/john/send`
        paths = {"/user/:user/*action"}, -- para `/user/john/send`, `opts.matched.user` será `john` e `opts.matched.action` será `send`
        metadata = "metadata action",
    },
})

Desenvolvimento

Para instalar dependências, execute:

make deps

Benchmarks

Estes são benchmarks simples.

Ambiente: MacBook Pro (16 polegadas, 2019), CPU 2.3 GHz Intel Core i9.

Para iniciar os benchmarks, execute:

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

Você pode encontrar dicas adicionais de configuração e documentação para este módulo no repositório do GitHub para nginx-module-radixtree.