HTTP Router 算法演進

概述

本文從開發中常見的應用場景 “路由管理” 爲例，介紹三種常用的實現方案背後的數據結構和算法 (代碼實現爲 Go 語言)。

應用示例

下面是一個典型的 REST 風格的 API 列表:

kwvK8R

上面的 API 翻譯爲 Go 代碼，大致如下 (忽略方法的具體實現):

package main

import (
 "log"
 "net/http"
)

func main() {
 http.HandleFunc("/users/list", nil)
 http.HandleFunc("/users/dbwu", nil)
 http.HandleFunc("/users", nil)
 http.HandleFunc("/users/dbwu", nil)
 http.HandleFunc("/users/dbwu", nil)

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

標準庫方案

最簡單的方案就是直接使用 map[string]func() 作爲路由的數據結構，鍵爲具體的路由，值爲具體的處理方法。

標準庫中使用的就是這種方案，我們可以簡單追蹤一下對應的代碼:

// 路由管理數據結構

type ServeMux struct {
 mu    sync.RWMutex          // 對象操作讀寫鎖
 m     map[string]muxEntry   // 存儲路由映射關係
}

方法從 http.HandleFunc 方法開始追蹤:

// 註冊路由處理方法
func HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
 DefaultServeMux.HandleFunc(pattern, handler)
}

func (mux *ServeMux) HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
 mux.Handle(pattern, HandlerFunc(handler))
}

func (mux *ServeMux) Handle(pattern string, handler Handler) {
 mux.mu.Lock()
 defer mux.mu.Unlock()

 ...

 if _, exist := mux.m[pattern]; exist {
  // 如果註冊的 URL 重複了，拋出 panic
  panic("http: multiple registrations for " + pattern)
 }

 if mux.m == nil {
  // 惰性初始化
  mux.m = make(map[string]muxEntry)
 }

 // 註冊完成
 e := muxEntry{h: handler, pattern: pattern}
 mux.m[pattern] = e

 ...
}

優點和不足

使用 map[string]func() 作爲路由的數據結構，最明顯的優點就是:

實現簡單: map 是標準庫內置的數據結構，可以直接使用並且代碼可讀性高
性能較高: 因爲路由寫入操作只會發生一次 (註冊時)，後續的操作全部是讀取操作，基於標準庫的 map 性能已經足夠優秀

同時，該方案的不足也是顯而易見的:

內存浪費: 即使存在很多前綴相同的路徑 (例如 /users, /users/list, /users/dbwu, 三個路徑的前綴都是 /users, 這部分是可以複用的)，map 結構還是會每個路徑單獨映射，浪費大量的內存
不夠靈活: 難以處理動態路由和正則表達式匹配等複雜的路徑 (例如 /users/:id 或 /users/{id:[0-9]+})
無法處理重複路徑：如果多個處理方法綁定到相同的路徑上 (例如 GET /users 和 POST /users)，map 只能存儲一個鍵值對，也就是隻有最後一個註冊的處理函數會被調用
不支持中間件：map 結構不支持中間件，這在現代 Web 開發中幾乎是不可接受的

基於以上特點，在真實的項目開發中不會使用 map[string]func() 作爲路由的實現數據結構。

Trie Tree

Trie Tree 也稱爲字典樹或前綴樹，是一種用於高效存儲和檢索、用於從某個集合中查到某個特定 key 的數據結構。這些 key 通常是字符串，節點之間的父子關係不是由整個 key 定義，而是由 key 中的單個字符定義。對某個 key 對應的元素進行相關操作 (寫入、更新、刪除) 就是一次 DFS (深度優先遍歷) 過程。

算法複雜度

N: 字符串的數量
M: 字符串的平均長度
L: 字符串的長度

PMAdBT

KERgJI

Trie Tree 的核心思想是空間換時間，利用字符串的公共前綴來減少字符比較操作，提升查詢效率。

圖示

