Go Web 框架 echo 路由分析

【导读】本文介绍了 echo 框架的路由。

在分析之前，带着问题去查找答案。

• 官方 http 包已经提供了server的功能，为什么要用框架？

路由注册

简单的程序

我们来看看 echo 的三种匹配模式和优先级顺序匹配，优先级从下到下:

• Static (固定路径) 类似于/users/new
• Param (参数路径) 类似于/users/:id
• Match any (匹配所有) 类似于/users/1/files/*

看到这些模式，http 自带的路由只支持 固定路径 和 匹配所有的模式。这也是提高的地方。

我们来写个例子覆盖 echo 路由所支持的模式，

package main

import (
    "fmt"
    "net/http"
    "time"

    "github.com/labstack/echo"
)

func main() {
    // Echo instance
    e := echo.New()

    // Routes
    e.GET("/", index)
    e.GET("/users/new", usersNew)
    e.GET("/users/", users)
    e.GET("/ups/", ups)
    e.GET("/users/:name", usersName)
    e.GET("/users/1/files/*", usersFiles)
    addr := fmt.Sprintf("%s:%s", "localhost", "1323")
    server := &http.Server{
        Addr:         addr,
        ReadTimeout:  5 * time.Second,
        WriteTimeout: 5 * time.Second,
    }

    // Start server
    e.Logger.Fatal(e.StartServer(server))
}

func index(c echo.Context) error {
    return c.String(http.StatusOK, "index~")
}

func usersNew(c echo.Context) error {
    return c.String(http.StatusOK, "userNew!")
}

func ups(c echo.Context) error {
    return c.String(http.StatusOK, "ups!")
}

func users(c echo.Context) error {
    return c.String(http.StatusOK, "user!")
}

func usersName(c echo.Context) error {
    name := c.Param("name")
    return c.String(http.StatusOK, fmt.Sprintf("%s, %s", "hi", name))
}

func usersFiles(c echo.Context) error {
    return c.String(http.StatusOK, "usersFiles!")
}

例子先放着，我们先往下看看路由结构。

路由结构

先来看看路由的结构，了解一下路由需要哪些信息。

type (
    // Router 结构是`Echo`实例注册路由的地方。路由树
    Router struct {
        tree   *node // 节点
        routes map[string]*Route // map 形式，Route 包含请求handler 和 匹配信息
        echo   *Echo
    }
    // Route 包含请求的 handler 和 用于匹配的信息。
    Route struct {
        Method string `json:"method"`
        Path   string `json:"path"`
        Name   string `json:"name"`
    }
    // 节点结构
    node struct {
        kind          kind // 路由类型skind 0（/echo/hi）, pkind 1 (/users/:name),  akind 2(/orders/*)
        label         byte // prefix的第一个字符，根据label和kind来查找子节点
        prefix        string // 前缀
        parent        *node // 父节点
        children      children // 子节点，列表
        ppath         string // 原始路径
        pnames        []string // 路径参数只有类型为 1(:后面的的字段)， 2([*])才有，
        methodHandler *methodHandler // 请求类型
    }
    kind          uint8
    children      []*node
    methodHandler struct {
        connect  HandlerFunc
        delete   HandlerFunc
        get      HandlerFunc
        head     HandlerFunc
        options  HandlerFunc
        patch    HandlerFunc
        post     HandlerFunc
        propfind HandlerFunc
        put      HandlerFunc
        trace    HandlerFunc
    }
)

Echo 的路由基于 radix tree ，它让路由的查询非常快，且使用 sync pool 来重复利用内存并且几乎达到了零内存占用。看路由的结构，跟字典树的结构一致，基数树就是字典树的一种优化结构。所以，通过请求来查找 handler 会比 http 提供的路由要快。在 http 的路由查找中是通过遍历方式的O(n)，这里使用基数树O(K)的时间复杂度要好的多，同样比普通的Trie树的效率也要高。

路由绑定

以示例的代码，来看看是如何把路由信息装入到 Router 树的。

路由绑定

根据整个分析流程，我们先把整颗树还原成图像，这样更有利于了解。我们可以用广度优先搜索把树遍历出来。

// 广度层序打印节点
func (e *Echo) BfsShowRoute() {
    bfsTree(e.router.tree)
}

func bfsTree(n *node) error {
    var queue []*node
    queue = append(queue, n)
    for len(queue) > 0 {
        queueLen := len(queue)
        fmt.Println("----------------level----------------")
        for i := queueLen; i > 0; i-- {
            cn := queue[0]
            parentPrefix := ""
            if cn.parent != nil {
                parentPrefix = cn.parent.prefix
            }
            fmt.Println("kind:", cn.kind, ",lable:", string(cn.label), ",prefix:", cn.prefix, ",ppath:", cn.ppath, ",pnames:", cn.pnames, ",handler:", runtime.FuncForPC(reflect.ValueOf(cn.methodHandler.get).Pointer()).Name(), ",parent->", parentPrefix)
            if len(cn.children) > 0 {
                queue = append(queue, cn.children...)
            }
            queue = queue[1:len(queue)]
        }
    }
    return nil
}

在注册路由后，我们可以用上面的代码去遍历打印路由树，可以得到结果

----------------level----------------
kind: 0 ,lable: / ,prefix: / ,ppath: / ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> 
----------------level----------------
kind: 0 ,lable: u ,prefix: u ,ppath:  ,pnames: [] ,handler:  ,parent-> /
----------------level----------------
kind: 0 ,lable: s ,prefix: sers/ ,ppath: /users/ ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
kind: 0 ,lable: p ,prefix: ps/ ,ppath: /ups/ ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
----------------level----------------
kind: 0 ,lable: n ,prefix: new ,ppath: /users/new ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
kind: 1 ,lable: : ,prefix: : ,ppath: /users/:name ,pnames: [name] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> sers/
kind: 0 ,lable: 1 ,prefix: 1/files/ ,ppath:  ,pnames: [] ,handler:  ,parent-> sers/
----------------level----------------
kind: 2 ,lable: * ,prefix: * ,ppath: /users/1/files/* ,pnames: [*] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> 1/files/

根据结果我们可以还原出，我们这颗路由树的图形，

路由树

了解了整个路由树的构造之后，我们来看看这颗树是怎么构建的。

// 注册三要素 方法类型，路由path，handler函数
func (r *Router) Add(method, path string, h HandlerFunc) {
    // 校验是否空路径
    if path == "" {
        panic("echo: path cannot be empty")
    }
    // 规范路径
    if path[0] != '/' {
        path = "/" + path
    }
    pnames := []string{} // 路径参数
    ppath := path        // 原始路径
    // 按字符挨个遍历
    for i, l := 0, len(path); i < l; i++ {
        // 参数路径
        if path[i] == ':' {
            j := i + 1

            r.insert(method, path[:i], nil, skind, "", nil)
            // 找到参数路径的参数
            for ; i < l && path[i] != '/'; i++ {
            }
            // 把参数路径存入 pnames
            pnames = append(pnames, path[j:i])
            // 拼接路径 继续查找是否还有 参数路径
            path = path[:j] + path[i:]
            i, l = j, len(path)
            // 已经结束 插入参数路径节点
            if i == l {
                r.insert(method, path[:i], h, pkind, ppath, pnames)
                return
            }
            r.insert(method, path[:i], nil, pkind, "", nil)
        // 全量路径
        } else if path[i] == '*' {
            r.insert(method, path[:i], nil, skind, "", nil)
            // 全量参数都是"*"
            pnames = append(pnames, "*")
            r.insert(method, path[:i+1], h, akind, ppath, pnames)
            return
        }
    }
    // 普通路径
    r.insert(method, path, h, skind, ppath, pnames)
}

// 核心函数，构建字典树
func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string, pnames []string) {
    // 调整最大参数
    l := len(pnames)
    if *r.echo.maxParam < l {
        *r.echo.maxParam = l
    }

    cn := r.tree // 当前节点 root
    if cn == nil {
        panic("echo: invalid method")
    }
    search := path

    for {
        sl := len(search)
        pl := len(cn.prefix)
        l := 0

        // LCP
        max := pl
        if sl < max {
            max = sl
        }
        // 找到共同前缀的位置 例如 users/ 和 users/new 的共同前缀为 users/ 
        for ; l < max && search[l] == cn.prefix[l]; l++ {
        }

        if l == 0 {
            // root 节点处理
            cn.label = search[0]
            cn.prefix = search
            if h != nil {
                cn.kind = t
                cn.addHandler(method, h)
                cn.ppath = ppath
                cn.pnames = pnames
            }
        } else if l < pl {
            // 分离共同前缀 users/ 和 users/new 创建一个 prefix为new 的节点 
            n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames)

            // 重置父节点 prefix 为 users
            cn.kind = skind
            cn.label = cn.prefix[0]
            cn.prefix = cn.prefix[:l]
            // 清空该节点的孩子节点
            cn.children = nil
            cn.methodHandler = new(methodHandler)
            cn.ppath = ""
            cn.pnames = nil
            // 给该节点加上 prefix 为new的节点
            cn.addChild(n)

            if l == sl {
                // 如果是
                cn.kind = t
                cn.addHandler(method, h)
                cn.ppath = ppath
                cn.pnames = pnames
            } else {
                // 创建子节点
                n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames)
                n.addHandler(method, h)
                cn.addChild(n)
            }
        } else if l < sl {
            search = search[l:]
            // 找到 lable 一样的节点，用 lable 来判断共同前缀
            c := cn.findChildWithLabel(search[0])
            if c != nil {
                // 找到共同节点 继续
                cn = c
                continue
            }
            // 创建子节点
            n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames)
            n.addHandler(method, h)
            cn.addChild(n)
        } else {
            // 节点已存在
            if h != nil {
                cn.addHandler(method, h)
                cn.ppath = ppath
                if len(cn.pnames) == 0 { // Issue #729
                    cn.pnames = pnames
                }
            }
        }
        return
    }
}

从上面来看，整个节点是根据新增的路由不断调整而生成的radix tree。了解了整个结构之后，再来看看如何查找路由的handler。

请求如何匹配上 handler

回顾之前的 http server 的代码，

serverHandler{c.server}.ServeHTTP(w, w.req)

通过这个函数我们知道，其实是调用ServeHTTP 接口来具体处理请求。

echo.go

// ServeHTTP 实现了 `http.Handler` 接口, 该接口用来处理请求
func (e *Echo) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    // 获取 context，这里为啥用pool实现？据文档说是为了节省内存
    c := e.pool.Get().(*context)
    c.Reset(r, w)

    h := NotFoundHandler

    // 没有请求前需要调用的 http 中间件
    if e.premiddleware == nil {
        // 查找 handler的方法
        e.router.Find(r.Method, getPath(r), c)
        h = c.Handler()
        h = applyMiddleware(h, e.middleware...)
    } else {
        h = func(c Context) error {
            e.router.Find(r.Method, getPath(r), c)
            h := c.Handler()
            h = applyMiddleware(h, e.middleware...)
            return h(c)
        }
        h = applyMiddleware(h, e.premiddleware...)
    }

    // 执行处理逻辑 
    if err := h(c); err != nil {
        e.HTTPErrorHandler(err, c)
    }

    // 释放 context
    e.pool.Put(c)
}

// 通过 method 和 path 查找注册的 handler，解析 URL 参数并把参数装进 context
func (r *Router) Find(method, path string, c Context) {
    ctx := c.(*context)
    ctx.path = path
    fmt.Println(ctx.path, ctx.query, ctx.pvalues, method, path, "ctx....")
    cn := r.tree // 当前节点

    var (
        search  = path
        child   *node         // 子节点
        n       int           // 参数计数器
        nk      kind          // 下一个节点的 Kind
        nn      *node         // 下一个节点
        ns      string        // 下一个 search 字符串
        pvalues = ctx.pvalues 
    )

    // 搜索顺序 static > param > any
    for {
        if search == "" {
            break
        }

        pl := 0 // Prefix length
        l := 0  // LCP length

        if cn.label != ':' {
            sl := len(search)
            pl = len(cn.prefix)

            // LCP
            max := pl
            if sl < max {
                max = sl
            }
            // 找到共同前缀的起始点
            for ; l < max && search[l] == cn.prefix[l]; l++ {
            }
        }

        if l == pl {
            // 重合 继续搜索
            search = search[l:]
        } else {
            cn = nn
            search = ns
            if nk == pkind {
                goto Param
            } else if nk == akind {
                goto Any
            }
            // 没有找到子节点 直接返回
            return
        }

        if search == "" {
            break
        }

        // Static 节点
        if child = cn.findChild(search[0], skind); child != nil {
            // Save next
            if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
                nk = pkind
                nn = cn
                ns = search
            }
            cn = child
            continue
        }

    // Param 节点
    Param:
        if child = cn.findChildByKind(pkind); child != nil {
            // Issue #378
            if len(pvalues) == n {
                continue
            }

            // Save next
            if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
                nk = akind
                nn = cn
                ns = search
            }

            cn = child
            i, l := 0, len(search)
            for ; i < l && search[i] != '/'; i++ {
            }
            pvalues[n] = search[:i]
            n++
            search = search[i:]
            continue
        }

    // Any 节点
    Any:
        if cn = cn.findChildByKind(akind); cn == nil {
            if nn != nil {
                cn = nn
                nn = cn.parent // Next (Issue #954)
                search = ns
                if nk == pkind {
                    goto Param
                } else if nk == akind {
                    goto Any
                }
            }
            // Not found
            return
        }
        pvalues[len(cn.pnames)-1] = search
        break
    }

    ctx.handler = cn.findHandler(method)
    ctx.path = cn.ppath
    ctx.pnames = cn.pnames

    // NOTE: Slow zone...
    if ctx.handler == nil {
        ctx.handler = cn.checkMethodNotAllowed()

        // Dig further for any, might have an empty value for *, e.g.
        // serving a directory. Issue #207.
        if cn = cn.findChildByKind(akind); cn == nil {
            return
        }
        if h := cn.findHandler(method); h != nil {
            ctx.handler = h
        } else {
            ctx.handler = cn.checkMethodNotAllowed()
        }
        ctx.path = cn.ppath
        ctx.pnames = cn.pnames
        pvalues[len(cn.pnames)-1] = ""
    }

    return

整个过程可以通过把路由树画出来，然后一个一个case去跑下来，可以理解整个构建和查找的过程。

再回过头来看看之前的问题

• 官方 http 包已经提供了server的功能，为什么要用框架？
  从echo这个框架的角度来说，提供了支持更多类型以及效率更高的路由，路由分组，http中间件，更优化的内存使用，请求参数上下文处理等等。从性能和功能的角度都极大的提升了开发效率。