[TOC]

gin的路由算法分享

gin是什么呢畴博？

我們在github上看看官方簡介

Gin is a web framework written in Go (Golang). It features a martini-like API with performance that is up to 40 times faster thanks to httprouter. If you need performance and good productivity, you will love Gin.

Gin 是用 Go 開發(fā)的一個微框架虱歪，Web框架钝计，類似 Martinier 的 API番舆，接口簡潔，性能極高，也因為 httprouter的性能提高了 40 倍。

如果你需要良好的表現(xiàn)和工作效率郑原，你會喜歡Gin唉韭。

img

gin有啥特性呢夜涕？

gin大致都包含了哪些知識點饵隙？

image

gin的實戰(zhàn)演練我們之前也有分享過撮珠，我們再來回顧一下，gin大致都包含了哪些知識點

• :路由和*路由
• query查詢參數(shù)
• 接收數(shù)組和 Map
• Form 表單
• 單文件和多文件上傳
• 分組路由金矛，以及路由嵌套
• 路由中間件
• 各種數(shù)據(jù)格式的支持芯急，json、struct驶俊、xml志于、yaml、protobuf
• HTML模板渲染
• url重定向
• 異步協(xié)程等等

要是朋友們對gin還有點興趣的話废睦，可以點進(jìn)來看看伺绽，這里有具體的知識點對應(yīng)的案例gin實戰(zhàn)演練

路由是什么？

我們再來了解一下路由是什么

路由器是一種連接多個網(wǎng)絡(luò)或網(wǎng)段的網(wǎng)絡(luò)設(shè)備嗜湃，它能將不同網(wǎng)絡(luò)或網(wǎng)段之間的數(shù)據(jù)信息進(jìn)行“翻譯”奈应，以使它們能夠相互“讀”懂對方的數(shù)據(jù)，從而構(gòu)成一個更大的網(wǎng)絡(luò)购披。

路由器有兩大典型功能

• 即數(shù)據(jù)通道功能

包括轉(zhuǎn)發(fā)決定杖挣、背板轉(zhuǎn)發(fā)以及輸出鏈路調(diào)度等，一般由特定的硬件來完成

• 控制功能

一般用軟件來實現(xiàn)刚陡，包括與相鄰路由器之間的信息交換惩妇、系統(tǒng)配置、系統(tǒng)管理等

gin里面的路由

路由是web框架的核心功能筐乳。

寫過路由的朋友最開始是不是這樣看待路由的：

• 根據(jù)路由里的 / 把路由切分成多個字符串?dāng)?shù)組
• 然后按照相同的前子數(shù)組把路由構(gòu)造成樹的結(jié)構(gòu)

當(dāng)需要尋址的時候歌殃，先把請求的 url 按照 / 切分，然后遍歷樹進(jìn)行尋址蝙云，這樣子有點像是深度優(yōu)先算法的遞歸遍歷氓皱，從根節(jié)點開始，不停的向根的地方進(jìn)行延伸，知道不能再深入為止波材，算是得到了一條路徑

舉個栗子

定義了兩個路由 /v1/hi股淡，/v1/hello

那么這就會構(gòu)造出擁有三個節(jié)點的路由樹，根節(jié)點是 v1廷区，兩個子節(jié)點分別是 hi hello唯灵。

image

上述是一種實現(xiàn)路由樹的方式，這種是比較直觀隙轻，容易理解的早敬。對 url 進(jìn)行切分、比較大脉，可是時間復(fù)雜度是 O(2n)搞监，那么我們有沒有更好的辦法優(yōu)化時間復(fù)雜度呢？大名鼎鼎的GIn框架有辦法镰矿，往后看

算法是什么琐驴？

再來提一提算法是啥。

算法是解決某個問題的計算方法秤标、步驟绝淡，不僅僅是有了計算機(jī)才有算法這個名詞/概念的，

例如我們小學(xué)學(xué)習(xí)的九九乘法表

中學(xué)學(xué)習(xí)的各種解決問題的計算方法苍姜，例如物理公式等等

現(xiàn)在各種吃播大秀廚藝牢酵，做法的流程和方法也是算法的一種

image

• 面臨的問題是bug ， 解決的方法不盡相同衙猪，步驟也大相徑庭
• 面臨豬蹄馍乙，烹飪方法各有特色
• 面臨我們生活中的難題，也許每個人都會碰到同樣的問題垫释，可是每個人解決問題的方式方法差異也非常大丝格，有的人處理事情非常漂亮，有的人拖拖拉拉棵譬，總留尾巴

大學(xué)里面學(xué)過算法這本書显蝌，算法是計算機(jī)的靈魂，面臨問題订咸，好的算法能夠輕易應(yīng)對且健壯性好

面臨人生難題曼尊，好的解決方式，也同樣能夠讓我們走的更遠(yuǎn)脏嚷，更確切有點來說骆撇，應(yīng)該是好的思維模型。

算法有如下五大特征

每個事物都會有自己的特點然眼，否則如何才能讓人記憶深刻呢

