Accessing keys and arguments in Redis - Time & Space Complexity

Time Complexity: Accessing keys and arguments

O(n)

Understanding Time Complexity

When working with Redis commands, it is important to understand how the time to access keys and arguments changes as the number of keys or arguments grows.

We want to know how the cost of accessing these keys and arguments grows when we have more of them.

Scenario Under Consideration

Analyze the time complexity of the following Redis Lua script snippet.

-- Access keys and arguments in a Redis Lua script
local key1 = KEYS[1]
local key2 = KEYS[2]
local arg1 = ARGV[1]
local arg2 = ARGV[2]

redis.call('SET', key1, arg1)
redis.call('SET', key2, arg2)
    

This script accesses two keys and two arguments, then sets values for those keys using the arguments.

Identify Repeating Operations

Look for repeated actions that take time as input grows.

• Primary operation: Accessing each key and argument once.
• How many times: Once per key and once per argument; no loops here.

How Execution Grows With Input

As the number of keys and arguments increases, the number of accesses grows directly with them.

Input Size (n keys + n args)	Approx. Operations
10	About 10 key accesses + 10 argument accesses = 20 operations
100	About 100 key accesses + 100 argument accesses = 200 operations
1000	About 1000 key accesses + 1000 argument accesses = 2000 operations

Pattern observation: The work grows in a straight line as the number of keys and arguments increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to access keys and arguments grows directly in proportion to how many there are.

Common Mistake

[X] Wrong: "Accessing keys and arguments is always constant time, no matter how many there are."

[OK] Correct: Each key and argument must be accessed individually, so more keys or arguments mean more work.

Interview Connect

Understanding how accessing keys and arguments scales helps you write efficient Redis scripts and shows you can think about performance clearly.

Self-Check

"What if the script used a loop to access keys instead of accessing them one by one? How would the time complexity change?"

Practice

1. In a Redis Lua script, which array is used to access the keys passed to the script?

easy

A. KEYS

B. ARGV

C. KEYSARGS

D. ARGS

Solution

1. Step 1: Understand Redis script inputs

   Redis Lua scripts receive keys and arguments separately.

2. Step 2: Identify the array for keys

   The keys are accessed using the KEYS array inside the script.

3. Final Answer:

   KEYS -> Option A

4. Quick Check:

   Keys = KEYS [OK]

Hint: Keys are always in KEYS array, arguments in ARGV [OK]

Common Mistakes:

• Confusing KEYS with ARGV
• Using ARGS instead of ARGV
• Assuming keys are in ARGV

2. Which of the following is the correct way to access the first argument (not key) inside a Redis Lua script?

easy

A. KEYS[1]

B. ARGV[0]

C. ARGV[1]

D. ARGS[1]

Solution

1. Step 1: Recall Lua array indexing

   Lua arrays start at 1, not 0.

2. Step 2: Identify argument array

   Arguments are accessed via ARGV array, so first argument is ARGV[1].

3. Final Answer:

   ARGV[1] -> Option C

4. Quick Check:

   First argument = ARGV[1] [OK]

Hint: Lua arrays start at 1, so first argument is ARGV[1] [OK]

Common Mistakes:

• Using zero-based index ARGV[0]
• Confusing KEYS with ARGV
• Using ARGS instead of ARGV

3. Consider this Redis Lua script snippet:

local key1 = KEYS[1]
local arg1 = ARGV[1]
return key1 .. '-' .. arg1

If the script is called with keys = ["user:1"] and arguments = ["active"], what is the returned result?

medium

A. "user:1-active"

B. "active-user:1"

C. "user:1active"

D. An error occurs

Solution

1. Step 1: Assign values from KEYS and ARGV

   key1 = "user:1", arg1 = "active" from the inputs.

2. Step 2: Concatenate with separator

   Return value is key1 .. '-' .. arg1 = "user:1-active".

3. Final Answer:

   "user:1-active" -> Option A

4. Quick Check:

   Concatenate KEYS[1] and ARGV[1] with '-' = "user:1-active" [OK]

Hint: Concatenate KEYS and ARGV with .. operator in Lua [OK]

Common Mistakes:

• Swapping KEYS and ARGV values
• Missing separator '-' in concatenation
• Using zero-based indexing

4. You wrote this Redis Lua script:

local key = KEYS[1]
local arg = ARGV[0]
return key .. arg

When running the script with one key and one argument, what will happen?

medium

A. It throws an error due to invalid index

B. It returns nil concatenated with key

C. It returns only the key

D. It returns concatenated key and argument

Solution

1. Step 1: Check Lua indexing rules

   Lua arrays start at 1, so ARGV[0] is invalid but returns nil.

2. Step 2: Understand behavior on invalid index

   Accessing ARGV[0] returns nil, concatenating key .. nil results in key .. "nil" or error depending on Lua version.

3. Final Answer:

   It returns nil concatenated with key -> Option B

4. Quick Check:

   Lua arrays start at 1, ARGV[0] returns nil, concatenation with nil results in string with 'nil' [OK]

Hint: Lua arrays start at 1, never use index 0 [OK]

Common Mistakes:

• Using zero-based index ARGV[0]
• Assuming ARGV[0] returns first argument
• Ignoring Lua indexing rules

5. You want to write a Redis Lua script that takes two keys and one argument. The script should return the value of the first key concatenated with the argument, then the value of the second key. Which is the correct way to access these inside the script?

hard

A. ARGV[1], KEYS[1], KEYS[2]

B. ARGV[0], KEYS[1], ARGV[1]

C. KEYS[0], ARGV[0], KEYS[1]

D. KEYS[1], ARGV[1], KEYS[2]

Solution

1. Step 1: Identify keys and argument positions

   Two keys are KEYS[1] and KEYS[2], one argument is ARGV[1].

2. Step 2: Access in correct order

   Access first key as KEYS[1], argument as ARGV[1], second key as KEYS[2].

3. Final Answer:

   KEYS[1], ARGV[1], KEYS[2] -> Option D

4. Quick Check:

   Keys in KEYS[], args in ARGV[], Lua index starts at 1 [OK]

Hint: Keys in KEYS[], args in ARGV[], index from 1 [OK]

Common Mistakes:

• Using zero-based indexes
• Mixing KEYS and ARGV order
• Using ARGV for keys