ACL rules and categories in Redis - Time & Space Complexity

Time Complexity: ACL rules and categories

O(n)

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

Practice

1. What is the main purpose of ACL rules in Redis?

easy

A. To control user access to commands and keys

B. To store data persistently on disk

C. To optimize query performance

D. To backup the database automatically

Solution

1. Step 1: Understand ACL rules function

   ACL rules define what commands and keys a user can access in Redis.

2. Step 2: Compare options with ACL purpose

   Only To control user access to commands and keys matches the control of user access, others describe unrelated features.

3. Final Answer:

   To control user access to commands and keys -> Option A

4. Quick Check:

   ACL rules = control access [OK]

Hint: ACL rules control access permissions in Redis [OK]

Common Mistakes:

• Confusing ACL rules with data storage
• Thinking ACL rules optimize performance
• Mixing ACL with backup features

2. Which of the following is the correct syntax to add a user with ACL rules in Redis?

easy

A. ACL SETUSER alice on >password ~* +@all

B. ACL CREATEUSER alice on >password ~* +@all

C. ACL ADDUSER alice on >password ~* +@all

D. ACL NEWUSER alice on >password ~* +@all

Solution

1. Step 1: Recall Redis ACL command for user creation

   The correct command to create or update a user is ACL SETUSER.

2. Step 2: Check each option's command

   Only ACL SETUSER alice on >password ~* +@all uses ACL SETUSER, others use invalid commands.

3. Final Answer:

   ACL SETUSER alice on >password ~* +@all -> Option A

4. Quick Check:

   Use ACL SETUSER to add/update users [OK]

Hint: Use ACL SETUSER to add or update users [OK]

Common Mistakes:

• Using ACL ADDUSER instead of ACL SETUSER
• Using ACL CREATEUSER or ACL NEWUSER which don't exist
• Confusing command names

3. Given the ACL rule ACL SETUSER bob on >mypassword ~cache:* +@read, which commands can user 'bob' execute?

medium

A. Only write commands on any keys

B. All commands including write commands

C. Only read commands on keys starting with 'cache:'

D. No commands because the user is off

Solution

1. Step 1: Analyze the ACL rule components

   User 'bob' is enabled (on), password set, keys limited to pattern 'cache:*', and allowed commands are in category '@read'.

2. Step 2: Determine allowed commands and keys

   Only read commands (+@read) on keys matching 'cache:*' are allowed.

3. Final Answer:

   Only read commands on keys starting with 'cache:' -> Option C

4. Quick Check:

   ACL keys + command categories limit access [OK]

Hint: Check key pattern and command category for user permissions [OK]

Common Mistakes:

• Assuming all commands are allowed
• Ignoring key pattern restrictions
• Thinking user is disabled

4. You run ACL SETUSER alice on >pass123 ~* +@write but Alice cannot execute SET commands. What is the likely issue?

medium

A. The user is not enabled

B. The command category @write does not include SET

C. The key pattern ~* is too restrictive

D. The password is incorrect

Solution

1. Step 1: Verify user status and rules

   User 'alice' is enabled (on), password set, keys unrestricted (~*), commands allowed in @write category.

2. Step 2: Check if SET is in @write category

   SET command belongs to @string category, not @write, so permission is missing.

3. Final Answer:

   The command category @write does not include SET -> Option B

4. Quick Check:

   Command categories must include needed commands [OK]

Hint: Confirm command category includes the command you want [OK]

Common Mistakes:

• Assuming @write includes all write commands
• Thinking key pattern restricts commands
• Ignoring user enabled status

5. You want to create a Redis user 'cacheAdmin' who can run all commands related to caching and keys starting with 'cache:'. Which ACL rule is correct?

hard

A. ACL SETUSER cacheAdmin on >secret ~cache:* +@read +@write

B. ACL SETUSER cacheAdmin on >secret ~cache:* +@all

C. ACL SETUSER cacheAdmin on >secret ~* +@cache

D. ACL SETUSER cacheAdmin on >secret ~cache:* +@cache +@keyspace

Solution

1. Step 1: Identify key pattern restriction

   User must access keys starting with 'cache:', so pattern ~cache:* is needed.

2. Step 2: Select command categories for caching

   Commands related to caching are in @cache and key management in @keyspace categories.

3. Step 3: Evaluate options

   ACL SETUSER cacheAdmin on >secret ~cache:* +@cache +@keyspace correctly combines key pattern and relevant categories; others either allow too much or wrong keys.

4. Final Answer:

   ACL SETUSER cacheAdmin on >secret ~cache:* +@cache +@keyspace -> Option D

5. Quick Check:

   Use key pattern + relevant categories for precise access [OK]

Hint: Combine key patterns with correct categories for precise ACL [OK]

Common Mistakes:

• Using ~* allows all keys, not just cache keys
• Using +@all grants too many permissions
• Missing key pattern restriction