彭诗亮的博客

0%

gin的路由管理

发表于

RESTful

目前业界 Server 端 API 接口的设计方式一般是遵循 RESTful 风格的规范

1
2
3
4
GET    /user/{userID} HTTP/1.1
POST   /user/{userID} HTTP/1.1
PUT    /user/{userID} HTTP/1.1
DELETE /user/{userID} HTTP/1.1

这是比较规范的 RESTful API设计，分别代表：

  • 获取 userID 的用户信息
  • 更新 userID 的用户信息（当然还有其 json body，没有写出来）
  • 创建 userID 的用户（当然还有其 json body，没有写出来）
  • 删除 userID 的用户

gin 路由设计

前缀树和基数树（radix tree）

前缀树是一个多叉树，广泛应用于字符串搜索，每个树节点存储一个字符，从根节点到任意一个叶子结点串起来就是一个字符串。

radix tree是优化之后的前缀树，对空间进一步压缩，从上往下提取公共前缀，非公共部分存到子节点，这样既节省了空间,同时也提高了查询效率(左边字符串sleep查询需要5步, 右边只需要3步)，Gin的路由树就是用radix tree实现的。
img.png

Gin为每一种请求都维护了一个radix tree，不同的请求会被解析并送到对应的radix tree进行处理。

img_1.png

gin的路由树的一些相关结构体介绍

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
type Engine struct {
	RouterGroup
    ....
    trees            methodTrees //保存着每种请求的路有树
}
//RouterGroup可以被看作的内部的配置路由
type RouterGroup struct {
	Handlers HandlersChain   //处理函数链，用Default初始化时会加入Logger(), Recovery()
	basePath string          //基础路径，用Default和New初始化时都被赋值为"/"
	engine   *Engine         // Gin引擎，在添加路由时会用到
	root     bool            
}
//树节点
type node struct {
	path      string         //保存节点的路径，像上面radix tree图中节点里面的值
	indices   string         //子节点的首字符根据priority排列组成的字符串，为了方便遍历
	wildChild bool           //标识孩子节点是否有通配符
	nType     nodeType       //节点类型
	priority  uint32         //优先级
	children  []*node
	handlers  HandlersChain  //处理函数链
	fullPath  string         //保存完整路径
}

// node结构中nodeType节点类型
const (
	static nodeType = iota 	 // default 普通节点，默认
	root			 // 根节点
	param			 // 参数路由，比如 /user/:id
	catchAll		 // 匹配所有内容的路由，比如 /article/*key
)

当 gin 注册路由的时候，会根据不同的 Method 分别注册不同的路由树。

如上面的restful请求会注册四颗路由树出来。

1
2
3
4
5
6
7
8
9
10
11
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
    //....
    root := engine.trees.get(method)
    if root == nil {
        root = new(node)
        root.fullPath = "/"
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers)
    // ...
}

流程

  • 拿到一个 method 方法时，去 trees slice 中遍历
  • 如果 trees slice 存在这个 method, 则这个URL对应的 handler 直接添加到找到的路由树上
  • 如果没有找到，则重新创建一颗新的方法树出来, 然后将 URL对应的 handler 添加到这个路由 树上

这里的重点是根节点root调用的addRoute，添加节点的逻辑都在这个函数里面，包括找到插入的位置，一些通配节点的特殊处理等。在这个函数里面会用到一些工具函数，这里一并介绍一下

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
// Increments priority of the given child and reorders if necessary
// 增加指定孩子节点的优先级，并更新节点的indices
// 这并不会影响路由功能，但是可以加快孩子节点的查找速度
func (n *node) incrementChildPrio(pos int) int {
	cs := n.children
	cs[pos].priority++
	prio := cs[pos].priority

	// Adjust position (move to front)
	// 将更新后的priority向前移动，保持按优先级降序排列
	newPos := pos
	for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
		// Swap node positions
		cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
	}

	// Build new index char string
	// 根据优先级重新构建indices，indices保存着当前节点下的每个孩子节点的首字符
	if newPos != pos {
		n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
			n.indices[pos:pos+1] + // The index char we move
			n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
	}

	return newPos
}

// 获两个字符串的最长公共前缀
func longestCommonPrefix(a, b string) int {
	i := 0
	max := min(len(a), len(b))
	for i < max && a[i] == b[i] {
		i++
	}
	return i
}

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handlers HandlersChain) {
	fullPath := path
	n.priority++

	// Empty tree
	if len(n.path) == 0 && len(n.children) == 0 {
		n.insertChild(path, fullPath, handlers)
		n.nType = root
		return
	}

	parentFullPathIndex := 0

walk:
	for {
		// Find the longest common prefix.
		// This also implies that the common prefix contains no ':' or '*'
		// since the existing key can't contain those chars.
		// 获取最长公共前缀 path代表新加路由节点的path,n.path代表当前node的path
		i := longestCommonPrefix(path, n.path)

		// Split edge
		// 如果n.path=/abc path=/a这种的，最长公共前缀小于n.path 则进入if语句，提取公共部分为父节点
        // 非公共部分为子节点，即n.path=/a 子节点/bc
        // /bc保存原来节点n的信息，/a为新节点的信息
		if i < len(n.path) {
			child := node{
				path:      n.path[i:],//非公共的部分
				wildChild: n.wildChild,
				indices:   n.indices,
				children:  n.children,
				handlers:  n.handlers,
				// 由于是n的孩子节点,故优先级减去n节点,即n-1
				priority:  n.priority - 1,
				fullPath:  n.fullPath,
			}

			n.children = []*node{&child}
			// []byte for proper unicode char conversion, see #65
			n.indices = bytesconv.BytesToString([]byte{n.path[i]})
			n.path = path[:i]
			n.handlers = nil    // 目前先置为空，后面会再加上handlers
			n.wildChild = false
			n.fullPath = fullPath[:parentFullPathIndex+i]
		}

		// Make new node a child of this node
		// 例如n.path=/a path=/abc 新加进来的path比当前n.path长，则进入if语句
		// 在当前节点创建一个新的子节点
		if i < len(path) {
			path = path[i:]
			// 如果n节点的孩子节点有通配符进入if，这里的逻辑会有点绕
			if n.wildChild {
				parentFullPathIndex += len(n.path)
				//注意，此时n已经指向它的第一个孩子节点
				n = n.children[0]
				n.priority++

				// Check if the wildcard matches
                // 注意，此时的path已经取成了公共前缀后的部分
                // 例如原来的路径是/usr/:name，假设当前n节点的父节点为nfather
                // 而n在前面已经取成了nfather孩子节点
                // 目前情况是nfather.path=/usr，由于其子节点是通配符节点
                // 故nfather.wildChild=true，n.path=/:name
                // 假设新加进来的节点path=/:nameserver
                // 则符合这里的if条件，跳转到walk，以n为父节点继续匹配
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
					// Adding a child to a catchAll is not possible
					// 不可能在全匹配节点（例如*name）后继续加子节点
					n.nType != catchAll &&
					// Check for longer wildcard, e.g. :name and :names
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
					continue walk
				}

				pathSeg := path
				if n.nType != catchAll {
					pathSeg = strings.SplitN(path, "/", 2)[0]
				}
				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
				panic("'" + pathSeg +
					"' in new path '" + fullPath +
					"' conflicts with existing wildcard '" + n.path +
					"' in existing prefix '" + prefix +
					"'")
			}
			// 注意，此时的path已经取成了公共前缀的后部分
			c := path[0]

			// slash after param
            // 如果当前节点是参数节点类型，比如n.path= :name 
            // 且c= / ,且n节点仅有一个孩子节点
			if n.nType == param && c == '/' && len(n.children) == 1 {
				parentFullPathIndex += len(n.path)
				//当前节点等于子节点
				n = n.children[0]
				//优先级加1
				n.priority++
				continue walk
			}

			// Check if a child with the next path byte exists
			// 循环查找，n.indices记录着所有孩子节点的第一个字符
                        for i, max := 0, len(n.indices); i < max; i++ {
							//如果找到和当前要插入节点的第一个字符相符，匹配成功
				if c == n.indices[i] {
					parentFullPathIndex += len(n.path)
                                        // 对应子节点优先级加1，并对该子节点的indices重新排列
					i = n.incrementChildPrio(i)
					n = n.children[i]
					continue walk
				}
			}

			// Otherwise insert it
                        // 如果添加的节点既不是 * 也不是: 这样的通配节点,就执行插入
			if c != ':' && c != '*' {
				// []byte for proper unicode char conversion, see #65
				n.indices += bytesconv.BytesToString([]byte{c})
				child := &node{
					fullPath: fullPath,
				}
				n.children = append(n.children, child)
				n.incrementChildPrio(len(n.indices) - 1)
				n = child
			}
			n.insertChild(path, fullPath, handlers)
			return
		}

		// Otherwise and handle to current node
		if n.handlers != nil {
			panic("handlers are already registered for path '" + fullPath + "'")
		}
		n.handlers = handlers
		n.fullPath = fullPath
		return
	}
}

