BUG-509: use concurrent hash-trie Map

This patch switches to using concurrent hash-trie map for metadata
tracking. It has the nice feature of having O(1) concurrent snapshots,
which should give us better performance when dealing with large children
bases.

This is a trade-off, please refer to yangtools.util.MapAdaptor for
system properties which tune its behavior.

Change-Id: I2ddb81a1296cc17528a605eeaeda1f303560fb55
Signed-off-by: Robert Varga <rovarga@cisco.com>

diff --git a/opendaylight/commons/opendaylight/pom.xml b/opendaylight/commons/opendaylight/pom.xml
index 47dbe123f8a8cd98ea701aad5817d8e0b194eb20..c166f668ccd48e9419e79536c7b39523b7f04238 100644 (file)
--- a/opendaylight/commons/opendaylight/pom.xml
+++ b/opendaylight/commons/opendaylight/pom.xml
@@ -49,6 +49,7 @@
     <containermanager.version>0.5.2-SNAPSHOT</containermanager.version>
     <controllermanager.northbound.version>0.0.2-SNAPSHOT</controllermanager.northbound.version>
     <corsfilter.version>7.0.42</corsfilter.version>
+    <ctrie.version>0.2.0</ctrie.version>
     <devices.web.version>0.4.2-SNAPSHOT</devices.web.version>
     <eclipse.persistence.version>2.5.0</eclipse.persistence.version>
     <!-- enforcer version -->
@@ -240,6 +241,11 @@
         <artifactId>jackson-module-jaxb-annotations</artifactId>
         <version>${jackson.version}</version>
       </dependency>
+      <dependency>
+        <groupId>com.github.romix</groupId>
+        <artifactId>java-concurrent-hash-trie-map</artifactId>
+        <version>${ctrie.version}</version>
+      </dependency>
       <dependency>
         <groupId>com.google.code.findbugs</groupId>
         <artifactId>jsr305</artifactId>
@@ -255,6 +261,7 @@
         <artifactId>guava</artifactId>
         <version>${guava.version}</version>
       </dependency>
+
       <dependency>
         <groupId>com.sun.jersey</groupId>
         <artifactId>jersey-client</artifactId>

diff --git a/opendaylight/md-sal/sal-dom-broker/pom.xml b/opendaylight/md-sal/sal-dom-broker/pom.xml
index 456af8353bd8610ac7a41047a34abe666f1b770d..bac9146bf5395f29a7ce9c8fa733802b0cf42259 100644 (file)
--- a/opendaylight/md-sal/sal-dom-broker/pom.xml
+++ b/opendaylight/md-sal/sal-dom-broker/pom.xml
@@ -10,6 +10,10 @@
   <packaging>bundle</packaging>
 
   <dependencies>
+    <dependency>
+      <groupId>com.github.romix</groupId>
+      <artifactId>java-concurrent-hash-trie-map</artifactId>
+    </dependency>
     <dependency>
       <groupId>com.google.guava</groupId>
       <artifactId>guava</artifactId>
@@ -50,6 +54,7 @@
       <groupId>org.opendaylight.yangtools</groupId>
       <artifactId>yang-parser-impl</artifactId>
     </dependency>
+
     <dependency>
       <groupId>org.slf4j</groupId>
       <artifactId>slf4j-api</artifactId>
@@ -88,6 +93,7 @@
                             org.opendaylight.yangtools.yang.util,
                             org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.controller.md.sal.dom.impl.rev131028.*</Private-Package>
             <Import-Package>*</Import-Package>
+            <Embed-Dependency>java-concurrent-hash-trie-map;inline=true</Embed-Dependency>
           </instructions>
         </configuration>
       </plugin>

diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/ContainerNode.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/ContainerNode.java
index 8f74f60498aeb515435e65b5fb4d5dd3725d9be2..3ca8db2405e44866d13f3e35adcf40b61e6d7381 100644 (file)
--- a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/ContainerNode.java
+++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/ContainerNode.java
@@ -7,10 +7,10 @@
  */
 package org.opendaylight.controller.md.sal.dom.store.impl.tree.spi;
 