圖片來源: https://theoryofprogramming.wordpress.com/2015/01/16/trie-tree-implementation/

如圖所示，是一個典型的 Trie Tree, 其中包含了如下元素:

"their", "there", "this", "that", "does", "did"

本文不再描述算法的具體操作過程了，讀者可以通過代碼來感受一下，如果希望抓住細節，可以閱讀維基百科的介紹，或者通過這個可視化在線工具 [1] 來手動操作體驗。

實現代碼

首先寫一個基礎版的 Trie Tree 代碼，對算法本身做一個初步認識。

package trie

// Trie Tree 節點
type Trie struct {
 // 標記當前節點是否爲有效的路由
 // 例如添加了路由 /users
 // 那麼 /user, /usr 不能算作有效的路由
 // 也就是隻有字符 "s" 節點的 IsPath 字段爲 true
 IsPath bool

 // 當前節點的子節點
 Children map[byte]*Trie
}

func New() Trie {
 return Trie{false, make(map[byte]*Trie)}
}

// Add 添加一個路由到 Trie Tree
func (t *Trie) Add(path string) {
 parent := t
 // 逐個 byte 加入到 Trie Tree
 for i := range path {
  if child, ok := parent.Children[path[i]]; ok {
   // 如果子節點不爲空，繼續向下遍歷
   parent = child
  } else {
   // 如果子節點爲空，構造新的節點
   newChild := &Trie{false, make(map[byte]*Trie)}
   parent.Children[path[i]] = newChild
   parent = newChild
  }
 }

 // 更新當前路由的葉子節點的 IsPath 字段
 parent.IsPath = true
}

// Find 返回指定路由是否存在於 Trie Tree 中
func (t *Trie) Find(path string) bool {
 parent := t
 for i := range path {
  if child, ok := parent.Children[path[i]]; ok {
   parent = child
  } else {
   return false
  }
 }
 return parent.IsPath
}

然後對上面的實現代碼做一個簡單的小測試:

package trie

import "testing"

func TestTrie(t *testing.T) {
 trieTree := New()

 if got := trieTree.Find("hello"); got != false {
  t.Errorf("Get() = %v, want %v", got, false)
 }

 trieTree.Add("hello")

 if got := trieTree.Find("hello"); got != true {
  t.Errorf("Get() = %v, want %v", got, true)
 }
 if got := trieTree.Find("he"); got != false {
  t.Errorf("Get() = %v, want %v", got, false)
 }

 trieTree.Add("he")
 if got := trieTree.Find("he"); got != true {
  t.Errorf("Get() = %v, want %v", got, true)
 }
}

實現路由管理

現在，我們將剛纔的 “算法部分” 代碼配合標準庫提供的 API 代碼，完成一個基礎版的路由管理功能。

package main

import (
 "fmt"
 "log"
 "net/http"
)

// Router 節點
type Router struct {
 Path   string
 Method string

 // 標記當前節點是否爲有效的路由
 // 例如添加了路由 /users
 // 那麼 /user, /usr 不能算作有效的路由
 // 也就是隻有字符 "s" 節點的 IsPath 字段爲 true
 IsPath bool

 // 當前節點的子節點
 Children map[byte]*Router

 // 路由處理方法
 Handler http.HandlerFunc
}

func NewRouter() *Router {
 return &Router{IsPath: false, Children: make(map[byte]*Router)}
}

// Add 添加一個路由到 Router
func (r *Router) Add(method, path string, handler http.HandlerFunc) {
 parent := r
 // 逐個 byte 加入到 Router Tree
 for i := range path {
  if child, ok := parent.Children[path[i]]; ok {
   // 如果子節點不爲空，繼續向下遍歷
   parent = child
  } else {
   // 如果子節點爲空，構造新的節點
   newChild := NewRouter()
   parent.Children[path[i]] = newChild
   parent = newChild
  }
 }

 parent.Method = method
 parent.Handler = handler

 // 更新當前路由的葉子節點的 IsPath 字段
 parent.IsPath = true
}

