GIN框架路由的实现原理

首先回顾一下gin框架的路由如何使用的

package mainimport ("fmt""github.com/gin-gonic/gin""net/http"
)func main() {//创建一个gin Engine ,Engine实现了net/http包下Handler接口，本质上是一个http Handlerr := gin.Default()//注册中间件r.Use(middleware1)r.Use(middleware2)//注册一个path为/hello的处理函数，将/hello域名下的get请求路由到后面的handler函数来处理r.GET("/hello", handler)r.Run()}
func middleware1(c *gin.Context) {fmt.Println("Executing middleware1")c.Next() //将控制权传递给下一个中间件或者处理函数//c.Abort() //在请求处理过程中发现错误或异常情况时，立即终止处理并返回错误信息，后续的处理程序或者中间件不在执行//Executing middleware1//middle1 endfmt.Println("middle1 end")
}func middleware2(c *gin.Context) {fmt.Println("Executing middleware2")c.Next()fmt.Println("middle2 end")
}func handler(c *gin.Context) {fmt.Println("Executing handler")fmt.Println("handler end")c.JSON(http.StatusOK, gin.H{"message": "hello word"})}/*
Executing middleware1
Executing middleware2
Executing handler
handler end
middle2 end
middle1 end*/

运行程序
在浏览器输入“http://127.0.0.1:8080/hello”可以看到

http的请求有9种，GET\HEAD\POST\PUT\PATCH\DELETE\CONNECT\OPTIONS\TRACE

从源码分析一下gin框架

首先通过“gin.Default()”创建一个Engine实例并附带有“Logger\Recovery”中间件

// Default returns an Engine instance with the Logger and Recovery middleware already attached.
func Default() *Engine {debugPrintWARNINGDefault()engine := New()engine.Use(Logger(), Recovery())return engine
}

Default()实际上是调用了New()，并使用use注册“Logger\Recovery”两个中间件

func New() *Engine {debugPrintWARNINGNew()engine := &Engine{RouterGroup: RouterGroup{Handlers: nil,basePath: "/",root:     true,},FuncMap:                template.FuncMap{},RedirectTrailingSlash:  true,RedirectFixedPath:      false,HandleMethodNotAllowed: false,ForwardedByClientIP:    true,RemoteIPHeaders:        []string{"X-Forwarded-For", "X-Real-IP"},TrustedPlatform:        defaultPlatform,UseRawPath:             false,RemoveExtraSlash:       false,UnescapePathValues:     true,MaxMultipartMemory:     defaultMultipartMemory,trees:                  make(methodTrees, 0, 9),delims:                 render.Delims{Left: "{{", Right: "}}"},secureJSONPrefix:       "while(1);",trustedProxies:         []string{"0.0.0.0/0", "::/0"},trustedCIDRs:           defaultTrustedCIDRs,}engine.RouterGroup.engine = engineengine.pool.New = func() any {return engine.allocateContext(engine.maxParams)}return engine
}

New()函数初始化Engine实例并返回，接下来看一下Engine struct都有些什么

type Engine struct {RouterGroup// RedirectTrailingSlash enables automatic redirection if the current route can't be matched but a// handler for the path with (without) the trailing slash exists.// For example if /foo/ is requested but a route only exists for /foo, the// client is redirected to /foo with http status code 301 for GET requests// and 307 for all other request methods.RedirectTrailingSlash bool// RedirectFixedPath if enabled, the router tries to fix the current request path, if no// handle is registered for it.// First superfluous path elements like ../ or // are removed.// Afterwards the router does a case-insensitive lookup of the cleaned path.// If a handle can be found for this route, the router makes a redirection// to the corrected path with status code 301 for GET requests and 307 for// all other request methods.// For example /FOO and /..//Foo could be redirected to /foo.// RedirectTrailingSlash is independent of this option.RedirectFixedPath bool// HandleMethodNotAllowed if enabled, the router checks if another method is allowed for the// current route, if the current request can not be routed.// If this is the case, the request is answered with 'Method Not Allowed'// and HTTP status code 405.// If no other Method is allowed, the request is delegated to the NotFound// handler.HandleMethodNotAllowed bool// ForwardedByClientIP if enabled, client IP will be parsed from the request's headers that// match those stored at `(*gin.Engine).RemoteIPHeaders`. If no IP was// fetched, it falls back to the IP obtained from// `(*gin.Context).Request.RemoteAddr`.ForwardedByClientIP bool// AppEngine was deprecated.// Deprecated: USE `TrustedPlatform` WITH VALUE `gin.PlatformGoogleAppEngine` INSTEAD// #726 #755 If enabled, it will trust some headers starting with// 'X-AppEngine...' for better integration with that PaaS.AppEngine bool// UseRawPath if enabled, the url.RawPath will be used to find parameters.UseRawPath bool// UnescapePathValues if true, the path value will be unescaped.// If UseRawPath is false (by default), the UnescapePathValues effectively is true,// as url.Path gonna be used, which is already unescaped.UnescapePathValues bool// RemoveExtraSlash a parameter can be parsed from the URL even with extra slashes.// See the PR #1817 and issue #1644RemoveExtraSlash bool// RemoteIPHeaders list of headers used to obtain the client IP when// `(*gin.Engine).ForwardedByClientIP` is `true` and// `(*gin.Context).Request.RemoteAddr` is matched by at least one of the// network origins of list defined by `(*gin.Engine).SetTrustedProxies()`.RemoteIPHeaders []string// TrustedPlatform if set to a constant of value gin.Platform*, trusts the headers set by// that platform, for example to determine the client IPTrustedPlatform string// MaxMultipartMemory value of 'maxMemory' param that is given to http.Request's ParseMultipartForm// method call.MaxMultipartMemory int64// UseH2C enable h2c support.UseH2C bool// ContextWithFallback enable fallback Context.Deadline(), Context.Done(), Context.Err() and Context.Value() when Context.Request.Context() is not nil.ContextWithFallback booldelims           render.DelimssecureJSONPrefix stringHTMLRender       render.HTMLRenderFuncMap          template.FuncMapallNoRoute       HandlersChainallNoMethod      HandlersChainnoRoute          HandlersChainnoMethod         HandlersChainpool             sync.Pooltrees            methodTreesmaxParams        uint16maxSections      uint16trustedProxies   []stringtrustedCIDRs     []*net.IPNet
}

从结构体中发现，Engine有一个“sync.Pool”类型的pool变量：
sync.Pool是sync包下的一个内存池组件用来实现对象的复用，避免重复创建相同的对象，造成频繁的内存分配和gc，以达到提升程序性能的目的，虽然池子中的对象可以被复用，
但是sync.Pool并不会永久保存这个对象，池子中的对象会在一定时间后被gc回收，这个时间是随机的。所以用sync.Pool持久化存储对象不可取
sync.Pool本身是线程安全的，支持多个goroutine并发的往sync.Pool存取数据

sync.Pool的使用例子

package main
import ("fmt""sync"
)type Student struct {Name stringAge  int
}func main() {pool := sync.Pool{New: func() interface{} {return &Student{Name: "zhangsan",Age:  23,}},}st := pool.Get().(*Student)fmt.Println(st.Age, st.Name)fmt.Printf("%p\n", &st)pool.Put(st)st = pool.Get().(*Student)fmt.Println(st.Age, st.Name)fmt.Printf("%p\n", &st)}
//23 zhangsan
//0xc00000a028
//23 zhangsan 
//0xc00000a028

Engine结构RouterGroup结构体，接下来看一下“RouterGroup”结构体

type RouterGroup struct {//HandlersChain defines a HandlerFunc slice//HandlerFunc defines the handler used by gin middleware as return valueHandlers HandlersChainbasePath stringengine   *Engineroot     bool
}

Engine中还有一个“methodTrees”类型的变量trees

trees            methodTrees
type methodTrees []methodTree
type methodTree struct{method stringroot *node
}
type node struct {path      stringindices   stringwildChild boolnType     nodeTypepriority  uint32children  []*node // child nodes, at most 1 :param style node at the end of the arrayhandlers  HandlersChainfullPath  string
}

node 中最重要的两个结构就是

type node struct{wildChild boolchildren []*node
}
//其实这个就是前缀树实现的比较重要的两个数据变量

gin的路由实现

gin的每种请求，都是一个域名对应着一个路由处理函数，就是一种映射关系；直观上可以使用map存储这种映射关系，key存储域名，value存储域名对应的处理函数；
但实际上，gin路由底层实现这个映射使用的是压缩前缀树，首先介绍一下前缀树

前缀树

前缀树就是trie树，是一种树形结构，用于高效地存储和检索字符串集合。基本思想就是将字符串中的每个字符作为树的一个节点，从根节点开始，每个节点代表代表字符串中的一个前缀。在Trie树，每个节点都包含一个指向子节点的指针数组，数组的大小等于字符集的大小。如果某个节点代表的字符串是一个单词的结尾，可以在该节点上做一个标记。
以下是前缀树的一些特性：

• 前缀匹配。前缀树可以高效地实现前缀匹配。给定一个前缀，可以在O(k)的时间复杂度内找到所有以该前缀开头的字符串，k是前缀的长度
• 高效存储和检索。前缀树可以高效地存储和检索字符串集合。在插入和查找字符串时，时间复杂度为O(k)，k是字符串的长度。相比于哈希表和二叉搜索树，前缀树在字符串存储和检索方面具有更好的性能
• 消耗较大的空间。空间复杂度较高，每个节点都需要存储指向子节点的指针数组，节点的数量可能会非常多。空间复杂度为O(n*m)其中n为字符串集合中字符串的平均长度，m为字符串数量
• 支持删除操作。删除操作相对比较复杂，删除一个字符串需要同时删除相应的节点，需要处理节点合并的情况。
• 应用场景。单词查询，自动补全，模糊匹配

前缀树的实现

前缀树的实现可以参考力扣上的一道代码题
题目链接
大致的思路就是

go 语言实现

type Trie struct {trie [26]*Trieflag bool
}func Constructor() Trie {return Trie{}
}func (this *Trie) Insert(word string)  {tr:= thisfor i:=0;i<len(word);i++{if tr.trie[word[i]-'a']==nil{tr.trie[word[i]-'a'] = &Trie{}}tr=tr.trie[word[i]-'a']}tr.flag=true
}func (this *Trie) Search(word string) bool {tr:=this.startpre(word)return tr!=nil && tr.flag
}func (this *Trie) StartsWith(prefix string) bool {return this.startpre(prefix)!=nil
}
func (this *Trie)startpre(pre string)*Trie{tr:=this    for i:=0;i<len(pre);i++{if tr.trie[pre[i]-'a']==nil{return nil}tr=tr.trie[pre[i]-'a']}return tr
}/*** Your Trie object will be instantiated and called as such:* obj := Constructor();* obj.Insert(word);* param_2 := obj.Search(word);* param_3 := obj.StartsWith(prefix);*/

C++实现版本，由于C++没有回收内存的机制所以需要手动释放内存

class Trie {
public:~Trie(){//析构函数释放内存del(this);}Trie():trie(26),flag(false){}void insert(string word) {Trie *tr = this;for(const char&c:word){if(!tr->trie[c-'a']) tr->trie[c-'a'] = new Trie();tr=tr->trie[c-'a'];}tr->flag=true;}bool search(string word) {Trie *tr = this;for(const char&c:word){if(!tr->trie[c-'a']) return false;tr=tr->trie[c-'a'];}return tr->flag;}bool startsWith(string prefix) {Trie *tr = this;for(const char&c:prefix){if(!tr->trie[c-'a']) return false;tr=tr->trie[c-'a'];}return true;}
private:vector<Trie*> trie;bool flag;
private:void del(Trie *tr){for(int i=0;i<26;++i){delete(tr->trie[i]);tr->trie[i]=nullptr;}}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

解释一下其中的关键代码，del

	void del(Trie *tr){//由于每个Trie节点都有一个长度为26的指向子节点的指针数组，所以写了一个长度为26的for循环for(int i=0;i<26;++i){//由于tr->trie[i]是一个Trie的数据类型变量，所以在delete tr->trie[i]的时候会触发tr-trie[i]的析构函数，往下递归的进行内存释放delete(tr->trie[i]);//释放完之后为了防止野指针，将tr->trie[i]设置为nullptrtr->trie[i]=nullptr;}}

压缩前缀树–Radix Trie

从上述的分析和代码实现可以看出，前缀树占用的空间特别大。那么为了优化空间的利用率，gin的路由采用了“压缩前缀树”。

使用如下方法进行压缩：

• 合并相邻的只有一个子节点的节点：遍历前缀树，当发现一个节点只有一个子节点时，将该节点与其子节点合并。合并时，将子节点的字符添加到父节点的字符中，形成新的字符
• 递归地压缩子树，在合并节点后，可能会出现新的节点也只有一个子节点的情况，可以递归的对子树进行压缩，直到无法压缩为止
• 使用特殊字符表示合并，为了在压缩前缀树中表示节点的合并，可以使用一些特殊的字符进行标记。例如可以使用$表示节点的合并

接下来，利用数据结构可视化工具查看两个结构的不同
依次插入[“apple”,“apricot”,“banana”,“bat”]

前缀树的结构如下

压缩前缀树的结构如下

从两图可以看出,Radix Trie对Trie进行了压缩：遍历Trie发现某个节点只有一个子节点，就与子节点进行合并，减少指针数组的占用，优化空间

Trie VS Map

接下来说一下为什么不用map实现路径和路由函数之间的映射。

• map并不支持模糊匹配和参数提取；前缀树可以根据前缀进行参数提取，而使用map进行参数提取需要额外的步骤
• 前缀树可以根据前缀进行分组管理，而map不行