原文鏈接:https://chai2010.cn/advanced-go-programming-book/ch5-web/ch5-02-router.html
在常見的 Web 框架中,router 是必備的組件。Go 語言圈子里 router 也時常被稱為 http
的 multiplexer。在上一節(jié)中我們通過對 Burrow 代碼的簡單學習,已經(jīng)知道如何用 http
標準庫中內(nèi)置的 mux 來完成簡單的路由功能了。如果開發(fā) Web 系統(tǒng)對路徑中帶參數(shù)沒什么興趣的話,用 http
標準庫中的 mux
就可以。
RESTful 是幾年前刮起的 API 設(shè)計風潮,在 RESTful 中除了 GET 和 POST 之外,還使用了 HTTP 協(xié)議定義的幾種其它的標準化語義。具體包括:
const (
MethodGet = "GET"
MethodHead = "HEAD"
MethodPost = "POST"
MethodPut = "PUT"
MethodPatch = "PATCH" // RFC 5789
MethodDelete = "DELETE"
MethodConnect = "CONNECT"
MethodOptions = "OPTIONS"
MethodTrace = "TRACE"
)
來看看 RESTful 中常見的請求路徑:
GET /repos/:owner/:repo/comments/:id/reactions
POST /projects/:project_id/columns
PUT /user/starred/:owner/:repo
DELETE /user/starred/:owner/:repo
相信聰明的你已經(jīng)猜出來了,這是 Github 官方文檔中挑出來的幾個 API 設(shè)計。RESTful 風格的 API 重度依賴請求路徑。會將很多參數(shù)放在請求 URI 中。除此之外還會使用很多并不那么常見的 HTTP 狀態(tài)碼,不過本節(jié)只討論路由,所以先略過不談。
如果我們的系統(tǒng)也想要這樣的 URI 設(shè)計,使用標準庫的 mux
顯然就力不從心了。
較流行的開源 go Web 框架大多使用 httprouter,或是基于 httprouter 的變種對路由進行支持。前面提到的 Github 的參數(shù)式路由在 httprouter 中都是可以支持的。
因為 httprouter 中使用的是顯式匹配,所以在設(shè)計路由的時候需要規(guī)避一些會導致路由沖突的情況,例如:
conflict:
GET /user/info/:name
GET /user/:id
no conflict:
GET /user/info/:name
POST /user/:id
簡單來講的話,如果兩個路由擁有一致的 http 方法 (指 GET
、POST
、PUT
、DELETE
) 和請求路徑前綴,且在某個位置出現(xiàn)了 A 路由是 wildcard(指 :id
這種形式)參數(shù),B 路由則是普通字符串,那么就會發(fā)生路由沖突。路由沖突會在初始化階段直接 panic:
panic: wildcard route ':id' conflicts with existing children in path '/user/:id'
goroutine 1 [running]:
github.com/cch123/httprouter.(*node).insertChild(0xc4200801e0, 0xc42004fc01, 0x126b177, 0x3, 0x126b171, 0x9, 0x127b668)
/Users/caochunhui/go_work/src/github.com/cch123/httprouter/tree.go:256 +0x841
github.com/cch123/httprouter.(*node).addRoute(0xc4200801e0, 0x126b171, 0x9, 0x127b668)
/Users/caochunhui/go_work/src/github.com/cch123/httprouter/tree.go:221 +0x22a
github.com/cch123/httprouter.(*Router).Handle(0xc42004ff38, 0x126a39b, 0x3, 0x126b171, 0x9, 0x127b668)
/Users/caochunhui/go_work/src/github.com/cch123/httprouter/router.go:262 +0xc3
github.com/cch123/httprouter.(*Router).GET(0xc42004ff38, 0x126b171, 0x9, 0x127b668)
/Users/caochunhui/go_work/src/github.com/cch123/httprouter/router.go:193 +0x5e
main.main()
/Users/caochunhui/test/go_web/httprouter_learn2.go:18 +0xaf
exit status 2
還有一點需要注意,因為 httprouter 考慮到字典樹的深度,在初始化時會對參數(shù)的數(shù)量進行限制,所以在路由中的參數(shù)數(shù)目不能超過 255,否則會導致 httprouter 無法識別后續(xù)的參數(shù)。不過這一點上也不用考慮太多,畢竟 URI 是人設(shè)計且給人來看的,相信沒有長得夸張的 URI 能在一條路徑中帶有 200 個以上的參數(shù)。
除支持路徑中的 wildcard 參數(shù)之外,httprouter 還可以支持 *
號來進行通配,不過 *
號開頭的參數(shù)只能放在路由的結(jié)尾,例如下面這樣:
Pattern: /src/*filepath
/src/ filepath = ""
/src/somefile.go filepath = "somefile.go"
/src/subdir/somefile.go filepath = "subdir/somefile.go"
這種設(shè)計在 RESTful 中可能不太常見,主要是為了能夠使用 httprouter 來做簡單的 HTTP 靜態(tài)文件服務(wù)器。
除了正常情況下的路由支持,httprouter 也支持對一些特殊情況下的回調(diào)函數(shù)進行定制,例如 404 的時候:
r := httprouter.New()
r.NotFound = http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
w.Write([]byte("oh no, not found"))
})
或者內(nèi)部 panic 的時候:
r.PanicHandler = func(w http.ResponseWriter, r *http.Request, c interface{}) {
log.Printf("Recovering from panic, Reason: %#v", c.(error))
w.WriteHeader(http.StatusInternalServerError)
w.Write([]byte(c.(error).Error()))
}
目前開源界最為流行(star 數(shù)最多)的 Web 框架 gin 使用的就是 httprouter 的變種。
httprouter 和眾多衍生 router 使用的數(shù)據(jù)結(jié)構(gòu)被稱為壓縮字典樹(Radix Tree)。讀者可能沒有接觸過壓縮字典樹,但對字典樹(Trie Tree)應(yīng)該有所耳聞。圖 5-1 是一個典型的字典樹結(jié)構(gòu):
圖 5-1 字典樹
字典樹常用來進行字符串檢索,例如用給定的字符串序列建立字典樹。對于目標字符串,只要從根節(jié)點開始深度優(yōu)先搜索,即可判斷出該字符串是否曾經(jīng)出現(xiàn)過,時間復雜度為 O(n)
,n 可以認為是目標字符串的長度。為什么要這樣做?字符串本身不像數(shù)值類型可以進行數(shù)值比較,兩個字符串對比的時間復雜度取決于字符串長度。如果不用字典樹來完成上述功能,要對歷史字符串進行排序,再利用二分查找之類的算法去搜索,時間復雜度只高不低??烧J為字典樹是一種空間換時間的典型做法。
普通的字典樹有一個比較明顯的缺點,就是每個字母都需要建立一個孩子節(jié)點,這樣會導致字典樹的層數(shù)比較深,壓縮字典樹相對好地平衡了字典樹的優(yōu)點和缺點。是典型的壓縮字典樹結(jié)構(gòu):
圖 5-2 壓縮字典樹
每個節(jié)點上不只存儲一個字母了,這也是壓縮字典樹中 “壓縮” 的主要含義。使用壓縮字典樹可以減少樹的層數(shù),同時因為每個節(jié)點上數(shù)據(jù)存儲也比通常的字典樹要多,所以程序的局部性較好(一個節(jié)點的 path 加載到 cache 即可進行多個字符的對比),從而對 CPU 緩存友好。
我們來跟蹤一下 httprouter 中,一個典型的壓縮字典樹的創(chuàng)建過程,路由設(shè)定如下:
PUT /user/installations/:installation_id/repositories/:repository_id
GET /marketplace_listing/plans/
GET /marketplace_listing/plans/:id/accounts
GET /search
GET /status
GET /support
補充路由:
GET /marketplace_listing/plans/ohyes
最后一條補充路由是我們臆想的,除此之外所有 API 路由均來自于 api.github.com
。
httprouter 的 Router 結(jié)構(gòu)體中存儲壓縮字典樹使用的是下述數(shù)據(jù)結(jié)構(gòu):
// 略去了其它部分的 Router struct
type Router struct {
// ...
trees map[string]*node
// ...
}
trees
中的 key
即為 HTTP 1.1 的 RFC 中定義的各種方法,具體有:
GET
HEAD
OPTIONS
POST
PUT
PATCH
DELETE
每一種方法對應(yīng)的都是一棵獨立的壓縮字典樹,這些樹彼此之間不共享數(shù)據(jù)。具體到我們上面用到的路由,PUT
和 GET
是兩棵樹而非一棵。
簡單來講,某個方法第一次插入的路由就會導致對應(yīng)字典樹的根節(jié)點被創(chuàng)建,我們按順序,先是一個 PUT
:
r := httprouter.New()
r.PUT("/user/installations/:installation_id/repositories/:reposit", Hello)
這樣 PUT
對應(yīng)的根節(jié)點就會被創(chuàng)建出來。把這棵 PUT
的樹畫出來:
圖 5-3 插入路由之后的壓縮字典樹
radix 的節(jié)點類型為 *httprouter.node
,為了說明方便,我們留下了目前關(guān)心的幾個字段:
path: 當前節(jié)點對應(yīng)的路徑中的字符串
wildChild: 子節(jié)點是否為參數(shù)節(jié)點,即 wildcard node,或者說 :id 這種類型的節(jié)點
nType: 當前節(jié)點類型,有四個枚舉值: 分別為 static/root/param/catchAll。
static // 非根節(jié)點的普通字符串節(jié)點
root // 根節(jié)點
param // 參數(shù)節(jié)點,例如 :id
catchAll // 通配符節(jié)點,例如 *anyway
indices:子節(jié)點索引,當子節(jié)點為非參數(shù)類型,即本節(jié)點的 wildChild 為 false 時,會將每個子節(jié)點的首字母放在該索引數(shù)組。說是數(shù)組,實際上是個 string。
當然,PUT
路由只有唯一的一條路徑。接下來,我們以后續(xù)的多條 GET 路徑為例,講解子節(jié)點的插入過程。
當插入 GET /marketplace_listing/plans
時,類似前面 PUT 的過程,GET 樹的結(jié)構(gòu)如 圖 5-4:
圖 5-4 插入第一個節(jié)點的壓縮字典樹
因為第一個路由沒有參數(shù),path 都被存儲到根節(jié)點上了。所以只有一個節(jié)點。
然后插入 GET /marketplace_listing/plans/:id/accounts
,新的路徑與之前的路徑有共同的前綴,且可以直接在之前葉子節(jié)點后進行插入,那么結(jié)果也很簡單,插入后的樹結(jié)構(gòu)見 圖 5-5:
圖 5-5 插入第二個節(jié)點的壓縮字典樹
由于 :id
這個節(jié)點只有一個字符串的普通子節(jié)點,所以 indices 還依然不需要處理。
上面這種情況比較簡單,新的路由可以直接作為原路由的子節(jié)點進行插入。實際情況不會這么美好。
接下來我們插入 GET /search
,這時會導致樹的邊分裂,見 圖 5-6。
圖 5-6 插入第三個節(jié)點,導致邊分裂
原有路徑和新的路徑在初始的 /
位置發(fā)生分裂,這樣需要把原有的 root 節(jié)點內(nèi)容下移,再將新路由 search
同樣作為子節(jié)點掛在 root 節(jié)點之下。這時候因為子節(jié)點出現(xiàn)多個,root 節(jié)點的 indices 提供子節(jié)點索引,這時候該字段就需要派上用場了。"ms" 代表子節(jié)點的首字母分別為 m(marketplace)和 s(search)。
我們一口作氣,把 GET /status
和 GET /support
也插入到樹中。這時候會導致在 search
節(jié)點上再次發(fā)生分裂,最終結(jié)果見 圖 5-7:
圖 5-7 插入所有路由后的壓縮字典樹
在路由本身只有字符串的情況下,不會發(fā)生任何沖突。只有當路由中含有 wildcard(類似 :id)或者 catchAll 的情況下才可能沖突。這一點在前面已經(jīng)提到了。
子節(jié)點的沖突處理很簡單,分幾種情況:
GET /user/getAll
? 和 ?GET /user/:id/getAddr
?,或者 ?GET /user/*aaa
? 和 ?GET /user/:id
?。GET /user/:id/info
? 和 ?GET /user/:name/info
?。GET /src/abc
? 和 ?GET /src/*filename
?,或者 ?GET /src/:id
? 和 ?GET /src/*filename
?。只要發(fā)生沖突,都會在初始化的時候 panic。例如,在插入我們臆想的路由 ?GET /marketplace_listing/plans/ohyes
? 時,出現(xiàn)第 4 種沖突情況:它的父節(jié)點 ?marketplace_listing/plans/
? 的 wildChild 字段為 true。
![]() | ![]() |
更多建議: