Go-Gin源码学习四

48次阅读

共计 9347 个字符,预计需要花费 24 分钟才能阅读完成。

基数树

这次学习的是 Gin 中的路由,在学习源码一种我们看到了 Gin 的路由是它的特色。然而基础数据使用了基数树也提供了性能的保障。因为路由这部分比较独立而且逻辑相对复杂,所以需要单独学习。
首先我们需要了解的是基数树,百度百科中的解释
其中有一个图可以让我们更加直观的看到数据是如何存储的。

基数树,相当于是一种前缀树。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。
在上面的图里也可以看到,数据结构会把所有相同前缀都提取 剩余的都作为子节点。

基数树在 Gin 中的应用

从上面可以看到基数树是一个前缀树,图中也可以看到数据结构。那基数树在 Gin 中是如何应用的呢?举一个例子其实就能看得出来
router.GET(“/support”, handler1)
router.GET(“/search”, handler2)
router.GET(“/contact”, handler3)
router.GET(“/group/user/”, handler4)
router.GET(“/group/user/test”, handler5)
最终的内存结构为:

/ (handler = nil, indices = "scg")
    s (handler = nil, indices = "ue")
        upport (handler = handler1, indices = "")
        earch (handler = handler2, indices = "")
    contact (handler = handler3, indices = "")
    group/user/ (handler = handler4, indices = "u")
        test (handler = handler5, indices = "")

可以看到 router 使用 get 方法添加了 5 个路由,实际存储结果就是上面显示的。我特地在后面加上了每个节点中的 handler 和 indices。indices 是有序保存所有子节点的第一个字符形成的字符串。为什么要特意突出这个字段,因为在查找子节点下面是否包含 path 的时候不需要循环子节点,只需要循环这个字段就可以知道是否包含。这样的操作也可以提升一些效率。

源码查看

先看一下节点的对象的定义和如何调用的,需要注意的是 indices 这个字段 上面已经提到了它的作用

type node struct {
    // 保存这个节点上的 URL 路径
    // 例如上图中的 search 和 support, 共同的 parent 节点的 path="s"
    // 后面两个节点的 path 分别是 "earch" 和 "upport"
    path string
    // 判断当前节点路径是不是参数节点, 例如上图的:post 部分就是 wildChild 节点
    wildChild bool
    // 节点类型包括 static, root, param, catchAll
    // static: 静态节点, 例如上面分裂出来作为 parent 的 s
    // root: 如果插入的节点是第一个, 那么是 root 节点
    // catchAll: 有 * 匹配的节点
    // param: 除上面外的节点
    nType nodeType
    // 记录路径上最大参数个数
    maxParams uint8
    // 和 children[]对应, 保存的是分裂的分支的第一个字符
    // 例如 search 和 support, 那么 s 节点的 indices 对应的 "eu"
    // 代表有两个分支, 分支的首字母分别是 e 和 u
    indices string
    // 保存孩子节点
    children []*node
    // 当前节点的处理函数
    handle Handle
    // 优先级
    priority uint32
}

//RouterGrou 实现的 GET 方法调用了 handler
func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {return group.handle("GET", relativePath, handlers)
}

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
    // 方法计算出路径,把 group 中的 basepath 和 relativepath 合并在一起
    absolutePath := group.calculateAbsolutePath(relativePath)
    // 合并 handler 把 group 中添加的中间件和传入的 handlers 合并起来
    handlers = group.combineHandlers(handlers)
    // 调用 addRoute 添加 router
    group.engine.addRoute(httpMethod, absolutePath, handlers)
    return group.returnObj()}

