The indexes mutation in the code also needs to be treated as transactions. In other words, before we commit the transaction, other transactions shouldn't see any index updates about our transaction made.

An implementation of Sync ART.

NOTES: There are still some bugs with concurrent removes.

• [x] Concurrent Insert
• [x] Concurrent Search
• [x] Concurrent Iterator
• [x] Remove

For Concurrent Read Write (Point Query)

I ran the benchmark used in badger's skip list, and it's 2-4x fast than badger's lock-free skip list implementation and better than both map implementations.

Sync ART

BenchmarkArtReadWrite
BenchmarkArtReadWrite/frac_0
BenchmarkArtReadWrite/frac_0-10         	 9391489	       206.7 ns/op
BenchmarkArtReadWrite/frac_1
BenchmarkArtReadWrite/frac_1-10         	 9414129	       128.0 ns/op
BenchmarkArtReadWrite/frac_2
BenchmarkArtReadWrite/frac_2-10         	12652800	       112.7 ns/op
BenchmarkArtReadWrite/frac_3
BenchmarkArtReadWrite/frac_3-10         	12118660	       109.0 ns/op
BenchmarkArtReadWrite/frac_4
BenchmarkArtReadWrite/frac_4-10         	15121713	       103.2 ns/op
BenchmarkArtReadWrite/frac_5
BenchmarkArtReadWrite/frac_5-10         	15300210	        97.91 ns/op
BenchmarkArtReadWrite/frac_6
BenchmarkArtReadWrite/frac_6-10         	16776656	        92.86 ns/op
BenchmarkArtReadWrite/frac_7
BenchmarkArtReadWrite/frac_7-10         	18277624	        71.15 ns/op
BenchmarkArtReadWrite/frac_8
BenchmarkArtReadWrite/frac_8-10         	30692596	        70.17 ns/op
BenchmarkArtReadWrite/frac_9
BenchmarkArtReadWrite/frac_9-10         	37829132	        48.09 ns/op
BenchmarkArtReadWrite/frac_10
BenchmarkArtReadWrite/frac_10-10        	256331475	         4.062 ns/op

Skip List

BenchmarkSklReadWrite
BenchmarkSklReadWrite/frac_0
BenchmarkSklReadWrite/frac_0-10         	 3064340	       423.5 ns/op
BenchmarkSklReadWrite/frac_1
BenchmarkSklReadWrite/frac_1-10         	 3445074	       384.5 ns/op
BenchmarkSklReadWrite/frac_2
BenchmarkSklReadWrite/frac_2-10         	 3858036	       366.4 ns/op
BenchmarkSklReadWrite/frac_3
BenchmarkSklReadWrite/frac_3-10         	 4230139	       324.9 ns/op
BenchmarkSklReadWrite/frac_4
BenchmarkSklReadWrite/frac_4-10         	 4768282	       304.6 ns/op
BenchmarkSklReadWrite/frac_5
BenchmarkSklReadWrite/frac_5-10         	 5529624	       282.2 ns/op
BenchmarkSklReadWrite/frac_6
BenchmarkSklReadWrite/frac_6-10         	 6300565	       240.9 ns/op
BenchmarkSklReadWrite/frac_7
BenchmarkSklReadWrite/frac_7-10         	 7794916	       215.3 ns/op
BenchmarkSklReadWrite/frac_8
BenchmarkSklReadWrite/frac_8-10         	 9882706	       180.8 ns/op
BenchmarkSklReadWrite/frac_9
BenchmarkSklReadWrite/frac_9-10         	12893433	       143.9 ns/op
BenchmarkSklReadWrite/frac_10
BenchmarkSklReadWrite/frac_10-10        	334537788	         4.518 ns/op

Map with Mutex

BenchmarkReadWriteMap
BenchmarkReadWriteMap/frac_0
BenchmarkReadWriteMap/frac_0-10         	 2532152	       436.3 ns/op
BenchmarkReadWriteMap/frac_1
BenchmarkReadWriteMap/frac_1-10         	 2543882	       424.2 ns/op
BenchmarkReadWriteMap/frac_2
BenchmarkReadWriteMap/frac_2-10         	 4153843	       334.0 ns/op
BenchmarkReadWriteMap/frac_3
BenchmarkReadWriteMap/frac_3-10         	 4696628	       318.8 ns/op
BenchmarkReadWriteMap/frac_4
BenchmarkReadWriteMap/frac_4-10         	 4834476	       290.0 ns/op
BenchmarkReadWriteMap/frac_5
BenchmarkReadWriteMap/frac_5-10         	 4959322	       297.2 ns/op
BenchmarkReadWriteMap/frac_6
BenchmarkReadWriteMap/frac_6-10         	 6529040	       288.7 ns/op
BenchmarkReadWriteMap/frac_7
BenchmarkReadWriteMap/frac_7-10         	 6084861	       216.3 ns/op
BenchmarkReadWriteMap/frac_8
BenchmarkReadWriteMap/frac_8-10         	 8690770	       238.2 ns/op
BenchmarkReadWriteMap/frac_9
BenchmarkReadWriteMap/frac_9-10         	10349421	       192.2 ns/op
BenchmarkReadWriteMap/frac_10
BenchmarkReadWriteMap/frac_10-10        	 9559381	       130.3 ns/op

