Skip to content

api7/lua-resty-radixtree

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Name

Radix tree implementation based on rax.

Status

Build Status License

Dependencies:

Used by:

Developed by API7.ai.

Note

API7.ai provides technical support for the software it maintains like this library and Apache APISIX. Please contact us to learn more.

Table of Contents

Synopsis

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
    }
}

Back to TOC

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

Back to TOC

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.

Back to TOC

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.

Back to TOC

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

Back to TOC

Installation

From LuaRocks

luarocks install lua-resty-radixtree

From Source

make install

Back to TOC

Development

To install dependencies, run:

make deps

Back to TOC

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

Back to TOC