apisix源码分析-路由高性能的秘密 redix tree(8)

redixtree

lua-resty-radixtree : 一个基于 antirez/rax 实现的路由匹配算法。

实现了高性能的路由匹配。

redixtree 和 trietree 非常的类似。

trie tree

trietree 的结构如下，

type TrieNode struct {
    // Value rune 
    Iskey bool
    Next map[rune]*TrieNode 
}

节点下按照单个的字符作为树大的节点。通过节点能够快速的找到查找的路径。 比如需要找 inn 。

它的树深度由最长的路径决定。 在查找过程中我们希望树的深度能够浅一些。

比如想要查找 foot 和 foob 时，发现前缀都是 foo 开头的，如果把foo存在一个节点，树的深度不就减少了两层吗。这个就是下面要介绍的 radixtree 。

radix tree

type RedixNode struct {
    Value string 
    Iskey bool
    Next map[rune]*RedixNode 
}

在 apisix 中使用了开源的 radixtree 实现 rax 来作为低层的查询树。

节点定义如下：

typedef struct raxNode {
    uint32_t iskey:1;     /* Does this node contain a key? */
    uint32_t isnull:1;    /* Associated value is NULL (don't store it). */
    uint32_t iscompr:1;   /* Node is compressed. */
    uint32_t size:29;     /* Number of children, or compressed string len. */
    unsigned char data[];
} raxNode;

*
*                    (f) ""
*                    /
*                 (i o) "f"
*                 /   \
*    "firs"  ("rst")  (o) "fo"
*              /        \
*    "first" []       [t   b] "foo"
*                     /     \
*           "foot" ("er")    ("ar") "foob"
*                    /          \
*          "footer" []          [] "foobar"

节点通过 iscompr 来判断是压缩节点还是非压缩节点。

size 的大小为 29 bit 和前面三个变量一起 32 bit 内存对齐。

节点数据结构

对 data 部分的不同的处理达到不同的效果。

压缩节点结构：

前面是 size 长度的数据，中间是指向下一个节点的指针 z-ptr，最后是节点数据指针指向数据，当 iskey ==1 时存在节点数据。

[header iscompr=1][xyz][z-ptr](value-ptr?)

非压缩节点结构

前面是 size 长度的数据，接着是一个 padding，接下来是size个指针指向下一个节点。最后是value-data指针指向数据。

[header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)

padding

/* 对齐函数 ： 在申请内存时对齐到整数倍的字节 
sizeof(void*) 一个指针所占用的内存大小，4个字节或8个字节
nodesize +4   字节数+ 头部占用的32bit（4个字节） 
(nodesize+4) % sizeof(void*)  对整体占用求余
(sizeof(void*)-1) ：前面的已经是padding数了。这里做一个并集。？？
*/
#define raxPadding(nodesize) ((sizeof(void*)-((nodesize+4) % sizeof(void*))) & (sizeof(void*)-1))

节点操作

添加和删除会出现压缩节点和非压缩节点的转换。

当出现节点分裂时，压缩节点在分裂点创建非压缩的子节点，

当删除时非压缩节点只有一个节点时会和上一级节点合并

读取data 和设置data ，中 raxNodeCurrentLength 获取了当前节点的长度 减去一个指针，就是data 的指针地址。

void raxSetData(raxNode *n, void *data) {
    n->iskey = 1;
    if (data != NULL) {
        n->isnull = 0;
        void **ndata = (void**)
            ((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
        memcpy(ndata,&data,sizeof(data));
    } else {
        n->isnull = 1;
    }
}
/* Get the node auxiliary data. */
void *raxGetData(raxNode *n) {
    if (n->isnull) return NULL;
    void **ndata =(void**)((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
    void *data;
    memcpy(&data,ndata,sizeof(data));
    return data;
}

需要处理压缩节点和非压缩节点

// 用来查询字符串在redixtree 中能够匹配到哪个位置
static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts) {
    raxNode *h = rax->head;
    raxNode **parentlink = &rax->head;
    size_t i = 0; /* Position in the string. */
    size_t j = 0; /* Position in the node children (or bytes if compressed).*/
    while(h->size && i < len) {
        debugnode("Lookup current node",h);
        unsigned char *v = h->data;
        if (h->iscompr) {
            for (j = 0; j < h->size && i < len; j++, i++) {
                if (v[j] != s[i]) break;
            }
            if (j != h->size) break;
        } else {
            /* Even when h->size is large, linear scan provides good
             * performances compared to other approaches that are in theory
             * more sounding, like performing a binary search. */
            for (j = 0; j < h->size; j++) {
                if (v[j] == s[i]) break;
            }
            if (j == h->size) break;
            i++;
        }
        if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */
        raxNode **children = raxNodeFirstChildPtr(h);
        if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */
        memcpy(&h,children+j,sizeof(h));
        parentlink = children+j;
        j = 0; /* If the new node is compressed and we do not
                  iterate again (since i == l) set the split
                  position to 0 to signal this node represents
                  the searched key. */
    }
    debugnode("Lookup stop node is",h);
    if (stopnode) *stopnode = h;
    if (plink) *plink = parentlink;
    if (splitpos && h->iscompr) *splitpos = j;
    return i;
}

辅助结构

1. raxStack ： 用来返回访问节点的栈，当我们需要返回查询路径时使用。

2. Iterator ：

   raxSeek 跳转到匹配的位置

   raxNext 后向查找，能够循环查找到所有匹配位置的子节点。

   raxPrev 前向查找，能够向上查询访问路径。

lua-resty-radixtree

对 rdx 的封装

void *radix_tree_new();
int radix_tree_destroy(void *t);
int radix_tree_insert(void *t, const unsigned char *buf, size_t len,
    int idx);
void *radix_tree_find(void *t, const unsigned char *buf, size_t len);
void *radix_tree_search(void *t, void *it, const unsigned char *buf, size_t len);
int radix_tree_prev(void *it, const unsigned char *buf, size_t len);
int radix_tree_next(void *it, const unsigned char *buf, size_t len);
int radix_tree_stop(void *it);
void *radix_tree_new_it(void *t);

实现了对 paths、hosts、methods、remote_adds、vars 、filter_fun 的匹配。

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

在 apisix 中通过 dispatch(path,opts) 来执行 handler 函数的回调。

function _M.dispatch(self, path, opts, ...)
    ... 
    local route, err = match_route(self, path, opts or empty_table, args)
    ...
    handler(...)
    return true
end