前言

最近重新接觸Go語言以及對(duì)應(yīng)框架，想借此機(jī)會(huì)深入下對(duì)應(yīng)部分。
并分享一下最近學(xué)的過程很喜歡的一句話：

The limits of my language mean the limits of my world. by Ludwig Wittgenstein
我的語言之局限，即我的世界之局限。

一、是否一定要用框架來使用路由？

• 首先來介紹一下什么是路由。

路由是指確定請(qǐng)求應(yīng)該由哪個(gè)處理程序處理的過程。在 Web 開發(fā)中，路由用于將請(qǐng)求映射到相應(yīng)的處理程序或控制器。路由的種類通常包括以下幾種：

• 靜態(tài)路由： 靜態(tài)路由是指將特定的 URL 路徑映射到特定的處理程序或控制器的路由。這種路由是最基本的路由類型，通常用于處理固定的 URL 請(qǐng)求。例如一個(gè)簡單的GET請(qǐng)求: /test/router
• 動(dòng)態(tài)路由： 動(dòng)態(tài)路由是指根據(jù) URL 中的參數(shù)或模式進(jìn)行匹配的路由。例如，可以使用動(dòng)態(tài)路由來處理包含變量或參數(shù)的 URL 請(qǐng)求，以便根據(jù)請(qǐng)求的內(nèi)容返回相應(yīng)的結(jié)果。例如一個(gè)簡單的GET請(qǐng)求: /test/:id

因?yàn)?Go 的 net/http 包提供了基礎(chǔ)的路由函數(shù)組合與豐富的功能函數(shù)。所以在社區(qū)里流行一種用 Go 編寫 API 不需要框架的觀點(diǎn)，在我們看來，如果你的項(xiàng)目的路由在個(gè)位數(shù)、URI 固定且不通過 URI 來傳遞參數(shù)，那么確實(shí)使用官方庫也就足夠。

Go 的 Web 框架大致可以分為這么兩類：

• Router 框架
• MVC 類框架

• 在框架的選擇上，大多數(shù)情況下都是依照個(gè)人的喜好和公司的技術(shù)棧。例如公司有很多技術(shù)人員是 PHP 出身轉(zhuǎn)go，那么他們一般會(huì)喜歡用 beego 這樣的框架（典型的mvc架構(gòu)），對(duì)于有些公司可能更喜歡輕量的框架那么則會(huì)使用gin，當(dāng)然像字節(jié)這種內(nèi)部則會(huì)去選擇性能更高的kiteX作為web框架。
• 但如果公司有很多 C 程序員，那么他們的想法可能是越簡單越好。比如很多大廠的 C 程序員甚至可能都會(huì)去用 C 語言去寫很小的 CGI 程序，他們可能本身并沒有什么意愿去學(xué)習(xí) MVC 或者更復(fù)雜的 Web 框架，他們需要的只是一個(gè)非常簡單的路由（甚至連路由都不需要，只需要一個(gè)基礎(chǔ)的 HTTP 協(xié)議處理庫來幫他省掉沒什么意思的體力勞動(dòng)）。
• 而對(duì)于一個(gè)簡單的web服務(wù)利用官方庫來編寫也只需要短短的幾行代碼足矣：

package main
import (...)

func echo(wr http.ResponseWriter, r *http.Request) {
    msg, err := ioutil.ReadAll(r.Body)
    if err != nil {
        wr.Write([]byte("echo error"))
        return
    }

    writeLen, err := wr.Write(msg)
    if err != nil || writeLen != len(msg) {
        log.Println(err, "write len:", writeLen)
    }
}

func main() {
    http.HandleFunc("/", echo)
    err := http.ListenAndServe(":8080", nil)
    if err != nil {
        log.Fatal(err)
    }
}

這個(gè)例子是為了說明在 Go 中寫一個(gè) HTTP 協(xié)議的小程序有多么簡單。如果你面臨的情況比較復(fù)雜，例如幾十個(gè)接口的企業(yè)級(jí)應(yīng)用，直接用 net/http 庫就顯得不太合適了。
例如來看早期開源社區(qū)中一個(gè) Kafka 監(jiān)控項(xiàng)目Burrow中的做法：

func NewHttpServer(app *ApplicationContext) (*HttpServer, error) {
    ...
    server.mux.HandleFunc("/", handleDefault)

    server.mux.HandleFunc("/burrow/admin", handleAdmin)

    server.mux.Handle("/v2/kafka", appHandler{server.app, handleClusterList})
    server.mux.Handle("/v2/kafka/", appHandler{server.app, handleKafka})
    server.mux.Handle("/v2/zookeeper", appHandler{server.app, handleClusterList})
    ...
}

看上去很簡短，但是我們?cè)偕钊脒M(jìn)去：

