03｜路由：如何让请求更快寻找到目标函数？

思考并回答以下问题：

geekbang/03

代码结构图

路由规则的需求

• 需求1：HTTP方法匹配，比如GET、POST、PUT、DELETE。
• 需求2：静态路由匹配，在第一讲中提到的DefaultServerMux这个路由器，从内部的map中直接根据key寻找value，这种查找路由的方式就是静态路由匹配。
• 需求3：批量通用前缀
• 需求4：动态路由匹配

// 注册路由规则
func registerRouter(core *framework.Core) {
    // 需求1+2:HTTP方法+静态路由匹配
    core.Post("/user/login", UserLoginController)

    // 需求3:批量通用前缀
    subjectApi := core.Group("/subject")
    {
        subjectApi.Post("/add", SubjectAddController)
        // 需求4:动态路由
        subjectApi.Delete("/:id", SubjectDelController)
        subjectApi.Put("/:id", SubjectUpdateController)
        subjectApi.Get("/:id", SubjectGetController)
        subjectApi.Get("/list/all", SubjectListController)
    }  
}

实现HTTP方法和静态路由匹配

首先看第一个需求和第二个需求。由于有两个待匹配的规则，Request-URI和Method，所以自然联想到可以使用两级哈希表来创建映射。

第一级hash是请求Method，第二级hash是Request-URI。

接下来按框架使用者使用路由的顺序分成四步来完善这个结构：定义路由map、注册路由、匹配路由、填充ServeHTTP方法。

首先，第一层map的每个key值都代表Method，而且为了避免之后在匹配的时候，要转换一次大小写，将每个key都设置为大写。

core.go

// 框架核心结构
type Core struct {
    router map[string]map[string]ControllerHandler // 二级map
}

// 初始化框架核心结构
func NewCore() *Core {
    // 定义二级map
    getRouter := map[string]ControllerHandler{}
    postRouter := map[string]ControllerHandler{}
    putRouter := map[string]ControllerHandler{}
    deleteRouter := map[string]ControllerHandler{}

    // 将二级map写入一级map
    router := map[string]map[string]ControllerHandler{}
    router["GET"] = getRouter
    router["POST"] = postRouter
    router["PUT"] = putRouter
    router["DELETE"] = deleteRouter

    return &Core{router: router}
}

下一步就是路由注册，将路由注册函数按照Method名拆分为4个方法：Get、Post、Put和Delete。

// 对应 Method = Get
func (c *Core) Get(url string, handler ControllerHandler) {
    upperUrl := strings.ToUpper(url)
    c.router["GET"][upperUrl] = handler
}

// 对应 Method = POST
func (c *Core) Post(url string, handler ControllerHandler) {
    upperUrl := strings.ToUpper(url)
    c.router["POST"][upperUrl] = handler
}

// 对应 Method = PUT
func (c *Core) Put(url string, handler ControllerHandler) {
    upperUrl := strings.ToUpper(url)
    c.router["PUT"][upperUrl] = handler
}

// 对应 Method = DELETE
func (c *Core) Delete(url string, handler ControllerHandler) {
    upperUrl := strings.ToUpper(url)
    c.router["DELETE"][upperUrl] = handler
}

这里将URL全部转换为大写了，在后续匹配路由的时候，也要记得把匹配的URL进行大写转换，这样的路由就会是“大小写不敏感”的，对使用者的容错性就大大增加了。

注册完路由之后，如何匹配路由就是第三步需要做的事情了。首先实现匹配路由方法。

core.go

// 匹配路由，如果没有匹配到，返回nil
func (c *Core) FindRouteByRequest(request *http.Request) ControllerHandler {
    // uri 和 method 全部转换为大写，保证大小写不敏感
    uri := request.URL.Path
    method := request.Method
    upperMethod := strings.ToUpper(method)
    upperUri := strings.ToUpper(uri)

    // 查找第一层map
    if methodHandlers, ok := c.router[upperMethod]; ok {
        // 查找第二层map
        if handler, ok := methodHandlers[upperUri]; ok {
            return handler
        }
    }
    return nil
}

