You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@helix.apache.org by GitBox <gi...@apache.org> on 2020/01/29 21:42:24 UTC
[GitHub] [helix] NealSun96 opened a new pull request #706: Implement trie
routing data
NealSun96 opened a new pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706
### Issues
- [x] My PR addresses the following Helix issues and references them in the PR description:
Fixes #701
### Description
- [x] Here are some details about my PR, including screenshots of any UI changes:
This PR is a successor to PR #682 .
As mentioned in the github issue, the original design of `ShardingKeyTrieNode` had numerous issues as revealed by the previous PR's comments, and therefore a new design is purposed and implemented. The previous design's has the following issues:
1. Since the trie node is exposed to outside users, extra effort is necessary to prevent misuse, such as making the children unmodifiable and make zkRealmAddress getter conditionally inaccessible.
2. Implementation details of the trie node are not properly obscured. For any user to iterate through the trie, the user needs to get the children mapping of a node and continue forward.
3. Traversal logic is not offered as at any common place and therefore can easily lead to repetition among different users.
With the new `TrieRoutingData` class, the trie node is encapsulated as a private class, therefore preventing any misuse. The class offers a sufficient but restrictive set of operations that outsider users may use, and can be expanded upon if necessary. The class implements the `RoutingData` interface, meaning that other forms of routing data can be implemented later to substitute `TrieRoutingData` if necessary.
NOTE: this PR does not complete the `TrieRoutingData` class. The current constructor is a placeholder (as noted in code comments) because the actual constructor is dependent on a `RoutingDataAccessor` class which is yet to be implemented (but is second in order). Once the accessor is complemented the constructor will be written in a separate PR.
### Tests
- [x] The following is the result of the "mvn test" command on the appropriate module:
[INFO] Tests run: 97, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 19.733 s - in TestSuite
[INFO]
[INFO] Results:
[INFO]
[INFO] Tests run: 97, Failures: 0, Errors: 0, Skipped: 0
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 23.970 s
[INFO] Finished at: 2020-01-29T13:30:43-08:00
[INFO] ------------------------------------------------------------------------
### Commits
- [x] My commits all reference appropriate Apache Helix GitHub issues in their subject lines, and I have squashed multiple commits if they address the same issue. In addition, my commits follow the guidelines from "[How to write a good git commit message](http://chris.beams.io/posts/git-commit/)":
1. Subject is separated from body by a blank line
1. Subject is limited to 50 characters (not including Jira issue reference)
1. Subject does not end with a period
1. Subject uses the imperative mood ("add", not "adding")
1. Body wraps at 72 characters
1. Body explains "what" and "why", not "how"
### Code Quality
- [x] My diff has been formatted using helix-style.xml
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372696639
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
Review comment:
Add JavaDoc.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373171826
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
Could we use an exception like **NotFoundException? IllegalArgumentException would be appropriate if the path was malformed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372696494
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
Review comment:
Should this be a private class? Also please move this to the end.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373237360
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private final String DELIMITER = "/";
Review comment:
This has been addressed by @jiajunwang and is fixed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373248057
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
+ } else {
+ curNode = nodeStack.pop();
+ for (TrieNode child : curNode._children.values()) {
+ nodeStack.push(child);
+ }
+ }
+ }
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is
+ * found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
Review comment:
If it's not easy, I'm okay with keeping it as one for now.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373288726
##########
File path: 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.substring(1).split(DELIMITER, 0);
+ }
Review comment:
Why is this if condition required if we're going to do the same thing either way?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] dasahcc commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
dasahcc commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372707738
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
Review comment:
This is not complete realm address. Naming as it could be confusing.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on issue #706: Implement trie routing
data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on issue #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#issuecomment-580861070
This PR is ready to be merged, approved by @narendly
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373279119
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ final boolean _isLeaf;
Review comment:
Nit: did we agree to rename this to _isTerminalNode?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372722451
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
Two points are raised here which I'll try to break down:
1. What if the path does not exist?
The path has to exist because it's traversing the previously constructed trie; whatever path is defined will be in the trie - this method is not creating arbitrary paths. I believe logically this method is correct. I have several unit tests to prove that it's working.
2. Why don't we store the complete path in the trie node?
I have considered this design before, and I believe storing complete paths also work. However, partial paths is working without an issue, therefore I see no significant benefit changing it. If you feel strongly about this, I'm happy to discuss further.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] dasahcc commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
dasahcc commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372710575
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
Let's try to use iterative way instead of recursive call. You may take more memory in memory stack for function recursive call.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372694627
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+package org.apache.helix.rest.metadatastore;
Review comment:
This is an interface class; therefore, we want to keep it generic. This means that this interface class should be independent of ZK.
Also please refrain from using internal details in comments. This is an open source project.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373238169
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
@NealSun96 Let's use https://docs.oracle.com/javase/8/docs/api/java/util/NoSuchElementException.html NoSuchElementException. This way, you don't have to import another library.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373232158
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 0);
+
+ TrieNode curNode = _rootNode;
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
Review comment:
Per offline discussion, the confusion is led by the variable `_isLeaf`. `_isLeaf` is not using the trie sense, but the regular tree sense - it means if the node is a node without children. In a separate discussion, @narendly insisted that one variable shouldn't have two functionalities and we should not use children to dictate the node status, therefore `_isLeaf` is necessary. I have added javadoc to the variable to clarify the confusion.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373123330
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
Review comment:
The recursion code is now replaced with an iterative method based on the feedback from both @dasahcc and @narendly. Because of such a change, I'm storing the complete path of a trie node to the `name` field of a `TrieNode`, the reasons are as follows:
1. Storing complete paths in trie nodes makes `getAllMappingUnderPath` marginally better than storing partial paths. Without complete paths, the function has to either add/remove partial paths from a list as it operates a trie node stack, or store paths for all nodes as it operates the stack and waste memory; storing compete paths are faster, less wasteful, and simpler than both of these approaches.
2. Trie nodes are usually seen to be associated with the complete prefix/strings they represent. Storing complete paths aligns with the common perception.
Happy to discuss this further, but closing this conversion for now as the code is now iterative.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373276755
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
+ } else {
+ curNode = nodeStack.pop();
+ for (TrieNode child : curNode._children.values()) {
+ nodeStack.push(child);
+ }
+ }
+ }
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is
+ * found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
Review comment:
Both approaches are fine to me. Keeping it as is for now.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373283331
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ 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;
Review comment:
Resolved offline. See https://github.com/apache/helix/pull/706#discussion_r373123330 for additional reference.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372715632
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
Review comment:
Do you have any suggestion on the naming?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373172066
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private final String DELIMITER = "/";
Review comment:
private static final for constant declarations
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] dasahcc commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
dasahcc commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372711207
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
What if the path does not exist? Why we dont use a complete path to add to trie but with partial info trie node to add to the path? Logically, it is not correct.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373118289
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
Update on point 2 (also replied on the previous comment): the "complete path" is marginally better for an iterative `getAllMappingUnderPath` therefore I added the full path field to `TrieNode`. Thanks for the suggestion @dasahcc . Leaving this conversation unresolved for point 1, point 2 has been resolved.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372667221
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,161 @@
+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.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(zkPath);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (zkPath.substring(zkPath.length() - 1).equals("/")) {
+ zkPath = zkPath.substring(0, zkPath.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, zkPath);
+ return resultMap;
+ }
+
+ public String getZkRealm(String zkPath) throws IllegalArgumentException {
+ TrieNode leafNode = findLeafTrieNodeAlongPath(zkPath);
+ return leafNode._zkRealmAddress;
+ }
+
+ /**
+ * Using the root node, find the trie node that the given zkPath is pointing to and return it.
+ * Raise IllegalArgumentException if the zkPath does not point to any node.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the node pointed by the zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing
+ */
+ private TrieNode findTrieNode(String zkPath) throws IllegalArgumentException {
+ if (zkPath.equals("/") || zkPath.equals("")) {
+ return _rootNode;
+ }
+
+ if (zkPath.substring(0, 1).equals("/")) {
+ zkPath = zkPath.substring(1);
+ }
+ String[] splitZkPath = zkPath.split("/", 0);
+ TrieNode curNode = _rootNode;
+ Map<String, TrieNode> curChildren = curNode._children;
+ for (String pathSection : splitZkPath) {
+ curNode = curChildren.get(pathSection);
+ if (curNode != null) {
+ curChildren = curNode._children;
+ } else {
+ throw new IllegalArgumentException("the provided zkPath is missing from the trie");
+ }
+ }
+ return curNode;
+ }
+
+ /**
+ * Using the root node, find the leaf node along the provided zkPath. Raise
+ * IllegalArgumentException if the zkPath does not point to any node or if there is no leaf node
+ * along the path.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the leaf node along the provided zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing or when there is no leaf
+ * node along the path.
+ */
+ private TrieNode findLeafTrieNodeAlongPath(String zkPath) throws IllegalArgumentException {
Review comment:
I could set a flag to reuse the same logic, but I was concerned about the code being a bit messy. I'll write it up and see how it turns out.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373093002
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
Review comment:
Please see the interface for JavaDoc of `getAllMappingUnderPath`. I looked at `CustomRestClient` and `CustomRestClientImpl` for reference and mimicked its style of having JavaDoc in interface but not implementation. If this isn't the correct convention, please feel free to correct me.
The `zkPath` comment is on an outdated version of the files. The parameter has already been renamed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372721207
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
Review comment:
What I assume you mean is to store all descendant leaf nodes of a trie node as the children of a trie node. If the purposed change is a structural design change, then I'm afraid I have to disagree.
The purposed structural change does allow a faster operation for `getAllMappingUnderPath`, however, it suffers from the following:
1. The trie will take longer to construct. Bear in mind that the trie is created on the fly by the major user, therefore construction cost is a realistic concern.
2. With the cost in mind, this change doesn't help with the other operation `getMetadataStoreRealm` at all.
3. A structural chagne like this makes the data structure no longer a trie. This is intended to be a trie class.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373239477
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
+ } else {
+ curNode = nodeStack.pop();
+ for (TrieNode child : curNode._children.values()) {
+ nodeStack.push(child);
+ }
+ }
+ }
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is
+ * found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
Review comment:
The two methods you mentioned were originally split out in this PR. It was @jiajunwang 's earlier comment that led to the merging of two methods (https://github.com/apache/helix/pull/706#discussion_r372655452). I don't have a strong opinion on either approach, but a general agreement should be made before I make any further changes.
In terms of extracting common logic, the way these methods work prevent that: leaf checking logic happens on every level of iteration - if common code is extracted, the common code will each be two lines long and is not reasonable as standalone code.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373280262
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ 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;
Review comment:
Didn't we agree to this:
TrieNode : _name
root node: "/"
"a": "a"
"b": "b"
instead of "/a/b"?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] jiajunwang commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373210489
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
Review comment:
nit, nodeStack.pop() can be done before check isLeaf()
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373279721
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
Review comment:
This is not very clear?
Shouldn't it be : If a node "a" has children "b", and "c", then ....?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] dasahcc commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
dasahcc commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372710184
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 0);
+
+ TrieNode curNode = _rootNode;
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
Review comment:
This logic confuse me here.
If you have trie:
a - leaf
b c -leaf
d e - leaf
And you are looking for /a/b with leaf flag as false. Then you will return root as /a. right? But for searching purpose. I think it is correct to return b node. Can you explain what is expected scenario?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372722451
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
Two points are raised here which I'll try to break down:
1. What if the path does not exist?
The path has to exist because the method is traversing the previously constructed trie; whatever path is defined will be in the trie - this method is not creating arbitrary paths. I believe logically this method is correct. I have several unit tests to prove that it's working.
2. Why don't we store the complete path in the trie node?
I have considered this design before, and I believe storing complete paths also work. However, partial paths is working without an issue, therefore I see no significant benefit changing it. If you feel strongly about this, I'm happy to discuss further.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373237268
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
I'll use `javassist.NotFoundException`, then.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373279388
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
Review comment:
Let's make this errorMsg more helpful. See my comment above.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373279943
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ final boolean _isLeaf;
Review comment:
Add here that if a node is terminal, it cannot have any children. This should be checked in this class as well.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373597158
##########
File path: 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.substring(1).split(DELIMITER, 0);
+ }
Review comment:
That was a mistake, thank you for catching it. I also added two more tests to ensure all if-paths are covered.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372721207
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
Review comment:
What I assume you mean is to store all descendant leaf nodes of a trie node as the children of a trie node. If the purposed change is a structural design change, then I'm afraid I have to disagree.
The purposed structural change does allow a faster operation for `getAllMappingUnderPath`, however, it suffers from the following:
1. The trie will take longer to construct. Bear in mind that the trie is created on the fly by the major user, therefore construction cost is a realistic concern.
2. With the cost in mind, this change doesn't help with the other operation `getMetadataStoreRealm` at all.
3. A structural change like this makes the data structure no longer a trie. This is intended to be a trie class.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372733323
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
Review comment:
Please use level-by-level traversal for this. We try to avoid recursion in production code.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373276612
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
Thank you for the suggestion. Updated.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373280262
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ 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;
Review comment:
Didn't we agree to this:
TrieNode : _name
root node: "/"
"a": "a"
"b": "b"
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373278931
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
Review comment:
Nit: Try to make the error msg more helpful by adding the arguments (path and findLeafAlongPath)
example:
"No terminal node found along the path given! Path: " + path
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373175388
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
+ } else {
+ curNode = nodeStack.pop();
+ for (TrieNode child : curNode._children.values()) {
+ nodeStack.push(child);
+ }
+ }
+ }
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is
+ * found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
Review comment:
Could we split this into two methods and remove this boolean flag? You could create another private method for the common logic.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372696697
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
Review comment:
zkPath -> path?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] dasahcc commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
dasahcc commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372708307
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
Review comment:
To fast the processing, we can sacrifice some memory usage as storing all the sub children in current node.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372694287
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+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;
+
+public interface RoutingData {
+ /**
+ * Given a zkPath, return all the "sharding key-zkRealmAddress" pairs where the sharding keys
+ * contain the given zkPath. For example, given "/ESPRESSO_MT_LD-1/schemata", return
+ * {"/ESPRESSO_MT_LD-1/schemata/ESPRESSO_MT_LD-1": "zk-ltx1-0-espresso.prod.linkedin.com:2181",
+ * "/ESPRESSO_MT_LD-1/schemata/ESPRESSO_MT_LD-2": "zk-ltx1-1-espresso.prod.linkedin.com:2181"}.
Review comment:
Please refrain from exposing internal details @nealsun-linkedin
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373280262
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
+ */
+ 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;
Review comment:
Didn't we agree to this:
TrieNode : _name
root node: "/"
"a": "a"
"b": "b"
instead of "/a/b"?
Since that would just require one String.split, and you'll have a comprehensive list of all nodes' names, which should make the tree traversal simpler as in it won't require any more splitting?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373118289
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
Update on point 2 (also replied on the previous comment): the "complete path" is marginally better for an iterative `getAllMappingUnderPath` therefore I added the full path field to `TrieNode`. Thanks for the suggestion @dasahcc . Since the method is iterative, point 1 no longer is an issue. Resolving the conversation.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372696125
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
Review comment:
In general, be careful about terminology you use here. I'd say this class could be used for all metadata stores that use a filesystem API (assuming there are paths).
So your variables will have to be named something other than zkPath..
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373230117
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
+ nodeStack.push(curNode);
+ while (!nodeStack.isEmpty()) {
+ if (nodeStack.peek()._isLeaf) {
+ resultMap.put(nodeStack.peek()._name, nodeStack.peek()._realmAddress);
+ nodeStack.pop();
Review comment:
Agreed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372723657
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
The recursive calls won't create many call stacks because the depth of the trie is typically limited: based on the current usage, the maximum is 3. The number of call stacks is bounded by the depth of the trie.
In terms of scaling in the future, I do agree that an iterative method is better, however, constructing the full paths for each node is more difficult than necessary. (This is related to your next comment - storing full paths resolves this problem. If you feel strongly about the full-path design, I'm happy to discuss further.)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] jiajunwang commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373207921
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private final String DELIMITER = "/";
Review comment:
private static final
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373283121
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
Review comment:
Good point. Modifying test cases as well.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373166009
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
Review comment:
I have reconsidered it and I find package private to be not secure enough. I will add a TODO on `TrieNode` because the unit tests are still dependent on it being package private; once the constructor is created, it will be changed to private.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] jiajunwang commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372655452
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,161 @@
+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.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(zkPath);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (zkPath.substring(zkPath.length() - 1).equals("/")) {
+ zkPath = zkPath.substring(0, zkPath.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, zkPath);
+ return resultMap;
+ }
+
+ public String getZkRealm(String zkPath) throws IllegalArgumentException {
+ TrieNode leafNode = findLeafTrieNodeAlongPath(zkPath);
+ return leafNode._zkRealmAddress;
+ }
+
+ /**
+ * Using the root node, find the trie node that the given zkPath is pointing to and return it.
+ * Raise IllegalArgumentException if the zkPath does not point to any node.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the node pointed by the zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing
+ */
+ private TrieNode findTrieNode(String zkPath) throws IllegalArgumentException {
+ if (zkPath.equals("/") || zkPath.equals("")) {
+ return _rootNode;
+ }
+
+ if (zkPath.substring(0, 1).equals("/")) {
+ zkPath = zkPath.substring(1);
+ }
+ String[] splitZkPath = zkPath.split("/", 0);
+ TrieNode curNode = _rootNode;
+ Map<String, TrieNode> curChildren = curNode._children;
+ for (String pathSection : splitZkPath) {
+ curNode = curChildren.get(pathSection);
+ if (curNode != null) {
+ curChildren = curNode._children;
+ } else {
+ throw new IllegalArgumentException("the provided zkPath is missing from the trie");
+ }
+ }
+ return curNode;
+ }
+
+ /**
+ * Using the root node, find the leaf node along the provided zkPath. Raise
+ * IllegalArgumentException if the zkPath does not point to any node or if there is no leaf node
+ * along the path.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the leaf node along the provided zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing or when there is no leaf
+ * node along the path.
+ */
+ private TrieNode findLeafTrieNodeAlongPath(String zkPath) throws IllegalArgumentException {
Review comment:
This method is 90% the same as the findTrieNode, can we please merge them?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
Re: [GitHub] [helix] NealSun96 commented on a change in pull request
#706: Implement trie routing data
Posted by Huizhi Lu <ih...@gmail.com>.
I think it would be cleaner to put it in a separate public class? TrieNode
is general
On Thu, Jan 30, 2020 at 9:30 AM GitBox <gi...@apache.org> wrote:
> NealSun96 commented on a change in pull request #706: Implement trie
> routing data
> URL: https://github.com/apache/helix/pull/706#discussion_r373089357
>
>
>
> ##########
> File path:
> helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
> ##########
> @@ -0,0 +1,136 @@
> +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;
> +
> +public class TrieRoutingData implements RoutingData {
> + 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;
> + }
> +
> + static class TrieNode {
>
> Review comment:
> The class is declared as package private for testing purpose. Otherwise
> trie nodes cannot be created in the unit tests.
> It'll be moved to the end as suggested.
>
> ----------------------------------------------------------------
> This is an automated message from the Apache Git Service.
> To respond to the message, please log on to 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
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
> For additional commands, e-mail: reviews-help@helix.apache.org
>
>
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373089357
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
Review comment:
The class is declared as package private for testing purpose. Otherwise trie nodes cannot be created in the unit tests.
It'll be moved to the end as suggested.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373237515
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
Review comment:
I didn't realize that Stack is Vector based. Thanks for the suggestion, I'll switch it over.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on issue #706: Implement trie routing
data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on issue #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#issuecomment-580864897
Final commit message:
Add MetadataStoreRoutingData interface and TrieRoutingData class to helix-rest
The TrieRoutingData class constructs a trie 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.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373179412
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
Optional: usually I think it might be a good idea to wrap this into a class like MetadataStoreInfo that contains fields like realm address, but it's okay to keep it a string for now.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373288726
##########
File path: 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.substring(1).split(DELIMITER, 0);
+ }
Review comment:
Why is this if condition required if we're going to the same thing either way?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372666971
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+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;
+
+public interface RoutingData {
Review comment:
I don't have the context for the routing table provider, therefore I don't have any objection to that. Tagging @narendly for reference.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373171180
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-realm address" pairs where the sharding keys
Review comment:
Just to make it specific and unambiguous, let's say "metadata store path sharding key" and "metadata store realm address". And give examples.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] jiajunwang commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372661344
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+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;
+
+public interface RoutingData {
Review comment:
Shall we just call it ZkRealmData?
It might be confusing because we have routing table provider for completely different usage.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372695715
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(zkPath, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (zkPath.substring(zkPath.length() - 1).equals("/")) {
+ zkPath = zkPath.substring(0, zkPath.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, zkPath);
+ return resultMap;
+ }
+
+ public String getZkRealm(String zkPath) throws IllegalArgumentException {
Review comment:
getMetadataStoreRealm since we want to make this metadata store-agnostic
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373279428
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the path");
Review comment:
See above.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372694026
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+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;
+
+public interface RoutingData {
+ /**
+ * Given a zkPath, return all the "sharding key-zkRealmAddress" pairs where the sharding keys
+ * contain the given zkPath. For example, given "/ESPRESSO_MT_LD-1/schemata", return
+ * {"/ESPRESSO_MT_LD-1/schemata/ESPRESSO_MT_LD-1": "zk-ltx1-0-espresso.prod.linkedin.com:2181",
+ * "/ESPRESSO_MT_LD-1/schemata/ESPRESSO_MT_LD-2": "zk-ltx1-1-espresso.prod.linkedin.com:2181"}.
+ * If the zkPath is invalid, returns an empty mapping.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return all "sharding key-zkRealmAddress" pairs where the sharding keys contain the given
+ * zkPath if the zkPath is valid; empty mapping otherwise
+ */
+ Map<String, String> getAllMappingUnderPath(String zkPath);
+
+ /**
+ * Given a zkPath, return the zkRealmAddress corresponding to the sharding key contained in the
+ * zkPath. If the zkPath doesn't contain a sharding key, throw IllegalArgumentException.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the zkRealmAddress corresponding to the sharding key contained in the zkPath
+ * @throws IllegalArgumentException - when the zkPath doesn't contain a sharding key
+ */
+ String getZkRealm(String zkPath) throws IllegalArgumentException;
Review comment:
We could rename this to getMetadataStoreRealm to keep the interface generic.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373230209
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private final String DELIMITER = "/";
Review comment:
Oops, thank you for catching it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373159912
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
Review comment:
Per offline meeting, the confusion has been cleared up. Action point: adding javadoc to explain what this field actually means, but the field will remain.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373239701
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java
##########
@@ -0,0 +1,44 @@
+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;
+
+public interface MetadataStoreRoutingData {
+ /**
+ * Given a path, return all the "sharding key-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"}. 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 IllegalArgumentException.
+ * @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 doesn't contain a sharding key
+ */
+ String getMetadataStoreRealm(String path) throws IllegalArgumentException;
Review comment:
I agree that this is a good idea, but for simplicity let's keep it as string for this PR.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373283353
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,157 @@
+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");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals(DELIMITER)) {
+ path = path.substring(1);
+ }
+ String[] 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");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new NoSuchElementException("no leaf node found along the 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.
Review comment:
Resolved offline. See https://github.com/apache/helix/pull/706#discussion_r373123330 for additional reference.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372693829
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/RoutingData.java
##########
@@ -0,0 +1,45 @@
+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;
+
+public interface RoutingData {
Review comment:
As we discussed, "MetadataStoreRoutingData" might be more appropriate here.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372674068
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,161 @@
+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.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class TrieRoutingData implements RoutingData {
+ 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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _zkRealmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _zkRealmAddress = zkRealmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String zkPath) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(zkPath);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (zkPath.substring(zkPath.length() - 1).equals("/")) {
+ zkPath = zkPath.substring(0, zkPath.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, zkPath);
+ return resultMap;
+ }
+
+ public String getZkRealm(String zkPath) throws IllegalArgumentException {
+ TrieNode leafNode = findLeafTrieNodeAlongPath(zkPath);
+ return leafNode._zkRealmAddress;
+ }
+
+ /**
+ * Using the root node, find the trie node that the given zkPath is pointing to and return it.
+ * Raise IllegalArgumentException if the zkPath does not point to any node.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the node pointed by the zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing
+ */
+ private TrieNode findTrieNode(String zkPath) throws IllegalArgumentException {
+ if (zkPath.equals("/") || zkPath.equals("")) {
+ return _rootNode;
+ }
+
+ if (zkPath.substring(0, 1).equals("/")) {
+ zkPath = zkPath.substring(1);
+ }
+ String[] splitZkPath = zkPath.split("/", 0);
+ TrieNode curNode = _rootNode;
+ Map<String, TrieNode> curChildren = curNode._children;
+ for (String pathSection : splitZkPath) {
+ curNode = curChildren.get(pathSection);
+ if (curNode != null) {
+ curChildren = curNode._children;
+ } else {
+ throw new IllegalArgumentException("the provided zkPath is missing from the trie");
+ }
+ }
+ return curNode;
+ }
+
+ /**
+ * Using the root node, find the leaf node along the provided zkPath. Raise
+ * IllegalArgumentException if the zkPath does not point to any node or if there is no leaf node
+ * along the path.
+ * @param zkPath - the zkPath where the search is conducted
+ * @return the leaf node along the provided zkPath
+ * @throws IllegalArgumentException - when the zkPath points to nothing or when there is no leaf
+ * node along the path.
+ */
+ private TrieNode findLeafTrieNodeAlongPath(String zkPath) throws IllegalArgumentException {
Review comment:
I combined the two methods. It seems a bit long to me, but it does work.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372716392
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 0);
+
+ TrieNode curNode = _rootNode;
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
Review comment:
Github formatting might have ruined the trie you drew.
Either way, if the leaf flag is false, then this if statement won't be triggered, and the method will search for `b` as it continues to the loop; if the leaf flag is true, it checks to see if `a` is a leaf, if yes then return.
If this is not clear, feel free to discuss with me in person. The comment formatting is not helping.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
narendly commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373173423
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,130 @@
+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.Stack;
+
+public class TrieRoutingData implements MetadataStoreRoutingData {
+ private 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 (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ Stack<TrieNode> nodeStack = new Stack<>();
Review comment:
Nit: ArrayDeque might provide better performance. Optional.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373117391
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
I experimented with "nodes storing full path" and "node storing partial path", and turns out the full path approach makes this method marginally better. I'm therefore adding a field that represents the full path of a trie node.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] narendly merged pull request #706: Implement trie routing
data
Posted by GitBox <gi...@apache.org>.
narendly merged pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on issue #706: Implement trie routing
data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on issue #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#issuecomment-580546460
Please remember to create the new branch for merging as you mentioned.
This PR is ready to be merged, approved by @narendly
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373161510
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
Review comment:
Per offline meeting, the agreement is to keep the implementation as is for the current PR, and based on future usage statistics, potentially make optimization updates as suggested.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org
[GitHub] [helix] NealSun96 commented on a change in pull request #706:
Implement trie routing data
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r373102611
##########
File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
##########
@@ -0,0 +1,136 @@
+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;
+
+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;
+ }
+
+ static class TrieNode {
+ final Map<String, TrieNode> _children;
+ final boolean _isLeaf;
+ final String _realmAddress;
+
+ TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) {
+ _children = children;
+ _isLeaf = isLeaf;
+ _realmAddress = realmAddress;
+ }
+ }
+
+ public Map<String, String> getAllMappingUnderPath(String path) {
+ TrieNode curNode;
+ try {
+ curNode = findTrieNode(path, false);
+ } catch (IllegalArgumentException e) {
+ return Collections.emptyMap();
+ }
+
+ Map<String, String> resultMap = new HashMap<>();
+ if (path.substring(path.length() - 1).equals("/")) {
+ path = path.substring(0, path.length() - 1);
+ }
+ addAllAddressesToMapping(resultMap, curNode, path);
+ return resultMap;
+ }
+
+ public String getMetadataStoreRealm(String path) throws IllegalArgumentException {
+ 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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException - when the path points to nothing or when no leaf node is found
+ */
+ private TrieNode findTrieNode(String path, boolean findLeafAlongPath)
+ throws IllegalArgumentException {
+ if (path.equals("/") || path.equals("")) {
+ if (findLeafAlongPath && !_rootNode._isLeaf) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return _rootNode;
+ }
+
+ if (path.substring(0, 1).equals("/")) {
+ path = path.substring(1);
+ }
+ String[] splitPath = path.split("/", 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 IllegalArgumentException("the provided path is missing from the trie");
+ }
+ if (findLeafAlongPath && curNode._isLeaf) {
+ return curNode;
+ }
+ curChildren = curNode._children;
+ }
+ if (findLeafAlongPath) {
+ throw new IllegalArgumentException("no leaf node found along the path");
+ }
+ return curNode;
+ }
+
+ /**
+ * Given a trie node, search for all leaf nodes that descend from the given trie node, and add
+ * all complete paths and realm addresses of these leaf nodes to a provided mapping. This method
+ * recursively calls itself.
+ * @param mapping - where the results (complete paths of leaf nodes and their realm addresses)
+ * are stored
+ * @param curNode - the current trie node where the search starts
+ * @param curPath - the complete path of the current trie node
+ */
+ private static void addAllAddressesToMapping(Map<String, String> mapping, TrieNode curNode,
+ String curPath) {
+ if (curNode._isLeaf) {
+ mapping.put(curPath, curNode._realmAddress);
+ return;
+ }
+
+ for (Map.Entry<String, TrieNode> entry : curNode._children.entrySet()) {
+ addAllAddressesToMapping(mapping, entry.getValue(), curPath + "/" + entry.getKey());
Review comment:
I thought about it and turns out the iterative method is not as ugly as I thought. Therefore I'm changing it from the recursive method since it is indeed better.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to 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
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org