// Find 返回指定路由是否存在於 Router 中
func (r *Router) Find(method, path string) (http.HandlerFunc, bool) {
 parent := r

 for i := range path {
  if child, ok := parent.Children[path[i]]; ok {
   parent = child
  } else {
   return nil, false
  }
 }

 return parent.Handler, parent.IsPath && parent.Method == method
}

// 實現 http.Handler 接口
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
 handler, ok := r.Find(req.Method, req.URL.Path)
 if ok {
  handler(w, req)
 } else {
  http.NotFound(w, req)
 }
}

// 處理所有路由的方法
// 輸出請求 Method 和 URL
func allHandler(w http.ResponseWriter, req *http.Request) {
 _, _ = fmt.Fprintln(w, req.Method, req.URL)
}

func main() {
 r := NewRouter()

 r.Add("GET", "/hello", allHandler)
 r.Add("GET", "/users/list", allHandler)

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

爲了節省篇幅，這裏就不寫測試代碼了，下面進行幾個簡單的測試:

# 啓動服務
$ go run main.go

# 測試兩個正常的 URL

$ curl 127.0.0.1:8080/hello

# 輸出如下
GET /hello

$ curl 127.0.0.1:8080/users/list

# 輸出如下
GET /users/list

# 測試兩個不存在的 URL

$ curl 127.0.0.1:8080

# 輸出如下
404 page not found

$ curl 127.0.0.1:8080/users/123456

# 輸出如下
404 page not found

優點

Trie Tree 時間複雜度低，和一般的樹形數據結構相比，Trie Tree 擁有更快的前綴搜索和查詢性能，和查詢時間複雜度爲 O(1) 常數的哈希算法相比， Trie Tree 支持前綴搜索，並且可以節省哈希函數的計算開銷和避免哈希值碰撞的情況，最後，Trie Tree 還支持對關鍵字進行字典排序。

適用場景

排序 : 一組字符串 key 的字典排序，可以通過爲給定 key 構建一個 Trie Tree，然後通過前序方式遍歷樹來實現, burstsort 是 2007 年最快的字符串排序算法，其基礎數據結構就是 Trie Tree
全文索引: 通過一種特殊的 Trie Tree 實現，一般稱爲後綴樹，可用於索引文本中的所有後綴以執行快速全文搜索
搜索引擎: 當你在搜索引擎的輸入框中輸入關鍵字時，自動補全的提示信息
生物信息: 基因序列對比軟件
路由管理: 網絡 IP 路由表，Web 中的 HTTP Router 管理

不適用場景

字符串公共前綴太少，造成 Trie Tree 節點稀疏分佈，這時哈希表是更好的選擇
節點之間的父子節點使用指針連接，對 CPU 和自帶 GC 語言不太友好
字符集過大會造成過多的存儲空間佔用 (Trie Tree 是空間換時間)
字符串過長會使 Trie Tree 深度變大，這時應該使用接下來講到的 Radix Tree

Radix Tree

Radix Tree（基數樹）是一種特殊的數據結構，用於高效地存儲和搜索字符串鍵值對，它是一種基於前綴的樹狀結構，通過將相同前綴的鍵值對合並在一起來減少存儲空間的使用。 Radix Tree 的關鍵思想是利用公共前綴來合併節點，每個節點代表一個字符，從根節點到葉子節點的路徑即爲一個字符串鍵，每個節點上存儲着一個字符串的部分子串，並且每個節點可以代表多個鍵值對。

算法複雜度

N: 字符串的數量
M: 字符串的平均長度
L: 字符串的長度

2yQow8

注意: Radix Tree 的使用場景是樹中有較多節點擁有相同前綴，所以即使和 Trie Tree 的空間複雜度一樣，但是實際應用中，Radix Tree 通過壓縮公共前綴，空間使用要比 Trie Tree 節省很多。

SpYUtj