Add ramping up weighted round robin strategy

[minwoox]

Motivation:
Related: #1757
It will be nice if we have a strategy EndpointSelectionStrategy which increases weight gradually
for the newly added Endpoints.

Modifications:

• Add EndpointSelectionStrategy.rampingUp() and builderForRampingUp()
  • The strategy increase the weights of newly added Endpoints using EndpointWeightTransition
  • The weight is ramped totalSteps times every rampingUpInterval.
  • Endpoints added within the same updatingTaskWindow are updated together.

Result:

• Close A new load-balancing EndpointSelectionStrategy which increases weight gradually #1757
• You can now use the EndpointSelectionStrategy which increases weight gradually
  for the newly added Endpoints.

[codecov]

Codecov Report

Merging #3217 (2c7189a) into master (a4724be) will decrease coverage by 0.00%.
The diff coverage is 77.89%.

@@             Coverage Diff              @@
##             master    #3217      +/-   ##
============================================
- Coverage     74.06%   74.05%   -0.01%     
- Complexity    13008    13140     +132     
============================================
  Files          1136     1146      +10     
  Lines         49276    50025     +749     
  Branches       6256     6394     +138     
============================================
+ Hits          36496    37047     +551     
- Misses         9566     9717     +151     
- Partials       3214     3261      +47     

Impacted Files	Coverage Δ	Complexity Δ
...ria/client/endpoint/EndpointSelectionStrategy.java	40.00% <0.00%> (-26.67%)	2.00 <0.00> (ø)
...lient/endpoint/WeightRampingUpStrategyBuilder.java	0.00% <0.00%> (ø)	0.00 <0.00> (?)
...meria/client/endpoint/WeightRampingUpStrategy.java	86.05% <86.05%> (ø)	3.00 <3.00> (?)
...nt/WeightedRandomDistributionEndpointSelector.java	88.00% <88.00%> (ø)	13.00 <13.00> (?)
...eria/client/endpoint/EndpointWeightTransition.java	100.00% <100.00%> (ø)	2.00 <2.00> (?)
...ia/client/endpoint/WeightedRoundRobinStrategy.java	98.59% <100.00%> (ø)	2.00 <0.00> (ø)
...inecorp/armeria/common/ClosedSessionException.java	54.54% <0.00%> (-18.19%)	5.00% <0.00%> (-1.00%)
...orp/armeria/common/AbstractHttpHeadersBuilder.java	52.63% <0.00%> (-14.04%)	8.00% <0.00%> (ø%)
...om/linecorp/armeria/common/DefaultHttpHeaders.java	78.26% <0.00%> (-4.10%)	9.00% <0.00%> (+1.00%)	⬇️
...a/com/linecorp/armeria/common/HttpHeadersBase.java	79.08% <0.00%> (-3.56%)	53.00% <0.00%> (+1.00%)	⬇️
... and 40 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 a4724be...b336112. Read the comment docs.

[anuraaga]

By the way, why does this class have the ability to remove entries but not add them? Seems assymetrical.

[minwoox]

Yeah, this is an asymmetric algorithm. 😉
Each entry is removed from currentEntries when the counter of each endpoint reached the weight.
And the removed entries are added back to the currentEntries when all entries are removed.
This guarantees that the endpoint whose weight is very low is always selected when selectEndpoint() is called by totalWeight times.

[anuraaga]

Just wondering, is the removal easier to reason about than making entries as unavailable? Something like this? Not sure if this works exactly but something along these lines

if (!entry.isFull()) {
  return selected;
} else if (entry.isUnavailable()) {
  continue;
}
entry.markUnavailable();
currentTotalWeight.decrementAndGet(entry.endpoint().weight());

[minwoox]

Hm, if we don't remove the entry, isn't there chances that the endpoint with low weight (e.g. 1) is not selected even after one turn(totalWeigth) is passed?
We use a random number to select an endpoint so removing entries will guarantee that the endpoint is selected evenly with its weight. 🤔

[anuraaga]

Well I figured an unavailable marker should be equivalent to removal, just without having to manage the list and maybe easier to mutate it atomically. if (unavailable) continue; feels equivalent semantically to removal. But maybe missing some corner case.

[minwoox]

I now realized the logic I implemented was not working as I expected. 😅 Maybe that's the reason that I got confused.
The current logic is slanted because the entry, which is next to the endpoint whose weight is large, will get much chance to get selected after the endpoint is full.
So I have to recalculate the lowerBound after the entry is removed but I forgot about it. 😅
On the other hand, I'm a bit doubtful about recalculation. Let me think about this. 🤔

[minwoox]

@anuraaga I updated the logic a bit. PTAL. 🙇‍♂️

[minwoox]

@trustin, @anuraaga and @ikhoon Addressed all comments. PTAL 🙇

[anuraaga]

Left some possible javadoc suggestions

[anuraaga]

Sets the ScheduledExecutorService to use to execute tasks for computing new weights.

By the way is it safe for this to be multi threaded or should it accept a netty type instead?

[minwoox]

Oh, it should be single-threaded. Let me use EventExecutor. Thanks!

[anuraaga]

numberSteps maybe better, its not so much a total.

[minwoox]

That's a good suggestion. 👍

[minwoox]

All fixed. PTAL. 😉

[ikhoon]

Left some minor nits.

[ikhoon]

Many users have been waiting for this feature. You made it! 🙇‍♂️

[trustin]

Shall we add @UnstableApi to all new public classes and methods, just in case we'll have to update the API?

[trustin]

Thanks a lot for your patience, @minwoox 🙇

[trustin]

🎉🎉🎉

[0x1306e6d]

Thanks!!!!!! 🎉🎉🎉

[minwoox]

Thanks a lot, reviewers!