Caching Strategies

1. Vì sao Caching?

Tốc độ: cache hit ratio cao → giảm latency 10–1000×, giảm tải DB cực mạnh.

1.1. Vì sao cache nhanh hơn DB?

Với mỗi 1 cache hit, tránh được 1 DB query. Hit rate 95% nghĩa là DB chỉ phục vụ 5% traffic — scale đơn giản nhiều.

2. Multi-tier Caching

2.1. Mỗi tầng giải vấn đề khác

• Browser HTTP cache: tránh request lặp với Cache-Control + ETag.
• CDN: serve static từ edge gần user; cache HTTP-level.
• Reverse proxy: cache response phổ biến, SSL session.
• App in-process: hot data nhỏ, lookup < 1µs (config, lookup table).
• Distributed cache (Redis): shared state giữa app instance.
• DB buffer pool: RAM cache nội bộ, không tự control.

2.2. Cache hit ratio mỗi tầng

Mục tiêu: hit ratio cao ở tầng càng "ngoài" càng tốt — request không đụng đến tầng trong.

Nếu mỗi tầng hit 80%, request đụng DB chỉ là 0.2^4 = 0.16% traffic. DB thoải mái.

2.3. Browser HTTP cache

Cache miễn phí, đừng bỏ qua. 2 cơ chế:

• Cache-Control: max-age=3600, public — browser cache 1h, không cần hỏi server.
• ETag: server gửi hash version. Request tiếp browser gửi If-None-Match: hash → server trả 304 Not Modified nếu chưa đổi (không cần body).

# Response từ server:
HTTP/1.1 200 OK
Content-Type: image/png
Cache-Control: public, max-age=31536000, immutable
ETag: "abc123"

# Request kế tiếp browser:
GET /image.png
If-None-Match: "abc123"

# Server response:
HTTP/1.1 304 Not Modified
ETag: "abc123"
# (không có body)

Pattern URL versioning: /static/app.v123.js — đổi nội dung = đổi URL → cache "đời đời" với immutable.

3. Cache Patterns — recap + system view

Đã học 4 pattern ở Database Ch11. Recap nhanh:

3.1. Cache-Aside cụ thể

async function getUser(id: number): Promise<User> {
  const cacheKey = `user:${id}`;

  // 1. Đọc cache
  const cached = await redis.get(cacheKey);
  if (cached) {
    metrics.increment('cache.hit');
    return JSON.parse(cached);
  }

  metrics.increment('cache.miss');

  // 2. Cache miss → đọc DB
  const user = await db.query('SELECT * FROM users WHERE id = $1', [id]);
  if (!user) return null;

  // 3. Set cache (TTL 10 phút + jitter ±10%)
  const ttl = 600 * (0.9 + Math.random() * 0.2);
  await redis.set(cacheKey, JSON.stringify(user), 'EX', ttl);

  return user;
}

async function updateUser(id: number, data: Partial<User>) {
  await db.query('UPDATE users SET ... WHERE id = $1', [id]);
  await redis.del(`user:${id}`);   // invalidate
}

3.2. Lưu ý: failure mode

Cache là optimization, không phải source of truth. Cache chết → app phải vẫn chạy (chậm hơn). Tránh:

// ❌ Cache chết → app chết
const cached = await redis.get(key);   // throws nếu Redis down
return JSON.parse(cached);

// ✓ Fail-open
let cached;
try {
  cached = await redis.get(key);
} catch (e) {
  logger.warn('Redis error, falling back to DB', e);
  cached = null;
}
return cached ? JSON.parse(cached) : await fetchFromDb();

4. Eviction Policies

Cache có giới hạn RAM. Khi đầy, eviction policy chọn key nào xóa.

4.1. Các thuật toán

4.2. Redis maxmemory-policy

# redis.conf
maxmemory 4gb
maxmemory-policy allkeys-lru     # LRU trên mọi key — phổ biến nhất

# Các option khác:
# noeviction      — báo lỗi khi đầy (default)
# allkeys-lru     — LRU trên mọi key
# allkeys-lfu     — LFU trên mọi key (Redis 4+)
# allkeys-random  — random
# volatile-lru    — LRU chỉ key có TTL (giữ key không TTL)
# volatile-lfu    — LFU chỉ key có TTL
# volatile-ttl    — xóa key có TTL ngắn nhất trước

4.3. LRU implementation đơn giản (in-memory app)

class LRUCache<K, V> {
  private cache = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key)!;
    // Re-insert để move to end (Map maintains insertion order)
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  set(key: K, value: V): void {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      // Xóa key đầu (LRU)
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }
}

JS Map giữ insertion order → LRU implementation đơn giản. Caffeine (Java) dùng W-TinyLFU phức tạp hơn nhưng hit rate tốt hơn 5-15%.

5. TTL Strategies

5.1. Chọn TTL

5.2. TTL Jitter — tránh expire đồng loạt

Nếu set TTL = 600s cho 1000 key cùng lúc, sau 600s tất cả expire cùng → cache stampede.

// ❌ TTL cố định → expire đồng loạt
await redis.set(key, value, 'EX', 600);

// ✓ TTL với jitter ±10%
const baseTTL = 600;
const jitter = Math.floor((Math.random() - 0.5) * baseTTL * 0.2);
await redis.set(key, value, 'EX', baseTTL + jitter);

5.3. Sliding window TTL

Mỗi access reset TTL (như session token). Đối lập với absolute TTL (cố định từ lúc tạo).

// Sliding: mỗi get → reset TTL
async function getWithSliding(key: string) {
  const value = await redis.get(key);
  if (value) await redis.expire(key, 1800);   // refresh TTL
  return value;
}

5.4. Lazy expiration vs Active expiration

• Lazy — chỉ kiểm tra TTL khi access. Key expired vẫn ở RAM đến khi ai đó request.
• Active — background task scan và xóa key expired.

Redis dùng cả hai: lazy + active sample (mỗi 100ms scan random 20 key có TTL).

6. Invalidation Strategies

Phil Karlton: "There are only two hard things in Computer Science: cache invalidation and naming things."

6.1. Strategies

• TTL only — đơn giản, an toàn. Stale tối đa = TTL. Phù hợp khi tolerate stale.
• Event-based — khi DB update, app trigger invalidate cache key liên quan. Lỗi nếu quên 1 path.
• Write-through — write update cả cache + DB. Khó với multi-region.
• Versioning — key chứa version: user:5:v123. Update → bump version → key cũ orphan, tự expire qua TTL.
• Tag-based — group key theo tag, invalidate tag. Redis không có native, cần lib hoặc convention.

6.2. Cascade invalidation

1 entity được cache ở nhiều key:

user:5
user:5:profile
home_feed:user:5:page:1
search:results:term:"alice"  ← chứa user 5
team:42:members              ← chứa user 5

Update user 5 → phải invalidate hết. Approaches:

• Pub/Sub: app publish event "user:5:updated", các cache subscriber tự xử lý.
• Redis SCAN + DEL: scan pattern user:5:* rồi xóa. Chậm trên cluster lớn.
• Tag stored: lưu set "tags:user:5" chứa các cache key liên quan.
• Short TTL + accept stale: dễ nhất, không cần code logic phức tạp.

6.3. Stale-while-revalidate

Pattern: trả ngay stale value, đồng thời trigger background refresh.

async function getWithSWR(key: string, fetcher: () => Promise<any>) {
  const cached = await redis.get(key);
  if (!cached) return await refreshAndCache(key, fetcher);

  const { value, fresh_until } = JSON.parse(cached);

  if (Date.now() > fresh_until) {
    // Stale — trả ngay, refresh nền
    void refreshAndCache(key, fetcher);
  }
  return value;
}

async function refreshAndCache(key: string, fetcher: () => Promise<any>) {
  const value = await fetcher();
  const cacheValue = {
    value,
    fresh_until: Date.now() + 5 * 60_000,
  };
  await redis.set(key, JSON.stringify(cacheValue), 'EX', 30 * 60);
  return value;
}

Lợi: user không bao giờ chờ; cache luôn được làm mới. Nhược: stale có thể là vài phút.

Next.js, SWR (Vercel), Cloudflare đều support pattern này native.

7. Stampede Protection — Thundering Herd

Đã đề cập Database Ch11. Đây mở rộng thêm.

7.1. Cách giải

7.1.a. Single-flight (per process)

const inFlight = new Map<string, Promise<any>>();

async function getOnce(key: string, fetcher: () => Promise<any>) {
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached);

  // Đã có request inflight → reuse promise
  if (inFlight.has(key)) return inFlight.get(key);

  const promise = (async () => {
    try {
      const value = await fetcher();
      await redis.set(key, JSON.stringify(value), 'EX', 300);
      return value;
    } finally {
      inFlight.delete(key);
    }
  })();

  inFlight.set(key, promise);
  return promise;
}

7.1.b. Distributed lock (cross-process)

async function getWithLock(key: string, fetcher: () => Promise<any>) {
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached);

  const lockKey = `lock:${key}`;
  // SETNX với expire — distributed lock
  const acquired = await redis.set(lockKey, '1', 'NX', 'EX', 5);

  if (!acquired) {
    // Process khác đang rebuild → chờ rồi đọc
    await new Promise(resolve => setTimeout(resolve, 50));
    return getWithLock(key, fetcher);
  }

  try {
    const value = await fetcher();
    await redis.set(key, JSON.stringify(value), 'EX', 300);
    return value;
  } finally {
    await redis.del(lockKey);
  }
}

