Closed aryalrabin closed 1 year ago
@tangyang9464 @imp2002
Thanks for the suggestion, I will try it in a few days.
Even 20 ms/ops is a bit more. Our actual operation takes under 1 ms and RBAC check is taking more than 20 ms. RBAC check is adding a 20X overhead in performance.
I cannot get 20 ms/ops for 10 million policies. What is your java version and JMH version?
Running a lookup on different numbers of policies parameters takes the following ms/ops
# JMH version: 1.36
# VM version: JDK 17.0.6, OpenJDK 64-Bit Server VM, 17.0.6+10-LTS
Benchmark (total_policies) Mode Cnt Score Error Units
BenchmarkBasicModel.benchmarkBasicModel 100 avgt 0.042 ms/op
BenchmarkBasicModel.benchmarkBasicModel 1000 avgt 0.343 ms/op
BenchmarkBasicModel.benchmarkBasicModel 10000 avgt 3.470 ms/op
BenchmarkBasicModel.benchmarkBasicModel 100000 avgt 39.378 ms/op
BenchmarkBasicModel.benchmarkBasicModel 1000000 avgt 406.477 ms/op
BenchmarkBasicModel.benchmarkBasicModel 10000000 avgt 4322.212 ms/op
code:
import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.casbin.jcasbin.main.Enforcer;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@State(Scope.Benchmark)
@Fork(value = 0) // change value to 0 to debug
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 1)
@Measurement(iterations = 1)
public class BenchmarkBasicModel {
private static final Random random = new Random();
@Param({"100", "1000", "10000", "100000", "1000000", "10000000"})
private static int total_policies = 1;
private static int randomIdx;
private static Enforcer e;
@Setup(Level.Iteration)
public static void setUp() {
e = new Enforcer("examples/basic_model.conf", "examples/basic_policy.csv", false);
e.enableAutoBuildRoleLinks(false);
for (int i=0; i< total_policies; i++) {
e.addPolicy(String.format("user%d", i), String.format("data%d", i/10), "read");
}
e.buildRoleLinks();
}
@Setup(Level.Invocation)
public static void setIteration() {
randomIdx = random.nextInt(total_policies);
}
@Threads(1)
@Benchmark
public static void benchmarkBasicModel() {
e.enforce(String.format("user%d", randomIdx), String.format("data%d", randomIdx/10), "read");
}
public static void main(String args[]) throws RunnerException {
Options options = new OptionsBuilder()
.include(BenchmarkBasicModel.class.getSimpleName())
.exclude("Perf")
.exclude("random")
.build();
new Runner(options).run();
}
}
If you look at the result for a single lookup for a different number of policies. The ms/ops time increases linearly with the number of total loaded policies.
Can you please run the code above and see what timing you get? Ideal timing will be less than 0.50 ms/ops for a single lookup.
Verified, I'll try your solution.
@aryalrabin first you can compare with the existing benchmarks in: https://casbin.org/docs/benchmark . Based on past experiences, Java should be slower than C++, similar speed with Go. If Java code is obviously much slower than Go, then maybe there are performance bugs in Java.
Second, see: https://casbin.org/docs/performance
@hsluoyz I agree the performance differs as per the programming language and hardware used.
Benchmarking RBAC (large) with Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, 6 Core
I get better performance
Benchmark Mode Cnt Score Error Units
BenchmarkRBACModelLarge.benchmarkRBACModelLarge avgt 100 15.023 ± 0.416 ms/op
As per your own benchmark in GO https://casbin.org/docs/benchmark the single lookup between RBAC (small, medium, and large) increases over 10X as the number of policies increases. The single lookup should not take that much in my opinion.
RBAC (small) | 1100 rules (1000 users, 100 roles) | 0.164309 | 80.620 |
---|---|---|---|
RBAC (medium) | 11000 rules (10000 users, 1000 roles) | 2.258262 | 765.152 |
RBAC (large) | 110000 rules (100000 users, 10000 roles) | 23.916776 | 7,606 |
As the number of loaded policies increases, the number of iterations increases in https://github.com/casbin/casbin/blob/1766ecae0d87431ea4140ac71afc84893772c802/enforcer.go#L594, which is adding to overall lookup performance.
Instead of iterating through all the loaded policies, performance can be improved if the loaded policy is filtered with request policy sub
before line https://github.com/casbin/casbin/blob/1766ecae0d87431ea4140ac71afc84893772c802/enforcer.go#L590. If the policy list is filtered in advance, there will be no need to iterate through all loaded policies.
@aryalrabin see: https://casbin.org/docs/performance#high-number-of-policy-rules , one way is that you manually call LoadFilteredPolicy() before enforcement
LoadFilteredPolicy() is only supported by FilteredAdapter, we are not using File or DB Adapter rather dynamically populating policies. Plus the policy will have to be dynamically loaded before enforcement. This may significantly add to the performance overhead.
My option now will be sharding.
@hsluoyz The single lookup performance needs to be evaluated. In the current implementation, the lookup time is tied to where the request policy is in the loaded policy list. For example, in the BenchmarkRBACModelLarge lookup time for user0, user5000 and user99999 show a significant difference. The single lookup should return same time no matter where the requested policy is in the list.
Benchmark Mode Cnt Score Error Units
BenchmarkRBACModelLarge.benchmarkRBACModelLarge_User0_Data0 avgt 0.098 ms/op
BenchmarkRBACModelLarge.benchmarkRBACModelLarge_User50000_Data500 avgt 8.409 ms/op
BenchmarkRBACModelLarge.benchmarkRBACModelLarge_User99999_Data999 avgt 16.477 ms/op
Code:
@Benchmark
public static void benchmarkRBACModelLarge_User0_Data0() {
e.enforce("user0", "data0", "read");
}
@Benchmark
public static void benchmarkRBACModelLarge_User50000_Data500() {
e.enforce("user50000", "data500", "read");
}
@Benchmark
public static void benchmarkRBACModelLarge_User99999_Data999() {
e.enforce("user99999", "data999", "read");
}
Even with sharding, I may run into the same issue as the policy will be loaded dynamically, and some shared enforcers may have a larger loaded policy than others. The lookup speed will the all over.
If it is possible, you may need to revisit the algorithm for enforcement and try to return the same lookup time for the requested policy no matter where they are on the loaded policy list.
@aryalrabin Casbin works in a way that runs the rules one by one. So it's not trivial efforts to support what you said. I don't think we can tune the algorithm for your specific case in a very short time. It will be good if you can contribute the code.
@hsluoyz Thanks for the response. I did a brief investigation, and the algorithm change is more complicated than I thought. It is simple for the basic model but gets complex for "RBAC model with the group", "ABAC with policy rule", and a few other models.
For our needs, we may be able to just override the enforcement on our side and improve the performance as we are using a basic model.
Thanks for the prompt reply and help.
I added https://github.com/casbin/jcasbin/pull/341 to improve performance. It does not change the algorithm, but provides about 7% improvement by micro-optimizations.
With the JMH (Java Microbenchmark Harness) lookup for a single request policy with 100,000 loaded policies takes over 50 ms. This is a lot and will add a lot to the operation.
Benchmark Mode Cnt Score Error Units RBACModelBenchmark.benchmarkRBACModel avgt 51.952 ms/op
The JMH code
Model used:
Upon debugging the JCasbin CoreEnforcer enforcer methods https://github.com/casbin/jcasbin/blob/00a5942586640f1089b7b8ad687575659477d579/src/main/java/org/casbin/jcasbin/main/CoreEnforcer.java#L510 loops through all 100,000 policies.
Is it possible to filter the policies with the request subject before looping to reduce the lookup time?