[TOC]

This is the fourth day of my participation in the More text Challenge. For details, see more text Challenge

Gin routing algorithm sharing

What is GIN?

We took a look at the official profile on Github

Gin is a web framework written in Go (Golang). 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 is a micro framework developed with Go, a Web framework, similar to Martinier’s API, simple interface, very high performance, also because httprouter performance is 40 times better.

If you need good performance and productivity, you will like Gin.

What features does GIN have?

tag instructions
Exception handling The service is always available,Not down.

Gin can capture panic and restore it. And there are extremely convenient mechanisms for handling errors that occur during HTTP requests.
Routing group You can group apis that require authorization and apis that do not require authorization, different versions of apis.

Moreover, the groups can be nested, and performance is not affected.

For example the v1 / v2 / / XXX XXX XXX XXX
Render the built-in Native supportJSON, XML and HTMLThe rendering.
JSON GinThe REQUESTED JSON can be parsed and validated.

This property pairsRestful APIIs especially useful.
The middleware HTTPRequest, which can be processed by a series of middleware

To the Logger, Authorization, etc.

The middleware mechanism also greatly improves the extensibility of the framework.

What does GIN generally include?

We have shared the actual practice of GIN before, so let’s review what knowledge points gin contains

  • : routingand* routing
  • Query Query parameter
  • Receive arrays and maps
  • Form Form
  • Single-file and multi-file uploads
  • Packet routing, and routing nesting
  • Routing middleware
  • Support for various data formats, JSON, struct, XML, YAML, Protobuf
  • HTML Template rendering
  • Url redirection
  • Asynchronous coroutines and so on

If you are still interested in GIN, you can click here to have a look. Here are specific knowledge points corresponding to the practical practice of GIN

What is routing?

Now, what is a route

A router is a network device that connects multiple networks or network segments. It can “translate” data information between different networks or network segments so that they can “read” each other’s data, thus forming a larger network.

Routers have two typical functions

  • The data channel function

Forwarding decisions, backplane forwarding, and output link scheduling are generally performed by specific hardware

  • Control function

It is generally realized by software, including information exchange, system configuration, system management and so on between adjacent routers

Routing in GIN

Routing is a core function of the Web framework.

The friend who wrote the route initially looked at the route like this:

  • According to the route/Cut routes into arrays of strings
  • The route is then constructed into a tree structure based on the same preceding subarray

When addressing is needed, the requested URL is divided into segments by /, and then the tree is addressed. This is a bit like the recursive traversal of the depth-first algorithm, starting from the root node and continuing to the root until you can’t go any further

Take a chestnut

Two routes /v1/hi and /v1/hello are defined

So this will create a routing tree with three nodes, the root node is v1, and the two children nodes are hi Hello.

Above is a way to achieve the routing tree, this is more intuitive, easy to understand. Url segmentation and comparison, but the time complexity is O(2n), so do we have a better way to optimize the time complexity? The famous GIn framework has a way of looking back

What’s the algorithm?

Again, let’s talk about what the algorithm is.

An algorithm is a computational method, a procedure, to solve a problem. It is not only the computer that has the term algorithm.

For example, we learned the multiplication table in primary school

I learned a variety of calculation methods for solving problems in middle school, such as physical formulas and so on

Now all kinds of cooking, cooking process and method is also a kind of algorithm

  • The problem is a bug, the solution is not the same, the steps are very different
  • Facing pig’s trotters, cooking methods have their own characteristics
  • In the face of problems in our life, maybe everyone will encounter the same problem, but everyone’s way to solve the problem is very different, some people deal with things very beautiful, some people procrastinate, always leave a tail

I have learned the book of algorithm in university. Algorithm is the soul of computer. When faced with problems, good algorithms can easily deal with them and have good robustness

Faced with life problems, good solutions can also let us go further, more accurately speaking, it should be a good thinking model.

The algorithm has the following five characteristics

Everything will have its own, otherwise how can it be remembered

  • Finiteness, the algorithm has to have a definite step limit and then it ends
  • Accuracy, each step is clear, the parameters involved are also exact
  • Inputs, the algorithm has zero or more inputs
  • Output, the algorithm has zero or more outputs
  • Feasibility, each step of the algorithm can be decomposed and executed, and can be completed in limited time

Gin routing algorithm

So let’s get to the point. Gin’s routing algorithm is coming out

The ROUTING algorithm of GIN is similar to a prefix tree

You only need to walk through the string once, and the time complexity is O(n). Compared to the above mentioned method, in terms of time complexity is really a big optimization

However, for a single HTTP request, it doesn’t work

Ah, hit the blackboard, what is called a prefix tree?

Trie Tree, also known as dictionary Tree and Prefix Tree, is a multi-tree structure

If you draw a picture, you’ll probably see what a prefix tree is

This tree is also different from a binary tree in that its keys are not stored directly in the nodes, but are determined by where the nodes are in the tree

All descendants of a node have the same prefix, which is the string corresponding to the node, and the root node corresponds to the empty string.

For example, in the figure above, if we address them one by one, there will be strings like this

  • MAC
  • TAG
  • TAB
  • HEX

