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 2016/08/28 23:28:07 UTC
[kudu-CR] compaction policy: fix bound calculation
Hello Anonymous Coward #174,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/4152
to review the following change.
Change subject: compaction_policy: fix bound calculation
......................................................................
compaction_policy: fix bound calculation
The upper-bound calculator for the knapsack problem maintains a heap
which is supposed to keep no more than one item beyond the maximum
weight allowed.
This invariant got broken in some cases when an item was added to the
heap -- in some cases a single addition actually requires removing
multiple old items.
Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
---
M src/kudu/tablet/compaction_policy.cc
1 file changed, 6 insertions(+), 5 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/4152/1
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Anonymous Coward #174
[kudu-CR] compaction policy: fix bound calculation
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 2:
anyway to add a simple test?
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Kudu Jenkins (Code Review)" <ge...@cloudera.org>.
Kudu Jenkins has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 1:
Build Started http://104.196.14.100/job/kudu-gerrit/3116/
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 1:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/4152/1/src/kudu/tablet/compaction_policy.cc
File src/kudu/tablet/compaction_policy.cc:
PS1, Line 160: fractional_solution_
> Nit: why not to use priority_queue for that as a handy wrapper?
good point, although in the next patch I'll need to actually access all the non-top elements of the heap, and priority_queue<> doesn't seem to let you access non-top elements without popping.
PS1, Line 161: >=
> So, if the resulting weight is equal to the specified max_weight, then it's
Done
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: Yes
[kudu-CR] compaction policy: fix bound calculation
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has submitted this change and it was merged.
Change subject: compaction_policy: fix bound calculation
......................................................................
compaction_policy: fix bound calculation
The upper-bound calculator for the knapsack problem maintains a heap
which is supposed to keep no more than one item beyond the maximum
weight allowed.
This invariant got broken in some cases when an item was added to the
heap -- in some cases a single addition actually requires removing
multiple old items.
A regression test for this fix is included in the following commit
("Optimize budgeted compaction policy with an approximation")
Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Reviewed-on: http://gerrit.cloudera.org:8080/4152
Reviewed-by: David Ribeiro Alves <dr...@apache.org>
Tested-by: Kudu Jenkins
---
M src/kudu/tablet/compaction_policy.cc
1 file changed, 6 insertions(+), 5 deletions(-)
Approvals:
David Ribeiro Alves: Looks good to me, approved
Kudu Jenkins: Verified
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
[kudu-CR] compaction policy: fix bound calculation
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 3: Code-Review+2
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Kudu Jenkins (Code Review)" <ge...@cloudera.org>.
Kudu Jenkins has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 3:
Build Started http://104.196.14.100/job/kudu-gerrit/3242/
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 2: Code-Review+1
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Will Berkeley, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/4152
to look at the new patch set (#2).
Change subject: compaction_policy: fix bound calculation
......................................................................
compaction_policy: fix bound calculation
The upper-bound calculator for the knapsack problem maintains a heap
which is supposed to keep no more than one item beyond the maximum
weight allowed.
This invariant got broken in some cases when an item was added to the
heap -- in some cases a single addition actually requires removing
multiple old items.
Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
---
M src/kudu/tablet/compaction_policy.cc
1 file changed, 6 insertions(+), 5 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/4152/2
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
[kudu-CR] compaction policy: fix bound calculation
Posted by "Will Berkeley (Code Review)" <ge...@cloudera.org>.
Will Berkeley has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 1: Code-Review+1
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Will Berkeley, Alexey Serbin, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/4152
to look at the new patch set (#3).
Change subject: compaction_policy: fix bound calculation
......................................................................
compaction_policy: fix bound calculation
The upper-bound calculator for the knapsack problem maintains a heap
which is supposed to keep no more than one item beyond the maximum
weight allowed.
This invariant got broken in some cases when an item was added to the
heap -- in some cases a single addition actually requires removing
multiple old items.
A regression test for this fix is included in the following commit
("Optimize budgeted compaction policy with an approximation")
Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
---
M src/kudu/tablet/compaction_policy.cc
1 file changed, 6 insertions(+), 5 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/52/4152/3
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
[kudu-CR] compaction policy: fix bound calculation
Posted by "Kudu Jenkins (Code Review)" <ge...@cloudera.org>.
Kudu Jenkins has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 2:
Build Started http://104.196.14.100/job/kudu-gerrit/3148/
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No
[kudu-CR] compaction policy: fix bound calculation
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 1:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/4152/1/src/kudu/tablet/compaction_policy.cc
File src/kudu/tablet/compaction_policy.cc:
PS1, Line 160: fractional_solution_
Nit: why not to use priority_queue for that as a handy wrapper?
PS1, Line 161: >=
So, if the resulting weight is equal to the specified max_weight, then it's not a solution?
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: Yes
[kudu-CR] compaction policy: fix bound calculation
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: compaction_policy: fix bound calculation
......................................................................
Patch Set 2:
The tests in the next commit actually catch this bug. If I revert this patch and run the test from "Optimize budgeted compaction policy with an approximation" it fails with:
../../src/kudu/tablet/compaction_policy-test.cc:112: Failure
Expected: (total_size) <= (budget_mb), actual: 144 vs 128
--
To view, visit http://gerrit.cloudera.org:8080/4152
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: I76364c17debd7293b36884d64c7747f8c604ae12
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Anonymous Coward #174
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Will Berkeley <wd...@gmail.com>
Gerrit-HasComments: No