Counter pattern in Redis - Time & Space Complexity

Time Complexity: Counter pattern

O(1)

Understanding Time Complexity

When using Redis counters, it is important to understand how the time to update or read a counter changes as the number of operations grows.

We want to know how fast Redis handles increasing increments or reads on a counter key.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands used to increment and read a counter.

INCR page_view_count
GET page_view_count
INCRBY page_view_count 5
GET page_view_count

This code increments a counter key and reads its value multiple times.

Identify Repeating Operations

Look at what repeats when we use the counter pattern.

• Primary operation: Incrementing the counter with INCR or INCRBY.
• How many times: Each increment is a single operation, repeated as many times as needed.

How Execution Grows With Input

Each increment or read command takes about the same time no matter how big the counter gets.

Input Size (n)	Approx. Operations
10	10 increments, 10 reads
100	100 increments, 100 reads
1000	1000 increments, 1000 reads

Pattern observation: The time per operation stays constant even as the number of increments grows.

Final Time Complexity

Time Complexity: O(1)

This means each increment or read takes the same small amount of time, no matter how large the counter value becomes.

Common Mistake

[X] Wrong: "Incrementing a very large counter will take longer because the number is bigger."

[OK] Correct: Redis stores counters efficiently and updates them in constant time, so the size of the number does not slow down the operation.

Interview Connect

Understanding that Redis counters operate in constant time helps you explain how to handle high-frequency updates efficiently in real applications.

Self-Check

"What if we used a sorted set to count instead of a simple counter? How would the time complexity change?"

Practice

1. What does the Redis command INCR do in the counter pattern?

easy

A. It increases the value of a key by 1.

B. It deletes the key from the database.

C. It sets the key to a specific string value.

D. It retrieves the current value of the key.

Solution

1. Step 1: Understand the purpose of INCR

   The INCR command is designed to increase the integer value stored at a key by 1.

2. Step 2: Compare with other commands

   Unlike GET which retrieves a value, or DEL which deletes a key, INCR modifies the value by incrementing it.

3. Final Answer:

   It increases the value of a key by 1. -> Option A

4. Quick Check:

   INCR means increment by 1 [OK]

Hint: INCR always adds one to the number stored [OK]

Common Mistakes:

• Thinking INCR deletes the key
• Confusing INCR with GET
• Assuming INCR sets a string value

2. Which of the following is the correct syntax to increment a counter named page_views in Redis?

easy

A. INCREMENT page_views

B. INCR('page_views')

C. increment page_views

D. INCR page_views

Solution

1. Step 1: Recall Redis command syntax

   Redis commands are issued as uppercase words followed by the key name without parentheses.

2. Step 2: Identify the correct command

   INCR page_views is the correct syntax; other options use invalid syntax or wrong command names.

3. Final Answer:

   INCR page_views -> Option D

4. Quick Check:

   Redis commands use space-separated syntax [OK]

Hint: Redis commands have no parentheses, just command and key [OK]

Common Mistakes:

• Using parentheses like a function call
• Typing 'increment' instead of 'INCR'
• Using lowercase command names

3. Given the following Redis commands executed in order:
INCR visits
INCR visits
INCR visits
GET visits
What will be the output of the last command?

medium

A. 3

B. 1

C. 0

D. Error

Solution

1. Step 1: Count increments

   Each INCR visits increases the value by 1. Three increments mean the value is 3.

2. Step 2: Retrieve the value

   GET visits returns the current value, which is 3 after three increments.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 increments = 3 [OK]

Hint: Count how many times INCR runs before GET [OK]

Common Mistakes:

• Assuming value starts at 0 without increments
• Confusing GET output with command name
• Expecting an error if key does not exist initially

4. You run the command INCR user_likes but get an error: "ERR value is not an integer or out of range". What is the most likely cause?

medium

A. The Redis server is down.

B. The key user_likes contains a non-integer value.

C. The command INCR is misspelled.

D. The key user_likes does not exist.

Solution

1. Step 1: Understand the error message

   The error says the value is not an integer or out of range, meaning the key exists but holds a non-integer.

2. Step 2: Check other options

   If the key did not exist, Redis would create it with value 1. Misspelling causes a different error. Server down means no response.

3. Final Answer:

   The key user_likes contains a non-integer value. -> Option B

4. Quick Check:

   INCR needs integer value to work [OK]

Hint: Check key's value type before INCR [OK]

Common Mistakes:

• Assuming key absence causes this error
• Thinking server down causes this error
• Ignoring value type requirements

5. You want to count unique visitors per day using Redis counters. Which approach correctly uses the counter pattern to track daily counts without mixing days?

hard

A. Use a list to store all visitor IDs and count its length.

B. Use a single key visits and reset it to zero every day at midnight.

C. Use keys like visits:2024-06-01, visits:2024-06-02 and increment each day separately.

D. Use INCR on a key named visits without any date information.

Solution

1. Step 1: Understand the need for daily separation

   To track counts per day, keys must be unique per day to avoid mixing counts.

2. Step 2: Evaluate options

   Using keys with date suffixes like visits:2024-06-01 keeps counts separate. Resetting a single key risks losing data if reset fails. Lists are not efficient counters. Using a single key mixes all days.

3. Final Answer:

   Use keys like visits:2024-06-01, visits:2024-06-02 and increment each day separately. -> Option C

4. Quick Check:

   Unique keys per day keep counts separate [OK]

Hint: Add date to key name for daily counters [OK]

Common Mistakes:

• Resetting counters can cause data loss
• Using single key mixes all days
• Using lists instead of counters