Sync Map

BenchmarkReadWriteSyncMap
BenchmarkReadWriteSyncMap/frac_0
BenchmarkReadWriteSyncMap/frac_0-10         	 1593249	       733.5 ns/op
BenchmarkReadWriteSyncMap/frac_1
BenchmarkReadWriteSyncMap/frac_1-10         	 1943055	       637.3 ns/op
BenchmarkReadWriteSyncMap/frac_2
BenchmarkReadWriteSyncMap/frac_2-10         	 2087097	       557.2 ns/op
BenchmarkReadWriteSyncMap/frac_3
BenchmarkReadWriteSyncMap/frac_3-10         	 2444947	       583.9 ns/op
BenchmarkReadWriteSyncMap/frac_4
BenchmarkReadWriteSyncMap/frac_4-10         	 2427559	       514.7 ns/op
BenchmarkReadWriteSyncMap/frac_5
BenchmarkReadWriteSyncMap/frac_5-10         	 2499624	       539.9 ns/op
BenchmarkReadWriteSyncMap/frac_6
BenchmarkReadWriteSyncMap/frac_6-10         	 2241314	       694.1 ns/op
BenchmarkReadWriteSyncMap/frac_7
BenchmarkReadWriteSyncMap/frac_7-10         	 2787932	       518.9 ns/op
BenchmarkReadWriteSyncMap/frac_8
BenchmarkReadWriteSyncMap/frac_8-10         	 2643914	       494.5 ns/op
BenchmarkReadWriteSyncMap/frac_9
BenchmarkReadWriteSyncMap/frac_9-10         	 3383490	       387.6 ns/op
BenchmarkReadWriteSyncMap/frac_10
BenchmarkReadWriteSyncMap/frac_10-10        	235237786	         5.011 ns/op

Bench

goos: darwin
goarch: arm64
pkg: github.com/casbin-mesh/neo/pkg/expression
BenchmarkSingleParse_govaluate
BenchmarkSingleParse_govaluate-8                     	 3065922	       392.1 ns/op
BenchmarkSingleParse
BenchmarkSingleParse-8                               	  289122	      4529 ns/op
BenchmarkEvaluationSingle_govaluate
BenchmarkEvaluationSingle_govaluate-8                	84913171	        14.12 ns/op
BenchmarkEvaluationSingle
BenchmarkEvaluationSingle-8                          	576282378	         2.146 ns/op
BenchmarkEvaluationNumericLiteral_govaluate
BenchmarkEvaluationNumericLiteral_govaluate-8        	27340820	        43.90 ns/op
BenchmarkEvaluationNumericLiteral
BenchmarkEvaluationNumericLiteral-8                  	35614648	        33.53 ns/op
BenchmarkEvaluationLiteralModifiers_govaluate
BenchmarkEvaluationLiteralModifiers_govaluate-8      	12292416	        96.38 ns/op
BenchmarkEvaluationLiteralModifiers
BenchmarkEvaluationLiteralModifiers-8                	28160942	        42.42 ns/op
BenchmarkEvaluationParameters_govaluate
BenchmarkEvaluationParameters_govaluate-8            	20129920	        59.26 ns/op
BenchmarkEvaluationParameters
BenchmarkEvaluationParameters-8                      	26136980	        46.15 ns/op
BenchmarkEvaluationParametersModifiers_govaluate
BenchmarkEvaluationParametersModifiers_govaluate-8   	 9632593	       123.8 ns/op
BenchmarkEvaluationParametersModifiers
BenchmarkEvaluationParametersModifiers-8             	13444178	        89.56 ns/op
BenchmarkEvaluationFunction_govaluate
BenchmarkEvaluationFunction_govaluate-8              	 5752874	       208.2 ns/op
BenchmarkEvaluationFunction
BenchmarkEvaluationFunction-8                        	11622660	       105.7 ns/op
BenchmarkEvaluationFunction_Naive
BenchmarkEvaluationFunction_Naive-8                  	1000000000	         0.3323 ns/op
BenchmarkEvaluationFunctionOnly
BenchmarkEvaluationFunctionOnly-8                    	10317328	       114.6 ns/op
PASS

Query Mutation (Front-end)

Background

A typically Casbin model can be defined as follows:

[request_definition]
r = sub, obj, act

[policy_definition]
p = sub, obj, act
p2 = sub, act

[policy_effect]
e = some(where (p.eft == allow))

[matchers]
m = r.sub == p.sub && r.obj == p.obj && r.act == p.act

Temporary unspported features

• Special grammer
• Expression evluator
  • Expression evaluation requires full-table scanning
    • [ ] Supported expression evaluation Index tree
• Multiple sections type
  • neo uses namespaces to isolate multiple sections instead

Model Persistence

