Gin is a web framework written in Go. It features a martini-like API with performance that is up to 40 times faster thanks to httprouter. If you need performance and good productivity, you will love Gin.
Gin's key features are:
Zero allocation router
Speed
Middleware support
Crash-free
JSON validation
Route grouping
Error management
Built-in rendering
Extensible
路由特性
:路由和*路由
query查询参数
接收数组和 Map
Form 表单
单文件和多文件上传
分组路由，以及路由嵌套
路由中间件
各种数据格式的支持，json、struct、xml、yaml、protobuf
HTML模板渲染
url重定向
异步协程等等
什么是路由
根据路由里的
/把路由切分成多个字符串数组然后按照相同的前子数组把路由构造成树的结构
/api/v1/sts/storage-record/
/api/v1/sts/storage-record-part/定义路由，正常情况下会定义出3节点路由树，根节点/api/v1/sts/，和2个子节点/api/v1/sts/storage-record/，/api/v1/sts/storage-record-part/
时间复杂度为O(2n)
前缀树路由算法
前缀树算法
为了提高路由效率，缩短路由时间：只需遍历一遍字符串即可，时间复杂度为O(n)
Trie树：字典树或者前缀树，多叉树结构
以下是一个简单的前缀树示意图:
root
/ \
t a
/ \
h n
/ \
e s
| |
r w
| |
ing er对于字符串集合 {"ing", "er", "ans", "and"}:
每个节点不是用于存储完整单词,而是仅作为一个标记,指向孩子节点
只有当从根节点到达一个节点经过的一系列边组合起来正好是一个单词,这个节点才有'终止'标记
路由注册过程就是在前缀树中添加新节点的过程。注册
/book/fetch路径就是在前缀树中添加一条root->b->o->o->k->fetch的路径路由匹配过程就是在前缀树中从根节点开始搜索满足条件的节点的过程。比如请求路径
/book/fetch/123时,就从根节点开始,一直匹配到fetch节点,然后进一步匹配处理前缀树的有序性质,对路由按照从长到短进行排序。这样在执行查找时,可以优先命中较长的路由路径
模型示例
节点类型(nType):
static: 静态路径节点,表示路径中的普通字符部分param: 参数路径节点,表示路径中的参数部分,以":"开头catchAll: 通配符节点,表示路径中的通配符部分,以"*"开头
path: 当前节点所表示的路径部分
children: 当前节点的子节点列表,用于存储下一级路径节点
indices: 一个字符串,存储当前节点的子节点索引,用于快速查找子节点
handlers: 存储当前节点关联的处理程序链(HandlersChain)
业务示例
gin的路由树算法类似于一棵前缀树. 不过并不是只有一颗树, 而是每种方法(POST, GET ，PATCH...)都有自己的一颗树
源码解析
// 数据节点，https://github.com/gin-gonic/gin/blob/master/tree.go
type node struct {
path string
indices string
wildChild bool
nType nodeType
priority uint32
children []*node // child nodes, at most 1 :param style node at the end of the array
handlers HandlersChain
fullPath string
}
// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handlers HandlersChain) {
fullPath := path
n.priority++
// Empty tree
if len(n.path) == 0 && len(n.children) == 0 {
n.insertChild(path, fullPath, handlers)
n.nType = root
return
}
parentFullPathIndex := 0
walk:
for {
// Find the longest common prefix.
// This also implies that the common prefix contains no ':' or '*'
// since the existing key can't contain those chars.
i := longestCommonPrefix(path, n.path)
// Split edge
if i < len(n.path) {
child := node{
path: n.path[i:],
wildChild: n.wildChild,
nType: static,
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1,
fullPath: n.fullPath,
}
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = bytesconv.BytesToString([]byte{n.path[i]})
n.path = path[:i]
n.handlers = nil
n.wildChild = false
n.fullPath = fullPath[:parentFullPathIndex+i]
}
// Make new node a child of this node
if i < len(path) {
path = path[i:]
c := path[0]
// '/' after param
if n.nType == param && c == '/' && len(n.children) == 1 {
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
continue walk
}
// Check if a child with the next path byte exists
for i, max_ := 0, len(n.indices); i < max_; i++ {
if c == n.indices[i] {
parentFullPathIndex += len(n.path)
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// Otherwise insert it
if c != ':' && c != '*' && n.nType != catchAll {
// []byte for proper unicode char conversion, see #65
n.indices += bytesconv.BytesToString([]byte{c})
child := &node{
fullPath: fullPath,
}
n.addChild(child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
} else if n.wildChild {
// inserting a wildcard node, need to check if it conflicts with the existing wildcard
n = n.children[len(n.children)-1]
n.priority++
// 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
}
// Wildcard conflict
pathSeg := path
if n.nType != catchAll {
pathSeg = strings.SplitN(pathSeg, "/", 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 +
"'")
}
n.insertChild(path, fullPath, handlers)
return
}
// Otherwise add handle to current node
if n.handlers != nil {
panic("handlers are already registered for path '" + fullPath + "'")
}
n.handlers = handlers
n.fullPath = fullPath
return
}
}定义了一个 addRoute 方法,接收一个要添加的路由路径 path 和相应的处理程序链 handlers。
该方法的主要工作流程如下:
如果当前节点为空树,则直接将该路由作为根节点插入。
否则,进入循环,寻找当前节点
n和新路径path的最长公共前缀。如果公共前缀长度小于当前节点路径长度,则需要分裂当前节点:
创建一个新节点
child,将当前节点剩余部分的路径、通配符信息、子节点和处理程序等数据放入child中。将当前节点
n的路径缩短为公共前缀部分,并将child作为子节点。
如果公共前缀长度小于新路径长度,则需要根据新路径剩余部分继续在子节点中插入:
如果当前节点是参数节点,且新路径下一个字符是斜杠,则直接移动到唯一子节点继续处理。
否则,在当前节点的子节点列表中查找与新路径下一个字符相同的子节点,如果找到则移动到该子节点继续处理。
如果没有找到匹配的子节点,且新路径中下一个字符不是通配符,则创建一个新的子节点,并将其插入到当前节点的子节点列表中。
如果新路径中下一个字符是通配符,且当前节点已经有通配符子节点,则需要检查是否与现有的通配符子节点冲突。如果冲突,则抛出异常。
如果新路径已经完全插入到树中,则将处理程序链
handlers附加到当前节点。如果当前节点已经有处理程序,则抛出异常(因为不允许重复注册相同路径)。
// HandlersChain is a slice of Handlers that can be safely shared between multiple goroutines.
type HandlersChain []HandlerFunc
// HandlerFunc is a request handler function
type HandlerFunc func(*Context)handlers 是一个 HandlersChain 类型的值,表示与一个特定路由关联的一系列处理程序(handler)函数。
HandlersChain 是一个处理程序链的切片(slice)
每个 HandlerFunc 是一个请求处理函数,接收一个 *Context 参数,表示当前请求的上下文信息。在处理一个请求时,Gin 会依次执行该路由关联的所有 HandlerFunc。
例如,注册一个 GET 请求的路由及其处理程序:
r := gin.Default()
r.GET("/ping", func(c *gin.Context) {
c.JSON(200, gin.H{
"message": "pong",
})
})在这个例子中, handlers 只包含一个匿名函数 func(c *gin.Context) {...}。
定义多个中间件处理程序,并组合在一起:
func Logger() gin.HandlerFunc {
// 实现日志中间件的逻辑...
}
func Authentication() gin.HandlerFunc {
// 实现身份验证中间件的逻辑...
}
r.GET("/secure", Logger(), Authentication(), func(c *gin.Context) {
// 处理已通过日志和身份验证中间件的请求
})在这种情况下, handlers 包含了 Logger、Authentication 和最终的请求处理程序。Gin 会按照定义的顺序依次执行它们。
handlers 本质上是一系列关联到特定路由的处理程序函数,用于处理传入的 HTTP 请求。通过有序地执行这些处理程序,可以实现日志记录、身份验证、请求预处理等各种中间件功能,以及最终的业务逻辑处理。
每一种注册方式，最终都会反应在gin的路由树上
普通路由注册
普通注册路由的方式是 router.xxx，可以是如下方式
GET
POST
PATCH
PUT
...
func CreateWorkOrder(c *gin.Context) {
}
// 普通注册
router.POST("/hi", func(context *gin.Context) {
context.String(http.StatusOK, "hi xiaomotong")
})
// 分组注册
func setupWorkOrderRouter(group *gin.RouterGroup) {
workOrders := group.Group("/work-order")
{
// 工单管理
workOrders.POST("/", controller.CreateWorkOrder)
}
}实际上在调用post等方法的时候，会调用handle函数
// POST is a shortcut for router.Handle("POST", path, handlers).
func (group *RouterGroup) POST(relativePath string, handlers ...HandlerFunc) IRoutes {
return group.handle(http.MethodPost, relativePath, handlers)
}
func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
absolutePath := group.calculateAbsolutePath(relativePath)
handlers = group.combineHandlers(handlers)
group.engine.addRoute(httpMethod, absolutePath, handlers)
return group.returnObj()
}addRoute就注册到路由树里
combineHandlers和calculateAbsolutePath如下：
func (group *RouterGroup) combineHandlers(handlers HandlersChain) HandlersChain {
finalSize := len(group.Handlers) + len(handlers)
if finalSize >= int(abortIndex) {
panic("too many handlers")
}
mergedHandlers := make(HandlersChain, finalSize)
copy(mergedHandlers, group.Handlers)
copy(mergedHandlers[len(group.Handlers):], handlers)
return mergedHandlers
}将一组中间件处理程序(group.Handlers)和一组路由处理程序(handlers)合并成一个新的处理程序链(HandlersChain)
finalSize := len(group.Handlers) + len(handlers)计算出合并后的处理程序链的总长度。if finalSize >= int(abortIndex) { panic("too many handlers") }这里检查合并后的处理程序链是否超过了最大长度限制(abortIndex)。如果超过,就会触发 panic。abortIndex是一个预定义的常量,用于标记处理程序链的结束位置,其值为math.MaxInt8 / 2。这个限制是为了防止处理程序链过长,导致性能下降或内存溢出。mergedHandlers := make(HandlersChain, finalSize)创建一个新的HandlersChain切片,长度为finalSize。copy(mergedHandlers, group.Handlers)将group.Handlers中的所有处理程序复制到mergedHandlers中。copy(mergedHandlers[len(group.Handlers):], handlers)将handlers中的所有处理程序复制到mergedHandlers的剩余部分。return mergedHandlers返回合并后的处理程序链mergedHandlers。
合并后程序执行顺序是:
首先执行
group.Handlers中的中间件处理程序;然后执行
handlers中的路由处理程序
允许在组级别定义中间件处理程序,并将它们应用于该组下的所有路由。同时,每个路由还可以指定自己特定的处理程序
对于同一个路由,中间件和路由处理程序的总数是有限制的。如果超过这个限制,就会导致 panic。这是出于性能和内存的考虑,防止处理程序链过长。
func (group *RouterGroup) calculateAbsolutePath(relativePath string) string {
return joinPaths(group.basePath, relativePath)
}
func joinPaths(absolutePath, relativePath string) string {
if relativePath == "" {
return absolutePath
}
finalPath := path.Join(absolutePath, relativePath)
appendSlash := lastChar(relativePath) == '/' && lastChar(finalPath) != '/'
if appendSlash {
return finalPath + "/"
}
return finalPath
}有一个路由组的基础路径为 /api/v1，然后在该路由组中注册一个相对路径为 /users/，那么通过 calculateAbsolutePath 方法计算出的绝对路径就会是 /api/v1/users/
中间件路由
// 初始化工单处理路由
func setupStorageRecordPartRouter(group *gin.RouterGroup) {
storageRecordPart := group.Group("/storage-record-part")
{
// 处理工单
storageRecordPart.Use(Limit.RequestSizeLimiter(2 << 20))
storageRecordPart.POST("/", controller.CreateStorageRecordPart)
storageRecordPart.POST("/merge/", controller.MergeStorageRecordPart)
}
}func (group *RouterGroup) Use(middleware ...HandlerFunc) IRoutes {
group.Handlers = append(group.Handlers, middleware...)
return group.returnObj()
}
handler方法 调用 calculateAbsolutePath 和 combineHandlers 将路由拼接好之后，调用addRoute方法，将路由预处理的结果注册到gin Engine的trees上
评论区