Building a Priority Task Queue with Dead-Letter Support

Redis sorted sets, atomic dequeue with Lua, and a dead-letter queue that catches tasks that can't be saved

By SysAdmin · Published 2026-05-27

Building a Priority Task Queue with Dead-Letter Support

Every message broker — from RabbitMQ to SQS — implements priority queues and dead-letter queues. Building one from scratch on Redis teaches you the atomic operations that make them reliable.

1. The Problem

Build a task queue where:

• Tasks have numeric priorities (higher = dequeued first)
• Equal priorities follow FIFO order
• Failed tasks can be retried up to a configurable limit
• Tasks that exhaust retries go to a dead-letter queue (DLQ)
• Concurrent consumers must never receive the same task
• All state persisted in Redis — no in-memory queues

2. The Naïve Approach (and Why It Fails)

PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(t -> -t.priority));

public String dequeue() {
    return queue.poll().id;  // Not thread-safe!
}

Problems:

1. Not distributed — each app instance has its own queue, so tasks get processed multiple times
2. Not atomic — two threads calling poll() simultaneously can get the same task
3. No persistence — restart the app, lose all pending tasks

3. The Right Model

Redis gives us the perfect primitives:

Key Design: Compound Scores for FIFO Tiebreaking

Redis sorted sets order by score, but equal scores have undefined order. To guarantee FIFO within the same priority:

long seq = redis.incr("tq:seq:" + queueName);
double score = priority + (1.0 - seq * 0.0000001);

Earlier tasks get a slightly higher fractional part, so ZREVRANGE returns them first among equal-priority tasks.

Task Lifecycle

PENDING → PROCESSING → COMPLETED
                     → FAILED → PENDING (retry)
                              → DEAD_LETTER (max retries exceeded)

4. The Implementation, Walked Through

The Interface

public interface TaskQueueContract {
    String enqueue(String queueName, String payload, int priority);
    String dequeue(String queueName);
    String getPayload(String taskId);
    boolean acknowledge(String taskId);
    boolean fail(String taskId, String errorMessage);
    boolean retry(String taskId);
    String getStatus(String taskId);
    List<String> getDeadLetterQueue(String queueName);
    int getQueueSize(String queueName);
    void configureMaxRetries(String queueName, int maxRetries);
}

Atomic Dequeue with Lua

The most critical operation. Without atomicity, two consumers calling dequeue could grab the same task:

local members = redis.call('ZREVRANGE', KEYS[1], 0, 0)
if #members == 0 then return nil end
local taskId = members[1]
redis.call('ZREM', KEYS[1], taskId)
redis.call('HSET', 'tq:task:' .. taskId, 'status', 'PROCESSING')
return taskId

This Lua script runs atomically in Redis:

1. Get the highest-score member
2. Remove it from the sorted set
3. Update its status to PROCESSING
4. Return the task ID

💡 Tip: ZREVRANGE (not ZRANGE) because we want highest priority first. A common mistake is using ZRANGE which gives lowest first.

Retry with DLQ Escalation

public boolean retry(String taskId) {
    String status = redis.hget(taskKey, "status");
    if (!"FAILED".equals(status)) return false;
    
    int retryCount = Integer.parseInt(redis.hget(taskKey, "retryCount"));
    int maxRetries = getMaxRetries(queueName);
    
    if (retryCount >= maxRetries) {
        redis.hset(taskKey, "status", "DEAD_LETTER");
        redis.rpush(dlqKey, taskId);
        return false;  // Moved to DLQ, not re-enqueued
    }
    
    redis.hset(taskKey, "status", "PENDING");
    redis.hset(taskKey, "retryCount", String.valueOf(retryCount + 1));
    redis.zadd(queueKey, score, taskId);
    return true;
}

⚠️ Trap: retry() returns false in TWO cases: (1) task is not in FAILED state, (2) task was moved to DLQ. The grader checks both. The DLQ transition is a side effect of a false return — don't confuse "retry failed" with "nothing happened."

Status Guards

Every state transition method checks the current status:

• acknowledge() only works on PROCESSING tasks
• fail() only works on PROCESSING tasks
• retry() only works on FAILED tasks

5. Performance + Concurrency

Redis Sorted Set Performance

ZADD and ZREM are O(log N) — fast enough for most workloads. The Lua script for dequeue adds minimal overhead since it's just 3 commands.

The grader targets 8,000+ ops/sec with p99 < 5ms — easily achievable since each operation is 2-4 Redis commands.

Concurrent Safety

The Lua-based dequeue is the key. Without it:

• Thread A: ZREVRANGE → gets task-1
• Thread B: ZREVRANGE → gets task-1 (same task!)
• Both process task-1 → duplicate work

With Lua, the ZREVRANGE + ZREM is atomic — Thread B would see an empty set or the next task.

6. What the Grader Checks

7. Takeaways

1. Sorted sets are natural priority queues. Redis ZADD/ZREVRANGE/ZREM gives you O(log N) priority queue operations with persistence built in.

1. Lua scripts prevent double-delivery. Any time you need "read and modify atomically" in Redis, a Lua script is the answer. It's simpler and faster than WATCH/MULTI.

1. Compound scores solve FIFO tiebreaking. Encoding a sequence number in the fractional part of the score gives you priority + FIFO without a secondary sort structure.

👉 Try it yourself: Priority Task Queue on Cruscible