Hello Will Berkeley, Mike Percy, Grant Henke,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/13536
to review the following change.
Change subject: KUDU-2809 (4/6): skip unobservable rows when iterating a DRS
......................................................................
KUDU-2809 (4/6): skip unobservable rows when iterating a DRS
The counterpart to the MRS patch, this one makes an equivalent change to the
DRS diff scanning logic. It's far more complicated than the MRS version, for
several reasons:
1. A row's history is fragmented across multiple delta stores.
2. UNDOs' view of time is inverted, complicating attempts at tracing a row's
liveness across stores.
To implement this, we need to reconsider how the DeltaApplier initializes
its selection vector. The overall structure remains the same:
1. The DeltaApplier sets up data structure to capture selectivity info.
2. It invokes a method on each store to add that store's selectivity info
to the structure.
3. Finally, converts the structure into the selection vector.
Before this patch, it was sufficient for the data structure to be the
selection vector itself. But now the selection vector is insufficient.
Instead we use a new data structure which tracks, for each row, the row's
oldest and newest selected deltas. Armed with this information, we can omit
unobservable rows at conversion time: if a row was dead before the oldest
delta and after the newest delta, its lifetime exists entirely within the
diff scan and it should be omitted from the results.
Much of the complexity here lies with the need to totally order all deltas,
regardless of whether they're UNDOs or REDOs, even if they share the same
timestamps (fuzz-itest is a super effective way of testing this). The
ordering starts with timestamps, but then orders deltas in some potentially
non-obvious ways based on Kudu invariants:
1. Timestamps (obviously)
2. UNDOs, then REDOs. Within a rowset all UNDOs come before REDOs.
3. The order in which the deltas were observed in the store. This is
equivalent to the order in which they are applied.
Change-Id: I2b616c4e8b99dbc7063b940bcb35352f87ab0226
---
M src/kudu/common/row_changelist.cc
M src/kudu/common/row_changelist.h
M src/kudu/common/rowblock.h
M src/kudu/tablet/compaction.cc
M src/kudu/tablet/delta_applier.cc
M src/kudu/tablet/delta_iterator_merger.cc
M src/kudu/tablet/delta_iterator_merger.h
M src/kudu/tablet/delta_store.cc
M src/kudu/tablet/delta_store.h
M src/kudu/tablet/deltafile.cc
M src/kudu/tablet/deltafile.h
M src/kudu/tablet/deltamemstore.cc
M src/kudu/tablet/deltamemstore.h
M src/kudu/tablet/tablet-test-util.h
M src/kudu/tablet/tablet-test.cc
15 files changed, 402 insertions(+), 60 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/36/13536/1
--
To view, visit http://gerrit.cloudera.org:8080/13536
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I2b616c4e8b99dbc7063b940bcb35352f87ab0226
Gerrit-Change-Number: 13536
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo <[email protected]>
Gerrit-Reviewer: Grant Henke <[email protected]>
Gerrit-Reviewer: Mike Percy <[email protected]>
Gerrit-Reviewer: Will Berkeley <[email protected]>
