uatuko / ruek

🔐 Lightning fast, global scale authorization service without the overhead of a yet another DSL.
Apache License 2.0
94 stars 6 forks source link

Traverse relations graph right to left when checking relations #103

Closed uatuko closed 5 months ago

uatuko commented 5 months ago

This is a slight optimisation to reduce the BFS graph traversal cost with the expectation that the graph is narrower on the left and wider on the right. Most of the time this would be the case if principals are on the left.

e.g. In the following example, to check user:jane -> reader -> doc:notes.txt with left to right BFS will require 10003 lookups whereas right to left will only take 3 lookups.

Relations graph, wider on the right

Benchmarks

Before ``` ------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations UserCounters... ------------------------------------------------------------------------------------------- bm_relations/check_graph/4/128 25076263 ns 3086440 ns 100 ops=323.998/s vertices=126.359k/s bm_relations/check_graph/8/128 57364218 ns 7036899 ns 99 ops=142.108/s vertices=128.75k/s bm_relations/check_graph/32/128 259431654 ns 33223300 ns 10 ops=30.0994/s vertices=120.458k/s bm_relations/check_graph/4/512 101723773 ns 12166667 ns 57 ops=82.1918/s vertices=126.74k/s bm_relations/check_graph/8/512 237103853 ns 27974560 ns 25 ops=35.7468/s vertices=128.474k/s bm_relations/check_graph/32/512 1078407325 ns 137229800 ns 5 ops=7.28705/s vertices=115.908k/s bm_relations/check_graph/4/2048 421086234 ns 51664538 ns 13 ops=19.3556/s vertices=119.037k/s bm_relations/check_graph/8/2048 974933250 ns 118474000 ns 6 ops=8.44067/s vertices=121.09k/s bm_relations/check_graph/32/2048 4466643000 ns 611284000 ns 1 ops=1.6359/s vertices=103.916k/s ```
-------------------------------------------------------------------------------------------
Benchmark                                 Time             CPU   Iterations UserCounters...
-------------------------------------------------------------------------------------------
bm_relations/check_graph/4/128       414345 ns        58750 ns        12076 ops=17.0214k/s vertices=102.128k/s
bm_relations/check_graph/8/128       646869 ns        91978 ns         7637 ops=10.8721k/s vertices=108.721k/s
bm_relations/check_graph/32/128     2107918 ns       321862 ns         2148 ops=3.10692k/s vertices=105.635k/s
bm_relations/check_graph/4/512       425155 ns        59755 ns        12022 ops=16.7349k/s vertices=100.41k/s
bm_relations/check_graph/8/512       664887 ns        92465 ns         7602 ops=10.8149k/s vertices=108.149k/s
bm_relations/check_graph/32/512     2142939 ns       311927 ns         2217 ops=3.20587k/s vertices=109k/s
bm_relations/check_graph/4/2048      430403 ns        58354 ns        12093 ops=17.1369k/s vertices=102.821k/s
bm_relations/check_graph/8/2048      678464 ns        91770 ns         7622 ops=10.8968k/s vertices=108.968k/s
bm_relations/check_graph/32/2048    2190622 ns       312404 ns         2219 ops=3.20098k/s vertices=108.833k/s
codecov[bot] commented 5 months ago

Codecov Report

Attention: Patch coverage is 88.88889% with 2 lines in your changes missing coverage. Please review.

Project coverage is 93.17%. Comparing base (bef3937) to head (c83821e).

Files Patch % Lines
src/svc/relations.cpp 88.88% 0 Missing and 2 partials :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #103 +/- ## ========================================== + Coverage 93.11% 93.17% +0.06% ========================================== Files 18 18 Lines 1307 1304 -3 Branches 161 160 -1 ========================================== - Hits 1217 1215 -2 Misses 64 64 + Partials 26 25 -1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.