[GitHub] liubao68 closed pull request #762: [SCB-654] bug fix: DiscoveryTree concurrency problems

[GitBox <gi...@apache.org>]

liubao68 closed pull request #762: [SCB-654] bug fix: DiscoveryTree concurrency problems
URL: https://github.com/apache/incubator-servicecomb-java-chassis/pull/762
 
 
   

This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:

As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):

diff --git a/foundations/foundation-common/src/main/java/org/apache/servicecomb/foundation/common/cache/VersionedCache.java b/foundations/foundation-common/src/main/java/org/apache/servicecomb/foundation/common/cache/VersionedCache.java
index daf9770f4..eccdbac25 100644
--- a/foundations/foundation-common/src/main/java/org/apache/servicecomb/foundation/common/cache/VersionedCache.java
+++ b/foundations/foundation-common/src/main/java/org/apache/servicecomb/foundation/common/cache/VersionedCache.java
@@ -129,6 +129,10 @@ public boolean isExpired(VersionedCache newCache) {
     return newCache.cacheVersion - cacheVersion > 0;
   }
 
+  public boolean isSameVersion(VersionedCache newCache) {
+    return newCache.cacheVersion == cacheVersion;
+  }
+
   public boolean isEmpty() {
     return isEmpty.isEmpty();
   }
diff --git a/foundations/foundation-common/src/test/java/org/apache/servicecomb/foundation/common/cache/TestVersionedCache.java b/foundations/foundation-common/src/test/java/org/apache/servicecomb/foundation/common/cache/TestVersionedCache.java
index e568411cb..b29093744 100644
--- a/foundations/foundation-common/src/test/java/org/apache/servicecomb/foundation/common/cache/TestVersionedCache.java
+++ b/foundations/foundation-common/src/test/java/org/apache/servicecomb/foundation/common/cache/TestVersionedCache.java
@@ -125,4 +125,14 @@ public void isExpired() {
     Assert.assertFalse(cacheOld.isExpired(cacheOld));
     Assert.assertFalse(cacheNew.isExpired(cacheOld));
   }
+
+  @Test
+  public void isSameVersion() {
+    VersionedCache cacheOld = new VersionedCache().autoCacheVersion();
+    VersionedCache cacheNew = new VersionedCache().autoCacheVersion();
+    VersionedCache cacheSame = new VersionedCache().cacheVersion(cacheNew.cacheVersion());
+
+    Assert.assertFalse(cacheOld.isSameVersion(cacheNew));
+    Assert.assertTrue(cacheSame.isSameVersion(cacheNew));
+  }
 }
diff --git a/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTree.java b/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTree.java
index ee4e2736f..e453e47ed 100644
--- a/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTree.java
+++ b/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTree.java
@@ -28,10 +28,54 @@
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
+/**
+ * <a href="https://servicecomb.atlassian.net/browse/JAV-479">help to understand DiscoveryTree</a>
+ * <pre>
+ * DiscoveryTree is used to:
+ * 1.get all instances by app/microserviceName/versionRule
+ * 2.filter all instances set, and output another set, the output set is instance or something else, this depend on filter set
+ *
+ * DiscoveryFilter have different types:
+ * 1.normal filter: just filter input set
+ * 2.grouping filter: will split input set to groups
+ * 3.convert filter: eg: convert from instance to endpoint
+ * different types can composite in one filter
+ *
+ * features:
+ * 1.every group combination(eg:1.0.0-2.0.0/1.0.0+/self/RESTful) relate to a loadBalancer instance
+ * 2.if some filter output set is empty, DiscoveryTree can support try refilter logic
+ *   eg: if there is no available instances in self AZ, can refilter in other AZ
+ *   red arrows in <a href="https://servicecomb.atlassian.net/browse/JAV-479">help to understand DiscoveryTree</a>, show the refilter logic
+ * 3.every filter must try to cache result, avoid calculate every time.
+ *
+ * usage:
+ * 1.declare a field: DiscoveryTree discoveryTree = new DiscoveryTree();
+ * 2.initialize:
+ *     discoveryTree.loadFromSPI(DiscoveryFilter.class);
+ *     // add filters by your requirement
+ *     discoveryTree.addFilter(new EndpointDiscoveryFilter());
+ *     discoveryTree.sort();
+ * 3.filter for a invocation:
+ *     DiscoveryContext context = new DiscoveryContext();
+ *     context.setInputParameters(invocation);
+ *     VersionedCache endpointsVersionedCache = discoveryTree.discovery(context,
+ *         invocation.getAppId(),
+ *         invocation.getMicroserviceName(),
+ *         invocation.getMicroserviceVersionRule());
+ *     if (endpointsVersionedCache.isEmpty()) {
+ *       // 404 not found logic
+ *       ......
+ *       return;
+ *     }
+ *
+ *     // result is endpoints or something else, which is depends on your filter set
+ *     List&lt;Endpoint&gt; endpoints = endpointsVersionedCache.data();
+ *</pre>
+ */
 public class DiscoveryTree {
   private static final Logger LOGGER = LoggerFactory.getLogger(DiscoveryTree.class);
 
-  private DiscoveryTreeNode root;
+  private volatile DiscoveryTreeNode root;
 
   private final Object lock = new Object();
 
@@ -56,6 +100,10 @@ public void sort() {
     }
   }
 
