HTTP Router 算法演进

2023-07-13 算法 Trie Tree Radix Tree Go 源码分析读代码

概述

本文从开发中常见的应用场景 “路由管理” 为例，介绍三种常用的实现方案背后的数据结构和算法 (代码实现为 Go 语言)。

应用示例

下面是一个典型的 REST 风格的 API 列表:

Method	URL
GET	/users/list
GET	/users/dbwu
POST	/users
PUT	/users/dbwu
DELETE	/users/dbwu

上面的 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: 字符串的长度

空间复杂度
O(NM)

操作	时间复杂度
插入	O(L)
查找	O(L)
删除	O(L)

Trie Tree 的核心思想是空间换时间，利用字符串的公共前缀来减少字符比较操作，提升查询效率。

图示

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

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

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

本文不再描述算法的具体操作过程了，读者可以通过代码来感受一下，如果希望抓住细节，可以阅读维基百科的介绍，或者通过这个可视化在线工具来手动操作体验。

实现代码

首先写一个基础版的 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: 字符串的长度

空间复杂度
O(NM)

注意: Radix Tree 的使用场景是树中有较多节点拥有相同前缀，所以即使和 Trie Tree 的空间复杂度一样，但是实际应用中，Radix Tree 通过压缩公共前缀，空间使用要比 Trie Tree 节省很多。

操作	时间复杂度
插入	O(L)
查找	O(L)
删除	O(L)