接下来我们需要看的是 addRoute 这个方法了,方法体比较长。其实大多的逻辑都在处理带参数的节点,真正核心的逻辑其实并不多。我把主要的逻辑都写上了注释应该还是比较容易理解的。如果看不懂其实一步步 debug 几次也能帮助理解。

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {assert1(path[0] == '/', "path must begin with'/'")
    assert1(method != "","HTTP method can not be empty")
    assert1(len(handlers) > 0, "there must be at least one handler")

    debugPrintRoute(method, path, handlers)
    // 获取 method 的树的根节点,每个 method 都有一个根节点,比如 GET,POST 都会维护一个根节点
    root := engine.trees.get(method)
    // 如果没有则创建一个节点
    if root == nil {root = new(node)
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    // 正式添加路由
    root.addRoute(path, handlers)
}

func (n *node) addRoute(path string, handlers HandlersChain) {
    // 记录原始 path
    fullPath := path
    n.priority++
    // 统计 path 中包含多少参数 就是判断 `:`,`*` 的数量 最多 255 个
    numParams := countParams(path)

    // 判断节点是否为空
    if len(n.path) > 0 || len(n.children) > 0 {
    walk:
        for {
            // 更新最大参数数量
            if numParams > n.maxParams {n.maxParams = numParams}

            // 找到相同前缀 循环次数 是取 path 和 n.path 长度的小那个长度
            i := 0
            max := min(len(path), len(n.path))
            // 循环判断是否字符相同,相同则 i ++ 直到最后
            for i < max && path[i] == n.path[i] {i++}

            // 判断是否有前缀相同,如果有相同的则把目前这个节点提取出来作为子节点
            // 再把相同前缀的 path 部分作为 父节点
            // 比如 n 的 path = romaned 现在新增路由的 path = romanus 相同前缀为 roman
            // 步骤为://1. 提取 ed 新建一个 child 节点 把原来 n 的属性都复制过去
            //2. 把原来的 n 的 path 改为相同前缀:roman 为 indices 添加 子节点的第一个字符:e
            if i < len(n.path) {
                child := node{path:      n.path[i:],
                    wildChild: n.wildChild,
                    indices:   n.indices,
                    children:  n.children,
                    handlers:  n.handlers,
                    priority:  n.priority - 1,
                }

                // Update maxParams (max of all children)
                for i := range child.children {if child.children[i].maxParams > child.maxParams {child.maxParams = child.children[i].maxParams
                    }
                }

                n.children = []*node{&child}
                // []byte for proper unicode char conversion, see #65
                n.indices = string([]byte{n.path[i]})
                n.path = path[:i]
                n.handlers = nil
                n.wildChild = false
            }

            // 原先的节点 n 现在已经分成 2 个节点了 结构为://roman 父节点
            //    ed    子节点[0]
            // 那么现在需要把传入的路由添加到这个父节点中
            // 最终结构为
            //roman 父节点
            //    ed 子节点[0]
            //    us 子节点[1]
            // 其中还有一些情况需要自调用 相当于递归 举例说明://roman
            //    ed
            //    uie
            // 当判断父节点 n 本来就有一个 uie 子节点 这时候 uie 和 us 又有相同前缀 u 这个时候需要把这个 u 再次提取出来作为父节点 所以需要递归调用 walk
            // 最终结果为 三层结构
            //roman
            //    ed
            //    u
            //        ie
            //        s
            // 还有一种情况是如果是带有参数的路由 则也会再次调用 walk
            if i < len(path) {path = path[i:]

                if n.wildChild {n = n.children[0]
                    n.priority++

                    // Update maxParams of the child node
                    if numParams > n.maxParams {n.maxParams = numParams}
                    numParams--

                    // Check if the wildcard matches
                    if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
                        // check for longer wildcard, e.g. :name and :names
                        if len(n.path) >= len(path) || path[len(n.path)] == '/' {continue walk}
                    }

                    panic("path segment'" + path +
                        "'conflicts with existing wildcard'" + n.path +
                        "'in path'" + fullPath + "'")
                }

                c := path[0]

                // slash after param
                if n.nType == param && c == '/' && len(n.children) == 1 {n = n.children[0]
                    n.priority++
                    continue walk
                }

                // Check if a child with the next path byte exists
                for i := 0; i < len(n.indices); i++ {if c == n.indices[i] {i = n.incrementChildPrio(i)
                        n = n.children[i]
                        continue walk
                    }
                }

                // Otherwise insert it
                if c != ':' && c != '*' {// []byte for proper unicode char conversion, see #65
                    n.indices += string([]byte{c})
                    child := &node{maxParams: numParams,}
                    n.children = append(n.children, child)
                    n.incrementChildPrio(len(n.indices) - 1)
                    n = child
                }
                n.insertChild(numParams, path, fullPath, handlers)
                return

            } else if i == len(path) {
                if n.handlers != nil {panic("handlers are already registered for path'" + fullPath + "'")
                }
                n.handlers = handlers
            }
            return
        }
    } else { // 节点为空,直接添加直接添加路由
        n.insertChild(numParams, path, fullPath, handlers)
        n.nType = root
    }
}

// 添加节点函数 主要处理包含参数节点
func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
    var offset int // already handled bytes of the path

    // 循环查找前缀为 ':' 或者 '*'
    for i, max := 0, len(path); numParams > 0; i++ {c := path[i]
        if c != ':' && c != '*' {continue}

        // 判断在 * 参数之后不能再有 * 或者: 否则则报错 除非到了下一个 /
        end := i + 1
        for end < max && path[end] != '/' {switch path[end] {
            // the wildcard name must not contain ':' and '*'
            case ':', '*':
                panic("only one wildcard per path segment is allowed, has:'" +
                    path[i:] + "'in path'" + fullPath + "'")
            default:
                end++
            }
        }

        // 检查这个节点是否存在子节点,如果我们在这里插入通配符,子节点将是不可访问的
        if len(n.children) > 0 {panic("wildcard route'" + path[i:end] +
                "'conflicts with existing children in path'" + fullPath + "'")
        }

        // check if the wildcard has a name
        if end-i < 2 {panic("wildcards must be named with a non-empty name in path'" + fullPath + "'")
        }

        // 参数类型 相当于注册路由时候带有:
        if c == ':' {
            // split path at the beginning of the wildcard
            if i > 0 {n.path = path[offset:i]
                offset = i
            }

            child := &node{
                nType:     param,
                maxParams: numParams,
            }
            n.children = []*node{child}
            n.wildChild = true
            n = child
            n.priority++
            numParams--

            if end < max {n.path = path[offset:end]
                offset = end

                child := &node{
                    maxParams: numParams,
                    priority:  1,
                }
                n.children = []*node{child}
                n = child
            }

        } else {
            // 如果是通配符 *
            if end != max || numParams > 1 {panic("catch-all routes are only allowed at the end of the path in path'" + fullPath + "'")
            }

            if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {panic("catch-all conflicts with existing handle for the path segment root in path'" + fullPath + "'")
            }

            // currently fixed width 1 for '/'
            i--
            if path[i] != '/' {panic("no / before catch-all in path'" + fullPath + "'")
            }

            n.path = path[offset:i]

            // first node: catchAll node with empty path
            child := &node{
                wildChild: true,
                nType:     catchAll,
                maxParams: 1,
            }
            n.children = []*node{child}
            n.indices = string(path[i])
            n = child
            n.priority++

            // second node: node holding the variable
            child = &node{path:      path[i:],
                nType:     catchAll,
                maxParams: 1,
                handlers:  handlers,
                priority:  1,
            }
            n.children = []*node{child}

            return
        }
    }

    // 插入路由 如果不包含参数节点 offset 为 0
    n.path = path[offset:]
    n.handlers = handlers
}

