Repository: casbin/casbin
Pull request #221 (2019-04-25 11:46:03)

Replace `sync.Mutex` with `sync.RWMutex` for CachedEnforcer 
`sync.Map` appears to fit better here as the current implementation serializes any writes to the map even though they are typically writing separate keys (and typically only ever a given key, once). Using `sync.Map` reduces contention on this mutex.

From https://golang.org/pkg/sync/#Map
> The Map type is optimized for two common use cases: (1) when the entry for a given key is only ever written once but read many times, as in caches that only grow, or (2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys. In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

I think this use case fits the first well.

Running the added benchmark locally, I saw a roughly 40% improvement.

Before:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel
2019/04/25 13:35:27 Start automatically load policy     
2019/04/25 13:35:27 Stop automatically load policy
2019/04/25 13:35:27 Start automatically load policy
2019/04/25 13:35:27 Model:
2019/04/25 13:35:27 p.p: sub, obj, act        
2019/04/25 13:35:27 e.e: some(where (p_eft == allow))
2019/04/25 13:35:27 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act     
2019/04/25 13:35:27 r.r: sub, obj, act
2019/04/25 13:35:27 Policy:                   
2019/04/25 13:35:27 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 13:35:27 Request: alice, data1, read ---> true
2019/04/25 13:35:27 Request: alice, data1, write ---> false                                                                                                                                                        
2019/04/25 13:35:27 Request: alice, data2, read ---> false
2019/04/25 13:35:27 Request: alice, data2, write ---> false
2019/04/25 13:35:27 Request: bob, data1, read ---> false
2019/04/25 13:35:27 Request: bob, data1, write ---> false
2019/04/25 13:35:27 Request: bob, data2, read ---> false
2019/04/25 13:35:27 Request: bob, data2, write ---> true
2019/04/25 13:35:27 Stop automatically load policy   
goos: linux                                                                
goarch: amd64              
pkg: github.com/casbin/casbin                                               
BenchmarkCachedRBACModelMediumParallel-4         5000000               359 ns/op
PASS                                                       
ok      github.com/casbin/casbin        5.137s    
```

After:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel
2019/04/25 13:35:11 Start automatically load policy
2019/04/25 13:35:11 Stop automatically load policy                              
2019/04/25 13:35:11 Start automatically load policy
2019/04/25 13:35:11 Model:
2019/04/25 13:35:11 r.r: sub, obj, act
2019/04/25 13:35:11 p.p: sub, obj, act
2019/04/25 13:35:11 e.e: some(where (p_eft == allow))
2019/04/25 13:35:11 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act
2019/04/25 13:35:11 Policy:
2019/04/25 13:35:11 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 13:35:11 Request: alice, data1, read ---> true
2019/04/25 13:35:11 Request: alice, data1, write ---> false
2019/04/25 13:35:11 Request: alice, data2, read ---> false
2019/04/25 13:35:11 Request: alice, data2, write ---> false
2019/04/25 13:35:11 Request: bob, data1, read ---> false
2019/04/25 13:35:11 Request: bob, data1, write ---> false
2019/04/25 13:35:11 Request: bob, data2, read ---> false
2019/04/25 13:35:11 Request: bob, data2, write ---> true
2019/04/25 13:35:11 Stop automatically load policy
goos: linux
goarch: amd64
pkg: github.com/casbin/casbin
BenchmarkCachedRBACModelMediumParallel-4        10000000               220 ns/op
PASS
ok      github.com/casbin/casbin        5.434s
```

I only added a parallel benchmark of BenchmarkCachedRBACModelMedium for now, but
we could opt to instead replace existing benchmarks with parallel benchmarks to show how the enforcer behaves when accessed from multiple goroutines.

coveralls: 
[![Coverage Status](https://coveralls.io/builds/23019901/badge)](https://coveralls.io/builds/23019901)

Coverage increased (+0.06%) to 80.884% when pulling **efe1181ef819f39ce3ba4c7162edc9d304d880f0 on jszwedko:use-sync-map-cached-enforcer** into **312d222b08a1d01f34bae3bac18237963300459b on casbin:master**.

vtolstov: Can you try test also, if sync.Mutex replaces with sync.RWMutex? as i read from other projects, sync.Map not recommended to use and using own locking with RWMutex gave more performance
jszwedko: @vtolstov good thought, it looks like the locking on read contention is the main culprit.

With this diff:

```diff
diff --git a/enforcer_cached.go b/enforcer_cached.go
index fffc834..14cea5e 100644
--- a/enforcer_cached.go
+++ b/enforcer_cached.go
@@ -23,7 +23,7 @@ type CachedEnforcer struct {
        *Enforcer
        m           map[string]bool
        enableCache bool
-       locker      *sync.Mutex
+       locker      *sync.RWMutex
 }

 // NewCachedEnforcer creates a cached enforcer via file or DB.
@@ -32,7 +32,7 @@ func NewCachedEnforcer(params ...interface{}) *CachedEnforcer {
        e.Enforcer = NewEnforcer(params...)
        e.enableCache = true
        e.m = make(map[string]bool)
-       e.locker = new(sync.Mutex)
+       e.locker = new(sync.RWMutex)
        return e
 }

@@ -57,13 +57,16 @@ func (e *CachedEnforcer) Enforce(rvals ...interface{}) bool {
                }
        }

-       e.locker.Lock()
-       defer e.locker.Unlock()
+       e.locker.RLock()
        if _, ok := e.m[key]; ok {
+               e.locker.RUnlock()
                return e.m[key]
        } else {
+               e.locker.RUnlock()
                res := e.Enforcer.Enforce(rvals...)
+               e.locker.Lock()
                e.m[key] = res
+               e.locker.Unlock()
                return res
        }
 }
```

I see:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel                                                                                                        
2019/04/25 19:20:49 Start automatically load policy
2019/04/25 19:20:49 Stop automatically load policy
2019/04/25 19:20:49 Start automatically load policy
2019/04/25 19:20:49 Model:
2019/04/25 19:20:49 r.r: sub, obj, act
2019/04/25 19:20:49 p.p: sub, obj, act
2019/04/25 19:20:49 e.e: some(where (p_eft == allow))
2019/04/25 19:20:49 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act
2019/04/25 19:20:49 Policy:
2019/04/25 19:20:49 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 19:20:49 Request: alice, data1, read ---> true
2019/04/25 19:20:49 Request: alice, data1, write ---> false
2019/04/25 19:20:49 Request: alice, data2, read ---> false
2019/04/25 19:20:49 Request: alice, data2, write ---> false
2019/04/25 19:20:49 Request: bob, data1, read ---> false
2019/04/25 19:20:49 Request: bob, data1, write ---> false
2019/04/25 19:20:49 Request: bob, data2, read ---> false
2019/04/25 19:20:49 Request: bob, data2, write ---> true
2019/04/25 19:20:49 Stop automatically load policy
goos: linux
goarch: amd64
pkg: github.com/casbin/casbin
BenchmarkCachedRBACModelMediumParallel-4        10000000               226 ns/op
PASS
ok      github.com/casbin/casbin        5.593s
```

Roughly the same as using `sync.Map`. I haven't profiled memory usage to see if there are any differences.

Do you have a preference between `sync.RWMutex` or `sync.Map` given this?
jszwedko: Benchmarks with memory usage:

Using `sync.Mutex`:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel -benchmem                                                                                                
2019/04/25 19:27:27 Start automatically load policy
2019/04/25 19:27:27 Stop automatically load policy
2019/04/25 19:27:27 Start automatically load policy
2019/04/25 19:27:27 Model:
2019/04/25 19:27:27 r.r: sub, obj, act
2019/04/25 19:27:27 p.p: sub, obj, act
2019/04/25 19:27:27 e.e: some(where (p_eft == allow))
2019/04/25 19:27:27 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act
2019/04/25 19:27:27 Policy:
2019/04/25 19:27:27 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 19:27:27 Request: alice, data1, read ---> true
2019/04/25 19:27:27 Request: alice, data1, write ---> false
2019/04/25 19:27:27 Request: alice, data2, read ---> false
2019/04/25 19:27:27 Request: alice, data2, write ---> false
2019/04/25 19:27:27 Request: bob, data1, read ---> false
2019/04/25 19:27:27 Request: bob, data1, write ---> false
2019/04/25 19:27:27 Request: bob, data2, read ---> false
2019/04/25 19:27:27 Request: bob, data2, write ---> true
2019/04/25 19:27:28 Stop automatically load policy
goos: linux
goarch: amd64
pkg: github.com/casbin/casbin
BenchmarkCachedRBACModelMediumParallel-4         5000000               375 ns/op             128 B/op          4 allocs/op                                                                                         
PASS
ok      github.com/casbin/casbin        5.450s
```

Using `sync.RWMutex`:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel -benchmem
2019/04/25 19:26:25 Start automatically load policy
2019/04/25 19:26:25 Stop automatically load policy
2019/04/25 19:26:25 Start automatically load policy
2019/04/25 19:26:25 Model:
2019/04/25 19:26:25 p.p: sub, obj, act
2019/04/25 19:26:25 e.e: some(where (p_eft == allow))
2019/04/25 19:26:25 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act
2019/04/25 19:26:25 r.r: sub, obj, act
2019/04/25 19:26:25 Policy:
2019/04/25 19:26:25 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 19:26:25 Request: alice, data1, read ---> true
2019/04/25 19:26:25 Request: alice, data1, write ---> false
2019/04/25 19:26:25 Request: alice, data2, read ---> false
2019/04/25 19:26:25 Request: alice, data2, write ---> false
2019/04/25 19:26:25 Request: bob, data1, read ---> false
2019/04/25 19:26:25 Request: bob, data1, write ---> false
2019/04/25 19:26:25 Request: bob, data2, read ---> false
2019/04/25 19:26:25 Request: bob, data2, write ---> true
2019/04/25 19:26:25 Stop automatically load policy
goos: linux
goarch: amd64
pkg: github.com/casbin/casbin
BenchmarkCachedRBACModelMediumParallel-4         5000000               234 ns/op             128 B/op          4 allocs/op
PASS
ok      github.com/casbin/casbin        4.656s
```

Using `sync.Map`:

```
go test -cpu 4 -bench BenchmarkCachedRBACModelMediumParallel -benchmem                                                                                                
2019/04/25 19:28:08 Start automatically load policy
2019/04/25 19:28:08 Stop automatically load policy
2019/04/25 19:28:08 Start automatically load policy
2019/04/25 19:28:08 Model:
2019/04/25 19:28:08 r.r: sub, obj, act
2019/04/25 19:28:08 p.p: sub, obj, act
2019/04/25 19:28:08 e.e: some(where (p_eft == allow))
2019/04/25 19:28:08 m.m: r_sub == p_sub && r_obj == p_obj && r_act == p_act
2019/04/25 19:28:08 Policy:
2019/04/25 19:28:08 p: sub, obj, act: [[alice data1 read] [bob data2 write]]
2019/04/25 19:28:08 Request: alice, data1, read ---> true
2019/04/25 19:28:08 Request: alice, data1, write ---> false
2019/04/25 19:28:08 Request: alice, data2, read ---> false
2019/04/25 19:28:08 Request: alice, data2, write ---> false
2019/04/25 19:28:08 Request: bob, data1, read ---> false
2019/04/25 19:28:08 Request: bob, data1, write ---> false
2019/04/25 19:28:08 Request: bob, data2, read ---> false
2019/04/25 19:28:08 Request: bob, data2, write ---> true
2019/04/25 19:28:09 Stop automatically load policy
goos: linux
goarch: amd64
pkg: github.com/casbin/casbin
BenchmarkCachedRBACModelMediumParallel-4        10000000               248 ns/op             128 B/op          4 allocs/op                                                                                         
PASS
ok      github.com/casbin/casbin        5.959s
```

Patch:
diff --git a/enforcer_cached.go b/enforcer_cached.go
index fffc834..1d1fcfc 100644
--- a/enforcer_cached.go
+++ b/enforcer_cached.go
@@ -23,7 +23,7 @@ type CachedEnforcer struct {
 	*Enforcer
 	m           map[string]bool
 	enableCache bool
-	locker      *sync.Mutex
+	locker      *sync.RWMutex
 }
 
 // NewCachedEnforcer creates a cached enforcer via file or DB.
@@ -32,7 +32,7 @@ func NewCachedEnforcer(params ...interface{}) *CachedEnforcer {
 	e.Enforcer = NewEnforcer(params...)
 	e.enableCache = true
 	e.m = make(map[string]bool)
-	e.locker = new(sync.Mutex)
+	e.locker = new(sync.RWMutex)
 	return e
 }
 
@@ -57,17 +57,28 @@ func (e *CachedEnforcer) Enforce(rvals ...interface{}) bool {
 		}
 	}
 
-	e.locker.Lock()
-	defer e.locker.Unlock()
-	if _, ok := e.m[key]; ok {
-		return e.m[key]
+	if res, ok := e.getCachedResult(key); ok {
+		return res
 	} else {
 		res := e.Enforcer.Enforce(rvals...)
-		e.m[key] = res
+		e.setCachedResult(key, res)
 		return res
 	}
 }
 
+func (e *CachedEnforcer) getCachedResult(key string) (res bool, ok bool) {
+	e.locker.RLock()
+	defer e.locker.RUnlock()
+	res, ok = e.m[key]
+	return res, ok
+}
+
+func (e *CachedEnforcer) setCachedResult(key string, res bool) {
+	e.locker.Lock()
+	defer e.locker.Unlock()
+	e.m[key] = res
+}
+
 // InvalidateCache deletes all the existing cached decisions.
 func (e *CachedEnforcer) InvalidateCache() {
 	e.m = make(map[string]bool)
diff --git a/examples/rbac_with_hierarchy_with_domains_policy.csv b/examples/rbac_with_hierarchy_with_domains_policy.csv
index 45d9173..49cce40 100644
--- a/examples/rbac_with_hierarchy_with_domains_policy.csv
+++ b/examples/rbac_with_hierarchy_with_domains_policy.csv
@@ -1,8 +1,8 @@
 p, role:reader, domain1, data1, read
 p, role:writer, domain1, data1, write
 
-p, alice, domain1, data2, read
-p, alice, domain2, data2, read
+p, alice, domain1, data1, read
+p, alice, domain2, data1, read
 
 g, role:global_admin, role:reader, domain1
 g, role:global_admin, role:writer, domain1
diff --git a/rbac_api.go b/rbac_api.go
index fef0b63..5fb3f9f 100644
--- a/rbac_api.go
+++ b/rbac_api.go
@@ -173,25 +173,23 @@ func (e *Enforcer) GetImplicitRolesForUser(name string, domain ...string) []stri
 // But GetImplicitPermissionsForUser("alice") will get: [["admin", "data1", "read"], ["alice", "data2", "read"]].
 func (e *Enforcer) GetImplicitPermissionsForUser(user string, domain ...string) [][]string {
 	roles := e.GetImplicitRolesForUser(user, domain...)
-	roles = append([]string{user}, roles...)
+	res := [][]string{}
+	permissions := [][]string{}
+
+	for _, role := range roles {
+		permissions = e.GetPermissionsForUser(role)
+		res = append(res, permissions...)
+	}
 
-	withDomain := false
 	if len(domain) == 1 {
-		withDomain = true
+		permissions = e.GetPermissionsForUserInDomain(user, domain[0])
 	} else if len(domain) > 1 {
 		panic("error: domain should be 1 parameter")
+	} else {
+		permissions = e.GetPermissionsForUser(user)
 	}
 
-	res := [][]string{}
-	permissions := [][]string{}
-	for _, role := range roles {
-		if withDomain {
-			permissions = e.GetPermissionsForUserInDomain(role, domain[0])
-		} else {
-			permissions = e.GetPermissionsForUser(role)
-		}
-		res = append(res, permissions...)
-	}
+	res = append(res, permissions...)
 
 	return res
 }


Test patch:
diff --git a/enforcer_cached_b_test.go b/enforcer_cached_b_test.go
index e8cd333..6bc38af 100644
--- a/enforcer_cached_b_test.go
+++ b/enforcer_cached_b_test.go
@@ -157,3 +157,25 @@ func BenchmarkCachedPriorityModel(b *testing.B) {
 		e.Enforce("alice", "data1", "read")
 	}
 }
+
+func BenchmarkCachedRBACModelMediumParallel(b *testing.B) {
+	e := NewCachedEnforcer("examples/rbac_model.conf")
+	// Do not rebuild the role inheritance relations for every AddGroupingPolicy() call.
+	e.EnableAutoBuildRoleLinks(false)
+	// 1000 roles, 100 resources.
+	for i := 0; i < 1000; i++ {
+		e.AddPolicy(fmt.Sprintf("group%d", i), fmt.Sprintf("data%d", i/10), "read")
+	}
+	// 10000 users.
+	for i := 0; i < 10000; i++ {
+		e.AddGroupingPolicy(fmt.Sprintf("user%d", i), fmt.Sprintf("group%d", i/10))
+	}
+	e.BuildRoleLinks()
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			e.Enforce("user5001", "data150", "read")
+		}
+	})
+}
diff --git a/rbac_api_test.go b/rbac_api_test.go
index 9b5f2d2..3cdde49 100644
--- a/rbac_api_test.go
+++ b/rbac_api_test.go
@@ -230,11 +230,11 @@ func TestImplicitPermissionAPI(t *testing.T) {
 	testGetPermissions(t, e, "alice", [][]string{{"alice", "data1", "read"}})
 	testGetPermissions(t, e, "bob", [][]string{{"bob", "data2", "write"}})
 
-	testGetImplicitPermissions(t, e, "alice", [][]string{{"alice", "data1", "read"}, {"data1_admin", "data1", "read"}, {"data1_admin", "data1", "write"}, {"data2_admin", "data2", "read"}, {"data2_admin", "data2", "write"}})
+	testGetImplicitPermissions(t, e, "alice", [][]string{{"data1_admin", "data1", "read"}, {"data1_admin", "data1", "write"}, {"data2_admin", "data2", "read"}, {"data2_admin", "data2", "write"}, {"alice", "data1", "read"}})
 	testGetImplicitPermissions(t, e, "bob", [][]string{{"bob", "data2", "write"}})
 }
 
 func TestImplicitPermissionAPIWithDomain(t *testing.T) {
 	e := NewEnforcer("examples/rbac_with_domains_model.conf", "examples/rbac_with_hierarchy_with_domains_policy.csv")
-	testGetImplicitPermissionsWithDomain(t, e, "alice", "domain1", [][]string{{"alice", "domain1", "data2", "read"}, {"role:reader", "domain1", "data1", "read"}, {"role:writer", "domain1", "data1", "write"}})
+	testGetImplicitPermissionsWithDomain(t, e, "alice", "domain1", [][]string{{"role:reader", "domain1", "data1", "read"}, {"role:writer", "domain1", "data1", "write"}, {"alice", "domain1", "data1", "read"}})
 }