Uploaded image for project: 'jclouds'
  1. jclouds
  2. JCLOUDS-1235

openstack-nova: list-security-groups request is slow, with O(n^2) behaviour

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 2.0.0
    • Fix Version/s: 2.1.0, 2.0.1
    • Component/s: jclouds-compute
    • Labels:
      None

      Description

      On an Openstack cloud with more than a trivial number of security groups, the “list security groups” operation takes a very long time, displaying an “O(n^2)” response behaviour. For example a simple live test like this, against an Openstack deployment I am using which has around 160 security groups, some with up to about 40 rules permitting access from other groups:

          @Test(groups = { "integration", "live" }, singleThreaded = true)
          public void testListSecurityGroups() throws RunNodesException, InterruptedException, ExecutionException {
              skipIfSecurityGroupsNotSupported();
      
              ComputeService computeService = view.getComputeService();
              Optional<SecurityGroupExtension> securityGroupExtension = computeService.getSecurityGroupExtension();
              assertTrue(securityGroupExtension.isPresent(), "security extension was not present");
      
              Set<SecurityGroup> groups = securityGroupExtension.get().listSecurityGroups();
              System.out.println(groups.size());
              for (SecurityGroup group : groups) {
                  System.out.println(group);
              }
          }
      

      ran for up to an hour before I gave up waiting. The problem can be seen in the following stack trace:

      	  at sun.net.www.protocol.http.HttpURLConnection.getInputStream(HttpURLConnection.java:1440)
      	  at sun.net.www.protocol.https.HttpsURLConnectionImpl.getInputStream(HttpsURLConnectionImpl.java:254)
      	  - locked <0x170a> (a sun.net.www.protocol.https.HttpsURLConnectionImpl)
      	  at org.jclouds.http.internal.JavaUrlHttpCommandExecutorService.invoke(JavaUrlHttpCommandExecutorService.java:97)
      	  at org.jclouds.http.internal.JavaUrlHttpCommandExecutorService.invoke(JavaUrlHttpCommandExecutorService.java:65)
      	  at org.jclouds.http.internal.BaseHttpCommandExecutorService.invoke(BaseHttpCommandExecutorService.java:100)
      	  at org.jclouds.rest.internal.InvokeHttpMethod.invoke(InvokeHttpMethod.java:90)
      	  at org.jclouds.rest.internal.InvokeHttpMethod.apply(InvokeHttpMethod.java:73)
      	  at org.jclouds.rest.internal.InvokeHttpMethod.apply(InvokeHttpMethod.java:44)
      	  at org.jclouds.reflect.FunctionalReflection$FunctionalInvocationHandler.handleInvocation(FunctionalReflection.java:117)
      	  at com.google.common.reflect.AbstractInvocationHandler.invoke(AbstractInvocationHandler.java:87)
      	  at com.sun.proxy.$Proxy88.list(Unknown Source:-1)
      	  at org.jclouds.openstack.nova.v2_0.predicates.FindSecurityGroupWithNameAndReturnTrue.apply(FindSecurityGroupWithNameAndReturnTrue.java:66)
      	  at org.jclouds.openstack.nova.v2_0.predicates.FindSecurityGroupWithNameAndReturnTrue.apply(FindSecurityGroupWithNameAndReturnTrue.java:44)
      	  at org.jclouds.util.Predicates2$RetryablePredicate.apply(Predicates2.java:117)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.SecurityGroupRuleToIpPermission$1.apply(SecurityGroupRuleToIpPermission.java:92)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.SecurityGroupRuleToIpPermission$1.apply(SecurityGroupRuleToIpPermission.java:87)
      	  at com.google.common.collect.Iterators$7.computeNext(Iterators.java:652)
      	  at com.google.common.collect.AbstractIterator.tryToComputeNext(AbstractIterator.java:143)
      	  at com.google.common.collect.AbstractIterator.hasNext(AbstractIterator.java:138)
      	  at com.google.common.collect.Iterators.getNext(Iterators.java:865)
      	  at com.google.common.collect.Iterables.getFirst(Iterables.java:775)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.SecurityGroupRuleToIpPermission.apply(SecurityGroupRuleToIpPermission.java:73)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.SecurityGroupRuleToIpPermission.apply(SecurityGroupRuleToIpPermission.java:48)
      	  at com.google.common.collect.Iterators$8.transform(Iterators.java:799)
      	  at com.google.common.collect.TransformedIterator.next(TransformedIterator.java:48)
      	  at com.google.common.collect.ImmutableCollection$Builder.addAll(ImmutableCollection.java:281)
      	  at com.google.common.collect.ImmutableCollection$ArrayBasedBuilder.addAll(ImmutableCollection.java:360)
      	  at com.google.common.collect.ImmutableSet$Builder.addAll(ImmutableSet.java:508)
      	  at org.jclouds.compute.domain.SecurityGroupBuilder.ipPermissions(SecurityGroupBuilder.java:43)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.NovaSecurityGroupToSecurityGroup.apply(NovaSecurityGroupToSecurityGroup.java:61)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.NovaSecurityGroupToSecurityGroup.apply(NovaSecurityGroupToSecurityGroup.java:39)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.NovaSecurityGroupInRegionToSecurityGroup.apply(NovaSecurityGroupInRegionToSecurityGroup.java:61)
      	  at org.jclouds.openstack.nova.v2_0.compute.functions.NovaSecurityGroupInRegionToSecurityGroup.apply(NovaSecurityGroupInRegionToSecurityGroup.java:43)
      	  at com.google.common.collect.Iterators$8.transform(Iterators.java:799)
      	  at com.google.common.collect.TransformedIterator.next(TransformedIterator.java:48)
      	  at com.google.common.collect.ImmutableCollection$Builder.addAll(ImmutableCollection.java:301)
      	  at com.google.common.collect.ImmutableSet$Builder.addAll(ImmutableSet.java:522)
      	  at com.google.common.collect.ImmutableSet.copyOf(ImmutableSet.java:321)
      	  at com.google.common.collect.ImmutableSet.copyOf(ImmutableSet.java:300)
      	  at org.jclouds.openstack.nova.v2_0.compute.extensions.NovaSecurityGroupExtension.listSecurityGroupsInLocation(NovaSecurityGroupExtension.java:116)
      	  at org.jclouds.openstack.nova.v2_0.compute.extensions.NovaSecurityGroupExtension.listSecurityGroupsInLocation(NovaSecurityGroupExtension.java:109)
      
      

      The listSecurityGroupsInRegion operation invokes pollSecurityGroupsByRegion
      which lists all security groups

      https://github.com/apache/jclouds/blob/rel/jclouds-2.0.0/apis/openstack-nova/src/main/java/org/jclouds/openstack/nova/v2_0/compute/extensions/NovaSecurityGroupExtension.java#L362

      return sgApi.get().list().transform(groupToGroupInRegion(from)).toSet();
      

      and then it transforms each in turn from a Nova object to a jclouds SecurityGroup using the injected groupConverter

      https://github.com/apache/jclouds/blob/rel/jclouds-2.0.0/apis/openstack-nova/src/main/java/org/jclouds/openstack/nova/v2_0/compute/extensions/NovaSecurityGroupExtension.java#L114-L115

      Iterable<SecurityGroup> groups = transform(filter(rawGroups, notNull()),
                    groupConverter);
      

      The converter is NovaSecurityGroupInRegionToSecurityGroup which implements Function<SecurityGroupInRegion, SecurityGroup>

      This is where the trouble arises - this signature transforms one Nova group to its jclouds representation independently of any others. However, because a security groups’s ingress rules can refer to other groups, it’s not actually possible to do this; you need information about the other groups that may be referred to in the ingress rules.

      Hence in the converter’s operation, where it delegates to NovaSecurityGroupToSecurityGroup

      https://github.com/apache/jclouds/blob/rel/jclouds-2.0.0/apis/openstack-nova/src/main/java/org/jclouds/openstack/nova/v2_0/compute/functions/NovaSecurityGroupToSecurityGroup.java#L61

      That class does the conversion of each ingress rule permitting access to a group using an injected Function<SecurityGroupRule, IpPermission> converter, ruleToPermission:

      builder.ipPermissions(transform(group.getRules(), ruleToPermission));
      

      This rule converter is SecurityGroupRuleToIpPermission, which, for every such rule, checks it against every location with a predicate isSecurityGroupInRegion
      https://github.com/apache/jclouds/blob/rel/jclouds-2.0.0/apis/openstack-nova/src/main/java/org/jclouds/openstack/nova/v2_0/compute/functions/SecurityGroupRuleToIpPermission.java#L73-L74

      String region = getFirst(filter(locationIndex.get().keySet(), isSecurityGroupInRegion(rule.getGroup().getName())), null);
      

      This method works using a predicate returnSecurityGroupExistsInRegion that is again injected by Guice, from FindSecurityGroupWithNameAndReturnTrue. There is no information available to this class about the list of security groups that was fetched at the start of this process, so it must find the security group with the name by doing another listing of the security groups, giving the n^2 behaviour, and then checking the group name against each result.

      https://github.com/apache/jclouds/blob/rel/jclouds-2.0.0/apis/openstack-nova/src/main/java/org/jclouds/openstack/nova/v2_0/predicates/FindSecurityGroupWithNameAndReturnTrue.java#L66

      SecurityGroup returnVal = Iterables.find(api.get().list(), new Predicate<SecurityGroup>() {
      

      Thus we have “for every group * every ingress-rule-from-group * every location * every group”.

        Activity

        Hide
        jira-bot ASF subversion and git services added a comment -

        Commit c4245acd35b00c238275ef133d5cb836601acb6b in jclouds's branch refs/heads/2.0.x from Geoff Macartney
        [ https://git-wip-us.apache.org/repos/asf?p=jclouds.git;h=c4245ac ]

        Fix O(n^2) response time for "list-security-groups" on openstack-nova.

        For https://issues.apache.org/jira/browse/JCLOUDS-1235.

        This change takes the approach of storing the information about the
        overall list of groups within the `SecurityGroupInRegion` when it is
        created, so that any subsequent conversion operation has access to all
        the groups in the same region as the one to be converted.

        It also collapses the functionality of `NovaSecurityGroupToSecurityGroup`,
        `SecurityGroupRuleToIpPermission` and `FindSecurityGroupWithNameAndReturnTrue`
        all into `NovaSecurityGroupInRegionToSecurityGroup`, and deletes the
        now unused-classes SecurityGroupRuleToIpPermission,
        NovaSecurityGroupToSecurityGroup and associated tests.

        Show
        jira-bot ASF subversion and git services added a comment - Commit c4245acd35b00c238275ef133d5cb836601acb6b in jclouds's branch refs/heads/2.0.x from Geoff Macartney [ https://git-wip-us.apache.org/repos/asf?p=jclouds.git;h=c4245ac ] Fix O(n^2) response time for "list-security-groups" on openstack-nova. For https://issues.apache.org/jira/browse/JCLOUDS-1235 . This change takes the approach of storing the information about the overall list of groups within the `SecurityGroupInRegion` when it is created, so that any subsequent conversion operation has access to all the groups in the same region as the one to be converted. It also collapses the functionality of `NovaSecurityGroupToSecurityGroup`, `SecurityGroupRuleToIpPermission` and `FindSecurityGroupWithNameAndReturnTrue` all into `NovaSecurityGroupInRegionToSecurityGroup`, and deletes the now unused-classes SecurityGroupRuleToIpPermission, NovaSecurityGroupToSecurityGroup and associated tests.
        Hide
        jira-bot ASF subversion and git services added a comment -

        Commit 717b75a34e261689f900c7f623088a866932a33e in jclouds's branch refs/heads/master from Geoff Macartney
        [ https://git-wip-us.apache.org/repos/asf?p=jclouds.git;h=717b75a ]

        Fix O(n^2) response time for "list-security-groups" on openstack-nova.

        For https://issues.apache.org/jira/browse/JCLOUDS-1235.

        This change takes the approach of storing the information about the
        overall list of groups within the `SecurityGroupInRegion` when it is
        created, so that any subsequent conversion operation has access to all
        the groups in the same region as the one to be converted.

        It also collapses the functionality of `NovaSecurityGroupToSecurityGroup`,
        `SecurityGroupRuleToIpPermission` and `FindSecurityGroupWithNameAndReturnTrue`
        all into `NovaSecurityGroupInRegionToSecurityGroup`, and deletes the
        now unused-classes SecurityGroupRuleToIpPermission,
        NovaSecurityGroupToSecurityGroup and associated tests.

        Show
        jira-bot ASF subversion and git services added a comment - Commit 717b75a34e261689f900c7f623088a866932a33e in jclouds's branch refs/heads/master from Geoff Macartney [ https://git-wip-us.apache.org/repos/asf?p=jclouds.git;h=717b75a ] Fix O(n^2) response time for "list-security-groups" on openstack-nova. For https://issues.apache.org/jira/browse/JCLOUDS-1235 . This change takes the approach of storing the information about the overall list of groups within the `SecurityGroupInRegion` when it is created, so that any subsequent conversion operation has access to all the groups in the same region as the one to be converted. It also collapses the functionality of `NovaSecurityGroupToSecurityGroup`, `SecurityGroupRuleToIpPermission` and `FindSecurityGroupWithNameAndReturnTrue` all into `NovaSecurityGroupInRegionToSecurityGroup`, and deletes the now unused-classes SecurityGroupRuleToIpPermission, NovaSecurityGroupToSecurityGroup and associated tests.
        Hide
        geomacy Geoff Macartney added a comment -

        I have raised a candidate fix for this in https://github.com/jclouds/jclouds/pull/1059.

        Show
        geomacy Geoff Macartney added a comment - I have raised a candidate fix for this in https://github.com/jclouds/jclouds/pull/1059 .

          People

          • Assignee:
            Unassigned
            Reporter:
            geomacy Geoff Macartney
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development