Deep Dive into Gin Framework: Compressed Radix Tree Routing and Request Processing

1. Introduction

Gin is an efficient and easy-to-use Go web framework widely used in web development. This article explores Gin's core implementation, focusing on the routing component's compressed radix tree (CRT), describing its architecture, request handling flow, and how to build high‑performance services with Gin.

2. Compressed Radix Tree

2.1 What is a Compressed Radix Tree?

Compressed Radix Tree (CRT) is an optimized trie that stores multiple characters per node, reducing depth and memory usage while improving lookup speed.

2.2 Advantages of CRT

CRT excels when handling large numbers of strings, offering lower memory consumption and faster searches.

2.3 Structure and Operations

Each node contains a value (one or more characters), child pointers, and a termination flag. Operations include insertion (merging common prefixes) and lookup (character‑by‑character matching).

Insertion: shared prefixes are kept, differing suffixes become new nodes.

Lookup: matches characters sequentially until a full key is found or mismatch occurs.

3. Gin and httprouter

Gin builds on httprouter , which uses CRT as its underlying data structure. When an HTTP request arrives, Gin leverages CRT to quickly locate the corresponding handler, improving routing speed and reducing memory overhead.

4. Gin Example Code Analysis

Example code shows router initialization, middleware registration, and route grouping.

router := gin.Default()
router.Use(gin_comm.CorsFunc())
router.Use(gin_comm.AuthMiddleWare())

// API v1 route group
v1 := router.Group("/api/v1") {
    v1.POST("/sayhello", handler())
}

The Engine contains a trees field, an array of CRTs, one per HTTP method. The New function creates the engine and initializes the trees.

func New() *Engine {
    engine := &Engine{
        RouterGroup: RouterGroup{
            Handlers: nil,
            basePath: "/",
            root:     true,
        },
        trees: make(methodTrees, 0, 9),
        // other fields omitted
    }
    engine.RouterGroup.engine = engine
    engine.pool.New = func() interface{} { return engine.allocateContext() }
    return engine
}

Middleware are added via router.Use , stored in the handlers slice of RouterGroup .

5. Request Processing Flow

5.1 HTTP Entry

router.Run() starts the server; incoming requests invoke Engine.ServeHTTP , which obtains a Context from a pool, resets it, and calls handleHTTPRequest .

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
    c := engine.pool.Get().(*Context)
    c.writermem.reset(w)
    c.Request = req
    c.reset()
    engine.handleHTTPRequest(c)
    engine.pool.Put(c)
}

5.2 Routing and Handling

handleHTTPRequest selects the tree matching the request method, uses root.getValue to traverse the CRT, and assigns the matched handlers to the context.

func (engine *Engine) handleHTTPRequest(c *Context) {
    httpMethod := c.Request.Method
    rPath := c.Request.URL.Path
    t := engine.trees
    for i := range t {
        if t[i].method != httpMethod { continue }
        root := t[i].root
        value := root.getValue(rPath, c.params)
        if value.handlers != nil {
            c.handlers = value.handlers
            c.Params = *c.params
            c.fullPath = value.fullPath
            c.Next()
            c.writermem.WriteHeaderNow()
            return
        }
    }
    c.handlers = engine.allNoRoute
    serveError(c, 404, default404Body)
}

The CRT matches characters step‑by‑step; on success it returns handlers, otherwise nil.

5.3 Middleware Execution

Middleware are stored in Context.handlers and executed in order via Context.Next() .

func (c *Context) Next() {
    c.index++
    for c.index < int8(len(c.handlers)) {
        c.handlers[c.index](c)
        c.index++
    }
}

5.4 Route Handler Execution

After middleware, the route’s handler runs, e.g., returning JSON.

v1.POST("/sayhello", func(c *gin.Context) {
    c.JSON(200, gin.H{"message": "Hello, World!"})
})

5.5 Response Generation

The response is written using writermem.WriteHeaderNow() to ensure headers and body are sent correctly.

func (c *Context) writermem.WriteHeaderNow() {
    if !c.writermem.Written() {
        c.writermem.WriteHeaderNow()
    }
}

5.6 Error and 404 Handling

If no route matches, Gin serves a predefined 404 handler.

if c.handlers == nil {
    c.handlers = engine.allNoRoute
    serveError(c, 404, default404Body)
}

6. Middleware and Route Groups

Middleware are added with router.Use ; route groups organize related routes, inheriting middleware automatically.

router.Use(gin_comm.CorsFunc())
router.Use(gin_comm.AuthMiddleWare())

v1 := router.Group("/api/v1") {
    v1.POST("/sayhello", handler())
}

7. Conclusion

The article provides an in‑depth analysis of Gin’s core components and request processing, highlighting how the compressed radix tree serves as a performance‑critical element that enables fast routing and low memory usage, making Gin suitable for high‑load web services.

Best‑practice recommendations:

Leverage Gin middleware for request pre‑processing and post‑processing.

Design routes to avoid excessively deep trees.

Consider object‑pool patterns to reduce allocation overhead.