Giter Club home page Giter Club logo

Comments (11)

aryalrabin avatar aryalrabin commented on June 2, 2024 1

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.

from jcasbin.

casbin-bot avatar casbin-bot commented on June 2, 2024

@tangyang9464 @imp2002

from jcasbin.

imp2002 avatar imp2002 commented on June 2, 2024

Thanks for the suggestion, I will try it in a few days.

from jcasbin.

imp2002 avatar imp2002 commented on June 2, 2024

Verified, I'll try your solution.

from jcasbin.

hsluoyz avatar hsluoyz commented on June 2, 2024

@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

from jcasbin.

aryalrabin avatar aryalrabin commented on June 2, 2024

@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.

from jcasbin.

hsluoyz avatar hsluoyz commented on June 2, 2024

@aryalrabin see: https://casbin.org/docs/performance#high-number-of-policy-rules , one way is that you manually call LoadFilteredPolicy() before enforcement

from jcasbin.

aryalrabin avatar aryalrabin commented on June 2, 2024

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.

from jcasbin.

hsluoyz avatar hsluoyz commented on June 2, 2024

@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.

from jcasbin.

aryalrabin avatar aryalrabin commented on June 2, 2024

@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.

from jcasbin.

kdebski85 avatar kdebski85 commented on June 2, 2024

I added #341 to improve performance. It does not change the algorithm, but provides about 7% improvement by micro-optimizations.

from jcasbin.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.