Cache-aside (lazy loading) deep dive in Redis - Time & Space Complexity

Time Complexity: Cache-aside (lazy loading) deep dive

O(n)

Understanding Time Complexity

We want to understand how the time to get data changes when using cache-aside in Redis.

Specifically, how the number of operations grows when fetching data that may or may not be cached.

Scenario Under Consideration

Analyze the time complexity of the following Redis cache-aside pattern.

# Try to get data from cache
GET user:123

# If cache miss, fetch from database
# Then store in cache
SET user:123 <data>
    

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

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Single GET command to Redis, possibly followed by a database fetch and SET.
• How many times: Once per data request; no loops or recursion inside this snippet.

How Execution Grows With Input

Each request involves one or two main operations: a cache GET and possibly a database fetch plus cache SET.

Input Size (n)	Approx. Operations
10	About 10 GETs, some SETs if misses
100	About 100 GETs, some SETs if misses
1000	About 1000 GETs, some SETs if misses

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

Final Time Complexity

Time Complexity: O(n)

This means the time grows directly in proportion to the number of data requests.

Common Mistake

[X] Wrong: "Cache-aside always makes data fetching faster regardless of input size."

[OK] Correct: If many requests miss the cache, each miss causes a database fetch, which can slow things down as requests grow.

Interview Connect

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

Self-Check

"What if we added a batch GET for multiple keys instead of single GETs? How would the time complexity change?"

Practice

1. What is the main idea behind the Cache-aside (lazy loading) pattern in Redis?

easy

A. Preload all data into cache before any request

B. Load data into cache only when it is requested and missing

C. Update cache only after database changes without reading cache

D. Keep cache and database completely separate without syncing

Solution

1. Step 1: Understand cache-aside purpose

   Cache-aside means data is loaded into cache only when requested and not found in cache.

2. Step 2: Compare options with definition

   Load data into cache only when it is requested and missing matches this lazy loading idea; others describe different caching strategies.

3. Final Answer:

   Load data into cache only when it is requested and missing -> Option B

4. Quick Check:

   Cache-aside = lazy loading on miss [OK]

Hint: Cache-aside loads data only on cache miss [OK]

Common Mistakes:

• Thinking cache preloads all data
• Confusing cache-aside with write-through caching
• Assuming cache and DB never sync

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. EXISTS

B. GET

C. SET

D. DEL

Solution

1. Step 1: Identify command to check key presence

   Redis command EXISTS returns if a key is present in cache.

2. Step 2: Eliminate other commands

   GET retrieves value, SET writes value, DEL deletes key; only EXISTS checks presence.

3. Final Answer:

   EXISTS -> Option A

4. Quick Check:

   Check key presence = EXISTS [OK]

Hint: Use EXISTS to check cache key before GET [OK]

Common Mistakes:

• Using GET to check existence (returns nil if missing)
• Confusing SET as check command
• Using DEL which deletes keys

3. Consider this pseudo-code for cache-aside in Redis:

if not redis.exists(key):
  data = db.query(key)
  redis.set(key, data)
return redis.get(key)

What will be returned if the key is missing in cache but present in database?

medium

A. Old stale data from cache

B. Null or empty because cache was empty initially

C. An error because key does not exist in cache

D. The data fetched from database and cached

Solution

1. Step 1: Follow code logic on cache miss

   If key missing in Redis, code queries database and sets cache with fresh data.

2. Step 2: Return cached data after setting

   After setting, code returns redis.get(key) which now holds fresh data.

3. Final Answer:

   The data fetched from database and cached -> Option D

4. Quick Check:

   Cache miss triggers DB fetch and cache set [OK]

Hint: Cache miss loads DB data then returns it [OK]

Common Mistakes:

• Assuming cache returns empty if initially missing
• Expecting error on missing cache key
• Thinking cache returns stale data without update

4. You have this cache-aside code snippet:

if redis.get(key) is None:
  data = db.query(key)
  redis.set(key, data)
return redis.get(key)

But sometimes stale data is returned after DB update. What is the likely bug?

medium

A. Setting cache before querying database

B. Using redis.get instead of redis.exists to check cache

C. Not deleting or updating cache after DB changes

D. Returning data before setting cache

Solution

1. Step 1: Identify stale data cause

   Stale data means cache was not refreshed after DB update.

2. Step 2: Check cache update strategy

   Code only sets cache on miss, but does not invalidate or update cache after DB changes.

3. Final Answer:

   Not deleting or updating cache after DB changes -> Option C

4. Quick Check:

   Cache stale if not refreshed after DB update [OK]

Hint: Always invalidate cache after DB update [OK]

Common Mistakes:

• Thinking redis.get check causes stale data
• Believing cache sets before DB query fixes stale data
• Ignoring cache invalidation on DB writes

5. You want to implement cache-aside with Redis for a user profile service. The database updates user info frequently. Which approach best ensures cache consistency and performance?

hard

A. On DB update, delete cache key; on read, load from DB if cache miss

B. Always write to cache first, then update DB asynchronously

C. Preload all user profiles into cache at service start

D. Never update cache; always read directly from DB

Solution

1. Step 1: Analyze cache consistency needs

   Frequent DB updates require cache invalidation to avoid stale data.

2. Step 2: Evaluate options for cache-aside pattern

   On DB update, delete cache key; on read, load from DB if cache miss deletes cache on DB update, so next read reloads fresh data, matching cache-aside best practice.

3. Final Answer:

   On DB update, delete cache key; on read, load from DB if cache miss -> Option A

4. Quick Check:

   Invalidate cache on update, lazy load on read [OK]

Hint: Delete cache on update, lazy load on read [OK]

Common Mistakes:

• Writing cache before DB causes inconsistency
• Preloading all data wastes memory and may be stale
• Ignoring cache leads to poor performance