You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "abhishekrb19 (via GitHub)" <gi...@apache.org> on 2024/07/10 17:51:52 UTC

[PR] Round-robin iterator for the KillUnusedSegments duty (druid)

abhishekrb19 opened a new pull request, #16719:
URL: https://github.com/apache/druid/pull/16719

   ### Problem
   Currently, there is a fairness problem in the `KillUnusedSegments` duty where the duty consistently selects the same set of datasources as discovered from the metadata store or dynamic config parameters. This is particularly problematic when there are a steady stream of unused segments created by retention rules and fewer kill task slots. 
   
   
   
   ### Fix
   To address the fairness problem, this patch adds a simple round-robin iterator to select datasources to kill. The `RoundRobinIterator` and has the following properties:
   1. Starts with an initial random cursor position in an ordered list of candidates.
   2. Consecutive iterations on the iterator are guaranteed to be deterministic unless the set of candidates change when `updateCandidates()` is called.
   3. Guarantees that no duplicate candidates are returned in two consecutive iterations on the iterator.
   
   In my testing, I observed that using a random index across multiple updates and iterations results in uniform selection of datasources. The property of avoiding consecutive duplicates is an optimization that can particularly benefit smaller clusters where task slots are limited by default.
   
   A few other heuristic greedy-based approaches that were considered:
   1. Total number of unused segments
   2. Total size of unused segments
   
   The problem with the above approaches is that computing and determining the heuristics can be expensive and non-trivial in the scope of the kill duty. Also, these greedy approaches won't necessarily address the fairness problem at hand in all scenarios.
   
   
   #### Miscellaneous changes
   This patch also includes a few annotation fixes and refactoring/logging improvements. While testing this patch in a medium-sized cluster, sometimes I couldn't tell what was happening in the duty. So I've added some info logs for the exit conditions to improve observability. These are relatively small changes, but I'm happy to pull these out to a separate PR to make reviewing easier if needed.
   
   #### Testing changes
   Since the round robin iterator has some notion of randomness baked in, it was difficult to write tests that are easy to follow. To that effect, I've added a couple of testing hooks `getInitialCursorPosition()` and `getCurrentPosition()`:
   1. `RoundRobinIteratorTest` includes unit tests that control the initial cursor position as well as a test that uses the built-in randomness without influencing the order of iteration.
   3. `KillUnusedSegmentsTest` doesn't need to care about the randomization, as it is an implementation detail of the underlying iterator. Therefore, it sets the round-robin iterator with an initial cursor position of 0, ensuring deterministic iteration that is straightforward to assert when multiple datasources are involved.
   
   
   #### Release note
   
   The `KillUnusedSegments` coordinator duty now uses a round-robin iterator to select datasources during each run, ensuring varied selection instead of repeatedly choosing the same set of datasources.
   
   
   This PR has:
   
   - [x] been self-reviewed.
   - [x] 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.
   - [x] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
   - [x] 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.
   - [x] 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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1692682396


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   Okay, thanks for the suggestions. I've added `CircularList` which is currently used by the kill duty. I haven't refactored `RoundRobinServerSelector` in this PR, so a few differences:
   1. `advanceCursor()` is not public, as it's not required by the kill duty
   2.  I didn't add `resetCursor()` to keep things simple. Since the kill duty also tracks `prevDatasourceKilled`, this seems sufficient
   
   `CircularList` is a sorted list. I've noted this in the Javadocs, but we can perhaps consider renaming the class to `CircularSortedList`. What do you think?
   
    



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672833377


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -249,6 +292,10 @@ private Interval findIntervalForKill(
     stats.add(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, datasourceKey, unusedSegmentIntervals.size());
 
     if (CollectionUtils.isNullOrEmpty(unusedSegmentIntervals)) {
+      log.info(

Review Comment:
   I think this will log for each autoKill run cycle, for each datasource where we do not find any segments to kill. Do you think this might get too chatty?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1673152844


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {

Review Comment:
   I'm not sure if its possible that `this.datasourceIterator` gets updated by another run of this duty in another thread, but if it can, then this loop may never exit. Consider the case where one run of this duty get to this point with a set of datasources `["d1", "d2"]`, but before being able to kill any segments and remove the datasource names from `remainingDatasourcesToKill`, another run of this duty runs and find another set of datasource `[""]`, or any strict subset of the previously found datasources 



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674084655


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -127,7 +148,7 @@ public DruidCoordinatorRuntimeParams run(final DruidCoordinatorRuntimeParams par
     if (canDutyRun()) {
       return runInternal(params);
     } else {
-      log.debug(
+      log.info(

Review Comment:
   Thanks!!



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672964992


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)
+  {
+    if (new HashSet<>(candidates).equals(input)) {
+      return;
+    }
+    this.candidates.clear();
+    this.candidates.addAll(input);
+    Collections.sort(this.candidates);
+    this.currentPosition = getInitialCursorPosition(input.size());
+  }
+
+  public Iterator<String> getIterator()
+  {
+    return new Iterator<String>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return candidates.size() > 0;
+      }
+
+      @Override
+      public String next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        // If the next candidate to be served is the same as the previous candidate served (duplicate),

Review Comment:
   Ah, the candidates list is constructed from the input set, so it will never have duplicates. I have updated the javadocs to call that out explicitly. Let me know if it looks ok.
   
   This logic is basically to avoid returning the same candidate twice in consecutive iterations even when the candidates have changed. Please see `testNoConsecutiveDuplicates`;  it's a small guarantee in the theme of "fairness" and there's no additional cost to do this besides tracking the last served candidate



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672847358


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   So this means that on every autoKill run cycle, we are affectively taking a new random start to the datasources to kill list, and working from there, right? If so, I think this is good.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1693340319


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -204,7 +230,10 @@ private void killUnusedSegments(
         );
         ++submittedTasks;
         datasourceToLastKillIntervalEnd.put(dataSource, intervalToKill.getEnd());
-        remainingDatasourcesToKill.remove(dataSource);
+
+        if (remainingDatasourcesToKill.isEmpty() || submittedTasks >= availableKillTaskSlots) {
+          break;
+        }

Review Comment:
   Yeah, we can. However, it will slightly change the semantics of the round-robin iteration, i.e., the loop will terminate _after_ seeing a new element without doing anything with it.
   
   I've added brief line comments next to these conditions for now.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1673001621


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -75,14 +77,23 @@ public class KillUnusedSegments implements CoordinatorDuty
   private final Duration durationToRetain;
   private final boolean ignoreDurationToRetain;
   private final int maxSegmentsToKill;
+  private final Duration bufferPeriod;
 
   /**
    * Used to keep track of the last interval end time that was killed for each
    * datasource.
    */
   private final Map<String, DateTime> datasourceToLastKillIntervalEnd;
+
+  /**
+   * State that is maintained in the duty to determine if the duty needs to run or not.
+   */
   private DateTime lastKillTime;
-  private final Duration bufferPeriod;
+
+  /**
+   * Round-robin iterator of the datasources to kill. It's updated in every run by the duty.
+   */
+  private final RoundRobinIterator datasourceIterator;

Review Comment:
   Good point, the implementation is not thread safe. I've added the `@NotThreadSafe` annotation to this class.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672995759


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -127,7 +148,7 @@ public DruidCoordinatorRuntimeParams run(final DruidCoordinatorRuntimeParams par
     if (canDutyRun()) {
       return runInternal(params);
     } else {
-      log.debug(
+      log.info(

Review Comment:
   Hm, this is an exit condition I think is worth keeping. Also, there's a similar log in the `MarkOvershadowedSegmentsAsUnused` which by default runs every minute (more frequent than the default 30m `KillUnusedSegments` duty cycle): https://github.com/apache/druid/blob/master/server/src/main/java/org/apache/druid/server/coordinator/duty/MarkOvershadowedSegmentsAsUnused.java#L74
   
   I will remove it if we feel strongly about it.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672966867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   >So this means that on every autoKill run cycle, we are affectively taking a new random start to the datasources to kill list, and working from there, right? If so, I think this is good.
   
   Yeah, exactly. If the datasources haven't changed, the iteration just resumes from the last position.
   
   > Also, if this is being updated each time, why keep the state at class level, instead of just having local variable that we use each time we go to kill unused segments. That way we dont have to worry about thread safety
   
   The cursor needs to be stateful as we reset it only when the candidates have changed when `updateCandidates()` is called. If we want thread-safety, we can perhaps address that separately using synchronization primitives. But right now, thread safety is not a current requirement, since the usage of the iterator in the kill duty is guaranteed to be thread-safe.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672828810


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {
+      if (remainingDatasourcesToKill.size() == 0) {
+        log.info(
+            "Submitted [%d] kill tasks for [%d] datasources. No more datasource to kill in this cycle.",
+            submittedTasks, datasourcesKilled.size()
+        );
+        break;
+      }
+
       if (submittedTasks >= availableKillTaskSlots) {
         log.info(
-            "Submitted [%d] kill tasks and reached kill task slot limit [%d].",
-            submittedTasks, availableKillTaskSlots
+            "Submitted [%d] kill tasks for [%d] datasources and reached kill task slot limit [%d].",
+            submittedTasks, datasourcesKilled.size(), availableKillTaskSlots
         );
         break;
       }
+
+      final String dataSource = dataSourcesToKillIterator.next();
       final DateTime maxUsedStatusLastUpdatedTime = DateTimes.nowUtc().minus(bufferPeriod);
       final Interval intervalToKill = findIntervalForKill(dataSource, maxUsedStatusLastUpdatedTime, stats);
       if (intervalToKill == null) {
         datasourceToLastKillIntervalEnd.remove(dataSource);
+        remainingDatasourcesToKill.remove(dataSource);

Review Comment:
   idea for improvement in this area, I think this issue existed before; if there is only one datasource with segments to kill, and it has more unused segments than we limit per task, and there is more than one task slot allotted to auto kill, then we only issue one task per run cycle, when we can fully use the capacity we have. Not to fix in this pr, since I believe it was an existing issue, just an idea for improvement.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672966867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   >So this means that on every autoKill run cycle, we are affectively taking a new random start to the datasources to kill list, and working from there, right? If so, I think this is good.
   
   Yeah, exactly. If the datasources haven't changed, the iteration just resumes from the last position.
   
   > Also, if this is being updated each time, why keep the state at class level, instead of just having local variable that we use each time we go to kill unused segments. That way we dont have to worry about thread safety
   
   The cursor needs to be stateful as we reset it only when the candidates have changed when `updateCandidates()` is called. If we want thread-safety, we can perhaps address that separately using synchronization primitives. But right now, thread safety is not a requirement, since the usage of the iterator in the kill duty is guaranteed to be thread-safe.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672850797


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -127,7 +148,7 @@ public DruidCoordinatorRuntimeParams run(final DruidCoordinatorRuntimeParams par
     if (canDutyRun()) {
       return runInternal(params);
     } else {
-      log.debug(
+      log.info(

Review Comment:
   I think this log can get quite chatty too if the autoKill duty period set to a more continous value, like 30 seconds or 1 minute.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674081880


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -127,7 +148,7 @@ public DruidCoordinatorRuntimeParams run(final DruidCoordinatorRuntimeParams par
     if (canDutyRun()) {
       return runInternal(params);
     } else {
-      log.debug(
+      log.info(

Review Comment:
   Okay, I will downgrade the newly added info logs for termination conditions to debug.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672964992


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)
+  {
+    if (new HashSet<>(candidates).equals(input)) {
+      return;
+    }
+    this.candidates.clear();
+    this.candidates.addAll(input);
+    Collections.sort(this.candidates);
+    this.currentPosition = getInitialCursorPosition(input.size());
+  }
+
+  public Iterator<String> getIterator()
+  {
+    return new Iterator<String>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return candidates.size() > 0;
+      }
+
+      @Override
+      public String next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        // If the next candidate to be served is the same as the previous candidate served (duplicate),

Review Comment:
   Ah, the candidates list is constructed from the input set, so it will never have duplicates. I have updated the javadocs to call that out explicitly. Let me know if it looks ok.
   
   This logic is basically to avoid returning the same candidate twice in consecutive iterations even when the candidates have changed. Please see `testNoConsecutiveDuplicates`;  it's a small optimization and there's no additional cost to do this besides tracking the last served candidate



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 merged PR #16719:
URL: https://github.com/apache/druid/pull/16719


-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1673268762


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -75,14 +77,23 @@ public class KillUnusedSegments implements CoordinatorDuty
   private final Duration durationToRetain;
   private final boolean ignoreDurationToRetain;
   private final int maxSegmentsToKill;
+  private final Duration bufferPeriod;
 
   /**
    * Used to keep track of the last interval end time that was killed for each
    * datasource.
    */
   private final Map<String, DateTime> datasourceToLastKillIntervalEnd;
+
+  /**
+   * State that is maintained in the duty to determine if the duty needs to run or not.
+   */

Review Comment:
   I am not sure if the new javadocs for the private fields are really adding any value.
   The field names are self-explanatory and it is trivial to check how they are being used.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   Some suggestions to make this class nicer:
   
   1. The iteration aspect of this class seems vaguely similar to `RoundRobinServerSelector.CircularServerList`. Let's just pull out `CircularServerList` as a generic class `CircularList<T>` and put it in the package `org.apache.druid.collections`.
   2. Make `CircularList` implement `Iterable`.
   3. Ideally, this class would have no public methods right now, but since `RoundRobinServerSelector` is already using `peekNext()` and `advanceCursor()`, let's keep them for now. I can later take a look at `EligibleServerSelector` to see if we can't do without these methods.
   4.  I am not entirely sold on requiring to reset the cursor to a random position (it would be nice to have a unit test that verifies the spread after say 1000 runs and compare when we reset to random and don't reset at all).
     - Either way, the `CircularList` should expose a method `resetCursor(int position)`. The randomness should not be baked into this class and should instead be provided by the caller (in this case, the kill duty).
     - Sorting and randomization should be mutually exclusive. If we are going to randomize, there is no point in sorting the set.
   5. We can also add a method `equalsSet(Set<>)`.
   6. The requirement to avoid duplicates should be a part of the caller, i.e. kill duty. (I recall having suggested it to be a part of the `RoundRobinIterator` but this seems cleaner now 😛 ).
   
   After all of this, the kill duty would look as follows:
   
   
   ```java
   private String prevDatasourceKilled;
   
   // I don't like this variable name myself, if something better comes to mind, use it
   private CircularList<String> datasourceCircularKillList;
   
   public void run()
   {
      ...
      ...
      // This goes where we identify the datasourcesToKill in the duty
      final Set<String> datasourcesToKill = ...;
      if (datasourceCircularKillList == null ||
            !datasourceCircularKillList.equalsSet(datasourcesToKill)) {
          datasourceCircularKillList = new CircularList<>(datasourcesToKill);
          
          // optional
          datasourceCircularKillList.resetCursor(randomPosition);
      }
      ...
      ...
      // This goes where we iterate over the circular list
      for (String datasource : datasourceCircularKillList) {
          if (datasource.equals(prevDatasourceKilled)) {
             continue;
          } else {
             prevDatasourceKilled = datasource;
          }
          
          // Do the rest of the kill processing
      }
      ...
      ...
   }
   ```



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {

Review Comment:
   Please invert the condition for readability.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");

Review Comment:
   This log can become verbose too. Once we have submitted all the kill tasks that we can, it is going to be a while before slots free up. So, if kill period is low, we might see many of these logs.
   
   I would advise leaving out all the new info logs for now.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default

Review Comment:
   Feels redundant as the code itself is doing exactly that.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();

Review Comment:
   It is redundant to maintain both these sets. Let's just keep `datasourcesKilled`, we can build the other from it as it is only needed once at the end.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -75,14 +77,23 @@ public class KillUnusedSegments implements CoordinatorDuty
   private final Duration durationToRetain;
   private final boolean ignoreDurationToRetain;
   private final int maxSegmentsToKill;
+  private final Duration bufferPeriod;
 
   /**
    * Used to keep track of the last interval end time that was killed for each
    * datasource.
    */
   private final Map<String, DateTime> datasourceToLastKillIntervalEnd;
+
+  /**
+   * State that is maintained in the duty to determine if the duty needs to run or not.
+   */
   private DateTime lastKillTime;
-  private final Duration bufferPeriod;
+
+  /**
+   * Round-robin iterator of the datasources to kill. It's updated in every run by the duty.
+   */
+  private final RoundRobinIterator datasourceIterator;

Review Comment:
   Good to mark the new class as not thread-safe. But it is not required to be thread-safe as a duty should never run on multiple threads (`CompactSegments` is the only one that could potentially run concurrently if manual compaction is triggered).



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -127,7 +148,7 @@ public DruidCoordinatorRuntimeParams run(final DruidCoordinatorRuntimeParams par
     if (canDutyRun()) {
       return runInternal(params);
     } else {
-      log.debug(
+      log.info(

Review Comment:
   +1 on keeping this as debug.
   
   While testing, it is natural to want more visibility but that can simply be achieved by setting log level to debug.
   
   In production, we should try that:
   - redundant logs of normal operation are avoided
   - all important warn or error information is included
   
   I plan to revisit other duties too to reduce redundant logging.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {

Review Comment:
   > I tried to find documentation on how the duties operate but couldn't find much information. I think adding some code/public-facing documentation on this would help clarify this. :-)
   
   Nah, it is really an implementation detail that only devs need to be privy to.
   
   In `DruidCoordinator`, every duty group has a dedicated single-threaded executor. See `DruidCoordinator.getOrCreateDutyGroupExecutors()`. We can add a comment there asserting that every executor __must always be single-threaded__.
   
   Note: Until a couple of releases ago, all the duties ran on a single thread, so even less concurrency 😂 .



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672976232


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)

Review Comment:
   I considered making it generic but punted on it until we have another real use case (perhaps the compaction duty?). We could have the caller pass a comparable as well, but I didn't want to make any premature changes. Does that sound reasonable?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672976232


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)

Review Comment:
   I considered making it generic but punted on it until we have another real use case (perhaps the compaction duty?). We could have the caller pass a comparable as well, but I didn't want to make any premature changes.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672966867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   >So this means that on every autoKill run cycle, we are affectively taking a new random start to the datasources to kill list, and working from there, right? If so, I think this is good.
   
   Yeah. If the datasources haven't changed, the iteration just resumes from the last cursor position.
   
   > Also, if this is being updated each time, why keep the state at class level, instead of just having local variable that we use each time we go to kill unused segments. That way we dont have to worry about thread safety
   
   The cursor needs to be stateful as we reset it only when the candidates have changed when `updateCandidates()` is called. If we want thread-safety, we can perhaps address that separately using synchronization primitives. But right now, thread safety is not a requirement, since the usage of the iterator in the kill duty is guaranteed to be thread-safe.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1693186473


##########
processing/src/test/java/org/apache/druid/collections/CircularListTest.java:
##########
@@ -0,0 +1,106 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+public class CircularListTest
+{
+  @Test
+  public void testIterateInNaturalOrder()
+  {
+    final Set<String> input = ImmutableSet.of("b", "a", "c");
+    final CircularList<String> circularList = new CircularList<>(input, Comparator.naturalOrder());
+    final List<String> observedElements = new ArrayList<>();
+    int cnt = 0;
+    for (String x : circularList) {
+      observedElements.add(x);
+      if (++cnt >= input.size()) {
+        break;
+      }
+    }
+    Assert.assertEquals(ImmutableList.of("a", "b", "c"), observedElements);
+  }
+
+  @Test
+  public void testIterateInReverseOrder()

Review Comment:
   Should we have a test where we have two `for` loops? We break the first in the middle of the cycle and ensure that the second resumes from where we started.
   
   I think your current code will maintain the order with two or more `for` loops since the current position is maintained in the `CircularList` itself rather than inside the returned iterator.
   
   Either way, it would be nice to call out the behaviour in the javadoc and have a test for it.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on PR #16719:
URL: https://github.com/apache/druid/pull/16719#issuecomment-2253334496

   Thanks for the thorough reviews & discussions, @kfaraz @zachjsh


-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1693055681


##########
processing/src/main/java/org/apache/druid/collections/CircularList.java:
##########
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A circular list that is backed by an ordered list of elements containing no duplicates. The list is ordered by the
+ * supplied comparator. Callers are responsible for terminating the iterator explicitly.
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class CircularList<T> implements Iterable<T>
+{
+  private final List<T> collection = new ArrayList<>();
+  private final Comparator<? super T> comparator;
+  private int currentPosition;
+
+  public CircularList(final Set<T> elements, Comparator<? super T> comparator)
+  {
+    this.collection.addAll(elements);
+    this.comparator = comparator;
+    this.collection.sort(comparator);
+  }
+
+  @Override
+  public Iterator<T> iterator()
+  {
+    return new Iterator<T>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return collection.size() > 0;
+      }
+
+      @Override
+      public T next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        T nextCandidate = peekNext();
+        advanceCursor();
+        return nextCandidate;
+      }
+
+      private T peekNext()
+      {
+        int nextPosition = currentPosition < collection.size() ? currentPosition : 0;
+        return collection.get(nextPosition);
+      }
+
+      private void advanceCursor()
+      {
+        if (++currentPosition >= collection.size()) {
+          currentPosition = 0;
+        }
+      }
+    };
+  }
+
+  /**
+   * @return true if the supplied set is equal to the set used to instantiate this circular list, otherwise false.
+   */
+  public boolean equalsSet(final Set<T> inputSet)
+  {
+    final List<T> sortedList = new ArrayList<>(inputSet);
+    sortedList.sort(comparator);
+    return collection.equals(sortedList);

Review Comment:
   Maybe we don't need to sort for the equality check:
   
   ```suggestion
       return new HashSet<>(collection).equals(inputSet);
   ```



##########
processing/src/test/java/org/apache/druid/collections/CircularListTest.java:
##########
@@ -0,0 +1,106 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+public class CircularListTest
+{
+  @Test
+  public void testIterateInNaturalOrder()
+  {
+    final Set<String> input = ImmutableSet.of("b", "a", "c");
+    final CircularList<String> circularList = new CircularList<>(input, Comparator.naturalOrder());
+    final List<String> observedElements = new ArrayList<>();
+    int cnt = 0;
+    for (String x : circularList) {
+      observedElements.add(x);
+      if (++cnt >= input.size()) {
+        break;
+      }
+    }
+    Assert.assertEquals(ImmutableList.of("a", "b", "c"), observedElements);
+  }
+
+  @Test
+  public void testIterateInReverseOrder()

Review Comment:
   Should we have a test where we have two `for` loops? We break the first in the middle of the cycle and ensure that the second resumes from where we started.
   Or is that not a valid use case? 😛 
   
   I think your current code will maintain the order with two or more `for` loops since the current position is maintained in the `CircularList` itself rather than inside the returned iterator.
   
   Either way, it would be nice to call out the behaviour in the javadoc and have a test for it.



##########
processing/src/main/java/org/apache/druid/collections/CircularList.java:
##########
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A circular list that is backed by an ordered list of elements containing no duplicates. The list is ordered by the
+ * supplied comparator. Callers are responsible for terminating the iterator explicitly.
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class CircularList<T> implements Iterable<T>
+{
+  private final List<T> collection = new ArrayList<>();
+  private final Comparator<? super T> comparator;
+  private int currentPosition;
+
+  public CircularList(final Set<T> elements, Comparator<? super T> comparator)

Review Comment:
   __Non-blocking suggestion:__
   
   We should be able to iterate over any list in a circular fashion using this class.
   Whether the list is sorted or not or has duplicates or not should be up to the caller.
   
   It is possible to have some usage of this class that requires the values to be in a specific order (I guess that would still be possible using an `Ordering.explicit()` for the comparator.)
   
   If not, then this class is more of a `CircularSortedSet` which is a nice alliteration but `CircularList` still has a better ring to it 😛 (and is easier to visualize).
   
   That said, if you prefer the current data structure, I am okay with it too.



##########
processing/src/main/java/org/apache/druid/collections/CircularList.java:
##########
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A circular list that is backed by an ordered list of elements containing no duplicates. The list is ordered by the
+ * supplied comparator. Callers are responsible for terminating the iterator explicitly.
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class CircularList<T> implements Iterable<T>
+{
+  private final List<T> collection = new ArrayList<>();
+  private final Comparator<? super T> comparator;
+  private int currentPosition;
+
+  public CircularList(final Set<T> elements, Comparator<? super T> comparator)
+  {
+    this.collection.addAll(elements);
+    this.comparator = comparator;
+    this.collection.sort(comparator);
+  }
+
+  @Override
+  public Iterator<T> iterator()
+  {
+    return new Iterator<T>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return collection.size() > 0;
+      }
+
+      @Override
+      public T next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        T nextCandidate = peekNext();
+        advanceCursor();
+        return nextCandidate;

Review Comment:
   I can't recall why RoundRobinServerSelector had a `peek` semantic (maybe because `advanceCursor()` was public?), but I think the current code can be simplified:
   
   ```suggestion
           advanceCursor();
           return collection.get(currentPosition);
   ```
   
   `currentPosition` would have to be initialized to -1 in the constructor and we wouldn't need the `peekNext()` method anymore.



##########
processing/src/main/java/org/apache/druid/collections/CircularList.java:
##########
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A circular list that is backed by an ordered list of elements containing no duplicates. The list is ordered by the
+ * supplied comparator. Callers are responsible for terminating the iterator explicitly.
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class CircularList<T> implements Iterable<T>
+{
+  private final List<T> collection = new ArrayList<>();

Review Comment:
   Super Nit:
   Maybe a better name would be `items` or `elements`.
   Or if you want to refer to the list itself, you could call it `delegate` or `backingList`.



##########
server/src/test/java/org/apache/druid/server/coordinator/duty/KillUnusedSegmentsTest.java:
##########
@@ -225,6 +225,154 @@ public void testKillWithMultipleDatasources()
     validateLastKillStateAndReset(DS2, null);
   }
 
+  /**
+   * Set up multiple datasources {@link #DS1}, {@link #DS2} and {@link #DS3} with unused segments with 2 kill task
+   * slots. Running the kill duty each time should pick at least one unique datasource in a round-robin manner.
+   */
+  @Test
+  public void testKillMultipleDatasourcesInRoundRobinManner()

Review Comment:
   Super Nit: Can we avoid using the suffix `Manner`?
   Maybe rename to `testRoundRobinKillMultipleDatasources()`?
   Same comment for the other test name.



##########
server/src/test/java/org/apache/druid/server/coordinator/duty/KillUnusedSegmentsTest.java:
##########
@@ -723,6 +901,17 @@ private void validateLastKillStateAndReset(final String dataSource, @Nullable fi
     overlordClient.deleteLastKillInterval(dataSource);
   }
 
+  private void createAndAddUsedSegment(final String dataSource, final Interval interval, final String version)
+  {
+    final DataSegment segment = createSegment(dataSource, interval, version);
+    try {
+      SqlSegmentsMetadataManagerTestBase.publishSegment(connector, config, TestHelper.makeJsonMapper(), segment);
+    }
+    catch (IOException e) {
+      throw new RuntimeException(e);
+    }
+  }
+
   private void createAndAddUnusedSegment(

Review Comment:
   Nit: This method can now call the `createAndAddUsedSegment` as that part is common.



##########
server/src/test/java/org/apache/druid/server/coordinator/duty/KillUnusedSegmentsTest.java:
##########
@@ -225,6 +225,154 @@ public void testKillWithMultipleDatasources()
     validateLastKillStateAndReset(DS2, null);
   }
 
+  /**
+   * Set up multiple datasources {@link #DS1}, {@link #DS2} and {@link #DS3} with unused segments with 2 kill task
+   * slots. Running the kill duty each time should pick at least one unique datasource in a round-robin manner.
+   */

Review Comment:
   Style:
   I generally prefer leaving one-line comments within the test method where relevant instead of javadocs (unless the test is too complicated). Ideally, the test name and the test code itself should be descriptive enough to clarify what is being verified.



##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -204,7 +230,10 @@ private void killUnusedSegments(
         );
         ++submittedTasks;
         datasourceToLastKillIntervalEnd.put(dataSource, intervalToKill.getEnd());
-        remainingDatasourcesToKill.remove(dataSource);
+
+        if (remainingDatasourcesToKill.isEmpty() || submittedTasks >= availableKillTaskSlots) {
+          break;
+        }

Review Comment:
   Would it be better to have this check right at the beginning of the loop?
   Currently there are multiple breaks and continue which makes the code a little difficult to follow.



##########
server/src/test/java/org/apache/druid/server/coordinator/duty/KillUnusedSegmentsTest.java:
##########
@@ -225,6 +225,154 @@ public void testKillWithMultipleDatasources()
     validateLastKillStateAndReset(DS2, null);
   }
 
+  /**
+   * Set up multiple datasources {@link #DS1}, {@link #DS2} and {@link #DS3} with unused segments with 2 kill task
+   * slots. Running the kill duty each time should pick at least one unique datasource in a round-robin manner.
+   */
+  @Test
+  public void testKillMultipleDatasourcesInRoundRobinManner()
+  {
+    configBuilder.withIgnoreDurationToRetain(true)
+                 .withMaxSegmentsToKill(2);
+    dynamicConfigBuilder.withMaxKillTaskSlots(2);
+
+    createAndAddUnusedSegment(DS1, YEAR_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, MONTH_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, DAY_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, NEXT_DAY, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, NEXT_MONTH, VERSION, NOW.minusDays(1));
+
+    createAndAddUnusedSegment(DS2, YEAR_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS2, DAY_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS2, NEXT_DAY, VERSION, NOW.minusDays(1));
+
+    createAndAddUnusedSegment(DS3, YEAR_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS3, DAY_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS3, NEXT_DAY, VERSION, NOW.minusDays(1));
+
+    initDuty();
+    CoordinatorRunStats stats = runDutyAndGetStats();
+
+    Assert.assertEquals(2, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS1_STAT_KEY));
+    Assert.assertEquals(2, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS2_STAT_KEY));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(4, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(4, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(4, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS3_STAT_KEY));
+    Assert.assertEquals(4, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS1_STAT_KEY));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(6, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(6, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(6, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(3, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS2_STAT_KEY));
+    Assert.assertEquals(3, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS3_STAT_KEY));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(8, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(7, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(8, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(5, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS1_STAT_KEY));
+    Assert.assertEquals(3, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS2_STAT_KEY));
+  }
+
+  /**
+   * The set of datasources to kill change in consecutive runs. The kill duty should avoid selecting two
+   * consecutive datasources across runs as long as there are other datasources to kill.
+   */
+  @Test
+  public void testKillInRoundRobinMannerWhenDatasourcesChange()
+  {
+    configBuilder.withIgnoreDurationToRetain(true)
+                 .withMaxSegmentsToKill(2);
+    dynamicConfigBuilder.withMaxKillTaskSlots(1);
+
+    createAndAddUnusedSegment(DS1, YEAR_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, MONTH_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS1, DAY_OLD, VERSION, NOW.minusDays(1));
+
+    initDuty();
+    CoordinatorRunStats stats = runDutyAndGetStats();
+
+    Assert.assertEquals(1, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(1, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(1, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS1_STAT_KEY));
+
+    validateLastKillStateAndReset(DS1, new Interval(YEAR_OLD.getStart(), MONTH_OLD.getEnd()));
+
+    createAndAddUnusedSegment(DS2, YEAR_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS2, DAY_OLD, VERSION, NOW.minusDays(1));
+    createAndAddUnusedSegment(DS2, NEXT_DAY, VERSION, NOW.minusDays(1));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(2, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(2, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS2_STAT_KEY));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(3, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(3, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(3, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(3, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS1_STAT_KEY));
+
+    stats = runDutyAndGetStats();
+
+    Assert.assertEquals(4, stats.get(Stats.Kill.AVAILABLE_SLOTS));
+    Assert.assertEquals(4, stats.get(Stats.Kill.SUBMITTED_TASKS));
+    Assert.assertEquals(4, stats.get(Stats.Kill.MAX_SLOTS));
+    Assert.assertEquals(3, stats.get(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, DS2_STAT_KEY));
+  }
+
+  /**
+   * There is a single datasource to kill across multiple runs. The duty should keep picking the same datasource.
+   */

Review Comment:
   Not needed, test name is self-explanatory.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672837536


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)

Review Comment:
   Should be make this more generic, instead of just for Strings?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672833377


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -249,6 +292,10 @@ private Interval findIntervalForKill(
     stats.add(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, datasourceKey, unusedSegmentIntervals.size());
 
     if (CollectionUtils.isNullOrEmpty(unusedSegmentIntervals)) {
+      log.info(

Review Comment:
   I think this will log for every datasource where we do not find any segments to kill. Do you think this might get too chatty?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672844590


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)
+  {
+    if (new HashSet<>(candidates).equals(input)) {
+      return;
+    }
+    this.candidates.clear();
+    this.candidates.addAll(input);
+    Collections.sort(this.candidates);
+    this.currentPosition = getInitialCursorPosition(input.size());
+  }
+
+  public Iterator<String> getIterator()
+  {
+    return new Iterator<String>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return candidates.size() > 0;
+      }
+
+      @Override
+      public String next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        // If the next candidate to be served is the same as the previous candidate served (duplicate),

Review Comment:
   Since the input list is sorted when constructing the resulting iterator backed list, If the input list contains an element with more than duplicate, then we will return the same element 2 times in row, is that right?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672844590


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)
+  {
+    if (new HashSet<>(candidates).equals(input)) {
+      return;
+    }
+    this.candidates.clear();
+    this.candidates.addAll(input);
+    Collections.sort(this.candidates);
+    this.currentPosition = getInitialCursorPosition(input.size());
+  }
+
+  public Iterator<String> getIterator()
+  {
+    return new Iterator<String>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return candidates.size() > 0;
+      }
+
+      @Override
+      public String next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        // If the next candidate to be served is the same as the previous candidate served (duplicate),

Review Comment:
   Since the input list is sorted when constructing the resulting iterator backed list, If the input list contains an element with more than one duplicate, then we will return the same element 2 times in row, is that right?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674367270


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   The code reorganization will also entail retesting `RoundRobinServerSelector`. I currently don't have the bandwidth to do that.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674396492


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   Oh, that should be fine. There are enough UTs and sims in place to ensure that everything continues to work as expected. You need not test it out separately.
   
   If you still don't feel comfortable touching `RoundRobinServerSelector`, you may leave it for now. I can take a look at it later.
   
   But we should still use the `CircularList` in this PR as discussed above instead of the current approach (given that you agree with the `CircularList` design).



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672953483


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {
+      if (remainingDatasourcesToKill.size() == 0) {
+        log.info(
+            "Submitted [%d] kill tasks for [%d] datasources. No more datasource to kill in this cycle.",
+            submittedTasks, datasourcesKilled.size()
+        );
+        break;
+      }
+
       if (submittedTasks >= availableKillTaskSlots) {
         log.info(
-            "Submitted [%d] kill tasks and reached kill task slot limit [%d].",
-            submittedTasks, availableKillTaskSlots
+            "Submitted [%d] kill tasks for [%d] datasources and reached kill task slot limit [%d].",
+            submittedTasks, datasourcesKilled.size(), availableKillTaskSlots
         );
         break;
       }
+
+      final String dataSource = dataSourcesToKillIterator.next();
       final DateTime maxUsedStatusLastUpdatedTime = DateTimes.nowUtc().minus(bufferPeriod);
       final Interval intervalToKill = findIntervalForKill(dataSource, maxUsedStatusLastUpdatedTime, stats);
       if (intervalToKill == null) {
         datasourceToLastKillIntervalEnd.remove(dataSource);
+        remainingDatasourcesToKill.remove(dataSource);

Review Comment:
   Good idea! We can address the existing capacity underutilization problem separately.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672954449


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -249,6 +292,10 @@ private Interval findIntervalForKill(
     stats.add(Stats.Kill.ELIGIBLE_UNUSED_SEGMENTS, datasourceKey, unusedSegmentIntervals.size());
 
     if (CollectionUtils.isNullOrEmpty(unusedSegmentIntervals)) {
+      log.info(

Review Comment:
   Good call, this is not really an exit condition, so I went ahead and removed this log. Thanks!



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674093338


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {

Review Comment:
   Thanks for confirming! Hopefully that clarifies most of the thread-safety concerns Zach had.
   
   >Note: Until a couple of releases ago, all the duties ran on a single thread, so even less concurrency 😂 .
   
   😅 



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "kfaraz (via GitHub)" <gi...@apache.org>.
kfaraz commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674336886


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   I should imagine the only extra refactor required would be moving `CircularServerList` out of `RoundRobinServerSelector`. Are there other changes involved?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1693333936


##########
processing/src/test/java/org/apache/druid/collections/CircularListTest.java:
##########
@@ -0,0 +1,106 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+public class CircularListTest
+{
+  @Test
+  public void testIterateInNaturalOrder()
+  {
+    final Set<String> input = ImmutableSet.of("b", "a", "c");
+    final CircularList<String> circularList = new CircularList<>(input, Comparator.naturalOrder());
+    final List<String> observedElements = new ArrayList<>();
+    int cnt = 0;
+    for (String x : circularList) {
+      observedElements.add(x);
+      if (++cnt >= input.size()) {
+        break;
+      }
+    }
+    Assert.assertEquals(ImmutableList.of("a", "b", "c"), observedElements);
+  }
+
+  @Test
+  public void testIterateInReverseOrder()

Review Comment:
   Added a test and updated the javadoc to highlight the resume behavior.
   



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672822867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -75,14 +77,23 @@ public class KillUnusedSegments implements CoordinatorDuty
   private final Duration durationToRetain;
   private final boolean ignoreDurationToRetain;
   private final int maxSegmentsToKill;
+  private final Duration bufferPeriod;
 
   /**
    * Used to keep track of the last interval end time that was killed for each
    * datasource.
    */
   private final Map<String, DateTime> datasourceToLastKillIntervalEnd;
+
+  /**
+   * State that is maintained in the duty to determine if the duty needs to run or not.
+   */
   private DateTime lastKillTime;
-  private final Duration bufferPeriod;
+
+  /**
+   * Round-robin iterator of the datasources to kill. It's updated in every run by the duty.
+   */
+  private final RoundRobinIterator datasourceIterator;

Review Comment:
   Is this iterator thread safe? What protects this duty from only having one thread running at a given time?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672837536


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)

Review Comment:
   Should we make this more generic, instead of just for Strings?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672851349


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");

Review Comment:
   I think this is a good log to have at info. 👌 



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672966867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   Yeah, exactly. If the datasources haven't changed, the iteration just resumes from the last position.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674090056


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();

Review Comment:
   Yeah, that's fair. `remainingDatasourcesToKill` is used as a termination condition for the iteration. We can remove `datasourcesKilled` because it can be easily computed at the end for logging.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674280104


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.druid.error.InvalidInput;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that is backed by an ordered list of candidates containing no duplicates. The iterator
+ * iterates endlessly over all the candidates. The caller must explicitly terminate it.
+ * The iterator has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Invoking {@code next()} on {@link #getIterator()} is guaranteed to result in a deterministic order
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. When the candidates change,
+ *   the cursor is reset to a random position in the new list of ordered candidates. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ *
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class RoundRobinIterator

Review Comment:
   Good suggestion! I borrowed some motivation from `RoundRobinServerSelector` :P 
   
   I like the idea and started refactoring and then realized it's going to bloat the changes in more than one place than what's necessary for the scope of this PR. I think it'll be best to do the refactoring-only change in a follow up. What do you think?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] CircularList round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1693343592


##########
processing/src/main/java/org/apache/druid/collections/CircularList.java:
##########
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.collections;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A circular list that is backed by an ordered list of elements containing no duplicates. The list is ordered by the
+ * supplied comparator. Callers are responsible for terminating the iterator explicitly.
+ * <p>
+ * This class is not thread-safe and must be used from a single thread.
+ */
+@NotThreadSafe
+public class CircularList<T> implements Iterable<T>
+{
+  private final List<T> collection = new ArrayList<>();
+  private final Comparator<? super T> comparator;
+  private int currentPosition;
+
+  public CircularList(final Set<T> elements, Comparator<? super T> comparator)

Review Comment:
   >We should be able to iterate over any list in a circular fashion using this class.
   Whether the list is sorted or not or has duplicates or not should be up to the caller.
   
   True that. 
   
   We can perhaps revisit the class name and its usage once we have other use cases. I think it should be relatively straightforward to adjust.
   
   



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1674093338


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {

Review Comment:
   Thanks for confirming! Hopefully that clarifies most of the thread-safe concerns Zach had.
   
   >Note: Until a couple of releases ago, all the duties ran on a single thread, so even less concurrency 😂 .
   
   😅 



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672837201


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/RoundRobinIterator.java:
##########
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.server.coordinator.duty;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * A round-robin iterator that has the following properties:
+ * <ul>
+ *   <li> Starts with an initial random cursor position in an ordered list of candidates. </li>
+ *   <li> Consecutive {@code next()} iterations from {@link #getIterator()} are guaranteed to be deterministic
+ *   unless the set of candidates change when {@link #updateCandidates(Set)} is called. </li>
+ *   <li> Guarantees that no duplicate candidates are returned in two consecutive {@code next()} iterations. </li>
+ * </ul>
+ */
+public class RoundRobinIterator
+{
+  private final List<String> candidates = new ArrayList<>();
+  private int currentPosition;
+  private String previousCandidate;
+
+  /**
+   * Update the candidates with the supplied input if the input set is different from the current candidates.
+   * If the input set is the same as the existing candidates, the cursor position remains unchanged so the iteration order
+   * is determistic and resumed. If the input set is different, the cursor position is reset to a random location in
+   * the new list of sorted candidates.
+   */
+  public void updateCandidates(final Set<String> input)
+  {
+    if (new HashSet<>(candidates).equals(input)) {
+      return;
+    }
+    this.candidates.clear();
+    this.candidates.addAll(input);
+    Collections.sort(this.candidates);
+    this.currentPosition = getInitialCursorPosition(input.size());
+  }
+
+  public Iterator<String> getIterator()
+  {
+    return new Iterator<String>()
+    {
+      @Override
+      public boolean hasNext()
+      {
+        return candidates.size() > 0;
+      }
+
+      @Override
+      public String next()
+      {
+        if (!hasNext()) {
+          throw new NoSuchElementException();
+        }
+
+        // If the next candidate to be served is the same as the previous candidate served (duplicate),

Review Comment:
   Does this only happen if the input list contains duplicates? If so, should we just remove duplicates during construction? Or do we want to allow for duplicates, and have the amount of duplication increase the probability of a candidate being constructed?



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "zachjsh (via GitHub)" <gi...@apache.org>.
zachjsh commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672953972


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   Also, if this is being updated each time, why keep the state at class level, instead of just having local variable that we use each time we go to kill unused segments. That way we dont have to worry about thread safety



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1672966867


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -141,18 +162,24 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
     final CoordinatorRunStats stats = params.getCoordinatorStats();
 
     final int availableKillTaskSlots = getAvailableKillTaskSlots(dynamicConfig, stats);
-    Collection<String> dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
-
-    if (availableKillTaskSlots > 0) {
-      // If no datasource has been specified, all are eligible for killing unused segments
-      if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
-        dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
-      }
+    if (availableKillTaskSlots <= 0) {
+      log.info("Skipping KillUnusedSegments because there are no available kill task slots.");
+      return params;
+    }
 
-      lastKillTime = DateTimes.nowUtc();
-      killUnusedSegments(dataSourcesToKill, availableKillTaskSlots, stats);
+    final Set<String> dataSourcesToKill;
+    if (!CollectionUtils.isNullOrEmpty(dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn())) {
+      dataSourcesToKill = dynamicConfig.getSpecificDataSourcesToKillUnusedSegmentsIn();
+    } else {
+      // If no datasource has been specified, all are eligible for killing unused segments by default
+      dataSourcesToKill = segmentsMetadataManager.retrieveAllDataSourceNames();
     }
 
+    datasourceIterator.updateCandidates(dataSourcesToKill);

Review Comment:
   >So this means that on every autoKill run cycle, we are affectively taking a new random start to the datasources to kill list, and working from there, right? If so, I think this is good.
   
   Yeah, exactly. If the datasources haven't changed, the iteration just resumes from the last position.
   
   > Also, if this is being updated each time, why keep the state at class level, instead of just having local variable that we use each time we go to kill unused segments. That way we dont have to worry about thread safety
   
   The cursor needs to be stateful as we reset it only when the candidates have changed when `updateCandidates()` is called. If we want thread-safety, we can perhaps address that separately via synchronization primitives, but right now thread safety is not a required goal since the usage of the iterator in the kill duty is guaranteed to be thread-safe.



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1673001621


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -75,14 +77,23 @@ public class KillUnusedSegments implements CoordinatorDuty
   private final Duration durationToRetain;
   private final boolean ignoreDurationToRetain;
   private final int maxSegmentsToKill;
+  private final Duration bufferPeriod;
 
   /**
    * Used to keep track of the last interval end time that was killed for each
    * datasource.
    */
   private final Map<String, DateTime> datasourceToLastKillIntervalEnd;
+
+  /**
+   * State that is maintained in the duty to determine if the duty needs to run or not.
+   */
   private DateTime lastKillTime;
-  private final Duration bufferPeriod;
+
+  /**
+   * Round-robin iterator of the datasources to kill. It's updated in every run by the duty.
+   */
+  private final RoundRobinIterator datasourceIterator;

Review Comment:
   Good point, the implementation is not thread safe. I've added the `@NotThreadSafe` annotation to this class.
   
   Also, related comment: https://github.com/apache/druid/pull/16719#discussion_r1673243028



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Round-robin iterator for the KillUnusedSegments duty (druid)

Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #16719:
URL: https://github.com/apache/druid/pull/16719#discussion_r1673243028


##########
server/src/main/java/org/apache/druid/server/coordinator/duty/KillUnusedSegments.java:
##########
@@ -163,30 +190,44 @@ private DruidCoordinatorRuntimeParams runInternal(final DruidCoordinatorRuntimeP
    * Spawn kill tasks for each datasource in {@code dataSourcesToKill} upto {@code availableKillTaskSlots}.
    */
   private void killUnusedSegments(
-      @Nullable final Collection<String> dataSourcesToKill,
+      final Set<String> dataSourcesToKill,
       final int availableKillTaskSlots,
       final CoordinatorRunStats stats
   )
   {
-    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill) || availableKillTaskSlots <= 0) {
+    if (CollectionUtils.isNullOrEmpty(dataSourcesToKill)) {
+      log.info("Skipping KillUnusedSegments because there are no datasources to kill.");
       stats.add(Stats.Kill.SUBMITTED_TASKS, 0);
       return;
     }
+    final Iterator<String> dataSourcesToKillIterator = this.datasourceIterator.getIterator();
+    final Set<String> remainingDatasourcesToKill = new HashSet<>(dataSourcesToKill);
+    final Set<String> datasourcesKilled = new HashSet<>();
 
-    final Collection<String> remainingDatasourcesToKill = new ArrayList<>(dataSourcesToKill);
     int submittedTasks = 0;
-    for (String dataSource : dataSourcesToKill) {
+    while (dataSourcesToKillIterator.hasNext()) {

Review Comment:
   > I'm not sure if its possible that this.datasourceIterator gets updated by another run of this duty in another thread,
   
   Each duty [group](https://github.com/apache/druid/blob/master/server/src/main/java/org/apache/druid/server/coordinator/DruidCoordinator.java#L505) is allocated a single scheduled executor with only [1](https://github.com/apache/druid/blob/master/server/src/main/java/org/apache/druid/server/coordinator/DruidCoordinator.java#L549) thread.  And each duty within a group run sequentially. So I don't think we can have more than one duty running concurrently at the same time.  
   
   I think that running the duties concurrently would cause race conditions and other issues. Also, I noticed the `RoundRobinServerSelector` [is](https://github.com/apache/druid/blob/master/server/src/main/java/org/apache/druid/server/coordinator/loading/RoundRobinServerSelector.java#L47) `@NotThreadSafe`, which is used by a few coordinator duties. It looks like they're operating under the same assumption?
   
   @kfaraz, could you please confirm this assumption?
   
   I tried to find documentation on how the duties operate but couldn't find much information. I think adding some code/public-facing documentation on this would help clarify this. :-)



-- 
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: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org