Optimize RoundRobinLoadBalance by gudegg · Pull Request #2586 · apache/dubbo

gudegg · 2018-09-30T03:10:02Z

What is the purpose of the change

fix:#2578

Brief changelog

Optimize RoundRobinLoadBalance

Verifying this change

Follow this checklist to help us incorporate your contribution quickly and easily:

Make sure there is a GITHUB_issue filed for the change (usually before you start working on it). Trivial changes like typos do not require a GITHUB issue. Your pull request should address just this issue, without pulling in other changes - one PR resolves one issue.
Format the pull request title like [Dubbo-XXX] Fix UnknownException when host config not exist #XXX. Each commit in the pull request should have a meaningful subject line and body.
Write a pull request description that is detailed enough to understand what the pull request does, how, and why.
Write necessary unit-test to verify your logic correction, more mock a little better when cross module dependency exist. If the new feature or significant change is committed, please remember to add integration-test in test module.
Run mvn clean install -DskipTests & mvn clean test-compile failsafe:integration-test to make sure unit-test and integration-test pass.
If this contribution is large, please follow the Software Donation Guide.

codecov-io · 2018-09-30T04:01:20Z

Codecov Report

Merging #2586 into master will decrease coverage by 0.08%.
The diff coverage is 100%.

@@             Coverage Diff              @@
##             master    #2586      +/-   ##
============================================
- Coverage      55.2%   55.11%   -0.09%     
+ Complexity     5298     5291       -7     
============================================
  Files           573      573              
  Lines         25538    25529       -9     
  Branches       4531     4530       -1     
============================================
- Hits          14097    14070      -27     
- Misses         9341     9355      +14     
- Partials       2100     2104       +4

Impacted Files	Coverage Δ	Complexity Δ
...rpc/cluster/loadbalance/RoundRobinLoadBalance.java	`93.75% <100%> (+5.94%)`	`8 <0> (-1)`	⬇️
...he/dubbo/remoting/transport/netty/NettyClient.java	`72.88% <0%> (-10.17%)`	`12% <0%> (-1%)`
...ubbo/rpc/protocol/dubbo/ChannelWrappedInvoker.java	`41.66% <0%> (-8.34%)`	`3% <0%> (ø)`
...apache/dubbo/rpc/protocol/dubbo/FutureAdapter.java	`58.06% <0%> (-6.46%)`	`3% <0%> (ø)`
...org/apache/dubbo/rpc/filter/ActiveLimitFilter.java	`83.33% <0%> (-5.56%)`	`6% <0%> (-1%)`
.../apache/dubbo/rpc/protocol/dubbo/DubboInvoker.java	`68.33% <0%> (-3.34%)`	`11% <0%> (ø)`
...he/dubbo/registry/multicast/MulticastRegistry.java	`55.6% <0%> (-1.73%)`	`35% <0%> (-3%)`
...bo/remoting/transport/netty/NettyCodecAdapter.java	`53.12% <0%> (-1.57%)`	`3% <0%> (ø)`
...dubbo/rpc/protocol/dubbo/CallbackServiceCodec.java	`77.2% <0%> (-1.48%)`	`29% <0%> (ø)`
...a/org/apache/dubbo/monitor/dubbo/DubboMonitor.java	`89.71% <0%> (-0.94%)`	`15% <0%> (-1%)`
... and 2 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 9b7284f...58290c4. Read the comment docs.

carryxyh · 2018-09-30T04:10:33Z

@kimmking
Have a look. :)

kimmking · 2018-09-30T04:40:45Z

dubbo-cluster/src/main/java/org/apache/dubbo/rpc/cluster/loadbalance/RoundRobinLoadBalance.java

        }
        // Round robin
-        return invokers.get(sequence.incrementAndGet() % length);
+        return invokers.get(sequence.getAndIncrement() % length);


kimmking · 2018-09-30T08:36:18Z

@carryxyh it's okay and works well.
I send a mail to describe it clear and shortly.
I will be merge it soon and then add some test cases for the new algorithm with performance case.

