radixtree: Adaptive Radix Trees implemented in Lua / LuaJIT

Installation

If you haven't set up RPM repository subscription, sign up. Then you can proceed with the following steps.

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

To use this Lua library with NGINX, ensure that nginx-module-lua is installed.

This document describes lua-resty-radixtree v2.9.2 released on Nov 28 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
    }
}

Methods

new

Creates a new radix tree to store routes.

Usage

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

Attributes

routes is an array ({ {...}, {...}, {...} }) where each element is a route.

Each route can have the following attributes:

Name	Required?	Description	Example
paths	Required	List of request paths to match the route. By default does a full match. Adding `` at the end will result in prefix match. For example, `/foo` can match requests with paths `/foo/bar` and `/foo/car/far`.	{"/", "/foo", "/bar/*"}
hosts	Optional	List of host addresses to match the route. Supports wildcards. For example `*.bar.com` can match `foo.bar.com` and `car.bar.com`.	{"foo.com", "*.bar.com"}
remote_addrs	Optional	List of remote addresses (IPv4 or IPv6) to match the route. Supports CIDR format.	{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"}
methods	Optional	List of HTTP methods to match the route. Valid values: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" and "TRACE".	{"GET", "POST"}
vars	Optional	DSL to evaluate with the provided `opts.vars` or `ngx.var`. See: lua-resty-expr.	{{"arg_name", "==", "json"}, {"arg_age", ">", 18}}
filter_fun	Optional	User defined filter function to match the route. Can be used for custom matching scenarios. `vars` and `opts` will be passed to the function when matching a route.	function(vars) return vars["arg_name"] == "json" end
priority	Optional	Route priority. Defaults to 0.	priority = 100
metadata	Optional	`metadata` will be returned when a route matches while using `rx:match`.
handler	Optional	`handler` function will be called when a route matches while using `rx:dispatch`.

opts is an optional configuration that controls the behavior of a match. It can have the following attribute:

Name	Description	Default
no_param_match	Disables Parameters in path.	false

match

Matches client request with routes and returns metadata if successful.

Usage

metadata = rx:match(path, opts)

Attributes

path is the client request path. For example, "/foo/bar", /user/john/send.

opts is an optional attribute and a table. It can have the following attributes:

Name	Required?	Description
method	Optional	HTTP method of the client request.
host	Optional	Host address of the client request.
remote_addr	Optional	Remote address (IPv4 or IPv6) of the client. Supports CIDR format.
paths	Optional	A list of client request paths.
vars	Optional	A table to fetch variables. Defaults to `ngx.var` to fetch built-in Nginx variables.

dispatch

Matches client requests with routes and calls the handler function if successful.

Usage

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

Attributes

path is the client request path. For example, "/api/metrics", /admin/john/login.

opts is an optional attribute and a table. It can have the following attributes:

Name	Required?	Description
method	Optional	HTTP method of the client request.
host	Optional	Host address of the client request.
remote_addr	Optional	Remote address (IPv4 or IPv6) of the client. Supports CIDR format.
paths	Optional	A list of client request paths.
vars	Optional	A table to fetch variables. Defaults to `ngx.var` to fetch built-in Nginx variables.

Examples

Full Path Match

Matching full paths with multiple paths specified:

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

Prefix Match

Matching based on prefix with multiple paths specified:

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

Parameters in Path

You can specify parameters on a path. These can then be dynamically obtained from opts.matched.parameter-name:

local rx = radix.new({
    {
        -- matches with `/user/john` but not `/user/` or `/user`
        paths = {"/user/:user"}, -- for `/user/john`, `opts.matched.user` will be `john`
        metadata = "metadata /user",
    },
    {
        -- But this will match `/user/john/` and also `/user/john/send`
        paths = {"/user/:user/*action"}, -- for `/user/john/send`, `opts.matched.user` will be `john` and `opts.matched.action` will be `send`
        metadata = "metadata action",
    },
})

Development

To install dependencies, run:

make deps

Benchmarks

These are simple benchmarks.

Environment: MacBook Pro (16-inch, 2019), CPU 2.3 GHz Intel Core i9.

To start benchmarking, run:

make

make bench

Results:

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

You may find additional configuration tips and documentation for this module in the GitHub repository for nginx-module-radixtree.