apache
Optimize isOvershadowed when there is a unique minor version for an interval
The coordinator tries to poll segments every minute (or based on the configured periodicPollDelay) In each cycle, the DataSourcesSnapshot
- Polls the database for all used segments
- Create a segment timeline for each of the datasources
- Determine all the overshadowed segments
The third step to compute overshadowed segments is currently based on calling isOvershadowed on each segment individually. The complexity for this operation is O(n ^ 2) for each interval with n segments.
This can lead to coordinator polls happening infrequently, which causes a delay in segments being discovered after having been committed, which leads to stale data and slow handoffs etc.
Optimize the isOvershadowed method when there there is a single value of minorVersion across all segments in an interval (When segment locking is not used, for example) to reduce the complexity to O(n) in such cases. This is a simple optimization that may be useful for most large clusters since segment locking is seldom used.
BENCHMARKS:
VersionedIntervalTimelineBenchmark#benchIsOvershadowedTotal
Benchmarks were run with 1000 / 10000 segments per interval with Monthly granularity over a year.
Existing code:
Benchmark (numInitialRootGenSegmentsPerInterval) (numNonRootGenerations) (segmentGranularity) (useSegmentLock) Mode Cnt Score Error Units
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 1 MONTH false thrpt 3 0.347 ± 0.030 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 1 MONTH true thrpt 3 0.366 ± 0.033 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 2 MONTH false thrpt 3 0.343 ± 0.015 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 2 MONTH true thrpt 3 0.365 ± 0.033 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 1 MONTH false thrpt 3 0.004 ± 0.001 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 1 MONTH true thrpt 3 0.004 ± 0.001 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 2 MONTH false thrpt 3 0.003 ± 0.001 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 2 MONTH true thrpt 3 0.004 ± 0.001 ops/s
With this patch:
Benchmark (numInitialRootGenSegmentsPerInterval) (numNonRootGenerations) (segmentGranularity) (useSegmentLock) Mode Cnt Score Error Units
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 1 MONTH false thrpt 3 82.062 ± 5.082 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 1 MONTH true thrpt 3 80.937 ± 33.370 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 2 MONTH false thrpt 3 59.582 ± 6.060 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 1000 2 MONTH true thrpt 3 59.314 ± 9.134 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 1 MONTH false thrpt 3 8.165 ± 0.675 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 1 MONTH true thrpt 3 8.193 ± 0.431 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 2 MONTH false thrpt 3 5.831 ± 1.910 ops/s
VersionedIntervalTimelineBenchmark.benchIsOvershadowedTotal 10000 2 MONTH true thrpt 3 5.927 ± 0.421 ops/s
TODO:
- Add tests to ensure correctness of the new method
This PR has:
- [x] been self-reviewed.
- [ ] using the concurrency checklist (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.
- [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
- [x] 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 is met.
- [ ] added integration tests.
- [ ] been tested in a test Druid cluster.
@AmatyaAvadhanula , looking at the benchmarking, is it correct to conclude that the new logic is faster even when useSegmentLock = true (i.e. minor versions exist)? But how can that be the case?
Is it because the object.getMinorVersion turns out to be equal to the maxMinorVersion?
So the performance would be worst only when we have multiple minor versions?
Another point, is the default minor version of -1 safe?
What is the default value of minor version for any segment when it actually has no minor version? I should assume that the value would be 0.
On a cluster with 600k active segments, this patch reduce the time to build timeline from 160,000ms to 2,000ms. On a cluster with ~7 million active segments, this patch reduce the time to build timeline from 850,000ms to 35,000ms. We have some datasources with 100K++ segments.
