之前做 API server，制定 route path 時有遇到一些問題，於是就順手看了幾個 HTTP router / web framework 的 router 部分實作方式，並且記錄下來，提供給大家做個參考。

需要加入

這兩個 path 對應到不同的 handlers。

package github.com/go-chi/chi

知名 HTTP router library chi，其輕量、快速、handler 使用原生 net/http struct，都是不錯的優勢。和多數主流的 HTTP router 相似，chi 的 router 是採用 radix tree 結構，比較特別的是 chi 將 node type 分成四種：

與其他 router 相較起來，多了 Regexp 這個 type，而在插入新的 node 時候，會根據 type 來將 node 插入到適當的位置。

假設我們要插入兩個 path：

其樹狀圖如下：


為什麼要將 nodes 分類插入呢？因為就 path match 的嚴謹程度而言是 Static > Regexp > Param > CatchAll，因此如果先分類好， router 在進行尋找的時候，就會先從 Static 分類 (index = 0) 開始找起，以符合使用者預期的行為。

不過這樣做也會有個小問題，就是沒有用到的 bucket 會空著。(因為 node children 是 array 型態呈現)

另外一個問題是， Chi 在 search 的時候是使用 recursion 方式，這點對於效率與記憶體使用上都會有所影響。其他多數的 router 在 search tree 的時候是使用 iteration，只有在一些必要的部分才使用 recursion。

package github.com/labstack/echo/v4

echo 是蠻老牌的 web framework，在 2015 年第一次釋出正式版本，目前已來到 V4 版本。同樣地，echo 的 router 結構也是採用 radix tree ，不過在表現上和 chi 略有些差異。

echo 的 node type 只有三種：

缺少 Regexp type，因此 chi 相對來說，在 route path 設定上更豐富一些 。再來看一下插入 path 時的樹狀圖：


echo 的 node children 是 slice 型態，而 slice 內的 node 順序是根據插入先後來決定的，當要尋找 node 的時候，echo 也是會按照 skind > pkind > akind 的順序去找，不過由於 children 插入時並沒有預先分類，因此必須要 loop children 篩選出 type priority 高的 node，這裡是與 chi 明顯的差異處。

但即使如此，整體上 echo 的 search algorithm 還是寫的很不錯，在 Benchmark 上有優異的表現。

package github.com/gin-gonic/gin

同樣為老牌 web framework，gin 最為人所知的就是 router 的速度快，當然要快的話肯定也是基於 radix tree 所組成。

gin 的 node type 大同小異也是三種：

但與上面兩個 router 設計不同的是，gin 在插入 node 會有一些限制，例如上面的例子：


gin 不允許這樣的 path 設計，其原因 node 中有一個 wildChild member 是用來進行搜尋判斷，而當插入含有 params path 時，這個 wildChild 會被設定成 true，進而導致同一層的 static path child 會變成 unreachable 狀態。

此外，今天假設我們有些 path 需求，例如：

如果要兼容 gin 本身的限制，就要將 path 設定成：

這樣就能夠根據不同的 path 來進入到對應的 handler 了。

package github.com/gorilla/mux

以上幾個 router 都是採用 radix tree，所以最後來介紹一個很常見，但是採用單純 matcher list 設計的 gorilla/mux。

當我們在加入新的 path 時，gorilla mux 會將其新增到 routes slice 上，順序採用加入先後排列。


(Note: route 中其實有 matchers list，可以結合不同種類的 matcher，例如 headerMatcher, schemeMatcher 等)

在搜尋適合的 route 時候，會從第一個開始匹配，也就是說即使我們要找的 path 是 /stations/instances ，但是由於第一個 route 的 matcher 已經符合，所以就不會繼續比對到下一個更精確的 route。

因此也可以知道，gorilla mux 在搜尋上的速度一定是較慢，但可以搭配想要的 matcher，彈性也是蠻高的。

除了 path 搜尋速度之外，各大 router libraries 也會針對 context 做額外的效能提升。最明顯的就是使用 sync.Pool 來避免當每個 request 進來的時候，需要新建立一個 context 給 handler 使用。當短時間有大量 request 進出時，如果動態分配太多 context，會造成 Garbage Collection 的壓力，進而觸發清理而影響效能。使用 sync.Pool 的好處是可以重複使用閒置的 context，以減少此類問題發生。

以 Echo source code 為例，可以看到 context 從 pool 中取出和放回。

另外， Echo 更有趣的地方是，它在新建 context 的時候，會建立一個可以容納最大 params 數的 string slice(pvalues)，這樣就可以將 params 值放入 context 而不觸發 slice expansion。

Chi 則是有使用 sync.Pool，不過 context 的 params 會是一個 0 size 的 string slice，而在需要放入 params 值再使用 append 來插入到 params slice。雖然可能會觸發 slice expansion，不過如果 params 數很少，是不太會有明顯地效能影響。

有一點要特別注意的是，sync.Pool 不是每個場景都很適用的，例如：它會在 GC trigger 時候，把 pool 內的 object 清除，因此不適合放需要長時間保留的 object。還有就是即使使用 sync.Pool 也有可能降低效能，可以參考 Go: Understand the Design of Sync.Pool，文章中有例子講解和實作原理。

最後不可免俗地跑個 Benchmark，基於 julienschmidt/go-http-routing-benchmark 所測試的結果。老實說 Chi 的表現有點出乎我意料，除了 recursion 因素之外，推測還與 context reuse 方式有關，可參考 chi/tree.go。