钉钉事件订阅前缀树算法gin框架解析

当钉钉监测到发生一些事件，如下图

此处举例三个事件user_add_org、user_change_org、user_leave_org，传统的做法是，我们写三个if条件，类似下图

 这样字符串匹配效率比较低，于是联想到gin框架中的路由匹配算法，可以借鉴模仿gin框架的实现方式。 

用实际需求驱动开发，掌握知识的同时还能应用知识，理解得会更加深入。

gin框架源代码解析

gin框架根据路由字符串建树

无论是POST、还是GET底层都是下方代码

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)// 把这个新的handlefunc和之前的handlefunc（比如说中间件中的）加在一起handlers = group.combineHandlers(handlers)// 给这个POST请求去建树group.engine.addRoute(httpMethod, absolutePath, handlers)return group.returnObj()
}func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {assert1(path[0] == '/', "path must begin with '/'")assert1(method != "", "HTTP method can not be empty")assert1(len(handlers) > 0, "there must be at least one handler")debugPrintRoute(method, path, handlers)# 取出POST方法的树root := engine.trees.get(method)if root == nil {root = new(node)root.fullPath = "/"engine.trees = append(engine.trees, methodTree{method: method, root: root})}# 具体去建树root.addRoute(path, handlers)
}

树的节点结构如下：

type node struct {path      stringindices   stringwildChild boolnType     nodeTypepriority  uint32children  []*node // child nodes, at most 1 :param style node at the end of the arrayhandlers  HandlersChain // 此处就是对应路径要执行的HandleFuncfullPath  string
}type HandlersChain []HandlerFunctype HandlerFunc func(*Context)

gin框架在请求到来时具体查树执行逻辑

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {c := engine.pool.Get().(*Context) // 取出一个context对象c.writermem.reset(w)c.Request = reqc.reset()// 关键处理函数engine.handleHTTPRequest(c)engine.pool.Put(c)
}func (engine *Engine) handleHTTPRequest(c *Context) {httpMethod := c.Request.MethodrPath := c.Request.URL.Pathunescape := falseif engine.UseRawPath && len(c.Request.URL.RawPath) > 0 {rPath = c.Request.URL.RawPathunescape = engine.UnescapePathValues}if engine.RemoveExtraSlash {rPath = cleanPath(rPath)}// Find root of the tree for the given HTTP method// 找到对应请求方法的前缀树t := engine.treesfor i, tl := 0, len(t); i < tl; i++ {if t[i].method != httpMethod {continue}root := t[i].root// Find route in tree// 去前缀树中取值value := root.getValue(rPath, c.params, c.skippedNodes, unescape)if value.params != nil {c.Params = *value.params}if value.handlers != nil {// 找到所有的handlerfuncc.handlers = value.handlersc.fullPath = value.fullPath// 具体去执行handlerfuncc.Next()c.writermem.WriteHeaderNow()return}......}
}func (c *Context) Next() {c.index++for c.index < int8(len(c.handlers)) {c.handlers[c.index](c) // 依次调用handlefunc，让c（context）在不同的func中传递c.index++}
}

钉钉事件回调具体实现

方式一：修改gin框架源代码（不推荐修改源代码）

我们第一步是先来建树，并且绑定对应的方法

第二步的话，就是当有钉钉群聊修改了名称，钉钉会给我们发送请求，会执行以下代码

 

 其中，ServeHTTP是当网络请求过来的时候，我们会执行的方法，下面我新添加的两个方法，是当钉钉事件发生的时候，就会执行，然后找到路由树中对应的方法，即可做出对应的逻辑处理。 

问题：

由于在查找树的时候，修改了gin框架的源代码，所以我们提交代码到仓库里面，其他同事是无法使用的，所以我们需要尽量不修改gin的源代码，也就是说查树的时候，不要修改源代码。

方法二：不修改gin框架源代码

把钉钉的事件注册到gin框架的路由中，在收到钉钉的回调请求之后，再自己给自己发送一个请求，然后就可以了，推荐使用这种方法。

方法三：自己实现前缀树

我们也要给树中的节点上面挂上对应的func，就类似于gin框架中

具体实现后续更新，需要用到context，sync.pool....

参考链接：

​​​​​​事件订阅总览 - 钉钉开放平台

基于 Golang 实现前缀树 Trie

gin框架源码解析 | 李文周的博客