代码很容易看懂，匹配逻辑就是去二层哈希map中一层层匹配，先查找第一层匹配Method，再查第二层匹配Request-URI。

最后，就可以填充未实现的ServeHTTP方法了，所有请求都会进到这个函数中处理。

core.go

func (c *Core) ServeHTTP(response http.ResponseWriter, request *http.Request) {

    // 封装自定义context
    ctx := NewContext(request, response)

    // 寻找路由
    router := c.FindRouteByRequest(request)
    if router == nil {
        // 如果没有找到，这里打印日志
        ctx.Json(404, "not found")
        return
    }

    // 调用路由函数，如果返回err 代表存在内部错误，返回500状态码
    if err := router(ctx); err != nil {
        ctx.Json(500, "inner error")
        return
    }
}

这个函数就把前面三讲的内容都串起来了。先封装第二讲创建的自定义Context，然后使用FindRouteByRequest函数寻找需要的路由，如果没有找到路由，返回404状态码；如果找到了路由，就调用路由控制器，另外如果路由控制器出现内部错误，返回500状态码。

到这里，第一个和第二个需求就都完成了。

实现批量通用前缀

对于第三个需求，可以通过一个Group方法归拢路由前缀地址。

route.go

// 注册路由规则
func registerRouter(core *framework.Core) {
    // 需求1+2:HTTP方法+静态路由匹配
    core.Get("/user/login", UserLoginController)

    // 需求3:批量通用前缀
    subjectApi := core.Group("/subject")
    {
        subjectApi.Get("/list", SubjectListController)
    }
}

看下这个Group方法，它的参数是一个前缀字符串，返回值应该是包含Get、Post、Put、Delete方法的一个结构，给这个结构命名Group，在其中实现各种方法。

这么设计直接返回Group结构，确实可以实现功能，但试想一下，随着框架发展，如果发现Group结构的具体实现并不符合的要求了，需要引入实现另一个Group2结构，该怎么办？直接修改Group结构的具体实现么？

其实更好的办法是使用接口来替代结构定义。在框架设计之初，要保证框架使用者，在最少的改动中，就能流畅迁移到Group2，这个时候，如果返回接口IGroup，而不是直接返回Group结构，就不需要修改core.Group的定义了，只需要修改core.Group的具体实现，返回Group2就可以。

尽量使用接口来解耦合，是一种比较好的设计思路。

这里定义IGroup接口来作为Group方法的返回值。在框架文件夹下创建group.go文件来存放分组相关的信息：

// IGroup 代表前缀分组
type IGroup interface {
    Get(string, ControllerHandler)
    Post(string, ControllerHandler)
    Put(string, ControllerHandler)
    Delete(string, ControllerHandler)
}

并且继续搭好Group结构代码来实现这个接口：

// 初始化Group
func NewGroup(core *Core, prefix string) *Group {
    return &Group{
        core:   core,
        prefix: prefix,
    }
}

// 实现Get方法
func (g *Group) Get(uri string, handler ControllerHandler) {
    uri = g.prefix + uri
    g.core.Get(uri, handler)
}

....

// 从core中初始化这个Group
func (c *Core) Group(prefix string) IGroup {
    return NewGroup(c, prefix)
}

这个Group结构包含自身的前缀地址和Core结构的指针。它的Get、Put、Post、Delete方法就是把这个Group结构的前缀地址和目标地址组合起来，作为Core的Request-URI地址。

回到的路由，使用IGroup接口后，core.Group这个方法返回的是一个约定，而不依赖具体的Group实现。

实现动态路由匹配

首先，一旦引入了动态路由匹配的规则，之前使用的哈希规则就无法使用了。因为有通配符，在匹配Request-URI的时候，请求URI的某个字符或者某些字符是动态变化的，无法使用URI做为key来匹配。那么，就需要其他的算法来支持路由匹配。

这个问题本质是一个字符串匹配，而字符串匹配，比较通用的高效方法就是字典树，也叫trie树。

