前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Httprouter—用go实现的高性能路由器

Httprouter—用go实现的高性能路由器

作者头像
歪歪梯
发布2020-08-17 17:34:28
1.6K0
发布2020-08-17 17:34:28
举报
文章被收录于专栏:歪歪梯Club

简介

官方——https://github.com/julienschmidt/httprouter

HttpRouter is a lightweight high performance HTTP request router (also called multiplexer or just mux for short) for Go. In contrast to the default mux of Go's net/http package, this router supports variables in the routing pattern and matches against the request method. It also scales better. The router is optimized for high performance and a small memory footprint. It scales well even with very long paths and a large number of routes. A compressing dynamic trie (radix tree) structure is used for efficient matching.

简单描述,httprouter是一个golang实现的路由组件。httprouter使用一个前缀树来维护映射的父子关系,通过前缀树快速路由。同时其里面的HttpRouter结构体实现了golang的net.http.server的Handler接口,可以作为httpHandle发布。golang以性能出名的gin使用的也就是httprouter来做路由处理。

依赖

代码语言:javascript
复制
require github.com/julienschmidt/httprouter latest

使用Demo

代码语言:javascript
复制
package httpRouterDemo

import (
    "net/http"
    "github.com/julienschmidt/httprouter"
)

func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
    w.Write([]byte("hello world"))
}

func main() {
    router := httprouter.New()
    router.GET("/", Index)
    http.ListenAndServe(":80", router)
}

源码分析

New方法实际就是生成一个HttpRouter对象 接下来看看注册Get映射的实现

代码语言:javascript
复制
func (r *Router) GET(path string, handle Handle) {
    r.Handle(http.MethodGet, path, handle)
}
func (r *Router) Handle(method, path string, handle Handle) {
    if len(path) < 1 || path[0] != '/' {
        panic("path must begin with '/' in path '" + path + "'")
    }

    if r.trees == nil {
        r.trees = make(map[string]*node)
    }

    root := r.trees[method]
    if root == nil {
        root = new(node)
        r.trees[method] = root

        r.globalAllowed = r.allowed("*", "")
    }

    root.addRoute(path, handle)
}
func (n *node) addRoute(path string, handle Handle) {
    fullPath := path
    n.priority++
    numParams := countParams(path)

    // non-empty tree
    if len(n.path) > 0 || len(n.children) > 0 {
    walk:
        for {
            // Update maxParams of the current node
            if numParams > n.maxParams {
                n.maxParams = numParams
            }

            //查询最长公共前缀
            i := 0
            max := min(len(path), len(n.path))
            for i < max && path[i] == n.path[i] {
                i++
            }

            // 出现部分前缀匹配,最极端情况/根路径
            //创建一个以匹配部分为映射路径的空节点顶替当前匹配节点n,当前匹配节点n作为其子节点
            if i < len(n.path) {
                child := node{
                    path:      n.path[i:],
                    wildChild: n.wildChild,
                    nType:     static,
                    indices:   n.indices,
                    children:  n.children,
                    handle:    n.handle,
                    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.handle = nil
                n.wildChild = false
            }
            //到这里可以确认,n绝对可以成为注册映射的祖先节点
            //找到最匹配的祖先节点作为自己的父节点
            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)] &&
                        // Adding a child to a catchAll is not possible
                        n.nType != catchAll &&
                        // Check for longer wildcard, e.g. :name and :names
                        (len(n.path) >= len(path) || path[len(n.path)] == '/') {
                        continue walk
                    } else {
                        // Wildcard conflict
                        var pathSeg string
                        if n.nType == catchAll {
                            pathSeg = path
                        } else {
                            pathSeg = strings.SplitN(path, "/", 2)[0]
                        }
                        prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
                        panic("'" + pathSeg +
                            "' in new path '" + fullPath +
                            "' conflicts with existing wildcard '" + n.path +
                            "' in existing prefix '" + prefix +
                            "'")
                    }
                }

                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, handle)
                return

            } else if i == len(path) { // Make node a (in-path) leaf
                if n.handle != nil {
                    panic("a handle is already registered for path '" + fullPath + "'")
                }
                n.handle = handle
            }
            return
        }
    } else { 
        //树是空的,直接作为root
        n.insertChild(numParams, path, fullPath, handle)
        n.nType = root
    }
}

