ACL system for user permissions in Redis - Time & Space Complexity

Time Complexity: ACL system for user permissions

O(n)

Understanding Time Complexity

When managing user permissions with Redis ACLs, it's important to know how the time to check or update permissions changes as the number of users or rules grows.

We want to understand how fast Redis handles permission checks and updates as more users and rules are added.

Scenario Under Consideration

Analyze the time complexity of the following Redis ACL commands.

ACL SETUSER alice on >password ~* +get +set
ACL SETUSER bob on >password ~cache:* +get
ACL LIST
ACL GETUSER alice
ACL DELUSER bob
ACL CAT all
ACL WHOAMI

This snippet shows commands to create users with permissions, list users, get user details, delete a user, list all categories of commands, and check the current user.

Identify Repeating Operations

Look for operations that repeat or scale with input size.

• Primary operation: Searching user entries and permission rules in Redis internal data structures.
• How many times: Depends on the number of users and rules; for example, listing all users or categories involves scanning all entries.

How Execution Grows With Input

As the number of users or ACL rules grows, commands that scan or list all users or rules take longer.

Input Size (n users)	Approx. Operations
10	About 10 lookups or scans
100	About 100 lookups or scans
1000	About 1000 lookups or scans

Pattern observation: The time grows roughly in direct proportion to the number of users or rules scanned.

Final Time Complexity

Time Complexity: O(n)

This means the time to perform ACL operations that list or scan users grows linearly with the number of users or rules.

Common Mistake

[X] Wrong: "Checking a user's permission is always instant and does not depend on the number of users or rules."

[OK] Correct: While checking a single permission is fast, commands that list or manage many users or rules take longer as the data grows.

Interview Connect

Understanding how permission checks and updates 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 we changed the ACL system to cache user permissions in memory? How would the time complexity of permission checks change?"

Practice

1. What is the main purpose of Redis ACL (Access Control List)?

easy

A. To speed up Redis database queries

B. To control which users can perform specific commands and access keys

C. To backup Redis data automatically

D. To monitor Redis server performance

Solution

1. Step 1: Understand ACL purpose

   ACL in Redis is designed to manage user permissions, controlling what commands and keys users can access.

2. Step 2: Compare options

   Options B, C, and D describe unrelated Redis features like performance and backup, not ACL.

3. Final Answer:

   To control which users can perform specific commands and access keys -> Option B

4. Quick Check:

   ACL controls permissions = A [OK]

Hint: ACL is about permissions, not performance or backups [OK]

Common Mistakes:

• Confusing ACL with performance tuning
• Thinking ACL manages backups
• Assuming ACL monitors server stats

2. Which of the following is the correct Redis command to create or update a user with specific permissions?

easy

A. ACL CREATEUSER username on >password ~keys +commands

B. ACL UPDATEUSER username on >password ~keys +commands

C. ACL ADDUSER username on >password ~keys +commands

D. ACL SETUSER username on >password ~keys +commands

Solution

1. Step 1: Recall Redis ACL command syntax

   The correct command to create or update a user is ACL SETUSER followed by username and permissions.

2. Step 2: Check options

   Only ACL SETUSER username on >password ~keys +commands uses ACL SETUSER. Others use invalid commands like CREATEUSER, ADDUSER, UPDATEUSER which do not exist in Redis ACL.

3. Final Answer:

   ACL SETUSER username on >password ~keys +commands -> Option D

4. Quick Check:

   Use ACL SETUSER to set permissions [OK]

Hint: Remember: ACL SETUSER sets or updates users [OK]

Common Mistakes:

• Using non-existent ACL commands like CREATEUSER
• Confusing SETUSER with other verbs
• Missing required syntax parts like 'on' or '>'

3. Given the command ACL SETUSER alice on >mypassword ~cache:* +get +set, what permissions does user 'alice' have?

medium

A. User 'alice' is disabled and cannot run any commands

B. User 'alice' can run all commands on all keys

C. User 'alice' can only run GET and SET commands on keys starting with 'cache:'

D. User 'alice' can run GET and SET commands on all keys

Solution

1. Step 1: Analyze ACL SETUSER command parts

   'on' enables the user, '>mypassword' sets password, '~cache:*' limits keys to those starting with 'cache:', '+get +set' allows only GET and SET commands.

2. Step 2: Interpret permissions

   User 'alice' can only run GET and SET commands on keys matching 'cache:*'. Other commands or keys are denied.

3. Final Answer:

   User 'alice' can only run GET and SET commands on keys starting with 'cache:' -> Option C

4. Quick Check:

   Commands + keys limited = A [OK]

Hint: Check '+' for commands and '~' for key patterns [OK]

Common Mistakes:

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

4. You run ACL SETUSER bob on >secret +@all but Bob still cannot execute commands. What is the likely problem?

medium

A. Bob's client did not authenticate with the password

B. Bob's password was not set correctly

C. The command '+@all' is invalid syntax

D. Bob's user is disabled because 'on' was not set

Solution

1. Step 1: Check user status and permissions

   'on' enables Bob, '+@all' grants all command categories, and '>secret' sets password correctly.

2. Step 2: Identify why commands fail

   If Bob cannot run commands, likely he did not authenticate with the password, so Redis denies access despite permissions.

3. Final Answer:

   Bob's client did not authenticate with the password -> Option A

4. Quick Check:

   Authentication required after ACL SETUSER [OK]

Hint: Set password and authenticate client to enable commands [OK]

Common Mistakes:

• Forgetting to authenticate after setting password
• Assuming 'on' disables user if missing
• Thinking '+@all' is invalid

5. You want to create a Redis user 'reporter' who can only run the INFO command and read keys starting with stats:. Which command correctly sets this up?

hard

A. ACL SETUSER reporter on >pass123 ~stats:* +info

B. ACL SETUSER reporter on >pass123 ~stats:* +@read

C. ACL SETUSER reporter on >pass123 ~stats:* +get +info

D. ACL SETUSER reporter on >pass123 ~stats:* +get

Solution

1. Step 1: Understand command requirements

   User 'reporter' needs only the INFO command and access to keys starting with 'stats:'.

2. Step 2: Evaluate options

   ACL SETUSER reporter on >pass123 ~stats:* +info: ACL SETUSER reporter on >pass123 ~stats:* +info grants only the INFO command on keys starting with 'stats:'. ACL SETUSER reporter on >pass123 ~stats:* +get +info incorrectly grants +get which is not required. ACL SETUSER reporter on >pass123 ~stats:* +@read grants all read commands (+@read), which is too broad. ACL SETUSER reporter on >pass123 ~stats:* +get misses +info, so cannot run INFO command.

3. Final Answer:

   ACL SETUSER reporter on >pass123 ~stats:* +info -> Option A

4. Quick Check:

   Only INFO command + key permissions = C [OK]

Hint: Grant only needed commands with '+' and keys with '~' [OK]

Common Mistakes:

• Granting command categories instead of specific commands
• Missing +info for INFO command
• Forgetting to enable user with 'on'