HttpRouter is a lightweight, high-performance HTTP request router (also known as a multiplexer). Net/HTTP HttpServeMux compared to the official Go default router, this router supports dynamic routing, where a portion of the route address can be converted to handler parameters that match the Request method. It’s also more scalable.

Github address: github.com/julienschmi…

Comparison of performance Benchmarks

As you can see from this table, HttpRouter is over 40 times more efficient to implement in static routes than in the GO standard library. Although the memory footprint is a bit higher, in modern computers a small footprint is no longer a bottleneck.

The dictionary Trie tree

Also known as word lookup tree, Trie tree, is a tree structure, is a variant of hash tree. It is typically used to count, sort and save large numbers of strings (but not limited to strings), so it is often used for text word frequency statistics by search engine systems. Its advantages are that it reduces query time by using the common prefix of strings, minimizes unnecessary string comparisons, and improves query efficiency over hash trees.

HttpRouter how to work

The disadvantage of HttpServeMux

Go’s official HttpServeMux saves routes via hashMap. This data structure determines that it cannot support dynamic routing and efficient lookup.

Route implementation of HttpRouter

HttpRouter is optimized for high performance and small memory footprint. It scales well even in the case of very long paths and lots of paths. HttpRouter relies on the familiar dictionary tree Trie to store routing addresses. It is basically a compact prefix tree (Radix tree). Nodes with a common prefix also share a common parent node. Here is a short example of the route tree for the GET Request method:

Priority Path Handle 9 \ * 3 ├ s nil < 1 > 2 | ├ earch \ * < 2 > 1 | └ upport \ \ * * < 3 > 2 ├ blog < 4 > 1 | └ : post nil 1 | └ \ * < 5 > 2 ├ about - us \ * < 6 > 1 | └ team \ * < 7 > 1 └ contact \ * 8 > <Copy the code

Under Handle, each *

represents the memory address of the handler function (pointer).

If you follow the path from Root Root to the leaf node, you get the full routing path, such as \blog:post\, where :post is just a placeholder (argument). Unlike hashMap, the tree structure also allows us to use dynamic parts such as: POST parameters, because we are actually matching based on routing patterns, not just comparing hashes. As the benchmark shows, this approach is very effective.

Because URL paths are hierarchical and use only a limited set of characters (byte values), it is likely that there are many common prefixes. This allows us to easily reduce routing to smaller and smaller problems. In addition, the router manages a separate tree for each request method POST/GET/DELETE, etc. On the one hand, it saves more space than keeping method-> Handle in every node compared to a map, and it allows us to greatly reduce routing problems before we even start looking in the prefix tree.

conclusion

HttpRouter uses dictionary trees to store routing information and creates a separate dictionary tree for each request method. In addition, he manages Param objects through sync.pool recycling to reduce GC costs.

Welcome to follow my wechat public number, Geek Road. Ask big brothers praise ~ ~