ranger-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From me...@apache.org
Subject [17/27] ranger git commit: RANGER-2188: Support multiple threads to build Trie and on-lookup post-setup for Trie nodes
Date Thu, 30 Aug 2018 10:58:27 GMT
RANGER-2188: Support multiple threads to build Trie and on-lookup post-setup for Trie nodes


Project: http://git-wip-us.apache.org/repos/asf/ranger/repo
Commit: http://git-wip-us.apache.org/repos/asf/ranger/commit/ca7a8d70
Tree: http://git-wip-us.apache.org/repos/asf/ranger/tree/ca7a8d70
Diff: http://git-wip-us.apache.org/repos/asf/ranger/diff/ca7a8d70

Branch: refs/heads/ranger-1
Commit: ca7a8d7020cc1982d44678178c7b2a8f55e4f013
Parents: 0ab1077
Author: Abhay Kulkarni <akulkarni@hortonworks.com>
Authored: Tue Aug 14 10:42:42 2018 -0700
Committer: Mehul Parikh <mehul@apache.org>
Committed: Wed Aug 29 14:31:01 2018 +0530

----------------------------------------------------------------------
 .../contextenricher/RangerTagEnricher.java      |   9 +
 .../policyengine/RangerPolicyEngineOptions.java |  15 +-
 .../policyengine/RangerPolicyRepository.java    |  25 +-
 .../ranger/plugin/util/RangerResourceTrie.java  | 383 ++++++++++++++++---
 .../plugin/policyengine/TestPolicyEngine.java   |   7 +
 5 files changed, 372 insertions(+), 67 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/ranger/blob/ca7a8d70/agents-common/src/main/java/org/apache/ranger/plugin/contextenricher/RangerTagEnricher.java
----------------------------------------------------------------------
diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/contextenricher/RangerTagEnricher.java
b/agents-common/src/main/java/org/apache/ranger/plugin/contextenricher/RangerTagEnricher.java
index b12d8ff..d671b73 100644
--- a/agents-common/src/main/java/org/apache/ranger/plugin/contextenricher/RangerTagEnricher.java
+++ b/agents-common/src/main/java/org/apache/ranger/plugin/contextenricher/RangerTagEnricher.java
@@ -62,6 +62,8 @@ public class RangerTagEnricher extends RangerAbstractContextEnricher {
 	private static final Log LOG = LogFactory.getLog(RangerTagEnricher.class);
 
 	private static final Log PERF_CONTEXTENRICHER_INIT_LOG = RangerPerfTracer.getPerfLogger("contextenricher.init");
+	private static final Log PERF_TRIE_OP_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.retrieval");
+
 
 	public static final String TAG_REFRESHER_POLLINGINTERVAL_OPTION = "tagRefresherPollingInterval";
 	public static final String TAG_RETRIEVER_CLASSNAME_OPTION       = "tagRetrieverClassName";
@@ -401,6 +403,12 @@ public class RangerTagEnricher extends RangerAbstractContextEnricher
{
 		if (resource == null || resource.getKeys() == null || resource.getKeys().isEmpty() || serviceResourceTrie
== null) {
 			ret = enrichedServiceTags.getServiceResourceMatchers();
 		} else {
+			RangerPerfTracer perf = null;
+
+			if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) {
+				perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerTagEnricher.getEvaluators(resource="
+ resource.getAsString() + ")");
+			}
+
 			Set<String> resourceKeys = resource.getKeys();
 			List<List<RangerServiceResourceMatcher>> serviceResourceMatchersList = null;
 			List<RangerServiceResourceMatcher> smallestList = null;
@@ -452,6 +460,7 @@ public class RangerTagEnricher extends RangerAbstractContextEnricher {
 					ret = smallestList;
 				}
 			}
+			RangerPerfTracer.logAlways(perf);
 		}
 
 		if(ret == null) {

http://git-wip-us.apache.org/repos/asf/ranger/blob/ca7a8d70/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyEngineOptions.java
----------------------------------------------------------------------
diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyEngineOptions.java
b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyEngineOptions.java
index b76820c..01dbbe8 100644
--- a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyEngineOptions.java
+++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyEngineOptions.java
@@ -33,6 +33,7 @@ public class RangerPolicyEngineOptions {
 	public boolean evaluateDelegateAdminOnly = false;
 	public boolean enableTagEnricherWithLocalRefresher = false;
 	public boolean disableAccessEvaluationWithPolicyACLSummary = true;
+	public boolean optimizeTrieForRetrieval = true;
 
 	private RangerServiceDefHelper serviceDefHelper;
 
@@ -50,6 +51,8 @@ public class RangerPolicyEngineOptions {
 		evaluateDelegateAdminOnly = false;
 		enableTagEnricherWithLocalRefresher = false;
 		disableAccessEvaluationWithPolicyACLSummary = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.access.evaluation.with.policy.acl.summary",
true);
+		optimizeTrieForRetrieval = conf.getBoolean(propertyPrefix + ".policyengine.option.optimize.trie.for.retrieval",
true);
+
 	}
 
 	public void configureDefaultRangerAdmin(Configuration conf, String propertyPrefix) {
@@ -62,6 +65,8 @@ public class RangerPolicyEngineOptions {
 		evaluateDelegateAdminOnly = false;
 		enableTagEnricherWithLocalRefresher = false;
 		disableAccessEvaluationWithPolicyACLSummary = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.access.evaluation.with.policy.acl.summary",
true);
+		optimizeTrieForRetrieval = conf.getBoolean(propertyPrefix + ".policyengine.option.optimize.trie.for.retrieval",
false);
+
 	}
 
 	public void configureDelegateAdmin(Configuration conf, String propertyPrefix) {
@@ -69,6 +74,8 @@ public class RangerPolicyEngineOptions {
 		disableCustomConditions = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.custom.conditions",
true);
 		disableTagPolicyEvaluation = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.tagpolicy.evaluation",
true);
 		disableTrieLookupPrefilter = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.trie.lookup.prefilter",
false);
+		optimizeTrieForRetrieval = conf.getBoolean(propertyPrefix + ".policyengine.option.optimize.trie.for.retrieval",
false);
+
 
 		cacheAuditResults = false;
 		evaluateDelegateAdminOnly = true;
