jihoonson commented on a change in pull request #8222: Fix bugs in
overshadowableManager and add unit tests
URL: https://github.com/apache/incubator-druid/pull/8222#discussion_r311296658
##########
File path:
core/src/main/java/org/apache/druid/timeline/partition/OvershadowableManager.java
##########
@@ -189,89 +247,362 @@ private void
transitAtomicUpdateGroupState(AtomicUpdateGroup<T> atomicUpdateGrou
}
/**
- * Find all atomicUpdateGroups of the given state overshadowed by the given
rootPartitionRange and minorVersion.
+ * Find all atomicUpdateGroups of the given state overshadowed by the
minorVersion in the given rootPartitionRange.
* The atomicUpdateGroup of a higher minorVersion can have a wider
RootPartitionRange.
* To find all atomicUpdateGroups overshadowed by the given
rootPartitionRange and minorVersion,
* we first need to find the first key contained by the given
rootPartitionRange.
* Once we find such key, then we go through the entire map until we see an
atomicUpdateGroup of which
* rootRangePartition is not contained by the given rootPartitionRange.
+ *
+ * @param rangeOfAug the partition range to search for overshadowed groups.
+ * @param minorVersion the minor version to check overshadow relation. The
found groups will have lower minor versions
+ * than this.
+ * @param fromState the state to search for overshadowed groups.
+ *
+ * @return a list of found atomicUpdateGroups. It could be empty if no
groups are found.
+ */
+ @VisibleForTesting
+ List<AtomicUpdateGroup<T>> findOvershadowedBy(RootPartitionRange rangeOfAug,
short minorVersion, State fromState)
+ {
+ final TreeMap<RootPartitionRange,
Short2ObjectSortedMap<AtomicUpdateGroup<T>>> stateMap = getStateMap(fromState);
+ Entry<RootPartitionRange, Short2ObjectSortedMap<AtomicUpdateGroup<T>>>
current = findLowestOverlappingEntry(
+ rangeOfAug,
+ stateMap,
+ true
+ );
+
+ if (current == null) {
+ return Collections.emptyList();
+ }
+
+ // Going through the map to find all entries of the RootPartitionRange
contained by the given rangeOfAug.
+ // Note that RootPartitionRange of entries are always consecutive.
+ final List<AtomicUpdateGroup<T>> found = new ArrayList<>();
+ while (current != null && rangeOfAug.overlaps(current.getKey())) {
+ if (rangeOfAug.contains(current.getKey())) {
+ // versionToGroup is sorted by minorVersion.
+ // versionToGroup.headMap(minorVersion) below returns a map containing
all entries of lower minorVersions
+ // than the given minorVersion.
+ final Short2ObjectSortedMap<AtomicUpdateGroup<T>> versionToGroup =
current.getValue();
+ // Short2ObjectRBTreeMap.SubMap.short2ObjectEntrySet() implementation,
especially size(), is not optimized.
+ // Note that size() is indirectly called in ArrayList.addAll() when
ObjectSortedSet.toArray() is called.
+ // See AbstractObjectCollection.toArray().
+ // If you see performance degradation here, probably we need to
improve the below line.
+ if (versionToGroup.firstShortKey() < minorVersion) {
+ found.addAll(versionToGroup.headMap(minorVersion).values());
+ }
+ }
+ current = stateMap.higherEntry(current.getKey());
+ }
+ return found;
+ }
+
+ private List<AtomicUpdateGroup<T>> findOvershadows(AtomicUpdateGroup<T> aug,
State fromState)
+ {
+ return findOvershadows(RootPartitionRange.of(aug), aug.getMinorVersion(),
fromState);
+ }
+
+ /**
+ * Find all atomicUpdateGroups which overshadow others of the given
minorVersion in the given rootPartitionRange.
+ * Similar to {@link #findOvershadowedBy}.
+ *
+ * Note that one atommicUpdateGroup can overshadow multiple other groups. If
you're finding overshadowing
Review comment:
Thanks, fixed.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@druid.apache.org
For additional commands, e-mail: commits-h...@druid.apache.org
