You are viewing a plain text version of this content. The canonical link for it is here.
Posted to jira@kafka.apache.org by "gabriellefu (via GitHub)" <gi...@apache.org> on 2026/10/22 18:12:13 UTC

[PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

gabriellefu opened a new pull request, #23924:
URL: https://github.com/apache/kafka/pull/23924

   The classic HA assignor already implementing rack aware, in this pr we implement RackAwareStandbyPicker into balanced assignor
   


-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560465950


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -124,16 +128,18 @@ public GroupAssignment assign(final GroupSpec groupSpec, final TopologyDescriber
         final ProcessTasks[] processesById = processes.values().toArray(new ProcessTasks[0]);
         final int[] period = dealPeriod(processesById);
         dealTasks(processesById, period, 0, statefulTasks, process -> process.statefulActiveTasks);
+        dealTasks(processesById, period, statefulTasks.size(), statelessTasks, process -> process.statelessActiveTasks);

Review Comment:
   \cc @lucasbru @suzhiking 



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568362819


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;

Review Comment:
   Changed to int,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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560821459


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a

Review Comment:
   Something is off... (cf my other comments).
   
   It does not seem that this class is used to model `The per-member quota on active plus standby tasks`... It seems to be something global, not per-member.



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4561056154


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            final List<ProcessTasks> taskHolders = holders.get(task);
+            taskHolders.set(taskHolders.indexOf(source), destination);

Review Comment:
   This is hard to read? Is there any reason why `destination` must be inserted as the exact same index as `source` to replace it? The code would be more readable if we would do:
   ```
   taskHolders.remove(source);
   taksHolders.add(destination);
   ```
   If we switch from `ArrayList` to `LinkedList` it would be equally expensive (one linear scan for either `indexOf` vs `remove`, and an O(1) `set` vs `add` operation), and we would gain code readability?
   



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560523622


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;

Review Comment:
   Why is this a `long`? It seems an `int` would be sufficient?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568207724


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {

Review Comment:
   changed, thanks



##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            final List<ProcessTasks> taskHolders = holders.get(task);
+            taskHolders.set(taskHolders.indexOf(source), destination);
+        }
+    }
+
     /**
      * The tasks placed on one process, and the members the process contributes. The assignment across processes
      * works on this level; the tasks are spread over the members only once the placement is final.
      */
-    private static final class ProcessTasks {
+    static final class ProcessTasks {
         private final String processId;
         private final TreeSet<String> memberIds = new TreeSet<>();
-        private final SortedSet<TaskId> statefulActiveTasks = new TreeSet<>();
+        final SortedSet<TaskId> statefulActiveTasks = new TreeSet<>();
         private final SortedSet<TaskId> statelessActiveTasks = new TreeSet<>();
-        private final SortedSet<TaskId> standbyTasks = new TreeSet<>();
+        final SortedSet<TaskId> standbyTasks = new TreeSet<>();
         // The member of this process that currently holds a task in any role, so that a stateful task can stay on
         // the member that has its state, as the classic client does through the offset sums each thread reports.
         private final Map<TaskId, String> currentOwner = new HashMap<>();
+        private Map<String, String> clientTags = Map.of();
 
-        private ProcessTasks(final String processId) {
+        ProcessTasks(final String processId) {
             this.processId = processId;
         }
 
         private String processId() {
             return processId;
         }
 
-        private void addMember(final String memberId, final MemberAssignmentState currentAssignment) {
+        void addMember(final String memberId,
+                       final Map<String, String> memberClientTags,
+                       final MemberAssignmentState currentAssignment) {

Review Comment:
   updated, 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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "github-actions[bot] (via GitHub) via jira" <ji...@kafka.apache.org>.
github-actions[bot] commented on PR #23924:
URL: https://github.com/apache/kafka/pull/23924#issuecomment-6757924113

   A label of 'needs-attention' was automatically added to this PR in order to raise the
   attention of the committers. Once this issue has been triaged, the `triage` label
   should be removed to prevent this automation from happening again.


-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560560676


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            final List<ProcessTasks> taskHolders = holders.get(task);
+            taskHolders.set(taskHolders.indexOf(source), destination);
+        }
+    }
+
     /**
      * The tasks placed on one process, and the members the process contributes. The assignment across processes
      * works on this level; the tasks are spread over the members only once the placement is final.
      */
-    private static final class ProcessTasks {
+    static final class ProcessTasks {
         private final String processId;
         private final TreeSet<String> memberIds = new TreeSet<>();
-        private final SortedSet<TaskId> statefulActiveTasks = new TreeSet<>();
+        final SortedSet<TaskId> statefulActiveTasks = new TreeSet<>();
         private final SortedSet<TaskId> statelessActiveTasks = new TreeSet<>();
-        private final SortedSet<TaskId> standbyTasks = new TreeSet<>();
+        final SortedSet<TaskId> standbyTasks = new TreeSet<>();
         // The member of this process that currently holds a task in any role, so that a stateful task can stay on
         // the member that has its state, as the classic client does through the offset sums each thread reports.
         private final Map<TaskId, String> currentOwner = new HashMap<>();
+        private Map<String, String> clientTags = Map.of();
 
-        private ProcessTasks(final String processId) {
+        ProcessTasks(final String processId) {
             this.processId = processId;
         }
 
         private String processId() {
             return processId;
         }
 
-        private void addMember(final String memberId, final MemberAssignmentState currentAssignment) {
+        void addMember(final String memberId,
+                       final Map<String, String> memberClientTags,
+                       final MemberAssignmentState currentAssignment) {

Review Comment:
   ```suggestion
           void addMember(
               final String memberId,
               final Map<String, String> memberClientTags,
               final MemberAssignmentState currentAssignment
           ) {
   ```



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4542910715


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -124,16 +128,18 @@ public GroupAssignment assign(final GroupSpec groupSpec, final TopologyDescriber
         final ProcessTasks[] processesById = processes.values().toArray(new ProcessTasks[0]);
         final int[] period = dealPeriod(processesById);
         dealTasks(processesById, period, 0, statefulTasks, process -> process.statefulActiveTasks);
+        dealTasks(processesById, period, statefulTasks.size(), statelessTasks, process -> process.statelessActiveTasks);

Review Comment:
   change it to assign stateless active task before standby task, which improve the balanced



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "github-actions[bot] (via GitHub) via jira" <ji...@kafka.apache.org>.
github-actions[bot] commented on PR #23924:
URL: https://github.com/apache/kafka/pull/23924#issuecomment-6538250126

   A label of 'needs-attention' was automatically added to this PR in order to raise the
   attention of the committers. Once this issue has been triaged, the `triage` label
   should be removed to prevent this automation from happening again.


-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560581814


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {
+        final Map<TaskId, ProcessTasks> activeTaskToProcess = Utils.newHashMap(statefulTasks.size());
+        for (final ProcessTasks process : processes) {
+            for (final TaskId task : process.statefulActiveTasks) {
+                activeTaskToProcess.put(task, process);
+            }
+        }
+
+        final TaskQuota quota = new TaskQuota(processes, (long) statefulTasks.size() * numStandbyReplicas);
+        // The processes are in sorted order of their ID, so a load tie goes to the smaller ID, as in BY_ASSIGNED_LOAD.
+        final RackAwareStandbyPicker<ProcessTasks> picker = new RackAwareStandbyPicker<>(
+            rackAwareAssignmentTags,
+            processes,
+            process -> process.clientTags,
+            ProcessTasks::assignedTaskLoad,
+            quota::hasRoom
+        );
+        final Map<TaskId, Integer> rackAwareStandbys = Utils.newHashMap(statefulTasks.size());
+        for (final TaskId task : statefulTasks) {
+            picker.startTask(List.of(activeTaskToProcess.get(task)));
+            int placed = 0;
+            while (placed < numStandbyReplicas) {

Review Comment:
   Similar question as for the "sticky" case -- would it make sense to flip the nested-loop from:
   ```
   for each task
     for R replicas
       assign standby
   ```
   to
   ```
   for R replicas
     for each task
       assign standby
   ```



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560512428


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();

Review Comment:
   Is `totalMembersWithTaskCapacity` not the same for all `TaskQuota` instances? Why do we compute it inside this constructor? It seems we can compute it once for an "assign()" call, and it should never change with one "assign()" ?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4561001627


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {

Review Comment:
   It seems this method _moves_ the given task from the source process to the destination process, ie, update the internal data structures to reflect the move.
   
   Should it be called `move(...)` instead of `moved(...)`?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560482482


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {

Review Comment:
   This formatting give better (ie smaller) diffs going forward, if we change the method signature or name



##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {

Review Comment:
   This formatting gives better (ie smaller) diffs going forward, if we change the method signature or name



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560918447


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:

Review Comment:
   > The processes holding each stateful task
   
   Cannot follow?
   
   It describes the class mainly as a container, but that not the point. Sure, there is a `Map<TaskId, List<ProcessTasks>> holders` but that in implementation detail, and it's also a Map keyed by task-id, not process-id.



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560968291


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.

Review Comment:
   > The source's value stays
   
   What does "stays" mean? The source is a process, right? The client-tag config of a process is fixed. Why would it "go away" or "stay" ?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568577949


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();

Review Comment:
   totalMembersWithTaskCapacity is the number of members still have capacity and the totalTasksPerMember=  ceil(totalTasks / totalMembersWithTaskCapacity), once a member reach totalTasksPerMember, totalMembersWithTaskCapacity-=1, and totalTasks-=totalTasksPerMember, and totalTasksPerMember will also be updated



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568365439


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -300,10 +366,14 @@ private static ProcessTasks pollLeastLoadedProcessWithoutTask(final PriorityQueu
 
     /**
      * Moves tasks from more loaded to less loaded processes until no single move reduces the skew of the per-member
-     * task load any further. A task is never moved to a process that already holds it as active or standby task.
+     * task load any further. A task is never moved to a process that already holds it as active or standby task, nor,
+     * with {@code rackDiversity}, so that its rack diversity drops.
+     *
+     * @param rackDiversity The rack diversity of the tasks, or {@code null} without {@code rack.aware.assignment.tags}.
      */
-    private static void balanceTasksOverProcesses(final Collection<ProcessTasks> processes,
-                                                  final Function<ProcessTasks, SortedSet<TaskId>> tasksToBalance) {
+    static void balanceTasksOverProcesses(final Collection<ProcessTasks> processes,
+                                          final Function<ProcessTasks, SortedSet<TaskId>> tasksToBalance,
+                                          final RackDiversity rackDiversity) {

Review Comment:
   updated, 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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560552622


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {
+        final Map<TaskId, ProcessTasks> activeTaskToProcess = Utils.newHashMap(statefulTasks.size());
+        for (final ProcessTasks process : processes) {
+            for (final TaskId task : process.statefulActiveTasks) {
+                activeTaskToProcess.put(task, process);
+            }
+        }
+
+        final TaskQuota quota = new TaskQuota(processes, (long) statefulTasks.size() * numStandbyReplicas);

Review Comment:
   Why do we have only one instance of `TaskQuota`? Don't we need one instance per member?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560918447


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:

Review Comment:
   > The processes holding each stateful task
   
   Cannot follow?
   
   



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560479103


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {

Review Comment:
   nit
   ```suggestion
       private static Map<TaskId, Integer> assignRackAwareStandbys(
           final Collection<ProcessTasks> processes,
           final SortedSet<TaskId> statefulTasks,
           final int numStandbyReplicas,
           final List<String> rackAwareAssignmentTags
       ) {
   ```



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568945401


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {

Review Comment:
   sounds good, ill change 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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568877968


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.

Review Comment:
   it's like there are two set, the first set is all the tag values (all other holders has)+(source process has) and the other set is (all other holders has)+(destination process has), the stay and go away means the change from the first set to the second set. None means this new value not in the (all other holders has), so it will add new value to the set(makes the second set lexicographically higher than the first one )



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560487403


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -300,10 +366,14 @@ private static ProcessTasks pollLeastLoadedProcessWithoutTask(final PriorityQueu
 
     /**
      * Moves tasks from more loaded to less loaded processes until no single move reduces the skew of the per-member
-     * task load any further. A task is never moved to a process that already holds it as active or standby task.
+     * task load any further. A task is never moved to a process that already holds it as active or standby task, nor,
+     * with {@code rackDiversity}, so that its rack diversity drops.
+     *
+     * @param rackDiversity The rack diversity of the tasks, or {@code null} without {@code rack.aware.assignment.tags}.
      */
-    private static void balanceTasksOverProcesses(final Collection<ProcessTasks> processes,
-                                                  final Function<ProcessTasks, SortedSet<TaskId>> tasksToBalance) {
+    static void balanceTasksOverProcesses(final Collection<ProcessTasks> processes,
+                                          final Function<ProcessTasks, SortedSet<TaskId>> tasksToBalance,
+                                          final RackDiversity rackDiversity) {

Review Comment:
   ```suggestion
       static void balanceTasksOverProcesses(
           final Collection<ProcessTasks> processes,
           final Function<ProcessTasks, SortedSet<TaskId>> tasksToBalance,
           final RackDiversity rackDiversity
       ) {
   ```



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4561056154


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.
+                boolean sourceValueStays = sourceValue == null;
+                boolean destinationValueNew = destinationValue != null;
+                for (final ProcessTasks holder : holders.get(task)) {
+                    if (holder != source) {
+                        final String value = holder.clientTags.get(key);
+                        sourceValueStays |= Objects.equals(value, sourceValue);
+                        destinationValueNew &= !Objects.equals(value, destinationValue);
+                    }
+                }
+                // The first key whose distinct values change decides: a gain allows the move, a loss blocks it.
+                if (sourceValueStays && destinationValueNew) {
+                    return true;
+                }
+                if (!sourceValueStays && !destinationValueNew) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private void moved(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            final List<ProcessTasks> taskHolders = holders.get(task);
+            taskHolders.set(taskHolders.indexOf(source), destination);

Review Comment:
   This is hard to read? Is there any reason why `destination` must be inserted as the exact same index as `source` to replace it? The code would be more readable if we would do:
   ```
   taskHolders.remove(source);
   taksHolders.add(destination);
   ```
   If we switch from `ArrayList` to `LinkedList` it would be equally expensive (one linear scan for either `indexOf` vs `remove`, and an O(1) `set` vs `add` operation, but we would gain code readability?
   



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560968291


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:
+     * the first tag key, in {@code rack.aware.assignment.tags} order, whose distinct values among the holders change
+     * may not lose one. A missing value counts as no value.
+     */
+    static final class RackDiversity {
+        private final List<String> tagKeys;
+        private final Map<TaskId, List<ProcessTasks>> holders;
+
+        RackDiversity(final Collection<ProcessTasks> processes, final int numStatefulTasks, final List<String> tagKeys) {
+            this.tagKeys = tagKeys;
+            this.holders = Utils.newHashMap(numStatefulTasks);
+            for (final ProcessTasks process : processes) {
+                for (final TaskId task : process.statefulActiveTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+                for (final TaskId task : process.standbyTasks) {
+                    holders.computeIfAbsent(task, taskId -> new ArrayList<>()).add(process);
+                }
+            }
+        }
+
+        /** Whether moving the task's standby from source to destination would not decrease its rack diversity. */
+        private boolean wouldNotDecrease(final TaskId task, final ProcessTasks source, final ProcessTasks destination) {
+            for (final String key : tagKeys) {
+                final String sourceValue = source.clientTags.get(key);
+                final String destinationValue = destination.clientTags.get(key);
+                if (Objects.equals(sourceValue, destinationValue)) {
+                    continue;
+                }
+                // The source's value stays if another holder has it; the destination's value is new if none has it.

Review Comment:
   > The source's value stays
   
   What does "stays" mean? The source is a process, right? The client-tag config of a process is fixed. Why would it "go away" or "stay" ?
   
   > the destination's value is new if none has it
   
   What does "is new" mean? What does "if none has it" mean?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568636420


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();

Review Comment:
   there's only one TaskQuota for every member, but it will change, but it starts with total number of members in the every process



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568832579


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:

Review Comment:
   i have updated it, so for each task, if one of its replica go to a least-loaded member, but the rack diversity decrease, this move will be prohibited. two diversities are compared lexicographically in rack.aware.assignment.tags order



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4570482712


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +453,149 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The upper bound on how many active plus standby tasks any member may hold, one value for the whole group: all
+     * tasks over all members, rounded up. When a member reaches it, the member and its tasks are taken out and the
+     * bound is computed again from the rest, which can lower it for the others.

Review Comment:
   Nit: Is "The upper bound on how many active plus standby tasks any member may hold" correct? I believe it only gates the rack-aware pass. The tag-blind fill afterwards ignores it, so a member can end up above it. Something like "...any member may take in the rack-aware pass" would be accurate.



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on PR #23924:
URL: https://github.com/apache/kafka/pull/23924#issuecomment-6638775122

   the comparison of this branch change with the balanced assignor on trunk in testbed 
   ### Testbed results
   
   Run with the randomized testbed from #23556 (`new TaskAssignorTestbed(new BalancedTaskAssignor())`, default base seed 42) on 9e7183d6be: SMALL has 300 scenarios, LARGE has 30. A cell is `trunk → this PR`, averaged over the scenarios, and a single value means unchanged. **Initial** is the assignment from empty; **rebalance** is the assignment after a random change (1291 SMALL, 131 LARGE), graded against the assignment before the change. LARGE scenarios use only the `region` and `zone` keys. Balance rows are max − min (lower is better), "kept" and "moved" rows are fractions (1.0 = all), and "standby tasks placed without state" is a count per rebalance. Trunk does not read the tags, so its numbers are the same with and without them.
   
   **Rack awareness**
   
   | metric | SMALL initial | SMALL rebalance | LARGE initial | LARGE rebalance |
   |---|---|---|---|---|
   | distinct tag values [region] | 0.786 → 0.876 | 0.790 → 0.875 | 0.762 → 0.882 | 0.762 → 0.881 |
   | distinct tag values [zone] | 0.742 → 0.838 | 0.769 → 0.854 | 0.785 → 0.887 | 0.782 → 0.890 |
   | distinct tag values [rack] | 0.756 → 0.854 | 0.782 → 0.873 | n/a | n/a |
   | tasks lost when one [region] value fails | 0.320 → 0.182 | 0.327 → 0.199 | 0.412 → 0.191 | 0.393 → 0.183 |
   | tasks lost when one [zone] value fails | 0.421 → 0.253 | 0.362 → 0.221 | 0.390 → 0.194 | 0.392 → 0.186 |
   | tasks lost when one [rack] value fails | 0.326 → 0.146 | 0.336 → 0.166 | n/a | n/a |
   
   The share of stateful tasks that lose their state when one tag value fails drops by 39–55%.
   
   **Balance**
   
   | metric | SMALL initial | SMALL rebalance | LARGE initial | LARGE rebalance |
   |---|---|---|---|---|
   | task balance per member | 1.170 → 1.143 | 1.527 → 1.479 | 1.500 → 1.667 | 1.573 → 1.702 |
   | load balance per process | 0.729 → 0.691 | 1.085 → 1.055 | 0.968 → 1.197 | 1.086 → 1.286 |
   | active balance per member | 1.027 → 1.007 | 1.082 → 1.076 | 1.533 | 1.763 → 1.756 |
   | stateful active balance per member | 0.747 | 0.751 | 1.000 | 1.000 |
   | active load balance per process | 0.355 | 0.350 | 0.353 | 0.364 |
   | stateful active load balance per process | 0.299 | 0.320 | 0.376 | 0.411 |
   | subtopology balance | 0.047 → 0.067 | 0.272 → 0.263 | 0.267 → 0.400 | 1.298 → 1.328 |
   
   The active tasks are placed across processes as on trunk. On LARGE, the standbys cost some balance to reach the diversity above: task balance per member +0.13–0.17 and load balance per process +0.20–0.23. SMALL is slightly better than trunk.
   
   **Stickiness**
   
   | metric | SMALL rebalance | LARGE rebalance |
   |---|---|---|
   | stateful active tasks kept on member | 0.608 → 0.607 | 0.462 |
   | stateful active tasks moved to a process with state | 0.193 → 0.191 | 0.084 |
   | stateful active tasks moved to a process without state | 0.199 → 0.201 | 0.454 → 0.455 |
   | active tasks kept on member | 0.492 → 0.488 | 0.369 → 0.366 |
   | standby tasks placed without state | 2.153 → 2.112 | 341.534 → 342.244 |
   
   Unchanged within noise. Rounds to converge and not converged are identical to trunk (see all metrics).
   
   **Without rack-aware assignment tags**
   
   This PR also deals the stateless active tasks before the standbys when no tags are set (trunk deals them after), so the standbys are placed by the load of all active tasks. The stateless tasks still continue the deal of the stateful ones, so the active placement across processes does not change.
   
   | metric | SMALL initial | SMALL rebalance | LARGE initial | LARGE rebalance |
   |---|---|---|---|---|
   | task balance per member | 1.170 → 1.080 | 1.527 → 1.405 | 1.500 → 1.300 | 1.573 → 1.313 |
   | load balance per process | 0.729 → 0.614 | 1.085 → 0.968 | 0.968 → 0.790 | 1.086 → 0.814 |
   | active balance per member | 1.027 → 1.020 | 1.082 | 1.533 → 1.433 | 1.763 → 1.679 |
   | subtopology balance | 0.047 → 0.063 | 0.272 → 0.276 | 0.267 → 0.367 | 1.298 → 1.237 |
   | active tasks kept on member | n/a | 0.492 → 0.489 | n/a | 0.369 → 0.364 |
   | standby tasks placed without state | n/a | 2.153 → 2.619 | n/a | 341.534 → 377.046 |
   
   Task balance per member improves by 8–17% and load balance per process by 11–25%. The cost is more standbys placed without state (+10% on LARGE, +22% on SMALL), since the standbys now follow the stateless deal, which does not look at the previous assignment. The other rows, including the rack rows (here the assignor does not see the tags), move by 0.021 at most.
   
   <details>
   <summary>All metrics, with rack-aware assignment tags</summary>
   
   | metric | SMALL initial | SMALL rebalance | LARGE initial | LARGE rebalance |
   |---|---|---|---|---|
   | stateful active balance per member | 0.747 | 0.751 | 1.000 | 1.000 |
   | active balance per member | 1.027 → 1.007 | 1.082 → 1.076 | 1.533 | 1.763 → 1.756 |
   | task balance per member | 1.170 → 1.143 | 1.527 → 1.479 | 1.500 → 1.667 | 1.573 → 1.702 |
   | stateful active load balance per process | 0.299 | 0.320 | 0.376 | 0.411 |
   | active load balance per process | 0.355 | 0.350 | 0.353 | 0.364 |
   | load balance per process | 0.729 → 0.691 | 1.085 → 1.055 | 0.968 → 1.197 | 1.086 → 1.286 |
   | subtopology balance | 0.047 → 0.067 | 0.272 → 0.263 | 0.267 → 0.400 | 1.298 → 1.328 |
   | tasks lost when one [region] value fails | 0.320 → 0.182 | 0.327 → 0.199 | 0.412 → 0.191 | 0.393 → 0.183 |
   | tasks lost when one [zone] value fails | 0.421 → 0.253 | 0.362 → 0.221 | 0.390 → 0.194 | 0.392 → 0.186 |
   | tasks lost when one [rack] value fails | 0.326 → 0.146 | 0.336 → 0.166 | n/a | n/a |
   | distinct tag values [region] | 0.786 → 0.876 | 0.790 → 0.875 | 0.762 → 0.882 | 0.762 → 0.881 |
   | distinct tag values [zone] | 0.742 → 0.838 | 0.769 → 0.854 | 0.785 → 0.887 | 0.782 → 0.890 |
   | distinct tag values [rack] | 0.756 → 0.854 | 0.782 → 0.873 | n/a | n/a |
   | stateful active tasks kept on member | n/a | 0.608 → 0.607 | n/a | 0.462 |
   | stateful active tasks moved to a process with state | n/a | 0.193 → 0.191 | n/a | 0.084 |
   | stateful active tasks moved to a process without state | n/a | 0.199 → 0.201 | n/a | 0.454 → 0.455 |
   | active tasks kept on member | n/a | 0.492 → 0.488 | n/a | 0.369 → 0.366 |
   | standby tasks placed without state | n/a | 2.153 → 2.112 | n/a | 341.534 → 342.244 |
   | rounds to converge | 1.000 | 0.990 | 1.000 | 1.000 |
   | not converged | 0.000 | 0.000 | 0.000 | 0.000 |
   
   </details>
   
   <details>
   <summary>All metrics, without rack-aware assignment tags</summary>
   
   | metric | SMALL initial | SMALL rebalance | LARGE initial | LARGE rebalance |
   |---|---|---|---|---|
   | stateful active balance per member | 0.747 | 0.751 | 1.000 | 1.000 |
   | active balance per member | 1.027 → 1.020 | 1.082 | 1.533 → 1.433 | 1.763 → 1.679 |
   | task balance per member | 1.170 → 1.080 | 1.527 → 1.405 | 1.500 → 1.300 | 1.573 → 1.313 |
   | stateful active load balance per process | 0.299 | 0.320 | 0.376 | 0.411 |
   | active load balance per process | 0.355 | 0.350 | 0.353 | 0.364 |
   | load balance per process | 0.729 → 0.614 | 1.085 → 0.968 | 0.968 → 0.790 | 1.086 → 0.814 |
   | subtopology balance | 0.047 → 0.063 | 0.272 → 0.276 | 0.267 → 0.367 | 1.298 → 1.237 |
   | tasks lost when one [region] value fails | 0.320 → 0.335 | 0.327 → 0.332 | 0.412 → 0.406 | 0.393 → 0.394 |
   | tasks lost when one [zone] value fails | 0.421 → 0.409 | 0.362 → 0.351 | 0.390 → 0.396 | 0.392 → 0.384 |
   | tasks lost when one [rack] value fails | 0.326 → 0.327 | 0.336 → 0.315 | n/a | n/a |
   | distinct tag values [region] | 0.786 → 0.780 | 0.790 → 0.787 | 0.762 → 0.765 | 0.762 |
   | distinct tag values [zone] | 0.742 → 0.752 | 0.769 → 0.772 | 0.785 → 0.781 | 0.782 → 0.785 |
   | distinct tag values [rack] | 0.756 → 0.759 | 0.782 → 0.795 | n/a | n/a |
   | stateful active tasks kept on member | n/a | 0.608 | n/a | 0.462 → 0.461 |
   | stateful active tasks moved to a process with state | n/a | 0.193 → 0.192 | n/a | 0.084 |
   | stateful active tasks moved to a process without state | n/a | 0.199 → 0.200 | n/a | 0.454 |
   | active tasks kept on member | n/a | 0.492 → 0.489 | n/a | 0.369 → 0.364 |
   | standby tasks placed without state | n/a | 2.153 → 2.619 | n/a | 341.534 → 377.046 |
   | rounds to converge | 1.000 | 0.990 | 1.000 | 1.000 |
   | not converged | 0.000 | 0.000 | 0.000 | 0.000 |
   
   </details>
   


-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on PR #23924:
URL: https://github.com/apache/kafka/pull/23924#issuecomment-6639315374

   ### JMH results
   
   Run with `StreamsAssignorBenchmark` (`assignorType=BALANCED`) on 9e7183d6be, and with the same benchmark on trunk's `BalancedTaskAssignor`, for the four tag layouts only. Trunk does not read the tags, so its numbers are the tag-blind cost of the same group. 1000 members, 100 subtopologies with 100 partitions each (10,000 tasks), no reported offsets, 1 fork, 3 × 2s warmup, 5 × 2s measurement. A cell is the average time of one assignment in ms, `trunk → this PR`, with the error where it is above 10% of the score. **Full** is the assignment from empty; **incremental** is the assignment after one member joins. Each process takes the value of every tag key round-robin, and `host` has a value of its own per process.
   
   **1000 processes (1 member per process)**
   
   | rack.aware.assignment.tags | full, 1 standby | full, 2 standbys | incremental, 1 standby | incremental, 2 standbys |
   |---|---|---|---|---|
   | cluster, zone | 9.65 → 13.89 | 21.14 → 24.39 | 10.22 → 14.89 | 21.70 → 21.12 |
   | cluster, zone, rack | 9.61 → 11.40 | 21.74 → 23.12 | 10.11 → 12.43 | 24.35 → 21.75 ± 2.66 |
   | cluster, zone, host | 9.32 → 9.59 | 21.91 → 25.02 | 10.22 → 10.60 | 24.32 → 25.05 |
   | region, cluster, zone, rack, host | 9.25 → 10.13 | 20.28 → 21.67 | 10.30 → 10.89 | 23.22 → 28.59 |
   
   **20 processes (50 members per process)**
   
   | rack.aware.assignment.tags | full, 1 standby | full, 2 standbys | incremental, 1 standby | incremental, 2 standbys |
   |---|---|---|---|---|
   | cluster, zone | 3.78 → 3.32 | 5.64 → 5.13 | 4.04 ± 0.41 → 3.97 | 8.48 → 6.22 |
   | cluster, zone, rack | 3.71 → 3.55 | 8.69 → 5.35 | 7.05 → 4.30 | 8.65 → 6.38 |
   | cluster, zone, host | 3.69 → 3.46 | 8.72 → 5.20 | 4.04 → 4.16 | 9.85 → 6.42 |
   | region, cluster, zone, rack, host | 3.72 → 3.80 | 8.70 → 5.81 | 6.92 → 4.51 | 6.07 → 7.21 |
   
   Since trunk does the same work for every tag layout, its four rows in a column show the run-to-run noise: up to 12% apart with 1000 processes, but up to 1.7× apart with 20 processes (for example 4.04 and 7.05 ms for incremental with 1 standby).
   
   With 1000 single-member processes and 1 standby, `cluster, zone` costs the most (+44–46%, 13.9–14.9 ms), `cluster, zone, rack` +19–23%, and the layouts with a host key +3–9%. With 2 standbys the change is −11% to +23%, and the slowest assignment takes 28.6 ms (incremental, five keys; 23.2 ms on trunk). With 20 processes this PR takes 3.3–7.2 ms against 3.7–9.8 ms on trunk; trunk's spread there is too large for one fork to show a difference.
   
   <details>
   <summary>All results</summary>
   
   ```
   ./jmh-benchmarks/jmh.sh 'StreamsAssignor(Trunk)?Benchmark\.doAssignment' \
       -f 1 -wi 3 -w 2s -i 5 -r 2s \
       -p assignorType=BALANCED -p memberCount=1000 -p partitionCount=100 -p subtopologyCount=100 \
       -p reportedOffsets=NONE -p membersPerProcess=1,50 -p assignmentType=FULL,INCREMENTAL -p standbyReplicas=1,2 \
       -p rackAwareTags=CLUSTER_AND_ZONE,CLUSTER_ZONE_AND_RACK,CLUSTER_ZONE_AND_HOST,REGION_CLUSTER_ZONE_RACK_AND_HOST
   ```
   
   `StreamsAssignorTrunkBenchmark` is a local copy of `StreamsAssignorBenchmark` that runs trunk's `BalancedTaskAssignor`. Score ± error in ms.
   
   ```
   members per process type        standbys rackAwareTags                      side                ms/op
                     1 FULL               1 CLUSTER_AND_ZONE                   trunk       9.646 ± 0.427
                     1 FULL               1 CLUSTER_AND_ZONE                   this PR    13.888 ± 0.441
                     1 FULL               1 CLUSTER_ZONE_AND_RACK              trunk       9.609 ± 0.387
                     1 FULL               1 CLUSTER_ZONE_AND_RACK              this PR    11.400 ± 0.607
                     1 FULL               1 CLUSTER_ZONE_AND_HOST              trunk       9.315 ± 0.299
                     1 FULL               1 CLUSTER_ZONE_AND_HOST              this PR     9.595 ± 0.471
                     1 FULL               1 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk       9.255 ± 0.421
                     1 FULL               1 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR    10.128 ± 0.533
                     1 FULL               2 CLUSTER_AND_ZONE                   trunk      21.139 ± 0.757
                     1 FULL               2 CLUSTER_AND_ZONE                   this PR    24.386 ± 1.817
                     1 FULL               2 CLUSTER_ZONE_AND_RACK              trunk      21.737 ± 1.436
                     1 FULL               2 CLUSTER_ZONE_AND_RACK              this PR    23.117 ± 1.072
                     1 FULL               2 CLUSTER_ZONE_AND_HOST              trunk      21.911 ± 0.699
                     1 FULL               2 CLUSTER_ZONE_AND_HOST              this PR    25.016 ± 1.224
                     1 FULL               2 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk      20.283 ± 0.857
                     1 FULL               2 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR    21.674 ± 1.834
                     1 INCREMENTAL        1 CLUSTER_AND_ZONE                   trunk      10.222 ± 0.418
                     1 INCREMENTAL        1 CLUSTER_AND_ZONE                   this PR    14.892 ± 0.205
                     1 INCREMENTAL        1 CLUSTER_ZONE_AND_RACK              trunk      10.108 ± 0.530
                     1 INCREMENTAL        1 CLUSTER_ZONE_AND_RACK              this PR    12.434 ± 0.042
                     1 INCREMENTAL        1 CLUSTER_ZONE_AND_HOST              trunk      10.224 ± 0.309
                     1 INCREMENTAL        1 CLUSTER_ZONE_AND_HOST              this PR    10.596 ± 0.127
                     1 INCREMENTAL        1 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk      10.303 ± 0.246
                     1 INCREMENTAL        1 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR    10.888 ± 0.111
                     1 INCREMENTAL        2 CLUSTER_AND_ZONE                   trunk      21.704 ± 1.033
                     1 INCREMENTAL        2 CLUSTER_AND_ZONE                   this PR    21.117 ± 1.173
                     1 INCREMENTAL        2 CLUSTER_ZONE_AND_RACK              trunk      24.348 ± 1.255
                     1 INCREMENTAL        2 CLUSTER_ZONE_AND_RACK              this PR    21.745 ± 2.661
                     1 INCREMENTAL        2 CLUSTER_ZONE_AND_HOST              trunk      24.319 ± 2.018
                     1 INCREMENTAL        2 CLUSTER_ZONE_AND_HOST              this PR    25.053 ± 1.879
                     1 INCREMENTAL        2 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk      23.217 ± 1.284
                     1 INCREMENTAL        2 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR    28.588 ± 0.916
                    50 FULL               1 CLUSTER_AND_ZONE                   trunk       3.781 ± 0.085
                    50 FULL               1 CLUSTER_AND_ZONE                   this PR     3.321 ± 0.200
                    50 FULL               1 CLUSTER_ZONE_AND_RACK              trunk       3.706 ± 0.054
                    50 FULL               1 CLUSTER_ZONE_AND_RACK              this PR     3.548 ± 0.143
                    50 FULL               1 CLUSTER_ZONE_AND_HOST              trunk       3.688 ± 0.022
                    50 FULL               1 CLUSTER_ZONE_AND_HOST              this PR     3.462 ± 0.124
                    50 FULL               1 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk       3.716 ± 0.051
                    50 FULL               1 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR     3.801 ± 0.172
                    50 FULL               2 CLUSTER_AND_ZONE                   trunk       5.636 ± 0.205
                    50 FULL               2 CLUSTER_AND_ZONE                   this PR     5.126 ± 0.160
                    50 FULL               2 CLUSTER_ZONE_AND_RACK              trunk       8.692 ± 0.196
                    50 FULL               2 CLUSTER_ZONE_AND_RACK              this PR     5.349 ± 0.202
                    50 FULL               2 CLUSTER_ZONE_AND_HOST              trunk       8.722 ± 0.107
                    50 FULL               2 CLUSTER_ZONE_AND_HOST              this PR     5.203 ± 0.215
                    50 FULL               2 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk       8.700 ± 0.127
                    50 FULL               2 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR     5.814 ± 0.333
                    50 INCREMENTAL        1 CLUSTER_AND_ZONE                   trunk       4.042 ± 0.409
                    50 INCREMENTAL        1 CLUSTER_AND_ZONE                   this PR     3.966 ± 0.077
                    50 INCREMENTAL        1 CLUSTER_ZONE_AND_RACK              trunk       7.048 ± 0.303
                    50 INCREMENTAL        1 CLUSTER_ZONE_AND_RACK              this PR     4.298 ± 0.300
                    50 INCREMENTAL        1 CLUSTER_ZONE_AND_HOST              trunk       4.042 ± 0.132
                    50 INCREMENTAL        1 CLUSTER_ZONE_AND_HOST              this PR     4.156 ± 0.282
                    50 INCREMENTAL        1 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk       6.925 ± 0.253
                    50 INCREMENTAL        1 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR     4.506 ± 0.163
                    50 INCREMENTAL        2 CLUSTER_AND_ZONE                   trunk       8.482 ± 0.247
                    50 INCREMENTAL        2 CLUSTER_AND_ZONE                   this PR     6.221 ± 0.295
                    50 INCREMENTAL        2 CLUSTER_ZONE_AND_RACK              trunk       8.647 ± 0.518
                    50 INCREMENTAL        2 CLUSTER_ZONE_AND_RACK              this PR     6.382 ± 0.175
                    50 INCREMENTAL        2 CLUSTER_ZONE_AND_HOST              trunk       9.848 ± 0.231
                    50 INCREMENTAL        2 CLUSTER_ZONE_AND_HOST              this PR     6.417 ± 0.368
                    50 INCREMENTAL        2 REGION_CLUSTER_ZONE_RACK_AND_HOST  trunk       6.070 ± 0.241
                    50 INCREMENTAL        2 REGION_CLUSTER_ZONE_RACK_AND_HOST  this PR     7.213 ± 0.286
   ```
   
   </details>
   


-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560454574


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -124,16 +128,18 @@ public GroupAssignment assign(final GroupSpec groupSpec, final TopologyDescriber
         final ProcessTasks[] processesById = processes.values().toArray(new ProcessTasks[0]);
         final int[] period = dealPeriod(processesById);
         dealTasks(processesById, period, 0, statefulTasks, process -> process.statefulActiveTasks);
+        dealTasks(processesById, period, statefulTasks.size(), statelessTasks, process -> process.statelessActiveTasks);

Review Comment:
   Hmmm... This is something we should explore more. Seems we don't have a uniform strategy, and it's not clear to me if one order is strictly better than the other, or if it really depends on "sticky" vs "balances" which one is better...
   
   My gut feeling is, that placing all stateful task (first active, than standby) before all stateless tasks might better: if should distribute overall state better, and lead to fewer state movements during a rebalance (if active tasks are not assigned yet, there is more freedom to assign standbys "sticky" because there is no members with exhausted capacity yet).
   
   In classic, HA-assignor uses active-stateful, standby, stateless order. Both sticky (new and legacy) use active-stateful, stateless, standby order.
   
   The new sticky for "streams" also uses active-stateful, stateless, standby order.
   
   Thoughts?



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560884641


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {

Review Comment:
   It seems `taskNo` is a misleading name? We are passing in the _count_ of currently assigned task right?
   
   It currently sound like "task number 5" if, we pass in the number of a task.



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "mjsax (via GitHub) via jira" <ji...@kafka.apache.org>.
mjsax commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4560918447


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a
+     * member that reaches it leaves with its tasks. The members of a process are levelled once the placement is final,
+     * so the member that takes the n-th task of a process with c members reaches ceil(n / c).
+     */
+    private static final class TaskQuota {
+        private int totalMembersWithTaskCapacity;
+        private long totalTasks;
+        private int totalTasksPerMember;
+
+        /**
+         * @param standbysToPlace The standbys still to place; the tasks the processes hold count as placed one by one.
+         */
+        private TaskQuota(final Collection<ProcessTasks> processes, final long standbysToPlace) {
+            totalTasks = standbysToPlace;
+            for (final ProcessTasks process : processes) {
+                totalMembersWithTaskCapacity += process.capacity();
+                totalTasks += process.assignedTaskCount();
+            }
+            totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            for (final ProcessTasks process : processes) {
+                for (int taskCount = 1; taskCount <= process.assignedTaskCount(); taskCount++) {
+                    maybeUpdateTotalTasksPerMember(memberTaskCount(taskCount, process.capacity()));
+                }
+            }
+        }
+
+        /** Whether one of the members of the process is below the quota. */
+        private boolean hasRoom(final ProcessTasks process) {
+            return process.assignedTaskCount() < (long) process.capacity() * totalTasksPerMember;
+        }
+
+        private void maybeUpdateTotalTasksPerMember(final int taskNo) {
+            if (taskNo == totalTasksPerMember) {
+                totalMembersWithTaskCapacity--;
+                totalTasks -= taskNo;
+                totalTasksPerMember = computeTasksPerMember(totalTasks, totalMembersWithTaskCapacity);
+            }
+        }
+
+        private static int computeTasksPerMember(final long numberOfTasks, final int numberOfMembers) {
+            return numberOfMembers == 0 ? 0 : (int) ((numberOfTasks + numberOfMembers - 1) / numberOfMembers);
+        }
+
+        /** The task count of the member that takes the {@code processTaskCount}-th task of a levelled process. */
+        private static int memberTaskCount(final int processTaskCount, final int capacity) {
+            return (processTaskCount + capacity - 1) / capacity;
+        }
+    }
+
+    /**
+     * The processes holding each stateful task, to tell whether moving a standby lowers the rack diversity of its task:

Review Comment:
   > The processes holding each stateful task
   
   Cannot follow?
   
   It describes the class mainly as a container, but that not the point. Sure, there is a `Map<TaskId, List<ProcessTasks>> holders` but that in implementation detail.



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568647977


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -273,7 +283,63 @@ private static void assignStandbyReplicaTasks(final Collection<ProcessTasks> pro
                 tasksShortOfReplicas, statefulTasks.size(), numStandbyReplicas, missingReplicas, processes.size());
         }
 
-        balanceTasksOverProcesses(processes, process -> process.standbyTasks);
+        balanceTasksOverProcesses(
+            processes,
+            process -> process.standbyTasks,
+            rackAwareAssignmentTags.isEmpty() ? null : new RackDiversity(processes, statefulTasks.size(), rackAwareAssignmentTags)
+        );
+    }
+
+    /**
+     * Places the standby tasks that make their task more rack-diverse, each on the least loaded process among the
+     * most diverse ones, and returns the number placed per task. A process takes them while one of its members is
+     * below the per-member task quota.
+     */
+    private static Map<TaskId, Integer> assignRackAwareStandbys(final Collection<ProcessTasks> processes,
+                                                               final SortedSet<TaskId> statefulTasks,
+                                                               final int numStandbyReplicas,
+                                                               final List<String> rackAwareAssignmentTags) {
+        final Map<TaskId, ProcessTasks> activeTaskToProcess = Utils.newHashMap(statefulTasks.size());
+        for (final ProcessTasks process : processes) {
+            for (final TaskId task : process.statefulActiveTasks) {
+                activeTaskToProcess.put(task, process);
+            }
+        }
+
+        final TaskQuota quota = new TaskQuota(processes, (long) statefulTasks.size() * numStandbyReplicas);

Review Comment:
   cause it's taskquota is for the whole group which is the upper bound of how many each member can at most hold right now.(for those haven't full yet)



-- 
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: jira-unsubscribe@kafka.apache.org

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


Re: [PR] KAFKA-20999: [3/N] Add rack-aware standby task assignment to balanced assignor [kafka]

Posted by "gabriellefu (via GitHub) via jira" <ji...@kafka.apache.org>.
gabriellefu commented on code in PR #23924:
URL: https://github.com/apache/kafka/pull/23924#discussion_r4568761159


##########
group-coordinator/src/main/java/org/apache/kafka/coordinator/group/streams/assignor/BalancedTaskAssignor.java:
##########
@@ -373,29 +447,143 @@ private static Map<String, Set<Integer>> toCompactedTaskIds(final Set<TaskId> ta
         return ret;
     }
 
+    /**
+     * The per-member quota on active plus standby tasks: the tasks left over the members left, rounded up, where a

Review Comment:
   Yes, it's global, I will update the javadoc to make it clearer



-- 
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: jira-unsubscribe@kafka.apache.org

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