ACL-based authorization in Kafka - Time & Space Complexity

Time Complexity: ACL-based authorization

O(n)

Understanding Time Complexity

When Kafka checks if a user can access a resource using ACLs, it needs to look through the list of rules. We want to understand how the time to check access changes as the number of ACL rules grows.

How does the number of ACL rules affect the time it takes to authorize a request?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simplified ACL check in Kafka
boolean isAuthorized(String user, String resource, String operation) {
  for (AclRule rule : aclRules) {
    if (rule.matches(user, resource, operation)) {
      return rule.isAllowed();
    }
  }
  return false; // deny if no match
}

This code checks each ACL rule one by one to see if it matches the user, resource, and operation. It returns as soon as it finds a matching rule.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of ACL rules.
• How many times: Up to the total number of ACL rules, until a match is found or all rules are checked.

How Execution Grows With Input

As the number of ACL rules increases, the time to check authorization grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	Up to 10 rule checks
100	Up to 100 rule checks
1000	Up to 1000 rule checks

Pattern observation: The number of checks grows linearly with the number of ACL rules.

Final Time Complexity

Time Complexity: O(n)

This means the time to authorize grows linearly as the number of ACL rules increases.

Common Mistake

[X] Wrong: "Authorization time stays the same no matter how many ACL rules exist."

[OK] Correct: Since the code checks rules one by one, more rules mean more checks, so time grows with the number of rules.

Interview Connect

Understanding how authorization checks scale helps you design systems that stay fast as they grow. This skill shows you can think about real-world performance, not just code correctness.

Self-Check

"What if the ACL rules were stored in a hash map keyed by user and resource? How would the time complexity change?"