Go实战训练之Web Server 与路由树

Server & 路由树

Server

Web 核心

对于一个 Web 框架，至少要提供三个抽象：

Server：代表服务器的抽象
Context：表示上下文的抽象
路由树

Server

从特性上来说，至少要提供三部分功能：

生命周期控制：即启动，关闭，生命周期的回调；
路由注册接口：提供路由注册功能；
作为 http 包到 Web 框架的桥梁

http.Handler接口

http 包暴露了一个接口 Handler。
它是我们引入自定义 Web 框架相关的连接点。

// ListenAndServe listens on the TCP network address addr and then calls
// Serve with handler to handle requests on incoming connections.
// Accepted connections are configured to enable TCP keep-alives.
//
// The handler is typically nil, in which case the DefaultServeMux is used.
//
// ListenAndServe always returns a non-nil error.
func ListenAndServe(addr string, handler Handler) error {
	server := &Server{Addr: addr, Handler: handler}
	return server.ListenAndServe()
}

接口的定义

版本一：只组合 http.Handler

//Server file
type Server interface {
	http.Handler
}

//Server_test file
func TestServer(t *testing.T) {
	var s Server
	http.ListenAndServe("localhost:8080", s)
}

优点：

用户在使用的时候只需要调用 http.ListenAndServe 就可以
和 HTTPS 协议完全无缝衔接
极简设计

缺点：

难以控制生命周期，并且在控制生命周期的时候增加回调支持
缺乏控制力：如果将来希望支持优雅退出的功能，将难以支持

版本二：组合 http.Handler 并且增加 Start 方法。

//Server file
type Server interface {
	http.Handler
	Start(addr string) error
}

//Server_test file
func TestServer(t *testing.T) {
	var s Server
	http.ListenAndServe("localhost:8080", s)

	s.Start(":8080")
	//Start 方法可以不需要 addr 参数，那么在创建实现类的时候传入地址就可以。
}

优点：

Server 既可以当成普通的 http.Handler 来使用，又可以作为一个独立的实体，拥有自己的管理生命周期的能力
完全的控制，可以为所欲为

缺点：

如果用户不希望使用 ListenAndServeTLS，那么 Server 需要提供 HTTPS 的支持

版本一和版本二都直接耦合了 Go 自带的 http 包，如果我们希望切换为 fasthttp 或者类似的 http 包，则会非常困难。

HTTPServer 实现 Server

// Server_test file
type HTTPServer struct {}

var _Server = &HTTPServer{}

func (s *HTTPServer) ServerHTTP(writer http.ResponseWriter, request *http.Request)  {
	
}

func (s *HTTPServer) Start(addr string) error {
	return http.ListenAndServe(addr, s)
}

该实现直接使用 http.ListenAndServe 来启动，后续可以根据需要替换为：

内部创建 http.Server 来启动
使用 http.Serve 来启动，换取更大的灵活性，如将端口监听和服务器启动分离等

ServeHTTP 则是我们整个 Web 框架的核心入口。我们将在整个方法内部完成：

Context 构建
路由匹配
执行业务逻辑

路由树

实现路由树得步骤：

全静态匹配
支持通配符匹配
支持参数路由

不同框架路由树的实现：

Beego：
- ControllerRegister：类似于容器，放着所有的路由树
  - 路由树是按照 HTTP method 来组织的，例如 GET 方法会对应有一棵路由树
- Tree：它代表的就是路由树，在 Beego 里
  面，一棵路由树被看做是由子树组成的
- leafInfo：代表叶子节点
- 树的设计并没有采用 children 式来定义，而是采用递归式的定义，即一棵树是由根节点 + 子树构成

Gin：
- methodTrees：也就是路由树也是按照 HTTP 方法组织的，例如 GET 会有一棵路由树
- methodTree：定义了单棵树。树在 Gin 里面采用的是 children 的定义方式，即树由节点构成（注意对比 Beego）
- node：代表树上的一个节点，里面维持住了 children，即子节点。同时有 nodeType 和 wildChild 来标记一些特殊节点
- gin是利用路由的公共前缀来构造路由树

路由树的设计总结：

归根结底就是设计一颗多叉树。

同时我们按照 HTTP 方法来组织路由树，每个 HTTP 方法一棵树
节点维持住自己的子节点

静态匹配

所谓的静态匹配，就是路径的每一段都必须严格相等。

接口设计

关键类型：

router：维持住了所有的路由树，它是整个路由注册和查找的总入口。router 里面维护了一个 map，是按照 HTTP 方法来组织路由树的
node：代表的是节点。它里面有一个 children 的 map 结构，使用 map 结构是为了快速查找到子节点

type router struct {
	// trees 是按照 HTTP 方法来组织的
	// 如 GET => *node
	trees map[string]*node
}

