Go Web 框架 echo 路由分析

【導讀】本文介紹了 echo 框架的路由。

在分析之前,帶着問題去查找答案。

路由註冊

簡單的程序

我們來看看 echo 的三種匹配模式和優先級順序匹配,優先級從下到下:

看到這些模式,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 去跑下來,可以理解整個構建和查找的過程。

再回過頭來看看之前的問題

轉自:

jianshu.com/p/40f9213b702f

Go 開發大全

參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/axAIKVMRrERTVQyUxOJ3_g