@@ -81,6 +88,8 @@ public class RangerPolicyEngineOptions {
 		disableCustomConditions = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.custom.conditions",
true);
 		disableTagPolicyEvaluation = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.tagpolicy.evaluation",
false);
 		disableTrieLookupPrefilter = conf.getBoolean(propertyPrefix + ".policyengine.option.disable.trie.lookup.prefilter",
false);
+		optimizeTrieForRetrieval = conf.getBoolean(propertyPrefix + ".policyengine.option.optimize.trie.for.retrieval",
false);
+
 
 		cacheAuditResults = false;
 		evaluateDelegateAdminOnly = false;
@@ -111,7 +120,8 @@ public class RangerPolicyEngineOptions {
 					&& this.disableTrieLookupPrefilter == that.disableTrieLookupPrefilter
 					&& this.cacheAuditResults == that.cacheAuditResults
 					&& this.evaluateDelegateAdminOnly == that.evaluateDelegateAdminOnly
-					&& this.enableTagEnricherWithLocalRefresher == that.enableTagEnricherWithLocalRefresher;
+					&& this.enableTagEnricherWithLocalRefresher == that.enableTagEnricherWithLocalRefresher
+					&& this.optimizeTrieForRetrieval == that.optimizeTrieForRetrieval;
 		}
 		return ret;
 	}
@@ -133,6 +143,8 @@ public class RangerPolicyEngineOptions {
 		ret *= 2;
 		ret += enableTagEnricherWithLocalRefresher ? 1 : 0;
 		ret *= 2;
+		ret += optimizeTrieForRetrieval ? 1 : 0;
+		ret *= 2;
 		return ret;
 	}
 
@@ -144,6 +156,7 @@ public class RangerPolicyEngineOptions {
 				", disableContextEnrichers: " + disableContextEnrichers +
 				", disableCustomConditions: " + disableContextEnrichers +
 				", disableTrieLookupPrefilter: " + disableTrieLookupPrefilter +
+				", optimizeTrieForRetrieval: " + optimizeTrieForRetrieval +
 				" }";
 
 	}

