{"title":"Design Distributed Task Queue","description":null,"content":"\n> **QUESTION**\n>\n> #### What is a Distributed Task Queue?\n>\n> A Distributed Task Queue is a system that manages the asynchronous execution of tasks across multiple worker nodes. It decouples task producers (who submit work) from task consumers (who execute work), enabling systems to handle background jobs, scheduled tasks, and workloads that would otherwise block user-facing operations.\n>\n> The core idea is straightforward: instead of executing expensive operations synchronously, you push them onto a queue and let workers process them independently. This pattern is fundamental to building scalable, resilient systems.\n>\n> **Popular Examples:** Celery (Python), Sidekiq (Ruby), Amazon SQS, RabbitMQ, Apache Kafka\n\n\nIn this article, we will explore the **high-level design of a distributed task queue**.\n\nLet's start by clarifying the requirements.\n\n---\n\n# 1. Clarifying Requirements\n\nBefore starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.\n\nHere is an example of how a discussion between the candidate and the interviewer might unfold:\n\n\n> **DISCUSSION**\n>\n> **Candidate:** \"What is the expected scale? How many tasks per day do we need to handle?\"\n>\n> **Interviewer:** \"Let's design for 100 million tasks per day, with peaks during business hours.\"\n>\n> **Candidate:** \"What types of tasks will the system handle? Are they short-running or long-running?\"\n>\n> **Interviewer:** \"Mostly short tasks (under 30 seconds), but we should support tasks up to 15 minutes.\"\n>\n> **Candidate:** \"Do we need to guarantee task execution? What happens if a worker crashes mid-task?\"\n>\n> **Interviewer:** \"Yes, we need at-least-once delivery. Tasks should be retried if a worker fails.\"\n>\n> **Candidate:** \"Should we support task prioritization and delayed execution?\"\n>\n> **Interviewer:** \"Yes, we need multiple priority levels and the ability to schedule tasks for future execution.\"\n>\n> **Candidate:** \"Do clients need to track task status and retrieve results?\"\n>\n> **Interviewer:** \"Yes, clients should be able to check if a task is pending, running, completed, or failed.\"\n\n\nAfter gathering the details, we can summarize the key system requirements.\n\n## 1.1 Functional Requirements\n\n- **Task Submission:** Clients can submit tasks with a payload and optional configuration (priority, delay, timeout).\n- **Task Execution:** Workers pull tasks from the queue and execute them.\n- **Task Status:** Clients can query the status of a submitted task.\n- **Retry on Failure:** Failed tasks are automatically retried with configurable backoff.\n- **Priority Queues:** Support multiple priority levels (high, normal, low).\n- **Delayed Tasks:** Schedule tasks to execute at a future time.\n- **Dead Letter Queue:** Tasks that exceed retry limits are moved to a DLQ for inspection.\n\n## 1.2 Non-Functional Requirements\n\n- **High Availability:** The system must be highly available (99.99% uptime).\n- **At-Least-Once Delivery:** Every task must be executed at least once.\n- **Low Latency:** Task pickup latency should be under 100ms for high-priority tasks.\n- **Scalability:** Handle 100 million tasks per day with horizontal scaling.\n- **Durability:** Submitted tasks must not be lost, even during failures.\n- **Ordering:** Best-effort ordering within the same priority level (not strict FIFO).\n\n---\n\n# 2. Back-of-the-Envelope Estimation\n\nTo understand the scale of our system, let's make some reasonable assumptions.\n\n\n> **NOTE**\n>\n> ### Assumptions:\n>\n> - Tasks submitted: **100 million per day**\n> - Average task duration: **5 seconds**\n\n\n#### **Task Submissions (Writes)**\n\n- Average write QPS = `100,000,000 / 86,400` ≈ **1,150 QPS (steady state)**\n- Peak write load (3x factor) ≈ **3,500 QPS**\n\n#### **Task Status Queries (Reads)**\n\n- Assume a **5:1 read/write ratio** (clients check status multiple times per task)\n- Status queries: **500 million per day**\n- Average read QPS = `500,000,000 / 86,400` ≈ **5,800 QPS (steady state)**\n- Peak read load (3x factor) ≈ **17,500 QPS**\n\n#### **Worker Throughput**\n\n- Tasks per worker per day = `86,400 / 5` = **17,280 tasks**\n- Workers needed = `100,000,000 / 17,280` ≈ **5,800 workers**\n- With overhead and buffer ≈ **8,000-10,000 workers**\n\n#### **Storage (30 days retention)**\n\nEach task stores:\n\n- Task ID (~36 bytes, UUID)\n- Payload (avg 1 KB)\n- Metadata (~200 bytes: status, timestamps, retry count)\n\nTotal ≈ **1.2 KB per task**\n\n**Monthly storage:** `100M tasks/day * 30 days * 1.2 KB` ≈ **3.6 TB** for task metadata.\n\n---\n\n# 3. Core APIs\n\nThe distributed task queue needs APIs for task submission, status tracking, and management. Below are the core APIs required for basic functionality.\n\n### **1. Submit Task**\n\n#### Endpoint: `POST /tasks`\n\nSubmits a new task to the queue for execution.\n\n##### **Request Parameters:**\n\n- **task_type** _(required)_: Identifier for the type of task (e.g., \"send_email\", \"process_image\").\n- **payload** _(required)_: JSON object containing task-specific data.\n- **priority** _(optional)_: Priority level (\"high\", \"normal\", \"low\"). Default: \"normal\".\n- **delay_seconds** _(optional)_: Delay before task becomes eligible for execution.\n- **timeout_seconds** _(optional)_: Maximum execution time before task is considered failed.\n- **max_retries** _(optional)_: Maximum retry attempts. Default: 3.\n- **idempotency_key** _(optional)_: Client-provided key for deduplication.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"task_id\": \"550e8400-e29b-41d4-a716-446655440000\",\n \"status\": \"pending\",\n \"created_at\": \"2024-01-15T10:30:00Z\",\n \"scheduled_at\": \"2024-01-15T10:30:00Z\"\n}\n```\n\n\n##### **Error Cases:**\n\n- `400 Bad Request`: Invalid payload or unknown task type.\n- `429 Too Many Requests`: Rate limit exceeded.\n- `409 Conflict`: Duplicate idempotency key with different payload.\n\n### **2. Get Task Status**\n\n#### Endpoint: `GET /tasks/{task_id}`\n\nRetrieves the current status and details of a task.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"task_id\": \"550e8400-e29b-41d4-a716-446655440000\",\n \"task_type\": \"send_email\",\n \"status\": \"completed\",\n \"priority\": \"normal\",\n \"created_at\": \"2024-01-15T10:30:00Z\",\n \"started_at\": \"2024-01-15T10:30:05Z\",\n \"completed_at\": \"2024-01-15T10:30:08Z\",\n \"retry_count\": 0,\n \"result\": {\"message_id\": \"abc123\"}\n}\n```\n\n\n##### **Status Values:**\n\n- `pending`: Task is waiting in the queue.\n- `scheduled`: Task is delayed and waiting for its scheduled time.\n- `running`: Task is currently being executed by a worker.\n- `completed`: Task finished successfully.\n- `failed`: Task failed after exhausting retries.\n- `dead`: Task moved to dead letter queue.\n\n##### **Error Cases:**\n\n- `404 Not Found`: Task ID does not exist.\n\n### **3. Cancel Task**\n\n#### Endpoint: `DELETE /tasks/{task_id}`\n\nCancels a pending or scheduled task. Running tasks cannot be cancelled.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"task_id\": \"550e8400-e29b-41d4-a716-446655440000\",\n \"status\": \"cancelled\",\n \"cancelled_at\": \"2024-01-15T10:31:00Z\"\n}\n```\n\n\n##### **Error Cases:**\n\n- `404 Not Found`: Task ID does not exist.\n- `409 Conflict`: Task is already running or completed.\n\n### **4. Internal: Fetch Tasks (Worker API)**\n\n#### Endpoint: `POST /internal/tasks/fetch`\n\nWorkers call this endpoint to fetch tasks for execution. This is an internal API not exposed to clients.\n\n##### **Request Parameters:**\n\n- **worker_id** _(required)_: Unique identifier for the worker.\n- **task_types** _(required)_: List of task types this worker can handle.\n- **batch_size** _(optional)_: Maximum number of tasks to fetch. Default: 1.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"tasks\": [\n {\n \"task_id\": \"550e8400-e29b-41d4-a716-446655440000\",\n \"task_type\": \"send_email\",\n \"payload\": {\"to\": \"user@example.com\", \"subject\": \"Hello\"},\n \"timeout_seconds\": 30,\n \"attempt\": 1\n }\n ],\n \"lease_duration_seconds\": 60\n}\n```\n\n\n---\n\n# 4. High-Level Design\n\nAt a high level, our system must satisfy three core requirements:\n\n1. **Task Ingestion:** Accept tasks from clients and persist them durably.\n2. **Task Distribution:** Efficiently distribute tasks to available workers.\n3. **Task Execution:** Execute tasks reliably with proper failure handling.\n\nThe system has an interesting asymmetry: task submissions are relatively lightweight writes, but task distribution requires careful coordination to ensure exactly one worker picks up each task.\n\n**Note:** Instead of presenting the full architecture at once, we'll build it incrementally by addressing one requirement at a time. This approach is easier to follow and mirrors how you would explain the design in an interview.\n\n## 4.1 Requirement 1: Task Ingestion\n\nClients need to submit tasks reliably. Even if internal components are temporarily unavailable, we should accept and durably store the task.\n\n### Components Needed\n\n#### **API Gateway**\n\nThe entry point for all client requests. Handles authentication, rate limiting, and request routing.\n\n**Responsibilities:**\n\n- Authenticate and authorize clients.\n- Apply rate limiting per client/tenant.\n- Route requests to the appropriate service.\n\n#### **Task Service**\n\nHandles all task-related operations: submission, status queries, and cancellation.\n\n**Responsibilities:**\n\n- Validate task payloads against registered schemas.\n- Generate unique task IDs.\n- Persist task metadata to the database.\n- Enqueue tasks for processing.\n\n#### **Task Database**\n\nStores task metadata, status, and results. This is the source of truth for task state.\n\n**Responsibilities:**\n\n- Durably store all task information.\n- Support efficient queries by task ID and status.\n- Handle high write throughput for task submissions.\n\n### Flow: Submitting a Task\n\n\n```mermaid\nflowchart LR\n Client[Client]:::primary --> Gateway[API Gateway]:::secondary\n Gateway --> TaskSvc[Task Service]:::primary\n TaskSvc --> DB[(Task Database)]:::purple\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\n1. Client sends a `POST /tasks` request with the task payload.\n2. The **API Gateway** authenticates the request and applies rate limiting.\n3. The **Task Service** receives the request and: validates the payload against the task type schema, generates a unique task ID (UUID) and persists the task with status \"pending\" to the **Task Database**.\n4. The service returns the task ID to the client.\n\nAt this point, the task is durably stored but not yet available for workers. We need a mechanism to make it available for execution.\n\n---\n\n## 4.2 Requirement 2: Task Distribution\n\nWorkers need to efficiently discover and claim tasks. This is the most challenging part of the design because we must ensure:\n\n- Each task is processed by exactly one worker (no duplicates).\n- Tasks are distributed fairly across workers.\n- High-priority tasks are processed before low-priority ones.\n\n### Additional Components Needed\n\n#### **Message Queue**\n\nA distributed queue that holds tasks ready for execution. Workers pull tasks from this queue.\n\n**Responsibilities:**\n\n- Store tasks until workers are ready to process them.\n- Support multiple priority levels (separate queues per priority).\n- Provide visibility timeout to handle worker failures.\n\n**Technology choices:** Redis, Amazon SQS, RabbitMQ, or Apache Kafka.\n\n#### **Scheduler Service**\n\nHandles delayed tasks and periodic scheduling. Moves tasks from \"scheduled\" state to the message queue when their time arrives.\n\n**Responsibilities:**\n\n- Track tasks scheduled for future execution.\n- Move delayed tasks to the queue at the scheduled time.\n- Handle recurring/cron-style tasks (if supported).\n\n### Flow: Making Tasks Available\n\n\n```mermaid\nflowchart LR\n TaskSvc[Task Service]:::primary --> Queue[Message Queue]:::orange\n Scheduler[Scheduler]:::secondary --> Queue\n DB[(Task DB)]:::purple --> Scheduler\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\n**For immediate tasks:**\n\n1. After persisting to the database, the **Task Service** enqueues the task to the **Message Queue**.\n2. The task is now available for workers to pick up.\n\n**For delayed tasks:**\n\n1. The **Task Service** persists the task with status \"scheduled\" and a `scheduled_at` timestamp.\n2. The **Scheduler Service** periodically scans for tasks where `scheduled_at <= now()`.\n3. The scheduler enqueues these tasks to the **Message Queue** and updates their status to \"pending\".\n\n---\n\n## 4.3 Requirement 3: Task Execution\n\nWorkers must reliably execute tasks and handle failures gracefully.\n\n### Additional Components Needed\n\n#### **Workers**\n\nStateless processes that fetch tasks from the queue, execute them, and report results.\n\n**Responsibilities:**\n\n- Fetch tasks from the message queue.\n- Execute task logic based on task type.\n- Report success/failure back to the Task Service.\n- Handle graceful shutdown without losing tasks.\n\n#### **Dead Letter Queue (DLQ)**\n\nA separate queue for tasks that have failed permanently (exceeded retry limits).\n\n**Responsibilities:**\n\n- Store failed tasks for manual inspection.\n- Preserve full task context for debugging.\n- Allow manual retry or deletion.\n\n### Flow: Executing a Task\n\n\n```mermaid\nflowchart LR\n Queue[Message Queue]:::orange --> Worker[Worker]:::primary\n Worker --> TaskSvc[Task Service]:::secondary\n TaskSvc --> DB[(Task DB)]:::purple\n Worker -.-> DLQ[Dead Letter Queue]:::red\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n1. **Worker** polls the **Message Queue** for available tasks.\n2. The queue returns a task with a **visibility timeout** (e.g., 60 seconds). During this window, no other worker can see this task.\n3. The worker calls the **Task Service** to mark the task as \"running\".\n4. The worker executes the task logic.\n5. **On success:** Worker calls the Task Service to mark the task as \"completed\" with the result. The task is deleted from the queue.\n6. **On failure:** Worker calls the Task Service to mark the task as \"failed\".\n\n - If retries remain, the task is re-enqueued with exponential backoff.\n - If retries exhausted, the task is moved to the **Dead Letter Queue**.\n\n---\n\n## 4.4 Putting It All Together\n\nHere is the complete architecture combining all requirements:\n\n\n```mermaid\nflowchart TB\n subgraph Clients\n C1[Client 1]:::rose\n C2[Client 2]:::rose\n end\n\n subgraph Ingestion\n Gateway[API Gateway]:::secondary\n TaskSvc[Task Service]:::primary\n end\n\n subgraph Storage\n DB[(Task Database)]:::purple\n Cache[(Redis Cache)]:::teal\n end\n\n subgraph Queuing\n HQ[High Priority Queue]:::red\n NQ[Normal Priority Queue]:::orange\n LQ[Low Priority Queue]:::yellow\n DLQ[Dead Letter Queue]:::red\n end\n\n subgraph Scheduling\n Scheduler[Scheduler Service]:::secondary\n end\n\n subgraph Workers\n W1[Worker Pool 1]:::primary\n W2[Worker Pool 2]:::primary\n W3[Worker Pool 3]:::primary\n end\n\n C1 --> Gateway\n C2 --> Gateway\n Gateway --> TaskSvc\n TaskSvc --> DB\n TaskSvc --> Cache\n TaskSvc --> HQ\n TaskSvc --> NQ\n TaskSvc --> LQ\n\n DB --> Scheduler\n Scheduler --> HQ\n Scheduler --> NQ\n Scheduler --> LQ\n\n HQ --> W1\n NQ --> W2\n LQ --> W3\n\n W1 --> TaskSvc\n W2 --> TaskSvc\n W3 --> TaskSvc\n\n W1 -.-> DLQ\n W2 -.-> DLQ\n W3 -.-> DLQ\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef rose fill:#f783ac,stroke:#000,color:#000\n```\n\n\n### Core Components Summary\n\n\n| ##### Component | ##### Purpose |\n| --- | --- |\n| API Gateway | Authentication, rate limiting, request routing |\n| Task Service | Task CRUD operations, status management |\n| Task Database | Durable storage for task metadata and results |\n| Redis Cache | Fast status lookups, idempotency key storage |\n| Message Queues | Task distribution to workers (per priority) |\n| Scheduler | Delayed task management, moves tasks to queues |\n| Workers | Task execution, result reporting |\n| Dead Letter Queue | Storage for permanently failed tasks |\n\n\n---\n\n# 5. Database Design\n\n### 5.1 SQL vs NoSQL\n\nTo choose the right database for our needs, let's consider some factors:\n\n- We need to store hundreds of millions of task records.\n- Most operations are simple: insert, update status, lookup by task ID.\n- We need efficient queries by status (for monitoring and cleanup).\n- Strong consistency is important for task state transitions.\n- The schema is relatively fixed and well-defined.\n\nGiven these points, a **SQL database** like **PostgreSQL** is a solid choice due to:\n\n- Strong consistency guarantees for status updates.\n- Efficient indexing for status-based queries.\n- Mature tooling for operations and monitoring.\n\nFor very high scale (billions of tasks), a **NoSQL database** like **Cassandra** or **DynamoDB** may be more appropriate, with the trade-off of eventual consistency.\n\n**Hybrid approach:** Use PostgreSQL for task metadata and Redis for the actual queuing mechanism. This combines the durability of SQL with the speed of in-memory queues.\n\n### 5.2 Database Schema\n\n#### **1. Tasks Table**\n\nStores all task metadata and state.\n\n\n| ##### Field | ##### Type | ##### Description |\n| --- | --- | --- |\n| `task_id` | UUID (PK) | Unique identifier for the task |\n| `task_type` | VARCHAR(100) | Type of task (e.g., \"send_email\") |\n| `payload` | JSONB | Task-specific data |\n| `status` | VARCHAR(20) | Current status (pending, running, completed, failed, dead) |\n| `priority` | VARCHAR(10) | Priority level (high, normal, low) |\n| `created_at` | TIMESTAMP | When the task was submitted |\n| `scheduled_at` | TIMESTAMP | When the task should be executed |\n| `started_at` | TIMESTAMP | When execution began |\n| `completed_at` | TIMESTAMP | When execution finished |\n| `timeout_seconds` | INTEGER | Maximum execution time |\n| `max_retries` | INTEGER | Maximum retry attempts |\n| `retry_count` | INTEGER | Current retry count |\n| `last_error` | TEXT | Error message from last failure |\n| `result` | JSONB | Result data (on success) |\n| `worker_id` | VARCHAR(100) | ID of worker executing the task |\n| `idempotency_key` | VARCHAR(255) | Client-provided deduplication key |\n\n\n**Indexes:**\n\n- Primary key on `task_id`\n- Index on `status` for monitoring queries\n- Index on `scheduled_at` for scheduler queries\n- Unique index on `idempotency_key` (where not null)\n- Composite index on `(status, priority, created_at)` for queue ordering\n\n#### **2. Task History Table**\n\nStores execution attempts for debugging and auditing.\n\n\n| ##### Field | ##### Type | ##### Description |\n| --- | --- | --- |\n| `id` | BIGSERIAL (PK) | Auto-incrementing ID |\n| `task_id` | UUID (FK) | Reference to the task |\n| `attempt` | INTEGER | Attempt number (1, 2, 3...) |\n| `worker_id` | VARCHAR(100) | Worker that processed this attempt |\n| `started_at` | TIMESTAMP | When this attempt started |\n| `ended_at` | TIMESTAMP | When this attempt ended |\n| `status` | VARCHAR(20) | Outcome (success, failure, timeout) |\n| `error` | TEXT | Error message if failed |\n\n\n#### **3. Dead Letter Queue Table**\n\nStores tasks that have permanently failed.\n\n\n| ##### Field | ##### Type | ##### Description |\n| --- | --- | --- |\n| `id` | BIGSERIAL (PK) | Auto-incrementing ID |\n| `task_id` | UUID | Original task ID |\n| `task_type` | VARCHAR(100) | Type of task |\n| `payload` | JSONB | Original payload |\n| `failure_reason` | TEXT | Why the task permanently failed |\n| `retry_count` | INTEGER | Number of attempts made |\n| `moved_at` | TIMESTAMP | When moved to DLQ |\n| `resolved_at` | TIMESTAMP | When manually resolved (if applicable) |\n\n\n---\n\n# 6. Design Deep Dive\n\nNow that we have the high-level architecture and database schema in place, let's dive deeper into some critical design choices.\n\n## 6.1 Task Distribution Strategies\n\nHow workers receive tasks is fundamental to the system's performance and reliability. The right strategy depends on your scale, latency requirements, and infrastructure.\n\n### **Approach 1: Pull-Based (Polling)**\n\nWorkers actively poll the queue for new tasks at regular intervals.\n\n#### How It Works\n\n1. Each worker runs a loop that periodically calls the queue's \"fetch\" operation.\n2. If tasks are available, the worker receives one or more tasks.\n3. If the queue is empty, the worker waits and retries after a delay.\n\n\n```shell\nwhile running:\n tasks = queue.fetch(batch_size=10, wait_timeout=30s)\n if tasks:\n for task in tasks:\n process(task)\n else:\n sleep(backoff_interval)\n```\n\n\n#### Pros\n\n- **Simple implementation:** Workers control their own pace.\n- **Natural backpressure:** Workers only fetch when ready.\n- **Fault tolerant:** Worker crashes don't affect the queue.\n\n#### Cons\n\n- **Latency:** Tasks may wait up to the polling interval before pickup.\n- **Wasted resources:** Empty polls consume network and CPU.\n- **Thundering herd:** Many workers polling simultaneously can overload the queue.\n\n#### Optimization: Long Polling\n\nInstead of short polls with sleep intervals, use **long polling**: the worker's fetch request blocks until either a task is available or a timeout expires.\n\nThis reduces empty polls while keeping latency low.\n\n### **Approach 2: Push-Based (Event-Driven)**\n\nThe queue actively pushes tasks to workers as they become available.\n\n#### How It Works\n\n1. Workers establish a persistent connection to the queue (WebSocket, gRPC stream, or message broker subscription).\n2. When a task arrives, the queue immediately pushes it to an available worker.\n3. The worker processes the task and acknowledges completion.\n\n#### Pros\n\n- **Low latency:** Tasks are delivered immediately.\n- **Efficient:** No wasted polling requests.\n- **Real-time:** Ideal for time-sensitive tasks.\n\n#### Cons\n\n- **Complex connection management:** Must handle disconnections and reconnections.\n- **Backpressure challenges:** Workers can be overwhelmed if pushed too fast.\n- **Stateful broker:** The queue must track worker connections.\n\n### **Approach 3: Hybrid (Recommended)**\n\nCombine the best of both approaches: use push notifications to wake workers, but let workers pull the actual tasks.\n\n#### How It Works\n\n1. Workers subscribe to a lightweight notification channel.\n2. When tasks arrive, the queue sends a \"tasks available\" signal.\n3. Workers fetch tasks at their own pace upon receiving the signal.\n\nThis provides the low latency of push with the backpressure control of pull.\n\n### Summary and Recommendation\n\n\n| ##### Strategy | ##### Latency | ##### Complexity | ##### Backpressure | ##### Best For |\n| --- | --- | --- | --- | --- |\n| **Pull (Polling)** | Higher | Low | Excellent | Simple systems, batch processing |\n| **Pull (Long Polling)** | Medium | Low | Excellent | Most general-purpose queues |\n| **Push** | Lowest | High | Challenging | Real-time, time-critical tasks |\n| **Hybrid** | Low | Medium | Good | Large-scale production systems |\n\n\n**Recommendation:** Start with **long polling** for simplicity. Move to a hybrid approach if you need sub-second latency at scale.\n\n---\n\n## 6.2 Delivery Guarantees\n\nMessage delivery semantics determine what happens when failures occur. This is one of the most important design decisions for a task queue.\n\n### **At-Most-Once Delivery**\n\nEach task is delivered to a worker at most one time. If the worker crashes, the task is lost.\n\n#### How It Works\n\n1. Worker fetches a task from the queue.\n2. The task is immediately deleted from the queue.\n3. Worker processes the task.\n4. If the worker crashes mid-processing, the task is gone.\n\n#### When to Use\n\n- Tasks are not critical (e.g., analytics events).\n- Duplicate processing is worse than missing tasks.\n- Tasks are cheap to regenerate.\n\n### **At-Least-Once Delivery**\n\nEach task is guaranteed to be delivered at least once, but may be delivered multiple times.\n\n#### How It Works\n\n1. Worker fetches a task from the queue.\n2. The task becomes **invisible** to other workers (visibility timeout).\n3. Worker processes the task.\n4. **On success:** Worker explicitly deletes the task from the queue.\n5. **On failure/timeout:** The task becomes visible again and another worker picks it up.\n\n\n```shell\nTask Flow:\nSubmit -> Queue (visible) -> Fetched (invisible for 60s) -> Success -> Deleted\n |\n +-> Timeout -> Visible again -> Retry\n```\n\n\n#### The Visibility Timeout\n\nThe visibility timeout is critical for at-least-once delivery:\n\n- **Too short:** Tasks become visible while still being processed, causing duplicates.\n- **Too long:** Failed tasks take too long to be retried.\n\n**Best practice:** Set the visibility timeout to 2-3x the expected task duration. For variable-duration tasks, allow workers to extend their lease.\n\n#### Handling Duplicates\n\nSince tasks may be delivered multiple times, your workers must be **idempotent**. Common strategies:\n\n1. **Idempotency keys:** Check if the task was already processed before executing.\n2. **Database constraints:** Use unique constraints to prevent duplicate side effects.\n3. **Conditional updates:** Use optimistic locking to detect concurrent processing.\n\n### **Exactly-Once Delivery**\n\nEach task is processed exactly once, regardless of failures. This is the holy grail but is extremely difficult to achieve in distributed systems.\n\n#### Why It's Hard\n\nTrue exactly-once delivery requires coordination between the queue and the processing logic, which typically means:\n\n1. **Transactional outbox:** The task completion and side effects must be in the same transaction.\n2. **Two-phase commit:** Coordinate between the queue and external systems.\n3. **Idempotent consumers:** Make duplicate processing have no additional effect.\n\nIn practice, \"exactly-once\" is usually implemented as \"at-least-once delivery with idempotent processing.\"\n\n### Recommendation\n\n\n| ##### Guarantee | ##### Complexity | ##### Data Safety | ##### Best For |\n| --- | --- | --- | --- |\n| **At-Most-Once** | Lowest | Lowest | Non-critical, fire-and-forget |\n| **At-Least-Once** | Medium | High | Most production systems |\n| **Exactly-Once** | Highest | Highest | Financial transactions, critical workflows |\n\n\n**Recommendation:** Use **at-least-once delivery** with idempotent task handlers. This provides strong guarantees without the complexity of true exactly-once semantics.\n\n---\n\n## 6.3 Handling Task Failures and Retries\n\nFailures are inevitable in distributed systems. A robust retry strategy ensures tasks eventually succeed while avoiding infinite loops and system overload.\n\n### Types of Failures\n\n1. **Transient failures:** Temporary issues that may resolve on retry (network timeout, service unavailable).\n2. **Permanent failures:** Issues that will never succeed on retry (invalid input, missing resource).\n3. **Poison pills:** Tasks that crash workers (infinite loops, memory exhaustion).\n\n### Retry Strategy\n\n#### 1. Exponential Backoff\n\nIncrease the delay between retries exponentially to avoid overwhelming failing dependencies.\n\n\n```shell\nAttempt 1: Immediate\nAttempt 2: 10 seconds\nAttempt 3: 100 seconds\nAttempt 4: 1000 seconds (~17 minutes)\n```\n\n\n**Formula:** `delay = base_delay * (multiplier ^ attempt)`\n\n#### 2. Jitter\n\nAdd randomness to prevent synchronized retries from many failed tasks hitting the system simultaneously.\n\n\n```shell\ndelay = base_delay * (multiplier ^ attempt) * random(0.5, 1.5)\n```\n\n\n#### 3. Maximum Retries\n\nSet a limit to prevent infinite retry loops. Common values are 3-5 retries.\n\n#### 4. Retry Classification\n\nNot all errors should be retried. Classify errors and handle them appropriately:\n\n\n| ##### Error Type | ##### Example | ##### Retry? |\n| --- | --- | --- |\n| Transient | Connection timeout | Yes |\n| Rate limit | 429 Too Many Requests | Yes (with longer backoff) |\n| Client error | 400 Bad Request | No |\n| Server error | 500 Internal Error | Yes (limited) |\n| Permanent | Resource not found | No |\n\n\n### Dead Letter Queue (DLQ)\n\nTasks that exhaust all retries are moved to a **Dead Letter Queue** for manual inspection.\n\n#### DLQ Best Practices\n\n1. **Preserve context:** Store the original payload, all error messages, and retry history.\n2. **Alerting:** Monitor DLQ depth and alert when tasks accumulate.\n3. **Manual replay:** Provide tools to retry DLQ tasks after fixing the underlying issue.\n4. **Retention:** Keep DLQ tasks for a reasonable period (7-30 days) before deletion.\n\n### Poison Pill Detection\n\nSome tasks can crash workers (out-of-memory, infinite loops). Detect and isolate these:\n\n1. **Attempt counter:** Track how many times a task has been attempted.\n2. **Worker health:** Monitor worker crash patterns.\n3. **Fast-fail:** If a task has crashed multiple workers, move it directly to DLQ.\n4. **Resource limits:** Run tasks in sandboxed environments with memory and CPU limits.\n\n---\n\n## 6.4 Priority and Fairness\n\nWhen your queue handles different types of tasks, you need mechanisms to ensure important tasks are processed first while still making progress on lower-priority work.\n\n### Separate Queues per Priority\n\nThe simplest approach: maintain separate queues for each priority level.\n\n\n```shell\nHigh Priority Queue -> Worker Pool\nNormal Priority Queue -> Worker Pool\nLow Priority Queue -> Worker Pool\n```\n\n\n#### Worker Assignment Strategies\n\n**Dedicated workers:** Assign specific workers to each priority level.\n\n- Pros: Guaranteed capacity for each priority.\n- Cons: Underutilized workers when queues are empty.\n\n**Weighted polling:** Workers poll high-priority queues more frequently.\n\n- Pros: Flexible resource allocation.\n- Cons: Complex to tune weights correctly.\n\n**Priority draining:** Workers always drain higher-priority queues first.\n\n- Pros: Simple logic, high-priority tasks always go first.\n- Cons: Low-priority tasks may starve.\n\n### Preventing Starvation\n\nIf high-priority tasks constantly arrive, low-priority tasks may never execute. Strategies to prevent this:\n\n1. **Aging:** Gradually increase the priority of old tasks.\n2. **Minimum throughput:** Reserve a percentage of workers for lower priorities.\n3. **Time slots:** Alternate between priority levels on a schedule.\n\n### Task Affinity\n\nSome tasks should be processed by specific workers (e.g., tasks for the same user should go to the same worker for caching benefits).\n\n#### Consistent Hashing\n\nRoute tasks to workers based on a hash of the task's affinity key:\n\n\n```shell\nworker_index = hash(user_id) % num_workers\n```\n\n\nThis ensures tasks for the same user usually go to the same worker, while still distributing load evenly.\n\n---\n\n## 6.5 Scaling Strategies\n\nAs task volume grows, different components require different scaling approaches.\n\n### Scaling the Task Service\n\nThe Task Service is stateless and can be horizontally scaled behind a load balancer.\n\n**Auto-scaling triggers:**\n\n- CPU utilization > 70%\n- Request latency p99 > 100ms\n- Queue depth growing faster than drain rate\n\n### Scaling the Message Queue\n\nDifferent queue technologies scale differently:\n\n\n| ##### Technology | ##### Scaling Approach |\n| --- | --- |\n| Redis | Cluster mode with hash slots |\n| SQS | Automatically scales, no limit |\n| RabbitMQ | Federation or sharding by queue |\n| Kafka | Add partitions, rebalance consumers |\n\n\n### Scaling Workers\n\nWorkers are the most common scaling target. Considerations:\n\n1. **Scale based on queue depth:** Add workers when queue grows, remove when empty.\n2. **Scale based on latency:** Add workers when task wait time exceeds threshold.\n3. **Over-provision for peaks:** Maintain headroom for traffic spikes.\n4. **Graceful shutdown:** Allow workers to finish current tasks before termination.\n\n### Scaling the Database\n\nThe Task Database can become a bottleneck at high scale.\n\n**Read scaling:** Add read replicas for status queries. **Write scaling:** Shard by task ID or tenant ID. **Archive old data:** Move completed tasks to cold storage after a retention period.\n\n### Multi-Region Deployment\n\nFor global availability, deploy the task queue in multiple regions:\n\n1. **Regional queues:** Tasks submitted in a region are processed in that region.\n2. **Cross-region replication:** Critical tasks are replicated to a backup region.\n3. **Failover:** If a region fails, tasks can be rerouted to another region.\n\n---\n\n## 6.6 Ensuring Exactly-Once Task Execution\n\nWhile true exactly-once delivery is difficult, we can achieve effective exactly-once processing through idempotency.\n\n### Idempotency Keys\n\nClients provide a unique key with each task submission. The system uses this key to detect and reject duplicates.\n\n**Implementation:**\n\n1. Store idempotency keys in Redis with a TTL (e.g., 24 hours).\n2. On task submission, check if the key exists.\n3. If exists, return the existing task ID without creating a duplicate.\n4. If not, create the task and store the key.\n\n\n```shell\ndef submit_task(payload, idempotency_key):\n existing = redis.get(f\"idempotency:{idempotency_key}\")\n if existing:\n return get_task(existing) # Return existing task\n\n task = create_task(payload)\n redis.setex(f\"idempotency:{idempotency_key}\", 86400, task.id)\n return task\n```\n\n\n### Worker-Side Idempotency\n\nFor tasks that modify external systems, the worker must ensure idempotency:\n\n1. **Check before write:** Query the target system to see if the action was already performed.\n2. **Conditional updates:** Use version numbers or ETags to prevent duplicate writes.\n3. **Unique constraints:** Let the database reject duplicate operations.\n\n### Deduplication Windows\n\nFor some use cases, you may want to deduplicate tasks within a time window (e.g., don't send more than one notification per user per hour).\n\n**Implementation:**\n\n1. Create a deduplication key from task attributes (e.g., `notify:user123`).\n2. Check if a task with this key was recently executed.\n3. If yes, skip or merge with the existing task.\n\n---\n\n## References\n\n- [Designing Data-Intensive Applications](undefined) - Martin Kleppmann's essential book covering message queues, delivery guarantees, and distributed systems fundamentals\n- [Amazon SQS Documentation](undefined) - AWS's managed queue service with detailed explanations of visibility timeout and dead letter queues\n- [Celery Architecture](undefined) - Popular distributed task queue for Python with extensive documentation on task routing and retries\n- [RabbitMQ Reliability Guide](undefined) - Covers message acknowledgments, persistence, and high availability patterns\n- [Building Reliable Reprocessing and Dead Letter Queues with Kafka](undefined) - Uber's engineering blog on handling failures at scale\n\n---\n\n# Quiz","pageType":"system-design-interviews"}

Design Distributed Task Queue

Ashish Pratap Singh

Get Premium