helix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hu...@apache.org
Subject [helix] 01/43: Add MetadataStoreRoutingData interface and TrieRoutingData class to helix-rest
Date Tue, 17 Mar 2020 00:03:32 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 f2540fd6d76482790faea46684860cbab26d9359
Author: Neal Sun <nealsun.0428@gmail.com>
AuthorDate: Fri Jan 31 11:00:51 2020 -0800

    Add MetadataStoreRoutingData interface and TrieRoutingData class to helix-rest
    
    The TrieRoutingData class constructs a trie-like structure for "metadata store sharding
keys - metadata store realm addressses" pairs to allow faster lookup operations. The MetadataStoreRoutingData
interface allows generalized access to routing data.
---
 .../metadatastore/MetadataStoreRoutingData.java    |  47 ++++++
 .../helix/rest/metadatastore/TrieRoutingData.java  | 159 ++++++++++++++++++++
 .../rest/metadatastore/TestTrieRoutingData.java    | 164 +++++++++++++++++++++
 3 files changed, 370 insertions(+)

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
new file mode 100644
index 0000000..237e9b6
--- /dev/null
+++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
@@ -0,0 +1,47 @@
+package org.apache.helix.rest.metadatastore;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+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
+   * where the sharding keys contain the given path. For example, given "/a/b", return {"/a/b/c":
+   * "realm.address.c.com:1234", "/a/b/d": "realm.address.d.com:1234"} where "a/b/c" and
"a/b/d" are
+   * sharding keys and the urls are realm addresses. If the path is invalid, returns an empty
+   * mapping.
+   * @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
+   */
+  Map<String, String> getAllMappingUnderPath(String path);
+
+  /**
+   * 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 NoSuchElementException - when the path doesn't contain a sharding key
+   */
+  String getMetadataStoreRealm(String path) throws 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
new file mode 100644
index 0000000..b89a5f9
--- /dev/null
+++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
@@ -0,0 +1,159 @@
+package org.apache.helix.rest.metadatastore;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.ArrayDeque;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+/**
+ * This is a class that uses a data structure similar to trie to represent metadata store
routing
+ * data. It is not exactly a trie because it in essence stores a mapping (from sharding keys
to
+ * realm addresses) instead of pure text information; also, only the terminal nodes store
meaningful
+ * information (realm addresses).
+ */
+public class TrieRoutingData implements MetadataStoreRoutingData {
+  private static final String DELIMITER = "/";
+
+  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 Map<String, String> getAllMappingUnderPath(String path) {
+    TrieNode curNode;
+    try {
+      curNode = findTrieNode(path, false);
+    } catch (NoSuchElementException e) {
+      return Collections.emptyMap();
+    }
+
+    Map<String, String> resultMap = new HashMap<>();
+    Deque<TrieNode> nodeStack = new ArrayDeque<>();
+    nodeStack.push(curNode);
+    while (!nodeStack.isEmpty()) {
+      curNode = nodeStack.pop();
+      if (curNode._isLeaf) {
+        resultMap.put(curNode._name, curNode._realmAddress);
+      } else {
+        for (TrieNode child : curNode._children.values()) {
+          nodeStack.push(child);
+        }
+      }
+    }
+    return resultMap;
+  }
+
+  public String getMetadataStoreRealm(String path) throws NoSuchElementException {
+    TrieNode leafNode = findTrieNode(path, true);
+    return leafNode._realmAddress;
+  }
+
+  /**
+   * If findLeafAlongPath is false, then starting from the root node, find the trie node
that the
+   * given path is pointing to and return it; raise NoSuchElementException if the path does
+   * not point to any node. If findLeafAlongPath is true, then starting from the root node,
find the
+   * leaf node along the provided path; raise NoSuchElementException if the path does not
+   * point to any node or if there is no leaf node along the path.
+   * @param path - the path where the search is conducted
+   * @param findLeafAlongPath - whether the search is for a leaf node on the path
+   * @return the node pointed by the path or a leaf node along the path
+   * @throws NoSuchElementException - when the path points to nothing or when no leaf node
is
+   *           found
+   */
+  private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+      throws NoSuchElementException {
+    if (path.equals(DELIMITER) || path.equals("")) {
+      if (findLeafAlongPath && !_rootNode._isLeaf) {
+        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) {
+      return curNode;
+    }
+    Map<String, TrieNode> curChildren = curNode._children;
+    for (String pathSection : splitPath) {
+      curNode = curChildren.get(pathSection);
+      if (curNode == null) {
+        throw new NoSuchElementException(
+            "The provided path is missing from the trie. Path: " + path);
+      }
+      if (findLeafAlongPath && curNode._isLeaf) {
+        return curNode;
+      }
+      curChildren = curNode._children;
+    }
+    if (findLeafAlongPath) {
+      throw new NoSuchElementException("No leaf node found along the path. Path: " + path);
+    }
+    return curNode;
+  }
+
+  // TODO: THE CLASS WILL BE CHANGED TO PRIVATE ONCE THE CONSTRUCTOR IS CREATED.
+  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;
+    /**
+     * 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.
+     */
+    final boolean _isLeaf;
+    /**
+     * 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
+     * is "/a", and the name of the child's child node is "/a/b".
+     */
+    final String _name;
+    /**
+     * This field represents the data contained in a node(which represents a path), and is
only
+     * available to the terminal nodes.
+     */
+    final String _realmAddress;
+
+    TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress)
{
+      _children = children;
+      _isLeaf = isLeaf;
+      _name = name;
+      _realmAddress = realmAddress;
+    }
+  }
+}
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
new file mode 100644
index 0000000..1b1754d
--- /dev/null
+++ b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java
@@ -0,0 +1,164 @@
+package org.apache.helix.rest.metadatastore;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import org.testng.Assert;
+import org.testng.annotations.Test;
+
+public class TestTrieRoutingData {
+  // TODO: add constructor related tests after constructor is finished
+
+  @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");
+  }
+
+  @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");
+  }
+
+  @Test
+  public void testGetAllMappingUnderPathFromSecondLevel() {
+    TrieRoutingData trie = constructTestTrie();
+    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");
+  }
+
+  @Test
+  public void testGetAllMappingUnderPathFromLeaf() {
+    TrieRoutingData trie = constructTestTrie();
+    Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d");
+    Assert.assertEquals(result.size(), 1);
+    Assert.assertEquals(result.get("/b/c/d"), "realmAddressD");
+  }
+
+  @Test
+  public void testGetAllMappingUnderPathWrongPath() {
+    TrieRoutingData trie = constructTestTrie();
+    Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d/g");
+    Assert.assertEquals(result.size(), 0);
+  }
+
+  @Test
+  public void testGetMetadataStoreRealm() {
+    TrieRoutingData trie = constructTestTrie();
+    try {
+      Assert.assertEquals(trie.getMetadataStoreRealm("/b/c/d/x/y/z"), "realmAddressD");
+    } catch (NoSuchElementException e) {
+      Assert.fail("Not expecting NoSuchElementException");
+    }
+  }
+
+  @Test
+  public void testGetMetadataStoreRealmNoSlash() {
+    TrieRoutingData trie = constructTestTrie();
+    try {
+      Assert.assertEquals(trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddressD");
+    } catch (NoSuchElementException e) {
+      Assert.fail("Not expecting NoSuchElementException");
+    }
+  }
+
+  @Test
+  public void testGetMetadataStoreRealmWrongPath() {
+    TrieRoutingData trie = constructTestTrie();
+    try {
+      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"));
+    }
+  }
+
+  @Test
+  public void testGetMetadataStoreRealmNoLeaf() {
+    TrieRoutingData trie = constructTestTrie();
+    try {
+      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