type node struct {
	path string
	//children 子节点
	//子节点的 path => *node
	children map[string]*node
	//handler 命中路由之后的逻辑
	handler HandlerFunc
}

func newRouter() router {
	return router{
		trees: map[string]*node{},
	}
}

用简化版的 TDD，即：

定义 API
定义测试
添加测试用例
实现，并且确保实现能够通过测试用例
重复 3-4 直到考虑了所有的场景
重复步骤 1-5

全局静态匹配

方法路由设计

{
	method: http.MethodGet,
	path:   "/",
},
{
	method: http.MethodGet,
	path:   "/user",
},
{
	method: http.MethodGet,
	path:   "/user/home",
},
{
	method: http.MethodGet,
	path:   "/order/detail",
},
{
	method: http.MethodPost,
	path:   "/order/create",
},
{
	method: http.MethodPost,
	path:   "/login",
},

非法用例进行判断

//非法样例
r = newRouter()

//空字符串
assert.PanicsWithValue(t, "web: 路由是空字符串", func() {
	r.addRoute(http.MethodGet, "", mockHandler)
})

//前导没有 /
assert.PanicsWithValue(t, "web: 路由必须以 / 开头", func() {
	r.addRoute(http.MethodGet, "a/b/c", mockHandler)
})
//后缀有 /
assert.PanicsWithValue(t, "web: 路由不能以 / 结尾", func() {
	r.addRoute(http.MethodGet, "/a/b/c/", mockHandler)
})

r.addRoute(http.MethodGet, "/", mockHandler)
// 根节点重复注册
assert.PanicsWithValue(t, "web: 路由重复注册", func() {
	r.addRoute(http.MethodGet, "/", mockHandler)
})
// 普通节点重复注册
r.addRoute(http.MethodGet, "/a/b/c", mockHandler)
assert.PanicsWithValue(t, http.MethodGet, func() {
	r.addRoute(http.MethodGet, "/a/b/c", mockHandler)
})

// 多个
assert.PanicsWithValue(t, "web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [/a//b]", func() {
	r.addRoute(http.MethodGet, "/a//b", mockHandler)
})
assert.PanicsWithValue(t, "web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [//a/b]", func() {
	r.addRoute(http.MethodGet, "//a/b", mockHandler)
})

添加路由

// addRoute 注册路由
// method 是 HTTP 方法
//	path 必须以 / 开始并且结尾不能有 /，中间也不允许有连续的 /
func (r *router) addRoute(method string, path string, handler HandlerFunc) {
	// 空字符串判断
	if path == "" {
		panic("web: 路由是空字符串")
	}
	// 必须以 / 为开头判断
	if path[0] != '/' {
		panic("web: 路由必须以 / 开头")
	}
	// 结尾不能有 /
	if path != "/" && path[len(path)-1] == '/' {
		panic("web: 不能以 / 为结尾")
	}

	root, ok := r.trees[method]
	//这是一个全新的 HTTP 方法，我们必须创建根节点
	if !ok {
		root = &node{
			path: "/",
		}
		r.trees[method] = root
	}
	// 路径冲突
	if path == "/" {
		if root.handler != nil {
			panic("web: 路径冲突")
		}
		root.handler = handler
		return
	}

	// 对路由进行切割
	segs := strings.Split(path[1:], "/")

	//开始进行处理
	for _, s := range segs {
		// 对空路径进行判断
		if s == "" {
			panic(fmt.Sprintf("web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [%s]", path))
		}
		root = root.childrenOfCreate(s)
	}
	if root.handler != nil {
		panic(fmt.Sprintf("web: 路由冲突[%s]", path))
	}
}

查找或者创建一个子节点

//子节点不存在则创建一个子节点
func (n *node) childrenOfCreate(path string) *node {
	if n.children == nil {
		n.children = make(map[string]*node)
	}
	child, ok := n.children[path]
	if !ok {
		child = &node{path: path}
		n.children[path] = child
	}
	return child
}

对 method 进行校验

定义为私有的 addRoute 即可实现：
- 用户只能通过 Get 或者 Post 方法来注册，那么可以确保 method 参数永远都是对的
- addRoute 在接口里面是私有的，限制了用户将无法实现 Server。实际上如果用户想要实现 Server，就约等于自己实现一个 Web 框架了。

path 之所以会有那么强的约束，是因为我希望用户写出来的代码风格要一致，就是注册的路由有些人喜欢加 /，有些人不喜欢加 /。

路由查找

