Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

routesrv route listing changes Etag more often than needed #2519

Open
szuecs opened this issue Aug 16, 2023 · 1 comment
Open

routesrv route listing changes Etag more often than needed #2519

szuecs opened this issue Aug 16, 2023 · 1 comment
Assignees
Labels
bugfix Bug fixes and patches

Comments

@szuecs
Copy link
Member

szuecs commented Aug 16, 2023

Describe the bug

If you use routesrv and the client you want to have at best a stable Etag to limit work on the control plane part of the data plane.
Routes and Predicates are sorted to mitigate this, but if multiple routes have the same predicate with different value, then it seems not sort stable.

Example:

% curl -I http://127.0.0.1:9990/routes
HTTP/1.1 200 OK
Accept-Ranges: bytes
Content-Length: 1041476
Content-Type: text/plain; charset=utf-8
Etag: "0a860e4c0868b48977f322eaf6eff0bee1d8e0d5191c9b1f1654bb963813777d"
Last-Modified: Wed, 16 Aug 2023 10:42:22 GMT
X-Count: 1225
Date: Wed, 16 Aug 2023 10:42:23 GMT

% curl -I http://127.0.0.1:9990/routes
HTTP/1.1 200 OK
Accept-Ranges: bytes
Content-Length: 1041476
Content-Type: text/plain; charset=utf-8
Etag: "0aa578823d84defb968ceba18eb7b14646441f9d8ceab0726ec8a150be0c2b28"
Last-Modified: Wed, 16 Aug 2023 10:42:25 GMT
X-Count: 1225
Date: Wed, 16 Aug 2023 10:42:26 GMT

% curl -I http://127.0.0.1:9990/routes
HTTP/1.1 200 OK
Accept-Ranges: bytes
Content-Length: 1041476
Content-Type: text/plain; charset=utf-8
Etag: "0aa578823d84defb968ceba18eb7b14646441f9d8ceab0726ec8a150be0c2b28"
Last-Modified: Wed, 16 Aug 2023 10:42:25 GMT
X-Count: 1225
Date: Wed, 16 Aug 2023 10:42:27 GMT

% curl -I http://127.0.0.1:9990/routes
HTTP/1.1 200 OK
Accept-Ranges: bytes
Content-Length: 1041476
Content-Type: text/plain; charset=utf-8
Etag: "fabcdda1761dcfa4417e8f9841f308ce1f0d3778971b70fa4fb1b55c73d80638"
Last-Modified: Wed, 16 Aug 2023 10:42:34 GMT
X-Count: 1225
Date: Wed, 16 Aug 2023 10:42:35 GMT

A minimal example that I guess would flap is this:

r1: Header("A") -> <shunt>;
r2: Header("B") -> <shunt>;

or can be listed like this:

r1: Header("B") -> <shunt>;
r2: Header("A") -> <shunt>;

To Reproduce

internal only

Expected behavior

stable sorting is expected

Observed behavior

unstable sorting

@szuecs szuecs added the bugfix Bug fixes and patches label Aug 16, 2023
@MustafaSaber
Copy link
Member

Related PRs if someone wants to take over #2208 & #2202

AlexanderYastrebov added a commit that referenced this issue Sep 5, 2023
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Several built-in predicates represented as maps internally therefore
sorting is necessary to obtain stable eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in predicates
unconditionally and leave regular predicates intact.

This change:

* sorts built-in predicates unconditionally in-place using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
              │            sec/op             │   sec/op     vs base               │
RouteString-8                     11.69µ ± 2%   12.49µ ± 1%  +6.83% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
              │             B/op              │     B/op      vs base               │
RouteString-8                    1.789Ki ± 0%   1.883Ki ± 0%  +5.24% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new   │
              │           allocs/op           │ allocs/op   vs base               │
RouteString-8                      63.00 ± 0%   67.00 ± 0%  +6.35% (p=0.000 n=10)
```
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit that referenced this issue Sep 5, 2023
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Several built-in predicates represented as maps internally therefore
sorting is necessary to obtain stable eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in predicates
unconditionally and leave regular predicates intact.

This change:

* sorts built-in predicates unconditionally in-place using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.67µ ± 1%   14.43µ ± 1%  +5.52% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                     7.086µ ± 1%   7.092µ ± 1%       ~ (p=0.424 n=10)
geomean                                               9.843µ        10.11µ       +2.77%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.523Ki ± 0%  +3.86% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.748Ki       +1.91%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   98.00 ± 0%  +4.26% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        72.07       +2.11%
¹ all samples are equal
```

Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit that referenced this issue Sep 5, 2023
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Header and HeaderRegexp built-in predicates are represented as maps
internally therefore sorting is necessary to obtain stable
eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in Header and
HeaderRegexp predicates unconditionally and leave regular predicates intact.

This change:

* sorts built-in Header and HeaderRegexp predicates unconditionally in-place
  using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.70µ ± 2%   14.07µ ± 2%  +2.74% (p=0.009 n=10)
RouteStringNoRepeatedPredicates-8                     7.083µ ± 3%   7.102µ ± 1%       ~ (p=0.079 n=10)
geomean                                               9.850µ        9.997µ       +1.50%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.477Ki ± 0%  +1.93% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.732Ki       +0.96%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   96.00 ± 0%  +2.13% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        71.33       +1.06%
¹ all samples are equal
```

Note that sorting only happens when there are several Header or HeaderRegexp predicates in the route.
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit that referenced this issue Sep 6, 2023
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Header and HeaderRegexp built-in predicates are represented as maps
internally therefore sorting is necessary to obtain stable
eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in Header and
HeaderRegexp predicates unconditionally and leave regular predicates intact.

This change:

* sorts built-in Header and HeaderRegexp predicates unconditionally in-place
  using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.70µ ± 2%   14.07µ ± 2%  +2.74% (p=0.009 n=10)
RouteStringNoRepeatedPredicates-8                     7.083µ ± 3%   7.102µ ± 1%       ~ (p=0.079 n=10)
geomean                                               9.850µ        9.997µ       +1.50%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.477Ki ± 0%  +1.93% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.732Ki       +0.96%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   96.00 ± 0%  +2.13% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        71.33       +1.06%
¹ all samples are equal
```

Note that sorting only happens when there are several Header or HeaderRegexp predicates in the route.
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>

---------

Signed-off-by: Alexander Yastrebov <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugfix Bug fixes and patches
Projects
None yet
Development

No branches or pull requests

2 participants