The prefix tree has the following characteristics:

  • The root node of the prefix tree does not contain characters, and all other nodes contain characters
  • Each node’s children contain different strings
  • From the root node to a node, the characters passing through the path are concatenated to form the corresponding string of the node
  • The child node of each node usually has a flag bit that identifies the end of a word

Does this look like a routing tree?

Gin’s routing tree algorithm is similar to a prefix tree. But it’s not just one tree, it’s every method (POST, GET, PATCH…) Each has its own tree

For example, the address of the route is

  • /hi
  • /hello
  • /:name/:id

So the tree for Gin would look like this

The node data structure for routes in GO looks like this

type node struct {
    path      string
    indices   string
    children  []*node
    handlers  HandlersChain
    priority  uint32
    nType     nodeType
    maxParams uint8
    wildChild bool
}
Copy the code

The specific method of adding routes, the implementation method is like this

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)
    // You can have a good look here
    root := engine.trees.get(method) 
    if root == nil {
        root = new(node)
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers)
}
Copy the code

On closer inspection, the gin implementation doesn’t look like a real tree

The children []*node array contains all the children in the array. In this case, it will use the indices, priority to implement a tree

Let’s look at the different ways to register routes. Each registration mode is reflected in the GIN routing tree

Common Registered route

The common route registration mode is router. XXX, which can be either of the following

  • GET
  • POST
  • PATCH
  • PUT
  • .
router.POST("/hi".func(context *gin.Context) {
    context.String(http.StatusOK, "hi xiaomotong")})Copy the code

You can also register routes in groups and groups to facilitate version maintenance

v1 := router.Group("v1")
{
    v1.POST("hello".func(context *gin.Context) {
        context.String(http.StatusOK, "v1 hello world")})}Copy the code

Handle is called when the route HTTP related functions such as POST, GET, and PATCH are called

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
    absolutePath := group.calculateAbsolutePath(relativePath) // calculateAbsolutePath
    handlers = group.combineHandlers(handlers) // combineHandlers
    group.engine.addRoute(httpMethod, absolutePath, handlers)
    return group.returnObj()
}
Copy the code

CalculateAbsolutePath and combineHandlers will appear again

Call the group, and see how it works

func (group *RouterGroup) Group(relativePath string, handlers ... HandlerFunc) *RouterGroup {
    return &RouterGroup{
        Handlers: group.combineHandlers(handlers),
        basePath: group.calculateAbsolutePath(relativePath),
        engine:   group.engine,
    }
}
Copy the code

CalculateAbsolutePath and combineHandlers are also called, so let’s see what those two functions are doing, and maybe we can guess what they’re doing, so let’s look at the source code

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
}
Copy the code
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
}
Copy the code

The joinPaths function is very important here, mainly for concatenation purposes

From the above, we can see the following two points:

  • When you call the middleware, you place both the handler handler for a particular route and the middleware handler in the Handlers array
  • When you call Group, you spell the value of Group over the path of the route. So /hi/:id, v1/hi/:id

Use middleware to register routes

We can also use middleware to register routes. For example, before accessing our routes, we need to add an authenticated middleware, which can access the routes only after being authenticated

router.Use(Login())
Copy the code
func (group *RouterGroup) Use(middleware ... HandlerFunc) IRoutes {
    group.Handlers = append(group.Handlers, middleware...)
    return group.returnObj()
}
Copy the code

There is a key handler in the registration, whether it is a normal registration or a middleware registration

After the handler method calls calculateAbsolutePath and combineHandlers, the handler method calls the addRoute method to register the result of route preprocessing to the Trees of the Gin Engine to read the implementation of the handler

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()
}
Copy the code

So, after the server writes the route, when we make the HTTP request through the specific route, how does the server find the specific handler through the route?

After carefully tracing the source code, we can see the following implementation

.// A prefix tree
t := engine.trees
for i, tl := 0.len(t); i < tl; i++ {
    ift[i].method ! = httpMethod {continue
    }
    root := t[i].root
    // Find route in tree
    // We use path to locate the corresponding handlers
    handlers, params, tsr := root.getValue(path, c.Params, unescape) 
    ifhandlers ! =nil {
        c.handlers = handlers
        c.Params = params
        // Call the specific handler here
        c.Next()
        c.writermem.WriteHeaderNow()
        return
    }
    ifhttpMethod ! ="CONNECT"&& path ! ="/" {
        if tsr && engine.RedirectTrailingSlash {
            redirectTrailingSlash(c)
            return
        }
        if engine.RedirectFixedPath && redirectFixedPath(c, root, engine.RedirectFixedPath) {
            return}}break}...Copy the code
func (c *Context) Next(a) {
    c.index++
    for c.index < int8(len(c.handlers)) {
        c.handlers[c.index](c)
        c.index++
    }
}
Copy the code

Handlers, params, TSR := root.getValue(path, c.params, unescape);

Handlers and params are copied to the service and executed using c.ext () to get to the routing address of the response requested by the client. The server can then handle the response route accordingly

conclusion

  • Briefly review the features of GIN
  • This section describes routes in GIN
  • Shared gin routing algorithm, as well as specific source code implementation process

Ok, that’s it for now. Next time, I’ll share the most common flow limiting algorithms and how to incorporate flow control into HTTP middleware.

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am nezha, welcome to like the collection, see you next time ~