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 中間件,更優化的內存使用,請求參數上下文處理等等。從性能和功能的角度都極大的提升了開發效率。
轉自:
jianshu.com/p/40f9213b702f
Go 開發大全
參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/axAIKVMRrERTVQyUxOJ3_g