RANGER-2173: Optimize Trie constuction and Policy lookup
Project: http://git-wip-us.apache.org/repos/asf/ranger/repo Commit: http://git-wip-us.apache.org/repos/asf/ranger/commit/97f7b4da Tree: http://git-wip-us.apache.org/repos/asf/ranger/tree/97f7b4da Diff: http://git-wip-us.apache.org/repos/asf/ranger/diff/97f7b4da Branch: refs/heads/ranger-1 Commit: 97f7b4da8acd1fa2e80fc67297e1ead1f0ea297f Parents: cd42a61 Author: Abhay Kulkarni <akulka...@hortonworks.com> Authored: Tue Jul 31 16:30:47 2018 -0700 Committer: Mehul Parikh <me...@apache.org> Committed: Wed Aug 29 14:18:32 2018 +0530 ---------------------------------------------------------------------- .../ranger/plugin/util/RangerResourceTrie.java | 450 +++++++++++-------- agents-common/src/test/resources/log4j.xml | 4 + 2 files changed, 267 insertions(+), 187 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ranger/blob/97f7b4da/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java index e7e8cf5..1723d14 100644 --- a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java +++ b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java @@ -21,6 +21,7 @@ package org.apache.ranger.plugin.util; import org.apache.commons.collections.CollectionUtils; +import org.apache.commons.lang.StringUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.ranger.plugin.model.RangerPolicy.RangerPolicyResource; @@ -31,7 +32,6 @@ import org.apache.ranger.plugin.resourcematcher.RangerResourceMatcher; import java.util.ArrayList; import java.util.Collection; -import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.List; @@ -39,14 +39,16 @@ import java.util.Map; public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { private static final Log LOG = LogFactory.getLog(RangerResourceTrie.class); + private static final Log PERF_TRIE_INIT_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.init"); + private static final Log PERF_TRIE_OP_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.op"); private static final String DEFAULT_WILDCARD_CHARS = "*?"; - private final String resourceName; - private final boolean optIgnoreCase; - private final boolean optWildcard; - private final String wildcardChars; - private final TrieNode root; + private final String resourceName; + private final boolean optIgnoreCase; + private final boolean optWildcard; + private final String wildcardChars; + private final TrieNode<T> root; private final Comparator<T> comparator; public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T> evaluators) { @@ -58,6 +60,12 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { LOG.debug("==> RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ")"); } + RangerPerfTracer perf = null; + + if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) { + perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie(name=" + resourceDef.getName() + ")"); + } + Map<String, String> matcherOptions = resourceDef.getMatcherOptions(); boolean optReplaceTokens = RangerAbstractResourceMatcher.getOptionReplaceTokens(matcherOptions); @@ -78,7 +86,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { this.optIgnoreCase = RangerAbstractResourceMatcher.getOptionIgnoreCase(matcherOptions); this.optWildcard = RangerAbstractResourceMatcher.getOptionWildCard(matcherOptions); this.wildcardChars = optWildcard ? DEFAULT_WILDCARD_CHARS + tokenReplaceSpecialChars : "" + tokenReplaceSpecialChars; - this.root = new TrieNode(Character.valueOf((char)0)); + this.root = new TrieNode<>(null); this.comparator = comparator; for(T evaluator : evaluators) { @@ -112,7 +120,15 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { root.postSetup(null, comparator); - LOG.info(toString()); + RangerPerfTracer.logAlways(perf); + + if (PERF_TRIE_INIT_LOG.isTraceEnabled()) { + PERF_TRIE_INIT_LOG.trace(toString()); + + StringBuilder sb = new StringBuilder(); + root.toString("", sb); + PERF_TRIE_INIT_LOG.trace("Trie Dump:\n{" + sb.toString() + "}"); + } if(LOG.isDebugEnabled()) { LOG.debug("<== RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + "): " + toString()); @@ -140,7 +156,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { return null; } - public TrieData getTrieData() { + private TrieData getTrieData() { TrieData ret = new TrieData(); root.populateTrieData(ret); @@ -149,34 +165,33 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { return ret; } - public int getMaxDepth() { + private int getMaxDepth() { return root.getMaxDepth(); } - private final Character getLookupChar(char ch) { - if(optIgnoreCase) { - ch = Character.toLowerCase(ch); - } + private Character getLookupChar(char ch) { + return optIgnoreCase ? Character.toLowerCase(ch) : ch; + } - return Character.valueOf(ch); + private Character getLookupChar(String str, int index) { + return getLookupChar(str.charAt(index)); } private void insert(String resource, boolean isRecursive, T evaluator) { - TrieNode curr = root; - boolean isWildcard = false; - final int len = resource.length(); - for(int i = 0; i < len; i++) { - Character ch = getLookupChar(resource.charAt(i)); + RangerPerfTracer perf = null; - if(optWildcard) { - if (wildcardChars.indexOf(ch) != -1) { - isWildcard = true; - break; - } - } + if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) { + perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.insert(resource=" + resource + ")"); + } + + TrieNode<T> curr = root; + + final String prefix = getNonWildcardPrefix(resource); + final boolean isWildcard = prefix.length() != resource.length(); - curr = curr.getOrCreateChild(ch); + if (StringUtils.isNotEmpty(prefix)) { + curr = curr.getOrCreateChild(prefix); } if(isWildcard || isRecursive) { @@ -184,6 +199,20 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { } else { curr.addEvaluator(evaluator); } + + RangerPerfTracer.logAlways(perf); + } + + private String getNonWildcardPrefix(String str) { + if (!optWildcard) return str; + int minIndex = str.length(); + for (int i = 0; i < wildcardChars.length(); i++) { + int index = str.indexOf(wildcardChars.charAt(i)); + if (index != -1 && index < minIndex) { + minIndex = index; + } + } + return str.substring(0, minIndex); } private List<T> getEvaluatorsForResource(String resource) { @@ -191,29 +220,38 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { LOG.debug("==> RangerResourceTrie.getEvaluatorsForResource(" + resource + ")"); } - List<T> ret = null; - TrieNode curr = root; + RangerPerfTracer perf = null; + + if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) { + perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerResourceTrie.getEvaluatorsForResource(resource=" + resource + ")"); + } - final int len = resource.length(); - for(int i = 0; i < len; i++) { - Character ch = getLookupChar(resource.charAt(i)); - TrieNode child = curr.getChild(ch); + TrieNode<T> curr = root; - if(child == null) { - ret = curr.getWildcardEvaluators(); - curr = null; // so that curr.getEvaluators() will not be called below + final int len = resource.length(); + int i = 0; + + while (i < len) { + final TrieNode<T> child = curr.getChild(getLookupChar(resource, i)); + + if (child == null) { break; } - curr = child; - } + final String childStr = child.getStr(); - if(ret == null) { - if(curr != null) { - ret = curr.getEvaluators(); + if (!resource.regionMatches(optIgnoreCase, i, childStr, 0, childStr.length())) { + break; } + + curr = child; + i += childStr.length(); } + List<T> ret = i == len ? curr.getEvaluators() : curr.getWildcardEvaluators(); + + RangerPerfTracer.logAlways(perf); + if(LOG.isDebugEnabled()) { LOG.debug("<== RangerResourceTrie.getEvaluatorsForResource(" + resource + "): evaluatorCount=" + (ret == null ? 0 : ret.size())); } @@ -240,7 +278,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { if (ret == null) { // first resource: don't create map yet ret = resourceEvaluators; } else if (ret != resourceEvaluators) { // if evaluator list is same as earlier resources, retain the list, else create a map - evaluatorsMap = new HashMap(); + evaluatorsMap = new HashMap<>(); for (T evaluator : ret) { evaluatorsMap.put(evaluator.getId(), evaluator); @@ -261,7 +299,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { ret = new ArrayList<>(evaluatorsMap.values()); if (comparator != null) { - Collections.sort(ret, comparator); + ret.sort(comparator); } } @@ -294,7 +332,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { return sb.toString(); } - public class TrieData { + class TrieData { int nodeCount; int leafNodeCount; int singleChildNodeCount; @@ -304,209 +342,247 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { int evaluatorListRefCount; int wildcardEvaluatorListRefCount; } -} -class TrieNode<T extends RangerPolicyResourceEvaluator> { - private final Character c; - private Map<Character, TrieNode> children; - private List<T> evaluators; - private List<T> wildcardEvaluators; - private boolean isSharingParentWildcardEvaluators; + class TrieNode<U extends RangerPolicyResourceEvaluator> { + private String str; + private Map<Character, TrieNode<U>> children = new HashMap<>(); + private List<U> evaluators; + private List<U> wildcardEvaluators; + private boolean isSharingParentWildcardEvaluators; - TrieNode(Character c) { - this.c = c; - } + TrieNode(String str) { + this.str = str; + } - Character getChar() { - return c; - } + String getStr() { + return str; + } - Map<Character, TrieNode> getChildren() { - return children; - } + void setStr(String str) { + this.str = str; + } - List<T> getEvaluators() { - return evaluators; - } + Map<Character, TrieNode<U>> getChildren() { + return children; + } - List<T> getWildcardEvaluators() { - return wildcardEvaluators; - } + List<U> getEvaluators() { + return evaluators; + } - TrieNode getChild(Character c) { - TrieNode ret = children == null ? null : children.get(c); + List<U> getWildcardEvaluators() { + return wildcardEvaluators; + } - return ret; - } + TrieNode<U> getChild(Character ch) { + return children == null ? null : children.get(ch); + } - void populateTrieData(RangerResourceTrie.TrieData trieData) { - trieData.nodeCount++; + void populateTrieData(RangerResourceTrie.TrieData trieData) { + trieData.nodeCount++; - if(wildcardEvaluators != null) { - if(isSharingParentWildcardEvaluators) { - trieData.wildcardEvaluatorListRefCount++; - } else { - trieData.wildcardEvaluatorListCount++; + if (wildcardEvaluators != null) { + if (isSharingParentWildcardEvaluators) { + trieData.wildcardEvaluatorListRefCount++; + } else { + trieData.wildcardEvaluatorListCount++; + } } - } - if(evaluators != null) { - if(evaluators == wildcardEvaluators) { - trieData.evaluatorListRefCount++; - } else { - trieData.evaluatorListCount++; + if (evaluators != null) { + if (evaluators == wildcardEvaluators) { + trieData.evaluatorListRefCount++; + } else { + trieData.evaluatorListCount++; + } } - } - if(children != null && !children.isEmpty()) { - if(children.size() == 1) { - trieData.singleChildNodeCount++; - } + if (children != null && !children.isEmpty()) { + if (children.size() == 1) { + trieData.singleChildNodeCount++; + } - for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { - TrieNode child = entry.getValue(); + for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) { + TrieNode child = entry.getValue(); - child.populateTrieData(trieData); + child.populateTrieData(trieData); + } + } else { + trieData.leafNodeCount++; } - } else { - trieData.leafNodeCount++; } - } - int getMaxDepth() { - int ret = 0; + int getMaxDepth() { + int ret = 0; - if(children != null) { - for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { - TrieNode child = entry.getValue(); + if (children != null) { + for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) { + TrieNode<U> child = entry.getValue(); - int maxChildDepth = child.getMaxDepth(); + int maxChildDepth = child.getMaxDepth(); - if(maxChildDepth > ret) { - ret = maxChildDepth; + if (maxChildDepth > ret) { + ret = maxChildDepth; + } } } - } - - return ret + 1; - } - TrieNode getOrCreateChild(Character c) { - if(children == null) { - children = new HashMap<>(); + return ret + 1; } - TrieNode child = children.get(c); + TrieNode<U> getOrCreateChild(String str) { + int len = str.length(); - if(child == null) { - child = new TrieNode(c); - children.put(c, child); - } + TrieNode<U> child = children.get(getLookupChar(str, 0)); - return child; - } + if (child == null) { + child = new TrieNode<>(str); + addChild(child); + } else { + final String childStr = child.getStr(); + final int childStrLen = childStr.length(); + + if (!StringUtils.equals(childStr, str)) { + final int numOfCharactersToMatch = childStrLen < len ? childStrLen : len; + int index = 1; + for (; index < numOfCharactersToMatch; index++) { + if (getLookupChar(childStr, index) != getLookupChar(str, index)) { + break; + } + } + if (index == numOfCharactersToMatch) { + // Matched all + if (childStrLen > len) { + // Existing node has longer string, need to break up this node + TrieNode<U> newChild = new TrieNode<>(str); + this.addChild(newChild); + child.setStr(childStr.substring(index)); + newChild.addChild(child); + child = newChild; + } else { + // This is a longer string, build a child with leftover string + child = child.getOrCreateChild(str.substring(index)); + } + } else { + // Partial match for both; both have leftovers + String matchedPart = str.substring(0, index); + TrieNode<U> newChild = new TrieNode<>(matchedPart); + this.addChild(newChild); + child.setStr(childStr.substring(index)); + newChild.addChild(child); + child = newChild.getOrCreateChild(str.substring(index)); + } + } + } - void addEvaluator(T evaluator) { - if(evaluators == null) { - evaluators = new ArrayList<>(); + return child; } - if(!evaluators.contains(evaluator)) { - evaluators.add(evaluator); + private void addChild(TrieNode<U> child) { + children.put(getLookupChar(child.getStr(), 0), child); } - } - void addWildcardEvaluator(T evaluator) { - if(wildcardEvaluators == null) { - wildcardEvaluators = new ArrayList<>(); - } + void addEvaluator(U evaluator) { + if (evaluators == null) { + evaluators = new ArrayList<>(); + } - if(!wildcardEvaluators.contains(evaluator)) { - wildcardEvaluators.add(evaluator); + if (!evaluators.contains(evaluator)) { + evaluators.add(evaluator); + } } - } - void postSetup(List<T> parentWildcardEvaluators, Comparator<T> comparator) { - // finalize wildcard-evaluators list by including parent's wildcard evaluators - if(parentWildcardEvaluators != null) { - if(CollectionUtils.isEmpty(this.wildcardEvaluators)) { - this.wildcardEvaluators = parentWildcardEvaluators; - } else { - for (T evaluator : parentWildcardEvaluators) { - addWildcardEvaluator(evaluator); - } + void addWildcardEvaluator(U evaluator) { + if (wildcardEvaluators == null) { + wildcardEvaluators = new ArrayList<>(); + } + + if (!wildcardEvaluators.contains(evaluator)) { + wildcardEvaluators.add(evaluator); } } - this.isSharingParentWildcardEvaluators = wildcardEvaluators == parentWildcardEvaluators; - // finalize evaluators list by including wildcard evaluators - if(wildcardEvaluators != null) { - if(CollectionUtils.isEmpty(this.evaluators)) { - this.evaluators = wildcardEvaluators; - } else { - for (T evaluator : wildcardEvaluators) { - addEvaluator(evaluator); + void postSetup(List<U> parentWildcardEvaluators, Comparator<U> comparator) { + // finalize wildcard-evaluators list by including parent's wildcard evaluators + if (parentWildcardEvaluators != null) { + if (CollectionUtils.isEmpty(this.wildcardEvaluators)) { + this.wildcardEvaluators = parentWildcardEvaluators; + } else { + for (U evaluator : parentWildcardEvaluators) { + addWildcardEvaluator(evaluator); + } } } - } + this.isSharingParentWildcardEvaluators = wildcardEvaluators == parentWildcardEvaluators; - if (comparator != null) { - if (!isSharingParentWildcardEvaluators && CollectionUtils.isNotEmpty(wildcardEvaluators)) { - Collections.sort(wildcardEvaluators, comparator); + // finalize evaluators list by including wildcard evaluators + if (wildcardEvaluators != null) { + if (CollectionUtils.isEmpty(this.evaluators)) { + this.evaluators = wildcardEvaluators; + } else { + for (U evaluator : wildcardEvaluators) { + addEvaluator(evaluator); + } + } } - if (evaluators != wildcardEvaluators && CollectionUtils.isNotEmpty(evaluators)) { - Collections.sort(evaluators, comparator); + if (comparator != null) { + if (!isSharingParentWildcardEvaluators && CollectionUtils.isNotEmpty(wildcardEvaluators)) { + wildcardEvaluators.sort(comparator); + } + + if (evaluators != wildcardEvaluators && CollectionUtils.isNotEmpty(evaluators)) { + evaluators.sort(comparator); + } } - } - if(children != null) { - for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { - TrieNode child = entry.getValue(); + if (children != null) { + for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) { + TrieNode<U> child = entry.getValue(); - child.postSetup(wildcardEvaluators, comparator); + child.postSetup(wildcardEvaluators, comparator); + } } } - } - public void toString(String prefix, StringBuilder sb) { - String nodeValue = prefix; + public void toString(String prefix, StringBuilder sb) { + String nodeValue = prefix; - if(c != 0) { - nodeValue += c; - } + if (str != null) { + nodeValue += str; + } - sb.append("nodeValue=").append(nodeValue); - sb.append("; childCount=").append(children == null ? 0 : children.size()); - sb.append("; evaluators=[ "); - if(evaluators != null) { - for(T evaluator : evaluators) { - sb.append(evaluator.getId()).append(" "); + sb.append("nodeValue=").append(nodeValue); + sb.append("; childCount=").append(children == null ? 0 : children.size()); + sb.append("; evaluators=[ "); + if (evaluators != null) { + for (U evaluator : evaluators) { + sb.append(evaluator.getId()).append(" "); + } } - } - sb.append("]"); + sb.append("]"); - sb.append("; wildcardEvaluators=[ "); - if(wildcardEvaluators != null) { - for(T evaluator : wildcardEvaluators) { - sb.append(evaluator.getId()).append(" "); + sb.append("; wildcardEvaluators=[ "); + if (wildcardEvaluators != null) { + for (U evaluator : wildcardEvaluators) { + sb.append(evaluator.getId()).append(" "); + } } - } - sb.append("]"); - sb.append(Character.LINE_SEPARATOR); + sb.append("]\n"); - if(children != null) { - for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { - TrieNode child = entry.getValue(); + if (children != null) { + for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) { + TrieNode<U> child = entry.getValue(); - child.toString(nodeValue, sb); + child.toString(nodeValue, sb); + } } } - } - public void clear() { - children = null; - evaluators = null; - wildcardEvaluators = null; + public void clear() { + children = null; + evaluators = null; + wildcardEvaluators = null; + } } } http://git-wip-us.apache.org/repos/asf/ranger/blob/97f7b4da/agents-common/src/test/resources/log4j.xml ---------------------------------------------------------------------- diff --git a/agents-common/src/test/resources/log4j.xml b/agents-common/src/test/resources/log4j.xml index d1a6f1c..714d463 100644 --- a/agents-common/src/test/resources/log4j.xml +++ b/agents-common/src/test/resources/log4j.xml @@ -35,6 +35,10 @@ </layout> </appender> <!-- + <logger name="org.apache.ranger.perf.resourcetrie" additivity="false"> + <level value="debug" /> + <appender-ref ref="ranger_perf_appender" /> + </logger> <logger name="org.apache.ranger.perf.policyengine.getResourceACLs" additivity="false"> <level value="debug" /> <appender-ref ref="ranger_perf_appender" />