You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by aw...@apache.org on 2021/06/08 17:19:15 UTC

[kudu] branch master updated: KUDU-3291: properly disambiguate between deltas of a row with the same timestamp

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

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


The following commit(s) were added to refs/heads/master by this push:
     new 3a1ce30  KUDU-3291: properly disambiguate between deltas of a row with the same timestamp
3a1ce30 is described below

commit 3a1ce304b3762166ba069767b842a42ea9af1009
Author: Andrew Wong <aw...@cloudera.com>
AuthorDate: Sun Jun 6 21:02:38 2021 -0700

    KUDU-3291: properly disambiguate between deltas of a row with the same timestamp
    
    In performing a diff scan, Kudu iterates in small batches of rows,
    selecting deltas associated with each row that are relevant to the
    scan's timestamp bounds. Once all selected deltas are collected for a
    given row, the oldest and newest deltas are found by a sorting criteria
    meant to sort deltas by their application order:
    
    1. Deltas of lower timestamps are less than deltas of higher timestmaps.
    2. UNDO deltas are less than REDO deltas.
    3. Within each delta store's iterator, a counter of selected deltas is
       used to disambiguate between rows that have the same timestamp. A
       critical assumption here is that this disambiguator is only used for
       deltas of the same delta store. For REDOs, a lower counter implies
       a lower application order -- the opposite is true for UNDOs.
    
    What the above criteria don't account for is the fact that certain
    iterators can iterate over separate delta stores that have deltas of the
    same timestamp and type. If Kudu delta flushes while applying a large
    batch of updates to the same row, the result is that some of the batch's
    updates can land in the newly flushed REDO delta file, while the rest
    land in the new DMS. In iterating over these stores with a
    DeltaIteratorMerger, which combines the deltas of several delta stores,
    this breaks the assumption described above, resulting in the crash
    reported in KUDU-3291.
    
    To remediate this, in iterators that merge multiple delta stores,
    namely, the DeltaIteratorMerger, a single top-level counter is used to
    guide the disambiguators generated by each sub-iterator. Before
    iterating over a new batch of deltas in a given sub-iterator, this
    counter is propagated to the sub-iterators as the new starting point of
    its counter. The result is that the disambiguators generated by the
    DeltaIteratorMerger can be used to define a total ordering of the deltas
    selected.
    
    Change-Id: Iccfc518999d36679f85ed901ba65cf7b4894cd55
    Reviewed-on: http://gerrit.cloudera.org:8080/17547
    Reviewed-by: Alexey Serbin <as...@cloudera.com>
    Tested-by: Andrew Wong <aw...@cloudera.com>
    Reviewed-by: Grant Henke <gr...@apache.org>
---
 src/kudu/tablet/delta_iterator_merger.cc |  5 ++-
 src/kudu/tablet/delta_iterator_merger.h  | 27 +++++++++++---
 src/kudu/tablet/delta_store.cc           |  5 ---
 src/kudu/tablet/delta_store.h            | 43 +++++++++++++++++-----
 src/kudu/tablet/deltafile.h              |  8 +++++
 src/kudu/tablet/deltamemstore.h          |  8 +++++
 src/kudu/tablet/diff_scan-test.cc        | 62 ++++++++++++++++++++++++++++++++
 src/kudu/tablet/tablet-test-base.h       | 33 ++++++++++-------
 8 files changed, 158 insertions(+), 33 deletions(-)

diff --git a/src/kudu/tablet/delta_iterator_merger.cc b/src/kudu/tablet/delta_iterator_merger.cc
index 24ef27b..e3d0af0 100644
--- a/src/kudu/tablet/delta_iterator_merger.cc
+++ b/src/kudu/tablet/delta_iterator_merger.cc
@@ -41,7 +41,8 @@ using strings::Substitute;
 
 DeltaIteratorMerger::DeltaIteratorMerger(
     vector<unique_ptr<DeltaIterator> > iters)
