Spring Security
  1. Spring Security
  2. SEC-593

org.acegisecurity.afterinvocation.AclEntryAfterInvocationCollectionFilteringProvider is slow

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Complete
    • Affects Version/s: 1.0.3
    • Fix Version/s: 3.1.0.M1
    • Component/s: ACLs
    • Labels:
      None
    • Environment:
      ubuntu feisty, Java HotSpot(TM) Client VM (build 1.6.0_01-b06, mixed mode, sharing)
      tomcat 5.5.16

      Description

      AclEntryAfterInvocationCollectionFilteringProvider is very slow for 2 reasons:

      1.) The hasPermission(Authentication, Object) method in AbstractAclProvider is called once for every object in the collection being filtered, which in turn calls aclService.readAclById(..). The net result is that if the Acl cache is empty (or doesn't yet contain Acls for the domain objects being checked) an Acl query to the database will occur for each item in the Collection. This is inefficient and gets very slow when filtering large collections. Since AclService supports looking up more than one Acl at a time, it makes more sense to collect a batch of ObjectIdentities and perform a lookup on the batch.

      2.) CollectionFilterer which is used by AclEntryAfterInvocationCollectionFilteringProvider to remove objects from the Collection being filtered exhibits O(n^2) performance when the collection being filtered has only sequential access (i.e. LinkedList or ArrayList). This is because a Set of objects to be removed from the collection is collected during iteration, and then each is removed when getFilteredObject() is called.

      I've written a AclEntryAfterInvocationCollectionBatchingFilteringProvider and a FastCollectionFilterer plus some unit tests to solve these problems. In our application when the AclCache is empty filtering ~3500 objects went from ~9sec down to ~2sec.

      1. AclEntryAfterInvocationCollectionBatchingFilteringProvider.java
        10 kB
        Simon van der Sluis
      2. FastCollectionFilterer.java
        4 kB
        Simon van der Sluis
      3. FastCollectionFiltererTest.java
        6 kB
        Simon van der Sluis
      4. FastCopyCollectionFilterer.java
        2 kB
        Simon van der Sluis
      5. FastCopyCollectionFiltererTest.java
        7 kB
        Simon van der Sluis

        Activity

        Hide
        Simon van der Sluis added a comment -

        Found the unit test

        Show
        Simon van der Sluis added a comment - Found the unit test
        Hide
        Ryan Gardner added a comment -

        Can I integrate this into a 2.0.4 application or does it have dependencies upon code in the 3.0 version?

        Show
        Ryan Gardner added a comment - Can I integrate this into a 2.0.4 application or does it have dependencies upon code in the 3.0 version?
        Hide
        Simon van der Sluis added a comment -

        It was written for acegi 1.0.3

        I'm guessing with a few minor changes (class names and imports) it would probably work in 2.0.4.
        Since it's all based on dependency injection, it's pretty easy to keep the new version in your own code base, and inject it via Spring config.

        Be sure to use the correct one FastCopyCollectionFilterer.java, as the first one I attached was buggy.

        Show
        Simon van der Sluis added a comment - It was written for acegi 1.0.3 I'm guessing with a few minor changes (class names and imports) it would probably work in 2.0.4. Since it's all based on dependency injection, it's pretty easy to keep the new version in your own code base, and inject it via Spring config. Be sure to use the correct one FastCopyCollectionFilterer.java, as the first one I attached was buggy.
        Hide
        Luke Taylor added a comment -

        Things have changed a bit for the 3.0 release - it's expected that the most common filtering mechanism wil be using EL, which may or may not include the use of ACLs. This means that the code which is doing the filtering (and deciding what to retain) is unaware of the ACL system when it evaluates a "hasPermission()" expression for a particular object in the collection. We could still probably implement this optimization by adding an extra interface on the AclPermissionEvaluator which would batch load the Acls, e.g.

        interface PermissionCacheOptimizer

        { cachePermissionsFor(Authentication a, Collection objects); }

        and adding a check in the DefaultMethodexpressionHandler whether its configured PermissionEvaluator also implements this interface.

        Show
        Luke Taylor added a comment - Things have changed a bit for the 3.0 release - it's expected that the most common filtering mechanism wil be using EL, which may or may not include the use of ACLs. This means that the code which is doing the filtering (and deciding what to retain) is unaware of the ACL system when it evaluates a "hasPermission()" expression for a particular object in the collection. We could still probably implement this optimization by adding an extra interface on the AclPermissionEvaluator which would batch load the Acls, e.g. interface PermissionCacheOptimizer { cachePermissionsFor(Authentication a, Collection objects); } and adding a check in the DefaultMethodexpressionHandler whether its configured PermissionEvaluator also implements this interface.
        Hide
        Luke Taylor added a comment -

        I've implemented the PermissionCacheOptimizer (plus as Acl implementation which batch loads Acls). This is now invoked with the list of objects to be filtered, prior to doing the actual filtering. It should be injected into DefaultMethodSecurityExpressionHandler.

        The actual filtering has changed quite a bit, so if additional optimizations are required, please open new issue(s) against the current codebase.

        Show
        Luke Taylor added a comment - I've implemented the PermissionCacheOptimizer (plus as Acl implementation which batch loads Acls). This is now invoked with the list of objects to be filtered, prior to doing the actual filtering. It should be injected into DefaultMethodSecurityExpressionHandler. The actual filtering has changed quite a bit, so if additional optimizations are required, please open new issue(s) against the current codebase.

          People

          • Assignee:
            Luke Taylor
            Reporter:
            Simon van der Sluis
          • Votes:
            1 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: