rbankar7 opened a new pull request, #19944:
URL: https://github.com/apache/druid/pull/19944
### Description
The default `roundRobin` segment distribution creates a skew in how many
segments each historical must scan to answer scan/export endpoint calls that
target a narrow, recent time range. Segments covering the same interval can
land unevenly across historicals, so some historicals do disproportionately
more work for such queries.
This PR adds a new `intervalAware` balancer strategy that spreads segments
covering the same time interval as evenly as possible across the historicals in
a tier.
#### Added `IntervalAwareBalancerStrategy`
For a segment being placed, moved, or dropped, the "cost" of a server is the
number of segments already projected on that server for the segment's interval.
The least-loaded-for-this-interval server is preferred.
- **O(1) per-server cost.** The count comes from the per-interval tallies
already maintained in `SegmentCountsPerInterval` (via
`ServerHolder.getProjectedSegmentCounts()`), so each placement is O(numServers)
with an O(1) lookup per server, rather than the O(segmentsPerServer) pairwise
computation of `cost`. This keeps the coordinator duty-cycle time low.
- **Interval-scoped, not decay-based.** Unlike `cost`, it does not model
query-time-decay across the whole retention window; it only equalises the
per-interval segment count, which is what matters for workloads that query a
narrow, recent time range.
- **Tie-breaking.** Ties are broken randomly — shuffle-then-stable-sort for
load/drop ordering, and reservoir sampling over the servers tied at the minimum
count for moves — so servers holding an equal count for an interval are not
always picked in the same order (which would otherwise skew distribution over
repeated runs).
- **Oscillation avoidance.** A move is only made when it strictly reduces
the maximum per-interval count (the destination, after gaining the segment,
would hold fewer segments for the interval than the source currently does).
This avoids pointless moves between servers that differ by a single segment.
#### Added the `perDatasource` option
The count can be scoped two ways via the `perDatasource` flag on the factory:
- `perDatasource=true` (default): counts only segments of the **same
datasource** for the interval. Each datasource is balanced independently —
optimal when a query targets a single datasource.
- `perDatasource=false`: counts segments of **all datasources** for the
interval — optimal when a query unions multiple datasources covering the same
time range.
#### Registered the `intervalAware` strategy
Added the `intervalAware` subtype to `BalancerStrategyFactory` so it can be
selected via the coordinator dynamic config:
```json
{ "strategy": "intervalAware" }
{ "strategy": "intervalAware", "perDatasource": false }
```
This strategy is only consulted for initial placement when round-robin
assignment is disabled (`useRoundRobinSegmentAssignment=false`, which also
requires `smartSegmentLoading=false`). It is always used for balancing moves.
#### Release note
Added a new `intervalAware` balancer strategy that distributes the segments
of an interval evenly across the historicals in a tier, reducing per-historical
scan skew for workloads that query a narrow, recent time range. It can be
enabled by setting the balancer `strategy` to `intervalAware` in the
coordinator dynamic config, with an optional `perDatasource` flag (default
`true`) to control whether the per-interval count is scoped to a single
datasource or across all datasources.
<hr>
##### Key changed/added classes in this PR
* `IntervalAwareBalancerStrategy`
* `IntervalAwareBalancerStrategyFactory`
* `BalancerStrategyFactory`
<hr>
This PR has:
- [ ] been self-reviewed.
- [ ] using the [concurrency
checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md)
(Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] a release note entry in the PR description.
- [ ] 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.
- [ ] 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.
- [ ] 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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
