kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [2/4] kudu git commit: compaction_policy: don't run a compaction if it provides very little improvement
Date Wed, 01 Nov 2017 23:42:27 GMT
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 <todd@apache.org>
Tested-by: Todd Lipcon <todd@apache.org>


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 <todd@apache.org>
Authored: Wed Nov 1 11:45:20 2017 -0700
Committer: Todd Lipcon <todd@apache.org>
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<double> 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();
   }
 


Mime
View raw message