VersionedIntervalTimeline.isOvershadowed is very slow when processing many segments

[viongpanzi]

Affected Version

0.18.1

Description

There are millions segments in our Druid cluster. Coordinator is very slow when processing duties. After generating the flame chart, we found that VersionedIntervalTimeline.isOvershadowed has poor performance.

But when we read the code according to the above call stack, we get confused about why DataSegment.includeRootPartitions cost so much time (A large part of the top of the flame chart is blank).

  private boolean includeRootPartitions(DataSegment other)
  {
    return shardSpec.getStartRootPartitionId() <= other.shardSpec.getStartRootPartitionId()
           && shardSpec.getEndRootPartitionId() >= other.shardSpec.getEndRootPartitionId();
  }

[abhishekagarwal87]

do you have a lot of segments in a single interval? The MarkAsUnusedOvershadowedSegments doesn't look very efficient when there are a lot of segments in a single interval. This duty iterates over each segment and then in each iteration may compare the segment in the outer loop against each segment in the interval. So it's not that the includeRootPartitions itself is costly. But it is being called too many times.

[viongpanzi]

@abhishekagarwal87 Yes. There are about 20,000 segments in a single interval.

[viongpanzi]

@abhishekagarwal87 Does it help to replace for loop with Iterators.all?

[abhishekagarwal87]

How will that help? As long as the number of computations/ops is the same, the time taken won't change much.

[viongpanzi]

How will that help? As long as the number of computations/ops is the same, the time taken won't change much.

@abhishekagarwal87 You're right! Thanks for your quick reply!

[jihoonson]

The current design assumes that there won't be too many segments in each time chunk. The number of "too many segments" can be defined differently based on your machine spec, but, a rule of thumb is less than 2k. The workaround can depend on why you have such many segments. If you have a lot of small segments, you can use auto compaction to merge them (https://support.imply.io/hc/en-us/articles/360055221054-How-to-set-the-auto-compaction-config-in-the-Druid-console). If you do have large segments of 20k, you can repartition your datasource with a smaller segment granularity. For example, if your datasource is currently daily-partitioned, you can repartition it to be hourly-partitioned. The auto compaction can help with switching segment granularity as well, but it started supporting segment granularity recently, so please check Druid docs to see if auto compaction supports segment granularity in your Druid version.

[viongpanzi]

@jihoonson Thank you for your explanation and advice! Our data volume is too large, we need to keep it to be daily-partitioned in order to save more disks. Now the Coordinator has been downgraded to 0.13 and the problem is gone (We are not using compaction yet ).

[kfaraz]

The main issue of high runtime of MarkAsUnusedOvershadowedSegments has been fixed in #13287 . As pointed earlier by @abhishekagarwal87 , the isOvershadowed method itself might not be too costly but since it was invoked too many times, it amounted to a very long runtime.

The fix looks only at the segments that have already been identified to be overshadowed by the timeline, rather than iterating over all the used segments.