Return-Path: X-Original-To: archive-asf-public-internal@cust-asf2.ponee.io Delivered-To: archive-asf-public-internal@cust-asf2.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by cust-asf2.ponee.io (Postfix) with ESMTP id 2EED6200D3E for ; Thu, 2 Nov 2017 00:42:29 +0100 (CET) Received: by cust-asf.ponee.io (Postfix) id 2D73B160BFC; Wed, 1 Nov 2017 23:42:29 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id 5D5E9160BEA for ; Thu, 2 Nov 2017 00:42:28 +0100 (CET) Received: (qmail 87609 invoked by uid 500); 1 Nov 2017 23:42:27 -0000 Mailing-List: contact commits-help@kudu.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@kudu.apache.org Delivered-To: mailing list commits@kudu.apache.org Received: (qmail 87600 invoked by uid 99); 1 Nov 2017 23:42:27 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 01 Nov 2017 23:42:27 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 7CAE1DFEEF; Wed, 1 Nov 2017 23:42:26 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: todd@apache.org To: commits@kudu.apache.org Date: Wed, 01 Nov 2017 23:42:27 -0000 Message-Id: In-Reply-To: <2fba1b90903b42139c9326197d071dd6@git.apache.org> References: <2fba1b90903b42139c9326197d071dd6@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [2/4] kudu git commit: compaction_policy: don't run a compaction if it provides very little improvement archived-at: Wed, 01 Nov 2017 23:42:29 -0000 compaction_policy: don't run a compaction if it provides very little improvement In the case that a compaction only results in a tiny amount of improvement (eg reducing height in only 1% of the key space or less) then we should not bother to run it. This patch implements this short circuit behavior and also ensures that we short-circuit the compaction policy calculation early as soon as we can see that we aren't going to find a worthwhile compaction. This provided a huge speedup on evaluating the compaction policies for cases where the rowsets don't (or minimally) overlap. Original: Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs): 6475.676701 task-clock (msec) # 1.000 CPUs utilized ( +- 1.35% ) 10 context-switches # 0.001 K/sec ( +- 29.76% ) 0 cpu-migrations # 0.000 K/sec ( +-100.00% ) 2,505 page-faults # 0.387 K/sec ( +- 4.24% ) 24,174,771,160 cycles # 3.733 GHz ( +- 0.50% ) 79,871,269,334 instructions # 3.30 insn per cycle ( +- 0.00% ) 14,113,123,041 branches # 2179.405 M/sec ( +- 0.00% ) 58,160,529 branch-misses # 0.41% of all branches ( +- 0.02% ) 6.476139848 seconds time elapsed ( +- 1.35% ) With patch: Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs): 426.861117 task-clock (msec) # 0.999 CPUs utilized ( +- 0.87% ) 2 context-switches # 0.004 K/sec ( +- 23.13% ) 0 cpu-migrations # 0.000 K/sec 2,476 page-faults # 0.006 M/sec ( +- 4.38% ) 1,597,139,052 cycles # 3.742 GHz ( +- 0.67% ) 4,013,990,056 instructions # 2.51 insn per cycle ( +- 0.01% ) 628,035,462 branches # 1471.288 M/sec ( +- 0.01% ) 2,408,063 branch-misses # 0.38% of all branches ( +- 0.13% ) 0.427287921 seconds time elapsed ( +- 0.86% ) Change-Id: I2522f960ee5413b54c9936721eef5ef200586bc9 Reviewed-on: http://gerrit.cloudera.org:8080/8444 Reviewed-by: Todd Lipcon Tested-by: Todd Lipcon Project: http://git-wip-us.apache.org/repos/asf/kudu/repo Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/db3894f6 Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/db3894f6 Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/db3894f6 Branch: refs/heads/master Commit: db3894f6fa6a96da1118341d2ee40c71f863e570 Parents: 55dcdd0 Author: Todd Lipcon Authored: Wed Nov 1 11:45:20 2017 -0700 Committer: Todd Lipcon Committed: Wed Nov 1 23:17:20 2017 +0000 ---------------------------------------------------------------------- src/kudu/tablet/compaction_policy.cc | 25 ++++++++++++++++++++++--- 1 file changed, 22 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kudu/blob/db3894f6/src/kudu/tablet/compaction_policy.cc ---------------------------------------------------------------------- diff --git a/src/kudu/tablet/compaction_policy.cc b/src/kudu/tablet/compaction_policy.cc index 1e7dbf4..d2695b1 100644 --- a/src/kudu/tablet/compaction_policy.cc +++ b/src/kudu/tablet/compaction_policy.cc @@ -50,6 +50,11 @@ DEFINE_double(compaction_approximation_ratio, 1.05f, "if it is known to be within 5% of the optimal solution."); TAG_FLAG(compaction_approximation_ratio, experimental); +DEFINE_double(compaction_minimum_improvement, 0.01f, + "The minimum quality for a compaction to run. If a compaction does not " + "improve the average height of DiskRowSets by at least this amount, the " + "compaction will be considered ineligible."); + namespace kudu { namespace tablet { @@ -301,7 +306,7 @@ void BudgetedCompactionPolicy::RunExact( // Here we also build in the approximation ratio as slop: the upper bound doesn't need // to just be better than the current solution, but needs to be better by at least // the approximation ratio before we bother looking for it. - if (upper_bound < best_solution->value * FLAGS_compaction_approximation_ratio) { + if (upper_bound <= best_solution->value * FLAGS_compaction_approximation_ratio) { continue; } @@ -414,6 +419,17 @@ Status BudgetedCompactionPolicy::PickRowSets(const RowSetTree &tree, vector best_upper_bounds; RunApproximation(asc_min_key, asc_max_key, &best_upper_bounds, &best_solution); + // If the best solution found above is less than some tiny threshold, we don't + // need to bother searching for the exact solution, since it could be at most twice + // the approximate solution. + if (best_solution.value * 2 <= FLAGS_compaction_minimum_improvement || + *std::max_element(best_upper_bounds.begin(), best_upper_bounds.end()) <= + FLAGS_compaction_minimum_improvement) { + VLOG(1) << "Approximation algorithm short-circuited exact compaction calculation"; + *quality = 0; + return Status::OK(); + } + // Pass 2 (precise) // ------------------------------------------------------------ // Now that we've found an approximate solution and upper bounds, do another pass. @@ -437,8 +453,11 @@ Status BudgetedCompactionPolicy::PickRowSets(const RowSetTree &tree, *quality = best_solution.value; - if (best_solution.value <= 0) { - VLOG(1) << "Best compaction available makes things worse. Not compacting."; + if (best_solution.value <= FLAGS_compaction_minimum_improvement) { + VLOG(1) << "Best compaction available (" << best_solution.value << " less than " + << "minimum quality " << FLAGS_compaction_minimum_improvement + << ": not compacting."; + *quality = 0; return Status::OK(); }