先简单梳理下trie树的数据结构。trie树不同于二叉树，它是多叉的树形结构，根节点一般是空字符串，而叶子节点保存的通常是字符串，一个节点的所有子孙节点都有相同的字符串前缀。

所以根据trie树的特性，结合前三条路由规则，可以构建出这样的结构：

1 /user/login
2 /user/logout
3 /subject/name
4 /subject/name/age
5 /subject/:id/name

这个trie树是按照路由地址的每个段（segment）来切分的，每个segment在trie树中都能找到对应节点，每个节点保存一个segment。树中，每个叶子节点都代表一个URI，对于中间节点来说，有的中间节点代表一个URI（比如上图中的/subject/name），而有的中间节点并不是一个URI（因为没有路由规则对应这个URI）。

1，定义树和节点的数据结构

2，编写函数：“增加路由规则”

3，编写函数：“查找路由”

4，将“增加路由规则”和“查找路由”添加到框架中

首先定义对应的数据结构（node和tree）。先在框架文件夹下创建tree.go文件，存储trie树相关逻辑。

// 代表树结构
type Tree struct {
    root *node // 根节点
}

// 代表节点
type node struct {
    isLast  bool              // 代表这个节点是否可以成为最终的路由规则。该节点是否能成为一个独立的uri, 是否自身就是一个终极节点
    segment string            // uri中的字符串，代表这个节点表示的路由中某个段的字符串
    handler ControllerHandler // 代表这个节点中包含的控制器，用于最终加载调用
    childs  []*node           // 代表这个节点下的子节点
}

Tree结构中包含一个根节点，只是这个根节点是一个没有segment的空的根节点。

node的结构定义了四个字段。childs字段让node组成了一个树形结构，handler是具体的业务控制器逻辑存放位置，segment是树中的这个节点存放的内容，isLast用于区别这个树中的节点是否有实际的路由含义。

有了数据结构后，第二步，就往Tree这个trie树结构中增加“路由规则”的逻辑。之前提过会存在通配符，那直接加规则其实是有可能冲突的。比如：

/user/name
/user/:id

这两个路由规则实际上就冲突了，如果请求地址是/user/name，那么两个规则都匹配，无法确定哪个规则生效。所以在增加路由之前，需要判断这个路由规则是否已经在trie树中存在了。

可以用matchNode方法，寻找某个路由在trie树中匹配的节点，如果有匹配节点，返回节点指针，否则返回nil。matchNode方法的参数是一个URI，返回值是指向node的指针，它的实现思路是使用函数递归：

首先，将需要匹配的URI根据第一个分隔符/进行分割，只需要最多分割成为两个段。

如果只能分割成一个段，说明URI中没有分隔符了，这时候再检查下一级节点中是否有匹配这个段的节点就行。

如果分割成了两个段，用第一个段来检查下一个级节点中是否有匹配这个段的节点。

• 如果没有，说明这个路由规则在树中匹配不到。
• 如果下一级节点中有符合第一个分割段的（这里需要注意可能不止一个符合），就将所有符合的节点进行函数递归，重新应用于matchNode函数中，只不过这时候matchNode函数作用于子节点，参数变成了切割后的第二个段。

整个流程里，会频繁使用到“过滤下一层满足segment规则的子节点”，所以也用一个函数filterChildNodes将它封装起来。这个函数的逻辑就比较简单了：遍历下一层子节点，判断segment是否匹配传入的参数segment。

tree.go

// 判断一个segment是否是通用segment，即以:开头
func isWildSegment(segment string) bool {
    return strings.HasPrefix(segment, ":")
}

// 过滤下一层满足segment规则的子节点
func (n *node) filterChildNodes(segment string) []*node {
    if len(n.childs) == 0 {
        return nil
    }
    // 如果segment是通配符，则所有下一层子节点都满足需求
    if isWildSegment(segment) {
        return n.childs
    }

    nodes := make([]*node, 0, len(n.childs))
    // 过滤所有的下一层子节点
    for _, cnode := range n.childs {
        if isWildSegment(cnode.segment) {
            // 如果下一层子节点有通配符，则满足需求
            nodes = append(nodes, cnode)
        } else if cnode.segment == segment {
            // 如果下一层子节点没有通配符，但是文本完全匹配，则满足需求
            nodes = append(nodes, cnode)
        }
    }

    return nodes
}

