美文网首页
golang echo 框架路由分析

golang echo 框架路由分析

作者: 咔叽咔叽_ | 来源:发表于2019-06-05 23:31 被阅读0次

    几个问题

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

    • 官方 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中间件,更优化的内存使用,请求参数上下文处理等等。从性能和功能的角度都极大的提升了开发效率。

    相关文章

      网友评论

          本文标题:golang echo 框架路由分析

          本文链接:https://www.haomeiwen.com/subject/lqsptctx.html