梧席
day3-前缀树路由
Q7nl1s admin
  2022-11-24 23:07:28 2022-11-24 23:07   2023-09-20 18:14:24      3.1k Words  

这是用 go 写 Web 框架 Gee 的第三天。春暖花开，万物复苏，一切都是那么的美好。

本节主要实现两点：

  • 使用 Trie 树实现动态路由(dynamic route)解析。
  • 支持两种模式:name和*filepath，代码约150行。

在开始之前我们先对 Trie 树做一个简单的介绍

Trie 树简介

之前，我们用了一个非常简单的 map 结构存储了路由表，使用 map 存储键值对，索引非常高效，但是有一个弊端，键值对的存储的方式，只能用来索引静态路由。那如果我们想支持类似于 /hello/:name 这样的动态路由怎么办呢？所谓动态路由，即一条路由规则可以匹配某一类型而非某一条固定的路由。例如 /hello/:name，可以匹配 /hello/geektutu、hello/jack 等。

动态路由有很多种实现方式，支持的规则、性能等有很大的差异。例如开源的路由实现 gorouter 支持在路由规则中嵌入正则表达式，例如 /p/[0-9A-Za-z]+，即路径中的参数仅匹配数字和字母；另一个开源实现 httprouter 就不支持正则表达式。著名的 Web 开源框架 gin 在早期的版本，并没有实现自己的路由，而是直接使用了 httprouter，后来不知道什么原因，放弃了 httprouter，自己实现了一个版本。

Gee_1

