introduce
First, what is routing? Routing is the process of locating a request to a specific implementation logic based on the request information
This process is called routing addressing
The performance of a route is judged by the addressing time. The shorter the time, the higher the performance
Traditional Routing Structure
We’ve all used expess or KOA + KoA-Router to develop projects
They store the routing mapping table in the form of an array and traverse the routing table for addressing by means of regular matching
This method is intuitive and simple, but in the case of a large number of routes, it consumes a lot of resources to perform a large number of unnecessary matches
Routing structure based on prefix tree
To improve addressing capabilities, we can use a space-for-time approach to split the request path and store it in a special data structure
storage
We registered the following four routes:
First, all routes are divided into the corresponding method tree according to the request method
The requests are then assembled into a tree structure with/unwrapped
To improve the matching performance, the storage node saves node types and matches nodes based on the types
search
So once we get the request path, again according to/split,
First, find the corresponding tree according to method
The tree is then recursively searched, and if the current node is matched, the next level is searched. Each node is divided into two types: regular and string
If the current node is of the regular type, regular matching is used for regular routes and parametric routes
If the current node is a string, equal matches are used to reduce the number of regular matches and improve performance
To optimize the
For greater performance improvement (reducing the number of matches), the nodes are prioritized so that the nodes with the most paths through them are placed first
In this way, hot routes are put in the front and can be matched with the least number of times (manual priority setting can be added later).
The benchmark
The machine is worse, compare good….
Dazejs + 1000 routes
| Stat | Avg | Stdev | Min |
|---|---|---|---|
| Req/Sec | 33122.91 | 2705.63 | 25830 |
| Bytes/Sec | 4.8 MB | 2.64 KB | 25.22 KB |
Express + 1000 routes
| Stat | Avg | Stdev | Min |
|---|---|---|---|
| Req/Sec | 11809.64 | 1232.99 | 8115 |
| Bytes/Sec | 2.42 MB | 1.2 KB | 7.92 KB |
Koa + KOa-router + 1000 routes
| Stat | Avg | Stdev | Min |
|---|---|---|---|
| Req/Sec | 6851.46 | 571.17 | 5103 |
| Bytes/Sec | 1016.86 KB | 571 B | 4.98 KB |
More and more
Project address: github.com/dazejs/daze
digression
Many Node applications are currently middle-tier, and a bit of routing addressing optimization is negligible