You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@kudu.apache.org by "Todd Lipcon (Code Review)" <ge...@cloudera.org> on 2017/03/25 01:10:01 UTC
[kudu-CR] WIP: check for row presence in rowset-wise order
Hello David Ribeiro Alves,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/6483
to review the following change.
Change subject: WIP: check for row presence in rowset-wise order
......................................................................
WIP: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if it's not present in any rowset (based on above marking)
apply it
The aim here is that because we end up accessing each rowset many times
sequentially in ascending key order, we open up the opportunity for two
potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
TODO: clean up
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
3 files changed, 141 insertions(+), 45 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/1
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 11: Code-Review+2
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 11
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: No
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 10:
(8 comments)
http://gerrit.cloudera.org:8080/#/c/6483/10//COMMIT_MSG
Commit Message:
PS10, Line 50: This patch isn't meant to give big wins on its own, but the further
: patches in the series ought to.
nit: it would make this reviewer more at ease if I could take a peek at those numbers in a commit message somewhere.
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/row_op.h
File src/kudu/tablet/row_op.h:
PS8, Line 85: Flag whether this op has already had 'present_in_rowset' filled in.
> hrm... you mean down below for the comment on 'present_in_rowset' right? Wi
oh, yeah. thanks
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/row_op.h
File src/kudu/tablet/row_op.h:
PS10, Line 88: exists in no RowSet.
nit: doesn't exist in any RowSet
PS10, Line 93: to be alive in no RowSet.
nit: not to be alive in any RowSet.
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/tablet.cc
File src/kudu/tablet/tablet.cc:
PS10, Line 680: num_ops == 0
predict_false
PS10, Line 698: // equivalent indexes.
nit: no need to wrap
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/tablet.h
File src/kudu/tablet/tablet.h:
PS10, Line 404: // invalid.
nit: no need to wrap
PS10, Line 407: // Validate 'op' as in 'ValidateOp()' above. If it is invalid, marks
: // the op as failed and returns false. If valid, marks the op as validated
: // and returns true.
nit: two lines instead of three
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 10
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] WIP: tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#6).
Change subject: WIP: tablet: check for row presence in rowset-wise order
......................................................................
WIP: tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 297 insertions(+), 82 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/6
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 6
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello David Ribeiro Alves, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#11).
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't meant to give big wins on its own, but the further
patches in the series reap big benefits (see later commit messages for details)
As a simple benchmark to make sure performance didn't regress, I used
tpch_real_world with 12 writer threads on a single machine for scale
factor 100 (600M rows).
Before:
Wall time: 1007s
Server CPU time: 9333s
After:
Wall time: 1014s (+0.7%, probably noise)
Server CPU time: 8861s (-5.3%, could be significant)
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 306 insertions(+), 85 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/11
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 11
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 9:
Compilation issues with old gcc. Please review anyway and I'll rev to fix if it looks good.
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 9
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: No
[kudu-CR] WIP: tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#7).
Change subject: WIP: tablet: check for row presence in rowset-wise order
......................................................................
WIP: tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 299 insertions(+), 84 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/7
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 7
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has submitted this change and it was merged.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't meant to give big wins on its own, but the further
patches in the series reap big benefits (see later commit messages for details)
As a simple benchmark to make sure performance didn't regress, I used
tpch_real_world with 12 writer threads on a single machine for scale
factor 100 (600M rows).
Before:
Wall time: 1007s
Server CPU time: 9333s
After:
Wall time: 1014s (+0.7%, probably noise)
Server CPU time: 8861s (-5.3%, could be significant)
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Reviewed-on: http://gerrit.cloudera.org:8080/6483
Tested-by: Kudu Jenkins
Reviewed-by: David Ribeiro Alves <dr...@apache.org>
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 306 insertions(+), 85 deletions(-)
Approvals:
David Ribeiro Alves: Looks good to me, approved
Kudu Jenkins: Verified
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 12
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] WIP: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#2).
Change subject: WIP: check for row presence in rowset-wise order
......................................................................
WIP: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if it's not present in any rowset (based on above marking)
apply it
The aim here is that because we end up accessing each rowset many times
sequentially in ascending key order, we open up the opportunity for two
potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
TODO: clean up
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
3 files changed, 163 insertions(+), 45 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/2
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#8).
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't meant to give big wins on its own, but the further
patches in the series ought to.
As a simple benchmark to make sure performance didn't regress, I used
tpch_real_world with 12 writer threads on a single machine for scale
factor 100 (600M rows).
Before:
Wall time: 1007s
Server CPU time: 9333s
After:
Wall time: 1014s (+0.7%, probably noise)
Server CPU time: 8861s (-5.3%, could be significant)
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 303 insertions(+), 84 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/8
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 8
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] WIP: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#5).
Change subject: WIP: check for row presence in rowset-wise order
......................................................................
WIP: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if it's not present in any rowset (based on above marking)
apply it
The aim here is that because we end up accessing each rowset many times
sequentially in ascending key order, we open up the opportunity for two
potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
TODO: clean up
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
4 files changed, 233 insertions(+), 43 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/5
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] WIP: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#4).
Change subject: WIP: check for row presence in rowset-wise order
......................................................................
WIP: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if it's not present in any rowset (based on above marking)
apply it
The aim here is that because we end up accessing each rowset many times
sequentially in ascending key order, we open up the opportunity for two
potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
TODO: clean up
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
4 files changed, 234 insertions(+), 43 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/4
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 10:
(6 comments)
http://gerrit.cloudera.org:8080/#/c/6483/10//COMMIT_MSG
Commit Message:
PS10, Line 50: This patch isn't meant to give big wins on its own, but the further
: patches in the series ought to.
> nit: it would make this reviewer more at ease if I could take a peek at tho
working on gathering some numbers for the next patch in the series to be posted later this afternoon.
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/row_op.h
File src/kudu/tablet/row_op.h:
PS10, Line 93: to be alive in no RowSet.
> nit: not to be alive in any RowSet.
Done
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/tablet.cc
File src/kudu/tablet/tablet.cc:
PS10, Line 680: num_ops == 0
> predict_false
Done
PS10, Line 698: // equivalent indexes.
> nit: no need to wrap
Done
http://gerrit.cloudera.org:8080/#/c/6483/10/src/kudu/tablet/tablet.h
File src/kudu/tablet/tablet.h:
PS10, Line 404: // invalid.
> nit: no need to wrap
Done
PS10, Line 407: // Validate 'op' as in 'ValidateOp()' above. If it is invalid, marks
: // the op as failed and returns false. If valid, marks the op as validated
: // and returns true.
> nit: two lines instead of three
Done
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 10
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 8:
(14 comments)
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/row_op.h
File src/kudu/tablet/row_op.h:
PS8, Line 85: Flag whether this op has already had 'present_in_rowset' filled in.
> rephrase here and elsewhere to "present and alive"
hrm... you mean down below for the comment on 'present_in_rowset' right? Will do, there.
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/tablet.cc
File src/kudu/tablet/tablet.cc:
PS8, Line 650: mutate->present_in_rowset->MutateRow(
: ts,
: *mutate->key_probe,
: mutate->decoded_op.changelist,
: tx_state->op_id(),
: stats,
: result.get());
> inconsistent wrapping with MutateRow below.
yea. I think I can probably improve this code a bit anyway to only call MutateRow once.
PS8, Line 658: rowset
> should refer here and elsewhere to "DiskRowSet" since the MRS is also a row
Well, the existing RowSet might be a DuplicatingRowSet implementation, not necessarily a DRS, right?
Line 667: if (s.ok()) {
> PREDICT_TRUE
Done
PS8, Line 688: // TODO(todd) determine why we sometimes get empty writes!
> is this new or did it happen before this patch series?
not new. it seems to be in the master, we sometimes make a SyncWrite of an empty batch.
PS8, Line 696: pair<Slice, int>
> aren't you using a struct for this somewhere else? can you reuse the same s
we are, but it's in the internals of RowSetTree, so I don't think it would make it more clear to make someone go dig into a different file.
PS8, Line 703: keys_and_indexes.emplace_back(op->key_probe->encoded_key_slice(), i);
> could you determine in this loop whether the keys were already sorted and r
will add a TODO.
PS8, Line 717: &
> nit: pair<Slice, int>&
Done
PS8, Line 740: const auto& ClearPending = [&]() {
: next_key.clear();
: if (pending.empty()) return;
: DCHECK(std::is_sorted(pending.begin(), pending.end(),
: [&](const pair<RowSet*, int>& a,
: const pair<RowSet*, int>& b) {
: auto s_a = keys[a.second];
: auto s_b = keys[b.second];
: return s_a.compare(s_b) < 0;
: }));
: RowSet* rs = pending[0].first;
: for (auto it = pending.begin();
: it != pending.end();
: ++it) {
: DCHECK_EQ(it->first, rs);
: int op_idx = keys_and_indexes[it->second].second;
: RowOp* op = row_ops_base[op_idx];
: if (op->present_in_rowset) {
: // Already found this op present somewhere.
: continue;
: }
:
: // TODO(todd) is CHECK_OK correct? it used to be that errors here
: // would just be silently ignored, so this seems at least an improvement.
: bool present = false;
: CHECK_OK(rs->CheckRowPresent(*op->key_probe, &present, tx_state->mutable_op_stats(op_idx)));
: if (present) {
: op->present_in_rowset = rs;
: }
: }
: pending.clear();
: };
> this is quite the hefty anonymous function. move it somwhere else?
the problem is that it refers to quite a few variables in scope (row_ops_base, tx_state, keys_and_indexes, etc). Let me see if adding the docs you requested below make it clearer what's going on.
PS8, Line 773: const TabletComponents* comps = DCHECK_NOTNULL(tx_state->tablet_components());
: comps->rowsets->ForEachRowSetContainingKeys(
: keys,
: [&](RowSet* rs, int i) {
: if (!pending.empty() && rs != pending.back().first) {
: ClearPending();
: }
: pending.emplace_back(rs, i);
: });
: ClearPending();
> doc what this is doing
Done
PS8, Line 784: for (auto& p : keys_and_indexes) {
: row_ops_base[p.second]->checked_present = true;
: }
> is checked_present used before this? could we just set it in one of the ear
We can't set it in the ClearPending callback because it's possible that some of the ops would be completely culled by the IntervalTree (i.e. fall fully outside any existing interval).
We can't set it before the std::unique() call because then we'd end up marking duplicate rowkeys as having been checked, which is not accurate.
We could weave it into the std::unique loop, but then we'd have to stop using std::unique and implement it ourselves. Might be worth it to avoid some cache misses. I'll add a TODO.
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/tablet.h
File src/kudu/tablet/tablet.h:
PS8, Line 403: // Validate the contents of 'op' and return a bad Status if it is
: // invalid.
: Status ValidateOp(const RowOp& op) const;
:
: // Validate 'op' as in 'ValidateOp()' above. If it is invalid, marks
: // the op as failed and returns false. If valid, marks the op as validated
: // and returns true.
: bool ValidateOpOrMarkFailed(RowOp* op) const;
> general wondering since this is not dependent on tablet internal state coul
It does depend on the tablet state a little bit in that it requires the schema. Would rather avoid this refactoring for now, though I agree that tablet.cc is a bit of a monster at 2k+ lines.
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/transactions/write_transaction.cc
File src/kudu/tablet/transactions/write_transaction.cc:
PS8, Line 273:
> nit no need to wrap
Done
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/transactions/write_transaction.h
File src/kudu/tablet/transactions/write_transaction.h:
PS8, Line 163: // 'i'.
> nit no need to wrap
Done
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 8
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#9).
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
tablet: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if insert:
if it's not present in any rowset (based on above marking)
apply it
if mutate:
apply to the rowset determined above
The one wrinkle not expressed in the above pseudo-code is the handling
of batches with duplicate keys (eg insert/update/delete/insert
sequences of the same PK in one batch). In those cases, the later
operations may find their keys in different RowSets based on the results
of the earlier operations, and thus we need to continue to do the
presence checks one-by-one.
The aim with this patch is that because we end up accessing each rowset
many times sequentially in ascending key order, we open up the
opportunity for two potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't meant to give big wins on its own, but the further
patches in the series ought to.
As a simple benchmark to make sure performance didn't regress, I used
tpch_real_world with 12 writer threads on a single machine for scale
factor 100 (600M rows).
Before:
Wall time: 1007s
Server CPU time: 9333s
After:
Wall time: 1014s (+0.7%, probably noise)
Server CPU time: 8861s (-5.3%, could be significant)
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/integration-tests/fuzz-itest.cc
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
M src/kudu/tablet/transactions/write_transaction.cc
M src/kudu/tablet/transactions/write_transaction.h
6 files changed, 309 insertions(+), 85 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/9
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 9
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] WIP: check for row presence in rowset-wise order
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/6483
to look at the new patch set (#3).
Change subject: WIP: check for row presence in rowset-wise order
......................................................................
WIP: check for row presence in rowset-wise order
This changes the overall flow of applying batches of writes from:
for each key in batch:
find which rowsets may contain this key
for each rowset:
check if key is present in rowset
if not present in any rowset, apply the write
to:
sort all ops by key
bulk-query the interval tree
for each rowset:
for each key which might be in that rowset, in sorted order:
check if the key is present
if so, mark it as such
for each op:
if it's not present in any rowset (based on above marking)
apply it
The aim here is that because we end up accessing each rowset many times
sequentially in ascending key order, we open up the opportunity for two
potential optimizations:
1) a thread-local cache can keep seeked iterators within that rowset, as
well as hot blocks such as the index blocks, and reuse it cross-op
within the same batch
2) we can detect when several of the ops in a batch all fall into a
"gap" in a particular rowset, and "skip ahead", short circuiting a
bunch of checks
This patch isn't likely to give big wins on its own, but the further
patches in the series ought to.
TODO: do a quick benchmark or two to make sure this doesn't _regress_.
TODO: clean up
Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
---
M src/kudu/tablet/row_op.h
M src/kudu/tablet/tablet.cc
M src/kudu/tablet/tablet.h
3 files changed, 189 insertions(+), 43 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/83/6483/3
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] tablet: check for row presence in rowset-wise order
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: tablet: check for row presence in rowset-wise order
......................................................................
Patch Set 8:
(14 comments)
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/row_op.h
File src/kudu/tablet/row_op.h:
PS8, Line 85: Flag whether this op has already had 'present_in_rowset' filled in.
rephrase here and elsewhere to "present and alive"
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/tablet.cc
File src/kudu/tablet/tablet.cc:
PS8, Line 650: mutate->present_in_rowset->MutateRow(
: ts,
: *mutate->key_probe,
: mutate->decoded_op.changelist,
: tx_state->op_id(),
: stats,
: result.get());
inconsistent wrapping with MutateRow below.
PS8, Line 658: rowset
should refer here and elsewhere to "DiskRowSet" since the MRS is also a row set.
Line 667: if (s.ok()) {
PREDICT_TRUE
PS8, Line 688: // TODO(todd) determine why we sometimes get empty writes!
is this new or did it happen before this patch series?
PS8, Line 696: pair<Slice, int>
aren't you using a struct for this somewhere else? can you reuse the same struct or at least typedef it?
PS8, Line 703: keys_and_indexes.emplace_back(op->key_probe->encoded_key_slice(), i);
could you determine in this loop whether the keys were already sorted and remove the duplicates that you find along the way?
this would allow to skip the sort and std::unique below if the client already sorted the keys and maybe also allow to build key vector in the same loop.
if you feel this is early optimization maybe just leave a TODO
PS8, Line 717: &
nit: pair<Slice, int>&
same below
PS8, Line 740: const auto& ClearPending = [&]() {
: next_key.clear();
: if (pending.empty()) return;
: DCHECK(std::is_sorted(pending.begin(), pending.end(),
: [&](const pair<RowSet*, int>& a,
: const pair<RowSet*, int>& b) {
: auto s_a = keys[a.second];
: auto s_b = keys[b.second];
: return s_a.compare(s_b) < 0;
: }));
: RowSet* rs = pending[0].first;
: for (auto it = pending.begin();
: it != pending.end();
: ++it) {
: DCHECK_EQ(it->first, rs);
: int op_idx = keys_and_indexes[it->second].second;
: RowOp* op = row_ops_base[op_idx];
: if (op->present_in_rowset) {
: // Already found this op present somewhere.
: continue;
: }
:
: // TODO(todd) is CHECK_OK correct? it used to be that errors here
: // would just be silently ignored, so this seems at least an improvement.
: bool present = false;
: CHECK_OK(rs->CheckRowPresent(*op->key_probe, &present, tx_state->mutable_op_stats(op_idx)));
: if (present) {
: op->present_in_rowset = rs;
: }
: }
: pending.clear();
: };
this is quite the hefty anonymous function. move it somwhere else?
PS8, Line 773: const TabletComponents* comps = DCHECK_NOTNULL(tx_state->tablet_components());
: comps->rowsets->ForEachRowSetContainingKeys(
: keys,
: [&](RowSet* rs, int i) {
: if (!pending.empty() && rs != pending.back().first) {
: ClearPending();
: }
: pending.emplace_back(rs, i);
: });
: ClearPending();
doc what this is doing
PS8, Line 784: for (auto& p : keys_and_indexes) {
: row_ops_base[p.second]->checked_present = true;
: }
is checked_present used before this? could we just set it in one of the earlier loops?
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/tablet.h
File src/kudu/tablet/tablet.h:
PS8, Line 403: // Validate the contents of 'op' and return a bad Status if it is
: // invalid.
: Status ValidateOp(const RowOp& op) const;
:
: // Validate 'op' as in 'ValidateOp()' above. If it is invalid, marks
: // the op as failed and returns false. If valid, marks the op as validated
: // and returns true.
: bool ValidateOpOrMarkFailed(RowOp* op) const;
general wondering since this is not dependent on tablet internal state could we just do this before the op is submitted, outside of tablet.cc (Maybe some static method in RowOp or in a new tablet_util.cc file). tablet.cc is already pretty big and it's beginning to become untenable to navigate in it. This would avoid expanding it further and maybe even trim it a bit. It would also help slightly if we ever decide that we want to do this non-state changing work while replication is ongoing.
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/transactions/write_transaction.cc
File src/kudu/tablet/transactions/write_transaction.cc:
PS8, Line 273:
nit no need to wrap
http://gerrit.cloudera.org:8080/#/c/6483/8/src/kudu/tablet/transactions/write_transaction.h
File src/kudu/tablet/transactions/write_transaction.h:
PS8, Line 163: // 'i'.
nit no need to wrap
--
To view, visit http://gerrit.cloudera.org:8080/6483
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I9a678bb0da130ce94aae3634c82ace2d6898ffa2
Gerrit-PatchSet: 8
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-HasComments: Yes