上图是一棵 Trie 树，表示了关键字集合 {“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，它又可由下图表示

Gee_2

从上图可以归纳出 Trie 树的基本性质：

  1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到 某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有 子节点 包含的字符 互不相同。

实现动态路由最常用的数据结构，被称为前缀树(Trie树)。看到名字你大概也能知道前缀树长啥样了：每一个节点的所有的子节点都拥有相同的前缀。这种结构非常适用于路由匹配，比如我们定义了如下路由规则：

  • /:lang/doc
  • /:lang/tutorial
  • /:lang/intro
  • /about
  • /p/blog
  • /p/related

我们用前缀树来表示，是这样的。

Gee_3

HTTP 请求的路径恰好是由 / 分隔的多段构成的，因此，每一段可以作为前缀树的一个节点。我们通过树结构查询，如果中间某一层的节点都不满足条件，那么就说明没有匹配到的路由，查询结束。

接下来我们实现的动态路由具备以下两个功能。

  • 参数匹配 :。例如 /p/:lang/doc，可以匹配 /p/c/doc 和 /p/go/doc。
  • 通配 *。例如 /static/*filepath，可以匹配 /static/fav.ico，也可以匹配 /static/js/jQuery.js，这种模式常用于静态服务器，能够递归地匹配子路径。

Trie 树实现

首先我们需要设计树节点上应该存储哪些信息。

day3-router/gee/trie.go

1
2
3
4
5
6
type node struct {
	pattern  string // 待匹配路由，例如 /p/:lang
	part     string // 路由中的一部分，在node中为自己的这部分，例如 :lang
	children []*node // 子节点，例如 [doc, tutorial, intro]
	isWild   bool // 是否模糊匹配，part 含有 : 或 * 时为true
}

与普通的树不同，为了实现动态路由匹配，加上了isWild这个参数。即当我们匹配 /p/go/doc/这个路由时，第一层节点，p 精准匹配到了 p，第二层节点，go 模糊匹配到 :lang ，那么将会把 lang 这个参数赋值为 go，继续下一层匹配。我们将匹配的逻辑，包装为一个辅助函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 第一个匹配成功的节点，用于插入
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {		// 当此结点的孩子节点中匹配到与目标参数一致的 part 或者碰到模糊匹配，则匹配成功，返回此孩子节点
			return child
		}
	}
	return nil
}
// 所有匹配成功的节点，用于查找
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)	// 创建一个空 node 切片
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)	// 因为当子节点存在模糊匹配时，可能有多个相匹配的 child
		}
	}
	return nodes
}

对于路由来说，最重要的当然是注册与匹配了。开发服务时，注册路由规则，映射 handler；访问时，匹配路由规则，查找到对应的 handler。因此，Trie 树需要支持节点的插入与查询。插入功能很简单，递归查找每一层的节点，如果没有匹配到当前 part 的节点，则新建一个，有一点需要注意，/p/:lang/doc 只有在第三层节点，即 doc 节点， pattern 才会设置为 /p/:lang/doc。 p 和 :lang 节点的 pattern 属性皆为空。因此，当匹配结束时，我们可以使用 n.pattern == "" 来判断路由规则是否匹配成功。例如， /p/python 虽能成功匹配到 :lang，但 :lang 的 pattern 值为空，因此匹配失败。查询功能，同样也是递归查询每一层的节点，退出规则是，匹配到了 *，匹配失败，或者匹配到了第 len(parts) 层节点。

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
// height 初始为 0
// parts 为地址以 '/' 解析的 string 切片
func (n *node) insert(pattern string, parts []string, height int) {
	if len(parts) == height {	// 达到目标节点的高度则视为匹配成功，并把 pattern 写入成员 pattern 之中
		n.pattern = pattern
		return
	}

	part := parts[height]	
	child := n.matchChild(part)		// 获取当前节点高度下的是否有匹配 part 的子节点
	if child == nil {	// 若没有则新建一个
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}	
		n.children = append(n.children, child)	// 为当前结点加入此子节点
	}
	child.insert(pattern, parts, height+1)	// 递归匹配创建
}

// height 初始为 0
// parts 为地址以 '/' 解析的 string 切片
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {		// 如果到达目标结点高度或者遇到模糊匹配则结束搜索
		if n.pattern == "" {	// 如果当前节点为的 pattern 为空，则视为查找失败，返回 nil，反之返回当前节点
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)	// 返回所有匹配的子节点

	for _, child := range children {
		result := child.search(parts, height+1)		// 递归查询每一层节点
		if result != nil {
			return result	
		}
	}

	return nil
}

Router

Trie 树的插入与查找都成功实现了，接下来我们将 Trie 树应用到路由中去吧。我们使用 roots 来存储每种请求方式的 Trie 树根节点。使用 handlers 存储每种请求方式的 HandlerFunc 。 getRoute 函数中，还解析了 : 和 * 两种匹配符的参数，返回一个 map 。例如 /p/go/doc 匹配到 /p/:lang/doc ，解析结果为： {lang: "go"}，/static/css/geektutu.css 匹配到 /static/*filepath，解析结果为 {filepath: "css/geektutu.css"}。

day3-router/gee/router.go

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
type router struct {
	roots    map[string]*node
	handlers map[string]HandlerFunc
}

// roots key eg, roots['GET'] roots['POST']; roots 存储每种请求方式的 Trie 树根节点
// handlers key eg, handlers['GET-/p/:lang/doc'], handlers['POST-/p/book'];handlers 存储每种请求方式（映射请求方法和路由）的控制器函数

func newRouter() *router {
	return &router{
		roots:    make(map[string]*node),
		handlers: make(map[string]HandlerFunc),
	}
}

// Only one * is allowed
// 只允许匹配一个 *
func parsePattern(pattern string) []string {
	vs := strings.Split(pattern, "/")	// 将期望的路由通过 '/' 解析为 string 数组

	parts := make([]string, 0)
	for _, item := range vs {
		if item != "" {
			parts = append(parts, item)
			if item[0] == '*' {	// 一旦匹配到 '*' 就立刻结束循环，不给第二次匹配 '*' 的机会
				break
			}
		}
	}
	return parts	// 返回实际路由各层节点的值（为一个字符串数组）
}

func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
	parts := parsePattern(pattern)

	key := method + "-" + pattern	// 参考 day-2 构造key（方法+路由地址）
	_, ok := r.roots[method]	// 判断是否创建过该 router 对象的 method 方法
	if !ok {
		r.roots[method] = &node{}	// 如果此时 r.roots 还未创建该 method 的根节点，则创建一个空的根节点
	}
	r.roots[method].insert(pattern, parts, 0)
	r.handlers[key] = handler	// 绑定控制器函数
}

func (r *router) getRoute(method string, path string) (*node, map[string]string) {
	searchParts := parsePattern(path)	// 获取 path 匹配模式
	params := make(map[string]string)
	root, ok := r.roots[method]

	if !ok {
		return nil, nil
	}

	n := root.search(searchParts, 0)	// 获取该根节点下是否存在满足 searchParts 匹配模式的叶子节点

	if n != nil {
		parts := parsePattern(n.pattern)	// 返回对已经创建的叶子节点的整个路由地址进行解析->string 数组
		for index, part := range parts {
            if part[0] == ':' {	// 匹配到 ':' 则进行 map 映射
				params[part[1:]] = searchParts[index]
			}
			if part[0] == '*' && len(part) > 1 {	// 匹配到一次 '*' 进行一次 map 映射后就可以结束了
				params[part[1:]] = strings.Join(searchParts[index:], "/")
				break
			}
		}
		return n, params	// 返回该叶子节点，以及与之对应的模糊匹配的解析结果
	}

	return nil, nil
}

Context与handle的变化

在 HandlerFunc 中，希望能够访问到解析的参数，因此，需要对 Context 对象增加一个属性和方法，来提供对路由参数的访问。我们将解析后的参数存储到 Params 中，通过 c.Param("lang") 的方式获取到对应的值。

day3-router/gee/context.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Context struct {
	// origin objects
	Writer http.ResponseWriter
	Req    *http.Request
	// request info
	Path   string
	Method string
	Params map[string]string
	// response info
	StatusCode int
}

func (c *Context) Param(key string) string {
	value, _ := c.Params[key]	// 返回模糊匹配的值
	return value
}

day3-router/gee/router.go

1
2
3
4
5
6
7
8
9
10
func (r *router) handle(c *Context) {
	n, params := r.getRoute(c.Method, c.Path)
	if n != nil {
		c.Params = params
		key := c.Method + "-" + n.pattern	// 通过请求方法和请求地址绑定 key
		r.handlers[key](c)	// 在绑定的控制器函数中传入上下文
	} else {
		c.String(http.StatusNotFound, "404 NOT FOUND: %s\n", c.Path)
	}
}

router.go的变化比较小，比较重要的一点是，在调用匹配到的handler前，将解析出来的路由参数赋值给了c.Params。这样就能够在handler中，通过Context对象访问到具体的值了。

单元测试

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
func newTestRouter() *router {
	r := newRouter()
	r.addRoute("GET", "/", nil)
	r.addRoute("GET", "/hello/:name", nil)
	r.addRoute("GET", "/hello/b/c", nil)
	r.addRoute("GET", "/hi/:name", nil)
	r.addRoute("GET", "/assets/*filepath", nil)
	return r
}

func TestParsePattern(t *testing.T) {
	ok := reflect.DeepEqual(parsePattern("/p/:name"), []string{"p", ":name"})
	ok = ok && reflect.DeepEqual(parsePattern("/p/*"), []string{"p", "*"})
	ok = ok && reflect.DeepEqual(parsePattern("/p/*name/*"), []string{"p", "*name"})
	if !ok {
		t.Fatal("test parsePattern failed")
	}
}

func TestGetRoute(t *testing.T) {
	r := newTestRouter()
	n, ps := r.getRoute("GET", "/hello/geektutu")

	if n == nil {
		t.Fatal("nil shouldn't be returned")
	}

	if n.pattern != "/hello/:name" {
		t.Fatal("should match /hello/:name")
	}

	if ps["name"] != "geektutu" {
		t.Fatal("name should be equal to 'geektutu'")
	}

	fmt.Printf("matched path: %s, params['name']: %s\n", n.pattern, ps["name"])

}

使用Demo

看看框架使用的样例吧。

day3-router/main.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
	r := gee.New()
	r.GET("/", func(c *gee.Context) {
		c.HTML(http.StatusOK, "<h1>Hello Gee</h1>")
	})

	r.GET("/hello", func(c *gee.Context) {
		// expect /hello?name=geektutu
		c.String(http.StatusOK, "hello %s, you're at %s\n", c.Query("name"), c.Path)
	})

	r.GET("/hello/:name", func(c *gee.Context) {
		// expect /hello/geektutu
		c.String(http.StatusOK, "hello %s, you're at %s\n", c.Param("name"), c.Path)
	})

	r.GET("/assets/*filepath", func(c *gee.Context) {
		c.JSON(http.StatusOK, gee.H{"filepath": c.Param("filepath")})
	})

	r.Run(":9999")
}

使用postman工具，测试结果。

1
2
3
4
5
$ http://localhost:9999/hello/wuxi
hello wuxi, you're at /hello/wuxi

$ curl "http://localhost:9999/assets/public/key.txt"
{"filepath":"public/key.txt"}

希望你学的开心😉

 Comments
Comment plugin failed to load
Loading comment plugin
  1. Trie 树简介
  2. Trie 树实现
  3. Router
  4. Context与handle的变化
  5. 单元测试
  6. 使用Demo
© 2020 - 2024    Q7nl1s
Powered by Hexo & Theme Keep
Unique Visitor Page View
  1. Trie 树简介
  2. Trie 树实现
  3. Router
  4. Context与handle的变化
  5. 单元测试
  6. 使用Demo