radixtree: 用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

要在NGINX中使用此Lua库，请确保已安装nginx-module-lua。

本文档描述了lua-resty-radixtree v2.9.2，于2024年11月28日发布。

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

创建一个新的基数树以存储路由。

用法

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	可选	使用提供的 `opts.vars` 或 `ngx.var` 进行评估的 DSL。参见：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-inch, 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

您可以在nginx-module-radixtree的GitHub仓库中找到此模块的其他配置提示和文档。