http://git-wip-us.apache.org/repos/asf/ranger/blob/ca7a8d70/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java
----------------------------------------------------------------------
diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java
b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java
index 088b729..f1b9764 100644
--- a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java
+++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java
@@ -54,6 +54,7 @@ class RangerPolicyRepository {
     private static final Log LOG = LogFactory.getLog(RangerPolicyRepository.class);
 
     private static final Log PERF_CONTEXTENRICHER_INIT_LOG = RangerPerfTracer.getPerfLogger("contextenricher.init");
+    private static final Log PERF_TRIE_OP_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.retrieval");
 
     enum AuditModeEnum {
         AUDIT_ALL, AUDIT_NONE, AUDIT_DEFAULT
@@ -145,9 +146,9 @@ class RangerPolicyRepository {
             dataMaskResourceTrie  = null;
             rowFilterResourceTrie = null;
         } else {
-            policyResourceTrie    = createResourceTrieMap(policyEvaluators);
-            dataMaskResourceTrie  = createResourceTrieMap(dataMaskPolicyEvaluators);
-            rowFilterResourceTrie = createResourceTrieMap(rowFilterPolicyEvaluators);
+            policyResourceTrie    = createResourceTrieMap(policyEvaluators, options.optimizeTrieForRetrieval);
+            dataMaskResourceTrie  = createResourceTrieMap(dataMaskPolicyEvaluators, options.optimizeTrieForRetrieval);
+            rowFilterResourceTrie = createResourceTrieMap(rowFilterPolicyEvaluators, options.optimizeTrieForRetrieval);
         }
     }
 
@@ -190,9 +191,9 @@ class RangerPolicyRepository {
             dataMaskResourceTrie  = null;
             rowFilterResourceTrie = null;
         } else {
-            policyResourceTrie    = createResourceTrieMap(policyEvaluators);
-            dataMaskResourceTrie  = createResourceTrieMap(dataMaskPolicyEvaluators);
-            rowFilterResourceTrie = createResourceTrieMap(rowFilterPolicyEvaluators);
+            policyResourceTrie    = createResourceTrieMap(policyEvaluators, options.optimizeTrieForRetrieval);
+            dataMaskResourceTrie  = createResourceTrieMap(dataMaskPolicyEvaluators, options.optimizeTrieForRetrieval);
+            rowFilterResourceTrie = createResourceTrieMap(rowFilterPolicyEvaluators, options.optimizeTrieForRetrieval);
         }
     }
 
