helix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hu...@apache.org
Subject [helix] 08/11: Add TrieRoutingData constructor (#731)
Date Wed, 12 Feb 2020 02:52:28 GMT
This is an automated email from the ASF dual-hosted git repository.

hulee pushed a commit to branch zooscalability
in repository https://gitbox.apache.org/repos/asf/helix.git

commit 6b62f0dc41ab0de42e2ad9eec489184dd8750ca8
Author: Neal Sun <nealsun.0428@gmail.com>
AuthorDate: Mon Feb 10 16:41:11 2020 -0800

    Add TrieRoutingData constructor (#731)
    
    This PR adds a constructor to TrieRoutingData. The constructor takes in a mapping of sharding
keys to realm addresses and parses it into a trie. Also, TrieRoutingData now treats sharding
keys without leading slashes as invalid. Related changes are made due to the addition of the
constructor: TrieNode is made private; missing logic is added for refreshRoutingData in ZkMetadataStoreDirectory.
---
 .../metadatastore/MetadataStoreRoutingData.java    |   7 +-
 .../helix/rest/metadatastore/TrieRoutingData.java  | 201 ++++++++++++---
 .../metadatastore/ZkMetadataStoreDirectory.java    |  36 ++-
 .../rest/metadatastore/TestTrieRoutingData.java    | 282 ++++++++++++++-------
 4 files changed, 380 insertions(+), 146 deletions(-)

diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
index 237e9b6..8d8b7e3 100644
--- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
+++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
@@ -22,7 +22,6 @@ package org.apache.helix.rest.metadatastore;
 import java.util.Map;
 import java.util.NoSuchElementException;
 
-
 public interface MetadataStoreRoutingData {
   /**
    * Given a path, return all the "metadata store sharding key-metadata store realm address"
pairs
@@ -33,15 +32,17 @@ public interface MetadataStoreRoutingData {
    * @param path - the path where the search is conducted
    * @return all "sharding key-realm address" pairs where the sharding keys contain the given
    *         path if the path is valid; empty mapping otherwise
+   * @throws IllegalArgumentException - when the path is invalid
    */
-  Map<String, String> getAllMappingUnderPath(String path);
+  Map<String, String> getAllMappingUnderPath(String path) throws IllegalArgumentException;
 
   /**
    * Given a path, return the realm address corresponding to the sharding key contained in
the
    * path. If the path doesn't contain a sharding key, throw NoSuchElementException.
    * @param path - the path where the search is conducted
    * @return the realm address corresponding to the sharding key contained in the path
+   * @throws IllegalArgumentException - when the path is invalid
    * @throws NoSuchElementException - when the path doesn't contain a sharding key
    */
-  String getMetadataStoreRealm(String path) throws NoSuchElementException;
+  String getMetadataStoreRealm(String path) throws IllegalArgumentException, NoSuchElementException;
 }
diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
index b89a5f9..28add4c 100644
--- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
+++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
@@ -23,8 +23,10 @@ import java.util.ArrayDeque;
 import java.util.Collections;
 import java.util.Deque;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
+import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException;
 
 /**
  * This is a class that uses a data structure similar to trie to represent metadata store
routing
@@ -37,15 +39,26 @@ public class TrieRoutingData implements MetadataStoreRoutingData {
 
   private final TrieNode _rootNode;
 
-  // TODO: THIS IS A TEMPORARY PLACEHOLDER. A proper constructor will be created, which will
not
-  // take in a TrieNode; it instead initializes the rootNode and creates a trie based on
-  // some input data. The constructor is blocked by the implementation of RoutingDataAccessor,
and
-  // will therefore be implemented later.
-  public TrieRoutingData(TrieNode rootNode) {
-    _rootNode = rootNode;
+  public TrieRoutingData(Map<String, List<String>> routingData) throws InvalidRoutingDataException
{
+    if (routingData == null || routingData.isEmpty()) {
+      throw new InvalidRoutingDataException("routingData cannot be null or empty");
+    }
+
+    if (isRootShardingKey(routingData)) {
+      Map.Entry<String, List<String>> entry = routingData.entrySet().iterator().next();
+      _rootNode = new TrieNode(Collections.emptyMap(), "/", true, entry.getKey());
+    } else {
+      _rootNode = new TrieNode(new HashMap<>(), "/", false, "");
+      constructTrie(routingData);
+    }
   }
 
-  public Map<String, String> getAllMappingUnderPath(String path) {
+  public Map<String, String> getAllMappingUnderPath(String path) throws IllegalArgumentException
{
+    if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) {
+      throw new IllegalArgumentException("Provided path is empty or does not have a leading
\""
+          + DELIMITER + "\" character: " + path);
+    }
+
     TrieNode curNode;
     try {
       curNode = findTrieNode(path, false);
@@ -58,10 +71,10 @@ public class TrieRoutingData implements MetadataStoreRoutingData {
     nodeStack.push(curNode);
     while (!nodeStack.isEmpty()) {
       curNode = nodeStack.pop();
-      if (curNode._isLeaf) {
-        resultMap.put(curNode._name, curNode._realmAddress);
+      if (curNode.isShardingKey()) {
+        resultMap.put(curNode.getPath(), curNode.getRealmAddress());
       } else {
-        for (TrieNode child : curNode._children.values()) {
+        for (TrieNode child : curNode.getChildren().values()) {
           nodeStack.push(child);
         }
       }
@@ -69,9 +82,15 @@ public class TrieRoutingData implements MetadataStoreRoutingData {
     return resultMap;
   }
 
-  public String getMetadataStoreRealm(String path) throws NoSuchElementException {
+  public String getMetadataStoreRealm(String path)
+      throws IllegalArgumentException, NoSuchElementException {
+    if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) {
+      throw new IllegalArgumentException("Provided path is empty or does not have a leading
\""
+          + DELIMITER + "\" character: " + path);
+    }
+
     TrieNode leafNode = findTrieNode(path, true);
-    return leafNode._realmAddress;
+    return leafNode.getRealmAddress();
   }
 
   /**
@@ -88,35 +107,28 @@ public class TrieRoutingData implements MetadataStoreRoutingData {
    */
   private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
       throws NoSuchElementException {
-    if (path.equals(DELIMITER) || path.equals("")) {
-      if (findLeafAlongPath && !_rootNode._isLeaf) {
+    if (path.equals(DELIMITER)) {
+      if (findLeafAlongPath && !_rootNode.isShardingKey()) {
         throw new NoSuchElementException("No leaf node found along the path. Path: " + path);
       }
       return _rootNode;
     }
 
-    String[] splitPath;
-    if (path.substring(0, 1).equals(DELIMITER)) {
-      splitPath = path.substring(1).split(DELIMITER, 0);
-    } else {
-      splitPath = path.split(DELIMITER, 0);
-    }
-
     TrieNode curNode = _rootNode;
-    if (findLeafAlongPath && curNode._isLeaf) {
+    if (findLeafAlongPath && curNode.isShardingKey()) {
       return curNode;
     }
-    Map<String, TrieNode> curChildren = curNode._children;
-    for (String pathSection : splitPath) {
+    Map<String, TrieNode> curChildren = curNode.getChildren();
+    for (String pathSection : path.substring(1).split(DELIMITER, 0)) {
       curNode = curChildren.get(pathSection);
       if (curNode == null) {
         throw new NoSuchElementException(
             "The provided path is missing from the trie. Path: " + path);
       }
-      if (findLeafAlongPath && curNode._isLeaf) {
+      if (findLeafAlongPath && curNode.isShardingKey()) {
         return curNode;
       }
-      curChildren = curNode._children;
+      curChildren = curNode.getChildren();
     }
     if (findLeafAlongPath) {
       throw new NoSuchElementException("No leaf node found along the path. Path: " + path);
@@ -124,36 +136,145 @@ public class TrieRoutingData implements MetadataStoreRoutingData {
     return curNode;
   }
 
-  // TODO: THE CLASS WILL BE CHANGED TO PRIVATE ONCE THE CONSTRUCTOR IS CREATED.
-  static class TrieNode {
+  /**
+   * Checks for the edge case when the only sharding key in provided routing data is the
delimiter
+   * or an empty string. When this is the case, the trie is valid and contains only one node,
which
+   * is the root node, and the root node is a leaf node with a realm address associated with
it.
+   * @param routingData - a mapping from "sharding keys" to "realm addresses" to be parsed
into a
+   *          trie
+   * @return whether the edge case is true
+   */
+  private boolean isRootShardingKey(Map<String, List<String>> routingData) {
+    if (routingData.size() == 1) {
+      for (List<String> shardingKeys : routingData.values()) {
+        return shardingKeys.size() == 1 && shardingKeys.get(0).equals(DELIMITER);
+      }
+    }
+
+    return false;
+  }
+
+  /**
+   * Constructs a trie based on the provided routing data. It loops through all sharding
keys and
+   * constructs the trie in a top down manner.
+   * @param routingData- a mapping from "sharding keys" to "realm addresses" to be parsed
into a
+   *          trie
+   * @throws InvalidRoutingDataException - when there is an empty sharding key (edge case
that
+   *           always renders the routing data invalid); when there is a sharding key which
already
+   *           contains a sharding key (invalid); when there is a sharding key that is a
part of
+   *           another sharding key (invalid)
+   */
+  private void constructTrie(Map<String, List<String>> routingData)
+      throws InvalidRoutingDataException {
+    for (Map.Entry<String, List<String>> entry : routingData.entrySet()) {
+      if (entry.getValue().isEmpty()) {
+        throw new InvalidRoutingDataException(
+            "Realm address does not have associating sharding keys: " + entry.getKey());
+      }
+      for (String shardingKey : entry.getValue()) {
+        // Missing leading delimiter is invalid
+        if (shardingKey.isEmpty() || !shardingKey.substring(0, 1).equals(DELIMITER)) {
+          throw new InvalidRoutingDataException("Sharding key does not have a leading \""
+              + DELIMITER + "\" character: " + shardingKey);
+        }
+
+        // Root can only be a sharding key if it's the only sharding key. Since this method
is
+        // running, the special case has already been checked, therefore it's definitely
invalid
+        if (shardingKey.equals(DELIMITER)) {
+          throw new InvalidRoutingDataException(
+              "There exist other sharding keys. Root cannot be a sharding key.");
+        }
+
+        // Locate the next delimiter
+        int nextDelimiterIndex = shardingKey.indexOf(DELIMITER, 1);
+        int prevDelimiterIndex = 0;
+        String keySection = shardingKey.substring(prevDelimiterIndex + 1,
+            nextDelimiterIndex > 0 ? nextDelimiterIndex : shardingKey.length());
+        TrieNode curNode = _rootNode;
+        TrieNode nextNode = curNode.getChildren().get(keySection);
+
+        // If the key section is not the last section yet, go in the loop; if the key section
is the
+        // last section, exit
+        while (nextDelimiterIndex > 0) {
+          // If the node is already a leaf node, the current sharding key is invalid; if
the node
+          // doesn't exist, construct a node and continue
+          if (nextNode != null && nextNode.isShardingKey()) {
+            throw new InvalidRoutingDataException(shardingKey + " cannot be a sharding key
because "
+                + shardingKey.substring(0, nextDelimiterIndex)
+                + " is its parent key and is also a sharding key.");
+          } else if (nextNode == null) {
+            nextNode = new TrieNode(new HashMap<>(), shardingKey.substring(0, nextDelimiterIndex),
+                false, "");
+            curNode.addChild(keySection, nextNode);
+          }
+          prevDelimiterIndex = nextDelimiterIndex;
+          nextDelimiterIndex = shardingKey.indexOf(DELIMITER, prevDelimiterIndex + 1);
+          keySection = shardingKey.substring(prevDelimiterIndex + 1,
+              nextDelimiterIndex > 0 ? nextDelimiterIndex : shardingKey.length());
+          curNode = nextNode;
+          nextNode = curNode.getChildren().get(keySection);
+        }
+
+        // If the last node already exists, it's a part of another sharding key, making the
current
+        // sharding key invalid
+        if (nextNode != null) {
+          throw new InvalidRoutingDataException(shardingKey
+              + " cannot be a sharding key because it is a parent key to another sharding
key.");
+        }
+        nextNode = new TrieNode(new HashMap<>(), shardingKey, true, entry.getKey());
+        curNode.addChild(keySection, nextNode);
+      }
+    }
+  }
+
+  private static class TrieNode {
     /**
      * This field is a mapping between trie key and children nodes. For example, node "a"
has
      * children "ab" and "ac", therefore the keys are "b" and "c" respectively.
      */
-    Map<String, TrieNode> _children;
+    private Map<String, TrieNode> _children;
     /**
-     * This field means if the node is a terminal node in the tree sense, not the trie sense.
Any
-     * node that has children cannot possibly be a leaf node because only the node without
children
-     * can store information. If a node is leaf, then it shouldn't have any children.
+     * This field states whether the path represented by the node is a sharding key
      */
-    final boolean _isLeaf;
+    private final boolean _isShardingKey;
     /**
-     * This field aligns the traditional trie design: it entails the complete path/prefix
leading to
-     * the current node. For example, the name of root node is "/", then the name of its
child node
+     * This field contains the complete path/prefix leading to the current node. For example,
the
+     * name of root node is "/", then the name of its child node
      * is "/a", and the name of the child's child node is "/a/b".
      */
-    final String _name;
+    private final String _path;
     /**
      * This field represents the data contained in a node(which represents a path), and is
only
      * available to the terminal nodes.
      */
-    final String _realmAddress;
+    private final String _realmAddress;
 
-    TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress)
{
+    TrieNode(Map<String, TrieNode> children, String path, boolean isShardingKey,
+        String realmAddress) {
       _children = children;
-      _isLeaf = isLeaf;
-      _name = name;
+      _isShardingKey = isShardingKey;
+      _path = path;
       _realmAddress = realmAddress;
     }
+
+    public Map<String, TrieNode> getChildren() {
+      return _children;
+    }
+
+    public boolean isShardingKey() {
+      return _isShardingKey;
+    }
+
+    public String getPath() {
+      return _path;
+    }
+
+    public String getRealmAddress() {
+      return _realmAddress;
+    }
+
+    public void addChild(String key, TrieNode node) {
+      _children.put(key, node);
+    }
   }
 }
diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java
b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java
index 85f8f4a..5a88ca9 100644
--- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java
+++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java
@@ -42,9 +42,9 @@ import org.apache.zookeeper.Watcher;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-
 /**
- * ZK-based MetadataStoreDirectory that listens on the routing data in routing ZKs with a
update callback.
+ * ZK-based MetadataStoreDirectory that listens on the routing data in routing ZKs with a
update
+ * callback.
  */
 public class ZkMetadataStoreDirectory implements MetadataStoreDirectory, RoutingDataListener
{
   private static final Logger LOG = LoggerFactory.getLogger(ZkMetadataStoreDirectory.class);
@@ -156,34 +156,42 @@ public class ZkMetadataStoreDirectory implements MetadataStoreDirectory,
Routing
 
   /**
    * Callback for updating the cached routing data.
-   * Note: this method should not synchronize on the class or the map. We do not want namespaces
blocking each other.
+   * Note: this method should not synchronize on the class or the map. We do not want namespaces
+   * blocking each other.
    * Threadsafe map is used for _realmToShardingKeysMap.
-   * The global consistency of the in-memory routing data is not a requirement (eventual
consistency is enough).
+   * The global consistency of the in-memory routing data is not a requirement (eventual
consistency
+   * is enough).
    * @param namespace
    */
   @Override
   public void refreshRoutingData(String namespace) {
-    // Safe to ignore the callback if routingDataMap is null.
+    // Safe to ignore the callback if any of the mapping is null.
     // If routingDataMap is null, then it will be populated by the constructor anyway
     // If routingDataMap is not null, then it's safe for the callback function to update
it
+    if (_routingZkAddressMap == null || _routingDataMap == null
+        || _realmToShardingKeysMap == null) {
+      LOG.error("Construction is not completed! ");
+      return;
+    }
 
     // Check if namespace exists; otherwise, return as a NOP and log it
     if (!_routingZkAddressMap.containsKey(namespace)) {
-      LOG.error("Failed to refresh internally-cached routing data! Namespace not found: "
+ namespace);
+      LOG.error("Failed to refresh internally-cached routing data! Namespace not found: {}",
+          namespace);
+      return;
     }
 
     try {
-      _realmToShardingKeysMap.put(namespace, _routingDataReaderMap.get(namespace).getRoutingData());
+      Map<String, List<String>> rawRoutingData =
+          _routingDataReaderMap.get(namespace).getRoutingData();
+      _realmToShardingKeysMap.put(namespace, rawRoutingData);
+
+      MetadataStoreRoutingData routingData = new TrieRoutingData(rawRoutingData);
+      _routingDataMap.put(namespace, routingData);
     } catch (InvalidRoutingDataException e) {
-      LOG.error("Failed to get routing data for namespace: " + namespace + "!");
+      LOG.error("Failed to refresh cached routing data for namespace {}", namespace, e);
     }
 
-    if (_routingDataMap != null) {
-      MetadataStoreRoutingData newRoutingData =
-          new TrieRoutingData(new TrieRoutingData.TrieNode(null, null, false, null));
-      // TODO call constructRoutingData() here.
-      _routingDataMap.put(namespace, newRoutingData);
-    }
   }
 
   @Override
diff --git a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java
b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java
index 1b1754d..bf71456 100644
--- a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java
+++ b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java
@@ -19,146 +19,250 @@ package org.apache.helix.rest.metadatastore;
  * under the License.
  */
 
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
+import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException;
 import org.testng.Assert;
 import org.testng.annotations.Test;
 
 public class TestTrieRoutingData {
-  // TODO: add constructor related tests after constructor is finished
+  private TrieRoutingData _trie;
 
   @Test
-  public void testGetAllMappingUnderPathFromRoot() {
-    TrieRoutingData trie = constructTestTrie();
-    Map<String, String> result = trie.getAllMappingUnderPath("/");
-    Assert.assertEquals(result.size(), 4);
-    Assert.assertEquals(result.get("/b/c/d"), "realmAddressD");
-    Assert.assertEquals(result.get("/b/c/e"), "realmAddressE");
-    Assert.assertEquals(result.get("/b/f"), "realmAddressF");
-    Assert.assertEquals(result.get("/g"), "realmAddressG");
+  public void testConstructionMissingRoutingData() {
+    try {
+      new TrieRoutingData(null);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage().contains("routingData cannot be null or empty"));
+    }
+    try {
+      new TrieRoutingData(Collections.emptyMap());
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage().contains("routingData cannot be null or empty"));
+    }
+  }
+
+  /**
+   * This test case is for the situation when there's only one sharding key and it's root.
+   */
+  @Test
+  public void testConstructionSpecialCase() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress", Collections.singletonList("/"));
+    TrieRoutingData trie;
+    try {
+      trie = new TrieRoutingData(routingData);
+      Map<String, String> result = trie.getAllMappingUnderPath("/");
+      Assert.assertEquals(result.size(), 1);
+      Assert.assertEquals(result.get("/"), "realmAddress");
+    } catch (InvalidRoutingDataException e) {
+      Assert.fail("Not expecting InvalidRoutingDataException");
+    }
+  }
+
+  @Test
+  public void testConstructionEmptyShardingKeys() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Collections.emptyList());
+    try {
+      new TrieRoutingData(routingData);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage()
+          .contains("Realm address does not have associating sharding keys: realmAddress1"));
+    }
+  }
+
+  @Test
+  public void testConstructionShardingKeyNoLeadingSlash() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Arrays.asList("/g", "/h/i", "/h/j"));
+    routingData.put("realmAddress2", Arrays.asList("b/c/d", "/b/f"));
+    routingData.put("realmAddress3", Collections.singletonList("/b/c/e"));
+    try {
+      new TrieRoutingData(routingData);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(
+          e.getMessage().contains("Sharding key does not have a leading \"/\" character:
b/c/d"));
+    }
+  }
+
+  @Test
+  public void testConstructionRootAsShardingKeyInvalid() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Arrays.asList("/a/b", "/"));
+    try {
+      new TrieRoutingData(routingData);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage()
+          .contains("There exist other sharding keys. Root cannot be a sharding key."));
+    }
   }
 
   @Test
-  public void testGetAllMappingUnderPathFromRootEmptyPath() {
-    TrieRoutingData trie = constructTestTrie();
-    Map<String, String> result = trie.getAllMappingUnderPath("");
-    Assert.assertEquals(result.size(), 4);
-    Assert.assertEquals(result.get("/b/c/d"), "realmAddressD");
-    Assert.assertEquals(result.get("/b/c/e"), "realmAddressE");
-    Assert.assertEquals(result.get("/b/f"), "realmAddressF");
-    Assert.assertEquals(result.get("/g"), "realmAddressG");
+  public void testConstructionShardingKeyContainsAnother() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Arrays.asList("/a/b", "/a/b/c"));
+    try {
+      new TrieRoutingData(routingData);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage().contains(
+          "/a/b/c cannot be a sharding key because /a/b is its parent key and is also a sharding
key."));
+    }
   }
 
   @Test
+  public void testConstructionShardingKeyIsAPartOfAnother() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Arrays.asList("/a/b/c", "/a/b"));
+    try {
+      new TrieRoutingData(routingData);
+      Assert.fail("Expecting InvalidRoutingDataException");
+    } catch (InvalidRoutingDataException e) {
+      Assert.assertTrue(e.getMessage().contains(
+          "/a/b cannot be a sharding key because it is a parent key to another sharding key."));
+    }
+  }
+
+  /**
+   * Constructing a trie that will also be reused for other tests
+   * -----<empty>
+   * ------/-|--\
+   * -----b--g--h
+   * ----/-\---/-\
+   * ---c--f--i--j
+   * --/-\
+   * -d--e
+   * Note: "g", "i", "j" lead to "realmAddress1"; "d", "f" lead to "realmAddress2"; "e" leads
to
+   * "realmAddress3"
+   */
+  @Test
+  public void testConstructionNormal() {
+    Map<String, List<String>> routingData = new HashMap<>();
+    routingData.put("realmAddress1", Arrays.asList("/g", "/h/i", "/h/j"));
+    routingData.put("realmAddress2", Arrays.asList("/b/c/d", "/b/f"));
+    routingData.put("realmAddress3", Collections.singletonList("/b/c/e"));
+    try {
+      _trie = new TrieRoutingData(routingData);
+    } catch (InvalidRoutingDataException e) {
+      Assert.fail("Not expecting InvalidRoutingDataException");
+    }
+  }
+
+  @Test(dependsOnMethods = "testConstructionNormal")
+  public void testGetAllMappingUnderPathEmptyPath() {
+    try {
+      _trie.getAllMappingUnderPath("");
+      Assert.fail("Expecting IllegalArgumentException");
+    } catch (IllegalArgumentException e) {
+      Assert.assertTrue(e.getMessage()
+          .contains("Provided path is empty or does not have a leading \"/\" character: "));
+    }
+  }
+
+  @Test(dependsOnMethods = "testConstructionNormal")
+  public void testGetAllMappingUnderPathNoLeadingSlash() {
+    try {
+      _trie.getAllMappingUnderPath("test");
+      Assert.fail("Expecting IllegalArgumentException");
+    } catch (IllegalArgumentException e) {
+      Assert.assertTrue(e.getMessage()
+          .contains("Provided path is empty or does not have a leading \"/\" character: test"));
+    }
+  }
+
+  @Test(dependsOnMethods = "testConstructionNormal")
+  public void testGetAllMappingUnderPathFromRoot() {
+    Map<String, String> result = _trie.getAllMappingUnderPath("/");
+    Assert.assertEquals(result.size(), 6);
+    Assert.assertEquals(result.get("/b/c/d"), "realmAddress2");
+    Assert.assertEquals(result.get("/b/c/e"), "realmAddress3");
+    Assert.assertEquals(result.get("/b/f"), "realmAddress2");
+    Assert.assertEquals(result.get("/g"), "realmAddress1");
+    Assert.assertEquals(result.get("/h/i"), "realmAddress1");
+    Assert.assertEquals(result.get("/h/j"), "realmAddress1");
+  }
+
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetAllMappingUnderPathFromSecondLevel() {
-    TrieRoutingData trie = constructTestTrie();
-    Map<String, String> result = trie.getAllMappingUnderPath("/b");
+    Map<String, String> result = _trie.getAllMappingUnderPath("/b");
     Assert.assertEquals(result.size(), 3);
-    Assert.assertEquals(result.get("/b/c/d"), "realmAddressD");
-    Assert.assertEquals(result.get("/b/c/e"), "realmAddressE");
-    Assert.assertEquals(result.get("/b/f"), "realmAddressF");
+    Assert.assertEquals(result.get("/b/c/d"), "realmAddress2");
+    Assert.assertEquals(result.get("/b/c/e"), "realmAddress3");
+    Assert.assertEquals(result.get("/b/f"), "realmAddress2");
   }
 
-  @Test
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetAllMappingUnderPathFromLeaf() {
-    TrieRoutingData trie = constructTestTrie();
-    Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d");
+    Map<String, String> result = _trie.getAllMappingUnderPath("/b/c/d");
     Assert.assertEquals(result.size(), 1);
-    Assert.assertEquals(result.get("/b/c/d"), "realmAddressD");
+    Assert.assertEquals(result.get("/b/c/d"), "realmAddress2");
   }
 
-  @Test
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetAllMappingUnderPathWrongPath() {
-    TrieRoutingData trie = constructTestTrie();
-    Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d/g");
+    Map<String, String> result = _trie.getAllMappingUnderPath("/b/c/d/g");
     Assert.assertEquals(result.size(), 0);
   }
 
-  @Test
-  public void testGetMetadataStoreRealm() {
-    TrieRoutingData trie = constructTestTrie();
+  @Test(dependsOnMethods = "testConstructionNormal")
+  public void testGetMetadataStoreRealmEmptyPath() {
     try {
-      Assert.assertEquals(trie.getMetadataStoreRealm("/b/c/d/x/y/z"), "realmAddressD");
-    } catch (NoSuchElementException e) {
-      Assert.fail("Not expecting NoSuchElementException");
+      Assert.assertEquals(_trie.getMetadataStoreRealm(""), "realmAddress2");
+      Assert.fail("Expecting IllegalArgumentException");
+    } catch (IllegalArgumentException e) {
+      Assert.assertTrue(e.getMessage()
+          .contains("Provided path is empty or does not have a leading \"/\" character: "));
     }
   }
 
-  @Test
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetMetadataStoreRealmNoSlash() {
-    TrieRoutingData trie = constructTestTrie();
     try {
-      Assert.assertEquals(trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddressD");
+      Assert.assertEquals(_trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddress2");
+      Assert.fail("Expecting IllegalArgumentException");
+    } catch (IllegalArgumentException e) {
+      Assert.assertTrue(e.getMessage().contains(
+          "Provided path is empty or does not have a leading \"/\" character: b/c/d/x/y/z"));
+    }
+  }
+
+  @Test(dependsOnMethods = "testConstructionNormal")
+  public void testGetMetadataStoreRealm() {
+    try {
+      Assert.assertEquals(_trie.getMetadataStoreRealm("/b/c/d/x/y/z"), "realmAddress2");
     } catch (NoSuchElementException e) {
       Assert.fail("Not expecting NoSuchElementException");
     }
   }
 
-  @Test
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetMetadataStoreRealmWrongPath() {
-    TrieRoutingData trie = constructTestTrie();
     try {
-      trie.getMetadataStoreRealm("/x/y/z");
+      _trie.getMetadataStoreRealm("/x/y/z");
       Assert.fail("Expecting NoSuchElementException");
     } catch (NoSuchElementException e) {
-      Assert.assertTrue(e.getMessage().contains("The provided path is missing from the trie.
Path: /x/y/z"));
+      Assert.assertTrue(
+          e.getMessage().contains("The provided path is missing from the trie. Path: /x/y/z"));
     }
   }
 
-  @Test
+  @Test(dependsOnMethods = "testConstructionNormal")
   public void testGetMetadataStoreRealmNoLeaf() {
-    TrieRoutingData trie = constructTestTrie();
     try {
-      trie.getMetadataStoreRealm("/b/c");
+      _trie.getMetadataStoreRealm("/b/c");
       Assert.fail("Expecting NoSuchElementException");
     } catch (NoSuchElementException e) {
       Assert.assertTrue(e.getMessage().contains("No leaf node found along the path. Path:
/b/c"));
     }
   }
-
-  /**
-   * Constructing a trie for testing purposes
-   * -----<empty>
-   * ------/--\
-   * -----b---g
-   * ----/-\
-   * ---c--f
-   * --/-\
-   * -d--e
-   */
-  private TrieRoutingData constructTestTrie() {
-    TrieRoutingData.TrieNode nodeD =
-        new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/c/d", true, "realmAddressD");
-    TrieRoutingData.TrieNode nodeE =
-        new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/c/e", true, "realmAddressE");
-    TrieRoutingData.TrieNode nodeF =
-        new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/f", true, "realmAddressF");
-    TrieRoutingData.TrieNode nodeG =
-        new TrieRoutingData.TrieNode(Collections.emptyMap(), "/g", true, "realmAddressG");
-    TrieRoutingData.TrieNode nodeC =
-        new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>()
{
-          {
-            put("d", nodeD);
-            put("e", nodeE);
-          }
-        }, "c", false, "");
-    TrieRoutingData.TrieNode nodeB =
-        new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>()
{
-          {
-            put("c", nodeC);
-            put("f", nodeF);
-          }
-        }, "b", false, "");
-    TrieRoutingData.TrieNode root =
-        new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>()
{
-          {
-            put("b", nodeB);
-            put("g", nodeG);
-          }
-        }, "", false, "");
-
-    return new TrieRoutingData(root);
-  }
 }


Mime
View raw message