func handleKafka(app *ApplicationContext, w http.ResponseWriter, r *http.Request) (int, string) {
    pathParts := strings.Split(r.URL.Path[1:], "/")
    if _, ok := app.Config.Kafka[pathParts[2]]; !ok {
        return makeErrorResponse(http.StatusNotFound, "cluster not found", w, r)
    }
    if pathParts[2] == "" {
        // Allow a trailing / on requests
        return handleClusterList(app, w, r)
    }
    if (len(pathParts) == 3) || (pathParts[3] == "") {
        return handleClusterDetail(app, w, r, pathParts[2])
    }

    switch pathParts[3] {
    case "consumer":
        switch {
        case r.Method == "DELETE":
            switch {
            case (len(pathParts) == 5) || (pathParts[5] == ""):
                return handleConsumerDrop(app, w, r, pathParts[2], pathParts[4])
            default:
                return makeErrorResponse(http.StatusMethodNotAllowed, "request method not supported", w, r)
            }
        case r.Method == "GET":
            switch {
            case (len(pathParts) == 4) || (pathParts[4] == ""):
                return handleConsumerList(app, w, r, pathParts[2])
            case (len(pathParts) == 5) || (pathParts[5] == ""):
                // Consumer detail - list of consumer streams/hosts? Can be config info later
                return makeErrorResponse(http.StatusNotFound, "unknown API call", w, r)
            case pathParts[5] == "topic":
                switch {
                case (len(pathParts) == 6) || (pathParts[6] == ""):
                    return handleConsumerTopicList(app, w, r, pathParts[2], pathParts[4])
                case (len(pathParts) == 7) || (pathParts[7] == ""):
                    return handleConsumerTopicDetail(app, w, r, pathParts[2], pathParts[4], pathParts[6])
                }
            case pathParts[5] == "status":
                return handleConsumerStatus(app, w, r, pathParts[2], pathParts[4], false)
            case pathParts[5] == "lag":
                return handleConsumerStatus(app, w, r, pathParts[2], pathParts[4], true)
            }
        default:
            return makeErrorResponse(http.StatusMethodNotAllowed, "request method not supported", w, r)
        }
    case "topic":
        switch {
        case r.Method != "GET":
            return makeErrorResponse(http.StatusMethodNotAllowed, "request method not supported", w, r)
        case (len(pathParts) == 4) || (pathParts[4] == ""):
            return handleBrokerTopicList(app, w, r, pathParts[2])
        case (len(pathParts) == 5) || (pathParts[5] == ""):
            return handleBrokerTopicDetail(app, w, r, pathParts[2], pathParts[4])
        }
    case "offsets":
        // Reserving this endpoint to implement later
        return makeErrorResponse(http.StatusNotFound, "unknown API call", w, r)
    }

    // If we fell through, return a 404
    return makeErrorResponse(http.StatusNotFound, "unknown API call", w, r)
}

這會(huì)發(fā)現(xiàn)這其中的這個(gè)handler擴(kuò)展的比較復(fù)雜，這個(gè)原因是因?yàn)槟J(rèn)的 net/http 包中的 mux 不支持帶參數(shù)的路由，所以 Burrow 這個(gè)項(xiàng)目使用了非常蹩腳的字符串 Split 和亂七八糟的 switch case 來達(dá)到自己的目的，但卻讓本來應(yīng)該很集中的路由管理邏輯變得復(fù)雜，散落在系統(tǒng)的各處，難以維護(hù)和管理。但如今Burrow項(xiàng)目的路由已經(jīng)重構(gòu)為使用httpRouter。感興趣的小伙伴可以自己再去看看相關(guān)源碼：Burrow

type Coordinator struct {
	// App is a pointer to the application context. This stores the channel to the storage subsystem
	App *protocol.ApplicationContext

	// Log is a logger that has been configured for this module to use. Normally, this means it has been set up with
	// fields that are appropriate to identify this coordinator
	Log *zap.Logger

	router  *httprouter.Router
	servers map[string]*http.Server
	theCert map[string]string
	theKey  map[string]string
}

包括如今的web框架的路由部分也是由httprouter改造而成的，后續(xù)也會(huì)繼續(xù)深入講下這部分。

二、httprouter

在常見的 Web 框架中，router 是必備的組件。Go 語言圈子里 router 也時(shí)常被稱為 http 的 multiplexer。如果開發(fā) Web 系統(tǒng)對(duì)路徑中帶參數(shù)沒什么興趣的話，用 http 標(biāo)準(zhǔn)庫中的 mux 就可以。而對(duì)于最近新起的Restful的api設(shè)計(jì)風(fēng)格則基本重度依賴路徑參數(shù)：

GET /repos/:owner/:repo/comments/:id/reactions

POST /projects/:project_id/columns

PUT /user/starred/:owner/:repo

DELETE /user/starred/:owner/:repo

如果我們的系統(tǒng)也想要這樣的 URI 設(shè)計(jì)，使用之前標(biāo)準(zhǔn)庫的 mux 顯然就力不從心了。而這時(shí)候一般就會(huì)使用之前提到的httprouter。

2.1 httprouter介紹

地址：
https://github.com/julienschmidt/httprouter
https://godoc.org/github.com/julienschmidt/httprouter

因?yàn)?httprouter 中使用的是顯式匹配，所以在設(shè)計(jì)路由的時(shí)候需要規(guī)避一些會(huì)導(dǎo)致路由沖突的情況，例如：

#沖突的情況:
GET /user/info/:name
GET /user/:id

#不沖突的情況:
GET /user/info/:name
POST /user/:id

簡單來講的話，如果兩個(gè)路由擁有一致的 http 方法 (指 GET、POST、PUT、DELETE) 和請(qǐng)求路徑前綴，且在某個(gè)位置出現(xiàn)了 A 路由是 帶動(dòng)態(tài)的參數(shù)（/:id)，B 路由則是普通字符串，那么就會(huì)發(fā)生路由沖突。路由沖突會(huì)在初始化階段直接 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

除支持路徑中的 動(dòng)態(tài)參數(shù)之外，httprouter 還可以支持 * 號(hào)來進(jìn)行通配，不過 * 號(hào)開頭的參數(shù)只能放在路由的結(jié)尾，例如下面這樣：

