一文讀懂主流 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 協議等功能。我們看下其基本情況。

9NPcG3

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 結構體。如下:

這裏我們只列出來核心的字段,省略了一些輔助字段。這裏有幾個主要的字段:

routeRegexp 結構體中的主要字段分別如下:

根據路由表及路由的結構,具體的路由匹配查找基本過程如下: 第一步,從 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/" 的子節點。如下:

那麼,按節點組成的路由樹就如下所示:

這裏,我們首先看根節點的變化:

其次,是從原根節點中拆分出一個 info 節點。最後是 detail 節點成爲 info 節點的子節點。

以上就是路由樹的構建過程。更細節的構造,有興趣的同學可以查看源碼進一步瞭解。

總結

本文總結了 3 中路由的實現。路由本質上就是將請求的路徑和對應的處理函數一一對應。通過路徑查找到處理函數的過程。不同框架基於不同的數據結構實現了路由表以及匹配過程。希望本文對大家理解 web 框架的路由有所幫助。

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