一文讀懂主流 web 框架中路由的實現原理
一、什麼是路由
路由,就是 url 地址到業務處理代碼的映射。當用戶輸入一個 url 地址時,服務器該知道該用戶返回什麼內容。比如,當用戶點擊登錄時,服務器應該做登錄相關的事情,並給用戶返回登錄成功或失敗的頁面。當用戶點擊退出時,服務器應該做和退出相關的事情(比如清理用戶登錄的數據),並返回給用戶退出之後的頁面。
一個 url 到一個具體的處理函數之間的映射叫做一條路由。
多條路由組成路由表。路由表主要用於路由查找,根據不同的路由表的組織形式,可以有不同的查找方法。最簡單的路由表就是使用 map。直接以 key-value 的形式進行匹配即可。
給定一個 url,找到對應的處理函數的過程叫做路由查找。路由器就是用來管理路由表以及進行路由查找的。
所以,在 web 系統中一個路由系統由路由、路由表、路由匹配三部分功能組成。
二、基於映射表的路由實現
go 內建標準包 net/http 中路由的實現是基於映射表實現的。也是最簡單的路由實現。本節我們就來看來 http 請求的處理流程以及內建包默認的路由實現原理。
2.1 http 的處理流程
首先,我們來看下 http 包是如何處理請求的。通過以下代碼我們就能啓動一個 http 服務,並處理請求:
import (
"net/http"
)
func main() {
// 指定路由
http.Handle("/", &HomeHandler{})
// 啓動http服務
http.ListenAndServe(":8000", nil)
}
type HomeHandler struct {}
// 實現ServeHTTP
func (h *HomeHandler) ServeHTTP(response http.ResponseWriter, request *http.Request) {
response.Write([]byte("Hello World"))
}
當我們輸入 http://localhost:8000 / 的時候,就會走到 HomeHandler 的 ServeHTTP 方法,並返回 Hello World。
那這裏爲什麼要給 HomeHandler 定義 ServeHTTP 方法呢?或者說爲什麼會走到 ServeHTTP 方法中呢?
我們順着 http.ListenAndServe 方法的定義:
func ListenAndServe(addr string, handler Handler) error
發現第二個參數是個 Handler 類型,而 Handler 是一個定義了 ServeHTTP 方法的接口類型:
type Handler interface {
ServeHTTP(ResponseWriter, *Request)
}
似乎有了一點點關聯,HomeHandler 類型也實現了 ServeHTTP 方法。但我們在 main 函數中調用http.ListenAndServe(":8000", nil)
的時候第二個參數傳遞的是 nil,那 HomeHandler 裏的 ServeHTTP 方法又是如何被找到的呢?
我們接着再順着源碼一層一層的找下去可以發現,在 / src/net/http/server.go 的第 1930 行有這麼一段代碼:
serverHandler{c.server}.ServeHTTP(w, w.req)
有個 serverHandler 結構體,包裝了 c.server。這裏的 c 是建立的 http 連接,而 c.server 就是在 http.ListenAndServe(":8000", nil) 函數中創建的 server 對象:
func ListenAndServe(addr string, handler Handler) error {
server := &Server{Addr: addr, Handler: handler}
return server.ListenAndServe()
}
server 中的 Handler 就是 http.ListenAndServe(":8000", nil) 傳遞進來的 nil。
好,我們進入 serverHandler{c.server}.ServeHTTP(w, w.req)
函數中再次查看,就可以發現如下代碼:
func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
handler := sh.srv.Handler
if handler == nil {
handler = DefaultServeMux
}
...
handler.ServeHTTP(rw, req)
}
/src/net/http/server.go 的第 2859 行到 2862 行,就是獲取到 server 中的 Handler,如果是 nil,則使用默認的 DefaultServeMux,然後調用了 hander.ServeHTTP 方法。
繼續再看 DefaultServeMux 中的 ServeHTTP 方法,在 / src/net/http/server.go 中的第 2416 行,發現有一行 h,_ := mux.Handler(r) 和 h.ServeHTTP 方法。這就是通過請求的路徑查找到對應的 handler,然後調用該 handler 的 ServeHTTP 方法。
func (mux *ServeMux) ServeHTTP(w ResponseWriter, r *Request) {
if r.RequestURI == "*" {
if r.ProtoAtLeast(1, 1) {
w.Header().Set("Connection", "close")
}
w.WriteHeader(StatusBadRequest)
return
}
h, _ := mux.Handler(r)
h.ServeHTTP(w, r)
}
在一開始的實例中,就是我們的 HomeHandler 的 ServeHTTP 方法。也就是說 ServeHTTP 方法是 net/http 包中規定好了要調用的,所以每一個頁面處理函數都必須實現 ServeHTTP 方法。
同時也說明,net/http 包中的路由是在 DefaultServeMux 對象中實現的,該對象是一個 ServeMux 結構體類型,接下來我們看 ServeMux 路由的具體實現。
2.2 net/http 包中路由的實現
在 net/http 包中實現路由的機構提是 ServeMux,其結構定義如下。
type ServeMux struct {
mu sync.RWMutex
m map[string]muxEntry
es []muxEntry // slice of entries sorted from longest to shortest.
hosts bool // whether any patterns contain hostnames
}
結構體字段很簡單,我們重點看 m 變量,是一個 map 類型,即 key-value 結構,就是我們所說的路由表。key 就是路由的路徑,value 是一個 muxEntry 對象,muxEntry 結構如下:
type muxEntry struct {
h Handler
pattern string
}
pattern 是對應的路徑,h 就是對應的處理函數。當我們調用http.Handle("/", &HomeHandler{})�
進行路由註冊時候,實質上就是將路徑和 HomeHandler 對象構建成一個 muxEntry 對象,然後加入到 ServeMux 的 m 中。
接下來我們再看路由的查找,既然路由表是有 map 實現的,那麼路由的查找過程自然就是通過路徑從 map 中查找對應的 muxEntry,然後獲取對應的 handler 即可。該實現就是在 / src/net/http/server.go 中的第 2416 行的 mux.Handler(r) 進行的。
以上就是 net/http 包中自己路由的實現。非常簡單,同時也意味着功能有限。比如不能對路由進行分組、不能限定路由的請求方法(GET、POST 或其他)、不能對路由加中間件等等。 這也就給第三方包提供了再次實現的機會。
三、基於正則表達式的路由實現
3.1 gorilla/mux 包簡介
該包是基於正則表達式實現的路由。該路由支持分組、restful 風格路徑的定義、綁定路由請求的方法(GET、POST 等)、限定路徑使用 http 還是 https 協議等功能。我們看下其基本情況。
3.2 基本使用
由於該包支持的路由規則比較多,所以我們先從最簡單的例子開始看一下基本使用,然後再通過分析其實現原理看各種規則是如何支持的。
package main
import (
"fmt"
"net/http"
"github.com/gorilla/mux"
)
func main() {
r := mux.NewRouter()
r.HandleFunc("/", HomeHandler)
r.HandleFunc("/products", ProductsHandler)
//定義restful風格的路徑,例如/product/12345
r.HandleFunc("/product/{id:[0-9]+}", ProductHandler)
http.ListenAndServe(":8000", r)
}
func HomeHandler(response http.ResponseWriter, request *http.Request) {
response.Write([]byte("Hi, this is Home page"))
}
func ProductsHandler(response http.ResponseWriter, request *http.Request) {
response.Write([]byte("Hi, this is Product page"))
}
func ProductHandler(response http.ResponseWriter, request *http.Request) {
vars := mux.Vars(request)
// 獲取產品的ID值。
id := vars["id"]
response.Write([]byte("Hi, this is product:" + id))
}
3.3 實現原理分析
首先我們通過 mux.NewRouter() 方法返回了一個 Router 結構體對象。該結構體對象也實現了 ServeHTTP 方法,在該方法中實現了對路由的匹配和轉發。所以覆蓋作爲 http.ListenAndServe 的第二個參數,替代了默認的路由分發對象 DefaultServeMux。以下展示了 Router 的 ServeHTTP 方法對路由的匹配和分發部分的代碼,其他代碼省略。
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
...
var match RouteMatch
var handler http.Handler
// 路由匹配
if r.Match(req, &match) {
handler = match.Handler
req = requestWithVars(req, match.Vars)
req = requestWithRoute(req, match.Route)
}
...
// 路由分發
handler.ServeHTTP(w, req)
}
本質上是和默認的路由分發器 DefaultServeMux 的實現是一樣的。不同的是路由的管理以及匹配上。
接下來我們看下 Router 結構體。如下:
這裏我們只列出來核心的字段,省略了一些輔助字段。這裏有幾個主要的字段:
-
Router 中的 routes: Route 切片類型,角色是路由表,存儲所有的路由。
-
Route: 一個具體的路由,handler 字段存儲的是具體的處理函數,同時每個路由的路徑是在最後的 routeRegexp 結構體中的。
-
matchers 字段: 切片類型,存儲了該路由下的所有要匹配的規則。matchers 的類型是一個 matcher 接口,定義了 Match 方法。其中 routeRegexp 結構體實現了該方法,所以一個 routeRegexp 實例就是一個 matcher。
-
routeRegexp 結構體: 該結構體代表了路由中具體的路徑的匹配規則。將路由中的路徑轉換成對應的正則表達式,存儲與 regexp 字段中。
routeRegexp 結構體中的主要字段分別如下:
-
template: 保存的是路由的路徑模版。比如
r.HandleFunc("/product/{id:[0-9]+}", ProductHandler)
中,則是"/product/{id:[0-9]+}"
-
regexpType: 正則類型,目前支持 regexpTypePath、regexpTypeHost、regexpTypePrefix、regexpTypeQuery 四種類型。比如
r.HandleFunc("/product/{id:[0-9]+}", ProductHandler)
就是路徑匹配 regexpTypePath。而r.Host("www.example.com")
就是域名匹配 regexpTypeHost。稍後我們會一一介紹。 -
regexp: 是根據路由中的模版路徑構造出來的正則表達式。以
"/product/{id:[0-9]+}"
爲例,最終構造的正則表達式是^/product/(?P<v0>[0-9]+)$�
-
reverse:
-
varsN: 是路徑模式中花括號 {} 中的變量個數。以
"/product/{id:[0-9]+}"
爲例,varsN 則等於[]{"id"}
。 -
varsR: 是路徑模式中每個花括號 {} 對應的正則表達式。以 "/product/{id:[0-9]+}" 爲例,varsR 則等於[]{"^[0-9]+$"}。如果路由中是設置 r.HandleFunc("/product/{id}", ProductHandler),varsR 的元素則是
[]{"^[^/]+�"}
的正則表達式。
根據路由表及路由的結構,具體的路由匹配查找基本過程如下: 第一步,從 Router.routes 開始依次循環 第二步,從每個路由中的 matchers 中循環,看請求的路徑是否符合 matchers 中的每一項規則,如果都匹配,則說明找到了該路由,否則繼續步驟 1。
接下來,我們看看該路由是如何支持各種功能的。
3.4 路由支持的功能及對應的正則
3.4.1 匹配特定域名或子域名
r := mux.NewRouter()
// Only matches if domain is "www.example.com".
r.Host("www.example.com")
// Matches a dynamic subdomain.
r.Host("{subdomain:[a-z]+}.example.com")
我們先看 r.Host("www.example.com") 的路由。在 routeRegexp 結構體中,regexp 值會是正則表達式"^www\.example\.com$
,regexpType 字段是 regexpTypeHost。同時賦值給 routeRegexpGroup 中的 host 字段。
從路由表 Router.routes 中依次匹配本次請求的時候,發現 route.regexpType 字段是域名的正則,則從請求中獲取當前的 host,然後跟 routeRegexp.regexp 正則表達式進行匹配。如果匹配成功則繼續匹配後面的路由,否則直接匹配失敗。
再來看匹配子域名 r.Host("{subdomain:[a-z]+}.example.com") 的情況。在 routeRegexp 結構體中,regexp 值會是正則表達式"^(?P<v0>[a-z]+)\.example\.com$
,regexpType 字段是 regexpTypeHost。同時賦值給 routeRegexpGroup 中的 host 字段。匹配過程和上述過程一樣,不再重複介紹。
3.4.2 給路徑增加前綴
r.PathPrefix("/products/")
顧名思義,就是隻有路徑中是以 / products 爲前綴的才能匹配到該路由。該路由的設置最終編譯成的正則表達式是^/products
。這裏注意該表達式中結尾並沒有結尾符號 $
。其匹配過程和上述一致。
3.4.3 限制路由的請求方法(GET、POST 等)
r.Methods("GET", "POST")
對請求方法的限制 是不經過正則,而是將允許的方法(GET、POST)轉換成一個 methodMatcher�類型,該類型本質上是一個字符串切片,並且實現了 Match 方法,也就是 matcher 接口。然後將其加入到該路由的 matchers 中,在路由匹配時看當前的請求是否滿足該路由的這條規則。其定義如下:
type methodMatcher []string
func (m methodMatcher) Match(r *http.Request, match *RouteMatch) bool {
return matchInArray(m, r.Method)
}
3.4.4 支持路由分組
userRouter := r.PathPrefix("/user").Subrouter()
userRouter.HandleFunc("/info", HomeHandler)
通過. Subrouter() 函數就能實現一個子路由表,在該子路由表下注冊的所有路由都會遵循子路由上的公共設置,比如前綴。如上述例子 / info 的完整路徑就是 / user/info 指向 HomeHandler。
我們查看 Subrouter 函數的源碼,實際上是新建了一個 Router 結構體,而 Router 結構體實現了 Match 函數,即 matcher,所以也會將該 matcher 加入到 r.PathPrefix 這個路由的 matchers 中。相當於在路由中有建了一個專屬的路由表。以下是 Router 的 Match 函數實現,我們看到循環到該 matcher 時,循環子路由表的 routes,再對每個子路由依次進行匹配:
func (r *Router) Match(req *http.Request, match *RouteMatch) bool {
for _, route := range r.routes {
if route.Match(req, match) {
// Build middleware chain if no error was found
if match.MatchErr == nil {
for i := len(r.middlewares) - 1; i >= 0; i-- {
match.Handler = r.middlewares[i].Middleware(match.Handler)
}
}
return true
}
}
...//省略代碼
}
3.4.5 支持中間件
// 定義中間件
func loggingMiddleware(next http.Handler) http.Handler {
return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
// Do stuff here
log.Println(r.RequestURI)
// Call the next handler, which can be another middleware in the chain, or the final handler.
next.ServeHTTP(w, r)
})
}
r := mux.NewRouter()
r.HandleFunc("/", HomeHandler)
// 使用中間件
r.Use(loggingMiddleware)
func HomeHandler(response http.ResponseWriter, request *http.Request) {
response.Write([]byte("Hi, this is Home page"))
}
在該示例中,首先定義了一箇中間件 loggingMIddleware,然後使用 Use 函數將中間件加入到了 Router 中。
中間件的實現原理實際上是將原本要執行的 handler 包裝到中間件的 handler 中。先執行中間件的 handler 邏輯,然後再執行原本的 handler。以上述代碼爲例,會將 HomeHandler 傳遞給 loggingMiddleware 的 next 參數。執行的時候從第 4 行開始執行,最後纔是第 7 行,即 HomeHandler 的代碼邏輯。如下圖:
接下來我們看看中間件是如何實現一層層包裹的。
我們先看 r.Use 函數的定義:
func (r *Router) Use(mwf ...MiddlewareFunc) {
for _, fn := range mwf {
r.middlewares = append(r.middlewares, fn)
}
}
發現中間件的類型是 MiddlewareFunc,該類型的定義如下:
type MiddlewareFunc func(http.Handler) http.Handler
中間件本質上是一個函數類型,輸入和輸出都是一個 http.Handler,同時 MiddlewareFunc 中實現了一個 Middleware 的方法:
func (mw MiddlewareFunc) Middleware(handler http.Handler) http.Handler {
return mw(handler)
}
我們再看路由匹配時,執行中間件的邏輯:
func (r *Router) Match(req *http.Request, match *RouteMatch) bool {
for _, route := range r.routes {
if route.Match(req, match) {
// Build middleware chain if no error was found
if match.MatchErr == nil {
for i := len(r.middlewares) - 1; i >= 0; i-- {
match.Handler = r.middlewares[i].Middleware(match.Handler)
}
}
return true
}
}
...//省略代碼
}
在第 7 行,執行中間件的 Middleware 函數。以r.HandleFunc("/", HomeHandler)
使用 loggingMiddleware 中間件爲例,match.Handler 是 HomeHandler,loggingMiddleware.Middleware 即爲 loogingMIddleware(HomeHandler),該函數返回的是一個新的 handler:
http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
// Do stuff here
log.Println(r.RequestURI)
// Call the next handler, which can be another middleware in the chain, or the final handler.
next.ServeHTTP(w, r)
})
那麼,在具體執行的時候,就是先執行該 handler 的業務邏輯,即 log.Println(r.RequestURI),然後執行 next.ServerHTTP 邏輯,即 HomeHandler.ServeHTTP 的邏輯。
這就是中間件對 handler 的包裝及執行過程。其他更多功能可自行查看 gorilla/mux 包的源碼。
4 基於 tries 結構的路由實現
4.1 gin 框架中的路由
大名鼎鼎的 gin 框架採用的就是前綴樹結構實現的路由。我們先來看一下 gin 框架中路由是如何定義的。
package main
import (
"github.com/gin-gonic/gin"
)
func main() {
g := gin.New()
g.POST("/abc/info", InfoHandler)
g.POST("/abc/info/detail", InfoHandler)
g.POST("/abc/list", HomeHandler)
g.Run(":8000")
}
func HomeHandler(ctx *gin.Context) {
ctx.Writer.Write([]byte("Hi, this is Home page"))
}
func InfoHandler(ctx *gin.Context) {
ctx.Writer.Write([]byte("Hi, this is info"))
}
很簡單,首先通過 gin.New() 初始化一個 gin 對象 g,然後通過 g.POST 或 g.GET 等方法就可以註冊路由。很明顯,路由註冊過程也限制了請求的方法。 當然,還有一個方法是允許任何請求方法都能訪問該路徑的,就是 Any:
g.Any("/", HomeHandler)
Any 方法本質上是定義了一組方法名,然後依次調用對應的方法將該路由進行註冊,如下:
var anyMethods = []string{
http.MethodGet, http.MethodPost, http.MethodPut, http.MethodPatch,
http.MethodHead, http.MethodOptions, http.MethodDelete, http.MethodConnect,
http.MethodTrace,
}
// Any registers a route that matches all the HTTP methods.
// GET, POST, PUT, PATCH, HEAD, OPTIONS, DELETE, CONNECT, TRACE.
func (group *RouterGroup) Any(relativePath string, handlers ...HandlerFunc) IRoutes {
for _, method := range anyMethods {
group.handle(method, relativePath, handlers)
}
return group.returnObj()
}
接下來,我們分析下路由實現以及匹配的過程。
4.2 前綴樹路由的實現原理
相比較 map/hash 字典實現的優點:利用字符串公共前綴來減少查詢時間,減少無謂的字符串比較
4.2.1 路由中限制請求方法的實現
我們先看 gin 框架中的路由是如何對請求方法做限制的。 在 gin 框架中,路由樹的構建是基於方法的。每種方法一棵路由樹。如下:
type methodTree struct {
method string
root *node
}
type methodTrees []methodTree
例如,上述示例中的g.POST("/abc/info", InfoHandler)
路由,只會註冊到 POST 方法的路由樹中。若通過 GET 方法請求該路徑,則在搜索的時候,在 GET 方法的路由樹中就找不到該路由。這樣就起到了通過路由限制請求方法的作用。
而 g.Any 方法註冊的路由,相當於在所有的方法路由中都註冊了一遍,因此,使用任何方法都能找到對應的路由。
4.2.2 路由樹節點的數據結構
前綴樹中的路由都是基於這個 node 數據結構來進行構建的。其中包含了一個路由中的基本元素:路徑 fullPath、對應的處理函數 handlers。其中 handlers 包含了中間件處理函數,因此這裏使用一個 handlersChain 表示。
另外一個關鍵字段是 children,具有相同路徑前綴的子節點通過 children 節點來構成父、子關係。
接下來我們路由樹是如何基於 node 節點進行構建的。
4.2.3 路由樹的構建
首先,我們看第一個路由的註冊。
g.POST("/abc/info", InfoHandler)
因爲是第一個路由註冊,路由樹是空的。所以直接構建一個 node 節點,然後將該 node 節點作爲 POST 方法路由樹的根節點插入即可。如下圖:
好,我們接着看接着註冊第二個路由:
g.POST("/abc/info/detail", DetailHandler)
我們發現,這個路由的特點是和路由 "/abc/info" 有共同的前綴,所以會將該路由作爲第一個路由的子節點放到 children 中。如下圖:
這裏主要有三個變化:一個是根節點的 priority 由 1 變成了 2;一個是 children 中多了一個子節點路由;最後一個是 indices 字段的值變成了 "/",這個是第一個子節點的 path 字段的第一個字符,用於匹配時索引使用。在子節點中,要注意的是 path 的值,因爲前綴是 "/abc/info" 了,所以這裏 path 是 "/detail"。但 fullPath 依然是註冊時完整的路徑。
接下來,我們再註冊第三個路由:
g.POST("/abc/list", ListHandler)
這個路由的特點是和前兩個路由有共同的前綴 "/abc/",所以首先會將現在的根節點進行拆分,拆分成 "/abc/" 和 "info"。而 info 和原來的 "/abc/info/detail" 又有共同的前綴 info,所以原來的 "/abc/info/detail" 就變成了 info 的子節點。而 "/abc/list" 除去前綴 "/abc/" 後,剩餘 "list" 子節點,作爲 "/abc/" 的子節點。如下:
那麼,按節點組成的路由樹就如下所示:
這裏,我們首先看根節點的變化:
-
handlers 變爲 nil。因爲該節點不是一個具體的路徑,只是一個前綴,所以具體的 handler 下移到了子節點 info 節點。
-
path 變爲了前綴 "/abc/"。
-
indices 字段值變爲了 "il",其中 i 是第一個子節點中 path 字段的第一個字符,l 是第二個子節點中 path 字段的第一個字符。
-
priority 字段變成 3:代表從自身開始及子節點共有 4 個。
-
children 字段變成了兩個直接子節點。
-
fullPath 字段變爲了 "/abc/"。
其次,是從原根節點中拆分出一個 info 節點。最後是 detail 節點成爲 info 節點的子節點。
以上就是路由樹的構建過程。更細節的構造,有興趣的同學可以查看源碼進一步瞭解。
總結
本文總結了 3 中路由的實現。路由本質上就是將請求的路徑和對應的處理函數一一對應。通過路徑查找到處理函數的過程。不同框架基於不同的數據結構實現了路由表以及匹配過程。希望本文對大家理解 web 框架的路由有所幫助。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/cZ0fvVmUIrLKwlPFtetPKA