Re: [PR] KAFKA-13022: Optimize ClientQuotasImage#describe [kafka]

["chia7712 (via GitHub)" <gi...@apache.org>]

chia7712 commented on code in PR #19079:
URL: https://github.com/apache/kafka/pull/19079#discussion_r2959117696


##########
metadata/src/main/java/org/apache/kafka/image/ClientQuotasImage.java:
##########
@@ -118,40 +142,72 @@ public DescribeClientQuotasResponseData describe(DescribeClientQuotasRequestData
                     "user or clientId filter component.");
             }
         }
-        // TODO: this is O(N). We should add indexing here to speed it up. See KAFKA-13022.
-        for (Entry<ClientQuotaEntity, ClientQuotaImage> entry : entities.entrySet()) {
-            ClientQuotaEntity entity = entry.getKey();
-            ClientQuotaImage quotaImage = entry.getValue();
-            if (matches(entity, exactMatch, typeMatch, request.strict())) {
-                response.entries().add(toDescribeEntry(entity, quotaImage));
-            }
-        }
-        return response;
+
+        return matches(exactMatch, typeMatch, request.strict());
     }
 
-    private static boolean matches(ClientQuotaEntity entity,
-                                   Map<String, String> exactMatch,
-                                   Set<String> typeMatch,
-                                   boolean strict) {
-        if (strict) {
-            if (entity.entries().size() != exactMatch.size() + typeMatch.size()) {
-                return false;
+    private DescribeClientQuotasResponseData matches(
+        Map<String, String> exactMatch,
+        Set<String> typeMatch,
+        boolean strict
+    ) {
+        DescribeClientQuotasResponseData response = new DescribeClientQuotasResponseData();
+        Map<ClientQuotaEntity, ClientQuotaImage> candidates = null;
+        // Case 1: exact match exists. Filter candidates based on exact match first and then type match
+        if (!exactMatch.isEmpty()) {
+            for (Entry<String, String> exactMatchEntry : exactMatch.entrySet()) {
+                String entityType = exactMatchEntry.getKey();
+                String entityName = exactMatchEntry.getValue();
+                Map<ClientQuotaEntity, ClientQuotaImage> matches = entitiesByType.getOrDefault(entityType, Map.of()).getOrDefault(entityName, Map.of());
+                if (candidates == null) {
+                    candidates = new HashMap<>(matches);
+                } else {
+                    candidates.keySet().retainAll(matches.keySet());
+                }
             }
-        }
-        for (Entry<String, String> entry : exactMatch.entrySet()) {
-            if (!entity.entries().containsKey(entry.getKey())) {
-                return false;
+
+            for (String type : typeMatch) {
+                Set<ClientQuotaEntity> typeMatches = new HashSet<>();
+                for (Map<ClientQuotaEntity, ClientQuotaImage> entityToImage : entitiesByType.getOrDefault(type, Map.of()).values()) {
+                    typeMatches.addAll(entityToImage.keySet());
+                }
+                candidates.keySet().retainAll(typeMatches);
+            }
+        } else if (!typeMatch.isEmpty()) {
+            // Case 2: no exact match, only type match exists
+            for (String type : typeMatch) {
+                Map<ClientQuotaEntity, ClientQuotaImage> typeMatchesEntry = new HashMap<>();
+                for (Map<ClientQuotaEntity, ClientQuotaImage> entityToImage : entitiesByType.getOrDefault(type, Map.of()).values()) {
+                    typeMatchesEntry.putAll(entityToImage);

Review Comment:
   I'm thinking whether we should use two indexes to handle `typeMatches` and `exactMatch`? Otherwise, this is still a kind of O(N) ...



-- 
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