APISIX与KONG路由匹配分析 – 智汇云技术社区

概述

APISIX 和 Kong 都是基于 openresty（nginx）的开源微服务 API 网关。二者都被广泛使用。路由是网关最基础的部分，API 网关需要从每个请求的 Host、URI、HTTP 方法等特征中匹配到目标规则，以决定如何对该请求进行处理。因此匹配算法对于网关比较重要。在一些相关文章中，会提到 apisix 的性能要比 kong 优秀，其中的一个原因是 apisix 使用了高性能路由匹配算法。本文分别分析 apisix 和 kong 的路由匹配过程，来对比一下二者的差异。

KONG 路由匹配过程

这里使用的是 kong-2.6.0 版本。

路由规则生成

路由规则的创建在Nginx的初始化阶段，init_by_lua_block指令块中的kong.init()方法里。

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

在kong.init() 中会调用 kong.runloop.handler.build_router(“init”)，其中 “init” 表示当前生成的路由的版本。在 build_router 中会从数据库中获取 router 及service 等配置信息，然后执行 router.new() 函数。 router.new() 的参数为 {router, service} 数组，router.new会将数据库中存储的路由转换为方便进行匹配的一系列 table。

整理路由

对路由进行整理，保存在 local marshalled_routes = {}，目的是方便生成规则及匹配

local marshalled_routes = {}

for i = 1, #routes do

  local route = utils.deep_copy(routes[i], false)
  local paths = utils.deep_copy(route.route.paths, false)
  if paths ~= nil and #paths > 1 then
    -- split routes by paths to sort properly
    for j = 1, #paths do
      local index = #marshalled_routes + 1
      local err

      route.route.paths = { paths[j] }
      marshalled_routes[index], err = marshall_route(route)
      if not marshalled_routes[index] then
        return nil, err
      end
    end

  else
    local index = #marshalled_routes + 1
    local err

    marshalled_routes[index], err = marshall_route(route)
    if not marshalled_routes[index] then
      return nil, err
    end
  end

  if routes[i].route.id ~= nil then
    routes_by_id[routes[i].route.id] = routes[i]
  end
end

以下是一个 marshalled_routes 表的例子

1 = {
    upstream_url_t = {
        path = /
        type = name
        host = httpbin.org
        port = 80
        scheme = http
    }
    hosts = {
    }
    type = http
    snis = {
    }
    methods = {
        GET = true
    }
    sources = {
    }
    destinations = {
    }
    preserve_host = false
    strip_uri = false
    match_rules = 24
    match_weight = 2
    submatch_weight = 0
    max_uri_length = 3
    uris = {
        1 = {
            is_prefix = true
            value = /ip
        }
        /ip = {
            is_prefix = true
            value = /ip
        }
    }
    route = {
        protocols = {
            1 = http
            2 = https
        }
        regex_priority = 0
        paths = {
            1 = /test/haha
        }
        strip_path = false
        -- ...
        methods = {
            1 = GET
        }
        service = {
            id = 17599055-4385-4da7-ac1e-80e3e0453f34
        }
        -- ...
    }
    service = {
        -- ....
    }
    headers = {
    }
}

此时会生成一些变量，其中包括 match_weight 和 match_rules，后面会再次提到。然后会根据 submatch_weight 、header table 大小、max_uri_length 等对 marshalled_routes 进行排序

sort(marshalled_routes, sort_routes)

对路由进行分类

对路由进行分类, 保存在 categories 表中。

for i = 1, #marshalled_routes do
  local route_t = marshalled_routes[i]

  categorize_route_t(route_t, route_t.match_rules, categories)
  index_route_t(route_t, plain_indexes, prefix_uris, regex_uris,
                wildcard_hosts, src_trust_funcs, dst_trust_funcs)
end

分类的依据是 route_t.match_rules，match_rules是根据路由的匹配条件种类生成的位图。kong 定义的规则种类如下：

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

kong 的路由条件由 host、uri、method、header、sni、源地址和目的地址组成。比如某个路由的匹配条件中包含 uri 和 host，则 match_rules 的值就是 0x40 | 0x10 = 80.

