[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows

["Andrew Wong (Code Review)" <ge...@cloudera.org>]

Hello Tidy Bot, Alexey Serbin, Kudu Jenkins, Grant Henke, Hao Hao, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16752

to look at the new patch set (#5).

Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................

tablet: allow interleaving of row liveness between compaction input rows

It was previously true that when merging multiple rowsets, a row's
liveness always moved to the same or newer rowsets. I.e., if a row was
deleted and inserted again, the new insert would either land in the same
rowset from which it was deleted (e.g. if deleting from the MRS and
inserting back into the same MRS), or a rowset whose rows are newer than
the rowset being deleted from (e.g. if deleting from a DRS and inserting
into the MRS).

This invariant was upheld by various checks in compaction code. The
invariant is no longer true when considering transactional inserts.
Take the following example:
- ts=10: insert 'a' to the tablet's MRS
- ts=11: delete 'a' from the tablet's MRS
- begin txn
  - insert 'a' to a transactional MRS
  - ts=12: commit the transactional MRS
- ts=13: delete 'a' from the transactional MRS
- ts=14: insert 'a' to the tablet's MRS

In considering the row history for 'a' in the context of defining the
row's history, we're left with the following row histories in each
rowset, which serve as an input to our history-merging code:

  tablet MRS: UNDO(del@10) <- 'a' -> REDO(del@11) -> REDO(reins@14)
  txn MRS:    UNDO(del@12) <- 'a' -> REDO(del@13)

Previously, our invariant meant that one of these rows entire history
(both UNDOs and REDOs) was entirely ahead of the other. This meant that
merging was a matter of determining which input is older (which must be
a deleted "ghost" row, since there can only be a single live row at a
time), converting the older row and its history into UNDOs, and merging
that UNDO history with the newer row's UNDOs. Given the above sequence,
defining an older row isn't as straightforward, given the overlapping of
the histories. This led to broken invariants in the form of CHECK
failures or incorrect results.

However, a notable obvservation is that there _is_ a discernable history
that does abide by our previously held invariant, if we transfer the
newer REDOs from the tablet's MRS input to the txn's MRS input:

  UNDO(del@10) <- 'a' -> REDO(del@11)
  UNDO(del@12) <- 'a' -> REDO(del@13) -> REDO(reins@14)

This transferral is safe because we still expect that only a single
instance of a row can be "live" at a time. I.e., if there is such
overlap, it is caused by the deletion of a row from the older rowset,
and in transferring the history, there is no risk of ending up with two
histories for the same row that both end with a live row.

This patch implements this transferral of history onto the newer input,
and adds some fuzz test cases that helped snuff out the aforementioned
CHECK failures and incorrect results.

It also enables transactional ops in fuzz-itest, which helped find this
issue. Without this patch, fuzz-itest with transactional support fails
2/10 times in DEBUG mode. With it, it has passed 1000/1000 times.

Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/compaction-test.cc
M src/kudu/tablet/compaction.cc
M src/kudu/tablet/compaction.h
M src/kudu/tablet/mutation.h
5 files changed, 605 insertions(+), 81 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/5
-- 
To view, visit http://gerrit.cloudera.org:8080/16752
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 5
Gerrit-Owner: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Grant Henke <gr...@apache.org>
Gerrit-Reviewer: Hao Hao <ha...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)