算法分享: Golang HTTP 动态请求路径解析

[Nazz]

ACM 高手可以自动略过了.

大家好, 我是不知名框架`uRouter`的作者, 前 ACM 铜牌选手, 今天给大家分享一个动态路由匹配算法.

没看过gin这部分源码, 但自己实现一个也不难. 核心是一个字典树的变种, 称之为树形Map或许更为贴切.

• 代码

package main

import "strings"

const (
	defaultSeparator = "/" // 默认路径分隔符
	defaultVarPrefix = ':' // 默认变量前缀
)

type (
	apiHandler struct {
		VPath string   // API 路径
		Funcs []func() // 处理函数
	}

	routeTree struct {
		Value    *apiHandler           // 值
		Children map[string]*routeTree // 子节点
	}
)

func newRouteTree() *routeTree { return new(routeTree) }

// 判断字符串是否为变量
func isVar(s string) bool { return len(s) > 0 && s[0] == defaultVarPrefix }

// 分割字符串; 在原数组的基础上游走, 减少内存分配次数
func split(s string, sep string) []string {
	var j = 0
	var list = strings.Split(s, sep)
	for i, v := range list {
		if v != "" {
			list[j] = list[i]
			j++
		}
	}
	return list[:j]
}

// Set 注册接口
func (c *routeTree) Set(vpath string, funcs []func()) {
	var handler = &apiHandler{VPath: vpath, Funcs: funcs}
	var list = split(handler.VPath, defaultSeparator)
	if len(list) == 0 {
		return
	}
	c.doSet(c, 0, list, handler)
}

func (c *routeTree) doSet(node *routeTree, index int, list []string, handler *apiHandler) {
	var segment = list[index]
	if isVar(segment) {
		segment = "*"
	}

	var next = node.Children[segment]
	if node.Children == nil {
		node.Children = make(map[string]*routeTree)
	}
	if node.Children[segment] == nil {
		next = &routeTree{}
		node.Children[segment] = next
	}
	if index+1 == len(list) {
		next.Value = handler
	} else {
		c.doSet(next, index+1, list, handler)
	}
}

// Get 查找接口
func (c *routeTree) Get(path string) (*apiHandler, bool) {
	var list = split(path, defaultSeparator)
	if len(list) == 0 {
		return nil, false
	}
	return c.doGet(c, 0, list)
}

func (c *routeTree) doGet(node *routeTree, index int, list []string) (*apiHandler, bool) {
	if index == len(list) {
		return node.Value, true
	}
	var segment = list[index]
	if v, ok := node.Children[segment]; ok {
		return c.doGet(v, index+1, list)
	}
	if v, ok := node.Children["*"]; ok {
		return c.doGet(v, index+1, list)
	}
	return nil, false
}

• 性能测试

本测试共注册 1024 个接口, 每个接口分为 4 段.

goos: darwin
goarch: arm64
pkg: github.com/lxzan/uRouter
BenchmarkRouteTree_Get-8   	 6707703	       168.2 ns/op	      80 B/op	       1 allocs/op
PASS
ok  	github.com/lxzan/uRouter	1.433s

[Nazz]

不好意思说错了，是黑铁选手，距离黄铜还差一个气球🐸

[codehz]

gin 的实现思路大体上差不多，但是
第一不是简单的分割 /，而是会在插入 route 的时候去寻找最长前缀
第二也不是用 map 而是单纯的弄了一个 children 数组去匹配
其实挺符合现实使用场景的，因为一个目录下的分支通常没那么多（

[Nazz]

@codehz gin 似乎比我的实现复杂. 我是动静分离, 静态路由使用 map, 动态路由使用 tree.

[Nazz]

@codehz 分支较少的情况下, slice 实现 map 接口性能应该更优一点.

[cqcsdzmt]

一个不愿透露姓名的网友表示很赞

[ericls]

为啥非要给解决方案一个名字 解决方案的名字就应该叫： 「针对 XXX 问题的一种解决方案」

[Nazz]

@ericls 实事求是突出主题. 总不能这样起标题吧: 震惊! 比 gin 快一倍的动态路由解析算法 (乱说的, 没测试过)

[ColinLi]

@Nazz #3 gin 是前缀树

[ericls]

@Nazz 不是不是 我觉得这个标题很好 我就是说 总体上 那些 XXX tree 啊 xxx Map 啊 这种。

[ClarkAbe]

那你的 Benchmark 代码测试了一下我自己的新 router tux...

https://imgur.com/a/ZHM1oFI

我的路由结构是空间换时间以及利用数组不会 GC 的特性

```golang
type Tree struct {
father *Tree // 父路由节点
children [255]*Tree // 子路由节点
part []uint8 // 路径参数 (例如: :name *name)
method *Method // 路由方法 (methodTyp 类型)
}
```

```txt
Running tool: /usr/bin/go test -benchmem -run=^$ -bench ^BenchmarkRouteTree_Get$ tux

goos: linux
goarch: amd64
pkg: tux
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkRouteTree_Get-16 122476156 9.885 ns/op 0 B/op 0 allocs/op
PASS
ok tux 2.232s

```

[Nazz]

@ClarkAbe 可以控制变量和我的对比下: 1024 个接口, 每个路径分 4 段, 参数位置随机

[Nazz]

@ClarkAbe 我的测试代码在这里: https://github.com/lxzan/uRouter/blob/main/trie_test.go

[ClarkAbe]

@Nazz 我就是完全抄的你的测试代码.....

[ClarkAbe]

@Nazz 后续我把我的开源出来吧.....不过我框架还没写完, 还在整合 rest 接口架构

[ClarkAbe]

@Nazz gin 大部分用了 pool 来减少分配次数

[Nazz]

@ClarkAbe 还好吧，只在注册接口的时候创建一次 map, split 的 alloc 不可避免. 后续我测试下 sliceMap 怎么样，O(n)遍历数组

[huang82]

一个不愿透露姓名的网友表示很赞

[hailaz]

有个小小的疑惑，我想注册路径“/”，能成吗？

[iOCZ]

花了一点时间，能看懂 golang 了

[Nazz]

@hailaz 不行. 但是实际项目里面可以, 因为"/"会被注册到静态路由区

[ClarkAbe]

@Nazz 用你的测试代码写了 Benchmark 并且对比测试了 https://github.com/ClarkQAQ/tux

[Nazz]

@ClarkAbe 性能很不错, 在路径较短的时候接近静态路由了.