You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@kudu.apache.org by "Andrew Wong (Code Review)" <ge...@cloudera.org> on 2020/11/20 03:11:50 UTC
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Andrew Wong has uploaded this change for review. ( http://gerrit.cloudera.org:8080/16752
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.
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, 419 insertions(+), 59 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/1
--
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: newchange
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 1
Gerrit-Owner: Andrew Wong <aw...@cloudera.com>
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 6:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/integration-tests/fuzz-itest.cc
File src/kudu/integration-tests/fuzz-itest.cc:
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/integration-tests/fuzz-itest.cc@2044
PS6, Line 2044: TEST_INSERT_IGNORE
nit: is it crucial to have INSERT_INGORE instead of INSERT here? Do you mind adding a comment in this regard?
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/tablet/compaction.cc@366
PS6, Line 366: AdvanceToLastInList(&right_last);
Here and below: is AdvanceToLastInList really supposed to be under the #ifndef clause? Could you add a comment explaining the reasoning for adding this only for builds with builds where NDEBUG is not defined?
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 6
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)
Gerrit-Comment-Date: Tue, 23 Feb 2021 05:02:00 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 10:
Unrelated test failure:
TokenBasedConnectionITest.ReacquireAuthnToken
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 10
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)
Gerrit-Comment-Date: Sat, 27 Feb 2021 00:14:22 +0000
Gerrit-HasComments: No
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 10: Code-Review+2
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 10
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)
Gerrit-Comment-Date: Fri, 26 Feb 2021 23:08:32 +0000
Gerrit-HasComments: No
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 9: Code-Review+1
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 9
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)
Gerrit-Comment-Date: Fri, 26 Feb 2021 16:56:41 +0000
Gerrit-HasComments: No
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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 (#3).
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, 491 insertions(+), 70 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/3
--
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: 3
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Hao Hao (Code Review)" <ge...@cloudera.org>.
Hao Hao has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 8: Code-Review+2
(1 comment)
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@453
PS2, Line 453: / If the last chang
> We discussed this on Slack, that I don't think it's a valid sequence in ter
Ack
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 8
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)
Gerrit-Comment-Date: Thu, 25 Feb 2021 19:00:49 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 10: Verified+1
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 10
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)
Gerrit-Comment-Date: Sat, 27 Feb 2021 00:14:26 +0000
Gerrit-HasComments: No
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/16752
to look at the new patch set (#2).
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.
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, 418 insertions(+), 59 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/2
--
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: 2
Gerrit-Owner: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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 (#9).
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, 612 insertions(+), 83 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/9
--
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: 9
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 8: Code-Review+2
(1 comment)
http://gerrit.cloudera.org:8080/#/c/16752/8/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/8/src/kudu/tablet/compaction.cc@369
PS8, Line 369: if (PREDICT_TRUE(FLAGS_dcheck_on_kudu_2233_invariants)) {
nit: if this validation is empty in NDEBUG case, maybe put the whole 'if()' clause under '#ifndef NDEBUG' then?
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 8
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)
Gerrit-Comment-Date: Wed, 24 Feb 2021 21:48:02 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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 (#7).
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, 612 insertions(+), 83 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/7
--
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: 7
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 3:
(3 comments)
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@318
PS2, Line 318: //
: // UNDO(del@5) <- BASE(a) -> REDO(del@10) -> REDO(reins@25) // main MR
> Wondering what will happen if
Addressed in the other comment.
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@390
PS2, Line 390: const Mutation* newer_row_last = left_newer ? left_last: right_last;
> Just for my own understanding, wondering when this happen if all the ops ar
They would all be assigned different timestamps, and we'd take the branch at L363.
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@453
PS2, Line 453: CopyMutations(Mutat
> It seems for all REDOs in the 'older' that are greater than the REDO head o
We discussed this on Slack, that I don't think it's a valid sequence in terms of how tablets generate mutations. For this to happen, the txn MRS would have to become "active" again at ts=40 and accept a write, but the transaction was committed already at ts=15 and thus stopped inserting new inserts. The delete at ts=20 was part of a different op, but landed in the transaction MRS because mutations attach themselves to where the latest live row is.
I've added a comment explaining. Let me know if I can clarify more.
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 3
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)
Gerrit-Comment-Date: Fri, 11 Dec 2020 07:15:36 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Hao Hao (Code Review)" <ge...@cloudera.org>.
Hao Hao has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 2:
(3 comments)
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@318
PS2, Line 318: // UNDO(del@5) <- BASE(a) -> REDO(del@10) -> REDO(reins@25) // main MRS
: // UNDO(del@15) <- BASE(a) -> REDO(del@20) // txn MRS
Wondering what will happen if
UNDO(del@5) <- BASE(a) -> REDO(del@10) -> REDO(reins@25) ->REDO(del@35) // main MRS
UNDO(del@15) <- BASE(a) -> REDO(del@20) -> REDO(reins@40) ->REDO(del@45) // txn MRS
it will be transferred to the following?
UNDO(del@15) <- BASE(a) -> REDO(del@20) -> REDO(reins@25) ->REDO(del@35)-> REDO(reins@40) ->REDO(del@45) // txn MRS
UNDO(del@5) <- BASE(a) -> REDO(del@10) // main MRS
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@390
PS2, Line 390: For instance this is a valid history with non-disjoint REDO histories
Just for my own understanding, wondering when this happen if all the ops are not in the same txn?
http://gerrit.cloudera.org:8080/#/c/16752/2/src/kudu/tablet/compaction.cc@453
PS2, Line 453: TransferRedoHistory
It seems for all REDOs in the 'older' that are greater than the REDO head of 'newer' will be transferred to the end of the 'newer' REDO. What if there is a overlapped between the transferred REDOs and the 'newer' REDO? e.g.
UNDO(del@5) <- BASE(a) -> REDO(del@10) -> REDO(reins@25) ->REDO(del@35) // main MRS
UNDO(del@15) <- BASE(a) -> REDO(del@20) -> REDO(reins@40) ->REDO(del@45) // txn MRS
will be transferred to the following?
UNDO(del@15) <- BASE(a) -> REDO(del@20) -> REDO(reins@40) ->REDO(del@45) -> REDO(reins@25) ->REDO(del@35) // txn MRS
Do you think it is a valid example?Will it matter if the 'newer' REDO is out of sequence?
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 2
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)
Gerrit-Comment-Date: Tue, 08 Dec 2020 01:00:05 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has removed a vote on this change.
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Removed Verified-1 by Kudu Jenkins (120)
--
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: deleteVote
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 10
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/16752 )
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
Reviewed-on: http://gerrit.cloudera.org:8080/16752
Reviewed-by: Alexey Serbin <as...@cloudera.com>
Tested-by: Andrew Wong <aw...@cloudera.com>
---
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, 608 insertions(+), 81 deletions(-)
Approvals:
Alexey Serbin: Looks good to me, approved
Andrew Wong: Verified
--
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: merged
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 11
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 4:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/16752/4/src/kudu/tablet/compaction-test.cc
File src/kudu/tablet/compaction-test.cc:
http://gerrit.cloudera.org:8080/#/c/16752/4/src/kudu/tablet/compaction-test.cc@1109
PS4, Line 1109: TestRowHistoryJumpsBetweenRowsets2
Isn't this some sort of "sub-set" of TestRowHistoryJumpsBetweenRowsets? I'm not sure I understand why it's important to have this one as well if TestRowHistoryJumpsBetweenRowsets exists?
Could you add more colors to describe why it's important to have both?
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 4
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)
Gerrit-Comment-Date: Sat, 12 Dec 2020 05:38:15 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 4: Verified+1
Test failure is unrelated.
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 4
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)
Gerrit-Comment-Date: Sat, 12 Dec 2020 01:30:51 +0000
Gerrit-HasComments: No
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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 (#6).
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, 606 insertions(+), 81 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/6
--
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: 6
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "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 (#10).
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, 608 insertions(+), 81 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/16752/10
--
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: 10
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)
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 8:
(3 comments)
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/integration-tests/fuzz-itest.cc
File src/kudu/integration-tests/fuzz-itest.cc:
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/integration-tests/fuzz-itest.cc@2044
PS6, Line 2044: F(FuzzTest, TestDo
> nit: is it crucial to have INSERT_INGORE instead of INSERT here? Do you mi
Most of these cases were found by random fuzzing, and I just happened to hit a crash with INSERT_IGNORE. INSERT works too, so I'll update it to be less conspicuous.
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/6/src/kudu/tablet/compaction.cc@366
PS6, Line 366: nst Mutation* right_last = right.
> Here and below: is AdvanceToLastInList really supposed to be under the #ifn
Yeah, it's only necessary for the DCHECK. If we're not running the validation, there's no point in iterating.
http://gerrit.cloudera.org:8080/#/c/16752/8/src/kudu/tablet/compaction.cc
File src/kudu/tablet/compaction.cc:
http://gerrit.cloudera.org:8080/#/c/16752/8/src/kudu/tablet/compaction.cc@369
PS8, Line 369: if (PREDICT_TRUE(FLAGS_dcheck_on_kudu_2233_invariants)) {
> nit: if this validation is empty in NDEBUG case, maybe put the whole 'if()'
Good point. Done
--
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: comment
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 8
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)
Gerrit-Comment-Date: Fri, 26 Feb 2021 00:59:48 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/16752 )
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Patch Set 5:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/16752/4/src/kudu/tablet/compaction-test.cc
File src/kudu/tablet/compaction-test.cc:
http://gerrit.cloudera.org:8080/#/c/16752/4/src/kudu/tablet/compaction-test.cc@1109
PS4, Line 1109: mrs_a = CreateInvisibleMRS();
> Isn't this some sort of "sub-set" of TestRowHistoryJumpsBetweenRowsets? I'
Indeed, I meant to expand on this case a bit, but instead I generalized this into a randomized test case.
--
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: comment
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)
Gerrit-Comment-Date: Thu, 18 Feb 2021 21:25:37 +0000
Gerrit-HasComments: Yes
[kudu-CR] tablet: allow interleaving of row liveness between compaction input rows
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has removed a vote on this change.
Change subject: tablet: allow interleaving of row liveness between compaction input rows
......................................................................
Removed Verified-1 by Kudu Jenkins (120)
--
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: deleteVote
Gerrit-Change-Id: I042a7d70d32edf9d2a3a077790821893f162880a
Gerrit-Change-Number: 16752
Gerrit-PatchSet: 4
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)