From dev-return-60874-archive-asf-public=cust-asf.ponee.io@storm.apache.org Sun Oct 13 21:03:03 2019 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [207.244.88.153]) by mx-eu-01.ponee.io (Postfix) with SMTP id 839C818065D for ; Sun, 13 Oct 2019 23:03:03 +0200 (CEST) Received: (qmail 70417 invoked by uid 500); 13 Oct 2019 21:02:57 -0000 Mailing-List: contact dev-help@storm.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@storm.apache.org Delivered-To: mailing list dev@storm.apache.org Received: (qmail 70360 invoked by uid 99); 13 Oct 2019 21:02:57 -0000 Received: from ec2-52-202-80-70.compute-1.amazonaws.com (HELO gitbox.apache.org) (52.202.80.70) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 13 Oct 2019 21:02:57 +0000 From: GitBox To: dev@storm.apache.org Subject: [GitHub] [storm] Ethanlm commented on a change in pull request #3136: [STORM-3519] Change ConstraintSolverStrategy::backtrackSearch to iteration Message-ID: <157100057697.4296.10760798002664614291.gitbox@gitbox.apache.org> Date: Sun, 13 Oct 2019 21:02:56 -0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Ethanlm commented on a change in pull request #3136: [STORM-3519] Change ConstraintSolverStrategy::backtrackSearch to iteration URL: https://github.com/apache/storm/pull/3136#discussion_r334296619 ########## File path: storm-server/src/main/java/org/apache/storm/scheduler/resource/strategies/scheduling/ConstraintSolverStrategy.java ########## @@ -320,51 +320,101 @@ private boolean checkSchedulingFeasibility(int maxStateSearch) { return GenericResourceAwareStrategy.sortObjectResourcesImpl(allResources, exec, topologyDetails, existingScheduleFunc); } - // Backtracking algorithm does not take into account the ordering of executors in worker to reduce traversal space + /** + * Try to schedule till successful or till limits (backtrack count or time) have been exceeded. + * + * @param state terminal state of the executor assignment. + * @return SolverResult with success attribute set to true or false indicting whether ALL executors were assigned. + */ @VisibleForTesting protected SolverResult backtrackSearch(SearcherState state) { - state.incStatesSearched(); - if (state.areSearchLimitsExceeded()) { - LOG.warn("Limits Exceeded"); - return new SolverResult(state, false); - } + long startTimeMilli = System.currentTimeMillis(); + int maxExecCnt = state.getExecSize(); + + // following three are state information at each "execIndex" level + int[] progressIdxForExec = new int[maxExecCnt]; + RasNode[] nodeForExec = new RasNode[maxExecCnt]; + WorkerSlot[] workerSlotForExec = new WorkerSlot[maxExecCnt]; - if (Thread.currentThread().isInterrupted()) { - return new SolverResult(state, false); + for (int i = 0; i < maxExecCnt ; i++) { + progressIdxForExec[i] = -1; } + LOG.info("backtrackSearch: will assign {} executors", maxExecCnt); + + OUTERMOST_LOOP: + for (int loopCnt = 0 ; true ; loopCnt++) { + LOG.debug("backtrackSearch: loopCnt = {}, state.execIndex = {}", loopCnt, state.execIndex); + if (state.areSearchLimitsExceeded()) { + LOG.warn("backtrackSearch: Search limits exceeded"); + return new SolverResult(state, false); + } - ExecutorDetails exec = state.currentExec(); - Iterable sortedNodes = sortAllNodes(state.td, exec, favoredNodeIds, unFavoredNodeIds); + if (Thread.currentThread().isInterrupted()) { + return new SolverResult(state, false); + } - for (String nodeId: sortedNodes) { - RasNode node = nodes.get(nodeId); - for (WorkerSlot workerSlot : node.getSlotsAvailableToScheduleOn()) { - if (isExecAssignmentToWorkerValid(workerSlot, state)) { - state.tryToSchedule(execToComp, node, workerSlot); + int execIndex = state.execIndex; - if (state.areAllExecsScheduled()) { - //Everything is scheduled correctly, so no need to search any more. - return new SolverResult(state, true); - } + ExecutorDetails exec = state.currentExec(); + Iterable sortedNodesIter = sortAllNodes(state.td, exec, favoredNodeIds, unFavoredNodeIds); - SolverResult results = backtrackSearch(state.nextExecutor()); - if (results.success) { - //We found a good result we are done. - return results; + int progressIdx = -1; + boolean assigned = false; + for (String nodeId : sortedNodesIter) { + RasNode node = nodes.get(nodeId); + for (WorkerSlot workerSlot : node.getSlotsAvailableToScheduleOn()) { + progressIdx++; + if (progressIdx <= progressIdxForExec[execIndex]) { + continue; } + progressIdxForExec[execIndex]++; + LOG.debug("backtrackSearch: loopCnt = {}, state.execIndex = {}, node/slot-ordinal = {}, nodeId = {}", + loopCnt, execIndex, progressIdx, nodeId); - if (state.areSearchLimitsExceeded()) { - //No need to search more it is not going to help. - return new SolverResult(state, false); + if (!isExecAssignmentToWorkerValid(workerSlot, state)) { + continue; } - //backtracking (If we ever get here there really isn't a lot of hope that we will find a scheduling) - state.backtrack(execToComp, node, workerSlot); + try { + state.incStatesSearched(); + state.tryToSchedule(execToComp, node, workerSlot); + if (state.areAllExecsScheduled()) { + //Everything is scheduled correctly, so no need to search any more. + LOG.info("backtrackSearch: AllExecsScheduled at loopCnt = {} in {} milliseconds, elapsedtime in state={}", + loopCnt, System.currentTimeMillis() - startTimeMilli, Time.currentTimeMillis() - state.startTimeMillis); + return new SolverResult(state, true); + } + state = state.nextExecutor(); + nodeForExec[execIndex] = node; + workerSlotForExec[execIndex] = workerSlot; + assigned = true; + LOG.debug("backtrackSearch: Assigned execId={} to node={}, node/slot-ordinal={} at loopCnt={}", + execIndex, nodeId, progressIdx, loopCnt); + continue OUTERMOST_LOOP; + } catch (Exception ex) { + LOG.error("backtrackSearch: Failed to schedule execId {} to node/slot-ordinal = {} at loopCnt = {}, nodeId = {}", + ex, execIndex, progressIdx, loopCnt, nodeId); + continue; + } + } + } + if (!assigned) { Review comment: This seems redundant. `!assigned` will always be true if it ever reaches here ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: users@infra.apache.org With regards, Apache Git Services