[Bug] Performance issue in RBAC with pattern matching domains

[silverspace]

Describe the bug
When I modify the BenchmarkRBACModelWithDomainPatternLarge performance test to add a bunch of unrelated users and then try to fetch an unauthorized resource, I see an exponential number of calls to the domain matching function util.KeyMatch4, resulting in exponentially bad performance related to the number of additional users.

For context, I am trying to use a model.conf similar to this large scale performance test, but I am hitting massive performance issues when many different users with different domains are added.

To Reproduce
I've modified the existing BenchmarkRBACModelWithDomainPatternLarge benchmark test to first add 1000 unrelated users with different domains to the unrelated role staffOrgUser. The result is that each of these users are being evaluated an exponential number of times when we try to run the enforcer.

func BenchmarkRBACModelWithDomainPatternLarge(b *testing.B) {
	e, _ := NewEnforcer("examples/performance/rbac_with_pattern_large_scale_model.conf", "examples/performance/rbac_with_pattern_large_scale_policy.csv")
	e.AddNamedDomainMatchingFunc("g", "keyMatch4", util.KeyMatch4)

	_ = e.BuildRoleLinks()
	for i := 0; i < 1000; i++ {
		orgID := rand.Int()
		user := fmt.Sprintf("staffUser%d", orgID)
		role := fmt.Sprintf("staffOrgUser")
		dom := fmt.Sprintf("/orgs/%d/sites/*", orgID)
		if err := e.GetRoleManager().AddLink(user, role, dom); err != nil {
			b.Fatal(err)
		}
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		const unauthorizedSite = "/orgs/999/sites/site001"
		_, _ = e.Enforce("staffUser1001", unauthorizedSite, "App001.Module001.Action1001")
	}
}

This results in an exponential number of calls to util.KeyMatch4 (the domain matching function), exponentially related to the number of users added. (e.g. if I increase 1000 to 10000, the benchmark never ends).

goos: darwin
goarch: amd64
pkg: github.com/casbin/casbin/v2
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkRBACModelWithDomainPatternLarge-12    	      19	  61330779 ns/op
PASS

Expected behavior
Without these additional 1000 users, the performance is:

goos: darwin
goarch: amd64
pkg: github.com/casbin/casbin/v2
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkRBACModelWithDomainPatternLarge-12    	    7998	    139011 ns/op

[casbin-bot]

@tangyang9464 @closetool @sagilio

[hsluoyz]

@tangyang9464

[tangyang9464]

@abichinger maybe you have a better idea about it.

[abichinger]

I think the problem is that the default role manager can't distinguish between pattern and plain strings. As a result the role manager will treat every string as a pattern, if a MatchingFunc is supplied.

If we could identify patterns, then we would only have to iterate over a subset of all roles, instead of all of them, each time a user is added. (FastAC uses util.IMatcher to solve this)

Nonetheless, this would not fix the performance issue of the example, because the example uses patterns only.

dom := fmt.Sprintf("/orgs/%d/sites/*", orgID)

@silverspace do you really intend to only use patterns for dom or was that just for the example?

[silverspace]

For my actual use case I stopped using RBAC patterns entirely, since they were prohibitively expensive.

I think that the Casbin project should consider dropping this feature entirely, or at the very least adding a huge caveat to the documentation that this could lead to major performance issues. I don't think that my example above is far fetched for a reasonable implementation of domain patterns, and I think it is reasonable to assume that the built in MatchingFuncs would have tolerable performance for medium sized policies. At the very least I would have expected O(N) performance, and not O(N^2).

Thanks for the FastAC link! It doesn't look like they support pattern domains, but it does look like a clever approach of reducing the search space for the matching functions.

[FoeverA0]

[WeOpen Star]I would like to help

[fahussain]

This issue gave us so much headache for two days and finally we found out the culprit is the use of matchingDomainForGFunction and matchingForGFunction. We wanted to use pattern matching for domains but we eventually had to drop that due to the performance issues. Is there any plan to fix this problem?

[hsluoyz]

@JalinWang

/cc @tangyang9464

[tony-spark]

As a workaround, I implemented custom KeyMath2/RegexMatch with regexp caching.
It helped a little but still bad performance.

In the end, I have to rework my access model to get rid of heavy domain matching