apache /
kudu /
e9ea9840d30cc223e3a8f746169c11353e23ffa8 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
Reviewed-on: http://gerrit.cloudera.org:8080/16752
Reviewed-by: Alexey Serbin <aserbin@cloudera.com>
Tested-by: Andrew Wong <awong@cloudera.com>
5 files changed