// 判断路由是否已经在节点的所有子节点树中存在了
func (n *node) matchNode(uri string) *node {
    // 使用分隔符将uri切割为两个部分
    segments := strings.SplitN(uri, "/", 2)
    // 第一个部分用于匹配下一层子节点
    segment := segments[0]
    if !isWildSegment(segment) {
        segment = strings.ToUpper(segment)
    }
    // 匹配符合的下一层子节点
    cnodes := n.filterChildNodes(segment)
    // 如果当前子节点没有一个符合，那么说明这个uri一定是之前不存在, 直接返回nil
    if cnodes == nil || len(cnodes) == 0 {
        return nil
    }

    // 如果只有一个segment，则是最后一个标记
    if len(segments) == 1 {
        // 如果segment已经是最后一个节点，判断这些cnode是否有isLast标志
        for _, tn := range cnodes {
            if tn.isLast {
                return tn
            }
        }

        // 都不是最后一个节点
        return nil
    }

    // 如果有2个segment, 递归每个子节点继续进行查找
    for _, tn := range cnodes {
        tnMatch := tn.matchNode(segments[1])
        if tnMatch != nil {
            return tnMatch
        }
    }
    return nil
}

现在有了matchNode和filterChildNodes函数，就可以开始写第二步里最核心的增加路由的函数逻辑了。

首先，确认路由是否冲突。先检查要增加的路由规则是否在树中已经有可以匹配的节点了。如果有的话，代表当前待增加的路由和已有路由存在冲突，这里用到了刚刚定义的matchNode。更新刚才框架文件夹中的tree.go文件：

// 增加路由节点
func (tree *Tree) AddRouter(uri string, handler ControllerHandler) error {
    n := tree.root
    // 确认路由是否冲突
    if n.matchNode(uri) != nil {
        return errors.New("route exist: " + uri)
    }

    ...
}

然后继续增加路由规则。增加路由的每个段时，先去树的每一层中匹配查找，如果已经有了符合这个段的节点，就不需要创建节点，继续匹配待增加路由的下个段；否则，需要创建一个新的节点用来代表这个段。这里，用到了定义的filterChildNodes。

// 增加路由节点
/*
/book/list
/book/:id (冲突)
/book/:id/name
/book/:student/age
/:user/name
/:user/name/:age(冲突)
*/
func (tree *Tree) AddRouter(uri string, handler ControllerHandler) error {
    n := tree.root
    if n.matchNode(uri) != nil {
        return errors.New("route exist: " + uri)
    }

    segments := strings.Split(uri, "/")
    // 对每个segment
    for index, segment := range segments {

        // 最终进入Node segment的字段
        if !isWildSegment(segment) {
            segment = strings.ToUpper(segment)
        }
        isLast := index == len(segments)-1

        var objNode *node // 标记是否有合适的子节点

        childNodes := n.filterChildNodes(segment)
        // 如果有匹配的子节点
        if len(childNodes) > 0 {
            // 如果有segment相同的子节点，则选择这个子节点
            for _, cnode := range childNodes {
                if cnode.segment == segment {
                    objNode = cnode
                    break
                }
            }
        }

        if objNode == nil {
            // 创建一个当前node的节点
            cnode := newNode()
            cnode.segment = segment
            if isLast {
                cnode.isLast = true
                cnode.handler = handler
            }
            n.childs = append(n.childs, cnode)
            objNode = cnode
        }

        n = objNode
    }

    return nil
}

到这里，第二步增加路由的规则逻辑已经有了，要开始第三步，编写“查找路由”的逻辑。这里你会发现，由于之前已经定义过matchNode（匹配路由节点），所以这里只需要复用这个函数就行了。

// 匹配uri
func (tree *Tree) FindHandler(uri string) ControllerHandler {
    // 直接复用matchNode函数，uri是不带通配符的地址
    matchNode := tree.root.matchNode(uri)
    if matchNode == nil {
        return nil
    }
    return matchNode.handler
}

前三步已经完成了，最后一步，把“增加路由规则”和“查找路由”添加到框架中。还记得吗，在静态路由匹配的时候，在Core中使用哈希定义的路由，这里将哈希替换为trie树。

core.go

type Core struct {
    router map[string]*Tree // all routers
}

对应路由增加的方法，也从哈希的增加逻辑，替换为trie树的“增加路由规则”逻辑。

core.go

// 匹配GET 方法, 增加路由规则
func (c *Core) Get(url string, handler ControllerHandler) {
    if err := c.router["GET"].AddRouter(url, handler); err != nil {
        log.Fatal("add router error: ", err)
    }
}

// 匹配POST 方法, 增加路由规则
func (c *Core) Post(url string, handler ControllerHandler) {
    if err := c.router["POST"].AddRouter(url, handler); err != nil {
        log.Fatal("add router error: ", err)
    }
}

// 匹配PUT 方法, 增加路由规则
func (c *Core) Put(url string, handler ControllerHandler) {
    if err := c.router["PUT"].AddRouter(url, handler); err != nil {
        log.Fatal("add router error: ", err)
    }
}

// 匹配DELETE 方法, 增加路由规则
func (c *Core) Delete(url string, handler ControllerHandler) {
    if err := c.router["DELETE"].AddRouter(url, handler); err != nil {
        log.Fatal("add router error: ", err)
    }
}

之前在Core中定义的匹配路由函数的实现逻辑，从哈希匹配修改为trie树匹配就可以了。

core.go

// 匹配路由，如果没有匹配到，返回nil
func (c *Core) FindRouteByRequest(request *http.Request) ControllerHandler {
    // uri 和 method 全部转换为大写，保证大小写不敏感
    uri := request.URL.Path
    method := request.Method
    upperMethod := strings.ToUpper(method)

    // 查找第一层map
    if methodHandlers, ok := c.router[upperMethod]; ok {
        return methodHandlers.FindHandler(uri)
    }
    return nil
}

动态匹配规则就改造完成了。

验证

验证一下：定义包含有静态路由、批量通用前缀、动态路由的路由规则，每个控制器就直接输出控制器的名字，然后启动服务。

route.go

// 注册路由规则
func registerRouter(core *framework.Core) {
    // 需求1+2:HTTP方法+静态路由匹配
    core.Get("/user/login", UserLoginController)

    // 需求3:批量通用前缀
    subjectApi := core.Group("/subject")
    {
        // 需求4:动态路由
        subjectApi.Delete("/:id", SubjectDelController)
        subjectApi.Put("/:id", SubjectUpdateController)
        subjectApi.Get("/:id", SubjectGetController)
        subjectApi.Get("/list/all", SubjectListController)
    }
}

同时在业务文件夹下创建对应的业务控制器user_controller.go和subject_controller.go。具体里面的逻辑代码就是打印出对应的控制器名字，比如

func UserLoginController(c *framework.Context) error {
    // 打印控制器名字
    c.Json(200, "ok, UserLoginController")
    return nil
}

来看服务启动情况：访问地址/user/login匹配路由UserLoginContorller。

访问地址/subject/list/all匹配路由SubjectListController。

访问地址/subject/100匹配动态路由SubjectGetController。

路由规则符合要求！

思考题

针对第三个需求“批量通用前缀”，扩展一下变成：需要能多层嵌套通用前缀，这么定义路由：

// 注册路由规则
func registerRouter(core *framework.Core) {
    // 静态路由+HTTP方法匹配
    core.Get("/user/login", UserLoginController)

    // 批量通用前缀
    subjectApi := core.Group("/subject")
    {
        subjectInnerApi := subjectApi.Group("/info")
        {
            subjectInnerApi.Get("/name", SubjectNameController)
        }
    }
}

如何实现呢？