You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2021/05/14 08:20:48 UTC
[GitHub] [druid] yuanlihan opened a new pull request #11257: Reduce method invocation of reservoir sampling
yuanlihan opened a new pull request #11257:
URL: https://github.com/apache/druid/pull/11257
Fixes #11256.
### Description
Adding a new Reservoir Sampling method to sample K elements each time instead of only one element per method invocation.
A default method `pickSegmentsToMove` will be added to interface `BalancerStrategy` to pick K segments to move in a single method invocation.
<hr>
##### Key changed/added classes in this PR
* `BalancerStrategy`
* `ReservoirSegmentSampler`
* `BalanceSegments`
<hr>
<!-- Check the items by putting "x" in the brackets for the done things. Not all of these items apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items from the checklist below are strictly necessary, but it would be very helpful if you at least self-review the PR. -->
This PR has:
- [X] been self-reviewed.(Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [X] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [X] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
- [ ] added integration tests.
- [X] been tested in a test Druid cluster.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] clintropolis commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r648885387
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/duty/BalanceSegments.java
##########
@@ -180,22 +181,29 @@ private void balanceTier(
int maxSegmentsToMove
)
{
+ if (maxSegmentsToMove <= 0) {
+ return new Pair<>(0, 0);
+ }
+
final BalancerStrategy strategy = params.getBalancerStrategy();
final int maxIterations = 2 * maxSegmentsToMove;
final int maxToLoad = params.getCoordinatorDynamicConfig().getMaxSegmentsInNodeLoadingQueue();
int moved = 0, unmoved = 0;
+ Iterator<BalancerSegmentHolder> segmetnsToMove = strategy.pickSegmentsToMove(
Review comment:
nit: typo `segmetnsToMove` -> `segmentsToMove`
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
Review comment:
does it make sense to retain the `percentOfSegmentsToConsider` functionality to allow short-circuiting iterateAllSegments across all servers? We update the docs https://github.com/apache/druid/blob/master/docs/configuration/index.md#dynamic-configuration accordingly either way
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/BalancerStrategy.java
##########
@@ -71,13 +71,60 @@
* @return {@link BalancerSegmentHolder} containing segment to move and server it currently resides on, or null if
* there are no segments to pick from (i. e. all provided serverHolders are empty).
*/
+ @Deprecated
Review comment:
this doesn't really seem deprecated so much as no longer called at all, maybe we should remove it?
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
+ )
+ {
+ List<BalancerSegmentHolder> holders = new ArrayList<>(k);
+ int numSoFar = 0;
+
+ for (ServerHolder server : serverHolders) {
+ if (!server.getServer().getType().isSegmentReplicationTarget()) {
+ // if the server only handles broadcast segments (which don't need to be rebalanced), we have nothing to do
+ continue;
+ }
+
+ for (DataSegment segment : server.getServer().iterateAllSegments()) {
+ if (broadcastDatasources.contains(segment.getDataSource())) {
+ // we don't need to rebalance segments that were assigned via broadcast rules
+ continue;
+ }
+
+ if (numSoFar < k) {
+ holders.add(new BalancerSegmentHolder(server.getServer(), segment));
+ numSoFar++;
+ continue;
+ }
+ int randNum = ThreadLocalRandom.current().nextInt(numSoFar + 1);
+ if (randNum < k) {
+ holders.set(randNum, new BalancerSegmentHolder(server.getServer(), segment));
+ }
Review comment:
i think it would be worth adding some code comments here to describe that this algorithm has 2 phases, where it picks the first `k` segments from the servers, in order, then iterates through the server list randomly replacing these picked segments with decreasing frequency the more segments have been iterated.
Im also somewhat curious/nervous about random this pick method is compared to the previous one, though I'm not entirely sure how it would be measured.
I think we should add a new coordinator dynamic config property, https://github.com/apache/druid/blob/master/server/src/main/java/org/apache/druid/server/coordinator/CoordinatorDynamicConfig.java, to allow falling back to the old algorithm in case there are any unpredictable strange behavior caused by this new algorithm, maybe `useBatchedSegmentSampler` or .. i'm not sure, naming is hard.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] FrankChen021 commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
FrankChen021 commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-858635431
The new algorithm implementation looks good to me. But it drops the `percentOfSegmentsToConsider` parameter, I have no idea whether it should be kept. What do you think ? @jihoonson
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] asdf2014 merged pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
asdf2014 merged pull request #11257:
URL: https://github.com/apache/druid/pull/11257
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] capistrant commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
capistrant commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-858678690
I haven't read the code yet, just reading comments and responding to my tag from @a2l007 ... I do think it is very helpful to keep the `percentOfSegmentsToConsider` value. Our largest cluster has over 2MM segments with replication and slashing that value down has allowed us to cut a large chunk out of coordination time in this phase by short circuiting at what we have deemed to be an acceptable point in the iteration. I'll try to read through full PR today and update my comment
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] a2l007 commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
a2l007 commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r649229965
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
+ )
+ {
+ List<BalancerSegmentHolder> holders = new ArrayList<>(k);
+ int numSoFar = 0;
+
+ for (ServerHolder server : serverHolders) {
+ if (!server.getServer().getType().isSegmentReplicationTarget()) {
+ // if the server only handles broadcast segments (which don't need to be rebalanced), we have nothing to do
+ continue;
+ }
+
+ for (DataSegment segment : server.getServer().iterateAllSegments()) {
+ if (broadcastDatasources.contains(segment.getDataSource())) {
+ // we don't need to rebalance segments that were assigned via broadcast rules
+ continue;
+ }
+
+ if (numSoFar < k) {
+ holders.add(new BalancerSegmentHolder(server.getServer(), segment));
+ numSoFar++;
+ continue;
+ }
+ int randNum = ThreadLocalRandom.current().nextInt(numSoFar + 1);
+ if (randNum < k) {
+ holders.set(randNum, new BalancerSegmentHolder(server.getServer(), segment));
+ }
Review comment:
Echoing what @clintropolis suggested, it would be useful to have a new dynamic config to toggle between the old and new implementations. We could keep the new config for a couple of releases which would be enough time for operators to test it out and later on we could do away with the config property.
Could we also consider including `percentOfSegmentsToConsider` as part of this new approach? This is a useful knob especially for larger clusters.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r663619016
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/duty/BalanceSegments.java
##########
@@ -180,22 +181,29 @@ private void balanceTier(
int maxSegmentsToMove
)
{
+ if (maxSegmentsToMove <= 0) {
+ return new Pair<>(0, 0);
+ }
+
final BalancerStrategy strategy = params.getBalancerStrategy();
final int maxIterations = 2 * maxSegmentsToMove;
final int maxToLoad = params.getCoordinatorDynamicConfig().getMaxSegmentsInNodeLoadingQueue();
int moved = 0, unmoved = 0;
+ Iterator<BalancerSegmentHolder> segmetnsToMove = strategy.pickSegmentsToMove(
Review comment:
updated
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] capistrant edited a comment on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
capistrant edited a comment on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-858678690
I haven't read the code yet, just reading comments and responding to my tag from @a2l007 ... I do think it is very helpful to keep the `percentOfSegmentsToConsider` value. Our largest cluster has over 2MM segments with replication and slashing that value down has allowed us to cut a large chunk out of coordination time in this phase by short circuiting at what we have deemed to be an acceptable point in the iteration. I'll try to read through full PR today and update my comment.
Also this patch and the issue it is resolving would help with the underlying performance issues of the design here. My patch to short circuit was more of a bandaid. This seems like a design improvement that visits the root issue of this method being invoked more than needed! So maybe my tuning config is less helpful once this PR is in? Or maybe it is still useful and both together would be great?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-873774263
> I haven't read the code yet, just reading comments and responding to my tag from @a2l007 ... I do think it is very helpful to keep the `percentOfSegmentsToConsider` value. Our largest cluster has over 2MM segments with replication and slashing that value down has allowed us to cut a large chunk out of coordination time in this phase by short circuiting at what we have deemed to be an acceptable point in the iteration. I'll try to read through full PR today and update my comment.
>
> Also this patch and the issue it is resolving would help with the underlying performance issues of the design here. My patch to short circuit was more of a bandaid. This seems like a design improvement that visits the root issue of this method being invoked more than needed! So maybe my tuning config is less helpful once this PR is in? Or maybe it is still useful and both together would be great?
Hi @capistrant, thanks for your comment. It's great to know that we both have tried to solve this issue.
Ideally, this patch should be able to solve this issue fundamentally while it makes sense to me to evolve gradually in engineering. So, I agree to retain the `percentOfSegmentsToConsider` improvement and add an another parameter `useBatchedSegmentSampler` to enable to the new improvement as suggested by previous comments.
And it'll be great if you can help to review this PR!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] FrankChen021 commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
FrankChen021 commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-889599447
@yuanlihan Great work. Code change LGTM. For benchmark, could you add a combination of `50percentOfSegmentsToConsiderPerMove` and `useBatchedSegmentSampler` so that we could see how `percentOfSegmentsToConsider` improves the performance based on the new algorithm. This benchmark could help us to determine whether we need to keep `percentOfSegmentsToConsider` in future.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] capistrant commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
capistrant commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-902929050
> > It would be useful to add a benchmark for this code if possible to show the difference of the new implementation, maybe here: https://github.com/apache/druid/tree/master/benchmarks/src/test/java/org/apache/druid/server/coordinator
>
> Here's the benchmark data(or see [JMH result graph](https://jmh.morethan.io/?gist=577d9e192ca1f191309a82520d1d50e6))
>
> ```
> Benchmark (maxSegmentsToMove) (mode) (numberOfSegments) Mode Cnt Score Error Units
> BalancerStrategyBenchmark.pickSegmentsToMove 10 default 10000 avgt 10 2.402 ± 0.019 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 default 100000 avgt 10 41.890 ± 2.326 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 default 1000000 avgt 10 620.377 ± 14.541 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 1.475 ± 0.008 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 15.383 ± 0.342 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 310.409 ± 18.073 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 10000 avgt 10 0.234 ± 0.003 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 100000 avgt 10 3.944 ± 0.199 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 1000000 avgt 10 59.548 ± 2.327 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 default 10000 avgt 10 22.205 ± 0.105 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 default 100000 avgt 10 392.765 ± 23.001 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 default 1000000 avgt 10 5759.416 ± 171.515 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 13.925 ± 0.026 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 181.052 ± 2.517 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 2900.901 ± 81.967 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 10000 avgt 10 0.276 ± 0.001 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 100000 avgt 10 4.330 ± 0.037 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 1000000 avgt 10 56.426 ± 1.235 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 10000 avgt 10 222.513 ± 0.559 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 100000 avgt 10 4369.863 ± 62.496 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 1000000 avgt 10 57107.843 ± 1082.160 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 136.567 ± 0.301 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 1766.142 ± 12.927 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 28437.935 ± 257.949 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 10000 avgt 10 0.303 ± 0.002 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 100000 avgt 10 4.247 ± 0.057 ms/op
> BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 1000000 avgt 10 59.161 ± 1.597 ms/op
> ```
wow, awesome benchmark results! So sorry that I didn't participate more in the review of this PR, I hav been pulled away from Druid more than I'd like lately. Regardless, I see that y'all had it more than covered! So excited to start using this 💯
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r663621289
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
+ )
+ {
+ List<BalancerSegmentHolder> holders = new ArrayList<>(k);
+ int numSoFar = 0;
+
+ for (ServerHolder server : serverHolders) {
+ if (!server.getServer().getType().isSegmentReplicationTarget()) {
+ // if the server only handles broadcast segments (which don't need to be rebalanced), we have nothing to do
+ continue;
+ }
+
+ for (DataSegment segment : server.getServer().iterateAllSegments()) {
+ if (broadcastDatasources.contains(segment.getDataSource())) {
+ // we don't need to rebalance segments that were assigned via broadcast rules
+ continue;
+ }
+
+ if (numSoFar < k) {
+ holders.add(new BalancerSegmentHolder(server.getServer(), segment));
+ numSoFar++;
+ continue;
+ }
+ int randNum = ThreadLocalRandom.current().nextInt(numSoFar + 1);
+ if (randNum < k) {
+ holders.set(randNum, new BalancerSegmentHolder(server.getServer(), segment));
+ }
Review comment:
It makes sense to me to retain the `percentOfSegmentsToConsider` and add an another dynamic parameter `useBatchedSegmentSampler` to enable the new improvement. In this way, the changing will be less aggressive.
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/BalancerStrategy.java
##########
@@ -71,13 +71,60 @@
* @return {@link BalancerSegmentHolder} containing segment to move and server it currently resides on, or null if
* there are no segments to pick from (i. e. all provided serverHolders are empty).
*/
+ @Deprecated
Review comment:
updated
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r663620645
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
Review comment:
It makes sense to me to retain the `percentOfSegmentsToConsider` and add an another dynamic parameter `useBatchedSegmentSampler` to enable the new improvement. In this way, the changing will be less aggressive.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-873776301
> It would be useful to add a benchmark for this code if possible to show the difference of the new implementation, maybe here: https://github.com/apache/druid/tree/master/benchmarks/src/test/java/org/apache/druid/server/coordinator
Here's the benchmark data(or see [JMH result graph](https://jmh.morethan.io/?gist=577d9e192ca1f191309a82520d1d50e6))
```
Benchmark (maxSegmentsToMove) (mode) (numberOfSegments) Mode Cnt Score Error Units
BalancerStrategyBenchmark.pickSegmentsToMove 10 default 10000 avgt 10 2.402 ± 0.019 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 default 100000 avgt 10 41.890 ± 2.326 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 default 1000000 avgt 10 620.377 ± 14.541 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 1.475 ± 0.008 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 15.383 ± 0.342 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 310.409 ± 18.073 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 10000 avgt 10 0.234 ± 0.003 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 100000 avgt 10 3.944 ± 0.199 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 10 useBatchedSegmentSampler 1000000 avgt 10 59.548 ± 2.327 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 default 10000 avgt 10 22.205 ± 0.105 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 default 100000 avgt 10 392.765 ± 23.001 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 default 1000000 avgt 10 5759.416 ± 171.515 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 13.925 ± 0.026 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 181.052 ± 2.517 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 2900.901 ± 81.967 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 10000 avgt 10 0.276 ± 0.001 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 100000 avgt 10 4.330 ± 0.037 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 100 useBatchedSegmentSampler 1000000 avgt 10 56.426 ± 1.235 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 10000 avgt 10 222.513 ± 0.559 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 100000 avgt 10 4369.863 ± 62.496 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 default 1000000 avgt 10 57107.843 ± 1082.160 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 10000 avgt 10 136.567 ± 0.301 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 100000 avgt 10 1766.142 ± 12.927 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 50percentOfSegmentsToConsiderPerMove 1000000 avgt 10 28437.935 ± 257.949 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 10000 avgt 10 0.303 ± 0.002 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 100000 avgt 10 4.247 ± 0.057 ms/op
BalancerStrategyBenchmark.pickSegmentsToMove 1000 useBatchedSegmentSampler 1000000 avgt 10 59.161 ± 1.597 ms/op
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] a2l007 commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
a2l007 commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-889604733
Thanks for this patch. Looking forward to using this in our clusters. It would be nice if you could add a few lines in the doc regarding a recommended value for `useBatchedSegmentSampler`. Cluster operators could use this value as a starting point to see how it impacts their cluster. This is not a blocker for this PR, but can be done as a followup as well.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] FrankChen021 commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
FrankChen021 commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r649194445
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/ReservoirSegmentSampler.java
##########
@@ -31,6 +32,42 @@
private static final EmittingLogger log = new EmittingLogger(ReservoirSegmentSampler.class);
+ static List<BalancerSegmentHolder> getRandomBalancerSegmentHolders(
+ final List<ServerHolder> serverHolders,
+ Set<String> broadcastDatasources,
+ int k
+ )
+ {
+ List<BalancerSegmentHolder> holders = new ArrayList<>(k);
+ int numSoFar = 0;
+
+ for (ServerHolder server : serverHolders) {
+ if (!server.getServer().getType().isSegmentReplicationTarget()) {
+ // if the server only handles broadcast segments (which don't need to be rebalanced), we have nothing to do
+ continue;
+ }
+
+ for (DataSegment segment : server.getServer().iterateAllSegments()) {
+ if (broadcastDatasources.contains(segment.getDataSource())) {
+ // we don't need to rebalance segments that were assigned via broadcast rules
+ continue;
+ }
+
+ if (numSoFar < k) {
+ holders.add(new BalancerSegmentHolder(server.getServer(), segment));
+ numSoFar++;
+ continue;
+ }
+ int randNum = ThreadLocalRandom.current().nextInt(numSoFar + 1);
+ if (randNum < k) {
+ holders.set(randNum, new BalancerSegmentHolder(server.getServer(), segment));
+ }
Review comment:
Random picking here is a standard implementation of a reservoir sampling algorithm. It makes all segments have the same probability to be selected. The original code also uses this trick, so no need to worry :-)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] jihoonson commented on a change in pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
jihoonson commented on a change in pull request #11257:
URL: https://github.com/apache/druid/pull/11257#discussion_r678820747
##########
File path: server/src/main/java/org/apache/druid/server/coordinator/BalancerStrategy.java
##########
@@ -55,28 +55,90 @@
ServerHolder findNewSegmentHomeReplicator(DataSegment proposalSegment, List<ServerHolder> serverHolders);
/**
- * Pick the best segment to move from one of the supplied set of servers according to the balancing strategy.
+ * Pick the best segments to move from one of the supplied set of servers according to the balancing strategy.
+ *
* @param serverHolders set of historicals to consider for moving segments
* @param broadcastDatasources Datasources that contain segments which were loaded via broadcast rules.
* Balancing strategies should avoid rebalancing segments for such datasources, since
* they should be loaded on all servers anyway.
* NOTE: this should really be handled on a per-segment basis, to properly support
* the interval or period-based broadcast rules. For simplicity of the initial
* implementation, only forever broadcast rules are supported.
+ * @param reservoirSize the reservoir size maintained by the Reservoir Sampling algorithm.
* @param percentOfSegmentsToConsider The percentage of the total number of segments that we will consider when
* choosing which segment to move. {@link CoordinatorDynamicConfig} defines a
* config percentOfSegmentsToConsiderPerMove that will be used as an argument
* for implementations of this method.
- *
- * @return {@link BalancerSegmentHolder} containing segment to move and server it currently resides on, or null if
- * there are no segments to pick from (i. e. all provided serverHolders are empty).
+ * @return Iterator for set of {@link BalancerSegmentHolder} containing segment to move and server they currently
+ * reside on, or empty if there are no segments to pick from (i. e. all provided serverHolders are empty).
*/
- @Nullable
- BalancerSegmentHolder pickSegmentToMove(
+ default Iterator<BalancerSegmentHolder> pickSegmentsToMove(
List<ServerHolder> serverHolders,
Set<String> broadcastDatasources,
+ int reservoirSize,
double percentOfSegmentsToConsider
- );
+ )
+ {
+ if (reservoirSize > 1) {
+ return new Iterator<BalancerSegmentHolder>()
+ {
+ private Iterator<BalancerSegmentHolder> it = sample();
+
+ private Iterator<BalancerSegmentHolder> sample()
+ {
+ return ReservoirSegmentSampler.getRandomBalancerSegmentHolders(
+ serverHolders,
+ broadcastDatasources,
+ reservoirSize
+ ).iterator();
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ if (it.hasNext()) {
+ return true;
+ }
+ it = sample();
+ return it.hasNext();
+ }
+
+ @Override
+ public BalancerSegmentHolder next()
+ {
+ return it.next();
+ }
+ };
+ }
+
+ return new Iterator<BalancerSegmentHolder>()
+ {
+ private BalancerSegmentHolder next = sample();
+
+ private BalancerSegmentHolder sample()
+ {
+ return ReservoirSegmentSampler.getRandomBalancerSegmentHolder(
+ serverHolders,
+ broadcastDatasources,
+ percentOfSegmentsToConsider
+ );
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ return next != null;
+ }
+
+ @Override
+ public BalancerSegmentHolder next()
+ {
Review comment:
nit:
```java
if (!hasNext()) {
throw new NoSuchElementException();
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] jihoonson commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
jihoonson commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-889588976
@FrankChen021 @a2l007 @clintropolis do you have more comments?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] a2l007 commented on pull request #11257: Reduce method invocation of reservoir sampling
Posted by GitBox <gi...@apache.org>.
a2l007 commented on pull request #11257:
URL: https://github.com/apache/druid/pull/11257#issuecomment-858671961
It would be useful to incorporate `percentOfSegmentsToConsider` into the new algorithm as it is relevant in larger clusters. It could help the balance segments duty perform even better if say only 50% of the total segments are considered for the move. @capistrant What do you think about this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org