+  protected boolean isMatch(VersionedCache existing, VersionedCache inputCache) {
+    return existing != null && existing.isSameVersion(inputCache);
+  }
+
   protected boolean isExpired(VersionedCache existing, VersionedCache inputCache) {
     return existing == null || existing.isExpired(inputCache);
   }
@@ -71,32 +119,38 @@ public DiscoveryTreeNode discovery(DiscoveryContext context, String appId, Strin
   }
 
   public DiscoveryTreeNode discovery(DiscoveryContext context, VersionedCache inputCache) {
-    // must save root, otherwise, maybe use old cache to create children in new root
+    DiscoveryTreeNode tmpRoot = getOrCreateRoot(inputCache);
+    DiscoveryTreeNode parent = tmpRoot.children()
+        .computeIfAbsent(inputCache.name(), name -> new DiscoveryTreeNode().fromCache(inputCache));
+    return doDiscovery(context, parent);
+  }
+
+  protected DiscoveryTreeNode getOrCreateRoot(VersionedCache inputCache) {
     DiscoveryTreeNode tmpRoot = root;
-    if (isExpired(tmpRoot, inputCache)) {
-      synchronized (lock) {
-        if (isExpired(tmpRoot, inputCache)) {
-          root = new DiscoveryTreeNode().cacheVersion(inputCache.cacheVersion());
-          tmpRoot = root;
-        }
-      }
+    if (isMatch(tmpRoot, inputCache)) {
+      return tmpRoot;
     }
 
-    // tmpRoot.cacheVersion() >= inputCache.cacheVersion()
-    // 1) thread 1, use v1 inputCache, did not assign tmpRoot, and suspended
-    // 2) thread 2, use v2 inputCache, update root instance
-    // 3) thread 1 go on, in this time, tmpRoot.cacheVersion() > inputCache.cacheVersion()
-    //    is not expired
-    //    but if create old children in new version root, it's a wrong logic
-    //    and this is rarely to happen, so we only let it go with a real temporary root.
-    if (tmpRoot.cacheVersion() > inputCache.cacheVersion()) {
-      tmpRoot = new DiscoveryTreeNode().cacheVersion(inputCache.cacheVersion());
+    synchronized (lock) {
+      if (isExpired(root, inputCache)) {
+        // not initialized or inputCache newer than root, create new root
+        root = new DiscoveryTreeNode().cacheVersion(inputCache.cacheVersion());
+        return root;
+      }
+
+      if (root.isSameVersion(inputCache)) {
+        // reuse root directly
+        return root;
+      }
     }
 
-    DiscoveryTreeNode parent = tmpRoot.children().computeIfAbsent(inputCache.name(), name -> {
-      return new DiscoveryTreeNode().fromCache(inputCache);
-    });
-    return doDiscovery(context, parent);
+    // root newer than inputCache, it's a minimal probability event:
+    // 1) thread 1, use v1 inputCache, run into getOrCreateRoot, but did not run any code yet, suspend and switch to thread 2
+    // 2) thread 2, use v2 inputCache, v2 > v1, create new root
+    // 3) thread 1 go on, then root is newer than inputCache
+    //    but if create old children in new version root, it's a wrong logic
+    // so just create a temporary root for the inputCache, DO NOT assign to root
+    return new DiscoveryTreeNode().cacheVersion(inputCache.cacheVersion());
   }
 
   protected DiscoveryTreeNode doDiscovery(DiscoveryContext context, DiscoveryTreeNode parent) {
diff --git a/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTreeNode.java b/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTreeNode.java
index 5e81302bc..b764937ba 100644
--- a/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTreeNode.java
+++ b/service-registry/src/main/java/org/apache/servicecomb/serviceregistry/discovery/DiscoveryTreeNode.java
@@ -23,7 +23,7 @@
 import org.apache.servicecomb.foundation.common.concurrent.ConcurrentHashMapEx;
 
 public class DiscoveryTreeNode extends VersionedCache {
-  private boolean childrenInited;
+  private volatile boolean childrenInited;
 
   private int level;
 
diff --git a/service-registry/src/test/java/org/apache/servicecomb/serviceregistry/discovery/TestDiscoveryTree.java b/service-registry/src/test/java/org/apache/servicecomb/serviceregistry/discovery/TestDiscoveryTree.java
index b877fe03d..f34555f16 100644
--- a/service-registry/src/test/java/org/apache/servicecomb/serviceregistry/discovery/TestDiscoveryTree.java
+++ b/service-registry/src/test/java/org/apache/servicecomb/serviceregistry/discovery/TestDiscoveryTree.java
@@ -83,6 +83,23 @@ public void sort(@Mocked DiscoveryFilter f1, @Mocked DiscoveryFilter f2) {
     Assert.assertThat(filters, Matchers.contains(f1, f2));
   }
 
+  @Test
+  public void isMatch_existingNull() {
+    Assert.assertFalse(discoveryTree.isMatch(null, null));
+  }
+
+  @Test
+  public void isMatch_yes() {
+    parent.cacheVersion(1);
+    Assert.assertTrue(discoveryTree.isMatch(new DiscoveryTreeNode().cacheVersion(1), parent));
+  }
+
+  @Test
+  public void isMatch_no() {
+    parent.cacheVersion(0);
+    Assert.assertFalse(discoveryTree.isExpired(new DiscoveryTreeNode().cacheVersion(1), parent));
+  }
+
   @Test
   public void isExpired_existingNull() {
     Assert.assertTrue(discoveryTree.isExpired(null, null));
@@ -233,4 +250,36 @@ public void avoidConcurrentProblem() {
     discoveryTree.discovery(context, new VersionedCache().cacheVersion(0).name("input"));
     Assert.assertTrue(parent.children().isEmpty());
   }
+
+  @Test
+  public void getOrCreateRoot_match() {
+    Deencapsulation.setField(discoveryTree, "root", parent);
+
+    DiscoveryTreeNode root = discoveryTree.getOrCreateRoot(parent);
+
+    Assert.assertSame(parent, root);
+  }
+
+  @Test
+  public void getOrCreateRoot_expired() {
+    Deencapsulation.setField(discoveryTree, "root", parent);
+
+    VersionedCache inputCache = new VersionedCache().cacheVersion(parent.cacheVersion() + 1);
+    DiscoveryTreeNode root = discoveryTree.getOrCreateRoot(inputCache);
+
+    Assert.assertEquals(inputCache.cacheVersion(), root.cacheVersion());
+    Assert.assertSame(Deencapsulation.getField(discoveryTree, "root"), root);
+  }
+
+
+  @Test
+  public void getOrCreateRoot_tempRoot() {
+    Deencapsulation.setField(discoveryTree, "root", parent);
+
+    VersionedCache inputCache = new VersionedCache().cacheVersion(parent.cacheVersion() - 1);
+    DiscoveryTreeNode root = discoveryTree.getOrCreateRoot(inputCache);
+
+    Assert.assertEquals(inputCache.cacheVersion(), root.cacheVersion());
+    Assert.assertNotSame(Deencapsulation.getField(discoveryTree, "root"), root);
+  }
 }


 

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services