V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Nazz
V2EX  ›  程序员

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

  •  
  •   Nazz · 2023-02-08 08:19:46 +08:00 · 1884 次点击
    这是一个创建于 495 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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
    
    22 条回复    2023-02-09 13:02:59 +08:00
    Nazz
        1
    Nazz  
    OP
       2023-02-08 08:23:45 +08:00 via Android
    不好意思说错了,是黑铁选手,距离黄铜还差一个气球🐸
    codehz
        2
    codehz  
       2023-02-08 09:00:02 +08:00
    gin 的实现思路大体上差不多,但是
    第一不是简单的分割 /,而是会在插入 route 的时候去寻找最长前缀
    第二也不是用 map 而是单纯的弄了一个 children 数组去匹配
    其实挺符合现实使用场景的,因为一个目录下的分支通常没那么多(
    Nazz
        3
    Nazz  
    OP
       2023-02-08 09:15:44 +08:00
    @codehz gin 似乎比我的实现复杂. 我是动静分离, 静态路由使用 map, 动态路由使用 tree.
    Nazz
        4
    Nazz  
    OP
       2023-02-08 09:19:45 +08:00
    @codehz 分支较少的情况下, slice 实现 map 接口性能应该更优一点.
    cqcsdzmt
        5
    cqcsdzmt  
       2023-02-08 10:55:41 +08:00   ❤️ 1
    一个不愿透露姓名的网友表示很赞
    ericls
        6
    ericls  
       2023-02-08 10:58:38 +08:00
    为啥非要给解决方案一个名字 解决方案的名字就应该叫: 「针对 XXX 问题的一种解决方案」
    Nazz
        7
    Nazz  
    OP
       2023-02-08 11:36:43 +08:00
    @ericls 实事求是突出主题. 总不能这样起标题吧: 震惊! 比 gin 快一倍的动态路由解析算法 (乱说的, 没测试过)
    ColinLi
        8
    ColinLi  
       2023-02-08 11:41:12 +08:00
    @Nazz #3 gin 是前缀树
    ericls
        9
    ericls  
       2023-02-08 11:41:23 +08:00 via iPhone   ❤️ 1
    @Nazz 不是不是 我觉得这个标题很好 我就是说 总体上 那些 XXX tree 啊 xxx Map 啊 这种。
    ClarkAbe
        10
    ClarkAbe  
       2023-02-08 11:54:07 +08:00   ❤️ 1
    那你的 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
        11
    Nazz  
    OP
       2023-02-08 11:56:23 +08:00
    @ClarkAbe 可以控制变量和我的对比下: 1024 个接口, 每个路径分 4 段, 参数位置随机
    Nazz
        12
    Nazz  
    OP
       2023-02-08 11:56:56 +08:00   ❤️ 1
    ClarkAbe
        13
    ClarkAbe  
       2023-02-08 12:02:17 +08:00
    @Nazz 我就是完全抄的你的测试代码.....
    ClarkAbe
        14
    ClarkAbe  
       2023-02-08 12:03:16 +08:00   ❤️ 1
    @Nazz 后续我把我的开源出来吧.....不过我框架还没写完, 还在整合 rest 接口架构
    ClarkAbe
        15
    ClarkAbe  
       2023-02-08 12:04:07 +08:00
    @Nazz gin 大部分用了 pool 来减少分配次数
    Nazz
        16
    Nazz  
    OP
       2023-02-08 12:12:23 +08:00 via Android
    @ClarkAbe 还好吧,只在注册接口的时候创建一次 map, split 的 alloc 不可避免. 后续我测试下 sliceMap 怎么样,O(n)遍历数组
    huang82
        17
    huang82  
       2023-02-08 12:16:30 +08:00
    一个不愿透露姓名的网友表示很赞
    hailaz
        18
    hailaz  
       2023-02-08 12:51:20 +08:00
    有个小小的疑惑,我想注册路径“/”,能成吗?
    iOCZ
        19
    iOCZ  
       2023-02-08 13:31:57 +08:00
    花了一点时间,能看懂 golang 了
    Nazz
        20
    Nazz  
    OP
       2023-02-08 13:36:54 +08:00
    @hailaz 不行. 但是实际项目里面可以, 因为"/"会被注册到静态路由区
    ClarkAbe
        21
    ClarkAbe  
       2023-02-09 11:51:16 +08:00
    @Nazz 用你的测试代码写了 Benchmark 并且对比测试了 https://github.com/ClarkQAQ/tux
    Nazz
        22
    Nazz  
    OP
       2023-02-09 13:02:59 +08:00   ❤️ 1
    @ClarkAbe 性能很不错, 在路径较短的时候接近静态路由了.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1023 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:35 · PVG 03:35 · LAX 12:35 · JFK 15:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.