[KAFKA-15139] Optimize the performance of `Set.removeAll(List)` in `MirrorCheckpointConnector`

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 3.5.0
• Fix Version/s: 3.6.0
• Component/s: mirrormaker
• Assignee: hudeqi
• Reporter: hudeqi
• Created: 01/Jul/23 08:32
• Updated: 11/Jul/23 22:14
• Resolved: 11/Jul/23 04:19

Description

This is the hint of `removeAll` method in `Set`:

This implementation determines which is the smaller of this set and the specified collection, by invoking the size method on each. If this set has fewer elements, then the implementation iterates over this set, checking each element returned by the iterator in turn to see if it is contained in the specified collection. If it is so contained, it is removed from this set with the iterator's remove method. If the specified collection has fewer elements, then the implementation iterates over the specified collection, removing from this set each element returned by the iterator, using this set's remove method.

That's said, assume that M is the number of elements in the set and N is the number of elements in the List, if the type of the specified collection is `List`, and M<=N, then the time complexity of `removeAll` is O(MN) (because the time complexity of searching in List is O(N)), on the contrary, if N<M, it will search in `Set`, the time complexity is O(N).

In `MirrorCheckpointConnector`, `refreshConsumerGroups` method is repeatedly called in a daemon thread. There are two `removeAll` in this method. From a logical point of view, when this method is called in one round, when the number of groups in the source cluster simply increases or decreases, the two `removeAll` execution strategies will always hit the O(MN) situation mentioned above. Therefore, it is better to change all the variables here to Set type to avoid this "low performance".

Issue Links

• links to: GitHub Pull Request #13946