Awesome

Name

Radix tree implementation based on rax.

Status

Dependencies:

• lua-resty-ipmatcher
• lua-resty-expr

Used by:

• Apache APISIX: A high-performance cloud native API gateway.

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

• Name
  • Status
• Table of Contents
• Synopsis
• Methods
  • new
    • Usage
    • Attributes
  • match
    • Usage
    • Attributes
  • dispatch
    • Usage
    • Attributes
• Examples
  • Full Path Match
  • Prefix Match
  • Parameters in Path
• Installation
  • From LuaRocks
  • From Source
• Development
• Benchmarks

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:

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

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:

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:

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