gudegg · 2018-10-05T04:56:00Z

@kimmking Have a look! I made a little change.
algorithm: Only need invokers#size loop at most.

ralf0131 · 2018-10-05T14:40:08Z

dubbo-cluster/src/main/java/org/apache/dubbo/rpc/cluster/loadbalance/RoundRobinLoadBalance.java

        int minWeight = Integer.MAX_VALUE; // The minimum weight
-        final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
-        int weightSum = 0;
+        final List<Invoker<T>> invokerToWeightList = new ArrayList<>();


The name invokerToWeightList can be improved. I think weightedInvokerList or nonZeroWeightedInvokers should be better. :)

ralf0131 · 2018-10-05T14:41:56Z

This pull request looks good to me. Nice work!
The time complexity is O(n), where n is the number of invokers, which is a significant improvement to the previous one, which is O(n*w), where n is the number of invokers, and w is the max weight of the invokers.
I'd prefer to have more unit tests for this algorithm.

kimmking · 2018-10-06T02:26:10Z

This pull request looks good to me. Nice work!
The time complexity is O(n), where n is the number of invokers, which is a significant improvement to the previous one, which is O(n*w), where n is the number of invokers, and w is the max weight of the invokers.
I'd prefer to have more unit tests for this algorithm.

great, I also writed some UT for it. we can PR our UTs after merging it.

detailyang · 2018-10-06T08:16:05Z

dubbo-cluster/src/main/java/org/apache/dubbo/rpc/cluster/loadbalance/RoundRobinLoadBalance.java

+                int currentWeight;
+                if (index == 0) {
+                    currentWeight = sequence.incrementAndGet() % maxWeight;
+                }else {


space need:)

Gude added 2 commits September 30, 2018 10:54

Optimize RoundRobinLoadBalance

a6448fe

Optimize RoundRobinLoadBalance

237ff2b

carryxyh assigned kimmking Sep 30, 2018

carryxyh requested a review from kimmking September 30, 2018 04:10

kimmking reviewed Sep 30, 2018

View reviewed changes

Optimize RoundRobinLoadBalance

5d4289d

ralf0131 reviewed Oct 5, 2018

View reviewed changes

name improvement

f33359b

detailyang reviewed Oct 6, 2018

View reviewed changes

format

58290c4

kimmking merged commit adb5b0e into apache:master Oct 11, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Optimize RoundRobinLoadBalance#2586

Optimize RoundRobinLoadBalance#2586
kimmking merged 5 commits intoapache:masterfrom
gudegg:opt_roundrobin

gudegg commented Sep 30, 2018 •

edited

Loading

Uh oh!

codecov-io commented Sep 30, 2018 •

edited

Loading

Uh oh!

carryxyh commented Sep 30, 2018

Uh oh!

kimmking Sep 30, 2018

Uh oh!

kimmking commented Sep 30, 2018

Uh oh!

gudegg commented Oct 5, 2018

Uh oh!

ralf0131 Oct 5, 2018

Uh oh!

ralf0131 commented Oct 5, 2018

Uh oh!

kimmking commented Oct 6, 2018

Uh oh!

detailyang Oct 6, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Conversation

gudegg commented Sep 30, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What is the purpose of the change

Brief changelog

Verifying this change

Uh oh!

codecov-io commented Sep 30, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

carryxyh commented Sep 30, 2018

Uh oh!

kimmking Sep 30, 2018

Choose a reason for hiding this comment

Uh oh!

kimmking commented Sep 30, 2018

Uh oh!

gudegg commented Oct 5, 2018

Uh oh!

ralf0131 Oct 5, 2018

Choose a reason for hiding this comment

Uh oh!

ralf0131 commented Oct 5, 2018

Uh oh!

kimmking commented Oct 6, 2018

Uh oh!

detailyang Oct 6, 2018

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

gudegg commented Sep 30, 2018 •

edited

Loading

codecov-io commented Sep 30, 2018 •

edited

Loading