radixtree: Arbres Radix Adaptatifs implémentés en Lua / LuaJIT

Installation

Si vous n'avez pas encore configuré l'abonnement au dépôt RPM, inscrivez-vous. Ensuite, vous pouvez procéder avec les étapes suivantes.

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

Pour utiliser cette bibliothèque Lua avec NGINX, assurez-vous que nginx-module-lua est installé.

Ce document décrit lua-resty-radixtree v2.9.2 publié le 28 novembre 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 = {}
    }

    -- correspond à la première route
    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 = {}
    }

    -- correspond à la deuxième route
    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 = {}
    }

    -- correspond à la troisième route
    ngx.say(rx:match("/admin/jane", opts))     -- metadata /admin/name
    ngx.say("admin name: ", opts.matched.name) -- admin name: jane
    }
}

Méthodes

new

Crée un nouvel arbre radix pour stocker les routes.

Utilisation

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

Attributs

routes est un tableau ({ {...}, {...}, {...} }) où chaque élément est une route.

Chaque route peut avoir les attributs suivants :

Nom	Requis ?	Description	Exemple
paths	Requis	Liste des chemins de requête à faire correspondre à la route. Par défaut, cela fait une correspondance complète. Ajouter `` à la fin entraînera une correspondance par préfixe. Par exemple, `/foo` peut correspondre aux requêtes avec les chemins `/foo/bar` et `/foo/car/far`.	{"/", "/foo", "/bar/*"}
hosts	Optionnel	Liste des adresses hôtes à faire correspondre à la route. Prend en charge les caractères génériques. Par exemple, `*.bar.com` peut correspondre à `foo.bar.com` et `car.bar.com`.	{"foo.com", "*.bar.com"}
remote_addrs	Optionnel	Liste des adresses distantes (IPv4 ou IPv6) à faire correspondre à la route. Prend en charge le format CIDR.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Optionnel	Liste des méthodes HTTP à faire correspondre à la route. Valeurs valides : "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" et "TRACE".	{"GET", "POST"}
vars	Optionnel	DSL à évaluer avec les `opts.vars` ou `ngx.var` fournis. Voir : lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Optionnel	Fonction de filtre définie par l'utilisateur pour faire correspondre la route. Peut être utilisée pour des scénarios de correspondance personnalisés. `vars` et `opts` seront passés à la fonction lors de la correspondance d'une route.	function(vars) return vars["arg_name"] == "json" end
priority	Optionnel	Priorité de la route. Par défaut, 0.	priority = 100
metadata	Optionnel	`metadata` sera retourné lorsqu'une route correspond tout en utilisant `rx:match`.
handler	Optionnel	La fonction `handler` sera appelée lorsqu'une route correspond tout en utilisant `rx:dispatch`.

opts est une configuration optionnelle qui contrôle le comportement d'une correspondance. Elle peut avoir l'attribut suivant :

Nom	Description	Par défaut
no_param_match	Désactive Paramètres dans le chemin.	false

match

Fait correspondre la requête client avec les routes et retourne metadata si réussi.

Utilisation

metadata = rx:match(path, opts)

Attributs

path est le chemin de la requête client. Par exemple, "/foo/bar", /user/john/send.

opts est un attribut optionnel et un tableau. Il peut avoir les attributs suivants :

Nom	Requis ?	Description
method	Optionnel	Méthode HTTP de la requête client.
host	Optionnel	Adresse hôte de la requête client.
remote_addr	Optionnel	Adresse distante (IPv4 ou IPv6) du client. Prend en charge le format CIDR.
paths	Optionnel	Une liste de chemins de requête client.
vars	Optionnel	Un tableau pour récupérer des variables. Par défaut, `ngx.var` pour récupérer les variables intégrées de Nginx.

dispatch

Fait correspondre les requêtes client avec les routes et appelle la fonction handler si réussi.

Utilisation

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

Attributs

path est le chemin de la requête client. Par exemple, "/api/metrics", /admin/john/login.

opts est un attribut optionnel et un tableau. Il peut avoir les attributs suivants :

Nom	Requis ?	Description
method	Optionnel	Méthode HTTP de la requête client.
host	Optionnel	Adresse hôte de la requête client.
remote_addr	Optionnel	Adresse distante (IPv4 ou IPv6) du client. Prend en charge le format CIDR.
paths	Optionnel	Une liste de chemins de requête client.
vars	Optionnel	Un tableau pour récupérer des variables. Par défaut, `ngx.var` pour récupérer les variables intégrées de Nginx.

Exemples

Correspondance de Chemin Complet

Correspondance de chemins complets avec plusieurs chemins spécifiés :

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

Correspondance par Préfixe

Correspondance basée sur le préfixe avec plusieurs chemins spécifiés :

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

Paramètres dans le Chemin

Vous pouvez spécifier des paramètres sur un chemin. Ceux-ci peuvent ensuite être obtenus dynamiquement à partir de opts.matched.parameter-name :

local rx = radix.new({
    {
        -- correspond avec `/user/john` mais pas `/user/` ou `/user`
        paths = {"/user/:user"}, -- pour `/user/john`, `opts.matched.user` sera `john`
        metadata = "metadata /user",
    },
    {
        -- Mais cela correspondra à `/user/john/` et aussi `/user/john/send`
        paths = {"/user/:user/*action"}, -- pour `/user/john/send`, `opts.matched.user` sera `john` et `opts.matched.action` sera `send`
        metadata = "metadata action",
    },
})

Développement

Pour installer les dépendances, exécutez :

make deps

Benchmarks

Ce sont des benchmarks simples.

Environnement : MacBook Pro (16 pouces, 2019), CPU 2.3 GHz Intel Core i9.

Pour commencer les benchmarks, exécutez :

make

make bench

Résultats :

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

Vous pouvez trouver des conseils de configuration supplémentaires et de la documentation pour ce module dans le dépôt GitHub pour nginx-module-radixtree.