[kudu] 02/02: KUDU-2704: Rowsets that are much bigger than the target size discourage compactions

[aw...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

awong pushed a commit to branch branch-1.9.x
in repository https://gitbox.apache.org/repos/asf/kudu.git

commit 76e8af74e151c018de7e3d6aa34fadd49bf41601
Author: Will Berkeley <wd...@gmail.org>
AuthorDate: Wed Feb 20 12:27:17 2019 -0800

    KUDU-2704: Rowsets that are much bigger than the target size discourage compactions
    
    If rowsets are flushed that are much bigger than the target rowset size,
    then they may get a negative contribution to their score from the
    size-based portion of their valuation in the compaction knapsack
    problem. This is a problem for two reasons:
    
    1. It can cause fruitful height-based compactions not to run even though
       the compaction is under budget.
    2. In an extreme case, the value of the rowset can become negative,
       which breaks an invariant of the knapsack problem that item weights
       be nonnegative.
    
    This fixes the issue by flooring the size-based contribution at 0. A
    regression test is included that is based on the real-world example that
    I saw. I also tested that the real-life case I observed was fixed by
    this patch.
    
    Why do rowsets get flushed "too big"? It could be because the target
    size was changed after they were flushed, but I also see almost all
    rowsets flushed with a size that is much too big when the number of
    columns becomes large. For example, on the cluster where I discovered
    this problem, a table with 279 columns was flushing 85MB rowsets even
    though the target size is 32MB. That issue ought to be investigated, but
    in the meantime this is a workable fix. It has existed for a long time-
    the KUDU-2701 fix just made it apparent because it increased how much
    the rowsets exceed the target size in many cases.
    
    Change-Id: I1771cd3dbbb17c87160a4bc38b48b3fbc7307676
    Reviewed-on: http://gerrit.cloudera.org:8080/12538
    Reviewed-by: Andrew Wong <aw...@cloudera.com>
    Tested-by: Kudu Jenkins
    (cherry picked from commit fad69bb5104ebb8cf335f345475ffb02cec71329)
    Reviewed-on: http://gerrit.cloudera.org:8080/12539
---
 src/kudu/tablet/compaction_policy-test.cc | 32 +++++++++++++++++++++++++++++++
 src/kudu/tablet/rowset_info.cc            |  6 +++++-
 2 files changed, 37 insertions(+), 1 deletion(-)

diff --git a/src/kudu/tablet/compaction_policy-test.cc b/src/kudu/tablet/compaction_policy-test.cc
index ce99b5b..34824b0 100644
--- a/src/kudu/tablet/compaction_policy-test.cc
+++ b/src/kudu/tablet/compaction_policy-test.cc
@@ -598,5 +598,37 @@ TEST_F(KeySpaceCdfTest, TestComputingAverageRowSetHeight) {
             { "B", "D" }, { "F", "I" },
             { "A", "C" }, { "D", "D" }, { "F", "G" }, { "I", "I" } }));
 }
+
+// A regression test for KUDU-2704. If rowsets are larger than the target size
+// but there is fruitful height-based compaction that is within budget, it
+// might not occur because the size-based portion of the rowset's value is
+// negative.
+TEST_F(TestCompactionPolicy, TestKUDU2704) {
+  CompactionSelection picked;
+  double quality = 0.0;
+
+  constexpr auto kNumRowSets = 100;
+  const auto big_rowset_size = FLAGS_budgeted_compaction_target_rowset_size * 2;
+  const auto budget_mb = 2 * big_rowset_size / 1024 / 1024;
+  RowSetVector rowsets;
+  for (auto i = 0; i < kNumRowSets; i++) {
+    rowsets.emplace_back(new MockDiskRowSet(
+        StringPrintf("%010d", i * 2),
+        StringPrintf("%010d", i * 2 + 1),
+        big_rowset_size));
+  }
+  // Add one rowset overlapping the first rowset, so that it decreases average
+  // rowset height to compact this one and the first one, but the average rowset
+  // height doesn't decrease by much.
+  rowsets.emplace_back(new MockDiskRowSet("0000000000",
+                                          "0000000001",
+                                          big_rowset_size));
+  NO_FATALS(RunTestCase(rowsets, budget_mb, &picked, &quality));
+
+  // We should still pick two rowsets because we do not allow the above-target
+  // size of the rowsets to hurt compaction based on average height reduction.
+  ASSERT_EQ(2, picked.size());
+  ASSERT_GT(quality, 0.0);
+}
 } // namespace tablet
 } // namespace kudu
diff --git a/src/kudu/tablet/rowset_info.cc b/src/kudu/tablet/rowset_info.cc
index 5089a1d..187a96f 100644
--- a/src/kudu/tablet/rowset_info.cc
+++ b/src/kudu/tablet/rowset_info.cc
@@ -232,8 +232,12 @@ double ComputeRowsetValue(double width, uint64_t size_bytes) {
 
   // This is an approximation to the expected reduction in rowset count per
   // input rowset. See the compaction policy design doc for more details.
+  // The score is floored at 0 to prevent rowsets that are bigger than the
+  // target size from adding a negative score that discourages height-based
+  // compactions. In extreme circumstances, the overall value could be negative,
+  // which violates a knapsack problem invariant.
   const auto size_score =
-      1 - static_cast<double>(size_bytes) / target_size_bytes;
+      std::max(0.0, 1 - static_cast<double>(size_bytes) / target_size_bytes);
   return width + gamma * size_score;
 }