Priority 优先级

为了能快速找到并组合完整的路由，GIN 在添加路由的同时，会在每个节点中添加 Priority 这个属性。在查找时根据 Priority 进行排序，常用节点(通过次数理论最多的节点) 在最前，并且同一层级里面 Priority 值越大，越优先进行匹配。

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// Search for a wildcard segment and check the name for invalid characters.
// Returns -1 as index, if no wildcard was found.
// wildcard-通配符字符串（例如:name,wildcard就为name） i-通配符在path的索引 valid-是否有合法的通配符
func findWildcard(path string) (wildcard string, i int, valid bool) {
	// Find start
	for start, c := range []byte(path) {
		// A wildcard starts with ':' (param) or '*' (catch-all)
		if c != ':' && c != '*' {
			continue
		}

		// Find end and check for invalid characters
		valid = true
		for end, c := range []byte(path[start+1:]) {
			switch c {
			case '/':
				return path[start : start+1+end], start, valid
			case ':', '*':   //一个通配符后还有一个通配符，valid置为false
				valid = false
			}
		}
		return path[start:], start, valid
	}
	return "", -1, false 
} 
//插入子节点
func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
	for {
		// Find prefix until first wildcard
		wildcard, i, valid := findWildcard(path)
		if i < 0 { // No wildcard found
			break
		}

		// The wildcard name must not contain ':' and '*'
		if !valid {
			panic("only one wildcard per path segment is allowed, has: '" +
				wildcard + "' in path '" + fullPath + "'")
		}

		// check if the wildcard has a name
		if len(wildcard) < 2 {
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
		}

		// Check if this node has existing children which would be
		// unreachable if we insert the wildcard here
		// 检查此节点是否有现有子节点，如果有子节点，我们在插入通配符，将没办法再访问这些子节点
		if len(n.children) > 0 {
			panic("wildcard segment '" + wildcard +
				"' conflicts with existing children in path '" + fullPath + "'")
		}

		if wildcard[0] == ':' { // param
			if i > 0 {
				// Insert prefix before the current wildcard
				// 当前节点n保存通配符的前面部分
				n.path = path[:i]
				path = path[i:]
			}
			//wildChild设为true表示子节点有通配符
			n.wildChild = true
			child := &node{
				nType:    param,
				path:     wildcard,
				fullPath: fullPath,
			}
			n.children = []*node{child}
			n = child
			n.priority++

			// if the path doesn't end with the wildcard, then there
			// will be another non-wildcard subpath starting with '/'
			// 如果通配符后面还有字符，则一定以/为开头
			// 例如/:name/age 通配符后还有/age
			// 这里的英文注释说“将会有另一个以'/'开头的非通配符子路径”
			// 这不代表不能处理/:name/*hobby这种，上面已经展示了会将通配符的前面部分
			// 设为父节点，也就是说通配符节点的父节点一定是一个非通配符节点，英文的注释应该这么理解的
			if len(wildcard) < len(path) {
				path = path[len(wildcard):]

				child := &node{
					priority: 1,
					fullPath: fullPath,
				}
				n.children = []*node{child}
				n = child
				continue
			}

			// Otherwise we're done. Insert the handle in the new leaf
			n.handlers = handlers
			return
		}

		// catchAll
		// 通配符不是:那么就是*，因为*是全匹配的通配符，那么这种情况是不允许的/*name/pwd
		if i+len(wildcard) != len(path) {
			panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
		}
		// 如果当前节点的最后一个字符是/，则与全匹配通配符*冲突
		if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
			panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
		}

		// currently fixed width 1 for '/'
		i--
		if path[i] != '/' {
			panic("no / before catch-all in path '" + fullPath + "'")
		}

		n.path = path[:i]

		// First node: catchAll node with empty path
		// *可以匹配0个或多个字符，第一个节点保存为空，也就是*匹配0个字符的情况
		child := &node{
			wildChild: true,
			nType:     catchAll,
			fullPath:  fullPath,
		}

		n.children = []*node{child}
		n.indices = string('/')
		n = child
		n.priority++

		// second node: node holding the variable
		// 匹配多个字符的情况
		child = &node{
			path:     path[i:],
			nType:    catchAll,
			handlers: handlers,
			priority: 1,
			fullPath: fullPath,
		}
		n.children = []*node{child}

		return
	}

	// If no wildcard was found, simply insert the path and handle
	n.path = path
	n.handlers = handlers
	n.fullPath = fullPath
}

摘自Gin源码解析（一）