// test_file
// 待测试路由
testRoutes := []struct {
	method string
	path   string
}{
	{
		method: http.MethodGet,
		path:   "/",
	},
	{
		method: http.MethodGet,
			path:   "/user",
	},
	{
		method: http.MethodGet,
		path:   "/order/create",
	},
	{
		method: http.MethodGet,
		path:   "/user/*/home",
	},
	{
		method: http.MethodGet,
		path:   "/order/*",
	},
}
// 测试样例
testCase := []struct {
	name     string
	method   string
	path     string
	found    bool
	wantNode *node
}{
	{
		name:   "method not found",
		method: http.MethodHead,
	},
	{
		name:   "path not found",
		method: http.MethodGet,
		path:   "/abc",
	},
	{
		name:   "root",
		method: http.MethodGet,
		found:  true,
		path:   "/",
		wantNode: &node{
			path:    "/",
			handler: mockHandler,
		},
	},
	{
		name:   "user",
		method: http.MethodGet,
		found:  true,
		path:   "/user",
		wantNode: &node{
			path:    "user",
			handler: mockHandler,
		},
	},
	{
		name:   "no handler",
		method: http.MethodPost,
		found:  true,
		path:   "/order",
		wantNode: &node{
			path: "order",
		},
	},
	{
		name:   "two layer",
		method: http.MethodPost,
		found:  true,
		path:   "/order/create",
		wantNode: &node{
			path:    "create",
			handler: mockHandler,
		},
	},
}

实现代码

// 路由查找实现
func (r *router) findRoute(method string, path string) (*node, bool) {
	root, ok := r.trees[method]
	if !ok {
		return nil, false
	}

	if path == "/" {
		return root, true
	}

	segs := strings.Split(strings.Trim(path, "/"), "/")
	for _, s := range segs {
		root, ok = root.childof(s)
		if !ok {
			return nil, false
		}
	}
	return root, true
}

//判断是否存在子节点
func (n *node) childof(path string) (*node, bool) {
	if n.children == nil {
		return nil, false
	}
	res, ok := n.children[path]
	return res, ok
}

Server 集成 router

这种情况下，用户只能使用 NewHTTPServer 来创建服务器实例。

如果考虑到用户可能自己 s := &HTTPServer 引起 panic，那么可以将 HTTPServer
做成私有的，即改名为 httpServer。

type HTTPServer struct{ router }

func NewHTTPServer() *HTTPServer {
	return &HTTPServer{
		router: newRouter(),
	}
}

func (s *HTTPServer) server(ctx *Context) {
	n, ok := s.findRoute(ctx.Req.Method, ctx.Req.URL.Path)
	if !ok || n.handler == nil {
		ctx.Resp.WriteHeader(404)
		ctx.Resp.Write([]byte("Not Found"))
		return
	}
	n.handler(ctx)
}

通配符匹配

所谓通配符匹配，是指用 * 号来表达匹配任何路径。要考虑几个问题：
- 如果路径是 /a/b/c 能不能命中 /a/* 路由？
- 如果注册了两个路由 /user/123/home 和 /user/*/*。那么输入路径 /user/123/detail 能不能命中 /user/*/*?
这两个都是理论上可以，但是不应该命中。
- 从实现的角度来说，其实并不难。
- 从用户的角度来说，他们不应该设计这种路由。给用户自由，但是也要限制不良实践。
- 后者要求的是一种可回溯的路由匹配，即发现 /user/123/home 匹配不上之后要回溯回去 /user/* 进一步查找，典型的投入大产出低的特性。

对 node 进行修改：

// node 代表路由树的节点
// 路由树的匹配顺序为：
// 1、静态完全匹配
// 2、通配符匹配
// 这是不回溯匹配
type node struct {
	path string
	//children 子节点
	//子节点的 path => *node
	children map[string]*node
	//handler 命中路由之后的逻辑
	handler HandlerFunc

	//通配符 * 表示的节点，任意匹配
	starChild *node
}

对 childof 进行修改：

func (n *node) childof(path string) (*node, bool) {
	if n.children == nil {
		return n.starChild, n.starChild != nil
	}
	res, ok := n.children[path]
	if !ok {
		return n.starChild, n.starChild != nil
	}
	return res, ok
}

对 childOrCreate 进行修改：

func (n *node) childrenOfCreate(path string) *node {
	if path == "*" {
		if n.children == nil {
			n.starChild = &node{path: "*"}
		}
	}
	if n.children == nil {
		n.children = make(map[string]*node)
	}
	child, ok := n.children[path]
	if !ok {
		child = &node{path: path}
		n.children[path] = child
	}
	return child
}

增加 addRouter 测试用例

{
	method: http.MethodGet,
	path:   "/order/*",
},
{
	method: http.MethodGet,
	path:   "/*",
},
{
	method: http.MethodGet,
	path:   "/*/*",
},
{
	method: http.MethodGet,
	path:   "/*/abc",
},
{
	method: http.MethodGet,
	path:   "/*/abc/**",
},

增加 findRoute 测试用例