7.1.c. Probabilistic early expiration (XFetch)

Mỗi access tính xác suất "expire sớm" tăng dần khi gần TTL. Một process random sẽ refresh trước khi cache thực sự expire.

function shouldRefreshEarly(remainingTTL: number, fetchDuration: number, beta = 1) {
  const xfetch = fetchDuration * beta * Math.log(Math.random());
  return remainingTTL < -xfetch;
}

7.1.d. TTL jitter

Đã nói. Phương pháp đơn giản nhất, ngăn nhiều key expire cùng lúc.

8. Distributed Cache

Khi app có nhiều instance → cần shared cache. Redis cluster phổ biến nhất.

8.1. Redis Cluster

Redis Cluster: 16384 hash slot, mỗi slot map đến 1 master. Client tính CRC16(key) % 16384 để biết slot, route đến đúng master.

8.2. Hash tags — multi-key operation

Vấn đề: MGET user:1 user:2 user:3 có thể trên 3 master khác nhau → cluster reject.

Sửa: dùng hash tag {} để force vào cùng slot:

SET {team:42}:user:1 ...
SET {team:42}:user:2 ...
SET {team:42}:user:3 ...
# Cả 3 vào cùng slot vì cùng tag {team:42}
MGET {team:42}:user:1 {team:42}:user:2 {team:42}:user:3   # ✓ OK

8.3. Replication & failover

Mỗi master có ≥ 1 replica. Master chết → replica tự promote. Client tự discover topology mới.

Failover thường < 30s. Trong khoảng đó, write fail; read có thể OK qua replica (stale).

8.4. Memcached vs Redis

Đa số dự án mới chọn Redis vì versatility. Memcached khi chỉ cần cache key-value pure thuần và muốn multi-thread CPU.

9. Cache Consistency — vấn đề khó

9.1. Race condition kinh điển

Pattern UPDATE → DEL cache không thread-safe 100%. Có race window.

9.2. Mitigations

• Short TTL — race window có thì cache cũng tự expire sớm.
• Read-through write-through — không có "cache miss + reload" race.
• Versioning — đính kèm version vào key/value, đọc kiểm tra.
• Acceptance — chấp nhận stale ngắn hạn nếu workload tolerate.

9.3. Cache vs DB consistency model

• Strong: write atomic cả 2; transactional cache layer (rare).
• Read-your-writes: dùng "session cache" cho user vừa write — đảm bảo họ thấy update.
• Eventual: TTL ngắn + invalidation best-effort; phổ biến nhất.

9.4. Negative caching

Cache cả "không tồn tại":

async function getUser(id: number) {
  const cached = await redis.get(`user:${id}`);
  if (cached === '__null__') return null;          // negative cache
  if (cached) return JSON.parse(cached);

  const user = await db.query(...);
  if (!user) {
    await redis.set(`user:${id}`, '__null__', 'EX', 60);   // cache miss 1 phút
    return null;
  }
  await redis.set(`user:${id}`, JSON.stringify(user), 'EX', 600);
  return user;
}

Quan trọng để tránh DB bị spam với "id không tồn tại". Attacker biết pattern này có thể DDoS hệ.

10. Bài tập

1. Implement multi-tier cache cho 1 endpoint GET /products/:id:
   • L1: in-process LRU (max 1000 entry, TTL 60s)
   • L2: Redis (TTL 10 phút với jitter)
   • L3: DB
   Đo cache hit ratio mỗi tầng và latency overall.
2. Tự tay code LRU cache với capacity 100. Test với pattern access có locality vs random.
3. Reproduce cache stampede: tắt 1 hot key, gửi 1000 request đồng thời. Quan sát DB connections. Áp dụng single-flight, đo lại.
4. Tạo cache invalidation cho post + commentCount + likeCount. Khi post update, comment add, like add — invalidate đúng key. Dùng Pub/Sub Redis broadcast event.
5. Implement stale-while-revalidate cho weather API: stale OK trong 5 phút, fresh ưu tiên nhưng không block.
6. So sánh Redis vs Memcached: cho 4 use case, chọn cái nào phù hợp.
   • (a) Session store với TTL sliding
   • (b) Leaderboard top 100 user
   • (c) Cache user profile pure key-value
   • (d) Pub/Sub notification
7. Thiết kế negative cache cho "user không tồn tại": TTL bao nhiêu? Cách phân biệt "đã cached là null" vs "chưa cached"?

11. Quiz