最后我们要看下根据 path 获取 router 的方法 getRouter。这个方法还是比较简单的,注释基本也能明白。

// 根据 path 查找路由的方法
func (n *node) getValue(path string, po Params, unescape bool) (handlers HandlersChain, p Params, tsr bool) {
    p = po
walk:
    for {if len(path) > len(n.path) {if path[:len(n.path)] == n.path {path = path[len(n.path):]
                // 判断如果不是参数节点
                // 那 path 的第一个字符 循环对比 indices 中的每个字符查找到子节点
                if !n.wildChild {c := path[0]
                    for i := 0; i < len(n.indices); i++ {if c == n.indices[i] {n = n.children[i]
                            continue walk
                        }
                    }

                    tsr = path == "/" && n.handlers != nil
                    return
                }

                // handle wildcard child
                n = n.children[0]
                switch n.nType {
                case param:
                    // 如果是普通 ':' 节点, 那么找到 / 或者 path end, 获得参数
                    end := 0
                    for end < len(path) && path[end] != '/' {end++}

                    // save param value
                    if cap(p) < int(n.maxParams) {p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    p[i].Key = n.path[1:]
                    val := path[:end]
                    if unescape {
                        var err error
                        if p[i].Value, err = url.QueryUnescape(val); err != nil {p[i].Value = val // fallback, in case of error
                        }
                    } else {p[i].Value = val
                    }

                    // 如果参数还没处理完, 继续 walk
                    if end < len(path) {if len(n.children) > 0 {path = path[end:]
                            n = n.children[0]
                            continue walk
                        }

                        // ... but we can't
                        tsr = len(path) == end+1
                        return
                    }
                    // 否则获得 handle 返回就 OK
                    if handlers = n.handlers; handlers != nil {return}
                    if len(n.children) == 1 {
                        // No handle found. Check if a handle for this path + a
                        // trailing slash exists for TSR recommendation
                        n = n.children[0]
                        tsr = n.path == "/" && n.handlers != nil
                    }

                    return

                case catchAll:
                    // * 匹配所有参数
                    if cap(p) < int(n.maxParams) {p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    p[i].Key = n.path[2:]
                    if unescape {
                        var err error
                        if p[i].Value, err = url.QueryUnescape(path); err != nil {p[i].Value = path // fallback, in case of error
                        }
                    } else {p[i].Value = path
                    }

                    handlers = n.handlers
                    return

                default:
                    panic("invalid node type")
                }
            }
        } else if path == n.path {
            // We should have reached the node containing the handle.
            // Check if this node has a handle registered.
            if handlers = n.handlers; handlers != nil {return}

            if path == "/" && n.wildChild && n.nType != root {
                tsr = true
                return
            }

            // No handle found. Check if a handle for this path + a
            // trailing slash exists for trailing slash recommendation
            for i := 0; i < len(n.indices); i++ {if n.indices[i] == '/' {n = n.children[i]
                    tsr = (len(n.path) == 1 && n.handlers != nil) ||
                        (n.nType == catchAll && n.children[0].handlers != nil)
                    return
                }
            }

            return
        }

        // Nothing found. We can recommend to redirect to the same URL with an
        // extra trailing slash if a leaf exists for that path
        tsr = (path == "/") ||
            (len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
                path == n.path[:len(n.path)-1] && n.handlers != nil)
        return
    }
}

总结

Gin 的路由是它的特色,其实就是因为他的存储结构。基数树的存储结构可以很快的查询到对应路由并且执行到 handler。避免了每次请求循环所有路由的逻辑,提升了 Gin 整体的性能。试想如果一个大型项目中 GET 路由有 100 个,如果每次请求都去循环 100 次查找性能会很差,如果使用基数树的存储方式可能只需要经过几次的查询。

Gin 路由代码很长,其中大部分是处理带有参数的节点的逻辑。下一次的学习中,还是老规矩,自己模仿着写一个基数树存储结构的路由查找逻辑。去除掉那些参数逻辑只留下主要核心逻辑。

正文完
 0