• 有限性 艾船， 算法得有明確限步之后會結(jié)束
• 確切性葵腹，每一個步驟都是明確的高每，涉及的參數(shù)也是確切的
• 輸入屿岂，算法有零個或者多個輸入
• 輸出，算法有零個或者多個輸出
• 可行性鲸匿，算法的每一個步驟都是可以分解出來執(zhí)行的爷怀，且都可以在有限時間內(nèi)完成

gin的路由算法

那我們開始進(jìn)入進(jìn)入正題，gin的路由算法带欢，千呼萬喚始出來

gin的是路由算法類似于一棵前綴樹

只需遍歷一遍字符串即可运授，時間復(fù)雜度為O(n)。比上面提到的方式乔煞，在時間復(fù)雜度上來說真是大大滴優(yōu)化呀

不過吁朦，僅僅是對于一次 http 請求來說，是看不出啥效果的

誒渡贾，敲黑板了逗宜，什么叫做前綴樹呢？

Trie樹空骚，又叫字典樹纺讲、前綴樹（Prefix Tree），是一種多叉樹結(jié)構(gòu)

畫個圖囤屹，大概就能明白前綴樹是個啥玩意了

image

這棵樹還和二叉樹不太一樣熬甚，它的鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定

一個節(jié)點的所有子孫都有相同的前綴肋坚，也就是這個節(jié)點對應(yīng)的字符串乡括，而根節(jié)點對應(yīng)空字符串。

例如上圖智厌，我們一個一個的來尋址一下粟判，會有這樣的字符串

• MAC
• TAG
• TAB
• HEX

前綴樹有如下幾個特點：

• 前綴樹除根節(jié)點不包含字符，其他節(jié)點都包含字符
• 每個節(jié)點的子節(jié)點包含的字符串不相同
• 從根節(jié)點到某一個節(jié)點峦剔，路徑上經(jīng)過的字符連接起來档礁，為該節(jié)點對應(yīng)的字符串
• 每個節(jié)點的子節(jié)點通常有一個標(biāo)志位，用來標(biāo)識單詞的結(jié)束

有沒有覺得這個和路由的樹一毛一樣吝沫？

gin的路由樹算法類似于一棵前綴樹. 不過并不是只有一顆樹, 而是每種方法(POST, GET 呻澜，PATCH...)都有自己的一顆樹

例如，路由的地址是

• /hi
• /hello
• /:name/:id

那么gin對應(yīng)的樹會是這個樣子的

image

GO中 路由對應(yīng)的節(jié)點數(shù)據(jù)結(jié)構(gòu)是這個樣子的

type node struct {
    path      string
    indices   string
    children  []*node
    handlers  HandlersChain
    priority  uint32
    nType     nodeType
    maxParams uint8
    wildChild bool
}

具體添加路由的方法惨险，實現(xiàn)方法是這樣的

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
    assert1(path[0] == '/', "path must begin with '/'")
    assert1(method != "", "HTTP method can not be empty")
    assert1(len(handlers) > 0, "there must be at least one handler")

    debugPrintRoute(method, path, handlers)
    // 此處可以好好看看
    root := engine.trees.get(method) 
    if root == nil {
        root = new(node)
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers)
}

仔細(xì)看羹幸，gin的實現(xiàn)不像一個真正的樹

因為他的children []*node所有的孩子都會放在這個數(shù)組里面，具體實現(xiàn)是辫愉，他會利用indices, priority變相的去實現(xiàn)一棵樹

我們來看看不同注冊路由的方式有啥不同栅受？每一種注冊方式，最終都會反應(yīng)到gin的路由樹上面

普通注冊路由

普通注冊路由的方式是 router.xxx，可以是如下方式

• GET
• POST
• PATCH
• PUT
• ...

router.POST("/hi", func(context *gin.Context) {
    context.String(http.StatusOK, "hi xiaomotong")
})

也可以以組Group的方式注冊屏镊，以分組的方式注冊路由依疼，便于版本的維護(hù)

v1 := router.Group("v1")
{
    v1.POST("hello", func(context *gin.Context) {
        context.String(http.StatusOK, "v1 hello world")
    })
}

在調(diào)用POST, GET, PATCH等路由HTTP相關(guān)函數(shù)時, 會調(diào)用handle函數(shù)

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
    absolutePath := group.calculateAbsolutePath(relativePath) // calculateAbsolutePath
    handlers = group.combineHandlers(handlers) //  combineHandlers
    group.engine.addRoute(httpMethod, absolutePath, handlers)
    return group.returnObj()
}

calculateAbsolutePath 和 combineHandlers 還會再次出現(xiàn)

調(diào)用組的話，看看是咋實現(xiàn)的

func (group *RouterGroup) Group(relativePath string, handlers ...HandlerFunc) *RouterGroup {
    return &RouterGroup{
        Handlers: group.combineHandlers(handlers),
        basePath: group.calculateAbsolutePath(relativePath),
        engine:   group.engine,
    }
}

同樣也會調(diào)用 calculateAbsolutePath 和 combineHandlers 這倆函數(shù)而芥，我們來看看 這倆函數(shù)是干啥的律罢，看到函數(shù)名字，也許大概也能猜出個所以然了吧棍丐，來看看源碼

