This is an automated email from the ASF dual-hosted git repository. hulee pushed a commit to branch zooscalability in repository https://gitbox.apache.org/repos/asf/helix.git
commit cfba5f873736109273d9bbe116650d147f23cea0 Author: Neal Sun <[email protected]> AuthorDate: Tue Feb 18 09:38:13 2020 -0800 Add validation logic to MSD write operations (#759) This PR add routing data validation logic MSD writing operations to ensure the writes leave routing data in a valid state. TrieRoutingData logic is modified to reduce duplicate code. --- .../metadatastore/MetadataStoreRoutingData.java | 19 ++++ .../helix/rest/metadatastore/TrieRoutingData.java | 126 ++++++++++++--------- .../metadatastore/ZkMetadataStoreDirectory.java | 12 +- .../resources/helix/PropertyStoreAccessor.java | 3 +- .../resources/zookeeper/ZooKeeperAccessor.java | 19 +--- .../rest/metadatastore/TestTrieRoutingData.java | 76 +++++++++++-- .../helix/zookeeper/util/ZkValidationUtil.java | 38 +++++++ 7 files changed, 206 insertions(+), 87 deletions(-) diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java index 8d8b7e3..3bd9baa 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java @@ -45,4 +45,23 @@ public interface MetadataStoreRoutingData { * @throws NoSuchElementException - when the path doesn't contain a sharding key */ String getMetadataStoreRealm(String path) throws IllegalArgumentException, NoSuchElementException; + + /** + * Check if the provided sharding key can be inserted to the routing data. The insertion is + * invalid if: 1. the sharding key is a parent key to an existing sharding key; 2. the sharding + * key has a parent key that is an existing sharding key; 3. the sharding key already exists. In + * any of these cases, inserting the sharding key will cause ambiguity among 2 sharding keys, + * rendering the routing data invalid. + * @param shardingKey - the sharding key to be inserted + * @return true if the sharding key could be inserted, false otherwise + */ + boolean isShardingKeyInsertionValid(String shardingKey); + + /** + * Check if the provided sharding key and realm address pair exists in the routing data. + * @param shardingKey - the sharding key checked + * @param realmAddress - the realm address corresponding to the key + * @return true if the sharding key and realm address pair exist in the routing data + */ + boolean containsKeyRealmPair(String shardingKey, String realmAddress); } diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java index 923f818..f82b718 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java @@ -26,7 +26,10 @@ import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; + import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException; +import org.apache.helix.zookeeper.util.ZkValidationUtil; + /** * This is a class that uses a data structure similar to trie to represent metadata store routing @@ -54,15 +57,12 @@ public class TrieRoutingData implements MetadataStoreRoutingData { } public Map<String, String> getAllMappingUnderPath(String path) throws IllegalArgumentException { - if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) { - throw new IllegalArgumentException("Provided path is empty or does not have a leading \"" - + DELIMITER + "\" character: " + path); + if (!ZkValidationUtil.isPathValid(path)) { + throw new IllegalArgumentException("Provided path is not a valid Zookeeper path: " + path); } - TrieNode curNode; - try { - curNode = findTrieNode(path, false); - } catch (NoSuchElementException e) { + TrieNode curNode = getLongestPrefixNodeAlongPath(path); + if (!curNode.getPath().equals(path)) { return Collections.emptyMap(); } @@ -84,59 +84,73 @@ public class TrieRoutingData implements MetadataStoreRoutingData { public String getMetadataStoreRealm(String path) throws IllegalArgumentException, NoSuchElementException { - if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) { - throw new IllegalArgumentException("Provided path is empty or does not have a leading \"" - + DELIMITER + "\" character: " + path); + if (!ZkValidationUtil.isPathValid(path)) { + throw new IllegalArgumentException("Provided path is not a valid Zookeeper path: " + path); + } + + TrieNode node = getLongestPrefixNodeAlongPath(path); + if (!node.isShardingKey()) { + throw new NoSuchElementException( + "No sharding key found within the provided path. Path: " + path); + } + return node.getRealmAddress(); + } + + public boolean isShardingKeyInsertionValid(String shardingKey) { + if (!ZkValidationUtil.isPathValid(shardingKey)) { + throw new IllegalArgumentException( + "Provided shardingKey is not a valid Zookeeper path: " + shardingKey); + } + + TrieNode node = getLongestPrefixNodeAlongPath(shardingKey); + return !node.isShardingKey() && !node.getPath().equals(shardingKey); + } + + public boolean containsKeyRealmPair(String shardingKey, String realmAddress) { + if (!ZkValidationUtil.isPathValid(shardingKey)) { + throw new IllegalArgumentException( + "Provided shardingKey is not a valid Zookeeper path: " + shardingKey); } - TrieNode leafNode = findTrieNode(path, true); - return leafNode.getRealmAddress(); + TrieNode node = getLongestPrefixNodeAlongPath(shardingKey); + return node.getPath().equals(shardingKey) && node.getRealmAddress().equals(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. + /* + * Given a path, find a trie node that represents the longest prefix of the path. For example, + * given "/a/b/c", the method starts at "/", and attempts to reach "/a", then attempts to reach + * "/a/b", then ends on "/a/b/c"; if any of the node doesn't exist, the traversal terminates and + * the last seen existing node is returned. + * Note: + * 1. When the returned TrieNode is a sharding key, it is the only sharding key along the + * provided path (the path points to this sharding key); + * 2. When the returned TrieNode is not a sharding key but it represents the provided path, the + * provided path is a prefix(parent) to a sharding key; + * 3. When the returned TrieNode is not a sharding key and it does not represent the provided + * path (meaning the traversal ended before the last node of the path is reached), the provided + * path is not associated with any sharding key and can be added as a sharding key without + * creating ambiguity cases among sharding keys. * @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 + * @return a TrieNode that represents the longest prefix of the path */ - private TrieNode findTrieNode(String path, boolean findLeafAlongPath) - throws NoSuchElementException { + private TrieNode getLongestPrefixNodeAlongPath(String path) { if (path.equals(DELIMITER)) { - if (findLeafAlongPath && !_rootNode.isShardingKey()) { - throw new NoSuchElementException("No leaf node found along the path. Path: " + path); - } return _rootNode; } TrieNode curNode = _rootNode; - if (findLeafAlongPath && curNode.isShardingKey()) { - return curNode; - } - Map<String, TrieNode> curChildren = curNode.getChildren(); + TrieNode nextNode; for (String pathSection : path.substring(1).split(DELIMITER, 0)) { - curNode = curChildren.get(pathSection); - if (curNode == null) { - throw new NoSuchElementException( - "The provided path is missing from the trie. Path: " + path); - } - if (findLeafAlongPath && curNode.isShardingKey()) { + nextNode = curNode.getChildren().get(pathSection); + if (nextNode == null) { return curNode; } - curChildren = curNode.getChildren(); - } - if (findLeafAlongPath) { - throw new NoSuchElementException("No leaf node found along the path. Path: " + path); + curNode = nextNode; } return curNode; } - /** + /* * Checks for the edge case when the only sharding key in provided routing data is the delimiter * or an empty string. When this is the case, the trie is valid and contains only one node, which * is the root node, and the root node is a leaf node with a realm address associated with it. @@ -154,7 +168,7 @@ public class TrieRoutingData implements MetadataStoreRoutingData { return false; } - /** + /* * Constructs a trie based on the provided routing data. It loops through all sharding keys and * constructs the trie in a top down manner. * @param routingData- a mapping from "sharding keys" to "realm addresses" to be parsed into a @@ -169,9 +183,9 @@ public class TrieRoutingData implements MetadataStoreRoutingData { for (Map.Entry<String, List<String>> entry : routingData.entrySet()) { for (String shardingKey : entry.getValue()) { // Missing leading delimiter is invalid - if (shardingKey.isEmpty() || !shardingKey.substring(0, 1).equals(DELIMITER)) { - throw new InvalidRoutingDataException("Sharding key does not have a leading \"" - + DELIMITER + "\" character: " + shardingKey); + if (!ZkValidationUtil.isPathValid(shardingKey)) { + throw new InvalidRoutingDataException( + "Sharding key is not a valid Zookeeper path: " + shardingKey); } // Root can only be a sharding key if it's the only sharding key. Since this method is @@ -195,12 +209,14 @@ public class TrieRoutingData implements MetadataStoreRoutingData { // If the node is already a leaf node, the current sharding key is invalid; if the node // doesn't exist, construct a node and continue if (nextNode != null && nextNode.isShardingKey()) { - throw new InvalidRoutingDataException(shardingKey + " cannot be a sharding key because " - + shardingKey.substring(0, nextDelimiterIndex) - + " is its parent key and is also a sharding key."); + throw new InvalidRoutingDataException( + shardingKey + " cannot be a sharding key because " + shardingKey + .substring(0, nextDelimiterIndex) + + " is its parent key and is also a sharding key."); } else if (nextNode == null) { - nextNode = new TrieNode(new HashMap<>(), shardingKey.substring(0, nextDelimiterIndex), - false, ""); + nextNode = + new TrieNode(new HashMap<>(), shardingKey.substring(0, nextDelimiterIndex), false, + ""); curNode.addChild(keySection, nextNode); } prevDelimiterIndex = nextDelimiterIndex; @@ -224,22 +240,22 @@ public class TrieRoutingData implements MetadataStoreRoutingData { } private static class TrieNode { - /** + /* * This field is a mapping between trie key and children nodes. For example, node "a" has * children "ab" and "ac", therefore the keys are "b" and "c" respectively. */ private Map<String, TrieNode> _children; - /** + /* * This field states whether the path represented by the node is a sharding key */ private final boolean _isShardingKey; - /** + /* * This field contains the complete path/prefix leading to the current node. For example, the * name of root node is "/", then the name of its child node * is "/a", and the name of the child's child node is "/a/b". */ private final String _path; - /** + /* * This field represents the data contained in a node(which represents a path), and is only * available to the terminal nodes. */ diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java index 3be9b72..a57e08c 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java @@ -37,6 +37,7 @@ import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataExceptio import org.slf4j.Logger; import org.slf4j.LoggerFactory; + /** * ZK-based MetadataStoreDirectory that listens on the routing data in routing ZKs with a update * callback. @@ -157,10 +158,18 @@ public class ZkMetadataStoreDirectory implements MetadataStoreDirectory, Routing @Override public boolean addShardingKey(String namespace, String realm, String shardingKey) { - if (!_routingDataWriterMap.containsKey(namespace)) { + if (!_routingDataWriterMap.containsKey(namespace) || !_routingDataMap.containsKey(namespace)) { throw new IllegalArgumentException( "Failed to add sharding key: Namespace " + namespace + " is not found!"); } + if (_routingDataMap.get(namespace).containsKeyRealmPair(shardingKey, realm)) { + return true; + } + if (!_routingDataMap.get(namespace).isShardingKeyInsertionValid(shardingKey)) { + throw new IllegalArgumentException( + "Failed to add sharding key: Adding sharding key " + shardingKey + + " makes routing data invalid!"); + } return _routingDataWriterMap.get(namespace).addShardingKey(realm, shardingKey); } @@ -210,7 +219,6 @@ public class ZkMetadataStoreDirectory implements MetadataStoreDirectory, Routing } catch (InvalidRoutingDataException e) { LOG.error("Failed to refresh cached routing data for namespace {}", namespace, e); } - } @Override diff --git a/helix-rest/src/main/java/org/apache/helix/rest/server/resources/helix/PropertyStoreAccessor.java b/helix-rest/src/main/java/org/apache/helix/rest/server/resources/helix/PropertyStoreAccessor.java index 4ccc610..e50d67e 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/server/resources/helix/PropertyStoreAccessor.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/server/resources/helix/PropertyStoreAccessor.java @@ -31,6 +31,7 @@ import org.apache.helix.zookeeper.datamodel.ZNRecord; import org.apache.helix.manager.zk.ZNRecordSerializer; import org.apache.helix.manager.zk.ZkBaseDataAccessor; import org.apache.helix.rest.server.resources.zookeeper.ZooKeeperAccessor; +import org.apache.helix.zookeeper.util.ZkValidationUtil; import org.codehaus.jackson.node.ObjectNode; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -56,7 +57,7 @@ public class PropertyStoreAccessor extends AbstractHelixResource { public Response getPropertyByPath(@PathParam("clusterId") String clusterId, @PathParam("path") String path) { path = "/" + path; - if (!ZooKeeperAccessor.isPathValid(path)) { + if (!ZkValidationUtil.isPathValid(path)) { LOG.info("The propertyStore path {} is invalid for cluster {}", path, clusterId); return badRequest( "Invalid path string. Valid path strings use slash as the directory separator and names the location of ZNode"); diff --git a/helix-rest/src/main/java/org/apache/helix/rest/server/resources/zookeeper/ZooKeeperAccessor.java b/helix-rest/src/main/java/org/apache/helix/rest/server/resources/zookeeper/ZooKeeperAccessor.java index 0774bc7..bc2da05 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/server/resources/zookeeper/ZooKeeperAccessor.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/server/resources/zookeeper/ZooKeeperAccessor.java @@ -35,6 +35,7 @@ import org.apache.helix.manager.zk.ZkBaseDataAccessor; import org.apache.helix.rest.common.ContextPropertyKeys; import org.apache.helix.rest.server.ServerContext; import org.apache.helix.rest.server.resources.AbstractResource; +import org.apache.helix.zookeeper.util.ZkValidationUtil; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -72,7 +73,7 @@ public class ZooKeeperAccessor extends AbstractResource { path = "/" + path; // Check that the path supplied is valid - if (!isPathValid(path)) { + if (!ZkValidationUtil.isPathValid(path)) { String errMsg = "The given path is not a valid ZooKeeper path: " + path; LOG.info(errMsg); return badRequest(errMsg); @@ -170,20 +171,4 @@ public class ZooKeeperAccessor extends AbstractResource { private ZooKeeperCommand getZooKeeperCommandIfPresent(String command) { return Enums.getIfPresent(ZooKeeperCommand.class, command).orNull(); } - - /** - * Validates whether a given path string is a valid ZK path. - * - * Valid matches: - * / - * /abc - * /abc/abc/abc/abc - * Invalid matches: - * null or empty string - * /abc/ - * /abc/abc/abc/abc/ - **/ - public static boolean isPathValid(String path) { - return path.matches("^/|(/[\\w-]+)+$"); - } } diff --git a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java index 4de68a6..dedde19 100644 --- a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java +++ b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java @@ -25,10 +25,12 @@ import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; + import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException; import org.testng.Assert; import org.testng.annotations.Test; + public class TestTrieRoutingData { private TrieRoutingData _trie; @@ -76,8 +78,8 @@ public class TestTrieRoutingData { new TrieRoutingData(routingData); Assert.fail("Expecting InvalidRoutingDataException"); } catch (InvalidRoutingDataException e) { - Assert.assertTrue( - e.getMessage().contains("Sharding key does not have a leading \"/\" character: b/c/d")); + Assert + .assertTrue(e.getMessage().contains("Sharding key is not a valid Zookeeper path: b/c/d")); } } @@ -151,8 +153,7 @@ public class TestTrieRoutingData { _trie.getAllMappingUnderPath(""); Assert.fail("Expecting IllegalArgumentException"); } catch (IllegalArgumentException e) { - Assert.assertTrue(e.getMessage() - .contains("Provided path is empty or does not have a leading \"/\" character: ")); + Assert.assertTrue(e.getMessage().contains("Provided path is not a valid Zookeeper path: ")); } } @@ -162,8 +163,8 @@ public class TestTrieRoutingData { _trie.getAllMappingUnderPath("test"); Assert.fail("Expecting IllegalArgumentException"); } catch (IllegalArgumentException e) { - Assert.assertTrue(e.getMessage() - .contains("Provided path is empty or does not have a leading \"/\" character: test")); + Assert + .assertTrue(e.getMessage().contains("Provided path is not a valid Zookeeper path: test")); } } @@ -207,8 +208,7 @@ public class TestTrieRoutingData { Assert.assertEquals(_trie.getMetadataStoreRealm(""), "realmAddress2"); Assert.fail("Expecting IllegalArgumentException"); } catch (IllegalArgumentException e) { - Assert.assertTrue(e.getMessage() - .contains("Provided path is empty or does not have a leading \"/\" character: ")); + Assert.assertTrue(e.getMessage().contains("Provided path is not a valid Zookeeper path: ")); } } @@ -218,8 +218,8 @@ public class TestTrieRoutingData { Assert.assertEquals(_trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddress2"); Assert.fail("Expecting IllegalArgumentException"); } catch (IllegalArgumentException e) { - Assert.assertTrue(e.getMessage().contains( - "Provided path is empty or does not have a leading \"/\" character: b/c/d/x/y/z")); + Assert.assertTrue( + e.getMessage().contains("Provided path is not a valid Zookeeper path: b/c/d/x/y/z")); } } @@ -239,7 +239,7 @@ public class TestTrieRoutingData { Assert.fail("Expecting NoSuchElementException"); } catch (NoSuchElementException e) { Assert.assertTrue( - e.getMessage().contains("The provided path is missing from the trie. Path: /x/y/z")); + e.getMessage().contains("No sharding key found within the provided path. Path: /x/y/z")); } } @@ -249,7 +249,59 @@ public class TestTrieRoutingData { _trie.getMetadataStoreRealm("/b/c"); Assert.fail("Expecting NoSuchElementException"); } catch (NoSuchElementException e) { - Assert.assertTrue(e.getMessage().contains("No leaf node found along the path. Path: /b/c")); + Assert.assertTrue( + e.getMessage().contains("No sharding key found within the provided path. Path: /b/c")); } } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidNoSlash() { + try { + _trie.isShardingKeyInsertionValid("x/y/z"); + Assert.fail("Expecting IllegalArgumentException"); + } catch (IllegalArgumentException e) { + Assert.assertTrue( + e.getMessage().contains("Provided shardingKey is not a valid Zookeeper path: x/y/z")); + } + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidSlashOnly() { + Assert.assertFalse(_trie.isShardingKeyInsertionValid("/")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidNormal() { + Assert.assertTrue(_trie.isShardingKeyInsertionValid("/x/y/z")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidParentKey() { + Assert.assertFalse(_trie.isShardingKeyInsertionValid("/b/c")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidSameKey() { + Assert.assertFalse(_trie.isShardingKeyInsertionValid("/h/i")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testIsShardingKeyInsertionValidChildKey() { + Assert.assertFalse(_trie.isShardingKeyInsertionValid("/h/i/k")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testContainsKeyRealmPair() { + Assert.assertTrue(_trie.containsKeyRealmPair("/h/i", "realmAddress1")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testContainsKeyRealmPairNoKey() { + Assert.assertFalse(_trie.containsKeyRealmPair("/h/i/k", "realmAddress1")); + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testContainsKeyRealmPairNoRealm() { + Assert.assertFalse(_trie.containsKeyRealmPair("/h/i", "realmAddress0")); + } } diff --git a/zookeeper-api/src/main/java/org/apache/helix/zookeeper/util/ZkValidationUtil.java b/zookeeper-api/src/main/java/org/apache/helix/zookeeper/util/ZkValidationUtil.java new file mode 100644 index 0000000..59070ac --- /dev/null +++ b/zookeeper-api/src/main/java/org/apache/helix/zookeeper/util/ZkValidationUtil.java @@ -0,0 +1,38 @@ +package org.apache.helix.zookeeper.util; + +/* + * 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. + */ + +public class ZkValidationUtil { + /** + * Validates whether a given path string is a valid ZK path. + * + * Valid matches: + * / + * /abc + * /abc/abc/abc/abc + * Invalid matches: + * null or empty string + * /abc/ + * /abc/abc/abc/abc/ + **/ + public static boolean isPathValid(String path) { + return path.matches("^/|(/[\\w-]+)+$"); + } +}
