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 <[email protected]> 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); + } +}
