几个问题
在分析之前,带着问题去查找答案。
- 官方 http 包已经提供了server的功能,为什么要用框架?
路由注册
简单的程序
我们来看看 echo 的三种匹配模式和优先级顺序匹配,优先级从下到下:
- Static (固定路径) 类似于
/users/new
- Param (参数路径) 类似于
/users/:id
- Match any (匹配所有) 类似于
/users/1/files/*
看到这些模式,http 自带的路由只支持 固定路径 和 匹配所有的模式。这也是提高的地方。
我们来写个例子覆盖 echo 路由所支持的模式,
package main
import (
"fmt"
"net/http"
"time"
"github.com/labstack/echo"
)
func main() {
// Echo instance
e := echo.New()
// Routes
e.GET("/", index)
e.GET("/users/new", usersNew)
e.GET("/users/", users)
e.GET("/ups/", ups)
e.GET("/users/:name", usersName)
e.GET("/users/1/files/*", usersFiles)
addr := fmt.Sprintf("%s:%s", "localhost", "1323")
server := &http.Server{
Addr: addr,
ReadTimeout: 5 * time.Second,
WriteTimeout: 5 * time.Second,
}
// Start server
e.Logger.Fatal(e.StartServer(server))
}
func index(c echo.Context) error {
return c.String(http.StatusOK, "index~")
}
func usersNew(c echo.Context) error {
return c.String(http.StatusOK, "userNew!")
}
func ups(c echo.Context) error {
return c.String(http.StatusOK, "ups!")
}
func users(c echo.Context) error {
return c.String(http.StatusOK, "user!")
}
func usersName(c echo.Context) error {
name := c.Param("name")
return c.String(http.StatusOK, fmt.Sprintf("%s, %s", "hi", name))
}
func usersFiles(c echo.Context) error {
return c.String(http.StatusOK, "usersFiles!")
}
例子先放着,我们先往下看看路由结构。
路由结构
先来看看路由的结构,了解一下路由需要哪些信息。
type (
// Router 结构是`Echo`实例注册路由的地方。路由树
Router struct {
tree *node // 节点
routes map[string]*Route // map 形式,Route 包含请求handler 和 匹配信息
echo *Echo
}
// Route 包含请求的 handler 和 用于匹配的信息。
Route struct {
Method string `json:"method"`
Path string `json:"path"`
Name string `json:"name"`
}
// 节点结构
node struct {
kind kind // 路由类型skind 0(/echo/hi), pkind 1 (/users/:name), akind 2(/orders/*)
label byte // prefix的第一个字符,根据label和kind来查找子节点
prefix string // 前缀
parent *node // 父节点
children children // 子节点,列表
ppath string // 原始路径
pnames []string // 路径参数只有类型为 1(:后面的的字段), 2([*])才有,
methodHandler *methodHandler // 请求类型
}
kind uint8
children []*node
methodHandler struct {
connect HandlerFunc
delete HandlerFunc
get HandlerFunc
head HandlerFunc
options HandlerFunc
patch HandlerFunc
post HandlerFunc
propfind HandlerFunc
put HandlerFunc
trace HandlerFunc
}
)
Echo 的路由基于 radix tree ,它让路由的查询非常快,且使用 sync pool 来重复利用内存并且几乎达到了零内存占用。看路由的结构,跟字典树的结构一致,基数树就是字典树的一种优化结构。所以,通过请求来查找 handler 会比 http 提供的路由要快。在 http 的路由查找中是通过遍历方式的O(n),这里使用基数树O(K)的时间复杂度要好的多,同样比普通的Trie树的效率也要高。
路由绑定
以示例的代码,来看看是如何把路由信息装入到 Router 树的。
根据整个分析流程,我们先把整颗树还原成图像,这样更有利于了解。我们可以用广度优先搜索把树遍历出来。
// 广度层序打印节点
func (e *Echo) BfsShowRoute() {
bfsTree(e.router.tree)
}
func bfsTree(n *node) error {
var queue []*node
queue = append(queue, n)
for len(queue) > 0 {
queueLen := len(queue)
fmt.Println("----------------level----------------")
for i := queueLen; i > 0; i-- {
cn := queue[0]
parentPrefix := ""
if cn.parent != nil {
parentPrefix = cn.parent.prefix
}
fmt.Println("kind:", cn.kind, ",lable:", string(cn.label), ",prefix:", cn.prefix, ",ppath:", cn.ppath, ",pnames:", cn.pnames, ",handler:", runtime.FuncForPC(reflect.ValueOf(cn.methodHandler.get).Pointer()).Name(), ",parent->", parentPrefix)
if len(cn.children) > 0 {
queue = append(queue, cn.children...)
}
queue = queue[1:len(queue)]
}
}
return nil
}
在注册路由后,我们可以用上面的代码去遍历打印路由树,可以得到结果
----------------level----------------
kind: 0 ,lable: / ,prefix: / ,ppath: / ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent->
----------------level----------------
kind: 0 ,lable: u ,prefix: u ,ppath: ,pnames: [] ,handler: ,parent-> /
----------------level----------------
kind: 0 ,lable: s ,prefix: sers/ ,ppath: /users/ ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
kind: 0 ,lable: p ,prefix: ps/ ,ppath: /ups/ ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
----------------level----------------
kind: 0 ,lable: n ,prefix: new ,ppath: /users/new ,pnames: [] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> u
kind: 1 ,lable: : ,prefix: : ,ppath: /users/:name ,pnames: [name] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> sers/
kind: 0 ,lable: 1 ,prefix: 1/files/ ,ppath: ,pnames: [] ,handler: ,parent-> sers/
----------------level----------------
kind: 2 ,lable: * ,prefix: * ,ppath: /users/1/files/* ,pnames: [*] ,handler: github.com/labstack/echo.(*Echo).Add.func1 ,parent-> 1/files/
根据结果我们可以还原出,我们这颗路由树的图形,
了解了整个路由树的构造之后,我们来看看这颗树是怎么构建的。
// 注册三要素 方法类型,路由path,handler函数
func (r *Router) Add(method, path string, h HandlerFunc) {
// 校验是否空路径
if path == "" {
panic("echo: path cannot be empty")
}
// 规范路径
if path[0] != '/' {
path = "/" + path
}
pnames := []string{} // 路径参数
ppath := path // 原始路径
// 按字符挨个遍历
for i, l := 0, len(path); i < l; i++ {
// 参数路径
if path[i] == ':' {
j := i + 1
r.insert(method, path[:i], nil, skind, "", nil)
// 找到参数路径的参数
for ; i < l && path[i] != '/'; i++ {
}
// 把参数路径存入 pnames
pnames = append(pnames, path[j:i])
// 拼接路径 继续查找是否还有 参数路径
path = path[:j] + path[i:]
i, l = j, len(path)
// 已经结束 插入参数路径节点
if i == l {
r.insert(method, path[:i], h, pkind, ppath, pnames)
return
}
r.insert(method, path[:i], nil, pkind, "", nil)
// 全量路径
} else if path[i] == '*' {
r.insert(method, path[:i], nil, skind, "", nil)
// 全量参数都是"*"
pnames = append(pnames, "*")
r.insert(method, path[:i+1], h, akind, ppath, pnames)
return
}
}
// 普通路径
r.insert(method, path, h, skind, ppath, pnames)
}
// 核心函数,构建字典树
func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string, pnames []string) {
// 调整最大参数
l := len(pnames)
if *r.echo.maxParam < l {
*r.echo.maxParam = l
}
cn := r.tree // 当前节点 root
if cn == nil {
panic("echo: invalid method")
}
search := path
for {
sl := len(search)
pl := len(cn.prefix)
l := 0
// LCP
max := pl
if sl < max {
max = sl
}
// 找到共同前缀的位置 例如 users/ 和 users/new 的共同前缀为 users/
for ; l < max && search[l] == cn.prefix[l]; l++ {
}
if l == 0 {
// root 节点处理
cn.label = search[0]
cn.prefix = search
if h != nil {
cn.kind = t
cn.addHandler(method, h)
cn.ppath = ppath
cn.pnames = pnames
}
} else if l < pl {
// 分离共同前缀 users/ 和 users/new 创建一个 prefix为new 的节点
n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames)
// 重置父节点 prefix 为 users
cn.kind = skind
cn.label = cn.prefix[0]
cn.prefix = cn.prefix[:l]
// 清空该节点的孩子节点
cn.children = nil
cn.methodHandler = new(methodHandler)
cn.ppath = ""
cn.pnames = nil
// 给该节点加上 prefix 为new的节点
cn.addChild(n)
if l == sl {
// 如果是
cn.kind = t
cn.addHandler(method, h)
cn.ppath = ppath
cn.pnames = pnames
} else {
// 创建子节点
n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames)
n.addHandler(method, h)
cn.addChild(n)
}
} else if l < sl {
search = search[l:]
// 找到 lable 一样的节点,用 lable 来判断共同前缀
c := cn.findChildWithLabel(search[0])
if c != nil {
// 找到共同节点 继续
cn = c
continue
}
// 创建子节点
n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames)
n.addHandler(method, h)
cn.addChild(n)
} else {
// 节点已存在
if h != nil {
cn.addHandler(method, h)
cn.ppath = ppath
if len(cn.pnames) == 0 { // Issue #729
cn.pnames = pnames
}
}
}
return
}
}
从上面来看,整个节点是根据新增的路由不断调整而生成的radix tree。了解了整个结构之后,再来看看如何查找路由的handler。
请求如何匹配上 handler
回顾之前的 http server 的代码,
serverHandler{c.server}.ServeHTTP(w, w.req)
通过这个函数我们知道,其实是调用ServeHTTP 接口来具体处理请求。
echo.go
// ServeHTTP 实现了 `http.Handler` 接口, 该接口用来处理请求
func (e *Echo) ServeHTTP(w http.ResponseWriter, r *http.Request) {
// 获取 context,这里为啥用pool实现?据文档说是为了节省内存
c := e.pool.Get().(*context)
c.Reset(r, w)
h := NotFoundHandler
// 没有请求前需要调用的 http 中间件
if e.premiddleware == nil {
// 查找 handler的方法
e.router.Find(r.Method, getPath(r), c)
h = c.Handler()
h = applyMiddleware(h, e.middleware...)
} else {
h = func(c Context) error {
e.router.Find(r.Method, getPath(r), c)
h := c.Handler()
h = applyMiddleware(h, e.middleware...)
return h(c)
}
h = applyMiddleware(h, e.premiddleware...)
}
// 执行处理逻辑
if err := h(c); err != nil {
e.HTTPErrorHandler(err, c)
}
// 释放 context
e.pool.Put(c)
}
// 通过 method 和 path 查找注册的 handler,解析 URL 参数并把参数装进 context
func (r *Router) Find(method, path string, c Context) {
ctx := c.(*context)
ctx.path = path
fmt.Println(ctx.path, ctx.query, ctx.pvalues, method, path, "ctx....")
cn := r.tree // 当前节点
var (
search = path
child *node // 子节点
n int // 参数计数器
nk kind // 下一个节点的 Kind
nn *node // 下一个节点
ns string // 下一个 search 字符串
pvalues = ctx.pvalues
)
// 搜索顺序 static > param > any
for {
if search == "" {
break
}
pl := 0 // Prefix length
l := 0 // LCP length
if cn.label != ':' {
sl := len(search)
pl = len(cn.prefix)
// LCP
max := pl
if sl < max {
max = sl
}
// 找到共同前缀的起始点
for ; l < max && search[l] == cn.prefix[l]; l++ {
}
}
if l == pl {
// 重合 继续搜索
search = search[l:]
} else {
cn = nn
search = ns
if nk == pkind {
goto Param
} else if nk == akind {
goto Any
}
// 没有找到子节点 直接返回
return
}
if search == "" {
break
}
// Static 节点
if child = cn.findChild(search[0], skind); child != nil {
// Save next
if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
nk = pkind
nn = cn
ns = search
}
cn = child
continue
}
// Param 节点
Param:
if child = cn.findChildByKind(pkind); child != nil {
// Issue #378
if len(pvalues) == n {
continue
}
// Save next
if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
nk = akind
nn = cn
ns = search
}
cn = child
i, l := 0, len(search)
for ; i < l && search[i] != '/'; i++ {
}
pvalues[n] = search[:i]
n++
search = search[i:]
continue
}
// Any 节点
Any:
if cn = cn.findChildByKind(akind); cn == nil {
if nn != nil {
cn = nn
nn = cn.parent // Next (Issue #954)
search = ns
if nk == pkind {
goto Param
} else if nk == akind {
goto Any
}
}
// Not found
return
}
pvalues[len(cn.pnames)-1] = search
break
}
ctx.handler = cn.findHandler(method)
ctx.path = cn.ppath
ctx.pnames = cn.pnames
// NOTE: Slow zone...
if ctx.handler == nil {
ctx.handler = cn.checkMethodNotAllowed()
// Dig further for any, might have an empty value for *, e.g.
// serving a directory. Issue #207.
if cn = cn.findChildByKind(akind); cn == nil {
return
}
if h := cn.findHandler(method); h != nil {
ctx.handler = h
} else {
ctx.handler = cn.checkMethodNotAllowed()
}
ctx.path = cn.ppath
ctx.pnames = cn.pnames
pvalues[len(cn.pnames)-1] = ""
}
return
整个过程可以通过把路由树画出来,然后一个一个case去跑下来,可以理解整个构建和查找的过程。
再回过头来看看之前的问题
- 官方 http 包已经提供了server的功能,为什么要用框架?
从echo这个框架的角度来说,提供了支持更多类型以及效率更高的路由,路由分组,http中间件,更优化的内存使用,请求参数上下文处理等等。从性能和功能的角度都极大的提升了开发效率。
有疑问加站长微信联系(非本文作者)