Optimize RBAC access control check

[tjerman]

No description provided.

[tjerman]

The original versions index was sub optimal.
Rules were indexed by role and some other bits.
The issue arises when the number of rules increases as the lookup time is linear.

Benchmarks for the original implementation:

goos: darwin
goarch: arm64
pkg: github.com/cortezaproject/corteza/server/pkg/rbac
Benchmark_AccessCheck_role100_rule1000-12                  45502             26437 ns/op           10183 B/op        206 allocs/op
Benchmark_AccessCheck_role100_rule10000-12                  9054            143348 ns/op           10195 B/op        206 allocs/op
Benchmark_AccessCheck_role100_rule100000-12                  910           1399730 ns/op           10132 B/op        205 allocs/op
Benchmark_AccessCheck_role100_rule1000000-12                  40          32568396 ns/op           11196 B/op        226 allocs/op
Benchmark_AccessCheck_role100_rule10000000-12                  8         580995401 ns/op           14075 B/op        286 allocs/op
Benchmark_AccessCheck_role1000_rule1000-12                 10000            115692 ns/op           78850 B/op       1216 allocs/op
Benchmark_AccessCheck_role1000_rule10000-12                 4567            260073 ns/op           87800 B/op       1578 allocs/op
Benchmark_AccessCheck_role1000_rule100000-12                 758           1521378 ns/op           87707 B/op       1593 allocs/op
Benchmark_AccessCheck_role1000_rule1000000-12                 97          26178927 ns/op           79729 B/op       1447 allocs/op
Benchmark_AccessCheck_role1000_rule10000000-12                 6         338761798 ns/op           87824 B/op       1502 allocs/op
Benchmark_AccessCheck_role10000_rule1000-12                 1165           1113431 ns/op          875524 B/op      10173 allocs/op
Benchmark_AccessCheck_role10000_rule10000-12                 972           1259840 ns/op          877246 B/op      11239 allocs/op
Benchmark_AccessCheck_role10000_rule100000-12                404           2661588 ns/op          921948 B/op      14190 allocs/op
Benchmark_AccessCheck_role10000_rule1000000-12               100          25640188 ns/op         1038714 B/op      15395 allocs/op
Benchmark_AccessCheck_role10000_rule10000000-12                4         265117083 ns/op          882284 B/op      12844 allocs/op

Important
There is a noticeable time difference in building the original and reworked index.
Since the index is built only once, we'll take the hit since the lookup times are much better.

[tjerman]

Benchmarks for the reworked version:

goos: darwin
goarch: arm64
pkg: github.com/cortezaproject/corteza/server/pkg/rbac
Benchmark_AccessCheck_role100_rule1000-12                 101308             11020 ns/op            5120 B/op         23 allocs/op
Benchmark_AccessCheck_role100_rule10000-12                106794             10392 ns/op            5119 B/op         23 allocs/op
Benchmark_AccessCheck_role100_rule100000-12               106137             10957 ns/op            5135 B/op         23 allocs/op
Benchmark_AccessCheck_role100_rule1000000-12               94984             13411 ns/op            5110 B/op         23 allocs/op
Benchmark_AccessCheck_role100_rule10000000-12              78258             13923 ns/op            5118 B/op         23 allocs/op
Benchmark_AccessCheck_role1000_rule1000-12                 14739             79997 ns/op           52803 B/op         45 allocs/op
Benchmark_AccessCheck_role1000_rule10000-12                10000            111318 ns/op           53129 B/op         45 allocs/op
Benchmark_AccessCheck_role1000_rule100000-12               10000            119062 ns/op           53103 B/op         45 allocs/op
Benchmark_AccessCheck_role1000_rule1000000-12              10000            127920 ns/op           53166 B/op         45 allocs/op
Benchmark_AccessCheck_role1000_rule10000000-12              7801            406544 ns/op           53141 B/op         50 allocs/op
Benchmark_AccessCheck_role10000_rule1000-12                 1609            744085 ns/op          508033 B/op        106 allocs/op
Benchmark_AccessCheck_role10000_rule10000-12                1227            959672 ns/op          509599 B/op        106 allocs/op
Benchmark_AccessCheck_role10000_rule100000-12                447           2711555 ns/op          502836 B/op        105 allocs/op
Benchmark_AccessCheck_role10000_rule1000000-12               723           2202073 ns/op          528585 B/op        110 allocs/op
Benchmark_AccessCheck_role10000_rule10000000-12              418           2587235 ns/op          496879 B/op        108 allocs/op

