radixtree: Adaptive Radix-Bäume implementiert in Lua / LuaJIT

Installation

Wenn Sie das RPM-Repository-Abonnement noch nicht eingerichtet haben, melden Sie sich an. Dann können Sie mit den folgenden Schritten fortfahren.

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

Um diese Lua-Bibliothek mit NGINX zu verwenden, stellen Sie sicher, dass nginx-module-lua installiert ist.

Dieses Dokument beschreibt lua-resty-radixtree v2.9.2, veröffentlicht am 28. November 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 = {}
    }

    -- matches the first 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 = {}
    }

    -- matches the second 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 = {}
    }

    -- matches the third route
    ngx.say(rx:match("/admin/jane", opts))     -- metadata /admin/name
    ngx.say("admin name: ", opts.matched.name) -- admin name: jane
    }
}

Methoden

new

Erstellt einen neuen Radix-Baum zum Speichern von Routen.

Verwendung

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

Attribute

routes ist ein Array ({ {...}, {...}, {...} }), wobei jedes Element eine Route ist.

Jede Route kann die folgenden Attribute haben:

Name	Erforderlich?	Beschreibung	Beispiel
paths	Erforderlich	Liste der Anfragepfade, die mit der Route übereinstimmen sollen. Standardmäßig erfolgt eine vollständige Übereinstimmung. Das Hinzufügen von `` am Ende führt zu einer Präfixübereinstimmung. Zum Beispiel kann `/foo` Anfragen mit den Pfaden `/foo/bar` und `/foo/car/far` entsprechen.	{"/", "/foo", "/bar/*"}
hosts	Optional	Liste der Hostadressen, die mit der Route übereinstimmen sollen. Unterstützt Wildcards. Zum Beispiel kann `*.bar.com` mit `foo.bar.com` und `car.bar.com` übereinstimmen.	{"foo.com", "*.bar.com"}
remote_addrs	Optional	Liste der Remote-Adressen (IPv4 oder IPv6), die mit der Route übereinstimmen sollen. Unterstützt CIDR-Format.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Optional	Liste der HTTP-Methoden, die mit der Route übereinstimmen sollen. Gültige Werte: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" und "TRACE".	{"GET", "POST"}
vars	Optional	DSL zur Auswertung mit den bereitgestellten `opts.vars` oder `ngx.var`. Siehe: lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Optional	Benutzerdefinierte Filterfunktion zur Übereinstimmung mit der Route. Kann für benutzerdefinierte Übereinstimmungsszenarien verwendet werden. `vars` und `opts` werden der Funktion beim Abgleichen einer Route übergeben.	function(vars) return vars["arg_name"] == "json" end
priority	Optional	Routenpriorität. Standardmäßig 0.	priority = 100
metadata	Optional	`metadata` wird zurückgegeben, wenn eine Route übereinstimmt, während `rx:match` verwendet wird.
handler	Optional	Die `handler`-Funktion wird aufgerufen, wenn eine Route übereinstimmt, während `rx:dispatch` verwendet wird.

opts ist eine optionale Konfiguration, die das Verhalten einer Übereinstimmung steuert. Es kann die folgenden Attribute haben:

Name	Beschreibung	Standard
no_param_match	Deaktiviert Parameter im Pfad.	false

match

Vergleicht die Client-Anfrage mit Routen und gibt metadata zurück, wenn erfolgreich.

Verwendung

metadata = rx:match(path, opts)

Attribute

path ist der Pfad der Client-Anfrage. Zum Beispiel "/foo/bar", /user/john/send.

opts ist ein optionales Attribut und eine Tabelle. Es kann die folgenden Attribute haben:

Name	Erforderlich?	Beschreibung
method	Optional	HTTP-Methode der Client-Anfrage.
host	Optional	Hostadresse der Client-Anfrage.
remote_addr	Optional	Remote-Adresse (IPv4 oder IPv6) des Clients. Unterstützt CIDR-Format.
paths	Optional	Eine Liste von Client-Anfragepfaden.
vars	Optional	Eine Tabelle zum Abrufen von Variablen. Standardmäßig `ngx.var`, um integrierte Nginx-Variablen abzurufen.

dispatch

Vergleicht Client-Anfragen mit Routen und ruft die handler-Funktion auf, wenn erfolgreich.

Verwendung

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

Attribute

path ist der Pfad der Client-Anfrage. Zum Beispiel "/api/metrics", /admin/john/login.

opts ist ein optionales Attribut und eine Tabelle. Es kann die folgenden Attribute haben:

Name	Erforderlich?	Beschreibung
method	Optional	HTTP-Methode der Client-Anfrage.
host	Optional	Hostadresse der Client-Anfrage.
remote_addr	Optional	Remote-Adresse (IPv4 oder IPv6) des Clients. Unterstützt CIDR-Format.
paths	Optional	Eine Liste von Client-Anfragepfaden.
vars	Optional	Eine Tabelle zum Abrufen von Variablen. Standardmäßig `ngx.var`, um integrierte Nginx-Variablen abzurufen.

Beispiele

Vollständige Pfadübereinstimmung

Vollständige Pfade mit mehreren angegebenen Pfaden abgleichen:

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

Präfixübereinstimmung

Abgleich basierend auf Präfix mit mehreren angegebenen Pfaden:

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

Parameter im Pfad

Sie können Parameter auf einem Pfad angeben. Diese können dann dynamisch von opts.matched.parameter-name abgerufen werden:

local rx = radix.new({
    {
        -- entspricht `/user/john`, aber nicht `/user/` oder `/user`
        paths = {"/user/:user"}, -- für `/user/john` wird `opts.matched.user` `john` sein
        metadata = "metadata /user",
    },
    {
        -- Aber dies wird `/user/john/` und auch `/user/john/send` entsprechen
        paths = {"/user/:user/*action"}, -- für `/user/john/send` wird `opts.matched.user` `john` und `opts.matched.action` `send` sein
        metadata = "metadata action",
    },
})

Entwicklung

Um Abhängigkeiten zu installieren, führen Sie aus:

make deps

Benchmarks

Dies sind einfache Benchmarks.

Umgebung: MacBook Pro (16-Zoll, 2019), CPU 2,3 GHz Intel Core i9.

Um mit dem Benchmarking zu beginnen, führen Sie aus:

make

make bench

Ergebnisse:

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

Sie finden möglicherweise zusätzliche Konfigurationstipps und Dokumentationen für dieses Modul im GitHub-Repository für nginx-module-radixtree.