Time Complexity: ACL rules and categories
O(n)
0
0
ACL rules and categories in Redis - Time & Space Complexity
Understanding Time Complexity
When working with Redis ACL rules and categories, it's important to understand how the time to check permissions grows as the number of rules increases.
We want to know how Redis handles checking many ACL rules and what affects the speed.
Scenario Under Consideration
Analyze the time complexity of checking ACL rules for a command.
ACL SETUSER alice on >password ~* +@all
ACL SETUSER bob on >password ~cache:* +@read
ACL LIST
ACL GETUSER alice
ACL CAT
This snippet shows setting users with ACL rules, listing them, and retrieving categories.
Identify Repeating Operations
Look at what repeats when Redis checks ACL rules.
- Primary operation: Checking each ACL rule or category against the command or key pattern.
- How many times: Once per rule or category during permission checks.
How Execution Grows With Input
As the number of ACL rules or categories grows, Redis checks more rules to find matches.
| Input Size (number of rules) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The number of checks grows directly with the number of rules.
Final Time Complexity
Time Complexity: O(n)
This means the time to check permissions grows in a straight line as you add more ACL rules.
Common Mistake
[X] Wrong: "Checking ACL rules is instant no matter how many rules exist."
[OK] Correct: Each rule must be checked to see if it applies, so more rules mean more work.
Interview Connect
Understanding how ACL rule checks scale helps you explain system behavior and design efficient permission checks in real projects.
Self-Check
"What if Redis used a hash map to store ACL rules by command? How would the time complexity change?"