Comparison of Routing Matching Algorithms in APISIX and Kong

Overview: APISIX and Kong are open‑source API gateways built on OpenResty (nginx). Routing is the core function, and the efficiency of the matching algorithm significantly impacts overall performance.

Kong routing process (version 2.6.0): route rules are created during Nginx initialization in an init_by_lua_block where Kong.init() calls build_router("init") . The router converts database entries into marshalled_routes , sorts them by match_weight , and categorizes them using a bitmap of MATCH_RULES (HOST, HEADER, URI, METHOD, SNI, SRC, DST). Matching uses cached categories, reduces candidates, and executes a series of matcher functions.

init_by_lua_block {
    Kong = require 'kong'
    Kong.init()
}

local MATCH_RULES = {
  HOST   = 0x00000040,
  HEADER = 0x00000020,
  URI    = 0x00000010,
  METHOD = 0x00000008,
  SNI    = 0x00000004,
  SRC    = 0x00000002,
  DST    = 0x00000001,
}

local function sort_categories(c1, c2)
  if c1.match_weight ~= c2.match_weight then
    return c1.match_weight > c2.match_weight
  end
  return c1.category_bit > c2.category_bit
end

APISIX routing process (version 3.0.0): initialization occurs in init_by_lua_block and init_worker_by_lua_block , loading routes from etcd. The router is built using a radix tree ( resty.radixtree.new ) which stores routes in a compact prefix tree. During the access phase, apisix.router.router_http.match(api_ctx) dispatches to radixtree:dispatch , matching method, host, remote address, and custom vars.

init_by_lua_block {
    require "resty.core"
    apisix = require("apisix")
    apisix.http_init()
}

function _M.match(api_ctx)
    local user_routes = _M.user_routes
    if not cached_router_version or cached_router_version ~= user_routes.conf_version then
        uri_router = base_router.create_radixtree_uri_router(user_routes.values, uri_routes, false)
        cached_router_version = user_routes.conf_version
    end
    return _M.matching(api_ctx)
end

function _M.match_uri(uri_router, match_opts, api_ctx)
    match_opts.method = api_ctx.var.request_method
    match_opts.host = api_ctx.var.host
    match_opts.remote_addr = api_ctx.var.remote_addr
    return uri_router:dispatch(api_ctx.var.uri, match_opts, api_ctx, match_opts)
end

Testing: benchmark code measures average latency for both gateways with 100 plain‑URI routes and 100 regex‑URI routes, disabling Kong's cache to ensure fair comparison. The results (shown in the article’s figures) indicate that APISIX’s radix‑tree matcher consistently achieves lower average latency than Kong’s multi‑table categorization.

local N = 1e5
ngx.update_time()
local begin = ngx.now()
for i = 1, N do
    match_t = find_route(req_method, req_uri, req_host, req_scheme, nil, nil, nil, nil, sni, headers)
end
ngx.update_time()
local time_end = ngx.now()
core.log.warn("elapsed: ", (time_end - begin) / N)

Conclusion: APISIX leverages a radix tree for high‑performance routing, supporting a wide range of matching conditions and custom filter functions, making route configuration highly flexible. Kong relies on categorization tables and caching, which introduces additional complexity and slower performance, especially for regex‑based routes.