• [x] #19
• [x] #20
• [ ] #21

Policy Persistence

• [x] #22

Policy Indexes

• [ ] #23
• [ ] grouping //TBD

Query execution

• [ ] planer
• [x] #43
• [x] #46
• [x] #47

KV store (Back-end)

• [ ] overview //TBD

Memtable

• Prefix tree
• Optimistic lock coupling
• [x] #35

inspired by:

• The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases
• The ART of Practical Synchronization
• HOT: A Height Optimized Trie Index for Main-Memory Database Systems (Optional)

Logging

• Distributed logging(Optional)

inspired by:

• Rethinking Logging, Checkpoints, and Recovery for High-Performance Storage Engines

Levels

• Tried compaction
• Sorted view range indexes

inspired by:

• REMIX: Efficient Range Query for LSM-trees

Memory buffer (Optional)

• Variable-size pages buffer pool
• Decentralized buffers

inspired by:

• Umbra: A Disk-Based System with In-Memory Performance

Policy indexes

If a request were as follows, request schema

subject,object ,action 

request

alice, /cgi/booking/12234/view, read

Basic Index

If we have an index for the subject attribute, we only need to enforce the following highlighting policy. (i.e. search the index where sub == alice)

** p, alice, /cgi/booking/*/view, (read|write) **
 
p, bob   , /cgi/booking/*/view, read
p, chrome, /cgi/booking/*/view, read
p, foobar, /cgi/booking/*/view, read

** p, alice , /cgi/booking/*/trace, read **
p, bob   , /cgi/booking/*/trace, read
p, chrome, /cgi/booking/*/trace, read

** p, alice , /cgi/booking/*/trace, read **
p, bob   , /cgi/booking/*/trace, read
p, chrome, /cgi/booking/*/trace, read

Match with regex

If we have an Index for the object attribute, we only need to enforce the following highlighting policy. (i.e. search the index where regex(obj,/cgi/booking/12234/view, read))

Note: This needs to support * wildcards and route-matching-like wildcards (such as:id, {id})

** p, alice , /cgi/booking/*/view, read ** 
** p, bob   , /cgi/booking/*/view, read ** 
** p, chrome, /cgi/booking/*/view, read ** 
** p, foobar, /cgi/booking/*/view, read ** 

p, alice , /cgi/booking/*/trace, read
p, bob   , /cgi/booking/*/trace, read
p, chrome, /cgi/booking/*/trace, read

p, alice , /cgi/booking/*/trace, read
p, bob   , /cgi/booking/*/trace, read
p, chrome, /cgi/booking/*/trace, read

Matcher

A typically Casbin matcher can be defined as follows:

m = r.sub == p.sub && r.obj == p.obj && r.act == p.act

The above example can be represented as a schematic AST as:

                                      +
                                      |
                                      |
                                      |
                                      |
                                 +----+----+
                +----------------+    &    +----------------+
                |                +---------+                |
                |                                           |
                |                                           |
                |                                           |
                |                                           |
           +----+----+                                 +----+----+
     +-----+    &    +------+                    +-----+    &    +------+
     |     +---------+      |                    |     +---------+      |
     |                      |                    |                      |
     |                      |                    |                      |
     |                      |                    |                      |
     |                      |                    |                      |
+----+----+            +----+----+          +----+----+            +----+----+
|  r.sub  |            |  p.sub  |          |  r.obj  |            |  p.obj  |
+---------+            +---------+          +---------+            +---------+

With Functions

m = g(r.sub, p.sub) && r.obj == p.obj && r.act == p.act

If a node containing a function can be parsed as

                                +---------+
                +---------------+   g()   +-----------------+
                |               +---------+                 |
                |                                           |
                |                                           |
                |                                           |
                |                                           |
           +----+----+                                 +----+----+         
           |  r.sub  |                                 |  p.sub  |         
           +---------+                                 +---------+   

While the AST can be fully represented by a binary tree, can be stored as a heap. We call this format BMacher (B stands for Binary).

Basic API

• BMatcher Writer
  • New(ast)
• BMatcher Reader
  • Eval(BSchema,request Tuple,policy Tuple) bool

See also: https://github.com/Knetic/govaluate

Policy effect

As mentioned on Casbin's official website, the Policy Effect is hard-coded, and we will continue this strategy for now.

Although we designed the syntax of policy effect as above, the current implementations only use hard-coded policy effect, as we found there's no much need for that sort of flexibility. So for now, you must use one of the built-in policy effects instead of customizing your own one. Policy effect

Policy effect | Meaning | Example -- | -- | -- some(where (p.eft == allow)) | allow-override | ACL, RBAC, etc. !some(where (p.eft == deny)) | deny-override | Deny-override some(where (p.eft == allow)) && !some(where (p.eft == deny)) | allow-and-deny | Allow-and-deny priority(p.eft) | | deny | priority | Priority subjectPriority(p.eft) | priority base on role | Subject-Priority

The above supported Policy Effects will be stored as enumeration values. (i.e. some(where (p.eft == allow)) // 0)