// 通配符匹配
{
  // 命中/order/*
  name:   "star match",
  method: http.MethodPost,
  path:   "/order/delete",
  found:  true,
  wantNode: &node{
	path:    "*",
	handler: mockHandler,
	},
},
{
	//命中中间的通配符
    // user/*/home
	name:   "start in middle",
	method: http.MethodGet,
	path:   "/user/Tom/home",
	wantNode: &node{
	  path:    "home",
	  handler: mockHandler,
		},
},
{
	// 比/order/* 多一段
	name:   "overflow",
	method: http.MethodPost,
	path:   "/order/delete/123",
},

参数路径

所谓参数路径，就是指在路径中带上参数，同时这些参数对应的值可以被业务取出来使用。

例如：/user/:id ，如果输入路径 /user/123，那么会命中这个路由，并且 id = 123。

那么要考虑：
- 允不允许同样的参数路径和通配符匹配一起注册？例如同时注册 /user/* 和 /user/:id
可以，但是没必要，用户也不应该设计这种路由。

对 node 进行修改

type HandlerFunc func(ctx *Context)

// node 代表路由树的节点
// 路由树的匹配顺序为：
// 1、静态完全匹配
// 2、通配符匹配
// 这是不回溯匹配
type node struct {
	path string
	//children 子节点
	//子节点的 path => *node
	children map[string]*node
	//handler 命中路由之后的逻辑
	handler HandlerFunc

	//通配符 * 表示的节点，任意匹配
	starChild *node
	//路径参数
	paramchild *node
}

对 childrenOfCreate 进行变更

func (n *node) childrenOfCreate(path string) *node {
	if path == "*" {
		if n.children == nil {
			n.starChild = &node{path: "*"}
		}
	}

	if path == "*" {
		if n.paramchild != nil {
			panic(fmt.Sprintf("web: 非法路由，已有路径参数路由。不允许同时注册通配符路由和参数路由 [%s]", path))
		}
		if n.starChild == nil {
			n.starChild = &node{path: path}
		}
		return n.starChild
	}

	// 以 ： 开头，我们一般认为是参数路由
	if path[0] == ':' {
		if n.starChild != nil {
			panic(fmt.Sprintf("web: 非法路由，已有路径参数路由，不允许同时注册通配符路由和参数路由 [%s]", path))
		}
		if n.paramchild != nil {
			if n.paramchild.path != path {
				panic(fmt.Sprintf("web： 路由冲突， 参数路由冲突，已有 %s，新注册 %s", &n.paramchild.path, path))
			}
		} else {
			n.paramchild = &node{path: path}
		}
		return n.paramchild
	}
	if n.children == nil {
		n.children = make(map[string]*node)
	}
	child, ok := n.children[path]
	if !ok {
		child = &node{path: path}
		n.children[path] = child
	}
	return child
}

对 childof 进行修改

// childof 返回子节点
// 第一个返回值为 *node 是命中的节点
// 第二个返回值为 bool 代表是否命中参数值
// 第三个返回值为 bool 代表是否命中
func (n *node) childof(path string) (*node, bool, bool) {
	if n.children == nil {
		if n.paramchild != nil {
			return n.paramchild, true, true
		}
		return n.starChild, true, n.starChild != nil
	}
	res, ok := n.children[path]
	if !ok {
		if n.paramchild != nil {
			return n.paramchild, true, true
		}
		return n.starChild, false, n.starChild != nil
	}
	return res, true, true
}

获取路径参数

// 修改Context文件
type Context struct {
	Req        *http.Request
	Resp       http.ResponseWriter
	PathParams map[string]string
}

//新增 matchInfo 表示参数信息
type matchInfo struct {
	n          *node
	pathParams map[string]string
}

// 对 findRoute 进行修改
func (r *router) findRoute1(method string, path string) (*matchInfo, bool) {
	root, ok := r.trees[method]
	if !ok {
		return nil, false
	}

	if path == "/" {
		return &matchInfo{n: root}, true
	}

	segs := strings.Split(strings.Trim(path, "/"), "/")
	mi := &matchInfo{}
	for _, s := range segs {
		var matchParam bool
		root, matchParam, ok = root.childOf1(s)
		if !ok {
			return nil, false
		}
		if matchParam {
			mi.addValue(root.path[1:], s)
		}
	}
	mi.n = root
	return mi, true
}

如/user/:id，输入路径 /user/123，那么就相当于把 id = 123 这样一个键值对放进去了 mi (matchInfo) 里面。

路由树总结

已经注册了的路由，无法被覆盖，例如 /user/home 注册两次，会冲突
path 必须以 / 开始并且结尾不能有 /，中间也不允许有连续的 /
不能在同一个位置注册不同的参数路由，例如 /user/:id 和 /user/:name 冲突
不能在同一个位置同时注册通配符路由和参数路由，例如 /user/:id 和 /user/* 冲突
同名路径参数，在路由匹配的时候，值会被覆盖，例如 /user/:id/abc/:id，那么 /user/123/abc/456 最终 id = 456