然后查看其处理请求的方式,也就是对前缀树进行查询

代码语言:javascript
复制
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
    if r.PanicHandler != nil {
        defer r.recv(w, req)
    }

    path := req.URL.Path

    if root := r.trees[req.Method]; root != nil {
        //查询前缀树
        if handle, ps, tsr := root.getValue(path); handle != nil {
            //handle请求
            handle(w, req, ps)
            return
        } else if req.Method != http.MethodConnect && path != "/" {
            code := 301 // Permanent redirect, request with GET method
            if req.Method != http.MethodGet {
                // Temporary redirect, request with same method
                // As of Go 1.3, Go does not support status code 308.
                code = 307
            }

            if tsr && r.RedirectTrailingSlash {
                if len(path) > 1 && path[len(path)-1] == '/' {
                    req.URL.Path = path[:len(path)-1]
                } else {
                    req.URL.Path = path + "/"
                }
                http.Redirect(w, req, req.URL.String(), code)
                return
            }

            // Try to fix the request path
            if r.RedirectFixedPath {
                fixedPath, found := root.findCaseInsensitivePath(
                    CleanPath(path),
                    r.RedirectTrailingSlash,
                )
                if found {
                    req.URL.Path = string(fixedPath)
                    http.Redirect(w, req, req.URL.String(), code)
                    return
                }
            }
        }
    }

    if req.Method == http.MethodOptions && r.HandleOPTIONS {
        // Handle OPTIONS requests
        if allow := r.allowed(path, http.MethodOptions); allow != "" {
            w.Header().Set("Allow", allow)
            if r.GlobalOPTIONS != nil {
                r.GlobalOPTIONS.ServeHTTP(w, req)
            }
            return
        }
    } else if r.HandleMethodNotAllowed { // Handle 405
        if allow := r.allowed(path, req.Method); allow != "" {
            w.Header().Set("Allow", allow)
            if r.MethodNotAllowed != nil {
                r.MethodNotAllowed.ServeHTTP(w, req)
            } else {
                http.Error(w,
                    http.StatusText(http.StatusMethodNotAllowed),
                    http.StatusMethodNotAllowed,
                )
            }
            return
        }
    }

    // Handle 404
    if r.NotFound != nil {
        r.NotFound.ServeHTTP(w, req)
    } else {
        http.NotFound(w, req)
    }
}
func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) {
walk: // outer loop for walking the tree
    for {
        //查询前缀树节点
        if len(path) > len(n.path) {
            if path[:len(n.path)] == n.path {
                path = path[len(n.path):]
                // If this node does not have a wildcard (param or catchAll)
                // child,  we can just look up the next child node and continue
                // to walk down the tree
                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
                        }
                    }

                    // Nothing found.
                    // We can recommend to redirect to the same URL without a
                    // trailing slash if a leaf exists for that path.
                    tsr = (path == "/" && n.handle != nil)
                    return

                }

                // handle wildcard child
                n = n.children[0]
                switch n.nType {
                case param:
                    // find param end (either '/' or path end)
                    end := 0
                    for end < len(path) && path[end] != '/' {
                        end++
                    }

                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    p[i].Key = n.path[1:]
                    p[i].Value = path[:end]

                    // we need to go deeper!
                    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
                    }

                    if handle = n.handle; handle != nil {
                        return
                    } else 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.handle != nil)
                    }

                    return

                case catchAll:
                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    p[i].Key = n.path[2:]
                    p[i].Value = path

                    handle = n.handle
                    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 handle = n.handle; handle != 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.handle != nil) ||
                        (n.nType == catchAll && n.children[0].handle != 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.handle != nil)
        return
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-08-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 歪歪梯Club 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简介
  • 依赖
  • 使用Demo
  • 源码分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档