-    : iters_(std::move(iters)) {}
+    : total_deltas_selected_in_prepare_(0),
+      iters_(std::move(iters)) {}
 
 Status DeltaIteratorMerger::Init(ScanSpec* spec) {
   for (const unique_ptr<DeltaIterator> &iter : iters_) {
@@ -59,7 +60,9 @@ Status DeltaIteratorMerger::SeekToOrdinal(rowid_t idx) {
 
 Status DeltaIteratorMerger::PrepareBatch(size_t nrows, int prepare_flags) {
   for (const unique_ptr<DeltaIterator> &iter : iters_) {
+    iter->set_deltas_selected(total_deltas_selected_in_prepare_);
     RETURN_NOT_OK(iter->PrepareBatch(nrows, prepare_flags));
+    total_deltas_selected_in_prepare_ = iter->deltas_selected();
   }
   return Status::OK();
 }
diff --git a/src/kudu/tablet/delta_iterator_merger.h b/src/kudu/tablet/delta_iterator_merger.h
index bedf552..4c87e4d 100644
--- a/src/kudu/tablet/delta_iterator_merger.h
+++ b/src/kudu/tablet/delta_iterator_merger.h
@@ -14,14 +14,17 @@
 // KIND, either express or implied.  See the License for the
 // specific language governing permissions and limitations
 // under the License.
-#ifndef KUDU_TABLET_DELTA_ITERATOR_MERGER_H
-#define KUDU_TABLET_DELTA_ITERATOR_MERGER_H
+#pragma once
 
 #include <cstddef>
+#include <cstdint>
 #include <memory>
+#include <ostream>
 #include <string>
 #include <vector>
 
+#include <glog/logging.h>
+
 #include "kudu/common/rowid.h"
 #include "kudu/tablet/delta_store.h"
 #include "kudu/util/status.h"
@@ -44,7 +47,10 @@ struct RowIteratorOptions;
 class DeltaIteratorMerger : public DeltaIterator {
  public:
   // Create a new DeltaIterator which combines the deltas from
-  // all of the input delta stores.
+  // all of the input delta stores. It is expected that the caller has sorted
+  // the input stores according to the desired application order:
+  // - REDO stores are ordered in increasing timestamp order.
+  // - UNDO stores are ordered in decreasing timestamp order.
   //
   // If only one store is input, this will automatically return an unwrapped
   // iterator for greater efficiency.
@@ -81,13 +87,24 @@ class DeltaIteratorMerger : public DeltaIterator {
 
   std::string ToString() const override;
 
+  int64_t deltas_selected() const override {
+    return total_deltas_selected_in_prepare_;
+  }
+
+  void set_deltas_selected(int64_t /*deltas_selected*/) override {
+    LOG(DFATAL) << "Not implemented";
+  }
+
  private:
   explicit DeltaIteratorMerger(std::vector<std::unique_ptr<DeltaIterator> > iters);
 
+  // The number of deltas selected in PrepareBatch() across all iterators so
+  // far. This is useful to ensure that as we iterate through each
+  // DeltaIterator, we are able to define a total ordering of our deltas.
+  int64_t total_deltas_selected_in_prepare_;
+
   std::vector<std::unique_ptr<DeltaIterator> > iters_;
 };
 
 } // namespace tablet
 } // namespace kudu
-
-#endif // KUDU_TABLET_DELTA_ITERATOR_MERGER_H
diff --git a/src/kudu/tablet/delta_store.cc b/src/kudu/tablet/delta_store.cc
index decb6b2..07fe84e 100644
--- a/src/kudu/tablet/delta_store.cc
+++ b/src/kudu/tablet/delta_store.cc
@@ -269,14 +269,9 @@ Status DeltaPreparer<Traits>::AddDelta(const DeltaKey& key, Slice val, bool* fin
       // The logical ordering of UNDOs is the opposite of their counting order.
       int64_t disambiguator = Traits::kType == REDO ?
                               deltas_selected_ : -deltas_selected_;
-
-      // We use the address of the DeltaPreparer itself as a "delta store" ID.
-      // That's safe because it is globally unique and remains so for the
-      // duration of the scan, which outlives this delta.
       SelectedDeltas::Delta new_delta = { key.timestamp(),
                                           Traits::kType,
                                           disambiguator,
-                                          reinterpret_cast<int64_t>(this),
                                           decoder.get_type() };
 
       selected_.ProcessDelta(key.row_idx() - cur_prepared_idx_, new_delta);
diff --git a/src/kudu/tablet/delta_store.h b/src/kudu/tablet/delta_store.h
index 94c9cab..d3376d8 100644
--- a/src/kudu/tablet/delta_store.h
+++ b/src/kudu/tablet/delta_store.h
@@ -32,6 +32,7 @@
 #include "kudu/common/timestamp.h"
 #include "kudu/gutil/macros.h"
 #include "kudu/gutil/port.h"
+#include "kudu/gutil/strings/substitute.h"
 #include "kudu/tablet/delta_key.h"
 #include "kudu/tablet/rowset.h"
 #include "kudu/util/slice.h"
@@ -105,11 +106,6 @@ class SelectedDeltas {
 
     // Non-key fields.
 
-    // Identifier of the delta store that provided this delta. It must:
-    // 1. Be unique for the owning rowset, but needn't be more unique than that.
-    // 2. Remain unique for the lifetime of this delta scan.
-    int64_t delta_store_id;
-
     // Whether this delta was an UPDATE, DELETE, or REINSERT.
     RowChangeList::ChangeType ctype;
   };
@@ -146,11 +142,11 @@ class SelectedDeltas {
       // The timestamps and delta types match. It should only be possible to get
       // here if we're comparing deltas from within the same store, in which
       // case the disambiguators must not match.
-      CHECK_EQ(a.delta_store_id, b.delta_store_id);
-      if (a.disambiguator != b.disambiguator) {
+      if (PREDICT_TRUE(a.disambiguator != b.disambiguator)) {
         return a.disambiguator < b.disambiguator;
       }
-      LOG(FATAL) << "Could not differentiate between two deltas";
+      LOG(FATAL) << strings::Substitute("Could not differentiate between two deltas "
+          "ts=$0, type=$1, disambiguator=$2", a.ts.ToString(), a.dtype, a.disambiguator);
     }
   };
 
@@ -371,6 +367,23 @@ class DeltaIterator : public PreparedDeltas {
   // Return a string representation suitable for debug printouts.
   virtual std::string ToString() const = 0;
 
+  // Returns the number of deltas that have been selected so far. For iterators
+  // that iterate across multiple DeltaIterators, this value is useful in
+  // defining a total ordering for deltas across all sub-iterators, e.g. by
+  // defining the starting point of each sub-iterator's DeltaPreparer's
+  // disambiguator.
+  //
+  // See SelectedDeltas::Delta for more details.
+  virtual int64_t deltas_selected() const = 0;
+
+  // Sets the number of deltas selected by the preparer so far, used to define
+  // a starting point of a disambiguator between deltas in iterators that
+  // iterate across multiple DeltaIterators. Callers should only call this with
+  // a monotonically increasing value.
+  //
+  // See SelectedDeltas::Delta for more details.
+  virtual void set_deltas_selected(int64_t deltas_selected) = 0;
+
   virtual ~DeltaIterator() {}
 };
 
@@ -454,6 +467,18 @@ class DeltaPreparer : public PreparedDeltas {
   boost::optional<rowid_t> last_added_idx() const { return last_added_idx_; }
   const RowIteratorOptions& opts() const { return opts_; }
 
+  int64_t deltas_selected() const {
+    return deltas_selected_;
+  }
+
+  void set_deltas_selected(int64_t deltas_selected) {
+    // NOTE: it's possible that the iterator's number of 'deltas_selected'
+    // hasn't changed if no deltas were selected since last being called, hence
+    // the DCHECK_GE check instead of DCHECK_GT.
+    DCHECK_GE(deltas_selected, deltas_selected_);
+    deltas_selected_ = deltas_selected;
+  }
+
  private:
   // If 'decoder' is not yet initialized, initializes it in accordance with the
   // preparer's traits.
@@ -528,7 +553,7 @@ class DeltaPreparer : public PreparedDeltas {
   SelectedDeltas selected_;
 
   // The number of deltas selected so far by this DeltaPreparer. Used to build
-  // disambiguators (see SelectedDeltas::Delta). Never reset.
+  // disambiguators (see SelectedDeltas::Delta).
   int64_t deltas_selected_;
 
   // Used for PREPARED_FOR_APPLY mode.
diff --git a/src/kudu/tablet/deltafile.h b/src/kudu/tablet/deltafile.h
index d5b3f97..2a486ef 100644
--- a/src/kudu/tablet/deltafile.h
+++ b/src/kudu/tablet/deltafile.h
@@ -271,6 +271,14 @@ class DeltaFileIterator : public DeltaIterator {
 
   bool MayHaveDeltas() const override;
 
+  int64_t deltas_selected() const override {
+    return preparer_.deltas_selected();
+  }
+
+  void set_deltas_selected(int64_t deltas_selected) override {
+    preparer_.set_deltas_selected(deltas_selected);
+  }
+
  private:
   friend class DeltaFileReader;
 
diff --git a/src/kudu/tablet/deltamemstore.h b/src/kudu/tablet/deltamemstore.h
index 333a307..3ea117c 100644
--- a/src/kudu/tablet/deltamemstore.h
+++ b/src/kudu/tablet/deltamemstore.h
@@ -245,6 +245,14 @@ class DMSIterator : public DeltaIterator {
 
   bool MayHaveDeltas() const override;
 
+  int64_t deltas_selected() const override {
+    return preparer_.deltas_selected();
+  }
+
+  void set_deltas_selected(int64_t deltas_selected) override {
+    preparer_.set_deltas_selected(deltas_selected);
+  }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(DMSIterator);
   friend class DeltaMemStore;
diff --git a/src/kudu/tablet/diff_scan-test.cc b/src/kudu/tablet/diff_scan-test.cc
index ced3cb0..cecc367 100644
--- a/src/kudu/tablet/diff_scan-test.cc
+++ b/src/kudu/tablet/diff_scan-test.cc
@@ -17,8 +17,10 @@
 
 #include <algorithm>
 #include <cstdint>
+#include <cstdlib>
 #include <memory>
 #include <string>
+#include <thread>
 #include <tuple>
 #include <utility>
 #include <vector>
@@ -38,6 +40,9 @@
 #include "kudu/tablet/tablet-test-util.h"
 #include "kudu/tablet/tablet.h"
 #include "kudu/tablet/tablet_metadata.h"
+#include "kudu/util/monotime.h"
+#include "kudu/util/status.h"
+#include "kudu/util/scoped_cleanup.h"
 #include "kudu/util/test_macros.h"
 
 using std::string;
@@ -203,5 +208,62 @@ TEST_F(OrderedDiffScanWithDeletesTest, TestKudu3108) {
   ASSERT_EQ(3, rows.size());
 }
 
+// Regression test for KUDU-3291, where doing a diff scan after a delta flush
+// raced with a batch update to a single row could result in a crash.
+TEST_F(OrderedDiffScanWithDeletesTest, TestDiffScanAfterDeltaFlushRacesWithBatchUpdate) {
+  auto tablet = this->tablet();
+  auto tablet_id = tablet->tablet_id();
+  LocalTabletWriter writer(tablet.get(), &client_schema_);
+  constexpr int64_t kRowKey = 1;
+  ASSERT_OK(InsertTestRow(&writer, kRowKey, 1));
+  MvccSnapshot snap1(*tablet->mvcc_manager());
+
+  // Start off with a DRS that we can add deltas to.
+  ASSERT_OK(tablet->Flush());
+  Status s;
+
+  // Update the same row several times, and concurrently delta flush. Inject a
+  // short, random sleep to encourage different sizes of delta stores. If
+  // implemented incorrectly, the DeltaIteratorMerger could crash, unable to
+  // disambiguate between rows of the delta stores being merged.
+  const auto& sleep_ms = rand() % 3000;
+  std::thread t([&] {
+      SleepFor(MonoDelta::FromMilliseconds(sleep_ms));
+      s = tablet->FlushAllDMSForTests();
+  });
+  auto thread_joiner = MakeScopedCleanup([&] {
+      t.join();
+  });
+  ASSERT_OK(UpdateTestRow(&writer, kRowKey, 0, 10000));
+  t.join();
+  thread_joiner.cancel();
+  ASSERT_OK(s);
+  ASSERT_OK(tablet->mvcc_manager()->WaitForApplyingOpsToApply());
+
+  // Now perform a diff scan, which is an ordered scan with a start and end
+  // timestamp.
+  MvccSnapshot snap2(*tablet->mvcc_manager());
+  RowIteratorOptions opts;
+  opts.snap_to_exclude = snap1;
+  opts.snap_to_include = snap2;
+  opts.order = ORDERED;;
+  SchemaBuilder builder(tablet->metadata()->schema());
+  Schema projection = builder.BuildWithoutIds();
+  opts.projection = &projection;
+
+  unique_ptr<RowwiseIterator> row_iterator;
+  ASSERT_OK(tablet->NewRowIterator(std::move(opts), &row_iterator));
+  ASSERT_TRUE(row_iterator);
+
+  // Regression test for KUDU-3291, iterating through the rows shouldn't result
+  // in a crash.
+  ScanSpec spec;
+  ASSERT_OK(row_iterator->Init(&spec));
+  vector<string> rows;
+  ASSERT_OK(tablet::IterateToStringList(row_iterator.get(), &rows));
+  ASSERT_EQ(1, rows.size());
+  ASSERT_STR_CONTAINS(rows[0], "val=9999");
+}
+
 } // namespace tablet
 } // namespace kudu
diff --git a/src/kudu/tablet/tablet-test-base.h b/src/kudu/tablet/tablet-test-base.h
index 6c3de17..86b5a42 100644
--- a/src/kudu/tablet/tablet-test-base.h
+++ b/src/kudu/tablet/tablet-test-base.h
@@ -14,8 +14,7 @@
 // KIND, either express or implied.  See the License for the
 // specific language governing permissions and limitations
 // under the License.
-#ifndef KUDU_TABLET_TABLET_TEST_BASE_H
-#define KUDU_TABLET_TABLET_TEST_BASE_H
+#pragma once
 
 #include <algorithm>
 #include <limits>
@@ -389,15 +388,25 @@ class TabletTestBase : public KuduTabletTest {
 
   Status UpdateTestRow(LocalTabletWriter* writer,
                        int64_t key_idx,
-                       int32_t new_val) {
-    KuduPartialRow row(&client_schema_);
-    setup_.BuildRowKey(&row, key_idx);
-
-    // select the col to update (the third if there is only one key
-    // or the fourth if there are two col keys).
-    int col_idx = schema_.num_key_columns() == 1 ? 2 : 3;
-    CHECK_OK(row.SetInt32(col_idx, new_val));
-    return writer->Update(row);
+                       int32_t new_val,
+                       int num_updates = 1) {
+    std::vector<KuduPartialRow> rows;
+    for (int i = 0; i < num_updates; i++) {
+      KuduPartialRow row(&client_schema_);
+      setup_.BuildRowKey(&row, key_idx);
+
+      // Select the col to update (the third if there is only one key
+      // or the fourth if there are two col keys).
+      int col_idx = schema_.num_key_columns() == 1 ? 2 : 3;
+      CHECK_OK(row.SetInt32(col_idx, new_val++));
+      rows.emplace_back(std::move(row));
+    }
+    std::vector<LocalTabletWriter::RowOp> ops;
+    ops.reserve(rows.size());
+    for (const auto& row : rows) {
+      ops.emplace_back(RowOperationsPB::UPDATE, &row);
+    }
+    return writer->WriteBatch(ops);
   }
 
   Status UpdateTestRowToNull(LocalTabletWriter* writer,
@@ -542,5 +551,3 @@ class TabletTestBase : public KuduTabletTest {
 
 } // namespace tablet
 } // namespace kudu
-
-#endif