Go语言router请求路由
|
在常见的 Web 框架中，router 是必备的组件。Go语言圈子里 router 也时常被称为 http 的 multiplexer。通过前面几节的学习，我们已经知道了如何用 http 标准库中内置的 mux 来完成简单的路由功能了。如果开发 Web 系统对路径中带参数没什么兴趣的话，用 http 标准库中的 mux 就可以。 RESTful 是几年前刮起的 API 设计风潮，在 RESTful 中除了 GET 和 POST 之外，还使用了 HTTP 协议定义的几种其它的标准化语义。具体包括：
const (
GET /repos/:owner/:repo/comments/:id/reactions 如果我们的系统也想要这样的 URL 设计，使用标准库的 mux 显然就力不从心了。 httprouter较流行的开源 go Web 框架大多使用 httprouter，或是基于 httprouter 的变种对路由进行支持。前面提到的 github 的参数式路由在 httprouter 中都是可以支持的。因为 httprouter 中使用的是显式匹配，所以在设计路由的时候需要规避一些会导致路由冲突的情况，例如：
conflict:
panic: wildcard route ':id' conflicts with existing children in 除支持路径中的 wildcard 参数之外，httprouter 还可以支持 * 号来进行通配，不过 * 号开头的参数只能放在路由的结尾，例如下面这样：
Pattern: /src/*filepath 除了正常情况下的路由支持，httprouter 也支持对一些特殊情况下的回调函数进行定制，例如 404 的时候：
r := httprouter.New()
r.PanicHandler = func(w http.ResponseWriter,r *http.Request,c interface{}) { 原理httprouter 和众多衍生 router 使用的数据结构被称为压缩字典树（Radix Tree）。大家可能没有接触过压缩字典树，但对字典树（Trie Tree）应该有所耳闻。下图是一个典型的字典树结构： 图：字典树 字典树常用来进行字符串检索，例如用给定的字符串序列建立字典树。对于目标字符串，只要从根节点开始深度优先搜索，即可判断出该字符串是否曾经出现过，时间复杂度为 O(n) ，n 可以认为是目标字符串的长度。 为什么要这样做？字符串本身不像数值类型可以进行数值比较，两个字符串对比的时间复杂度取决于字符串长度。如果不用字典树来完成上述功能，要对历史字符串进行排序，再利用二分查找之类的算法去搜索，时间复杂度只高不低。可认为字典树是一种空间换时间的典型做法。 普通的字典树有一个比较明显的缺点，就是每个字母都需要建立一个孩子节点，这样会导致字典树的层数比较深，压缩字典树相对好地平衡了字典树的优点和缺点。下图是典型的压缩字典树结构：  图：压缩字典树 每个节点上不只存储一个字母了，这也是压缩字典树中“压缩”的主要含义。使用压缩字典树可以减少树的层数，同时因为每个节点上数据存储也比通常的字典树要多，所以程序的局部性较好（一个节点的 path 加载到 cache 即可进行多个字符的对比），从而对 CPU 缓存友好。 压缩字典树创建过程我们来跟踪一下 httprouter 中，一个典型的压缩字典树的创建过程，路由设定如下：
PUT /user/installations/:installation_id/repositories/:repository_id GET /marketplace_listing/plans/ohyes 最后一条补充路由是我们臆想的，除此之外所有 API 路由均来自于 api.github.com。root 节点创建httprouter 的 Router 结构体中存储压缩字典树使用的是下述数据结构：
// 略去了其它部分的 Router struct
GET 简单来讲，某个方法第一次插入的路由就会导致对应字典树的根节点被创建，我们按顺序，先是一个 PUT：
r := httprouter.New()  图：插入路由之后的压缩字典树 radix 的节点类型为 *httprouter.node ，为了说明方便，我们留下了目前关心的几个字段：
static // 非根节点的普通字符串节点
当然，PUT 路由只有唯一的一条路径。接下来，我们以后续的多条 GET 路径为例，讲解子节点的插入过程。 子节点插入当插入 GET /marketplace_listing/plans 时，类似前面 PUT 的过程，GET 树的结构如下图所示： 图：插入第一个节点的压缩字典树 因为第一个路由没有参数，path 都被存储到根节点上了。所以只有一个节点。 然后插入 GET /marketplace_listing/plans/:id/accounts ，新的路径与之前的路径有共同的前缀，且可以直接在之前叶子节点后进行插入，那么结果也很简单，插入后的树结构如下图所示：  图：插入第二个节点的压缩字典树 由于 :id 这个节点只有一个字符串的普通子节点，所以 indices 还依然不需要处理。 上面这种情况比较简单，新的路由可以直接作为原路由的子节点进行插入。实际情况不会这么美好。 边分裂接下来我们插入 GET /search，这时会导致树的边分裂，如下图所示。 图：插入第三个节点，导致边分裂 原有路径和新的路径在初始的 / 位置发生分裂，这样需要把原有的 root 节点内容下移，再将新路由 search 同样作为子节点挂在 root 节点之下。这时候因为子节点出现多个，root 节点的 indices 提供子节点索引，这时候该字段就需要派上用场了。"ms" 代表子节点的首字母分别为 m(marketplace) 和 s(search)。 我们一鼓作气，把 GET /status 和 GET /support 也插入到树中。这时候会导致在 search 节点上再次发生分裂，最终结果见下图：  图：插入所有路由后的压缩字典树 子节点冲突处理在路由本身只有字符串的情况下，不会发生任何冲突。只有当路由中含有 wildcard（类似 :id）或者 catchAll 的情况下才可能冲突。这一点在前面已经提到了。子节点的冲突处理很简单，分几种情况： 1) 在插入 wildcard 节点时，父节点的 children 数组非空且 wildChild 被设置为 false。例如：GET /user/getAll 和 GET /user/:id/getAddr，或者 GET /user/*aaa 和 GET /user/:id 。 2) 在插入 wildcard 节点时，父节点的 children 数组非空且 wildChild 被设置为 true，但该父节点的 wildcard 子节点要插入的 wildcard 名字不一样。例如：GET /user/:id/info 和 GET /user/:name/info。 3) 在插入 catchAll 节点时，父节点的 children 非空。例如：GET /src/abc 和 GET /src/*filename，或者 GET /src/:id 和 GET /src/*filename 。 4) 在插入 static 节点时，父节点的 wildChild 字段被设置为 true。 5) 在插入 static 节点时，父节点的 children 非空，且子节点 nType 为 catchAll。 只要发生冲突，都会在初始化的时候 panic。例如，在插入我们臆想的路由 GET /marketplace_listing/plans/ohyes 时，出现第 4 种冲突情况：它的父节点 marketplace_listing/plans/ 的 wildChild 字段为 true。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |