Cache-aside pattern in Redis - Time & Space Complexity

Time Complexity: Cache-aside pattern

O(n)

Understanding Time Complexity

When using the cache-aside pattern, we want to know how the time to get data changes as the data size grows.

We ask: How does the number of steps grow when we check cache and then the database?

Scenario Under Consideration

Analyze the time complexity of the following Redis cache-aside code snippet.

// Try to get data from cache
GET user:123

// If cache miss, get from database and update cache
if not found {
  data = DB.GET("user:123")
  SET user:123 data
}

// Return data
return data
    

This code tries to get user data from Redis cache first. If missing, it fetches from the database and updates the cache.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single key lookup in cache and possibly one database fetch.
• How many times: Exactly once per data request.

How Execution Grows With Input

Each request checks the cache once and may check the database once if needed.

Input Size (n)	Approx. Operations
10	10 cache lookups, up to 10 database fetches
100	100 cache lookups, up to 100 database fetches
1000	1000 cache lookups, up to 1000 database fetches

Pattern observation: The number of operations grows directly with the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle requests grows in a straight line as the number of requests increases.

Common Mistake

[X] Wrong: "Cache-aside pattern reduces time complexity to constant time regardless of requests."

[OK] Correct: Each request still requires at least one cache check, so time grows with requests, not fixed.

Interview Connect

Understanding how cache-aside scales helps you explain real-world data fetching strategies clearly and confidently.

Self-Check

"What if we batch multiple keys in one cache request? How would the time complexity change?"

Practice

1. What is the main idea behind the cache-aside pattern in Redis?

easy

A. Automatically update cache whenever the database changes without application intervention

B. Load data into cache only when the application requests it and cache misses occur

C. Preload all data into cache before any application requests

D. Use cache only for temporary data that does not come from the database

Solution

1. Step 1: Understand cache-aside pattern basics

   The cache-aside pattern means the application loads data into cache only when it is needed, not before.

2. Step 2: Compare options with this concept

   Load data into cache only when the application requests it and cache misses occur matches this idea exactly, while others describe different caching strategies.

3. Final Answer:

   Load data into cache only when the application requests it and cache misses occur -> Option B

4. Quick Check:

   Cache-aside = Load on demand [OK]

Hint: Cache-aside means load cache only on demand [OK]

Common Mistakes:

• Thinking cache is preloaded with all data
• Assuming cache updates automatically without app logic
• Confusing cache-aside with write-through caching

2. Which Redis command is typically used to check if a key exists in cache before loading from the database in cache-aside pattern?

easy

A. DEL

B. GET

C. SET

D. EXISTS

Solution

1. Step 1: Identify command to check key presence

   In Redis, EXISTS checks if a key is present in cache.

2. Step 2: Match commands with their purpose

   GET retrieves value, SET stores value, DEL deletes key. Only EXISTS checks presence.

3. Final Answer:

   EXISTS -> Option D

4. Quick Check:

   Check key presence = EXISTS [OK]

Hint: Use EXISTS to check if cache key is present [OK]

Common Mistakes:

• Using GET to check existence (GET returns null if missing)
• Confusing SET with checking commands
• Using DEL which deletes keys

3. Consider this Redis cache-aside pseudocode:

if not redis.exists('user:123'):
    data = db.query('SELECT * FROM users WHERE id=123')
    redis.set('user:123', data)
else:
    data = redis.get('user:123')

What happens if the key user:123 is missing in Redis?

medium

A. Redis automatically loads data from database

B. Data is fetched from Redis but will be empty

C. Data is fetched from the database and stored in Redis cache

D. An error occurs because key does not exist

Solution

1. Step 1: Analyze the if condition for cache miss

   If user:123 does not exist in Redis, the code queries the database for data.

2. Step 2: Understand cache population after miss

   After fetching from database, it stores the data in Redis with set for future requests.

3. Final Answer:

   Data is fetched from the database and stored in Redis cache -> Option C

4. Quick Check:

   Cache miss triggers DB fetch and cache store [OK]

Hint: Cache miss means fetch DB and store in cache [OK]

Common Mistakes:

• Assuming Redis auto-loads data from DB
• Expecting error on missing key
• Thinking Redis returns empty data silently

4. You have this cache-aside code snippet in Redis:

if redis.get('product:456') is None:
    data = db.query('SELECT * FROM products WHERE id=456')
    redis.set('product:456', data)
else:
    data = redis.get('product:456')

But the cache never updates even after database changes. What is the likely problem?

medium

A. The cache is never invalidated or updated after DB changes

B. The Redis GET command is incorrect

C. The database query syntax is wrong

D. The key name 'product:456' is invalid in Redis

Solution

1. Step 1: Identify cache update mechanism

   The code only sets cache if key is missing but does not update or invalidate cache after DB changes.

2. Step 2: Understand cache staleness cause

   Without cache invalidation or update logic after DB writes, cache remains stale and does not reflect DB changes.

3. Final Answer:

   The cache is never invalidated or updated after DB changes -> Option A

4. Quick Check:

   Cache stale if no invalidation after DB update [OK]

Hint: Cache must be invalidated after DB updates [OK]

Common Mistakes:

• Assuming GET command causes update
• Blaming DB query syntax without evidence
• Thinking Redis keys are invalid without reason

5. You want to implement cache-aside pattern in Redis for a user profile service. Which approach correctly handles cache misses and updates when user data changes?

1. On read: check cache, if miss fetch DB and set cache
2. On write: update DB, then delete cache key to force reload on next read

Why is deleting the cache key after DB update preferred over updating cache directly?

hard

A. Deleting cache key avoids race conditions and stale data issues

B. Updating cache directly is impossible in Redis

C. Deleting cache key improves Redis memory usage drastically

D. Updating cache directly causes Redis to crash

Solution

1. Step 1: Understand cache update strategies

   Deleting cache key after DB update forces next read to reload fresh data, avoiding stale cache.

2. Step 2: Recognize race condition prevention

   Direct cache update risks race conditions if multiple writes/read happen concurrently; deleting key is safer.

3. Final Answer:

   Deleting cache key avoids race conditions and stale data issues -> Option A

4. Quick Check:

   Delete cache key after DB write to avoid stale data [OK]

Hint: Delete cache key after DB update to avoid stale data [OK]

Common Mistakes:

• Thinking Redis cannot update cache values
• Believing direct cache update is always better
• Assuming deleting cache key crashes Redis