net/http: reuse ServerMux to match PathValues using radix

[eudore]

Describe

• Compare 1.20 file and object changes
  • ServeMux reimplemented, moved from server.go to file servemux.go.
  • The Request object has a new attribute PathValues []string and a method func (r *Request) GetPathValue(key string) string.
  • MethodNotAllowed adds a new 405 status code processing function, named the same as the http.NotFound function.
  • servemux_test.go Unit tests for new features.
  • benchmarkServeMux adds PathValues reset to Request of performance test.
• Compatibility
  • When the original path has the suffix /, the equivalent rule will match /*.
  • If the first character of the path is not /, it is registered with host mode. When matching, it will try to match the host mode.
  • panic when registering the same path again.
  • When requesting the path /tree, a redirect will be returned if it cannot be matched and there is a /tree/ rule.
  • When requesting a path such as //, redirect after cleaning the path.
• New features
  • PathValues, use :name, *, *name matching variables or wildcards in the path, such as /:name/*resourec and /*.
  • Path matching priority, priority matching is performed when performing matching, according to: Constant > Variable > Wildcard, and has nothing to do with the order during registration.
  • To specify method matching, you can add methods in the pattern parameter of Handle, such as GET, POST /index.
  • ANY method priority. When ANY and specific methods are supported in the same path, specific methods are returned first, such as ANY /index and GET /index. Different request methods return different Handlers, and the matching method is the same as The registration order does not matter; when matching the ANY method, the method is the global variable MuxAnyMethod.
  • Customize the router's allowed methods. The 9 request methods in RFC are allowed by default. You can modify the global variable MuxAllMethod to extend customization, such as Webdav's non-standard methods.
  • 405 status response. When the path matches and there is no matching method, 405 status and Allow Header can be returned.
  • Customize Hander for 404 and 405 status, for example: mux.HandleFunc("404", serve(403)).
  • Sub-route, allowing ServeMux to be used as http.Hander to perform multiple matches, using / + {last PathValue} as the next matching path.
• Implemented but not added functionality
  • Default PathValue constants, allowing constants to be added after the path during registration, such as /src/* autoindex=true, and the autoindex parameter can be obtained in the PathValue.
  • Regular sum verification function, allowing the use of /id|^\d+$ or /id|num when registering, adding function verification function to variables and wildcards, and matching performance will not be affected when verification rules are not registered.
  • Obtain registered routing information. Record the method, path, and function name when registering. You can use the method to obtain all routing information.
  • Route cutting uses block patterns, for example: {/:id}, which does not match variables, but matches the request path /:id.
  • Fixed the ANY method. After modifying the global variable MuxAnyMethod during the registration process, the Any method has a method and only the MuxAnyMethod value at the time of registration. Subsequent modification of the variable MuxAnyMethod will not affect the registered ANY method. Not sure which behavior is more appropriate.
  • Route deletion allows you to delete the path function for Radix. This function has no effect.
• Problems exist:
  • Whether to add a new func (*ServeMux) HandleMethod(string, string, Handler) method and register specific method routes; the current Handle method registration: path, host+path, method+path, 404 and other rules.
  • Whether to add func (*Request) GetPathValues(string) []string method to read all values of the same key.
  • /:name will not match the empty string, / or /* can match the empty string, is it necessary to unify the standard?
  • Route splitting allows /api/user:get to be split into [/api/user :get], without forcing variables and wildcards to follow /.
  • The registered path //a does not clear the path and becomes /a, otherwise it will cause a registration conflict when registering /a and //a again. Should the path be cleared?
  • The sub-route uses / + {last PathValue} as the matching path. The first route /api/*api matches, and the sub-route matching path is /{api}; but when using /user/: The name/list rule makes the sub-route matching path /{name}. How to define the sub-route path rule?
  • Since some other test cases cannot be executed, use CGO_ENABLED=1 go test -v -timeout=1m -race -cover -coverprofile=coverage.out -coverpkg=net/http -run='(Mux|Slash|Redirect|PathV)'The command executed ServeMux related tests, but 100% coverage test of ServeMux has been completed.
• Match performance and code complexity
  • The new version of ServeMuximplementation does not use map types and goto keywords.
  • Use BenchmarkServeMux to test the old and new versions. The static test performance of the new and old versions is similar.
  • Tested using Github Api with httprouter v1.3.0 and chi v1.5.5, the new version has at least 50% of the performance of httprouter and uses less memory.
  • New ServeMux code complexity Top 3: 16 12 10
  • httprouter v1.3.0 code complexity Top3: 46 33 28
  • chi v1.5.5 code complexity Top3: 31 18 17

example

func main() {
    serve := func(code int) http.HandlerFunc {
        return func(w http.ResponseWriter, r *http.Request) {
            w.WriteHeader(code)
        }
    }
    ok := serve(200)

    // add webdav method.
    http.MuxAllMethod = append(http.MuxAllMethod, "PROPFIND", "PROPPATCH", "MKCOL", "COPY", "MOVE", "LOCK", "UNLOCK")
    mux := http.NewServeMux2()

    // set 404 and 405 status hadler.
    mux.HandleFunc("404", serve(403))
    mux.HandleFunc("NOTFOUND", serve(403))
    mux.HandleFunc("405", serve(403))
    mux.HandleFunc("METHODNOTALLOWED", serve(403))
    mux.HandleFunc("404,405", serve(403)) // error: split to [ANY] 404,405.

    // The same path is registered by different methods.
    // ANY does not cover fixed methods and has nothing to do with the registration order.
    mux.HandleFunc("ANY /method/*", ok)
    // mux.HandleFunc("/method/*", ok) // Register the same rule panic again.
    mux.HandleFunc("GET,POST /method/*", ok)
    mux.HandleFunc("/method/any", ok) // to [ANY] /method/any.

    // Constants, variables, and wildcards registered within the same parent have path matching priority, regardless of the registration order.
    mux.HandleFunc("/var/*", ok) // Set the wildcard name to "*" and allow matching of empty strings.
    mux.HandleFunc("/var/*v", ok) // The name of the override wildcard is "v".。
    mux.HandleFunc("/var/v1", ok)
    mux.HandleFunc("/var/v2", ok)
    mux.HandleFunc("/var/:", ok)  // Set the name of the variable to ":" and cannot match the empty string.
    mux.HandleFunc("/var/:v", ok) // The variable name "v" is not overwritten and considered to be two different patterns. The "/var/:v" pattern will never be matched.
    mux.HandleFunc("/var/:v1/v1", ok)
    mux.HandleFunc("/var/:v2/v2", ok) // Two different patterns have different PathValue names when matching.

    // Create a sub-route and add a Middleware.
    admin := http.NewServeMux()
    admin.HandleFunc("/*", ok)
    admin.HandleFunc("/index", ok)
    admin.HandleFunc("/pprof/", ok)
    admin.HandleFunc("GET /src/*path", ok)
    mux.Handle("/admin/*", NewMiddlwareBaiscauth(admin))

    // compatibility
    mux.HandleFunc("/src/", ok) // Registering `[ANY] /src/` and `[ANY] /src/*` shows pattern as "/src/", and then registering a new version of the rule "/src/*" conflicts.
    mux.HandleFunc("golang.org/src/", ok) // Host matching and registration.
    // mux.HandleFunc("golang.org/src/", ok) // Register the same rule panic again.
    // Request "/src" redirected to "/src/".
    // Request "//src/" redirected to "/src/".
}

func NewMiddlwareBaiscauth(h http.Handler) http.Handler {
    passwords := map[string]string{"eudore": ""}
    return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        // Determine the permissions and return 403 if the user does not exist.
        if passwords == nil {
            w.WriteHeader(403)
            return
        }

        h.ServeHTTP(w, r)
    })
}

Router matching performance

Use the original BenchmarkServeMux method to test 180 static paths and compare the test results of version 1.20 ServeMux:

The old ServeMux uses Map to perform matching, and the new ServeMux uses Radix to implement it. The old and new versions have similar performance for static path testing.

go version go1.20.1 linux/amd64
goos: linux
goarch: amd64
cpu: Intel(R) Xeon(R) Gold 6133 CPU @ 2.50GHz
BenchmarkServeMux-2                    15058         86429 ns/op       17280 B/op        360 allocs/op
BenchmarkServeMux_SkipServe-2          33867         33695 ns/op           0 B/op          0 allocs/op
BenchmarkServeMux2-2                   13344        100731 ns/op       17280 B/op        360 allocs/op
BenchmarkServeMux2_SkipServe-2         36368         33317 ns/op           0 B/op          0 allocs/op
PASS
ok      command-line-arguments  8.392s

Use Github Api performance test to compare httprouter v1.3.0 and chi v1.5.5:

For test methods, refer to vishr/web-framework-benchmark to perform routing matching testing.

The new ServeMux, httprouter, and chi are all implemented using Radix. Compared with httprouter, they have about 50% static performance and 70% Api performance at worst, and use less memory.

go version go1.21.3 linux/amd64
goos: linux
goarch: amd64
cpu: Intel(R) Xeon(R) Gold 6133 CPU @ 2.50GHz
BenchmarkMuxStatic-2                   26119         53744 ns/op         960 B/op        157 allocs/op
BenchmarkMuxGitHubAPI-2                14208         88254 ns/op        1605 B/op        203 allocs/op
BenchmarkMuxGplusAPI-2                348153          4599 ns/op         122 B/op         13 allocs/op
BenchmarkMuxParseAPI-2                201105          6729 ns/op         218 B/op         26 allocs/op
BenchmarkHttprouterStatic-2            46622         21611 ns/op        1034 B/op        157 allocs/op
BenchmarkHttprouterGitHubAPI-2         20516         59241 ns/op       15018 B/op        370 allocs/op
BenchmarkHttprouterGplusAPI-2         425414          3163 ns/op         744 B/op         24 allocs/op
BenchmarkHttprouterParseAPI-2         321686          4709 ns/op         796 B/op         42 allocs/op
BenchmarkChiStatic-2                   11814        122406 ns/op       53788 B/op        471 allocs/op
BenchmarkChiGitHubAPI-2                 7807        209186 ns/op       69705 B/op        609 allocs/op
BenchmarkChiGplusAPI-2                139898         10290 ns/op        4454 B/op         39 allocs/op
BenchmarkChiParseAPI-2                 72057         20435 ns/op        8905 B/op         78 allocs/op
PASS
ok      command-line-arguments  25.929s

Code complexity

In the new ServeMux implementation, the goto keywords is not used, and the gocyclo tool is used to count the top 10 code complexity:

16 http (*muxNode).lookNode src/net/http/servemux.go:479:1
12 http (*ServeMux).Handle src/net/http/servemux.go:138:1
10 http muxSplitMethods src/net/http/servemux.go:538:1
8 http (*muxNode).insertNode src/net/http/servemux.go:422:1
8 http (*ServeMux).match src/net/http/servemux.go:324:1
7 http muxSplitRoutes src/net/http/servemux.go:586:1
7 http cleanPath src/net/http/servemux.go:287:1
7 http (*ServeMux).handlerHost src/net/http/servemux.go:261:1
6 http getSubsetPrefix src/net/http/servemux.go:619:1
6 http (*muxNode).insertNodeConst src/net/http/servemux.go:449:1

46 httprouter (*node).findCaseInsensitivePathRec github.com/julienschmidt/httprouter@v1.3.0/tree.go:492:1
33 httprouter (*node).getValue github.com/julienschmidt/httprouter@v1.3.0/tree.go:339:1
28 httprouter (*node).addRoute github.com/julienschmidt/httprouter@v1.3.0/tree.go:83:1
26 httprouter CleanPath github.com/julienschmidt/httprouter@v1.3.0/path.go:21:1
21 httprouter (*Router).ServeHTTP github.com/julienschmidt/httprouter@v1.3.0/router.go:378:1
18 httprouter (*node).insertChild github.com/julienschmidt/httprouter@v1.3.0/tree.go:217:1
13 httprouter (*Router).allowed github.com/julienschmidt/httprouter@v1.3.0/router.go:327:1
5 httprouter shiftNRuneBytes github.com/julienschmidt/httprouter@v1.3.0/tree.go:476:1
5 httprouter countParams github.com/julienschmidt/httprouter@v1.3.0/tree.go:22:1
5 httprouter (*Router).Handle github.com/julienschmidt/httprouter@v1.3.0/router.go:244:1

31 chi (*node).findRoute github.com/go-chi/chi@v1.5.5/tree.go:387:1
18 chi patNextSegment github.com/go-chi/chi@v1.5.5/tree.go:663:1
17 chi (*Mux).Mount github.com/go-chi/chi@v1.5.5/mux.go:279:1
13 chi (*node).routes github.com/go-chi/chi@v1.5.5/tree.go:594:1
10 chi (*node).InsertRoute github.com/go-chi/chi@v1.5.5/tree.go:125:1
10 middleware ThrottleWithOpts github.com/go-chi/chi@v1.5.5/middleware/throttle.go:43:1
10 middleware (*Compressor).SetEncoder github.com/go-chi/chi@v1.5.5/middleware/compress.go:148:1
9 chi walk github.com/go-chi/chi@v1.5.5/tree.go:831:1
9 chi (*node).findPattern github.com/go-chi/chi@v1.5.5/tree.go:552:1
9 chi (*node).addChild github.com/go-chi/chi@v1.5.5/tree.go:221:1

Design

Radix tree

The Radix tree algorithm will not be described again. In Eudore Router, three Kinds are distinguished: constants/variables/wildcards based on muxNode.

When inserting, it is judged that the Kind attribute is added to different children groups. When matching, children are processed in order to achieve matching priority and better logic.

In the previous stdNode implementation, stdNode also had the kind int32 attribute, which was added to different children according to Kind in the insertNode method; the new muxNode will remove the Kind attribute and determine the muxNode.kind value through data , perform adding different children; hide the Kind logic and delete a storage field.

stdNode is the previous implementation method, muxNode is the implementation method submitted to net/http.ServeMux.

muxNode attributes:

• path saves the path of Const Node, also in the Radix path.
• name saves Param Node and Wildcard Node variable names.
• route saves the current routing pattern and marks this Node as a Data Node with a Handler.
• children saves various types of children.
• methods saves registered methods.
• handlers saves registered Handlers.

When registering /api/:v1/v1 and /api/:v2/v2, since different variable names are considered to be different Param Nodes, they need to be saved using Pchildren []*muxNode.

type muxNode struct {
    path  string // constant path
    name  string // variable name
    route string // routing pattern

    // children
    Wchildren *muxNode
    Cchildren []*muxNode
    Pchildren []*muxNode

    // handlers
    anyHandler Handler
    methods    []string
    handlers   []Handler
}

func (r *stdNode) insertNode(path string, nextNode *stdNode) *stdNode {
    if len(path) == 0 {
        return r
    }
    switch nextNode.kind {
    case stdNodeKindConst:
        return r.insertNodeConst(path, nextNode)
    case stdNodeKindParam:
        ...
        r.Pchildren = append(r.Pchildren, nextNode)
    case stdNodeKindParamValid:
        ...
        r.PVchildren = append(r.PVchildren, nextNode)
    case stdNodeKindWildcardValid:
        ...
        r.WVchildren = append(r.WVchildren, nextNode)
    case stdNodeKindWildcard:
        ...
        r.Wchildren = nextNode
    }
    return nextNode
}

func (r *stdNode) lookNode(searchKey string, params *Params) *stdNode {
    // constant match, return data
    if len(searchKey) == 0 && r.route != "" {
        return r
    }

    for _, child := range r.Cchildren {...}
    for _, child := range r.PVchildren {...}
    for _, child := range r.Pchildren {...}
    for _, child := range r.WVchildren {...}
    if r.Wchildren != nil {...}
    return nil
}

Route split

In Router Radix, Node is classified into at least 3 types. You need to use a function to accurately convert the pattern into routes, and then create a type Node and add it to Radix.

Path cutting is implemented in the muxSplitRoutes function; for /: and /* it is cut into variables and wildcard Node, used for Radix to add children.

/                 => [/]
/api/note/        => [/api/note/]
api/note/         => [api/note/]
/api/space 2/     => [/api/space 2/] len is 1
//api/*           => [/api/ *]
////api/*name     => [/api/ *name]
/api/get/         => [/api/get/]
/api/get          => [/api/get]
/api/:            => [/api/ :]
/api/:get         => [/api/ :get]
/api/:get/*       => [/api/ :get / *]
/api/:name/info/* => [/api/ :name /info/ *]

In the insertRoute method, use the insertNode method to add the new Node that has been cut to the end of the current Radix until the end Node of the last path, and then set the routing pattern information.

In the insertNode method, the addition and reuse of Node and the splitting of Radix Node will be dealt with in detail.

func (mux *ServeMux) insertRoute(method, path string, handler Handler) {
    node := mux.root
    routes := muxSplitRoutes(path)
    for _, route := range routes {
        node = node.insertNode(newMuxNode(route))
    }

    node.route = strings.Join(routes, "")
    node.setHandler(method, handler)
}

Parameter symbols

Use : for variable parameters and * for wildcard parameters. Consider the following factors:

• Compatible with popular frameworks such as echo and gin.
• {} is retained as a block pattern matching complex rule and is not added to ServeMux.
• For example: /id/{:id|^/\\d+$}, with / in the regular rule, use block mode to force the cut Routes result.

Request.PathValues

Add PathValues []string to the Request object to save the path parameters, and use the []string{"route", "route pattern", "key1", "val1", "key2", "val2"} format to save it For key-value data, my personal habit is that the first place is the routing pattern.

There are following factors when using the []string type:

• When there is relatively little data, the performance of using []string to operate KV is higher than that of map and avoid GC.
• When used by a third-party framework, it can be used with sync.Pool for memory reuse.
• Compatible with third-party high-performance frameworks, the framework matching path parameters can be passed to the Request object for http.Handler to use the third-party framework path parameters.

type Request struct {
    PathValues []string
    ...
}

You can also add a new PathValue type, using the following definition, both have the same memory model.

type Request struct {
    PathValues []PathValue
    ...
}
type PathValue struct {
    Path  string
    Value string
}

Group Router

When using group middleware in net/http.ServeMux, you may only be able to use sub-routes without modifying the API, and execute middleware and multiple route matching on the sub-routes.

example:

    admin := http.NewServeMux()
    admin.HandleFunc("GET /src/", EchoRequest)
    admin.HandleFunc("/pprof/", EchoRequest)

    mux := http.NewServeMux()
    mux.Handle("/admin/*", NewBaiscauth(admin, passwords))
    mux.HandleFunc("/index", EchoRequest)
    http.ListenAndServe(":8080", mux)

In order to avoid conflicts with the Method and Host in the pattern used by ServeMux.Handle, the path registered using the sub-route is prefixed with /, allowing the method to be specified but not the Host.

In the ServeMux.Handler method, the number of Request.PathValues parameters is used to determine whether it is a sub-route; when it is a sub-route, the Host and redirection are no longer processed, and Request.URL.Path is not used as the route matching path. , instead obtain the path from PathValues; the matching path used by the corresponding sub-route is / + {last PathValue}, which also uses / as the prefix.

If allowed, I can add Basic auth, Black list, Compress, Cors, Rate request, Rate speed, Recover, Referer Handlers.

func (mux *ServeMux) Handler(r *Request) (Handler, string) {
    if len(r.PathValues) > 1 {
        path := "/"
        if r.PathValues[len(r.PathValues)-2] != MuxValueRoute {
            path += r.PathValues[len(r.PathValues)-1]
        }
        h, shouldRedirect := mux.match(r.Method, path, r)
        if h == nil || shouldRedirect {
            h = mux.handler404
        }
        return h, r.GetPathValue(MuxValueRoute)
    }
    return mux.handler(r)
}

[gopherbot]

Change https://go.dev/cl/536896 mentions this issue: net/http: reimplementing ServeMux

[seankhliao]

I believe this deviates significantly from the accepted proposal in #61410