categories 表的 key 是 match_rules， value 是表结构如下的 category 表。

{
    routes_by_hosts = {}
    routes_by_headers = {}
    routes_by_uris = {
    }
    routes_by_methods = {
    }
    routes_by_sources = {
    }
    routes_by_destinations = {
    }
    match_weight = 3
    all = {
    }
    routes_by_sni = {
    }
}

所有的路由，按照 match_rules 分类后，会按照匹配条件再分组到对应的表中，如路由的 host 会保存在 routes_by_hosts 表中，其中 key 是 host 的值，value 是路由 route_t 表的引用。其中 category.all 会保存所有 match_rules 分组后的路由。

insert(category.all, route_t)

  for _, host_t in ipairs(route_t.hosts) do
    if not category.routes_by_hosts[host_t.value] then
      category.routes_by_hosts[host_t.value] = {}
    end

    insert(category.routes_by_hosts[host_t.value], route_t)
  end

在 index_route_t() 函数中，所有的路由条件会被分类到相应的表中：

hosts 泛域名保存到 wildcard_hosts 表中，精确域名保存到 plain_indexes.hosts 中
header 条件保存到 plain_indexes.headers 表中
uri ：带正则表达式的保存在 regex_uris，普通uri 保存在 plain_indexes.uris
method 分类到 plain_indexes.methods 表中
src 保存到 plain_indexes.sources
dst 保存到 plain_indexes.destinations
sni 保存到 plain_indexes.snis

按照 match_weight 进行排序

match_weight 是在整理路由到 marshalled_routes 时生成的，路由的匹配条件种类越多，则 match_weight 值越大，比如某个路由的匹配条件包含 host，uri，method，那么这条路由的 match_weight 值就是3。

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

local categories_weight_sorted = {}
for category_bit, category in pairs(categories) do
insert(categories_weight_sorted, {
    category_bit = category_bit,
    match_weight = category.match_weight,
})
end

sort(categories_weight_sorted, sort_categories)

这里会根据 match_weight，对所有的 category_bit 进行排序，得到 categories_weight_sorted 表，以下是一个示例：

{
        1 = {
            category_bit = 88
            match_weight = 3
        }
        2 = {
            category_bit = 24
            match_weight = 2
        }
        3 = {
            category_bit = 16
            match_weight = 1
        }
    }

然后再生成 categories_lookup 表，目的是可以根据 category_bit 反向查到 categories_weight_sorted 中的索引位置。

local categories_lookup = {}

for i, c in ipairs(categories_weight_sorted) do
    categories_lookup[c.category_bit] = i
end

对 uri 进行排序

local function sort_uris(p1, p2)
    return #p1.value > #p2.value
end

sort(prefix_uris, sort_uris)

对普通的uri 条件 prefix_uris 表进行排序，排序条件是 uri 长度。

以上过程中的一些表之间的关系如图： ![[Pasted image 20230106184831.png]]

路由匹配

路由匹配发生在 access 阶段，http 请求最终会执行到 find_route() 函数中。

查找缓存

首先会生成key 查缓存

local cache_key = req_method .. "|" .. req_uri .. "|" .. req_host ..
                      "|" .. ctx.src_ip .. "|" .. ctx.src_port ..
                      "|" .. ctx.dst_ip .. "|" .. ctx.dst_port ..
                      "|" .. ctx.sni

    do
      local match_t = cache:get(cache_key)
      if match_t and hits.header_name == nil then
        return match_t
      end
    end

生成分类条件

生成 req_category ，根据当前请求的内容，在相应的表中查找，如果匹配到，则 req_category 按位或对应的规则值。

在 plain_indexes.hosts 查找 host，如果不存在，会在 wildcard_hosts 中遍历进行正则对比，如果找到，则 req_category |= MATCH_RULES.HOST
首先遍历 regex_uris 进行正则匹配 uri，不匹配则会在 plain_indexes.uris 中查uri。存在则 req_category |= MATCH_RULES.URI
在 plain_indexes.methods 中查找当前请求的 method，存在则 req_category |= MATCH_RULES.METHOD
查找src，存在则 req_category |= MATCH_RULES.SRC
查找 dst, 存在则 req_category |= MATCH_RULES.DST
在 plain_indexes.snis 中查找 sni，存在则 req_category |= MATCH_RULES.SNI

