You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@helix.apache.org by hu...@apache.org on 2020/04/01 22:46:56 UTC
[helix] 01/49: Add MetadataStoreRoutingData interface and
TrieRoutingData class to helix-rest
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 3b8b6217235905e997d4483d9ea1121b4d0942a6
Author: Neal Sun <ne...@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);
+ }
+}