[tjerman]

Comparing the numbers

Number for averages

time 3031 times better
memory 1.85 times better
allocs 53.64 times better

Numbers per benchmark

Benchmark_AccessCheck_role100_rule1000-12
time 26437/11020=2.39 times better
memory 10183/5120=1.98 times better
allocs 206/23=8.95 times better

Benchmark_AccessCheck_role100_rule10000-12
time 143348/10392=13.79 times better
memory 10195/5119=1.99 times better
allocs 206/23=8.95 times better

Benchmark_AccessCheck_role100_rule100000-12
time 1399730/10957=127.74 times better
memory 10132/5135=1.97 times better
allocs 205/23=8.91 times better

Benchmark_AccessCheck_role100_rule1000000-12
time 32568396/13411=2428.48 times better
memory 11196/5110=2.19 times better
allocs 226/23=9.82 times better

Benchmark_AccessCheck_role100_rule10000000-12
time 580995401/13923=41729.18 times better
memory 14075/5118=2.75 times better
allocs 286/23=12.43 times better


Benchmark_AccessCheck_role1000_rule1000-12
time 115692/79997=1.44 times better
memory 78850/52803=1.49 times better
allocs 1216/45=27.02 times better

Benchmark_AccessCheck_role1000_rule10000-12
time 260073/111318=2.33 times better
memory 87800/53129=1.65 times better
allocs 1578/45=35.06 times better

Benchmark_AccessCheck_role1000_rule100000-12
time 1521378/119062=12.77 times better
memory 87707/53103=1.65 times better
allocs 1593/45=35.4 times better

Benchmark_AccessCheck_role1000_rule1000000-12
time 26178927/127920=204.65 times better
memory 79729/53166=1.49 times better
allocs 1447/45=32.15 times better

Benchmark_AccessCheck_role1000_rule10000000-12
time 338761798/406544=833.27 times better
memory 87824/53141=1.65 times better
allocs 1502/50=30.04 times better


Benchmark_AccessCheck_role10000_rule1000-12
time 1113431/744085=1.49 times better
memory 875524/508033=1.72 times better
allocs 10173/106=95.97 times better

Benchmark_AccessCheck_role10000_rule10000-12
time 1259840/959672=1.31 times better
memory 877246/509599=1.72 times better
allocs 11239/106=106.02 times better

Benchmark_AccessCheck_role10000_rule100000-12
time 2661588/2711555=0.98 times better
memory 921948/502836=1.83 times better
allocs 14190/105=135.14 times better

Benchmark_AccessCheck_role10000_rule1000000-12
time 25640188/2202073=11.64 times better
memory 1038714/528585=1.96 times better
allocs 15395/110=139.95 times better

Benchmark_AccessCheck_role10000_rule10000000-12
time 265117083/2587235=102.47 times better
memory 882284/496879=1.77 times better
allocs 12844/108=118.92 times better

[tjerman]

Peek into the change

Instead of simple hash maps, we introduce a variation of a trie.
We split up the RBAC rule in chunks (separated by /) and use it to represent all the rules as a trie.
This lets us look up the values optimally.

Looking back at the numbers, it's not exactly what it should be so I've probably messed up the implementation.
The performance is more than enough so there is no much need to optimise further.

[github-actions]

Stale issue message