Pattern: /src/*filepath
 /src/                     filepath = ""
 /src/somefile.go          filepath = "somefile.go"
 /src/subdir/somefile.go   filepath = "subdir/somefile.go"

而這種場景主要是為了： httprouter 來做簡單的 HTTP 靜態(tài)文件服務(wù)器。

除了正常情況下的路由支持，httprouter 也支持對(duì)一些特殊情況下的回調(diào)函數(shù)進(jìn)行定制，例如 404 的時(shí)候：

r := httprouter.New()
r.NotFound = http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("oh no, not found"))
})

或者內(nèi)部 panic 的時(shí)候：

r := httprouter.New()
在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()))
}

2.2 httprouter原理

httprouter的使用在一開始時(shí)會(huì)使用New進(jìn)行注冊(cè)。對(duì)應(yīng)函數(shù)為：

func New() *Router {
	return &Router{
		RedirectTrailingSlash:  true,
		RedirectFixedPath:      true,
		HandleMethodNotAllowed: true,
		HandleOPTIONS:          true,
	}
}

這四個(gè)參數(shù)的分別的作用為：

• RedirectTrailingSlash： 指定是否重定向帶有尾部斜杠的 URL。如果設(shè)置為 true，則當(dāng)用戶訪問沒有斜杠結(jié)尾的 URL 時(shí)，httprouter 會(huì)將其重定向到帶有斜杠結(jié)尾的 URL。例如，將 “/path” 重定向到 “/path/”。
• RedirectFixedPath： 指定是否重定向固定路徑。如果設(shè)置為 true，則當(dāng)用戶訪問具有固定路徑的 URL 時(shí)，httprouter 會(huì)將其重定向到正確的固定路徑。這對(duì)于確保 URL 的一致性和規(guī)范性非常有用。
• HandleMethodNotAllowed： 指定是否處理不允許的 HTTP 方法。如果設(shè)置為 true，則當(dāng)用戶使用不允許的 HTTP 方法訪問 URL 時(shí)，httprouter 會(huì)返回 “405 Method Not Allowed” 錯(cuò)誤。
• HandleOPTIONS： 指定是否處理 OPTIONS 方法。如果設(shè)置為 true，則當(dāng)用戶使用 OPTIONS 方法訪問 URL 時(shí)，httprouter 會(huì)返回允許的 HTTP 方法列表。

更詳細(xì)的可以參考源碼注釋。
除此之外Router中還有一個(gè)很重要的字段：

type Router struct {
    // ...
    trees map[string]*node
    // ...
}

而這個(gè)字段則涉及到了底層的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，閱讀httprouter的源碼注釋可以簡單知道：

Package httprouter is a trie based high performance HTTP request router.

• 因此httprouter的底層是用壓縮字典樹實(shí)現(xiàn)的，屬于字典樹的一個(gè)變種，在繼續(xù)介紹這塊之前簡單做一個(gè)知識(shí)的補(bǔ)充：

• 字典樹即前綴樹（Trie樹），又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。
  它的優(yōu)點(diǎn)是： 利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較。
  以下是一顆字典樹的生成，分別插入app、apple、abcd、user、use、job。

• 而壓縮字典樹（Radix)也很好理解，因?yàn)樽值錁涞墓?jié)點(diǎn)粒度是以一個(gè)字母，而像路由這種有規(guī)律的字符串完全可以把節(jié)點(diǎn)粒度加粗，減少了不必要的節(jié)點(diǎn)層級(jí)減少存儲(chǔ)空間壓縮字符，并且由于深度的降低，搜索的速度也會(huì)相對(duì)應(yīng)的加快。例如做成如下這種形式：：
  
  因此上述的Map其實(shí)存放的key 即為 HTTP 1.1 的 RFC 中定義的各種方法，而node則為各個(gè)方法下的root節(jié)點(diǎn)。

  GET、HEAD、OPTIONS、POST、PUT、PATCH、DELETE
  

因此每一種方法對(duì)應(yīng)的都是一棵獨(dú)立的壓縮字典樹，這些樹彼此之間不共享數(shù)據(jù)。

• 對(duì)于node結(jié)構(gòu)體：

type node struct {
	path      string 
	indices   string
	wildChild bool     
	nType     nodeType
	priority  uint32
	children  []*node
	handle    Handle
}

參數(shù)分別代表的意思：

• path： 表示當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的路徑中的字符串。例如，如果節(jié)點(diǎn)對(duì)應(yīng)的路徑是 “/user/:id”，那么 path 字段的值就是 “:id”。

• indices： 一個(gè)字符串，用于快速查找子節(jié)點(diǎn)。它包含了當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)的第一個(gè)字符。為了加快路由匹配的速度。

• wildChild： 一個(gè)布爾值，表示子節(jié)點(diǎn)是否為參數(shù)節(jié)點(diǎn)，即 wildcard node，或者說像 “:id” 這種類型的節(jié)點(diǎn)。如果子節(jié)點(diǎn)是參數(shù)節(jié)點(diǎn)，則 wildChild 為 true，否則為 false。

• nType： 表示節(jié)點(diǎn)的類型，是一個(gè)枚舉類型。它可以表示靜態(tài)節(jié)點(diǎn)、參數(shù)節(jié)點(diǎn)或通配符節(jié)點(diǎn)等不同類型的節(jié)點(diǎn)。

• priority： 一個(gè)無符號(hào)整數(shù)，用于確定節(jié)點(diǎn)的優(yōu)先級(jí)。這有助于在路由匹配時(shí)確定最佳匹配項(xiàng)。

• children： 一個(gè)指向子節(jié)點(diǎn)的指針數(shù)組。它包含了當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)。

• handle： 表示與當(dāng)前節(jié)點(diǎn)關(guān)聯(lián)的處理函數(shù)（handler）。當(dāng)路由匹配到當(dāng)前節(jié)點(diǎn)時(shí)，將調(diào)用與之關(guān)聯(lián)的處理函數(shù)來處理請(qǐng)求。

• 對(duì)于nodeType:

const (
	static   nodeType = iota // 非根節(jié)點(diǎn)的普通字符串節(jié)點(diǎn)
	root                     // 根節(jié)點(diǎn)
	param                    // 參數(shù)節(jié)點(diǎn) 如：id
	catchAll                 // 通配符節(jié)點(diǎn) 如：*anyway
)

而對(duì)于添加一個(gè)路由的過程基本在源碼tree.go的addRoute的func中。大概得過程補(bǔ)充在注釋中：

// 增加路由并且配置節(jié)點(diǎn)handle，因?yàn)橹虚g的變量沒有加鎖，所以不保證并發(fā)安全，如children之間的優(yōu)先級(jí)
func (n *node) addRoute(path string, handle Handle) {
	fullPath := path
	n.priority++

	// 空樹的情況下插入一個(gè)root節(jié)點(diǎn)
	if n.path == "" && n.indices == "" {
		n.insertChild(path, fullPath, handle)
		n.nType = root
		return
	}

walk:
	for {
		// 找到最長的公共前綴。
		// 并且公共前綴中不會(huì)包含 no ':' or '*'，因?yàn)楣睬熬Ykey不能包含這兩個(gè)字符，遇到了則直接continue
		i := longestCommonPrefix(path, n.path)

		// 如果最長公共前綴小于 path 的長度，那么說明 path 無法與當(dāng)前節(jié)點(diǎn)路徑匹配，需要進(jìn)行邊的分裂
		// 例如：n 的路徑是 "/user/profile"，而當(dāng)前需要插入的路徑是 "/user/posts"
		if i < len(n.path) {
			child := node{
				path:      n.path[i:],
				wildChild: n.wildChild,
				nType:     static,
				indices:   n.indices,
				children:  n.children,
				handle:    n.handle,
				priority:  n.priority - 1,
			}

			n.children = []*node{&child}
			// []byte for proper unicode char conversion, see #65
			n.indices = string([]byte{n.path[i]})
			n.path = path[:i]
			n.handle = nil
			n.wildChild = false
		}

		// 處理剩下非公共前綴的部分
		if i < len(path) {
			path = path[i:]

			// 如果當(dāng)前節(jié)點(diǎn)有通配符（wildChild），則會(huì)檢查通配符是否匹配，如果匹配則繼續(xù)向下匹配，否則會(huì)出現(xiàn)通配符沖突的情況，并拋出異常。
			if n.wildChild {
				n = n.children[0]
				n.priority++

				// Check if the wildcard matches
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
					// Adding a child to a catchAll is not possible
					n.nType != catchAll &&
					// Check for longer wildcard, e.g. :name and :names
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
					continue walk
				} else {
					// Wildcard conflict
					pathSeg := path
					if n.nType != catchAll {
						pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
					}
					prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
					panic("'" + pathSeg +
						"' in new path '" + fullPath +
						"' conflicts with existing wildcard '" + n.path +
						"' in existing prefix '" + prefix +
						"'")
				}
			}

			idxc := path[0]

			// 如果當(dāng)前節(jié)點(diǎn)是參數(shù)類型（param）并且路徑中的下一個(gè)字符是 '/'，并且當(dāng)前節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則會(huì)繼續(xù)向下匹配。
			if n.nType == param && idxc == '/' && len(n.children) == 1 {
				n = n.children[0]
				n.priority++
				continue walk
			}

			// 檢查是否存在與路徑中的下一個(gè)字符相匹配的子節(jié)點(diǎn)，如果有則繼續(xù)向下匹配，否則會(huì)插入新的子節(jié)點(diǎn)來處理剩余的路徑部分。
			for i, c := range []byte(n.indices) {
				if c == idxc {
					i = n.incrementChildPrio(i)
					n = n.children[i]
					continue walk
				}
			}

			if idxc != ':' && idxc != '*' {
				// []byte for proper unicode char conversion, see #65
				n.indices += string([]byte{idxc})
				child := &node{}
				n.children = append(n.children, child)
				n.incrementChildPrio(len(n.indices) - 1)
				n = child
			}
			n.insertChild(path, fullPath, handle)
			return
		}

		// Otherwise add handle to current node
		if n.handle != nil {
			panic("a handle is already registered for path '" + fullPath + "'")
		}
		n.handle = handle
		return
	}
}

接下來以一個(gè)實(shí)際的案例,創(chuàng)建6個(gè)路由：

func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
	fmt.Fprint(w, "Welcome!\n")
}

func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
	fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}

func main() {
	router := httprouter.New()
	router.PUT("/hello/:name", Hello)
	router.GET("/test/router/", Hello)
	router.GET("/test/router/:name/branchA", Hello)
	router.GET("/test/router/:name/branchB", Hello)
	router.GET("status", Hello)
	router.GET("searcher", Hello)

	log.Fatal(http.ListenAndServe(":8080", router))
}

• 插入 “/hello/:name”
  

• 插入 “/test/router/”
  

• 插入 “/test/router/:name/branchA”
  

• 插入 “/test/router/:name/branchB”,此時(shí)由于/banch的孩子節(jié)點(diǎn)個(gè)數(shù)大于1，所以indices字段有作用，此時(shí)為兩個(gè)孩子節(jié)點(diǎn)path的首字母
  

• 插入 “/status”
  

• 插入 “searcher”
  

也因?yàn)榈讓訑?shù)據(jù)結(jié)構(gòu)的原因，所以為了不讓樹的深度過深，在初始化時(shí)會(huì)對(duì)參數(shù)的數(shù)量進(jìn)行限制，所以在路由中的參數(shù)數(shù)目不能超過 255，否則會(huì)導(dǎo)致 httprouter 無法識(shí)別后續(xù)的參數(shù)。

2.3 路由沖突情況

所以路由本身只有字符串的情況下，不會(huì)發(fā)生任何沖突。只有當(dāng)路由中含有 wildcard（類似 :id）或者 catchAll 的情況下才可能沖突。這在2.1中也提到過。

而子節(jié)點(diǎn)的沖突處理很簡單，分幾種情況：

• 在插入 wildcard 節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的 children 數(shù)組非空且 wildChild 被設(shè)置為 false。

例如：GET /user/getAll 和 GET /user/:id/getAddr，或者 GET /user/*aaa 和 GET /user/:id。

• 在插入 wildcard 節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的 children 數(shù)組非空且 wildChild 被設(shè)置為 true，但該父節(jié)點(diǎn)的 wildcard 子節(jié)點(diǎn)要插入的 wildcard 名字不一樣。

例如：GET /user/:id/info 和 GET /user/:name/info。

• 在插入 catchAll 節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的 children 非空。

例如：GET /src/abc 和 GET /src/*filename，或者 GET /src/:id 和 GET /src/*filename。

• 在插入 static 節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的 wildChild 字段被設(shè)置為 true。
• 在插入 static 節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的 children 非空，且子節(jié)點(diǎn) nType 為 catchAll。

三、gin中的路由

之前提到過現(xiàn)在Star數(shù)最高的web框架gin中的router中的很多核心實(shí)現(xiàn)很多基于httprouter中的，具體的可以去gin項(xiàng)目中的tree.go文件看對(duì)應(yīng)部分，這里主要講一下gin的路由除此之外額外實(shí)現(xiàn)了什么。

gin項(xiàng)目地址鏈接

在gin進(jìn)行初始化的時(shí)候，可以看到初始化的路由時(shí)它其實(shí)是初始化了一個(gè)路由組,而使用router對(duì)應(yīng)的GET\PUT等方法時(shí)則是復(fù)用了這個(gè)默認(rèn)的路由組，這里已經(jīng)略過不相干代碼。

r := gin.Default()

func Default() *Engine {
	...
	engine := New()
	...
}


func New() *Engine {
	...
	engine := &Engine{
		RouterGroup: RouterGroup{
			Handlers: nil,
			basePath: "/",
			root:     true,
		},
		...
	...
}

// RouterGroup is used internally to configure router, a RouterGroup is associated with
// a prefix and an array of handlers (middleware).
type RouterGroup struct {
	Handlers HandlersChain
	basePath string
	engine   *Engine
	root     bool
}

因此可以看出gin在底層實(shí)現(xiàn)上比普通的httprouter多出了一個(gè)路由組的概念。這個(gè)路由組的作用主要能對(duì)api進(jìn)行分組授權(quán)。例如正常的業(yè)務(wù)邏輯很多需要登錄授權(quán)，有的接口需要這個(gè)鑒權(quán)，有些則可以不用，這個(gè)時(shí)候就可以利用路由組的概念的去進(jìn)行分組。

• 這里用一個(gè)最簡單的例子去使用：

// 創(chuàng)建路由組
authorized := r.Group("/admin",func(c *gin.Context) {
		// 在此處編寫驗(yàn)證用戶權(quán)限的邏輯
		// 如果用戶未經(jīng)授權(quán)，則可以使用 c.Abort() 中止請(qǐng)求并返回相應(yīng)的錯(cuò)誤信息
	})

// 在路由組上添加需要授權(quán)的路徑
authorized.GET("/dashboard", dashboardHandler)
authorized.POST("/settings", settingsHandler)

當(dāng)然group源碼中也可以傳入一連串的handlers去進(jìn)行前置的處理業(yè)務(wù)邏輯。

// Group creates a new router group. You should add all the routes that have common middlewares or the same path prefix.
// For example, all the routes that use a common middleware for authorization could be grouped.
func (group *RouterGroup) Group(relativePath string, handlers ...HandlerFunc) *RouterGroup {
	return &RouterGroup{
		Handlers: group.combineHandlers(handlers),
		basePath: group.calculateAbsolutePath(relativePath),
		engine:   group.engine,
	}
}

對(duì)于正常的使用一個(gè)
而這個(gè)RouterGroup正如注釋提到的RouterGroup is used internally to configure router，只是配置對(duì)應(yīng)的路由，對(duì)應(yīng)真正的路由樹的結(jié)構(gòu)還是在對(duì)應(yīng)的engine的trees中的。與我們之前看的httprouter差不多

type methodTrees []methodTree

func New() *Engine {
	...
	trees            methodTrees
	...
}

所以總的來說，RouterGroup與Engine的關(guān)系是這樣

因此不管通過Engine實(shí)例對(duì)象可以創(chuàng)建多個(gè)routergroup，然后創(chuàng)建出來的routergroup都會(huì)再重新綁定上engine，而借助結(jié)構(gòu)體的正交性組合的特點(diǎn)，新構(gòu)建出來的組的路由組還可以繼續(xù)使用engine繼續(xù)創(chuàng)造新的路由組，而不管橫向創(chuàng)造多少個(gè)，或者縱向創(chuàng)建多少個(gè)，改變的始終是唯一那個(gè)engine的路由樹。而縱向創(chuàng)建group這種方式，則是gin中創(chuàng)建嵌套路由的使用方式。

package main

import (
	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	// 創(chuàng)建父級(jí)路由組
	v1 := router.Group("/v1")
	{
		// 在父級(jí)路由組中創(chuàng)建子級(jí)路由組
		users := v1.Group("/users")
		{
			// 子級(jí)路由組中的路由
			users.GET("/", func(c *gin.Context) {
				c.JSON(200, gin.H{"message": "Get all users"})
			})
			users.POST("/", func(c *gin.Context) {
				c.JSON(200, gin.H{"message": "Create a new user"})
			})
		}
	}

	router.Run(":8080")
}

四、hertz中的路由

hertz是字節(jié)內(nèi)部比較常用的web，而對(duì)于這一部分的router他做的結(jié)合優(yōu)化主要有兩種。

• 結(jié)合了httprouter的核心壓縮字典樹等理念，并且對(duì)沖突情況做了相應(yīng)的解決。
• 結(jié)合了gin中路由分組管理的概念。

第二點(diǎn)其實(shí)和Gin差不多，這里不再贅述，主要講下第一點(diǎn)。之前在httprouter中插入孩子節(jié)點(diǎn)的func會(huì)有很多wildcard的特殊處理，從而對(duì)應(yīng)的沖突時(shí)會(huì)報(bào)錯(cuò)。這樣做的原因是：

• 為了解決在同時(shí)遇到參數(shù)節(jié)點(diǎn)與靜態(tài)節(jié)點(diǎn)的情況時(shí)，httprouter不需要考慮匹配的的優(yōu)先級(jí)進(jìn)行返回。直接不解決拋出異常即可，這樣實(shí)現(xiàn)也會(huì)相應(yīng)的簡潔。 如：

func (n *node) insertChild(path, fullPath string, handle Handle) {
	for {
		// 找到路徑中第一個(gè)通配符前的前綴
		wildcard, i, valid := findWildcard(path)
		if i < 0 { // 沒有找到通配符
			break
		}

		// 通配符名稱不應(yīng)包含 ':' 和 '*'
		if !valid {
			panic("only one wildcard per path segment is allowed, has: '" +
				wildcard + "' in path '" + fullPath + "'")
		}

		// 檢查通配符是否有名稱
		if len(wildcard) < 2 {
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
		}

		// 檢查當(dāng)前節(jié)點(diǎn)是否有現(xiàn)有子節(jié)點(diǎn)，否則插入通配符將導(dǎo)致無法到達(dá)
		if len(n.children) > 0 {
			panic("wildcard segment '" + wildcard +
				"' conflicts with existing children in path '" + fullPath + "'")
		}

		// 參數(shù)通配符
		if wildcard[0] == ':' {
			if i > 0 {
				// 在當(dāng)前通配符之前插入前綴
				n.path = path[:i]
				path = path[i:]
			}

			n.wildChild = true
			child := &node{
				nType: param,
				path:  wildcard,
			}
			n.children = []*node{child}
			n = child
			n.priority++

			// 如果路徑不以通配符結(jié)尾，那么會(huì)有另一個(gè)以 '/' 開頭的非通配符子路徑
			if len(wildcard) < len(path) {
				path = path[len(wildcard):]
				child := &node{
					priority: 1,
				}
				n.children = []*node{child}
				n = child
				continue
			}

			// 否則完成。在新葉子節(jié)點(diǎn)中插入處理程序
			n.handle = handle
			return
		}

		// catchAll 通配符
		if i+len(wildcard) != len(path) {
			panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
		}

		if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
			panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
		}

		// 當(dāng)前固定寬度為 1，表示 '/'
		i--
		if path[i] != '/' {
			panic("no / before catch-all in path '" + fullPath + "'")
		}

		n.path = path[:i]

		// 第一個(gè)節(jié)點(diǎn): 具有空路徑的 catchAll 節(jié)點(diǎn)
		child := &node{
			wildChild: true,
			nType:     catchAll,
		}
		n.children = []*node{child}
		n.indices = string('/')
		n = child
		n.priority++

		// 第二個(gè)節(jié)點(diǎn): 包含變量的節(jié)點(diǎn)
		child = &node{
			path:     path[i:],
			nType:    catchAll,
			handle:   handle,
			priority: 1,
		}
		n.children = []*node{child}

		return
	}

	// 如果未找到通配符，直接插入路徑和處理程序
	n.path = path
	n.handle = handle
}

而對(duì)于hertz來講為了解決這個(gè)沖突，那么也是要將對(duì)應(yīng)的wildcard概念進(jìn)行淡化，例如之前httprouter的節(jié)點(diǎn)結(jié)構(gòu)體中會(huì)有一個(gè)wildChild bool的參數(shù)，來判斷下一個(gè)節(jié)點(diǎn)是否是參數(shù)的節(jié)點(diǎn)。而在hertz中則是淡化的相關(guān)的概念，完善了很多關(guān)于路由樹的結(jié)構(gòu)引用。對(duì)應(yīng)的節(jié)點(diǎn)定義如下：

type (
    node struct {
        kind       kind            // 節(jié)點(diǎn)類型，標(biāo)識(shí)節(jié)點(diǎn)是靜態(tài)、參數(shù)還是通配符
        label      byte            // 節(jié)點(diǎn)的標(biāo)簽，用于靜態(tài)路由節(jié)點(diǎn)，表示路由的一部分
        prefix     string          // 靜態(tài)路由節(jié)點(diǎn)的前綴
        parent     *node           // 父節(jié)點(diǎn)
        children   children        // 子節(jié)點(diǎn)列表
        ppath      string          // 原始路徑
        pnames     []string        // 參數(shù)名列表
        handlers   app.HandlersChain // 處理的handler鏈路
        paramChild *node           // 參數(shù)節(jié)點(diǎn)
        anyChild   *node           // 通配符節(jié)點(diǎn)
        isLeaf     bool            // 表示節(jié)點(diǎn)是否是葉子節(jié)點(diǎn)，即是否沒有子路由節(jié)點(diǎn)
    }

    kind     uint8   // 表示節(jié)點(diǎn)類型的枚舉
    children []*node // 子節(jié)點(diǎn)列表
)

因此他在是插入的實(shí)現(xiàn)上也更多偏向于一個(gè)更通用的路由樹。

// insert 將路由信息插入到路由樹中。
// path: 要插入的路由路徑
// h: 路由處理函數(shù)鏈
// t: 節(jié)點(diǎn)類型（靜態(tài)、參數(shù)、通配符）
// ppath: 父節(jié)點(diǎn)的路徑
// pnames: 參數(shù)名列表（對(duì)于參數(shù)節(jié)點(diǎn)）
func (r *router) insert(path string, h app.HandlersChain, t kind, ppath string, pnames []string) {
	currentNode := r.root
	if currentNode == nil {
		panic("hertz: invalid node")
	}
	search := path

	for {
		searchLen := len(search)
		prefixLen := len(currentNode.prefix)
		lcpLen := 0

		max := prefixLen
		if searchLen < max {
			max = searchLen
		}
		// 計(jì)算最長公共前綴長度
		for ; lcpLen < max && search[lcpLen] == currentNode.prefix[lcpLen]; lcpLen++ {
		}

		if lcpLen == 0 {
			// 根節(jié)點(diǎn)
			currentNode.label = search[0]
			currentNode.prefix = search
			// 如果有處理函數(shù)，handler鏈路更新當(dāng)前節(jié)點(diǎn)信息
			if h != nil {
				currentNode.kind = t
				currentNode.handlers = h
				currentNode.ppath = ppath
				currentNode.pnames = pnames
			}
			currentNode.isLeaf = currentNode.children == nil && currentNode.paramChild == nil && currentNode.anyChild == nil
		} else if lcpLen < prefixLen {
			// 分裂節(jié)點(diǎn)
			n := newNode(
				currentNode.kind,
				currentNode.prefix[lcpLen:],
				currentNode,
				currentNode.children,
				currentNode.handlers,
				currentNode.ppath,
				currentNode.pnames,
				currentNode.paramChild,
				currentNode.anyChild,
			)
			// 更新子節(jié)點(diǎn)的父節(jié)點(diǎn)信息
			for _, child := range currentNode.children {
				child.parent = n
			}
			if currentNode.paramChild != nil {
				currentNode.paramChild.parent = n
			}
			if currentNode.anyChild != nil {
				currentNode.anyChild.parent = n
			}

			// 重置父節(jié)點(diǎn)信息
			currentNode.kind = skind
			currentNode.label = currentNode.prefix[0]
			currentNode.prefix = currentNode.prefix[:lcpLen]
			currentNode.children = nil
			currentNode.handlers = nil
			currentNode.ppath = nilString
			currentNode.pnames = nil
			currentNode.paramChild = nil
			currentNode.anyChild = nil
			currentNode.isLeaf = false

			// 只有靜態(tài)子節(jié)點(diǎn)能夠到達(dá)此處
			currentNode.children = append(currentNode.children, n)

			if lcpLen == searchLen {
				// 在父節(jié)點(diǎn)處
				currentNode.kind = t
				currentNode.handlers = h
				currentNode.ppath = ppath
				currentNode.pnames = pnames
			} else {
				// 創(chuàng)建子節(jié)點(diǎn)
				n = newNode(t, search[lcpLen:], currentNode, nil, h, ppath, pnames, nil, nil)
				// 只有靜態(tài)子節(jié)點(diǎn)能夠到達(dá)此處
				currentNode.children = append(currentNode.children, n)
			}
			currentNode.isLeaf = currentNode.children == nil && currentNode.paramChild == nil && currentNode.anyChild == nil
		} else if lcpLen < searchLen {
			search = search[lcpLen:]
			c := currentNode.findChildWithLabel(search[0])
			if c != nil {
				// 深入下一級(jí)
				currentNode = c
				continue
			}
			// 創(chuàng)建子節(jié)點(diǎn)
			n := newNode(t, search, currentNode, nil, h, ppath, pnames, nil, nil)
			switch t {
			case skind:
				currentNode.children = append(currentNode.children, n)
			case pkind:
				currentNode.paramChild = n
			case akind:
				currentNode.anyChild = n
			}
			currentNode.isLeaf = currentNode.children == nil && currentNode.paramChild == nil && currentNode.anyChild == nil
		} else {
			// 節(jié)點(diǎn)已存在
			if currentNode.handlers != nil && h != nil {
				panic("handlers are already registered for path '" + ppath + "'")
			}

			if h != nil {
				currentNode.handlers = h
				currentNode.ppath = ppath
				currentNode.pnames = pnames
			}
		}
		return
	}
}

由于解決了沖突，使得參數(shù)節(jié)點(diǎn)與普通靜態(tài)節(jié)點(diǎn)兼容。那么對(duì)于相應(yīng)的查找肯定也是要做優(yōu)先校驗(yàn)，先上結(jié)論，在同一級(jí)上它的優(yōu)先級(jí)分別是：

• 靜態(tài)節(jié)點(diǎn)（static）> 參數(shù)節(jié)點(diǎn)（param） > 通配符節(jié)點(diǎn)（any） ，如下是將這個(gè)過程簡略后的代碼：

func (r *router) find(path string, paramsPointer *param.Params, unescape bool) (res nodeValue) {
	var (
		cn          = r.root  // 當(dāng)前節(jié)點(diǎn)
		search      = path    // 當(dāng)前路徑
		searchIndex = 0       // 當(dāng)前路徑的索引
		paramIndex  int       // 參數(shù)索引
		buf         []byte    // 字節(jié)緩沖區(qū)
	)

	// 回溯函數(shù)，每搜索的節(jié)點(diǎn)到盡頭時(shí)沒有搜索到結(jié)果就會(huì)調(diào)用此函數(shù)進(jìn)行回溯到第一個(gè)可能得節(jié)點(diǎn)
	// 它的搜索優(yōu)先級(jí)仍是靜態(tài)節(jié)點(diǎn)（static）> 參數(shù)節(jié)點(diǎn)（param） > 通配符節(jié)點(diǎn)（any）
	backtrackToNextNodeKind := func(fromKind kind) (nextNodeKind kind, valid bool) {
		...
		if previous.kind == akind {
			nextNodeKind = skind
		} else {
			nextNodeKind = previous.kind + 1
		}
		...
	}

	// 這是一個(gè)無限循環(huán)，因?yàn)樵谡业狡ヅ涔?jié)點(diǎn)之前，需要一直沿著路由樹向下搜索
	// search order: static > param > any
	for {
		if cn.kind == skind {
			...
			// 如果當(dāng)前節(jié)點(diǎn)是靜態(tài)節(jié)點(diǎn)（skind），則嘗試匹配當(dāng)前節(jié)點(diǎn)的前綴，并進(jìn)行切割
			if len(search) >= len(cn.prefix) && cn.prefix == search[:len(cn.prefix)] {
				// 匹配成功，將路徑中已匹配的部分去除，更新路徑為未匹配的部分。
				search = search[len(cn.prefix):]
				// 更新搜索索引，表示已經(jīng)匹配的部分的長度。
				searchIndex = searchIndex + len(cn.prefix)
			} else{
				//根據(jù)不同條件執(zhí)行相應(yīng)的操作，如回溯到上一層節(jié)點(diǎn)。調(diào)用（backtrackToNextNodeKind）
				nk, ok := backtrackToNextNodeKind(skind)
				if !ok {
					return // No other possibilities on the decision path
				} else if nk == pkind {
					goto Param
				} else {
					// Not found (this should never be possible for static node we are looking currently)
					break
				}
			}
		}
		
		// 檢查當(dāng)前節(jié)點(diǎn)是否是終端節(jié)點(diǎn)（葉子節(jié)點(diǎn)），并且該節(jié)點(diǎn)有對(duì)應(yīng)的handler(可以break跳出了）
		if search == nilString && len(cn.handlers) != 0 {
			...
		}

		// 當(dāng)路徑未完全匹配時(shí)，檢查當(dāng)前節(jié)點(diǎn)是否是靜態(tài)節(jié)點(diǎn)
		if search != nilString {
			...
		}
		// 當(dāng)路徑完全匹配但仍有可能有子節(jié)點(diǎn)的情況
		if search == nilString {
			...
		}

	Param:
		// Param node 節(jié)點(diǎn)處理情況
		...
	Any:
		// Any node 節(jié)點(diǎn)處理情況
		...
		// 當(dāng)前類型實(shí)在沒有可能得結(jié)果了，回溯上一層
		nk, ok := backtrackToNextNodeKind(akind)
		if !ok {
			break // No other possibilities on the decision path
		} 
		// 與backtrackToNextNodeKind(akind)中的情況進(jìn)行對(duì)應(yīng)，下一個(gè)節(jié)點(diǎn)類型的處理
		else if nk == pkind {
			goto Param
		} else if nk == akind {
			goto Any
		} else {
			// Not found
			break
		}
	}
	...
	return
}

因此可以看到整個(gè)搜索的過程其實(shí)是DFS+回溯遍歷這個(gè)路由樹的一個(gè)過程，然后在回溯的過程中不斷地按照節(jié)點(diǎn)的類型進(jìn)行優(yōu)先級(jí)遍歷，從而兼容了參數(shù)節(jié)點(diǎn)與靜態(tài)節(jié)點(diǎn)的沖突。

總結(jié)

最后來進(jìn)行一個(gè)總結(jié)：文章來源地址http://www.zghlxwxcb.cn/news/detail-804715.html

• 如果你的項(xiàng)目的路由在個(gè)位數(shù)、URI 固定且不通過 URI 來傳遞參數(shù)，實(shí)現(xiàn)restful風(fēng)格的api時(shí)，可以直接用官方庫,net/http 。
• 大部分的web框架路由很多都是由httprouter改編而來的，httprouter的路由本質(zhì)上是由壓縮字典樹作為數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，但httprouter不能兼容參數(shù)節(jié)點(diǎn)與通配符節(jié)點(diǎn)同時(shí)存在的問題，會(huì)拋出panic。
• gin框架以此基礎(chǔ)上實(shí)現(xiàn)了路由組的概念，一個(gè)gin的engine對(duì)象可以創(chuàng)建多個(gè)路由組（橫向創(chuàng)建），而路由組的結(jié)構(gòu)體中因?yàn)橛纸壎嗽衑ngine，則可以繼續(xù)嵌套創(chuàng)建路由（縱向創(chuàng)建），哪種創(chuàng)建方式最終指向的都是同一顆路由樹。
• hertz結(jié)合了gin與httprouter的，搜索時(shí)通過回溯+DFS進(jìn)行節(jié)點(diǎn)之間的優(yōu)先級(jí)排序，兼容了參數(shù)節(jié)點(diǎn)與靜態(tài)節(jié)點(diǎn)之間的沖突。

到了這里，關(guān)于深入淺出關(guān)于go web的請(qǐng)求路由的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！