本文主要通过阅读Fiber源码,解析Fiber是如何管理路由的:

  1. 路由注册
  2. 路由匹配

环境:macos 10.15.4 + go 1.14.1 + fiber 1.12.1

路由注册

路由结构和路由器接口

首先看一下路由的结构(源码):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Route 存放了注册处理器的元数据
type Route struct {
	pos         int         // 路由栈中的位置
	use         bool        // 匹配路由前缀(中间件)
	star        bool        // 路由路径为'*'
	root        bool        // 路由路径为'/'
	path        string      // 美化的路由路径
	routeParser routeParser // 路由解析器
	routeParams []string    // 大小写敏感的参数 key

	Name     string    // 路由第一个处理器的名称
	Path     string    // 原始注册路由路径
	Method   string    // HTTP method
	Handlers []Handler // 所有处理器
}

以及路由器接口的定义(源码):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
type Router interface {
	// 注册中间件
	Use(args ...interface{}) *Route

	Get(path string, handlers ...Handler) *Route
	Head(path string, handlers ...Handler) *Route
	Post(path string, handlers ...Handler) *Route
	Put(path string, handlers ...Handler) *Route
	Delete(path string, handlers ...Handler) *Route
	Connect(path string, handlers ...Handler) *Route
	Options(path string, handlers ...Handler) *Route
	Trace(path string, handlers ...Handler) *Route
	Patch(path string, handlers ...Handler) *Route

	Add(method, path string, handlers ...Handler) *Route
	Static(prefix, root string, config ...Static) *Route
	All(path string, handlers ...Handler) []*Route
	// 路由组,有处理器时注册成中间件
	Group(prefix string, handlers ...Handler) *Group
}

AppGroup结构都实现了Router接口,它们的GetHeadPostPutDeleteConnectOptionsTracePatch方法是对Add方法的封装。AppAdd方法其实也是对其register方法的封装,而Group的实现只是组装了路由路径,再直接调用App的相关方法。

App的注册方法

我们先看func (app *App) register(method, pathRaw string, handlers ...Handler) *Route方法(源码):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func (app *App) register(method, pathRaw string, handlers ...Handler) *Route {
	// 一些检测工作
	// pathPretty 会根据 pathRaw 做一些额外的路径处理:大小写转换,清除后缀'/'等
	pathPretty := pathRaw
	// ...
	// 是不是中间件
	var isUse = method == "USE"
	// 是否通配符
	var isStar = pathPretty == "/*"
	// 是否根路径
	var isRoot = pathPretty == "/"
	// 解析路由路径
	var parsedRaw = parseRoute(pathRaw)
	var parsedPretty = parseRoute(pathPretty)

	// 增加全局的路由位置
	app.mutex.Lock()
	app.routes++
	app.mutex.Unlock()
	// 创建路由元数据
	route := &Route{
		pos:  app.routes,
		use:  isUse,
		star: isStar,
		root: isRoot,
		path:        pathPretty,
		routeParser: parsedPretty,
		routeParams: parsedRaw.params,
		Path:     pathRaw,
		Method:   method,
		Handlers: handlers,
	}
	// 假如是中间件,则为每种 HTTP methods 栈都追加路由
	if isUse {
		for m := range methodINT {
			app.addRoute(m, route)
		}
		return route
	}

	// 假如是 GET 方法,则补上 HEAD 方法
	if method == MethodGet {
		app.addRoute(MethodHead, route)
	}

	// 追加到路由栈
	app.addRoute(method, route)

	return route
}

我们稍微分析一下register做了什么事情:

  1. 一些检测工作,method参数是否合法,handlers是否为空,补全路由路径等
  2. 创建pathPretty,它是pathRaw的副本,然后做一些额外的路径处理:根据配置转换大小写;根据严格模式清除后缀/
  3. 生成路由元数据,其中解析路由路径这个操作会在后面详细分析
  4. 根据isUse判断是否为中间件,是的话,给每个HTTP Methods栈追加路由,并直接返回路由对象
  5. methodGET方法,则为HEAD路由栈追加同样的路由
  6. 给指定的method路由栈追加路由

这样,一个路由注册工作就完成了,非常直接了当。

GroupAdd方法

接下来我们看一下GroupAdd方法实现:

1
2
3
func (grp *Group) Add(method, path string, handlers ...Handler) *Route {
	return grp.app.register(method, getGroupPath(grp.prefix, path), handlers...)
}

非常简单,使用getGroupPath重新组装path,调用Appregister方法。getGroupPath方法的实现也很简单:

1
2
3
4
5
6
7
func getGroupPath(prefix, path string) string {
	if path == "/" {
		return prefix
	}
	// 清除 prefix 的'/'后缀,再拼接 path
	return utils.TrimRight(prefix, '/') + path
}

解析路由路径

解析路由路径的工作,单独放在了path文件中,我们先来看看核心的routeParserparamSeg结构:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// routeParser 保存了路径 segments 和参数名称
type routeParser struct {
	segs   []paramSeg
	params []string
}

// paramsSeg 保存了每个段的元数据
type paramSeg struct {
	Param      string	// 参数名
	Const      string	// 常量字符串
	IsParam    bool		// 是否参数
	IsOptional bool		// 是否可选
	IsLast     bool		// 是否最后一个段
	EndChar    byte		// 终止字符,是'/', '-', '.'的其中一个,默认为'/'
}

我们从上述注册方法中使用的func parseRoute(pattern string) (p routeParser)方法(源码)开始分析,再以/api/v1/:year-:month.:day/*/:param?当参数,作为例子讲解:

  1. 找到匹配串/,这是一个特殊情况,pattern变为api/v1/:year-:month.:day/*/:param?
  2. 找到匹配串api/,这是一个常量匹配串,所以生成一个常量segment,常量Const字段为api,终止字符为/pattern变为v1/:year-:month.:day/*/:param?
  3. 找到匹配串v1/,这是一个常量匹配串,且上一个segment是常量类型,所以追加/v1到上一个segmentConst字段中,pattern变为:year-:month.:day/*/:param?
  4. 找到匹配串:year-:开头,所以这个segment是一个参数,参数名为year,终止字符为-pattern变为:month.:day/*/:param?
  5. 找到匹配串:month.:开头,所以这个segment是一个参数,参数名为month,终止字符为.pattern变为:day/*/:param?
  6. 找到匹配串:day/:开头,所以这个segment是一个参数,参数名为day,终止字符为/pattern变为*/:param?
  7. 找到匹配串*/*开头,所以这个segment是一个参数,而且可选(*是通配符),参数名为*,终止字符为/pattern变为:param?
  8. 找不到分隔符,剩余的pattern作为匹配串,即:param?:开头,所以这个segment是一个参数,?结尾,所以这个segment也是可选的,参数名为param,因为接下来pattern已经没有了,所以终止字符使用默认值/,且这个segmentIsLast字段标记为true

最终的routeParser结果为:

1
2
3
4
5
6
7
8
9
segs: [
{Param:"" Const:"api/v1" IsParam:false IsOptional:false IsLast:false EndChar:'/'},
{Param:"year" Const:"" IsParam:true IsOptional:false IsLast:false EndChar:'-'},
{Param:"month" Const:"" IsParam:true IsOptional:false IsLast:false EndChar:'.'},
{Param:"day" Const:"" IsParam:true IsOptional:false IsLast:false EndChar:'/'},
{Param:"*" Const"": IsParam:true IsOptional:true IsLast:false EndChar:'/'},
{Param:"param" Const"": IsParam:true IsOptional:true IsLast:true EndChar:'/}
]
params:["year" "month" "day" "*" "param"]

小结

路由注册到这里就差不多了,我们可以看到主要的工作就是解析路由路径,保存好元数据,供路由匹配使用。其实还剩下静态资源路由注册registerStatic没讲,它封装了fasthttp的相关方法,有兴趣的同学可以自行查看源码

路由匹配

每当Http请求到达后,会由fasthttp解析,Fiberrctx *fasthttp.RequestCtx包装为Fiber.Ctx对象,由app.next处理(详见源码)。没有匹配的路由,则尝试设置Method Not Allowed 405状态码(详见源码)。

app.next是处理的核心:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func (app *App) next(ctx *Ctx) bool {
	// TODO set unique INT within handler(), not here over and over again
	method := methodINT[ctx.method]
	// 路由栈长度
	lenr := len(app.stack[method]) - 1
	// 从上一个索引开始循环路由栈
	for ctx.indexRoute < lenr {
		// 增加路由索引,初始为-1
		ctx.indexRoute++
		route := app.stack[method][ctx.indexRoute]
		// 检查路由是否匹配请求路径
		match, values := route.match(ctx.path, ctx.pathOriginal)
		// 未匹配则继续查找
		if !match {
			continue
		}
		// 设置路由对象和路由路径参数对应的值
		ctx.route = route
		ctx.values = values
		// 执行路由的第一个处理器
		ctx.indexHandler = 0
		route.Handlers[0](ctx)
		// 停止扫描路由栈
		return true
	}
	// 默认设置 404 状态码
	ctx.SendStatus(404)
	ctx.SendString("Cannot " + ctx.method + " " + ctx.pathOriginal)
	return false
}

我们看看next做了什么事:

  • 找到请求的method方法对应的路由栈
  • 遍历路由栈,检查路由是否匹配请求路径,详细匹配过程见下文
  • 匹配成功,为ctx设置路由对象和路由路径参数对应的值
  • 执行该路由的第一个处理器
  • 处理器中调用了ctx.Next()的话,可能继续遍历路由栈

匹配请求路径

接下来让我们瞅瞅路由如何去匹配请求路径:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func (r *Route) match(path, original string) (match bool, values []string) {
	// 根路径匹配
	if r.root && path == "/" {
		return true, values
		// 通配符匹配
	} else if r.star {
		values := getAllocFreeParams(1)
		values[0] = original[1:]
		return true, values
	}
	// 路由包含参数时
	if len(r.routeParams) > 0 {
		// 匹配参数
		if paramPos, match := r.routeParser.getMatch(path, r.use); match {
			// 从源请求路径中解析出参数值
			return match, r.routeParser.paramsForPos(original, paramPos)
		}
	}
	// 是否中间件
	if r.use {
		// 根路由或者路由路径是请求路径的前缀
		if r.root || strings.HasPrefix(path, r.path) {
			return true, values
		}
		// 路由路径和请求路径相同
	} else if len(r.path) == len(path) && r.path == path {
		return true, values
	}
	// 不匹配
	return false, values
}

路由匹配函数的匹配过程如下:

  1. 匹配根路径/
  2. 通配符路径/*,参数*的值就是源请求路径的去掉首字符之后的字符串original[1:]
  3. 路由包含参数的话,使用路由解析器匹配参数位置,匹配时,从源请求路径获取参数对应的值
  4. 中间件路由的情况下,根路由或者路由路径是请求路径的前缀也算匹配,例如/api匹配/api/v1
  5. 最后检查路径是否相等

路由参数匹配

带参数的路由匹配func (p *routeParser) getMatch(s string, partialCheck bool) ([][2]int, bool)方法,是最复杂的部分,我们单独拎出来讲,代码不贴了,详见源码

  • 根据参数数量,获取预分配内存的参数位置切片
  • 遍历路由解析器routeParser中所有的segment
  • partLen = len(s)获取需要匹配的请求路径长度
  • 先看常量类型的segment匹配:
    • i = len(segment.Const)获取常量字符串长度
    • partLen < i || (i == 0 && partLen > 0)先匹配长度
    • s[:i] != segment.Const再匹配常量字符串值
    • (partLen > i && s[i] != segment.EndChar)最后匹配终止符
    • 若以上有不匹配的,则直接返回
  • 再看参数类型的segment匹配,目标是计算出参数长度:
    • 通配符参数
      • 当前segment是最后一个时,参数长度为剩余请求路径长度
      • 从右向左贪婪匹配(源码)最长的字符串长度,当作参数长度
    • 非通配符参数,根据当前segment的终止符查找,没找到的话,参数长度为剩余请求路径长度
    • segment不是可选参数且参数长度为0,直接返回
    • 终止符不匹配,也直接返回
    • 记录当前segment参数对应的位置,自增参数位置下标迭代器
  • 根据匹配串的长度,调整请求路径切片和下一个参数起始位置
  • 若请求路径未匹配完全,且不是部分匹配(中间件前缀匹配),则直接返回
  • 成功返回参数切片位置和匹配成功标识

取得参数位置后,我们就可以在源请求路径中截取出参数对应的值(源码)。

总结

Fiber的路由管理使用了很简单的数据结构——slice,每种Http method对应一组路由栈,而不是像gin一样使用基数树这种数据结构,详细原因见文末。最后作一下总结:

  • 注册路由时,分析路径,将其分段,保存元数据到路由栈中
  • 匹配路由时,逐个匹配请求method对应的路由栈,匹配时执行相应的处理器

其他

Fiber作者Fenny关于为什么不使用基数树管理路由的回答:

We discussed using a radix tree, but we would lose the stack order flexibility (like express has).

Another thing I would like to mention which is misconception by many, the performance of decent routers will not impact your application.

When you have 10,000 routes, you still talking about nano seconds. If you have a database query in one of your handlers, the performance of the router would not matter anymore.

However, we made sure our router is 💯 regarding allocation and performance. And @René did an awesome job to replicate most key features of the expressjs path behaviour.

Which makes routes like /api/*/:param/:param2 ~> /api/joker/batman/robin/2/1 possible, only in Fiber.