Repository: sentry Updated Branches: refs/heads/master 1fbb0aa41 -> 65eceff08
SENTRY-2398: Support multiple target versions on single source versions during schema upgrades (Sergio Pena, reviewed by Na Li) Project: http://git-wip-us.apache.org/repos/asf/sentry/repo Commit: http://git-wip-us.apache.org/repos/asf/sentry/commit/65eceff0 Tree: http://git-wip-us.apache.org/repos/asf/sentry/tree/65eceff0 Diff: http://git-wip-us.apache.org/repos/asf/sentry/diff/65eceff0 Branch: refs/heads/master Commit: 65eceff0863bc1a06a5c09c62b46e97675ca7421 Parents: 1fbb0aa Author: Sergio Pena <sergio.p...@cloudera.com> Authored: Thu Sep 13 11:29:16 2018 -0500 Committer: Sergio Pena <sergio.p...@cloudera.com> Committed: Thu Sep 13 11:29:16 2018 -0500 ---------------------------------------------------------------------- .../persistent/SentryStoreSchemaInfo.java | 45 ++--- .../service/persistent/SentryUpgradeOrder.java | 167 +++++++++++++++++ .../persistent/TestSentryUpgradeOrder.java | 187 +++++++++++++++++++ 3 files changed, 372 insertions(+), 27 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/sentry/blob/65eceff0/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryStoreSchemaInfo.java ---------------------------------------------------------------------- diff --git a/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryStoreSchemaInfo.java b/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryStoreSchemaInfo.java index 0d4f26c..f710253 100644 --- a/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryStoreSchemaInfo.java +++ b/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryStoreSchemaInfo.java @@ -18,14 +18,15 @@ package org.apache.sentry.provider.db.service.persistent; -import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; -import java.util.ArrayList; +import java.util.Collections; +import java.util.LinkedList; import java.util.List; +import java.util.Map; import org.apache.sentry.core.common.exception.SentryUserException; public class SentryStoreSchemaInfo { @@ -34,7 +35,7 @@ public class SentryStoreSchemaInfo { private static final String INIT_FILE_PREFIX = "sentry-"; private static final String VERSION_UPGRADE_LIST = "upgrade.order"; private final String dbType; - private final String sentrySchemaVersions[]; + private final Map<String, List<String>> sentrySchemaVersions; private final String sentryScriptDir; private static final String SENTRY_VERSION = "2.1.0"; @@ -43,21 +44,18 @@ public class SentryStoreSchemaInfo { throws SentryUserException { this.sentryScriptDir = sentryScriptDir; this.dbType = dbType; + // load upgrade order for the given dbType - List<String> upgradeOrderList = new ArrayList<String>(); String upgradeListFile = getSentryStoreScriptDir() + File.separator + VERSION_UPGRADE_LIST + "." + dbType; - try (BufferedReader bfReader = new BufferedReader(new FileReader(upgradeListFile))) { - String currSchemaVersion; - while ((currSchemaVersion = bfReader.readLine()) != null) { - upgradeOrderList.add(currSchemaVersion.trim()); - } + + try { + sentrySchemaVersions = SentryUpgradeOrder.readUpgradeGraph(new FileReader(upgradeListFile)); } catch (FileNotFoundException e) { throw new SentryUserException("File " + upgradeListFile + " not found ", e); } catch (IOException e) { throw new SentryUserException("Error reading " + upgradeListFile, e); } - sentrySchemaVersions = upgradeOrderList.toArray(new String[0]); } public String getSentrySchemaVersion() { @@ -66,31 +64,24 @@ public class SentryStoreSchemaInfo { public List<String> getUpgradeScripts(String fromSchemaVer) throws SentryUserException { - List<String> upgradeScriptList = new ArrayList<String>(); - // check if we are already at current schema level if (getSentryVersion().equals(fromSchemaVer)) { - return upgradeScriptList; + return Collections.emptyList(); } - // Find the list of scripts to execute for this upgrade - int firstScript = sentrySchemaVersions.length; - for (int i = 0; i < sentrySchemaVersions.length; i++) { - String fromVersion = sentrySchemaVersions[i].split("-to-")[0]; - if (fromVersion.equals(fromSchemaVer)) { - firstScript = i; - break; - } - } - if (firstScript == sentrySchemaVersions.length) { + List<String> upgradePathList = + SentryUpgradeOrder.getUpgradePath(sentrySchemaVersions, fromSchemaVer, getSentrySchemaVersion()); + if (upgradePathList.isEmpty()) { throw new SentryUserException("Unknown version specified for upgrade " - + fromSchemaVer + " Sentry schema may be too old or newer"); + + fromSchemaVer + " Sentry schema may be too old or newer"); } - for (int i = firstScript; i < sentrySchemaVersions.length; i++) { - String scriptFile = generateUpgradeFileName(sentrySchemaVersions[i]); - upgradeScriptList.add(scriptFile); + // Create a new list with the script file paths of the upgrade order path obtained before + List<String> upgradeScriptList = new LinkedList<>(); + for (String upgradePath : upgradePathList) { + upgradeScriptList.add(generateUpgradeFileName(upgradePath)); } + return upgradeScriptList; } http://git-wip-us.apache.org/repos/asf/sentry/blob/65eceff0/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryUpgradeOrder.java ---------------------------------------------------------------------- diff --git a/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryUpgradeOrder.java b/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryUpgradeOrder.java new file mode 100644 index 0000000..a7a3392 --- /dev/null +++ b/sentry-service/sentry-service-server/src/main/java/org/apache/sentry/provider/db/service/persistent/SentryUpgradeOrder.java @@ -0,0 +1,167 @@ +/** + * 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. + */ +package org.apache.sentry.provider.db.service.persistent; + +import java.io.BufferedReader; +import java.io.IOException; +import java.io.Reader; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.Stack; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +public class SentryUpgradeOrder { + private static final Logger LOGGER = LoggerFactory.getLogger(SentryUpgradeOrder.class); + + /** + * Returns a directed graph in the form of a map structure that contains the allowed upgrade + * order schema versions read from a specific Reader. + * </p> + * The format of the upgrade order schema versions is as follows: + * SOURCE-to-TARGET + * </p> + * where SOURCE is the version from where to upgrade, and TARGET is the target version where + * to upgrade, i.e. + * 1.8.0-to-1.9.0 + * </p> + * The reader may contain a list of upgrade path versions separated by a new line. + * 1.8.0-to-1.9.0 + * 1.8.0-to-2.0.0 + * 1.9.0-to-2.1.0 + * </p> + * Lines starting with the # are considered comments and are ignored. + * + * @param reader A Reader object from where to read the list of upgrade path versions. + * @return A map structure that contains the directed graph. + * @throws IOException If an error occurs while reading data from the Reader object. + */ + public static Map<String, List<String>> readUpgradeGraph(Reader reader) throws IOException { + Map<String, List<String>> upgradeSchemaVersions = new HashMap<>(); + + try (BufferedReader bfReader = new BufferedReader(reader)) { + String schemaVersion; + while ((schemaVersion = bfReader.readLine()) != null) { + String[] versions = schemaVersion.toLowerCase().split("-to-"); + + // Valid upgrade versions has a source and a target version + if (versions.length != 2) { + LOGGER.warn("Ignoring unknown Sentry schema upgrade path: " + schemaVersion); + continue; + } + + String source = versions[0].trim(); + String target = versions[1].trim(); + + // Valid upgrade versions should have different source and target versions + if (source.isEmpty() || source.startsWith("#") || source.equals(target)) { + continue; + } + + // There could be multiple source versions with different targets. + List<String> toVersions = upgradeSchemaVersions.getOrDefault(source, new LinkedList<>()); + toVersions.add(target); + upgradeSchemaVersions.put(source, toVersions); + } + } + + return upgradeSchemaVersions; + } + + /** + * Returns a list of upgrade path versions sorted from lower version to higher version. + * + * @param upgrades The map structured that contains a graph of directed path upgrades. + * @param from A string of the source version to search. + * @param to A string of the target version to search. + * @return An ordered list from lower to higher versions of the upgrade path versions. + */ + public static List<String> getUpgradePath(Map<String, List<String>> upgrades, String from, String to) { + // LinkedList is used to keep the correct order in Java 8 (ArrayList is known to not preserve + // the order at the moment of insertion). + List<String> upgradeListPath = new LinkedList<>(); + + Stack<String> upgradePaths = new Stack<>(); + Set<String> visited = new HashSet<>(); + searchPath(upgrades, from, to, upgradePaths, visited); + + // Reverse the stack to put the correct order in the list. + // To keep the behavior correctly, a list is returned instead of the stack to avoid the + // incorrect order obtained if a stack is used in the for() loop. + while (!upgradePaths.isEmpty()) { + upgradeListPath.add(upgradePaths.pop()); + } + + return upgradeListPath; + } + + /** + * Searches the complete upgrade path from the list of valid upgrades. + * + * @param from The string version from where to upgrade. + * @param to The string version to upgrade. + * @param upgradePath A stack where to put the complete upgrade path. Empty if no upgrade path + * is found. + * @param visited A set where to track the visited upgrade paths. + * + * @return True if a complete upgrade path is found; False otherwise. + */ + private static boolean searchPath(Map<String, List<String>> graph, String from, String to, Stack<String> upgradePath, Set<String> visited) { + /* + * It is not necessary to find the shortest path to the upgrade as the number of upgrade + * scripts are small and do not cause too much overhead during an upgrade. So a simple depth-first + * search is done to find the requested path. + */ + + if (from.equals(to)) { + return true; + } + + if (!graph.containsKey(from)) { + return false; + } + + boolean found = false; + for (String toVersion : graph.get(from)) { + String nextPath = generateUpgradeVersionString(from, toVersion); + boolean isVisited = visited.contains(nextPath); + if (!isVisited) { + visited.add(nextPath); + found = searchPath(graph, toVersion, to, upgradePath, visited); + if (found) { + upgradePath.push(nextPath); + break; + } else { + visited.remove(nextPath); + } + } + } + + return found; + } + + private static String generateUpgradeVersionString(String from, String to) { + StringBuilder sb = new StringBuilder(); + sb.append(from).append("-to-").append(to); + return sb.toString(); + } +} http://git-wip-us.apache.org/repos/asf/sentry/blob/65eceff0/sentry-service/sentry-service-server/src/test/java/org/apache/sentry/provider/db/service/persistent/TestSentryUpgradeOrder.java ---------------------------------------------------------------------- diff --git a/sentry-service/sentry-service-server/src/test/java/org/apache/sentry/provider/db/service/persistent/TestSentryUpgradeOrder.java b/sentry-service/sentry-service-server/src/test/java/org/apache/sentry/provider/db/service/persistent/TestSentryUpgradeOrder.java new file mode 100644 index 0000000..4d0141e --- /dev/null +++ b/sentry-service/sentry-service-server/src/test/java/org/apache/sentry/provider/db/service/persistent/TestSentryUpgradeOrder.java @@ -0,0 +1,187 @@ +/** + * 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. + */ +package org.apache.sentry.provider.db.service.persistent; + +import static org.junit.Assert.assertEquals; + +import java.io.IOException; +import java.io.StringReader; +import java.util.Arrays; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import org.apache.commons.lang.StringUtils; +import org.junit.Test; + +public class TestSentryUpgradeOrder { + @Test + public void testReadUpgradeOrderGraphInNormalOrder() throws IOException { + List<String> normalOrder = Arrays.asList( + "1.7.0-to-1.8.0", + "1.8.0-to-2.0.0", + "2.0.0-to-2.1.0" + ); + + Map<String, List<String>> upgradeGraph = + SentryUpgradeOrder.readUpgradeGraph(new StringReader(StringUtils.join(normalOrder, "\n"))); + + // The returned graph should be in the following form: + // key: 1.7.0 value: 1.8.0 + // key: 1.8.0 value: 2.0.0 + // key: 2.0.0 value: 2.1.0 + assertEquals(3, upgradeGraph.size()); + assertEquals(Arrays.asList("1.8.0"), upgradeGraph.get("1.7.0")); + assertEquals(Arrays.asList("2.0.0"), upgradeGraph.get("1.8.0")); + assertEquals(Arrays.asList("2.1.0"), upgradeGraph.get("2.0.0")); + } + + @Test + public void testReadUpgradeOrderGraphInReverseOrder() throws IOException { + List<String> simpleOrder = Arrays.asList( + "2.0.0-to-2.1.0", + "1.8.0-to-2.0.0", + "1.7.0-to-1.8.0" + ); + + Map<String, List<String>> upgradeGraph = + SentryUpgradeOrder.readUpgradeGraph(new StringReader(StringUtils.join(simpleOrder, "\n"))); + + // The returned graph should be in the following form: + // key: 1.7.0 value: 1.8.0 + // key: 1.8.0 value: 2.0.0 + // key: 2.0.0 value: 2.1.0 + assertEquals(3, upgradeGraph.size()); + assertEquals(Arrays.asList("1.8.0"), upgradeGraph.get("1.7.0")); + assertEquals(Arrays.asList("2.0.0"), upgradeGraph.get("1.8.0")); + assertEquals(Arrays.asList("2.1.0"), upgradeGraph.get("2.0.0")); + } + + @Test + public void testReadUpgradeOrderGraphWithSameSourceVersions() throws IOException { + List<String> normalOrder = Arrays.asList( + "1.7.0-to-1.8.0", + "1.7.0-to-2.0.0", + "1.8.0-to-2.0.0", + "2.0.0-to-2.1.0", + "2.0.0-to-2.2.0" + ); + + Map<String, List<String>> upgradeGraph = + SentryUpgradeOrder.readUpgradeGraph(new StringReader(StringUtils.join(normalOrder, "\n"))); + + // The returned graph should be in the following form: + // key: 1.7.0 value: 1.8.0, 2.0.0 + // key: 1.8.0 value: 2.0.0 + // key: 2.0.0 value: 2.1.0, 2.2.0 + assertEquals(3, upgradeGraph.size()); + assertEquals(Arrays.asList("1.8.0", "2.0.0"), upgradeGraph.get("1.7.0")); + assertEquals(Arrays.asList("2.0.0"), upgradeGraph.get("1.8.0")); + assertEquals(Arrays.asList("2.1.0", "2.2.0"), upgradeGraph.get("2.0.0")); + } + + @Test + public void testReadUpgradeOrderGraphWithIgnoredVersions() throws IOException { + List<String> simpleOrder = Arrays.asList( + "# comment", // comments are ignored + "# 1.8.0-to-1.9.0",// comments are ignored + "2.0.0-to-2.0.0", // same source/target versions are ignored + "1.8.0-to-", // no target versions are ignored + "-to-1.8.0", // no source versions are ignored + "1.8.0-1.7.0", // versions without -to- are ignored + "1.8.0-to-1.7.0-to-2.0.0", // more than two versions are ignored + "1.7.0-to-1.8.0" + ); + + Map<String, List<String>> upgradeGraph = + SentryUpgradeOrder.readUpgradeGraph(new StringReader(StringUtils.join(simpleOrder, "\n"))); + + // The returned graph should be in the following form: + // key: 1.7.0 value: 1.8.0 + assertEquals(1, upgradeGraph.size()); + assertEquals(Arrays.asList("1.8.0"), upgradeGraph.get("1.7.0")); + } + + @Test + public void testGetUpgradePathUsingSingleSourceVersions() { + Map<String, List<String>> normalOrder = new HashMap<String, List<String>>() {{ + put("1.7.0", Arrays.asList("1.8.0")); + put("1.8.0", Arrays.asList("2.0.0")); + put("2.0.0", Arrays.asList("2.1.0")); + }}; + + List<String> upgradePath; + + // The returned upgrade path should be: 1.8.0 -> 2.0.0 -> 2.1.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(normalOrder, "1.8.0", "2.1.0"); + assertEquals(2, upgradePath.size()); + assertEquals("1.8.0-to-2.0.0", upgradePath.get(0)); + assertEquals("2.0.0-to-2.1.0", upgradePath.get(1)); + + // The returned upgrade path should be: 1.7.0 -> 1.8.0 -> 2.0.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(normalOrder, "1.7.0", "2.0.0"); + assertEquals(2, upgradePath.size()); + assertEquals("1.7.0-to-1.8.0", upgradePath.get(0)); + assertEquals("1.8.0-to-2.0.0", upgradePath.get(1)); + + // This upgrade path does not exist + upgradePath = SentryUpgradeOrder.getUpgradePath(normalOrder, "1.8.0", "3.1.0"); + assertEquals(0, upgradePath.size()); + + // This upgrade path does not exist + upgradePath = SentryUpgradeOrder.getUpgradePath(normalOrder, "1.5.0", "2.1.0"); + assertEquals(0, upgradePath.size()); + } + + @Test + public void testGetUpgradePathUsingMultipleSourceTargetVersions() { + Map<String, List<String>> multiVersionsOrder = new HashMap<String, List<String>>() {{ + put("1.7.0", Arrays.asList("1.8.0", "2.0.0")); + put("1.8.0", Arrays.asList("2.0.0")); + put("1.9.0", Arrays.asList("2.1.0")); + put("2.0.0", Arrays.asList("2.1.0")); + }}; + + List<String> upgradePath; + + // The returned upgrade path should be: 1.8.0 -> 2.0.0 -> 2.1.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(multiVersionsOrder, "1.8.0", "2.1.0"); + assertEquals(2, upgradePath.size()); + assertEquals("1.8.0-to-2.0.0", upgradePath.get(0)); + assertEquals("2.0.0-to-2.1.0", upgradePath.get(1)); + + // The returned upgrade path should be: 1.7.0 -> 1.8.0 -> 2.0.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(multiVersionsOrder, "1.7.0", "2.0.0"); + assertEquals(2, upgradePath.size()); + assertEquals("1.7.0-to-1.8.0", upgradePath.get(0)); + assertEquals("1.8.0-to-2.0.0", upgradePath.get(1)); + + // The returned upgrade path should be: 1.9.0 -> 2.1.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(multiVersionsOrder, "1.9.0", "2.1.0"); + assertEquals(1, upgradePath.size()); + + // The returned upgrade path should be: 1.7.0 -> 1.8.0 -> 2.0.0 + upgradePath = SentryUpgradeOrder.getUpgradePath(multiVersionsOrder, "1.7.0", "2.0.0"); + assertEquals(2, upgradePath.size()); + assertEquals("1.7.0-to-1.8.0", upgradePath.get(0)); + assertEquals("1.8.0-to-2.0.0", upgradePath.get(1)); + + // This upgrade path does not exist + upgradePath = SentryUpgradeOrder.getUpgradePath(multiVersionsOrder, "1.9.0", "2.0.0"); + assertEquals(0, upgradePath.size()); + } +}