img

func (group *RouterGroup) combineHandlers(handlers HandlersChain) HandlersChain {
    finalSize := len(group.Handlers) + len(handlers)
    if finalSize >= int(abortIndex) {
        panic("too many handlers")
    }
    mergedHandlers := make(HandlersChain, finalSize)
    copy(mergedHandlers, group.Handlers)
    copy(mergedHandlers[len(group.Handlers):], handlers)
    return mergedHandlers
}

func (group *RouterGroup) calculateAbsolutePath(relativePath string) string {
    return joinPaths(group.basePath, relativePath)
}

func joinPaths(absolutePath, relativePath string) string {
    if relativePath == "" {
        return absolutePath
    }

    finalPath := path.Join(absolutePath, relativePath)
    appendSlash := lastChar(relativePath) == '/' && lastChar(finalPath) != '/'
    if appendSlash {
        return finalPath + "/"
    }
    return finalPath
}

joinPaths函數(shù)在這里相當(dāng)重要误辑，主要是做拼接的作用

從上面來看，可以看出如下2點：

• 調(diào)用中間件, 是將某個路由的handler處理函數(shù)和中間件的處理函數(shù)都放在了Handlers的數(shù)組中
• 調(diào)用Group, 是將路由的path上面拼上Group的值. 也就是/hi/:id, 會變成v1/hi/:id

使用中間件的方式注冊路由

我們也可以使用中間件的方式來注冊路由歌逢，例如在訪問我們的路由之前巾钉，我們需要加一個認(rèn)證的中間件放在這里，必須要認(rèn)證通過了之后秘案，才可以訪問路由

router.Use(Login())

func (group *RouterGroup) Use(middleware ...HandlerFunc) IRoutes {
    group.Handlers = append(group.Handlers, middleware...)
    return group.returnObj()
}

不管是普通的注冊睛琳，還是通過中間件的方式注冊，里面都有一個關(guān)鍵的handler

handler方法 調(diào)用 calculateAbsolutePath 和 combineHandlers 將路由拼接好之后踏烙，調(diào)用addRoute方法师骗，將路由預(yù)處理的結(jié)果注冊到gin Engine的trees上，來在看讀讀handler的實現(xiàn)

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
    absolutePath := group.calculateAbsolutePath(relativePath) // <---
    handlers = group.combineHandlers(handlers) // <---
    group.engine.addRoute(httpMethod, absolutePath, handlers)
    return group.returnObj()
}

那么讨惩，服務(wù)端寫好路由之后辟癌，我們通過具體的路由去做http請求的時候，服務(wù)端是如何通過路由找到具體的處理函數(shù)的呢荐捻？

image

我們仔細(xì)追蹤源碼黍少， 我們可以看到如下的實現(xiàn)

...
// 一棵前綴樹
t := engine.trees
for i, tl := 0, len(t); i < tl; i++ {
    if t[i].method != httpMethod {
        continue
    }
    root := t[i].root
    // Find route in tree
    // 這里通過 path 來找到相應(yīng)的  handlers 處理函數(shù)
    handlers, params, tsr := root.getValue(path, c.Params, unescape) 
    if handlers != nil {
        c.handlers = handlers
        c.Params = params
        // 在此處調(diào)用具體的 處理函數(shù)
        c.Next()
        c.writermem.WriteHeaderNow()
        return
    }
    if httpMethod != "CONNECT" && path != "/" {
        if tsr && engine.RedirectTrailingSlash {
            redirectTrailingSlash(c)
            return
        }
        if engine.RedirectFixedPath && redirectFixedPath(c, root, engine.RedirectFixedPath) {
            return
        }
    }
    break
}
...

func (c *Context) Next() {
    c.index++
    for c.index < int8(len(c.handlers)) {
        c.handlers[c.index](c)
        c.index++
    }
}

當(dāng)客戶端請求服務(wù)端的接口時， 服務(wù)端此處 handlers, params, tsr := root.getValue(path, c.Params, unescape) 处面， 通過 path 來找到相應(yīng)的 handlers 處理函數(shù)厂置，

將handlers ， params 復(fù)制給到服務(wù)中魂角，通過 c.Next()來執(zhí)行具體的處理函數(shù)昵济，此時就可以達(dá)到，客戶端請求響應(yīng)的路由地址野揪，服務(wù)端能過對響應(yīng)路由做出對應(yīng)的處理操作了

總結(jié)

• 簡單回顧了一下gin的特性
• 介紹了gin里面的路由
• 分享了gin的路由算法访忿，以及具體的源碼實現(xiàn)流程

img

好了，本次就到這里斯稳，下一次 分享最常用的限流算法以及如何在http中間件中加入流控海铆，

技術(shù)是開放的，我們的心態(tài)挣惰，更應(yīng)是開放的卧斟。擁抱變化殴边，向陽而生，努力向前行珍语。

我是小魔童哪吒锤岸，歡迎點贊關(guān)注收藏，下次見~