Handle Cache Invalidation and Consistency - Caches

                      TASK
                    

Implementation

Implement cache invalidation strategies to maintain consistency between cache and database. When data changes, cached copies must be updated or removed.

Three main strategies:

Write-Through: Update cache and DB synchronously
Write-Behind: Update cache, async update DB
Cache-Aside with Invalidation: Delete cache, update DB

Also handle cache stampede: when many requests hit an expired key simultaneously.

Sample Test Cases

Write-through consistencyTimeout: 5000ms

Input

{
  "src": "c0",
  "dest": "n1",
  "body": {
    "type": "init",
    "msg_id": 1,
    "node_id": "n1",
    "node_ids": [
      "n1"
    ]
  }
}

Expected Output

{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}

Hints

Hint 1▾

Invalidate on every write

Hint 2▾

Consider eventual vs strong consistency

Hint 3▾

Handle cache stampede scenarios

Resources

XFetch Paper

Optimal probabilistic cache stampede prevention

Redis Patterns

Caching patterns with Redis

                      OVERVIEW
                    

Theoretical Hub

Cache Invalidation

"There are only two hard things in Computer Science: cache invalidation and naming things." - Phil Karlton. Keeping cache consistent with the source of truth is notoriously difficult.

Write-Through

Every write goes to both cache and database synchronously. Simple to reason about but adds latency to writes. Cache is always consistent but writes are slow.

Write-Behind (Write-Back)

Writes go to cache immediately, then asynchronously to database. Fast writes but risk of data loss if cache fails before flush. Requires careful durability handling.

Cache Stampede

When a popular key expires, many requests simultaneously miss and hit the database. Solutions include: locking (only one fetches), early expiration (refresh before actual expiry), or probabilistic early expiration.

Key Concepts

invalidationconsistencywrite-throughwrite-behind

main.py

python

#!/usr/bin/env python3
import sys
import json
import time
import threading
import random
class AdvancedCache:
    def __init__(self, database, strategy="cache-aside"):
        self.cache = {}
        self.db = database
        self.strategy = strategy
        self.locks = {}
        self.lock = threading.Lock()
    
    def _get_lock(self, key):
        with self.lock:
            if key not in self.locks:
                self.locks[key] = threading.Lock()
            return self.locks[key]
    
    def get(self, key):
        # TODO: Implement get with stampede protection
        pass
    
    def set(self, key, value):
        # TODO: Implement based on strategy
        # write-through, write-behind, or cache-aside
        pass
    
    def invalidate(self, key):
        # TODO: Remove from cache
        pass
    
    def _fetch_with_lock(self, key):
        # TODO: Use locking to prevent stampede
        # Only one thread fetches, others wait
        pass
class ProbabilisticCache: