[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. To be extra safe, I also looped fuzz-itest 1000 times in slow mode. All of the runs passed. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Reviewed-on: http://gerrit.cloudera.org:8080/11395 Tested-by: Adar Dembo Reviewed-by: Adar Dembo --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 525 insertions(+), 403 deletions(-) Approvals: Adar Dembo: Looks good to me, approved; Verified -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: merged Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Nu
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 12: Code-Review+2 Carrying forward David's +2 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 12 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Wed, 31 Oct 2018 23:20:45 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 12: Verified+1 Overriding Jenkins, unrelated TSAN test failure. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 12 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Tue, 30 Oct 2018 04:59:52 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has removed Kudu Jenkins from this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Removed reviewer Kudu Jenkins with the following votes: * Verified-1 by Kudu Jenkins (120) -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: deleteReviewer Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 12 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
David Ribeiro Alves has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 10: Code-Review+2 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 10 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Tue, 16 Oct 2018 16:30:13 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Tidy Bot, Mike Percy, David Ribeiro Alves, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#10). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. To be extra safe, I also looped fuzz-itest 1000 times in slow mode. All of the runs passed. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 525 insertions(+), 403 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/10 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 10: > +2ing but might make sense to add to the commit message that you ran fuzz on > slow mode and all passed. feel free to keep the +2 on that change (or on the > rebase) unless there's something new you want me to look at. I had to rebase anyway due to other changes on master. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 10 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Tue, 16 Oct 2018 03:04:20 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
David Ribeiro Alves has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 9: Code-Review+2 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 9 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Tue, 09 Oct 2018 16:31:24 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
David Ribeiro Alves has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 9: +2ing but might make sense to add to the commit message that you ran fuzz on slow mode and all passed. feel free to keep the +2 on that change (or on the rebase) unless there's something new you want me to look at. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 9 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Tue, 09 Oct 2018 16:31:23 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has removed Kudu Jenkins from this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Removed reviewer Kudu Jenkins with the following votes: * Verified-1 by Kudu Jenkins (120) -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: deleteReviewer Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 9 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 9: Verified+1 Overriding Jenkins, unrelated test failure. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 9 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Fri, 05 Oct 2018 08:17:55 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 9: (13 comments) http://gerrit.cloudera.org:8080/#/c/11395/7/src/kudu/tablet/delta_key.h File src/kudu/tablet/delta_key.h: http://gerrit.cloudera.org:8080/#/c/11395/7/src/kudu/tablet/delta_key.h@51 PS7, Line 51: aTypeSelector ins > docs Done http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@222 PS8, Line 222: aPreparer traits > docs Done http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@271 PS8, Line 271: > ... under a snapshot? Done http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@290 PS8, Line 290: > hum, idx of what? docs would help As a general rule I prefer to leave simple accessors like this undocumented and to document the state itself. See the comment on last_added_idx_ below. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@301 PS8, Line 301: // convert the row's latest deletion state into a saved deletion or > hum this method seems weird and sketchy. when isn't there a new row index a I'll try to clarify the intent further. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@238 PS8, Line 238: for (const auto& row_id : deleted_) { : uint32_t idx_in_block = row_id - prev_prepared_idx_; : sel_vec->SetRowUnselected(idx_in_block); : } : : for (const auto& row_id : reinserted_) { : uint32_t idx_in_block = row_id - prev_prepared_idx_; : sel_vec->SetRowSelected(idx_in_block); : } > is this still correct if the same row has both deletes and reinserts? for i That's why UpdateDeletionState and MaybeProcessPreviousRowChange work the way they do: we effectively squash the entire sequence of liveness changes for a row into just the final state. So delete->reinsert->delete would be represented as a single entry in deleted_. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@342 PS8, Line 342: // We can't use RowChangeListDecoder.TwiddleDeleteStatus because: : // 1. Our deletion status includes an additional UNKNOWN state. : // 2. The logical chain of DELETEs and REINSERTs for a given row may extend : //across DeltaPreparer instances. For example, the same row may be deleted : //in one delta file and reinserted in the next. But, because : //DeltaPreparers cannot exchange this information in the context of batch : //preparation, we have to allow any state transition from UNKNOWN. : // : // DELETE+REINSERT pairs are reset back to UNKNOWN: these rows were both : // deleted and reinserted in the same batch, so their states haven't actually > this makes sense but I think this patch needs to come with an extensive dis Sure. I ran it 1000 times in slow mode and all passed. FWIW, I created a lower-level "fuzz" test to cover this and other aspects of this code. I'd appreciate a review on that too. https://gerrit.cloudera.org/c/11140/ http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@358 PS8, Line 358: UNKN > maybe UNKNOWN would be a better name? OK. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc File src/kudu/tablet/deltafile.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc@588 PS8, Line 588: prepared_ = true; > nit move this to the bottom? It's DCHECKed in AddDeltas() though. In the interest of reducing code churn I kept it where it was. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc@650 PS8, Line 650: if (VLOG_IS_ON(3)) { : RowChangeList rcl(slice); : DVLOG(3) << "Visited " << DeltaType_Name(DeltaTypeSelector::kTag) : << " delta for key: " << key.ToString() << " Mut: " : << rcl.ToString(*preparer_.opts().projection) : << " Continue?: " << (!finished_row ? "TRUE" : "FALSE"); : } > kinda weird this commet is here. move it to where finished_row is and maybe I'll move the comment, but finished_row isn't unused; it's referenced on L627. http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltamemstore-test.cc File src/kudu/tablet/deltamemstore-test.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltamemstore-te
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Tidy Bot, Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#9). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 525 insertions(+), 403 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/9 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 9 Gerrit-Owner: Adar Dembo Gerrit-Reviewe
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
David Ribeiro Alves has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 8: (13 comments) http://gerrit.cloudera.org:8080/#/c/11395/7/src/kudu/tablet/delta_key.h File src/kudu/tablet/delta_key.h: http://gerrit.cloudera.org:8080/#/c/11395/7/src/kudu/tablet/delta_key.h@51 PS7, Line 51: DeltaTypeSelector docs http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@222 PS8, Line 222: DMSPreparerTraits docs http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@271 PS8, Line 271: to 'key.row_idx()' are irrelevant ... under a snapshot? http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@290 PS8, Line 290: last_added_idx hum, idx of what? docs would help http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.h@301 PS8, Line 301: void MaybeProcessPreviousRowChange(boost::optional cur_row_idx); hum this method seems weird and sketchy. when isn't there a new row index and why are we updating previous values. maybe it will make more sense in the cc file http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@238 PS8, Line 238: for (const auto& row_id : deleted_) { : uint32_t idx_in_block = row_id - prev_prepared_idx_; : sel_vec->SetRowUnselected(idx_in_block); : } : : for (const auto& row_id : reinserted_) { : uint32_t idx_in_block = row_id - prev_prepared_idx_; : sel_vec->SetRowSelected(idx_in_block); : } is this still correct if the same row has both deletes and reinserts? for instance if the sequence of deltas is delete->reinsert->delete wouldn't this still mark it as selected? http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@342 PS8, Line 342: // We can't use RowChangeListDecoder.TwiddleDeleteStatus because: : // 1. Our deletion status includes an additional NONE state. : // 2. The logical chain of DELETEs and REINSERTs for a given row may extend : //across DeltaPreparer instances. For example, the same row may be deleted : //in one delta file and reinserted in the next. But, because : //DeltaPreparers cannot exchange this information in the context of batch : //preparation, we have to allow any state transition from NONE. : // : // DELETE+REINSERT pairs are reset back to NONE: these rows were both deleted : // and reinserted in the same batch, so their states haven't actually changed. this makes sense but I think this patch needs to come with an extensive dist-test run of fuzz test, particularly one that has many deltas on the same row http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/delta_store.cc@358 PS8, Line 358: NONE maybe UNKNOWN would be a better name? http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc File src/kudu/tablet/deltafile.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc@588 PS8, Line 588: prepared_ = true; nit move this to the bottom? http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltafile.cc@650 PS8, Line 650: // Note: if finished_row is true, we could skip the remaining deltas for : // this row by seeking the block decoder. This trades off the cost of a : // seek against the cost of decoding some irrelevant delta keys. : // : // Given that updates are expected to be uncommon and that most scans are : // _not_ historical, the current implementation eschews seeking in favor of : // skipping irrelevant deltas one by one. kinda weird this commet is here. move it to where finished_row is and maybe rename finished_row to finished_row_unused or something (I was looking for where it was used until I found this) http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltamemstore-test.cc File src/kudu/tablet/deltamemstore-test.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltamemstore-test.cc@73 PS8, Line 73: #ifdef NDEBUG : 100, : #else : 1, : #endif this is not how we normally do this, is it? http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/8/src/kudu/table
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Tidy Bot, Mike Percy, David Ribeiro Alves, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#8). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 507 insertions(+), 402 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/8 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 8 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 7: Verified+1 Overriding Jenkins, unrelated flaky test. I published http://gerrit.cloudera.org:8080/11523 for it. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 7 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Wed, 26 Sep 2018 18:31:37 + Gerrit-HasComments: No
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has removed Kudu Jenkins from this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Removed reviewer Kudu Jenkins with the following votes: * Verified-1 by Kudu Jenkins (120) -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: deleteReviewer Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 7 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Tidy Bot, Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#7). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 604 insertions(+), 402 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/7 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 7 Gerrit-Owner: Adar Dembo Gerrit-Reviewe
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Tidy Bot, Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#6). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 738 insertions(+), 484 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/6 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 6 Gerrit-Owner: Adar Dembo Gerrit-Reviewe
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 4: (6 comments) http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG Commit Message: http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG@10 PS4, Line 10: service > what's service? I meant "the servicing of deltas" (i.e. calls to ApplyUpdates, ApplyDeletes, etc.) It's an unorthodox application of the word, though, so I'll rephrase to avoid confusion. http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG@27 PS4, Line 27: I : don't have a suitable microbenchmark to prove this, > always skeptical of perf improvements that are not measured (and tracked to I ended up writing a microbenchmark for this. It's in the latest version of the patch. http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.h@274 PS4, Line 274: // Call when a new delta becomes available in DeltaIterator::PrepareBatch. > nit: maybe move this part before the paragraph above? But I want it to be the last sentence for Seek, Start, Finish, and AddDelta. http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc@95 PS4, Line 95: MvccSnapshot GetFullyInclusiveSnapshot(); > missing docs Agreed; this was from when I tried to make the DeltaPreparer code free of template-based runtime checks. A few already crept in, and one more isn't going to hurt. http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc@233 PS4, Line 233: DCHECK_LE(cur_prepared_idx_ - prev_prepared_idx_, dst->nrows()); > why again don't these match anymore? maybe doc it? I'll be honest: I don't fully understand. It has to do with the compaction code; DiskRowSetCompactionInput wraps an iterator tree that, when its NextBlock() is called, resizes the provided RowBlock down to the number of rows actually prepared, and this value is then used as input to the delta iterators' PrepareBatch(). However, the vector passed into CollectMutations() remains sized to 100 regardless. Here's what the crash looks like in compaction-test: F0918 16:56:52.669876 18710 delta_store.cc:299] Check failed: cur_prepared_idx_ - prev_prepared_idx_ == dst->size() (15 vs. 100) *** Check failure stack trace: *** *** Aborted at 1537315012 (unix time) try "date -d @1537315012" if you are using GNU date *** PC: @ 0x7f2b0f5ffe97 gsignal *** SIGABRT (@0x3e84916) received by PID 18710 (TID 0x7f2b09c48900) from PID 18710; stack trace: *** @ 0x7f2b117a9890 (unknown) @ 0x7f2b0f5ffe97 gsignal @ 0x7f2b0f601801 abort @ 0x7f2b10300d59 google::logging_fail() @ 0x7f2b10302d0d google::LogMessage::Fail() @ 0x7f2b10304ce4 google::LogMessage::SendToLog() @ 0x7f2b1030282d google::LogMessage::Flush() @ 0x7f2b103056b9 google::LogMessageFatal::~LogMessageFatal() @ 0x7f2b12042210 kudu::tablet::DeltaPreparer<>::CollectMutations() @ 0x7f2b12021183 kudu::tablet::DMSIterator::CollectMutations() @ 0x7f2b11f7307a kudu::tablet::(anonymous namespace)::DiskRowSetCompactionInput::PrepareBlock() @ 0x7f2b11f7cb38 kudu::tablet::DebugDumpCompactionInput() @ 0x7f2b11f9f3c0 kudu::tablet::DiskRowSet::DebugDump() @ 0x5634b671a439 kudu::tablet::TestCompaction_TestFlushMRSWithRolling_Test::TestBody() @ 0x7f2b119fcf9d testing::internal::HandleExceptionsInMethodIfSupported<>() @ 0x7f2b119f2622 testing::Test::Run() @ 0x7f2b119f2704 testing::TestInfo::Run() @ 0x7f2b119f2847 testing::TestCase::Run() @ 0x7f2b119f2d18 testing::internal::UnitTestImpl::RunAllTests() @ 0x7f2b119fd47d testing::internal::HandleExceptionsInMethodIfSupported<>() @ 0x7f2b119f2e71 testing::UnitTest::Run() @ 0x7f2b12378100 RUN_ALL_TESTS() @ 0x7f2b1237756b main @ 0x7f2b0f5e2b97 __libc_start_main @ 0x5634b67190fa _start http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc@248 PS3, Line 248: // Skip the remaining deltas be > Done. I left a TODO here for myself to also evaluate the optimization; I th I ended up writing a microbenchmark for this (attached). What I found was that we need to skip about 50 updates for the cost of the seek to be less than the cost of the unnecessary delta key decoding. Since most scans are on current data and the number of updates per row is expected to be relatively small, it doesn't seem like we'll be skipping that many updates in the
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#5). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. There's an opportunity to seek here and skip any remaining deltas belonging to the row, but testing with a new DMS iterator microbenchmark showed that this is only an improvement when the number of deltas skipped is sufficiently high. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. To prove it, I included a new deltafile iterator microbenchmark that scans a subset of a wide schema's columns as a DeltaApplier would. Before: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 11358.256100 task-clock (msec) #0.998 CPUs utilized ( +- 3.39% ) 140 context-switches #0.012 K/sec ( +- 27.37% ) 6 cpu-migrations#0.001 K/sec ( +- 52.36% ) 34,231 page-faults #0.003 M/sec ( +- 0.42% ) 42,288,292,153 cycles#3.723 GHz ( +- 4.12% ) 100,853,942,114 instructions #2.38 insn per cycle ( +- 5.35% ) 19,689,789,259 branches # 1733.522 M/sec ( +- 5.49% ) 69,419,478 branch-misses #0.35% of all branches ( +- 5.14% ) 11.378958537 seconds time elapsed ( +- 3.38% ) After: Performance counter stats for 'bin/deltafile-test --gtest_filter=*Benchmark*' (5 runs): 4089.419224 task-clock (msec) #0.995 CPUs utilized ( +- 1.25% ) 43 context-switches #0.011 K/sec ( +- 4.10% ) 2 cpu-migrations#0.000 K/sec ( +- 32.39% ) 34,948 page-faults #0.009 M/sec ( +- 0.22% ) 15,269,907,971 cycles#3.734 GHz ( +- 1.30% ) 32,409,048,370 instructions #2.12 insn per cycle ( +- 1.85% ) 5,848,268,795 branches # 1430.098 M/sec ( +- 1.85% ) 32,900,262 branch-misses #0.56% of all branches ( +- 2.80% ) 4.111096224 seconds time elapsed ( +- 1.18% ) It's interesting to see the number of page faults increase while everything else has gone down, but that makes sense: the new implementation allocates memory in PrepareBatch() in order to optimize the structure of the deltas. Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile-test.cc M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 12 files changed, 730 insertions(+), 483 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/5 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 5 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar De
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
David Ribeiro Alves has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 4: (5 comments) I think we should have at least a unit test to test the early out stuff, hopefully an microbench too. http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG Commit Message: http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG@10 PS4, Line 10: service what's service? http://gerrit.cloudera.org:8080/#/c/11395/4//COMMIT_MSG@27 PS4, Line 27: I : don't have a suitable microbenchmark to prove this, always skeptical of perf improvements that are not measured (and tracked to see whether they changed). maybe theres some test on the dashboard that we could reuse/adapt? we need to have more coverage for large tables anyway. http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.h@274 PS4, Line 274: // Call when a new delta becomes available in DeltaIterator::PrepareBatch. nit: maybe move this part before the paragraph above? http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc@95 PS4, Line 95: MvccSnapshot GetFullyInclusiveSnapshot(); missing docs these seem to be redundant, essentially an in class rename of the mvcc methods that requires the reader to now understand what "fullyinclusive" means http://gerrit.cloudera.org:8080/#/c/11395/4/src/kudu/tablet/delta_store.cc@233 PS4, Line 233: DCHECK_LE(cur_prepared_idx_ - prev_prepared_idx_, dst->nrows()); why again don't these match anymore? maybe doc it? -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 4 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Mon, 17 Sep 2018 16:16:31 + Gerrit-HasComments: Yes
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 3: (11 comments) http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h@293 PS3, Line 293: MaybeProcessRowChange > How about rename and slightly modify to be a bit more explicit about the se Done, except for the explicit description of the states that are compared; that feels like too much detail to me. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h@305 PS3, Line 305: rowid_t > How about boost::optional to avoid having to check for the sentine Done http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@59 PS3, Line 59: with a higher > at the given or a higher Documenting this correctly is pretty though. I'll go the other way and elide the details, since the code is just below and it's only a few lines long. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@60 PS3, Line 60: false; it's set to true > this looks reversed to me See above. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@165 PS3, Line 165: MaybeProcessRowChange(key.row_idx()); > It seems like this should be done after the IsDeltaRelevant() check Huh. I explicitly put this here because I had seen test failures when it was below, and I even rationalized it. Of course, when I moved it after the check to retest, I can't repro those failures, nor can I remember my rationalization. I'll move it. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@178 PS3, Line 178: if (!Traits::kAllowReinserts && decoder.is_reinsert()) { > nit: PREDICT_FALSE? Before he left Todd mentioned that the compiler will optimize this such that, in the specialization where it's true, it'll be kept, and in the specialization where it's false, the entire block will be removed. As for the delta file case (where reinserts are allowed), why would we PREDICT_FALSE? It's not like we know with certainty that REINSERTs are rare; that's workload dependent. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@182 PS3, Line 182: UpdateDeletionState(decoder.get_type()); > Can we call MaybeProcessRowChange() from within UpdateDeletionState() ? I'd rather not; it'd mean passing the row_idx into UpdateDeletionState(). Plus I think calling MaybeProcessRowChange only out of the main control flow methods (i.e. AddDelta and Finish) helps clarify its usage. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@223 PS3, Line 223: last_added_idx_ = key.row_idx(); > Can we call UpdateDeletionState() down here at the end? It would be better Not without some hackery; in the PREPARED_FOR_COLLECT case we haven't decoded the changelist, so we don't know whether it's a delete or not. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@337 PS3, Line 337: last_added_idx_ != MathLimits::kMax > I'm not a big fan of this... see my comment in the header file about using Changed to optional. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltafile.cc File src/kudu/tablet/deltafile.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltafile.cc@623 PS3, Line 623: visitor > AddDelta() call Done http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc@248 PS3, Line 248: // TODO(adar): is this correct? > I think this comment should be: Done. I left a TODO here for myself to also evaluate the optimization; I think I can prepare a test case that both proves its correctness and checks whether it's worth doing. Will report back. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 3 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Sat, 15 Sep 2018 01:54:35 + Gerrit-HasComments: Yes
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#4). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer for delta preparation and service. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. I modified DMSIterator to take advantage of this, which should result in a performance improvement. The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. I don't have a suitable microbenchmark to prove this, but I did run diskrowset-test's TestDeltaApplicationPerformance under perf and the resulting flame graphs showed the bulk of the iteration time as having moved from ApplyUpdates() to PrepareBatch(). Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.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-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 11 files changed, 468 insertions(+), 399 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/4 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 4 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Mike Percy has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 3: (11 comments) http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h@293 PS3, Line 293: MaybeProcessRowChange How about rename and slightly modify to be a bit more explicit about the semantics of the API? I know this is a private method but due to the nature of the control flow (it's tricky) I think it's worth explaining how to use this in more detail. // Checks whether we are done processing a row's deltas by comparing 'cur_row_idx' to 'last_added_idx_'. If they are both set and not equal, we assume we are done with the previous row, and we will attempt to convert the row's latest deletion state into a saved deletion or reinsertion if needed. // If 'cur_row_idx' is not set, we will process the delta state row the row in 'last_added_idx_' if it is set. That method should be called when we are done processing a batch of deltas, such as from Finish(). MaybeProcessPreviousRowChange(boost::optional cur_row_idx) http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.h@305 PS3, Line 305: rowid_t How about boost::optional to avoid having to check for the sentinel value numeric_limits::max()? http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@59 PS3, Line 59: with a higher at the given or a higher http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@60 PS3, Line 60: false; it's set to true this looks reversed to me http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@165 PS3, Line 165: MaybeProcessRowChange(key.row_idx()); It seems like this should be done after the IsDeltaRelevant() check http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@178 PS3, Line 178: if (!Traits::kAllowReinserts && decoder.is_reinsert()) { nit: PREDICT_FALSE? http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@182 PS3, Line 182: UpdateDeletionState(decoder.get_type()); Can we call MaybeProcessRowChange() from within UpdateDeletionState() ? http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@223 PS3, Line 223: last_added_idx_ = key.row_idx(); Can we call UpdateDeletionState() down here at the end? It would be better to update last_added_idx_ as part of the UpdateDeletionState call to manage that state all in one place. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/delta_store.cc@337 PS3, Line 337: last_added_idx_ != MathLimits::kMax I'm not a big fan of this... see my comment in the header file about using boost::optional for last_added_idx_ instead. http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltafile.cc File src/kudu/tablet/deltafile.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltafile.cc@623 PS3, Line 623: visitor AddDelta() call http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/3/src/kudu/tablet/deltamemstore.cc@248 PS3, Line 248: // TODO(adar): is this correct? I think this comment should be: // Skip the remaining timestamps for this row. By the way, this looks right to me, but it seems like we should put in test coverage for this optimization to be sure it does what we think it does. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 3 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Fri, 14 Sep 2018 18:43:46 + Gerrit-HasComments: Yes
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Mike Percy, David Ribeiro Alves, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#3). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer for delta preparation and service. Besides sharing code, the motivation is to take advantage of the performance improvement inherent to DeltaPreparer: decoding a batch of deltas just once in PrepareBatch() as opposed to on each call to ApplyUpdates(). Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. I modified DMSIterator to take advantage of this, which should result in a performance improvement. I tried to centralize as much state tracking in DeltaPreparer, though there were several aspects of this that were confusing (namely prepared_idx_, last_added_idx_, and prepared_count_). The improvement should be most noticeable on tables with wide schemas where multiple columns are projected. In these situations, the column-by-column ApplyUpdates() approach incurred a lot of unnecessary delta decoding. I don't have a suitable microbenchmark to prove this, but I did run diskrowset-test's TestDeltaApplicationPerformance under perf and the resulting flame graphs showed the bulk of the iteration time as having moved from ApplyUpdates() to PrepareBatch(). Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.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-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 11 files changed, 473 insertions(+), 395 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/3 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 3 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 3: (6 comments) http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG Commit Message: http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@7 PS2, Line 7: use DeltaPreparer > Can you talk more about how this changes the logic? Or do you view this as It's a refactor at heart, though it (obviously) affects the division of labor between PrepareBatch() and ApplyUpdates(). I mentioned that below where I talk about flame graphs. At the end of the day the DeltaFileIterator still does the same thing it always did: read deltas from a file, decode them, and apply the appropriate ones during a scan. It just does it more efficiently. I actually don't want to mention diff scans in these two patches because they stand on their own merits: they improve scan performance when projecting multiple columns by reducing CPU load incurred via unnecessary delta decoding. Bringing diff scans into this will just muddy the waters. Instead, I'll tie back to these patches in the diff scan patch series. http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@9 PS2, Line 9: leverage DeltaPreparer > why? just code reuse? get rid of Todd's TODO in the code? See the JIRA and below: this refactor improves performance by getting rid of the decoding-heavy approach taken by the "visitor" pattern previously used by DeltaFileIterator. http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@25 PS2, Line 25: entralize as > Can you be more specific about what we think these improvements are? The rest of the sentence explains: it does away with a bunch of unnecessary delta decoding. There's more information in the JIRA. I'll add some more color here but the commit message is already quite detailed (by my standards) and in the interest of brevity I don't want to duplicate too much from the JIRA. http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.h@258 PS2, Line 258: re irrelevan > nit: doc this parameter Done http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.cc@57 PS2, Line 57: // Returns whether a mutation at 'ts' is relevant under 'snap'. > Mind documenting the interface to this helper? It's not obvious what the me Done http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/deltamemstore.cc@248 PS2, Line 248: // TODO(adar): is this correct? > Mind adding a comment with the thought process behind this bookkeeping / cl Not sure what you mean. This isn't bookkeeping or cleanup; it's an optimization to skip any additional deltas for this row once we've established that we're done with the row. I added the TODO because this seemed like a brain-dead optimization that should have been done previously, so I was wondering if perhaps it's an incorrect thing to do. See https://gerrit.cloudera.org/c/11394/2/src/kudu/tablet/deltamemstore.cc#b268 for the old code here. -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 3 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Wed, 12 Sep 2018 19:40:18 + Gerrit-HasComments: Yes
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Mike Percy has posted comments on this change. ( http://gerrit.cloudera.org:8080/11395 ) Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. Patch Set 2: (6 comments) I'm working through this patch... as it's changing some core code I've never worked with before, I am just posting some initial thoughts. http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG Commit Message: http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@7 PS2, Line 7: use DeltaPreparer Can you talk more about how this changes the logic? Or do you view this as simply a refactor? Can you also put this in context of diff scans and explain how this helps? http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@9 PS2, Line 9: leverage DeltaPreparer why? just code reuse? get rid of Todd's TODO in the code? http://gerrit.cloudera.org:8080/#/c/11395/2//COMMIT_MSG@25 PS2, Line 25: improvements Can you be more specific about what we think these improvements are? http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.h File src/kudu/tablet/delta_store.h: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.h@258 PS2, Line 258: finished_row nit: doc this parameter http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.cc File src/kudu/tablet/delta_store.cc: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/delta_store.cc@57 PS2, Line 57: template Mind documenting the interface to this helper? It's not obvious what the meaning of 'finished_row' is in this context. http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/deltamemstore.cc File src/kudu/tablet/deltamemstore.cc: http://gerrit.cloudera.org:8080/#/c/11395/2/src/kudu/tablet/deltamemstore.cc@248 PS2, Line 248: // TODO(adar): is this correct? Mind adding a comment with the thought process behind this bookkeeping / cleanup code? -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 2 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Adar Dembo Gerrit-Reviewer: David Ribeiro Alves Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon Gerrit-Comment-Date: Wed, 12 Sep 2018 17:26:28 + Gerrit-HasComments: Yes
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Mike Percy, Kudu Jenkins, Todd Lipcon, I'd like you to reexamine a change. Please visit http://gerrit.cloudera.org:8080/11395 to look at the new patch set (#2). Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer for delta preparation and service. Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. I modified DMSIterator to take advantage of this, which should result in a performance improvement. I tried to centralize as much state tracking in DeltaPreparer, though there were several aspects of this that were confusing (namely prepared_idx_, last_added_idx_, and prepared_count_). The patch's improvements should be most noticeable on wide schemas where the column-by-column ApplyUpdates() approach yielded a lot of unnecessary delta decoding. I don't have a suitable microbenchmark to prove this, but I did run diskrowset-test's TestDeltaApplicationPerformance under perf and the resulting flame graphs showed the bulk of the iteration time as having moved from ApplyUpdates() to PrepareBatch(). Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.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-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 11 files changed, 417 insertions(+), 393 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/2 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newpatchset Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 2 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon
[kudu-CR] KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator
Hello Mike Percy, Todd Lipcon, I'd like you to do a code review. Please visit http://gerrit.cloudera.org:8080/11395 to review the following change. Change subject: KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator .. KUDU-686 (part 2/2): use DeltaPreparer in DeltaFileIterator This patch rewrites much of DeltaFileIterator to leverage DeltaPreparer for delta preparation and service. Seeing as DeltaPreparer was originally built for DMSIterator, here are the various augmentations that were necessary to support DeltaFileIterator: - REINSERT support, which meant more complicated deletion state tracking. - FilterColumnIdsAndCollectDeltas support, cribbed from DeltaFileIterator. - A templatized traits system to control which features were enabled. This also meant templatizing both DeltaPreparer and DeltaFileIterator. - Early out from the "apply all deltas for a row" loop when the timestamp is no longer relevant. I modified DMSIterator to take advantage of this, which should result in a performance improvement. I tried to centralize as much state tracking in DeltaPreparer, though there were several aspects of this that were confusing (namely prepared_idx_, last_added_idx_, and prepared_count_). The patch's improvements should be most noticeable on wide schemas where the column-by-column ApplyUpdates() approach yielded a lot of unnecessary delta I/O and decoding. I don't have a suitable microbenchmark to prove this, but I did run diskrowset-test's TestDeltaApplicationPerformance under perf and the resulting flame graphs showed the bulk of the iteration time as having moved from ApplyUpdates() to PrepareBatch(). Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 --- M src/kudu/tablet/delta_key.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-test.cc M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/mvcc.cc M src/kudu/tablet/mvcc.h M src/kudu/tablet/tablet-test-util.h 11 files changed, 417 insertions(+), 393 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/95/11395/1 -- To view, visit http://gerrit.cloudera.org:8080/11395 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: newchange Gerrit-Change-Id: I87de52092262c4b42c1bd5107f9139edfc3888b5 Gerrit-Change-Number: 11395 Gerrit-PatchSet: 1 Gerrit-Owner: Adar Dembo Gerrit-Reviewer: Mike Percy Gerrit-Reviewer: Todd Lipcon