Have Geek Brain

ACL Fast Passing Strategies

We are currently working on a project where the main domain objects are content nodes and we are using an ACL-like system where each node in the hierarchy can contain rules that override or complement those of their parents. For example, everything is also based on roles and actions.

Node 1 - {Deny All, Allow Role1 View}
\- Node 2 - {Allow Role2 View}
   \- Node 3 - {Deny Role1 View}

In this case, the rules will be read in order from top to bottom so that node 3 can only be viewed by Role2. It's not very difficult in concept.

Getting the rules for one node can lead to some queries, get all the parents, and then recreate the list of rules and evaluate them, but the process can be cumbersome as the hierarchy can get quite deep and there can be many rules for each node.

I was thinking about preparing a table with pre-calculated rules for each node that could be recreated whenever the resolution changes and propagates to all leaf nodes of the updated one.

Do you think of any other strategy for speeding up your search and calculation of rules? Ideally this should be done in a single query, but trees are not the best structures for them.

+2


a source to share


2 answers


I would have thought the observer pattern could be adapted .

The idea would be that everyone Node

maintains a precomputed list and is simply notified by their parent of any update so that they can recheck that list.

This can be done in two different ways:

  • report that the change happened, but don't recompile anything
  • recompose on every update

I would advise going with 1

if possible, as it does not involve re-linking the whole world when the root directory is updated, and only recalculating when needed (lazy eval actually), but you may prefer the second option if you update rarely but a fast search is required (there are concurrency issues).

Let's denote Solution 1:

Root ___ Node1 ___ Node1A
     \         \__ Node1B
      \_ Node2 ___ Node2A
               \__ Node2B

Now, to begin with, none of them have subtracted anything (everything is in a dirty state) if I ask for the rules Node2A

:



  • Node2A

    realizes that he is dirty: he asks for Node2

    rules
  • Node2

    realizes that he is dirty: he asks Root

  • Root

    has no parent, so it can't be messy, it sends its rules to Node2

  • Node2

    caches the response from Root

    , concatenates its rules with those received from Root

    , and cleans up the dirty bit, it sends the merge result (cached now) toNode2A

  • Node2A

    caches, concatenates, cleans up the dirty bit and returns the result

If I then ask for the rules Node2B

:

  • Node2B

    dirty, he asks Node2

  • Node2

    clean, he answers
  • Node2B

    caches, concatenates, cleans up the dirty bit and returns the result

Please note that Node2

nothing changed.

In case of update:

  • I update Node1

    : I am using caching rules Root

    to recheck new rules and send a bit in Node1A

    and Node1B

    out to notify them that their cache is out of date.
  • Node1A

    and Node1B

    set their dirty bit, they also spread this notice if they had kids

Note that since I have cached the rules Root

, I do not need to query the object Root

, if it is a simple enough operation, you may not cache them at all: if you are not playing with distributed here, and the query Root

only includes memory feedback you might choose not to duplicate to save memory and bookkeeping.

I hope you succeed.

+3


a source


Your precomputed version stores all the permissions specific to each role in each node. You can save a bit of time and space by traversing the tree, specifying nodes as you reach them, and creating for each role an array of node numbers and permission changes only for the nodes on which the permissions are related to that role change. This produces output only linear to the size of the input tree (including its annotations). Then, when you start checking the permission for a role in a node, use the number of that node to search the array to find the point in the array that represents the most recent resolution change when you visited that node during the tour.



It might be related in some way from http://en.wikipedia.org/wiki/Range_Minimum_Query and http://en.wikipedia.org/wiki/Lowest_common_ancestor , but I really don't know if these links will help or not.

+1


a source






More articles:


All Articles