@@ -383,6 +384,12 @@ class RangerPolicyRepository {
         List<RangerPolicyEvaluator> ret          = null;
         Set<String>                 resourceKeys = resource == null ? null : resource.getKeys();
 
+        RangerPerfTracer perf = null;
+
+        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) {
+            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerPolicyRepository.getLikelyMatchEvaluators(resource="
+ resource.getAsString() + ")");
+        }
+
         if(CollectionUtils.isNotEmpty(resourceKeys)) {
             List<List<RangerPolicyEvaluator>> resourceEvaluatorsList = null;
             List<RangerPolicyEvaluator> smallestList = null;
@@ -439,6 +446,8 @@ class RangerPolicyRepository {
             ret = Collections.emptyList();
         }
 
+        RangerPerfTracer.logAlways(perf);
+
         if(LOG.isDebugEnabled()) {
             LOG.debug("<== RangerPolicyRepository.getLikelyMatchPolicyEvaluators(" + resource.getAsString()
+ "): evaluatorCount=" + ret.size());
         }
@@ -876,14 +885,14 @@ class RangerPolicyRepository {
         return ret;
     }
 
-    private Map<String, RangerResourceTrie> createResourceTrieMap(List<RangerPolicyEvaluator>
evaluators) {
+    private Map<String, RangerResourceTrie> createResourceTrieMap(List<RangerPolicyEvaluator>
evaluators, boolean optimizeTrieForRetrieval) {
         final Map<String, RangerResourceTrie> ret;
 
         if (CollectionUtils.isNotEmpty(evaluators) && serviceDef != null &&
CollectionUtils.isNotEmpty(serviceDef.getResources())) {
             ret = new HashMap<>();
 
             for (RangerServiceDef.RangerResourceDef resourceDef : serviceDef.getResources())
{
-                ret.put(resourceDef.getName(), new RangerResourceTrie(resourceDef, evaluators,
RangerPolicyEvaluator.EVAL_ORDER_COMPARATOR));
+                ret.put(resourceDef.getName(), new RangerResourceTrie(resourceDef, evaluators,
RangerPolicyEvaluator.EVAL_ORDER_COMPARATOR, optimizeTrieForRetrieval));
             }
         } else {
             ret = null;

http://git-wip-us.apache.org/repos/asf/ranger/blob/ca7a8d70/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 10c6faa..e702684 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
@@ -24,6 +24,7 @@ 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.authorization.hadoop.config.RangerConfiguration;
 import org.apache.ranger.plugin.model.RangerPolicy.RangerPolicyResource;
 import org.apache.ranger.plugin.model.RangerServiceDef;
 import org.apache.ranger.plugin.policyresourcematcher.RangerPolicyResourceEvaluator;
@@ -36,6 +37,8 @@ import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.LinkedBlockingQueue;
 
 public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> {
     private static final Log LOG = LogFactory.getLog(RangerResourceTrie.class);
@@ -43,6 +46,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
     private static final Log PERF_TRIE_OP_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.op");
 
     private static final String DEFAULT_WILDCARD_CHARS = "*?";
+    private static final String TRIE_BUILDER_THREAD_COUNT = "ranger.policyengine.trie.builder.thread.count";
 
     private final String        resourceName;
     private final boolean       optIgnoreCase;
@@ -50,14 +54,15 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
     private final String        wildcardChars;
     private final TrieNode<T>   root;
     private final Comparator<T> comparator;
+    private final boolean       isOptimizedForRetrieval;
 
     public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T>
evaluators) {
-        this(resourceDef, evaluators, null);
+        this(resourceDef, evaluators, null, true);
     }
 
-    public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T>
evaluators, Comparator<T> comparator) {
+    public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T>
evaluators, Comparator<T> comparator, boolean isOptimizedForRetrieval) {
         if(LOG.isDebugEnabled()) {
-            LOG.debug("==> RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount="
+ evaluators.size() + ")");
+            LOG.debug("==> RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount="
+ evaluators.size() + ", isOptimizedForRetrieval=" + isOptimizedForRetrieval + ")");
         }
 
         RangerPerfTracer perf = null;
@@ -66,6 +71,15 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
             perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie(name="
+ resourceDef.getName() + ")");
         }
 
+        int builderThreadCount = RangerConfiguration.getInstance().getInt(TRIE_BUILDER_THREAD_COUNT,
1);
+
+        if (builderThreadCount < 1) {
+            builderThreadCount = 1;
+        }
+
+        LOG.info("builderThreadCount is set to ["+ builderThreadCount +"]");
+        PERF_TRIE_INIT_LOG.info("builderThreadCount is set to ["+ builderThreadCount +"]");
+
         Map<String, String> matcherOptions = resourceDef.getMatcherOptions();
 
         boolean optReplaceTokens = RangerAbstractResourceMatcher.getOptionReplaceTokens(matcherOptions);
@@ -86,40 +100,17 @@ 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<>(null);
         this.comparator    = comparator;
+        this.isOptimizedForRetrieval = isOptimizedForRetrieval;
 
-        for(T evaluator : evaluators) {
-            Map<String, RangerPolicyResource> policyResources = evaluator.getPolicyResource();
-            RangerPolicyResource              policyResource  = policyResources != null ?
policyResources.get(resourceName) : null;
-
-            if(policyResource == null) {
-                if(evaluator.getLeafResourceLevel() != null && resourceDef.getLevel()
!= null && evaluator.getLeafResourceLevel() < resourceDef.getLevel()) {
-                    root.addWildcardEvaluator(evaluator);
-                }
-
-                continue;
-            }
-
-            if(policyResource.getIsExcludes()) {
-                root.addWildcardEvaluator(evaluator);
-            } else {
-                RangerResourceMatcher resourceMatcher = evaluator.getResourceMatcher(resourceName);
+        TrieNode<T> tmpRoot = buildTrie(resourceDef, evaluators, comparator, builderThreadCount);
 
-                if(resourceMatcher != null && (resourceMatcher.isMatchAny())) {
-                    root.addWildcardEvaluator(evaluator);
-                } else {
-                    if(CollectionUtils.isNotEmpty(policyResource.getValues())) {
-                        for (String resource : policyResource.getValues()) {
-                            insert(resource, policyResource.getIsRecursive(), evaluator);
-                        }
-                    }
-                }
-            }
+        if (builderThreadCount > 1 && tmpRoot == null) { // if multi-threaded
trie-creation failed, build using a single thread
+            this.root = buildTrie(resourceDef, evaluators, comparator, 1);
+        } else {
+            this.root = tmpRoot;
         }
 
-        root.postSetup(null, comparator);
-
         RangerPerfTracer.logAlways(perf);
 
         if (PERF_TRIE_INIT_LOG.isDebugEnabled()) {
@@ -133,7 +124,7 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         }
 
         if(LOG.isDebugEnabled()) {
-            LOG.debug("<== RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount="
+ evaluators.size() + "): " + toString());
+            LOG.debug("<== RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount="
+ evaluators.size() + ", isOptimizedForRetrieval=" + isOptimizedForRetrieval + "): " + toString());
         }
     }
 
@@ -158,6 +149,138 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         return null;
     }
 
+    private TrieNode<T> buildTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T>
evaluators, Comparator<T> comparator, int builderThreadCount) {
+        if(LOG.isDebugEnabled()) {
+            LOG.debug("==> buildTrie(" + resourceDef.getName() + ", evaluatorCount=" +
evaluators.size() + ", isMultiThreaded=" + (builderThreadCount > 1) + ")");
+        }
+
+        TrieNode<T>                           ret                 = new TrieNode<>(null);
+        final boolean                         isMultiThreaded = builderThreadCount > 1;
+        final List<ResourceTrieBuilderThread> builderThreads;
+        final Map<Character, Integer>         builderThreadMap;
+        int                                   lastUsedThreadIndex = 0;
+
+        if (isMultiThreaded) {
+            builderThreads = new ArrayList<>();
+            for (int i = 0; i < builderThreadCount; i++) {
+                ResourceTrieBuilderThread t = new ResourceTrieBuilderThread(isOptimizedForRetrieval);
+                builderThreads.add(t);
+                t.start();
+            }
+            builderThreadMap = new HashMap<>();
+        } else {
+            builderThreads = null;
+            builderThreadMap = null;
+        }
+
+        for (T evaluator : evaluators) {
+            Map<String, RangerPolicyResource> policyResources = evaluator.getPolicyResource();
+            RangerPolicyResource policyResource = policyResources != null ? policyResources.get(resourceName)
: null;
+
+            if (policyResource == null) {
+                if (evaluator.getLeafResourceLevel() != null && resourceDef.getLevel()
!= null && evaluator.getLeafResourceLevel() < resourceDef.getLevel()) {
+                    ret.addWildcardEvaluator(evaluator);
+                }
+
+                continue;
+            }
+
+            if (policyResource.getIsExcludes()) {
+                ret.addWildcardEvaluator(evaluator);
+            } else {
+                RangerResourceMatcher resourceMatcher = evaluator.getResourceMatcher(resourceName);
+
+                if (resourceMatcher != null && (resourceMatcher.isMatchAny())) {
+                    ret.addWildcardEvaluator(evaluator);
+                } else {
+                    if (CollectionUtils.isNotEmpty(policyResource.getValues())) {
+                        for (String resource : policyResource.getValues()) {
+                            if (!isMultiThreaded) {
+                                insert(ret, resource, policyResource.getIsRecursive(), evaluator);
+                            } else {
+                                try {
+                                    lastUsedThreadIndex = insert(ret, resource, policyResource.getIsRecursive(),
evaluator, builderThreadMap, builderThreads, lastUsedThreadIndex);
+                                } catch (InterruptedException ex) {
+                                    LOG.error("Failed to dispatch " + resource + " to " +
builderThreads.get(lastUsedThreadIndex));
+                                    LOG.error("Failing and retrying with one thread");
+
+                                    ret = null;
+
+                                    break;
+                                }
+                            }
+                        }
+                        if (ret == null) {
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+        if (ret != null) {
+            if (isMultiThreaded) {
+                ret.setup(null, comparator);
+
+                for (ResourceTrieBuilderThread t : builderThreads) {
+                    t.setParentWildcardEvaluators(ret.wildcardEvaluators);
+                    try {
+                        // Send termination signal to each thread
+                        t.add("", false, null);
+                        // Wait for threads to finish work
+                        t.join();
+                        ret.getChildren().putAll(t.getSubtrees());
+                    } catch (InterruptedException ex) {
+                        LOG.error("BuilderThread " + t + " was interrupted:", ex);
+                        LOG.error("Failing and retrying with one thread");
+
+                        ret = null;
+
+                        break;
+                    }
+                }
+            } else {
+                if (isOptimizedForRetrieval) {
+                    RangerPerfTracer postSetupPerf = null;
+
+                    if (RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
+                        postSetupPerf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG,
"RangerResourceTrie(name=" + resourceDef.getName() + "-postSetup)");
+                    }
+
+                    ret.postSetup(null, comparator);
+
+                    RangerPerfTracer.logAlways(postSetupPerf);
+                } else {
+                    ret.setup(null, comparator);
+                }
+            }
+        }
+
+        if (isMultiThreaded) {
+            cleanUpThreads(builderThreads);
+        }
+
+        if(LOG.isDebugEnabled()) {
+            LOG.debug("<== buildTrie(" + resourceDef.getName() + ", evaluatorCount=" +
evaluators.size() + ", isMultiThreaded=" + isMultiThreaded + ") :" +  ret);
+        }
+
+        return ret;
+    }
+
+    private void cleanUpThreads(List<ResourceTrieBuilderThread> builderThreads) {
+        if (CollectionUtils.isNotEmpty(builderThreads)) {
+            for (ResourceTrieBuilderThread t : builderThreads) {
+                try {
+                    if (t.isAlive()) {
+                        t.interrupt();
+                        t.join();
+                    }
+                } catch (InterruptedException ex) {
+                    LOG.error("Could not terminate thread " + t);
+                }
+            }
+        }
+    }
+
     private TrieData getTrieData() {
         TrieData ret = new TrieData();
 
@@ -179,18 +302,37 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         return getLookupChar(str.charAt(index));
     }
 
-    private void insert(String resource, boolean isRecursive, T evaluator) {
+    private int insert(TrieNode<T> currentRoot, String resource, boolean isRecursive,
T evaluator, Map<Character, Integer> builderThreadMap, List<ResourceTrieBuilderThread>
builderThreads, int lastUsedThreadIndex) throws InterruptedException {
+        int          ret    = lastUsedThreadIndex;
+        final String prefix = getNonWildcardPrefix(resource);
+
+        if (StringUtils.isNotEmpty(prefix)) {
+            char    c     = getLookupChar(prefix.charAt(0));
+            Integer index = builderThreadMap.get(c);
+
+            if (index == null) {
+                ret = index = (lastUsedThreadIndex + 1) % builderThreads.size();
+                builderThreadMap.put(c, index);
+            }
+
+            builderThreads.get(index).add(resource, isRecursive, evaluator);
+        } else {
+            currentRoot.addWildcardEvaluator(evaluator);
+        }
+
+        return ret;
+    }
 
+    private void insert(TrieNode<T> currentRoot, String resource, boolean isRecursive,
T evaluator) {
         RangerPerfTracer perf = null;
 
         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();
+        TrieNode<T>   curr       = currentRoot;
+        final String  prefix     = getNonWildcardPrefix(resource);
+        final boolean isWildcard = prefix.length() != resource.length();
 
         if (StringUtils.isNotEmpty(prefix)) {
             curr = curr.getOrCreateChild(prefix);
@@ -206,14 +348,17 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
     }
 
     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);
     }
 
@@ -228,12 +373,16 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
             perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerResourceTrie.getEvaluatorsForResource(resource="
+ resource + ")");
         }
 
-        TrieNode<T> curr = root;
-
-        final int   len  = resource.length();
-        int         i    = 0;
+        TrieNode<T> curr   = root;
+        TrieNode<T> parent = null;
+        final int   len    = resource.length();
+        int         i      = 0;
 
         while (i < len) {
+            if (!isOptimizedForRetrieval) {
+                curr.setupIfNeeded(parent, comparator);
+            }
+
             final TrieNode<T> child = curr.getChild(getLookupChar(resource, i));
 
             if (child == null) {
@@ -246,10 +395,15 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
                 break;
             }
 
+            parent = curr;
             curr = child;
             i += childStr.length();
         }
 
+        if (!isOptimizedForRetrieval) {
+            curr.setupIfNeeded(parent, comparator);
+        }
+
         List<T> ret = i == len ? curr.getEvaluators() : curr.getWildcardEvaluators();
 
         RangerPerfTracer.logAlways(perf);
@@ -334,6 +488,91 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         return sb.toString();
     }
 
+    class ResourceTrieBuilderThread extends Thread {
+
+        class WorkItem {
+            final String  resourceName;
+            final boolean isRecursive;
+            final T       evaluator;
+
+            WorkItem(String resourceName, boolean isRecursive, T evaluator) {
+                this.resourceName   = resourceName;
+                this.isRecursive    = isRecursive;
+                this.evaluator      = evaluator;
+            }
+            @Override
+            public String toString() {
+                return
+                "resourceName=" + resourceName +
+                "isRecursive=" + isRecursive +
+                "evaluator=" + (evaluator != null? evaluator.getId() : null);
+            }
+        }
+
+        private final   TrieNode<T>             thisRoot  = new TrieNode<>(null);
+        private final   BlockingQueue<WorkItem> workQueue = new LinkedBlockingQueue<>();
+        private final   boolean                 isOptimizedForRetrieval;
+        private         List<T>                 parentWildcardEvaluators;
+
+        ResourceTrieBuilderThread(boolean isOptimizedForRetrieval) {
+            this.isOptimizedForRetrieval = isOptimizedForRetrieval;
+        }
+
+        void add(String resourceName, boolean isRecursive, T evaluator) throws InterruptedException
{
+            workQueue.put(new WorkItem(resourceName, isRecursive, evaluator));
+        }
+
+        void setParentWildcardEvaluators(List<T> parentWildcardEvaluators) {
+            this.parentWildcardEvaluators = parentWildcardEvaluators;
+        }
+
+        Map<Character, TrieNode<T>> getSubtrees() { return thisRoot.getChildren();
}
+
+        @Override
+        public void run() {
+            if (LOG.isDebugEnabled()) {
+                LOG.debug("Running " + this);
+            }
+
+            while (true) {
+                final WorkItem workItem;
+
+                try {
+                    workItem = workQueue.take();
+                } catch (InterruptedException exception) {
+                    LOG.error("Thread=" + this + " is interrupted", exception);
+
+                    break;
+                }
+
+                if (workItem.evaluator != null) {
+                    insert(thisRoot, workItem.resourceName, workItem.isRecursive, workItem.evaluator);
+                } else {
+                    if (LOG.isDebugEnabled()) {
+                        LOG.debug("Received termination signal. " + workItem);
+                    }
+                    break;
+                }
+            }
+
+            if (!isInterrupted() && isOptimizedForRetrieval) {
+                RangerPerfTracer postSetupPerf = null;
+
+                if (RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
+                    postSetupPerf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie(thread="
+ this.getName() + "-postSetup)");
+                }
+
+                thisRoot.postSetup(parentWildcardEvaluators, comparator);
+
+                RangerPerfTracer.logAlways(postSetupPerf);
+            }
+
+            if (LOG.isDebugEnabled()) {
+                LOG.debug("Exiting " + this);
+            }
+        }
+    }
+
     class TrieData {
         int nodeCount;
         int leafNodeCount;
@@ -346,11 +585,12 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
     }
 
     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;
+        private          String                      str;
+        private final    Map<Character, TrieNode<U>> children = new HashMap<>();
+        private          List<U>                     evaluators;
+        private          List<U>                     wildcardEvaluators;
+        private          boolean                     isSharingParentWildcardEvaluators;
+        private volatile boolean                     isSetup = false;
 
         TrieNode(String str) {
             this.str = str;
@@ -507,6 +747,38 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         }
 
         void postSetup(List<U> parentWildcardEvaluators, Comparator<U> comparator)
{
+
+            setup(parentWildcardEvaluators, comparator);
+
+            if (children != null) {
+                for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet())
{
+                    TrieNode<U> child = entry.getValue();
+
+                    child.postSetup(wildcardEvaluators, comparator);
+                }
+            }
+        }
+
+        void setupIfNeeded(TrieNode<U> parent, Comparator<U> comparator) {
+            if (parent == null) {
+                return;
+            }
+
+            boolean setupNeeded = !isSetup;
+
+            if (setupNeeded) {
+                synchronized (this) {
+                    setupNeeded = !isSetup;
+
+                    if (setupNeeded) {
+                        setup(parent.getWildcardEvaluators(), comparator);
+                        isSetup = true;
+                    }
+                }
+            }
+        }
+
+        void setup(List<U> parentWildcardEvaluators, Comparator<U> comparator)
{
             // finalize wildcard-evaluators list by including parent's wildcard evaluators
             if (parentWildcardEvaluators != null) {
                 if (CollectionUtils.isEmpty(this.wildcardEvaluators)) {
@@ -539,14 +811,6 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
                     evaluators.sort(comparator);
                 }
             }
-
-            if (children != null) {
-                for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet())
{
-                    TrieNode<U> child = entry.getValue();
-
-                    child.postSetup(wildcardEvaluators, comparator);
-                }
-            }
         }
 
         public void toString(String prefix, StringBuilder sb) {
@@ -584,8 +848,11 @@ public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator>
{
         }
 
         public void clear() {
-            children = null;
-            evaluators = null;
+            if (children != null) {
+                children.clear();
+            }
+
+            evaluators         = null;
             wildcardEvaluators = null;
         }
     }

http://git-wip-us.apache.org/repos/asf/ranger/blob/ca7a8d70/agents-common/src/test/java/org/apache/ranger/plugin/policyengine/TestPolicyEngine.java
----------------------------------------------------------------------
diff --git a/agents-common/src/test/java/org/apache/ranger/plugin/policyengine/TestPolicyEngine.java
b/agents-common/src/test/java/org/apache/ranger/plugin/policyengine/TestPolicyEngine.java
index 1d9b865..9d9be6c 100644
--- a/agents-common/src/test/java/org/apache/ranger/plugin/policyengine/TestPolicyEngine.java
+++ b/agents-common/src/test/java/org/apache/ranger/plugin/policyengine/TestPolicyEngine.java
@@ -160,6 +160,10 @@ public class TestPolicyEngine {
 				"                <name>ranger.plugin.tag.attr.additional.date.formats</name>\n"
+
 				"                <value>abcd||xyz||yyyy/MM/dd'T'HH:mm:ss.SSS'Z'</value>\n"
+
 				"        </property>\n" +
+				"        <property>\n" +
+				"                <name>ranger.policyengine.trie.builder.thread.count</name>\n"
+
+				"                <value>3</value>\n" +
+				"        </property>\n" +
                 "</configuration>\n");
 		writer.close();
 
@@ -368,6 +372,7 @@ public class TestPolicyEngine {
 
 		policyEngineOptions.disableTagPolicyEvaluation = false;
 		policyEngineOptions.disableAccessEvaluationWithPolicyACLSummary = false;
+		policyEngineOptions.optimizeTrieForRetrieval = false;
 
 		boolean useForwardedIPAddress = RangerConfiguration.getInstance().getBoolean("ranger.plugin.hive.use.x-forwarded-for.ipaddress",
false);
 		String trustedProxyAddressString = RangerConfiguration.getInstance().get("ranger.plugin.hive.trusted.proxy.ipaddresses");
@@ -383,6 +388,8 @@ public class TestPolicyEngine {
 		policyEngine.setTrustedProxyAddresses(trustedProxyAddresses);
 
 		policyEngineOptions.disableAccessEvaluationWithPolicyACLSummary = true;
+		policyEngineOptions.optimizeTrieForRetrieval = false;
+
 		RangerPolicyEngine policyEngineForResourceAccessInfo = new RangerPolicyEngineImpl(testName,
servicePolicies, policyEngineOptions);
 
 		policyEngineForResourceAccessInfo.setUseForwardedIPAddress(useForwardedIPAddress);


Mime
View raw message