-import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
 
+import org.opendaylight.yangtools.util.MapAdaptor;
 import org.opendaylight.yangtools.yang.data.api.InstanceIdentifier.PathArgument;
 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodeContainer;
@@ -50,14 +50,14 @@ final class ContainerNode extends AbstractTreeNode {
     }
 
     private static final class Mutable implements MutableTreeNode {
-        private final Map<PathArgument, TreeNode> children;
         private final Version version;
+        private Map<PathArgument, TreeNode> children;
         private NormalizedNode<?, ?> data;
         private Version subtreeVersion;
 
         private Mutable(final ContainerNode parent) {
             this.data = parent.getData();
-            this.children = new HashMap<>(parent.children);
+            this.children = MapAdaptor.getDefaultInstance().takeSnapshot(parent.children);
             this.subtreeVersion = parent.getSubtreeVersion();
             this.version = parent.getVersion();
         }
@@ -84,15 +84,11 @@ final class ContainerNode extends AbstractTreeNode {
 
         @Override
         public TreeNode seal() {
-            final Map<PathArgument, TreeNode> realChildren;
+            final TreeNode ret = new ContainerNode(data, version, MapAdaptor.getDefaultInstance().optimize(children), subtreeVersion);
 
-            if (children.isEmpty()) {
-                realChildren = Collections.emptyMap();
-            } else {
-                realChildren = children;
-            }
-
-            return new ContainerNode(data, version, realChildren, subtreeVersion);
+            // This forces a NPE if this class is accessed again. Better than corruption.
+            children = null;
+            return ret;
         }
 
         @Override
@@ -103,8 +99,8 @@ final class ContainerNode extends AbstractTreeNode {
 
     private static ContainerNode create(final Version version, final NormalizedNode<?, ?> data,
             final Iterable<NormalizedNode<?, ?>> children) {
-        final Map<PathArgument, TreeNode> map = new HashMap<>();
 
+        final Map<PathArgument, TreeNode> map = new HashMap<>();
         for (NormalizedNode<?, ?> child : children) {
             map.put(child.getIdentifier(), TreeNodeFactory.createTreeNode(child, version));
         }

diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/MutableTreeNode.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/MutableTreeNode.java
index dd3672cf113e8a785acfa434ba112079fa305f90..7ab309607b908e84e0603840b9aa6bc31a7c61c5 100644 (file)
--- a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/MutableTreeNode.java
+++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/MutableTreeNode.java
@@ -11,6 +11,11 @@ import org.opendaylight.controller.md.sal.dom.store.impl.tree.StoreTreeNode;
 import org.opendaylight.yangtools.yang.data.api.InstanceIdentifier.PathArgument;
 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
 
+/**
+ * A mutable tree node. This is a transient view materialized from a pre-existing
+ * node. Modifications are isolated. Once this object is {@link #seal()}-ed,
+ * any interactions with it will result in undefined behavior.
+ */
 public interface MutableTreeNode extends StoreTreeNode<TreeNode> {
     void setData(NormalizedNode<?, ?> data);
     void setSubtreeVersion(Version subtreeVersion);

diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/TreeNodeFactory.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/TreeNodeFactory.java
index c5d174caad9dcbe35ac81d83dcce39e7291f0364..9547628ae9565235d0519328d674953e83f54c68 100644 (file)
--- a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/TreeNodeFactory.java
+++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/tree/spi/TreeNodeFactory.java
@@ -11,6 +11,10 @@ import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodeContainer;
 import org.opendaylight.yangtools.yang.data.api.schema.OrderedNodeContainer;
 
+/**
+ * Public entrypoint for other packages. Allows instantiating a tree node
+ * with specified version.
+ */
 public final class TreeNodeFactory {
     private TreeNodeFactory() {
         throw new UnsupportedOperationException("Utility class should not be instantiated");