کیش اسٹیمپیڈ کیا ہے اور آپ اس سے کیسے بچاتے ہیں؟

Question

Accepted Answer

ایک **cache stampede** (یا dogpile) اس وقت ہوتا ہے جب کوئی hot cached key ختم ہو جائے اور **بہت سی بیک وقت درخواستیں اسے ایک ساتھ miss کریں**، سب origin کو واپس جاتے ہوئے ایک ہی وقت میں دوبارہ حساب لگانے کے لیے۔ Origin (DB یا service) ایک burst سے سخت متاثر ہوتا ہے جسے یہ سنبھال نہیں سکتا، کبھی کبھی نظام کو بند کر دیتا ہے۔

## وجہ

```text
t=0   hot key expires
t=0+  1000 requests arrive → all miss → all query the DB for the SAME value
      → DB overwhelmed; latency spikes; failures cascade
```

Trigger ایک مقبول key کی **بیک وقت ختم ہونا** ہے۔ حل یہ یقینی بنانا ہے کہ صرف ایک (یا کچھ) recomputation ہو، یا کہ درخواستیں سب ایک ساتھ ختم نہ ہوں۔

## حل

- **Locking / single-flight** — پہلی miss ایک lock لیتی ہے اور recompute کرتی ہے؛ باقی سب اس ایک نتیجے کے لیے انتظار کرتے ہیں بجائے اس کے کہ سب origin کو مارے۔
- **Stale-while-revalidate** — فوری طور پر تھوڑا سا stale value پیش کریں جب کہ ایک background task اسے تازہ کرتا ہے۔ کوئی بھی درخواست origin پر روک نہیں ہوتی۔
- **Early / probabilistic recomputation** — کسی key کو *expire ہونے سے پہلے* تازہ کریں، ایک احتمال کے ساتھ جو expiry کے قریب آتے ہی بڑھتا ہے، تو ایک خوش قسمت درخواست اسے stampede سے پہلے دوبارہ بناتی ہے۔
- **Jittered TTLs** — TTLs میں randomness شامل کریں تاکہ keys ایک ہی لمحے میں تمام expire نہ ہوں۔
- **Request coalescing** — ایک جیسی بیک وقت درخواستوں کو ایک origin call میں collapse کریں۔

## Single-flight pseudo-code

```text
function get(key):
  val = cache.get(key)
  if val is present: return val            // fast path: a hit

if lock.acquire(key, ttl=5s):            // only ONE request wins the lock
    try:
      val = recompute()                    // hit the origin exactly once
      cache.set(key, val, ttl)
    finally:
      lock.release(key)
    return val
  else:
    wait_briefly(); return get(key)        // others wait, then read the filled cache
```

Lock یقینی بناتا ہے کہ بالکل ایک origin call ہو؛ ہر دوسری بیک وقت درخواست انتظار کرتی ہے اور پھر تازہ cached value پڑھتی ہے۔

## یہ کیوں اہم ہے

ایک stampede routine cache expiry کو ایک بند کار میں بدل دیتا ہے: cache جو آپ کے DB کو محفوظ کر رہا تھا اچانک رک جاتا ہے، اور پورا ٹریفک ایک ساتھ origin پر آ گرتا ہے۔ وجہ (hot keys کا بیک وقت expiry) اور حل (single-flight، stale-while-revalidate، jitter) جاننا caches کو حقیقی load کے تحت قابل اعتماد رکھنے کے لیے ضروری ہے۔