14｜Gin 框架相关

Golang面试题库 - 这篇文章属于一个选集。

§ 14: 本文

1. Gin 框架的路由实现原理？
#

分析：

首先来回顾一下 Gin 框架的路由是怎么用的，下面代码介绍 post 请求的路由使用方式：

func main() {
    // 创建一个 gin Engine，Engine 实现了 net/http 包下 Handler 接口，本质上是一个 http Handler
    r := gin.Default()
    // 注册中间件
    r.Use(myMiddleWare)
    // 注册一个 path 为 /ping 的处理函数，将 /ping 域名下的 post 请求路由到后面这个 func 来处理
    r.POST("/ping", func(c *gin.Context) {
        c.JSON(http.StatusOK, "pone")
    })
    // ...
}

HTTP 的请求有 9 种：GET、HEAD、POST、PUT、PATCH、DELETE、CONNECT、OPTIONS、TRACE。

所以这里 Gin Engine 其实有 9 种请求，但是每种请求的路由使用逻辑其实差不多，都是对应于后面跟一个 handler 处理函数，用来处理这个域名下的对应请求。

从这里就可以看出一个域名对应着一个处理 handler，有一个映射关系，这就是路由。那么这种映射关系在 Gin 的底层是怎么实现的呢？直观感受是可以用 map，key 是域名，value 是这个域名对应的 handler。HTTP 有 9 种请求，那么建立 9 个这样的 map 就行了。

Gin 框架在底层实现这个映射用的并不是 map，而是用的压缩前缀树这种数据结构。至于为什么不用 map，后面分析。

什么是前缀树？
#

前缀树即 trie 树，是一种基于字符串公共前缀构建索引的多叉树，前缀树主要有以下特性：

除根节点之外，每个节点对应一个字符串。
从根节点到某一节点，路径上经过的字符串联起来，即为该节点对应的字符串。
尽可能复用公共前缀，如无必要不分配新的节点。

假设现在有 /user/info、/user/rank、/see、/search/v1、/search/v2 等字符串，则可以构建出一棵前缀树：

压缩前缀树
#

压缩前缀树又称基数树或 radix 树，是对前缀树的改良版本。优化点主要在于空间的节省，核心策略体现在：倘若某个子节点是其父节点的唯一孩子，则与父节点进行合并。

在 Gin 框架中，使用的正是压缩前缀树的数据结构。

树节点
#

树的每个结点的数据结构如下：

type node struct {
    path      string        // 节点的相对路径
    indices   string        // 每个 indice 字符对应一个孩子节点的 path 首字母
    priority  uint32        // 后继节点数量
    children  []*node       // 孩子节点列表
    handlers  HandlersChain // 处理函数链
    fullPath  string        // path 拼接上前缀后的完整路径
}