在gin框架中，最關鍵的就是前綴樹，是很重要的。
gin框架本質上是在http包的基礎之上，對其的一個二次封裝。
這里借鑒一下小徐先生的圖，可能當前版本的gin可能內容有所改變，但大致思想還是這樣。
gin框架所做的就是提供一個gin.Engine作為對象Handler注入其中，從而實現路由注冊匹配，請求處理鏈路的優化。
一.核心數據結構
1.1 gin.Engine
type Engine struct {// 路由組RouterGroup// ...// context 對象池pool sync.Pool// 方法路由樹trees methodTrees// ...
}Engine 為 Gin 中構建的 HTTP Handler，其實現了 net/http 包下 Handler interface 的抽象方法： Handler.ServeHTTP，因此可以作為 Handler 注入到 net/http 的 Server 當中.
Engine包含的核心內容包括：
- 路由組 RouterGroup
- Context 對象池 pool：基于 sync.Pool 實現，作為復用 gin.Context 實例的緩沖池.
- 路由樹數組 trees：共有 9 棵路由樹，對應于 9 種 http 方法. 路由樹基于壓縮前綴樹實現，
1.2 http方法
這里要知道一點，很多人都只用常見的4種方法，實際上gin框架并不僅僅只能處理這4種。
還可以處理這些方法：
- PATCH（用于對資源進行部分更新）
- HEAD（類似于GET，但只返回響應頭）
- OPTIONS（用于獲取服務器支持的請求方法等信息）
const (MethodGet = "GET"MethodHead = "HEAD"MethodPost = "POST"MethodPut = "PUT"MethodPatch = "PATCH" // RFC 5789MethodDelete = "DELETE"MethodConnect = "CONNECT"MethodOptions = "OPTIONS"MethodTrace = "TRACE"
)1.3 RouterGroup
type RouterGroup struct {Handlers HandlersChainbasePath stringengine *Engineroot bool
}RouterGroup 是路由組的概念，其中的配置將被從屬于該路由組的所有路由復用：
- Handlers：路由組共同的 handler 處理函數鏈. 組下的節點將拼接 RouterGroup 的公用 handlers 和自己的 handlers，組成最終使用的 handlers 鏈
- basePath：路由組的基礎路徑. 組下的節點將拼接 RouterGroup 的 basePath 和自己的 path，組成最終使用的 absolutePath
- engine：指向路由組從屬的 Engine
- root：標識路由組是否位于 Engine 的根節點. 當用戶基于 RouterGroup.Group 方法創建子路由組后，該標識為 false
1.4 HandlersChain
type HandlersChain []HandlerFunctype HandlerFunc func(*Context)HandlersChain 是由多個路由處理函數 HandlerFunc 構成的處理函數鏈. 在使用的時候，會按照索引的先后順序依次調用 HandlerFunc.
二.注冊和啟動流程
2.1 注冊流程
下面以創建 gin.Engine 、注冊 middleware 和注冊 handler 作為主線，進行源碼走讀和原理解析：
func main() {// 創建一個 gin Engine，本質上是一個 http Handlermux := gin.Default()// 注冊中間件mux.Use(myMiddleWare)// 注冊一個 path 為 /ping 的處理函數mux.POST("/ping", func(c *gin.Context) {c.JSON(http.StatusOK, "pone")})// ...
}接下來說一下注冊的流程，在gin框架底層到底發生了什么？
- 方法調用：gin.Default -> gin.New
- 創建一個 gin.Engine 實例
- 創建 Engine 的首個 RouterGroup，對應的處理函數鏈 Handlers 為 nil，基礎路徑 basePath 為 "/"，root 標識為 true
- 構造了 9 棵方法路由樹，對應于 9 種 http 方法
- 創建了 gin.Context 的對象池
- 注冊middleware
通過 Engine.Use 方法可以實現中間件的注冊，會將注冊的 middlewares 添加到 RouterGroup.Handlers 中. 后續 RouterGroup 下新注冊的 handler 都會在前綴中拼上這部分 group 公共的 handlers.
func (engine *Engine) Use(middleware ...HandlerFunc) IRoutes {engine.RouterGroup.Use(middleware...)// ...return engine
}可以看到這個Use函數，可以同時注冊多個中間件，他們是有一定的執行順序的。
- 注冊handler
以 http post 為例，注冊 handler 方法調用順序為 RouterGroup.POST-> RouterGroup.handle，接下來會完成三個步驟：
- 拼接出待注冊方法的完整路徑 absolutePath
- 拼接出代注冊方法的完整處理函數鏈 handlers
- 以 absolutePath 和 handlers 組成 kv 對添加到路由樹中
一開始root的路徑就是/，如果后續你添加路由組，也就是Group的時候，就會根據拼接，然后對應到相應的路由樹去。
2.2 啟動流程
這里是gin框架的運行http為主線，看下它的運行流程
func main() {// 創建一個 gin Engine，本質上是一個 http Handlermux := gin.Default()// 一鍵啟動 http 服務if err := mux.Run(); err != nil{panic(err)}
}
func (engine *Engine) Run(addr ...string) (err error) {// ...err = http.ListenAndServe(address, engine.Handler())return
}Run函數下調用ListenAndServe，傳入的是gin框架實現的處理器，從而實現連接
順便多提一嘴，ListenerAndServe 方法本身會基于主動輪詢 + IO 多路復用的方式運行，因此程序在正常運行時，會始終阻塞于 Engine.Run 方法，不會返回.
func (srv *Server) Serve(l net.Listener) error {// ...ctx := context.WithValue(baseCtx, ServerContextKey, srv)for {rw, err := l.Accept()// ...connCtx := ctx// ...c := srv.newConn(rw)// ...go c.serve(connCtx)}
}通過這個阻塞操作，每當有http請求來時，就會對他處理，然后開啟一個協程來處理這個請求。
在服務端接收到 http 請求時，會通過 Handler.ServeHTTP 方法進行處理. 而此處的 Handler 正是 gin.Engine，其處理請求的核心步驟如下：
- 對于每筆 http 請求，會為其分配一個 gin.Context，在 handlers 鏈路中持續向下傳遞
- 調用 Engine.handleHTTPRequest 方法，從路由樹中獲取 handlers 鏈，然后遍歷調用
- 處理完 http 請求后，會將 gin.Context 進行回收. 整個回收復用的流程基于對象池管理
func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {// 從對象池中獲取一個 contextc := engine.pool.Get().(*Context)// 重置/初始化 contextc.writermem.reset(w)c.Request = reqc.reset()// 處理 http 請求engine.handleHTTPRequest(c)// 把 context 放回對象池engine.pool.Put(c)
}
Engine.handleHTTPRequest 方法核心步驟分為三步：
- 根據 http method 取得對應的 methodTree
- 根據 path 從 methodTree 中找到對應的 handlers 鏈
- 將 handlers 鏈注入到 gin.Context 中，通過 Context.Next 方法按照順序遍歷調用 handler
三.路由實現原理
3.1 壓縮前綴樹（radix tree）
再說壓縮前綴樹之前，先來說說前綴樹：
前綴樹也稱Trie樹或字典樹，是一種基于字符串公共前綴構建樹形結構，來降低查詢時間和提高效率的目的。前綴樹一般用于統計和排序大量的字符串，其核心思想是空間換時間。
前綴樹有三個重要特性:
- 根節點不包含字符，除根節點外每一個節點都只包含一個字符。
- 從根節點到某一節點路徑上所有字符連接起來，就是該節點對應的字符串。
- 每個節點任意子節點包含的字符都不相同。
如下是普通前綴樹的結構:
接下來，看看什么是壓縮前綴樹。
壓縮前綴樹又稱基數樹或 radix 樹，是對前綴樹的改良版本，優化點主要在于空間的節省
gin框架就采用的是壓縮前綴樹實現。
他和普通前綴樹的區別就是倘若某個子節點是其父節點的唯一孩子，則與父節點進行合并。
3.2 為什么使用前綴樹？
我們一般會將前綴樹與哈希表結構進行對比，實際上標準庫采用的就是哈希表實現。哈希表實現簡單粗暴，但是有一些缺點，不太適合作為通用的路由結構。如:
- 哈希表實現只支持簡單的路徑，不支持路徑參數和通配
- 路由的數量一般是有限的，使用map的優勢并不明顯
- 哈希表需要存儲完整的路徑，相比較而言前綴樹存儲公共前綴只需要一個節點，空間效率更高
3.3 補償機制
在 Gin 路由樹中還使用一種補償策略，在組裝路由樹時，會將注冊路由句柄數量更多的 child node 擺放在 children 數組更靠前的位置.
這是因為某個鏈路注冊的 handlers 句柄數量越多，一次匹配操作所需要花費的時間就越長，且被匹配命中的概率就越大，因此應該被優先處理.
3.4 核心數據結構
下面聊一下路由樹的數據結構，對應于 9 種 http method，共有 9 棵 methodTree. 每棵 methodTree 會通過 root 指向 radix tree 的根節點.
type methodTree struct {method stringroot *node
}具體的內容就不再介紹了，有興趣可以下去了解一下
四.gin.Context
接下來來看一下gin框架的上下文，已經它是如何承接http的吧
4.1 核心數據結構
gin.Context 的定位是對應于一次 http 請求，貫穿于整條 handlersChain 調用鏈路的上下文，其中包含了如下核心字段：
- Request/Writer：http 請求和響應的 reader、writer 入口
- handlers：本次 http 請求對應的處理函數鏈
- index：當前的處理進度，即處理鏈路處于函數鏈的索引位置
- engine：Engine 的指針
- mu：用于保護 map 的讀寫互斥鎖
- Keys：緩存 handlers 鏈上共享數據的 map
type Context struct {// ...// http 請求參數Request *http.Request// http 響應 writerWriter ResponseWriter// ...// 處理函數鏈handlers HandlersChain// 當前處于處理函數鏈的索引index int8engine *Engine// ...// 讀寫鎖，保證并發安全mu sync.RWMutex// key value 對存儲 mapKeys map[string]any// ..
}4.2 復用策略
gin.Context 作為處理 http 請求的通用數據結構，不可避免地會被頻繁創建和銷毀. 為了緩解 GC 壓力，gin 中采用對象池 sync.Pool 進行 Context 的緩存復用，處理流程如下：
- ? http 請求到達時，從 pool 中獲取 Context，倘若池子已空，通過 pool.New 方法構造新的 Context 補上空缺
- ? http 請求處理完成后，將 Context 放回 pool 中，用以后續復用
sync.Pool 并不是真正意義上的緩存，將其稱為回收站或許更加合適，放入其中的數據在邏輯意義上都是已經被刪除的，但在物理意義上數據是仍然存在的，這些數據可以存活兩輪 GC 的時間，在此期間倘若有被獲取的需求，則可以被重新復用.
看一下gin.Context的回收和分配時機
gin.Context 分配與回收的時機是在 gin.Engine 處理 http 請求的前后，位于 Engine.ServeHTTP 方法當中：
- 從池中獲取 Context
- 重置 Context 的內容，使其成為一個空白的上下文
- 調用 Engine.handleHTTPRequest 方法處理 http 請求
- 請求處理完成后，將 Context 放回池中
func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {// 從對象池中獲取一個 contextc := engine.pool.Get().(*Context)// 重置/初始化 contextc.writermem.reset(w)c.Request = reqc.reset()// 處理 http 請求engine.handleHTTPRequest(c)// 把 context 放回對象池engine.pool.Put(c)
}4.3 使用時機
（1）handlesChain 入口
在 Engine.handleHTTPRequest 方法處理請求時，會通過 path 從 methodTree 中獲取到對應的 handlers 鏈，然后將 handlers 注入到 Context.handlers 中，然后啟動 Context.Next 方法開啟 handlers 鏈的遍歷調用流程.
func (engine *Engine) handleHTTPRequest(c *Context) {// ...t := engine.treesfor i, tl := 0, len(t); i < tl; i++ {if t[i].method != httpMethod {continue}root := t[i].root value := root.getValue(rPath, c.params, c.skippedNodes, unescape)// ...if value.handlers != nil {c.handlers = value.handlersc.fullPath = value.fullPathc.Next()c.writermem.WriteHeaderNow()return}// ...}// ...
}（2）handlesChain 遍歷調用
推進 handlers 鏈調用進度的方法正是 Context.Next. 可以看到其中以 Context.index 為索引，通過 for 循環依次調用 handlers 鏈中的 handler.
func (c *Context) Next() {c.index++for c.index < int8(len(c.handlers)) {c.handlers[c.index](c)c.index++}
}由于 Context 本身會暴露于調用鏈路中，因此用戶可以在某個 handler 中通過手動調用 Context.Next 的方式來打斷當前 handler 的執行流程，提前進入下一個 handler 的處理中.
由于此時本質上是一個方法壓棧調用的行為，因此在后置位 handlers 鏈全部處理完成后，最終會回到壓棧前的位置，執行當前 handler 剩余部分的代碼邏輯.
結合下面的代碼示例來說，用戶可以在某個 handler 中，于調用 Context.Next 方法的前后分別聲明前處理邏輯和后處理邏輯，這里的“前”和“后”相對的是后置位的所有 handler 而言.
func myHandleFunc(c *gin.Context){// 前處理preHandle() c.Next()// 后處理postHandle()
}此外，用戶可以在某個 handler 中通過調用 Context.Abort 方法實現 handlers 鏈路的提前熔斷.
其實現原理是將 Context.index 設置為一個過載值 63，導致 Next 流程直接終止. 這是因為 handlers 鏈的長度必須小于 63，否則在注冊時就會直接 panic. 因此在 Context.Next 方法中，一旦 index 被設為 63，則必然大于整條 handlers 鏈的長度，for 循環便會提前終止.
const abortIndex int8 = 63func (c *Context) Abort() {c.index = abortIndex
}此外，用戶還可以通過 Context.IsAbort 方法檢測當前 handlerChain 是出于正常調用，還是已經被熔斷.
func (c *Context) IsAborted() bool {return c.index >= abortIndex
}注冊 handlers，倘若 handlers 鏈長度達到 63，則會 panic
func (group *RouterGroup) combineHandlers(handlers HandlersChain) HandlersChain {finalSize := len(group.Handlers) + len(handlers)// 斷言 handlers 鏈長度必須小于 63assert1(finalSize < int(abortIndex), "too many handlers")// ...
}4.4 共享數據存取
gin.Context 作為 handlers 鏈的上下文，還提供對外暴露的 Get 和 Set 接口向用戶提供了共享數據的存取服務，相關操作都在讀寫鎖的保護之下，能夠保證并發安全.
type Context struct {// ...// 讀寫鎖，保證并發安全mu sync.RWMutex// key value 對存儲 mapKeys map[string]any
}
func (c *Context) Get(key string) (value any, exists bool) {c.mu.RLock()defer c.mu.RUnlock()value, exists = c.Keys[key]return
}
func (c *Context) Set(key string, value any) {c.mu.Lock()defer c.mu.Unlock()if c.Keys == nil {c.Keys = make(map[string]any)}c.Keys[key] = value
}
)
)