Cache-aside pattern in Azure - Time & Space Complexity

Time Complexity: Cache-aside pattern

O(n)

Understanding Time Complexity

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

Specifically, how many times the system checks cache and database as data requests grow.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Try to get data from cache
var data = cache.Get(key);
if (data == null) {
  // If not in cache, get from database
  data = database.Get(key);
  // Store data in cache for next time
  cache.Set(key, data);
}
return data;
    

This sequence tries to get data from cache first, then falls back to database if needed, and updates cache.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Cache read (cache.Get) and possibly database read (database.Get)
• How many times: Once per data request

How Execution Grows With Input

Each data request causes one cache check. If cache misses, one database read and one cache write happen.

Input Size (n)	Approx. Api Calls/Operations
10	10 cache reads + up to 10 database reads and cache writes
100	100 cache reads + up to 100 database reads and cache writes
1000	1000 cache reads + up to 1000 database reads and cache writes

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

Final Time Complexity

Time Complexity: O(n)

This means the time to handle requests grows directly in proportion to how many requests come in.

Common Mistake

[X] Wrong: "Cache reads and database reads happen only once no matter how many requests."

[OK] Correct: Each request triggers a cache check, and if the cache misses, a database read happens. So operations scale with requests.

Interview Connect

Understanding how cache and database calls grow with requests shows you can reason about system efficiency and scaling in real cloud apps.

Self-Check

"What if the cache never misses? How would the time complexity change?"

Practice

1. What is the main purpose of the cache-aside pattern in Azure applications?

easy

A. To load data into cache only when it is requested

B. To preload all data into cache at application start

C. To automatically update cache without application control

D. To store data only in the database without caching

Solution

1. Step 1: Understand cache-aside pattern behavior

   The cache-aside pattern loads data into cache only when the application requests it and the data is not already cached.

2. Step 2: Compare options with this behavior

   To load data into cache only when it is requested matches this behavior. Options B and C describe other caching strategies, and A ignores caching.

3. Final Answer:

   To load data into cache only when it is requested -> Option A

4. Quick Check:

   Cache-aside loads on demand = D [OK]

Hint: Cache-aside means load cache only when needed [OK]

Common Mistakes:

• Thinking cache preloads all data
• Assuming cache updates automatically
• Confusing cache-aside with write-through caching

2. Which of the following is the correct sequence when using the cache-aside pattern in Azure?

easy

A. Return data -> Check cache -> Read database -> Store in cache

B. Read database -> Store in cache -> Return data -> Check cache

C. Store in cache -> Check cache -> Read database -> Return data

D. Check cache -> If miss, read database -> Store in cache -> Return data

Solution

1. Step 1: Recall cache-aside pattern steps

   The application first checks the cache. If data is missing (cache miss), it reads from the database, stores the data in cache, then returns it.

2. Step 2: Match the sequence with options

   Check cache -> If miss, read database -> Store in cache -> Return data correctly shows this sequence. Other options have steps in wrong order.

3. Final Answer:

   Check cache -> If miss, read database -> Store in cache -> Return data -> Option D

4. Quick Check:

   Cache check first, then DB read if miss = A [OK]

Hint: Cache check first, then DB read if miss [OK]

Common Mistakes:

• Reading database before checking cache
• Storing data in cache before reading database
• Returning data before checking cache

3. Consider this Azure cache-aside pseudocode:

data = cache.get('user123')
if data is None:
    data = database.read('user123')
    cache.set('user123', data)
return data

What happens if the cache contains stale data for 'user123'?

medium

A. The application reads fresh data from the database every time

B. The application returns the stale data without checking the database

C. The cache automatically updates stale data before returning

D. The application throws an error due to stale cache

Solution

1. Step 1: Analyze cache-aside code behavior

   The code returns cached data if present, without verifying freshness. It reads database only if cache miss.

2. Step 2: Understand stale data impact

   If cache has stale data, the application returns it directly, ignoring database updates until cache expires or is invalidated.

3. Final Answer:

   The application returns the stale data without checking the database -> Option B

4. Quick Check:

   Cache returns stale data if present = A [OK]

Hint: Cache returns data if present, even if stale [OK]

Common Mistakes:

• Assuming cache auto-refreshes stale data
• Thinking database is read every time
• Believing stale cache causes errors

4. You implemented cache-aside in Azure but notice your cache never updates after data changes in the database. What is the most likely cause?

medium

A. The application does not invalidate or update cache after database writes

B. The cache service is down and cannot store data

C. The database is not reachable for reads

D. The cache is set to expire data too frequently

Solution

1. Step 1: Understand cache-aside update responsibility

   In cache-aside, the application must update or invalidate cache after database changes to keep cache fresh.

2. Step 2: Identify cause of stale cache

   If cache never updates, likely the app is not managing cache invalidation after writes, causing stale data to persist.

3. Final Answer:

   The application does not invalidate or update cache after database writes -> Option A

4. Quick Check:

   App must update cache after DB changes = C [OK]

Hint: App must update cache after DB changes [OK]

Common Mistakes:

• Blaming cache service downtime without checking app logic
• Assuming database read issues cause stale cache
• Thinking frequent expiry causes no updates

5. You want to optimize an Azure app using cache-aside pattern for user profiles. Which approach best ensures cache consistency when profiles update frequently?

hard

A. Only update cache when the profile is requested next time

B. Set cache expiration to 24 hours and never update manually

C. After updating the database, immediately update or remove the cached profile

D. Preload all profiles into cache at app startup

Solution

1. Step 1: Consider cache consistency needs

   For frequently updated profiles, cache must reflect changes quickly to avoid stale data.

2. Step 2: Evaluate options for freshness

   After updating the database, immediately update or remove the cached profile updates or removes cache immediately after DB update, ensuring fresh data. Only update cache when the profile is requested next time delays update causing stale reads. Set cache expiration to 24 hours and never update manually relies on expiry only, which is slow. Preload all profiles into cache at app startup wastes resources and may cause stale data.

3. Final Answer:

   After updating the database, immediately update or remove the cached profile -> Option C

4. Quick Check:

   Immediate cache update after DB write = B [OK]

Hint: Update cache right after DB changes for freshness [OK]

Common Mistakes:

• Relying only on cache expiration for updates
• Delaying cache update until next read
• Preloading cache wastes memory and risks staleness