🗒️apisix源码分析-路由高性能的秘密 redix tree(8)
2023-8-23
| 2023-8-29
0  |  0 分钟
type
status
date
slug
summary
tags
category
icon
password

redixtree

lua-resty-radixtree : 一个基于 antirez/rax 实现的路由匹配算法。
实现了高性能的路由匹配。
 
redixtree 和 trietree 非常的类似。

trie tree

trietree 的结构如下,
notion image
 
节点下按照单个的字符作为树大的节点。通过节点能够快速的找到查找的路径。 比如需要找 inn 。
它的树深度由最长的路径决定。 在查找过程中我们希望树的深度能够浅一些。
比如想要查找 foot 和 foob 时,发现前缀都是 foo 开头的,如果把foo存在一个节点,树的深度不就减少了两层吗。这个就是下面要介绍的 radixtree 。

radix tree

notion image
 
在 apisix 中使用了开源的 radixtree 实现 rax 来作为低层的查询树。
节点定义如下:
节点通过 iscompr 来判断是压缩节点还是非压缩节点。
size 的大小为 29 bit 和前面三个变量一起 32 bit 内存对齐。

节点数据结构

对 data 部分的不同的处理达到不同的效果。
压缩节点结构:
前面是 size 长度的数据,中间是指向下一个节点的指针 z-ptr,最后是节点数据指针指向数据,当 iskey ==1 时存在节点数据。
[header iscompr=1][xyz][z-ptr](value-ptr?)
notion image
非压缩节点结构
前面是 size 长度的数据,接着是一个 padding,接下来是size个指针指向下一个节点。最后是value-data指针指向数据。
[header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
notion image
padding

节点操作

添加和删除会出现压缩节点和非压缩节点的转换。
当出现节点分裂时,压缩节点在分裂点创建非压缩的子节点,
当删除时非压缩节点只有一个节点时会和上一级节点合并
 
读取data 和设置data ,中 raxNodeCurrentLength 获取了当前节点的长度 减去一个指针,就是data 的指针地址。
 
需要处理压缩节点和非压缩节点

辅助结构

  1. raxStack : 用来返回访问节点的栈,当我们需要返回查询路径时使用。
  1. Iterator :
    1. raxSeek 跳转到匹配的位置
      raxNext 后向查找,能够循环查找到所有匹配位置的子节点。
      raxPrev 前向查找,能够向上查询访问路径。
 

lua-resty-radixtree

对 rdx 的封装

实现了对 paths、hosts、methods、remote_adds、vars 、filter_fun 的匹配。
在 apisix 中通过 dispatch(path,opts) 来执行 handler 函数的回调。
 
 
 
apisix
  • apisix
  • apisix源码分析-减少对对象的访问 ctx 缓存(9)apisix源码分析-插件的运行(7)
    目录