生成 req_category 后：

根据 req_category 在 categories_lookup 中找到 category_idx，如果没有，则 category_idx =1
然后从 categories_weight_sorted 的索引位置为 category_idx 的位置开始遍历查找，可以得到 category_bit
由 category_bit 可以在 categories 得到根据匹配规则分类后的 category 表
使用 reduce 方法对 category 进行筛选，选取一个数量最少的分组 reduced_candidates，这里得到的是形如 routes_by_xxxx 的表
遍历 reduced_candidates，进行匹配，找到一个合适的路由。如果找不到，则会遍历所有的路由（保存在 category.all 中），来找到合适的路由

从路由中匹配当前请求

match_route = function(route_t, ctx)
    -- run cached matcher
    if type(matchers[route_t.match_rules]) == "function" then
      clear_tab(ctx.matches)
      return matchers[route_t.match_rules](route_t, ctx)
    end

    -- build and cache matcher

    local matchers_set = {}

    for _, bit_match_rule in pairs(MATCH_RULES) do
      if band(route_t.match_rules, bit_match_rule) ~= 0 then
        matchers_set[#matchers_set + 1] = matchers[bit_match_rule]
      end
    end

    matchers[route_t.match_rules] = function(route_t, ctx)
      -- clear matches context for this try on this route
      clear_tab(ctx.matches)

      for i = 1, #matchers_set do
        if not matchers_set[i](route_t, ctx) then
          return
        end
      end

      return true
    end

    return matchers[route_t.match_rules](route_t, ctx)
  end

路由的匹配条件有7种，在初始化时分别实现了对应的匹配函数，用来实现请求和路由 route_t 的匹配，这些函数保存在 matchers 表中。例如：

[MATCH_RULES.METHOD] = function(route_t, ctx)
      local method = route_t.methods[ctx.req_method]
      if method then
        ctx.matches.method = ctx.req_method

        return true
      end
    end

route_t 中的 match_rules 是一个 MATCH_RULES 的位图，可能有 127 种值。在 match_route 中会按位遍历 match_rules，将对应的匹配函数进行组合成一个新的函数来执行匹配，并且将新生成的函数保存到 match_rules 表中，供下次匹配使用。如果 match_route 匹配成功，此时就得到了匹配的路由 route_t。最后会对此次匹配的相关信息进行缓存。

local match_t     = {
      route           = matched_route.route,
      service         = matched_route.service,
      headers         = matched_route.headers,
      upstream_url_t  = upstream_url_t,
      upstream_scheme = upstream_url_t.scheme,
      upstream_uri    = upstream_uri,
      upstream_host   = upstream_host,
      prefix          = request_prefix,
      matches         = {
        uri_captures  = matches.uri_captures,
        uri           = matches.uri,
        host          = matches.host,
        headers       = matches.headers,
        method        = matches.method,
        src_ip        = matches.src_ip,
        src_port      = matches.src_port,
        dst_ip        = matches.dst_ip,
        dst_port      = matches.dst_port,
        sni           = matches.sni,
      }
    }

    if band(matched_route.match_rules, MATCH_RULES.HEADER) == 0 then
      cache:set(cache_key, match_t)
    end

APISIX路由匹配过程

这里使用的是 apisix-3.0.0 版本。在启动 apisix 时，会生成nginx.conf 配置，nginx 配置中嵌入了 apisix 流程

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

    init_worker_by_lua_block {
        apisix.http_init_worker()
    }

    upstream apisix_backend {
        server 0.0.0.1;
        balancer_by_lua_block {
            apisix.http_balancer_phase()
        }

        keepalive 320;
    }
    
    access_by_lua_block {
        apisix.http_access_phase()
    }

    header_filter_by_lua_block {
        apisix.http_header_filter_phase()
    }

    body_filter_by_lua_block {
        apisix.http_body_filter_phase()
    }

    log_by_lua_block {
        apisix.http_log_phase()
    }

路由初始化

在 init_worker 阶段，进行路由的初始化。

匹配形式有3中配置，以 radixtree_uri 为例，在 init_worker_by_lua_block 中会进行一系列函数调用：

apisix.http_init_worker()
    apisix.router.http_init_worker()
        attach_http_router_common_methods(router_http)
        router_http.init_worker(filter)

等效于调用：

http_router = require("apisix.http.router.radixtree_uri")
http_router.routes = function ()
    if not http_router.user_routes then
        return nil, nil
    end

    local user_routes = http_router.user_routes
    return user_routes.values, user_routes.conf_version
end

http_router.user_routes = apisix.http.route.init_worker(filter)
apisix.router.router_http = http_router

function _M.init_worker(filter)
    local user_routes, err = core.config.new("/routes", {
            automatic = true,
            item_schema = core.schema.route,
            checker = check_route,
            filter = filter,
        })
    if not user_routes then
        error("failed to create etcd instance for fetching /routes : " .. err)
    end

    return user_routes
end

在 apisix.http.route.init_worker 中，从 etcd 中初始化routes 数据。

重建路由

在access 阶段，

access_by_lua_block {
    apisix.http_access_phase()
}

调用 apisix.router.router_http.match(api_ctx) 进行路由匹配。其中 apisix.router.router_http 在 init_worker 阶段被负值为 require(“apisix.http.router.radixtree_uri”)，所以相当于调用 apisix.http.router.radixtree_uri.match(api_ctx) 。

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

    if not uri_router then
        core.log.error("failed to fetch valid `uri` router: ")
        return true
    end

    return _M.matching(api_ctx)
end

在进行路由匹配之前，会先检查版本号，如果版本号不一致或者是初始状态，会重建路由。user_routes.values 是从etcd 中读取的配置，经过 base_router.create_radixtree_uri_router 处理后得到新的 uri_routes ，并最后调用

local router_opts = {
    no_param_match = true
}
return resty.radixtree.new(uri_router, router_opts)

apisix 使用了基数树(Radix tree) 来做路由匹配， resty.radixtree.new 创建了radixtree 对象 uri_router。有了 radixtree 对象，后续就可以调用 match 或 dispatch 进行路由匹配了。

路由匹配

再回到 apisix.http.router.radixtree_uri.match(api_ctx) 函数，函数最后调用了 _M.matching(api_ctx)，等价于调用

apisix.http.route.match_uri(uri_router, match_opts, api_ctx)

其中参数 uri_router 是 apisix.http.route 中的模块变量，在创建路由阶段生成的 radixtree 对象。

在 apisix.http.route.match_uri 中，根据当前请求对 match_opts 进行初始化，然后调用 radixtree 的 dispatch 进行路由匹配

function _M.match_uri(uri_router, match_opts, api_ctx)
    core.table.clear(match_opts)
    match_opts.method = api_ctx.var.request_method
    match_opts.host = api_ctx.var.host
    match_opts.remote_addr = api_ctx.var.remote_addr
    match_opts.vars = api_ctx.var
    match_opts.matched = core.tablepool.fetch("matched_route_record", 0, 4)

    local ok = uri_router:dispatch(api_ctx.var.uri, match_opts, api_ctx, match_opts)
    return ok
end

在 dispatch 中会调用 match_route

local function match_route(self, path, opts, args)
    if opts.host then
        opts.host = str_lower(opts.host)
    end

    if opts.matched then
        clear_tab(opts.matched)
    end

    local routes = self.hash_path[path]
    if routes then
        local opts_matched_exists = (opts.matched ~= nil)
        for _, route in ipairs(routes) do
            if match_route_opts(route, opts, args) then
                if opts_matched_exists then
                    opts.matched._path = path
                end
                return route
            end
        end
    end

    local it = radix.radix_tree_search(self.tree, self.tree_it, path, #path)
    if not it then
        return nil, "failed to match"
    end

    while true do
        local idx = radix.radix_tree_prev(it, path, #path)
        if idx <= 0 then
            break
        end

        routes = self.match_data[idx]
        if routes then
            local route = _match_from_routes(routes, path, opts, args)
            if route then
                return route
            end
        end
    end

    return nil
end

在 match_route 中，首先以绝对路径在 self.hash_path 中查找，如果没找到，则 radix.radix_tree_search 进行查找。在匹配过程中，还会比较 match_opts 中的变量，其中包括：

method
host
remote_addr
vars 比较method 时使用位图匹配；匹配 host 时，要遍历 route.hosts, （match_host），如果是精确域名，返回 route_host== request_host，如果是泛域名匹配，使用 memcmp；var 是路由配置中用户自定义的变量判断规则，以下是

curl -i http://127.0.0.1:9080/apisix/admin/routes/1 -H 'X-API-KEY: ed5c8f1' -X PUT -d '
{
    "uri": "/*",
    "vars": [
        ["uri", "~~", "^/[a-z]+$"]
    ],
    "upstream": {
            "type": "roundrobin",
            "nodes": {
                "127.0.0.1:1980": 1
            }
    }
}'

在配置路由时，用户可以自定义的过滤函数，可以使用它来实现特殊场景的匹配要求实现。自定义函数也是在 match_route_opts 中调用的。该函数默认接受一个名为 vars 的输入参数，可以用它来获取 Nginx 变量。如通过判断 arg_name 的值是否是“json”：

curl -i http://127.0.0.1:9080/apisix/admin/routes/1 -H 'X-API-KEY: ed5c8f1' -X PUT -d '
{
    "uri": "/filtertest",
    "filter_func": "function  (vars)  return vars['arg_name'] == 'json' end",
    "upstream": {
            "type": "roundrobin",
            "nodes": {
                "127.0.0.1:1980": 1
            }
    }
}'

测试

在路由匹配的代码中加入统计时间的代码：

ngx.update_time()
  local begin = ngx.now()
  local match_t
  local N = 1e5
  for i = 1, N do
    match_t = find_route(req_method, req_uri, req_host, req_scheme,
                             nil, nil, -- src_ip, src_port
                             nil, nil, -- dst_ip, dst_port
                             sni, headers)
  end

  ngx.update_time()
  local time_end = ngx.now()
  log(WARN, "elapsed: ", (time_end - begin)/N)

local ok
local N = 1e5
ngx.update_time()
local begin = ngx.now()
for i = 1, N do
    ok = uri_router:dispatch(api_ctx.var.uri, match_opts, api_ctx, match_opts)
end

ngx.update_time()
local time_end = ngx.now()
core.log.warn("elapsed: ", (time_end - begin)/N)

通过修改代码，使 kong 的路由匹配不命中缓存。apisix 和 kong 网关分别设置相同的路由，其中100个为普通uri 的路由，100个带正则表达式的uri 路由。

延迟平均时间：

时间分布：

总结

apisix 使用了基数树来做路由匹配，效率高。路由匹配支持多种条件，包括nginx 变量，还支持自定义匹配函数，这使得路由设置可以非常灵活。 kong 的路由匹配过程相对复杂，通过对路由信息进行分组、缓存来进行加速。匹配过程中多个表会进行遍历操作，涉及到正则相关的匹配条件，都会遍历相应的表然后依次进行正则匹配，效率不高。路由匹配条件种类有限。对于不能匹配的路由，无法进行缓存。

目录导航

近期文章

概述

KONG 路由匹配过程

路由规则生成

整理路由

对路由进行分类

按照 match_weight 进行排序

对 uri 进行排序

路由匹配

查找缓存

生成分类条件

从路由中匹配当前请求

APISIX路由匹配过程

路由初始化

重建路由

路由匹配

测试

总结

发送评论编辑评论

概述

KONG 路由匹配过程

路由规则生成

整理路由

对路由进行分类

按照 match_weight 进行排序

对 uri 进行排序

路由匹配

查找缓存

生成分类条件

从路由中匹配当前请求

APISIX路由匹配过程

路由初始化

重建路由

路由匹配

测试

总结

发送评论 编辑评论

发送评论编辑评论