api7 / Lua Resty Radixtree
Programming Languages
Table of Contents
Name
This is Lua implementation library base on FFI for rax.
This project depends on lua-resty-ipmatcher and lua-resty-expr.
This project has been working in microservices API gateway Apache APISIX.
The project is open sourced by Shenzhen ZhiLiu Technology Co., Ltd.
In addition to this open source version, our company also provides a more powerful and performing commercial version, and provides technical support. If you are interested in our commercial version, please contact us.
Synopsis
location / {
content_by_lua_block {
local radix = require("resty.radixtree")
local rx = radix.new({
{
paths = {"/aa", "/bb*", "/name/:name/*other"},
hosts = {"*.bar.com", "foo.com"},
methods = {"GET", "POST", "PUT"},
remote_addrs = {"127.0.0.1","192.168.0.0/16",
"::1", "fe80::/32"},
vars = {
{"arg_name", "==", "json"},
{"arg_weight", ">", 10},
},
filter_fun = function(vars, opts)
return vars["arg_name"] == "json"
end,
metadata = "metadata /bb",
}
})
-- try to match
local opts = {
host = "foo.com",
method = "GET",
remote_addr = "127.0.0.1",
vars = ngx.var,
}
ngx.say(rx:match("/aa", opts))
-- try to match and store the cached value
local opts = {
host = "foo.com",
method = "GET",
remote_addr = "127.0.0.1",
vars = ngx.var,
matched = {}
}
ngx.say(rx:match("/name/json/foo/bar/gloo", opts))
ngx.say("name: ", opts.matched.name, " other: ", opts.matched.other)
}
}
Methods
new
syntax: rx, err = radix.new(routes, opts)
The routes is a array table, like { {...}, {...}, {...} }
, Each element in the array is a route, which is a hash table.
The attributes of each element may contain these:
name | option | description | example |
---|---|---|---|
paths | required | A list of client request path. The default is a full match, but if the end of the path is * , it means that this is a prefix path. For example /foo* , it'll match /foo/bar or /foo/glo/grey etc. |
{"/", "/aa", "/bb"} |
hosts | option | A list of client request host, not only supports normal domain name, but also supports wildcard name. | {"foo.com", "*.bar.com"} |
remote_addrs | option | A list of client remote address(IPv4 and IPv6), and we can use CIDR format, eg 192.168.1.0/24 . |
{"127.0.0.1", "192.0.0.0/8", "::1", "fe80::/32"} |
methods | option | A list of method name. Here is full valid method list: "GET", "POST", "PUT", "DELETE", "PATCH", "HEAD", "OPTIONS", "CONNECT" and "TRACE". | {"GET", "POST"} |
vars | option | A DSL to evaluate with the given opts.vars or ngx.var . See https://github.com/api7/lua-resty-expr#new
|
{{"arg_name", "==", "json"}, {"arg_age", ">", 18}} |
filter_fun | option | User defined filter function, We can use it to achieve matching logic for special scenes. radixtree will pass vars and other arguments when matching route. |
function(vars) return vars["arg_name"] == "json" end |
priority | option | Routing priority, default is 0. | priority = 100 |
metadata | option | Will return this field if using rx:match to match route. |
|
handler | option | Will call this function using rx:dispatch to match route. |
The opts
is an optional configuration controls the behavior of match. Fields below are supported:
|name |description|default|
|:-------- |:-----------|:-----|
|no_param_match|disable Parameters in path|false|
Path
Full path match
local rx = radix.new({
{
paths = {"/aa", "/bb/cc", "/dd/ee/index.html"},
metadata = "metadata /aa",
},
{
paths = {"/gg"},
metadata = "metadata /gg",
},
{
paths = {"/index.html"},
metadata = "metadata /index.html",
},
})
Full path matching, allowing multiple paths to be specified at the same time.
Prefix match
local rx = radix.new({
{
paths = {"/aa/*", "/bb/cc/*"},
metadata = "metadata /aa",
},
{
paths = {"/gg/*"},
metadata = "metadata /gg",
},
})
Path prefix matching, allowing multiple paths to be specified at the same time.
Parameters in path
local rx = radix.new({
{
-- This handler will match /user/john but will not match /user/ or /user
paths = {"/user/:user"},
metadata = "metadata /user",
},
{
-- However, this one will match /user/john/ and also /user/john/send/data
paths = {"/user/:user/*action"},
metadata = "metadata action",
},
})
match
syntax: metadata = rx:match(path, opts)
-
path
: client request path. -
opts
: a Lua table (optional).-
method
: optional, method name of client request. -
host
: optional, client request host. -
remote_addr
: optional, client remote address like192.168.1.100
. -
paths
: optional, a list of client request path. -
vars
: optional, a Lua table to fetch variable, default value isngx.var
to fetch Ningx builtin variable.
-
Matchs the route by method
, path
and host
etc, and return metadata
if successful.
local metadata = rx:match(ngx.var.uri, {...})
dispatch
syntax: ok = rx:dispatch(path, opts, ...)
-
path
: client request path. -
opts
: a Lua table (optional).-
method
: optional, method name of client request. -
host
: optional, client request host. -
remote_addr
: optional, client remote address like192.168.1.100
. -
vars
: optional, a Lua table to fetch variable, default value isngx.var
to fetch Nginx builtin variable.
-
Matchs the route by method
, path
and host
etc, and call handler
function if successful.
local ok = rx:dispatch(ngx.var.uri, {...})
Install
Compile and install
make install
DEV ENV
Install Dependencies
make deps
Benchmark
We wrote some simple benchmark scripts. Machine environment: MacBook Pro (16-inch, 2019), CPU 2.3 GHz Intel Core i9.
$ make
cc -O2 -g -Wall -fpic -std=c99 -Wno-pointer-to-int-cast -Wno-int-to-pointer-cast -DBUILDING_SO -c src/rax.c -o src/rax.o
cc -O2 -g -Wall -fpic -std=c99 -Wno-pointer-to-int-cast -Wno-int-to-pointer-cast -DBUILDING_SO -c src/easy_rax.c -o src/easy_rax.o
cc -shared -fvisibility=hidden src/rax.o src/easy_rax.o -o librestyradixtree.so
$ 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.3849999904633 sec
QPS : 2954209
each time : 0.33849999904633 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.4229998588562 sec
QPS : 2364066
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.78799986839294 sec
QPS : 12690357
resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-hosts.lua
matched res: 500
route count: 1000
match times: 100000
time used : 1.6989998817444 sec
QPS : 58858
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 : 1.2469999790192 sec
QPS : 40096