آپ 1 کروڑ timed tasks کے لیے scheduler کیسے ڈیزائن کریں گے؟

Question

IT Interview Practice · Accepted Answer

tasks کو **time-bucketed / priority queue** میں store کریں جو due time سے keyed ہو، صرف وہی tasks poll کریں جو *ابھی* due ہیں، اور انہیں idempotent workers کو **at-least-once** delivery کے ساتھ دیں۔ ہر tick پر کبھی 1 کروڑ rows scan نہ کریں — fire time کے حساب سے index کریں تاکہ ہر poll صرف due چیزوں کو چھوئے۔

## فن تعمیر

```text
API ─▶ Task store (DB/Redis ZSET, score = due_ts)  ── 10M tasks, sharded
             │
     Poller (leader per partition) ── ZPOPMIN due<=now ──▶ Ready queue (Kafka)
             │ leader election (etcd/ZK)                       │
             ▼                                                 ▼
     other pollers idle/standby                       Worker pool (idempotent)
                                                        └─ ack ✔ / retry ✖ ─▶ DLQ
```

## اجزاء اور بہاؤ

- **Fire time سے indexed task store**: ایک Redis sorted set (`ZADD tasks score=due_ts`) یا ایک DB table جو `(run_at)` پر indexed ہو۔ `ZPOPMIN`/`ZRANGEBYSCORE now` صرف اسی سیکنڈ due tasks کھینچتا ہے — O(log n)، table scan نہیں۔ task-id کے حساب سے **Sharding/partitioning** 1 کروڑ tasks کو nodes میں پھیلاتی ہے تاکہ کوئی ایک store hot نہ ہو۔
- **Leader election کے ساتھ poller**: ہر partition کا ایک active poller ہوتا ہے جو etcd/ZooKeeper کے ذریعے منتخب ہوتا ہے؛ ناکامی پر standbys سنبھال لیتے ہیں۔ فی partition ایک leader دو pollers کو ایک ہی task dispatch کرنے سے روکتا ہے، جبکہ partitioning throughput اونچا رکھتی ہے۔
- **Ready queue (Kafka)**: due tasks enqueue ہوتے ہیں، *scheduling* کو *execution* سے decouple کرتے ہوئے۔ Workers poller سے آزادانہ scale ہوتے ہیں۔
- **Idempotent workers** execute کرتے ہیں اور **ack** کرتے ہیں۔ چونکہ delivery at-least-once ہے، ایک task دو بار چل سکتا ہے (poller dispatch کے بعد، done مارک کرنے سے پہلے crash ہوا) — لہٰذا کام خود idempotent ہونا چاہیے، `task_id` پر keyed، ورنہ آپ کسی customer سے دو بار charge کر لیں گے۔ ناکامیاں backoff کے ساتھ retry ہوتی ہیں، پھر DLQ میں جاتی ہیں۔

## انٹرویو کا نقطۂ نظر

انٹرویو لینے والا دو چیزیں جانچتا ہے: **efficient time lookup** اور **exactly-once بمقابلہ at-least-once**۔ "اچھا" ایک table پر cron loop ہے؛ "عمدہ" sorted-set index کے ساتھ یہ ایماندارانہ اعتراف ہے کہ distributed exactly-once ناقابلِ عمل ہے، لہٰذا آپ **at-least-once + idempotent workers** چنتے ہیں۔ ایک کلاسک جال: ایک واحد scheduler node پر انحصار — یہ ایک SPOF اور throughput چھت ہے۔ ایک اور: بہت موٹا poll کرنا (ہر منٹ) جب tasks کو سیکنڈ کی درستگی چاہیے، یا بہت باریک اور store کو hammer کرنا۔

## توازن اور ناکامی

- **درستگی بمقابلہ load**: 1s tick سیکنڈ کی سطح کی درستگی دیتا ہے مگر زیادہ polls؛ tasks کو per-minute پھر per-second sub-queues میں bucket کریں تاکہ scan لاگت کم ہو (وہ "timing wheel" / hashed-wheel طریقہ جو Kafka اور Quartz استعمال کرتے ہیں)۔
- **At-least-once بمقابلہ exactly-once**: آپ crash boundary کے پار حقیقی exactly-once نہیں پا سکتے؛ idempotency keys double execution کو بے ضرر بنا دیتی ہیں — صحیح trade۔
- **ناکامی**: اگر poller dispatch کے دوران مر جائے تو leader election ایک standby کو promote کرتا ہے اور un-acked tasks دوبارہ deliver ہوتے ہیں — کچھ ضائع نہیں ہوتا، کچھ دہرا سکتے ہیں۔ nodes میں **clock skew** (NTP) پر نظر رکھیں ورنہ tasks جلدی/دیر سے fire ہوتے ہیں؛ اور retries کو محدود کریں تاکہ ایک مستقل ناکام task ہمیشہ کے لیے loop نہ کرے — اسے معائنے کے لیے DLQ میں بھیجیں۔

فن تعمیر

اجزاء اور بہاؤ

انٹرویو کا نقطۂ نظر

توازن اور ناکامی

متعلقہ سوالات