Reduce method invocation of reservoir sampling

[yuanlihan]

Motivation

The periodic task of the Coordinator service could be slow in a large cluster. The periodic task consists of several serial subtasks. According to the profiling result, the segment balance task has some performance issue. I found that the root cause is that the current implementation invokes the sampling method too many times. We can reduce the number of method invocations by increasing the sample size in each invocation.

Proposed changes

Adding a new Reservoir Sampling method to sample K elements each time instead of only one element each time.
A default method pickSegmentsToMove will be added to interface BalancerStrategy to pick K segments to move in a single method invocation.

Rationale

The current implementation picks up only one segment each time iterating all segments. When there are a lot segments need to be rebalanced or need to be decommissioned, the load balance calculation will be really slow. By picking up K segments each time will significantly reduce the number of iteration and thus speed up the process.

Operational impact

There will be no impact in operation

Test plan (optional)

Ensure test coverage and test it in test cluster

[jihoonson]

Adding a new Reservoir Sampling method to sample K elements each time instead of only one element each time.

I'm not sure how this can improve the performance. Does the new sampling method need to loop to sample K segments anyway? I guess I'm probably missing something. Would you please add more details on the proposed changes?

[yuanlihan]

Adding a new Reservoir Sampling method to sample K elements each time instead of only one element each time.

I'm not sure how this can improve the performance. Does the new sampling method need to loop to sample K segments anyway? I guess I'm probably missing something. Would you please add more details on the proposed changes?

Thanks for having a look at this. The default implementation samples only one segment in an iteration of all segments. Let's assume that:

• the list of server holders contains 1 million segments
• 1000 segments need to be picked up from these server holders

Then the current implementation needs to call the sampling method 1000 times and each time needs to iterate 1 million segments.
I found that the Reservoir Sampling actually can sample K elements a single pass over the items. So in this case, the new method can sample 1000 segments in a method invocation, which means it'll iterate 1 million segments only once.

[jihoonson]

@yuanlihan thanks. I think I was confused about what is expensive. I think what is expensive is not the sample method invocation, but is the algorithm that calls the sample method over again. I looked over your PR and understand what you want now. But I want to think about it more because we have no test coverage on the long term effect of this change. It would be great if you can provide some long term test results.

[yuanlihan]

@jihoonson

But I want to think about it more because we have no test coverage on the long term effect of this change.

As this change will be enabled by default, I understand your concern. I tried to confirm the correctness based on the following points:

• the set of segments in each server holder is immutable in each cycle
• the output of getting k segments in a single pass is roughly equal to the result of getting k segments in k passes(1 segment per pass)

It would be great if you can provide some long term test results.

Actually I have shipped this change into our on-premise cluster(which contains millions of segments) in Jan 2021 and it works well. In the past several months, the default cost-based balancer manages segment loading among 5 different historical tiers well. During this period, we have expanded the cluster by adding new historical nodes and decommissioned historical nodes for server maintenance. It seems hard to provide visual long term function testing result about this change.

[jihoonson]

@yuanlihan thank you for adding more details. I think the basic idea makes sense since every segment has the same probability of being picked up. I will review your PR soon.