12 min read

Redis vs SQS for a Crawl Frontier Queue

Once a crawl outgrows one process, the frontier — the queue of URLs still to fetch — has to live somewhere every worker can reach. The two defaults are a Redis instance you operate and a managed queue such as SQS. Both work; they fail differently, and the comparison that matters is not throughput but which of the frontier's four responsibilities each one actually covers. This page is part of Orchestrating Distributed Crawls Across Workers.

A frontier is four things, not one Four stacked responsibilities. Ordering decides which URL is fetched next and is where priority and depth limits live. Claiming ensures exactly one worker takes a URL, which both backends provide by different means. Redelivery returns an unfinished URL when a worker dies, built into SQS and hand-rolled on Redis. Deduplication answers whether a URL has been seen before, which SQS does not address at all. Ordering priority, depth limits, per-host fairness both, but Redis makes it explicit Claiming exactly one worker takes a URL SQS built in, Redis via SET NX Redelivery a dead worker returns its URLs SQS built in, Redis needs a reclaim loop Deduplication has this URL been seen before? Redis yes, SQS not at all Teams comparing "a queue against a queue" usually miss the fourth row, and then discover mid-migration that the dedup layer was doing more work than the queue was.

Comparison Table

Dimension Redis Amazon SQS
Claim semantics SET key NX or BRPOPLPUSH, composed by you Receive-with-visibility-timeout, built in
Redelivery on worker death A reclaim loop you run and supervise Automatic when the visibility timeout expires
Deduplication Same instance: a set or a Bloom filter Not addressed; needs a second system
Ordering / priority Explicit — one list per shard or priority None on standard queues; FIFO trades throughput
Latency per operation Sub-millisecond Tens of milliseconds
Capacity Bounded by instance memory Effectively unbounded
Operational burden Failover, persistence, maxmemory-policy None beyond IAM and queue configuration
Per-host politeness Natural, via one list per host shard Requires one queue per shard, or moving politeness into the worker
Cost shape An instance you pay for continuously Per request, plus per-message storage
Six properties a frontier depends on Two columns pairing the same six concerns. Redis gives per-shard lists with atomic claim semantics you build yourself, sub-millisecond latency, a visited set in the same store, memory-bound capacity, an instance you operate, and ordering you control. SQS gives a managed queue with built-in visibility timeouts and dead-letter handling, tens of milliseconds of latency, no place for a visited set, effectively unbounded capacity, nothing to operate, and no ordering guarantee on a standard queue. REDIS Per-shard lists, your own claim SET NX gives atomicity you compose Sub-millisecond latency the frontier is never the bottleneck Visited set in the same store one round trip, not two systems Memory-bound capacity tens of millions of URLs costs real RAM You operate it failover, persistence, memory policy Ordering is yours to define priority queues are straightforward AMAZON SQS Managed queue, built-in claims visibility timeout and DLQ included Tens of milliseconds latency fine unless you are fetching cached assets No visited set dedup needs a second system anyway Effectively unbounded capacity stops being a design constraint Nothing to operate the reason most teams pick it No ordering on standard queues FIFO queues trade throughput for it The decisive row is the third. A frontier is a queue plus a visited set, and SQS only solves the queue — so an SQS frontier is always two systems, which is a cost Redis does not have.

The routing decision in practice 

#!/usr/bin/env python3
# /opt/audit/frontier/backend.py — one interface, two implementations, so the
# crawl code never encodes which backend it is talking to.
from __future__ import annotations
import abc


class Frontier(abc.ABC):
    @abc.abstractmethod
    def push(self, url: str, shard: str, priority: int = 0) -> None: ...

    @abc.abstractmethod
    def claim(self, shard: str, visibility_s: int) -> str | None: ...

    @abc.abstractmethod
    def ack(self, url: str, shard: str) -> None: ...

    @abc.abstractmethod
    def seen(self, url: str) -> bool:
        """True if this URL has been claimed before. Note that SQS has no
        answer to this question — an SQS-backed frontier must compose a
        separate store, which is the single biggest difference between the
        two backends and the one most often discovered late."""

Defining the interface first is worth the small amount of ceremony. It forces the fourth method to exist, which forces the question of where deduplication lives to be answered before a backend is chosen rather than during the migration.

The Redis implementation covers all four responsibilities in one store:

class RedisFrontier(Frontier):
    def __init__(self, r, crawl_id: str):
        self.r, self.ns = r, f"crawl:{crawl_id}"

    def push(self, url, shard, priority=0):
        self.r.zadd(f"{self.ns}:q:{shard}", {url: -priority})

    def claim(self, shard, visibility_s):
        # Pop the highest-priority member and record it as in-flight, so a
        # reclaim loop can return it if this worker dies before ack().
        items = self.r.zpopmin(f"{self.ns}:q:{shard}", 1)
        if not items:
            return None
        url = items[0][0].decode()
        self.r.zadd(f"{self.ns}:inflight:{shard}",
                    {url: __import__("time").time() + visibility_s})
        return url

    def ack(self, url, shard):
        self.r.zrem(f"{self.ns}:inflight:{shard}", url)

    def seen(self, url) -> bool:
        # NX makes this atomic: exactly one worker gets False for a given URL.
        return not self.r.set(f"{self.ns}:seen:{url}", 1, nx=True, ex=86400 * 7)

The SQS implementation covers three of the four and has to compose the fourth:

class SqsFrontier(Frontier):
    def __init__(self, sqs, queue_urls: dict[str, str], dedup_store):
        self.sqs, self.queues = sqs, queue_urls
        self.dedup = dedup_store          # a Redis set, DynamoDB, or a Bloom filter

    def push(self, url, shard, priority=0):
        # Priority has no expression here; a standard queue is unordered.
        self.sqs.send_message(QueueUrl=self.queues[shard], MessageBody=url)

    def claim(self, shard, visibility_s):
        resp = self.sqs.receive_message(
            QueueUrl=self.queues[shard], MaxNumberOfMessages=1,
            VisibilityTimeout=visibility_s, WaitTimeSeconds=10)
        msgs = resp.get("Messages", [])
        if not msgs:
            return None
        self._handles[msgs[0]["Body"]] = msgs[0]["ReceiptHandle"]
        return msgs[0]["Body"]

    def ack(self, url, shard):
        self.sqs.delete_message(QueueUrl=self.queues[shard],
                                ReceiptHandle=self._handles.pop(url))

    def seen(self, url) -> bool:
        return self.dedup.check_and_add(url)   # a second system, unavoidably

Two observations fall out of writing both. First, push on the SQS side quietly discards priority, which is fine for a uniform crawl and is a silent behaviour change for one that used priority to reach high-value templates first. Second, seen on the SQS side takes a dependency the Redis version does not have — so an SQS frontier is always two systems, and the operational burden it saves on the queue it partly gives back on the dedup store.

Verification 

set -euo pipefail
# Run the same conformance suite against both implementations.
/opt/audit/.venv/bin/python3 -m pytest tests/test_frontier_conformance.py   --backend redis --backend sqs -q

# The three properties that must hold on either backend:
#  1. A claimed URL is never handed to a second worker before its visibility expires.
#  2. A URL claimed and never acked is redelivered after the visibility timeout.
#  3. seen() returns False exactly once per URL, under concurrency.

Expected output is an identical pass count for both backends. A conformance suite that runs against both is what makes a later migration a configuration change instead of a rewrite — and it is what catches the redelivery gap on Redis, which is otherwise only discovered when a worker dies in production.

Failure Modes

Three ways the swap goes wrong Three rows. Moving from Redis to SQS without replacing the visited set produces duplicate fetches at scale, because the queue never deduplicated anything. Moving to Redis without a reclaim loop loses URLs whenever a worker dies, because redelivery was a queue feature nobody replaced. And a per-host politeness scheme built on Redis sharding does not survive a move to a queue with no ordering guarantee. MIGRATION WHAT BREAKS FIX Redis to SQS duplicate fetches appear at scale, not in testing The visited set went away the queue never deduplicated — the other store did Keep a dedup store a Redis set or a Bloom filter alongside the managed queue SQS to Redis URLs vanish whenever a worker is killed Redelivery was a queue feature the visibility timeout had no equivalent on the new side Run a reclaim loop a supervised process per shard, not a library call Either direction per-host rate limits stop being enforceable Ordering assumptions moved host-sharded queues became one unordered queue Shard on the new side too one queue per shard, or accept that politeness moves elsewhere Every one of these is a responsibility that was covered by the old backend and silently uncovered by the new one, which is why the four-part model matters more than the feature comparison.

Redis memory grows until the instance refuses writes

The visited set is exact and the crawl is large. Confirm maxmemory-policy is noeviction so frontier data is never silently dropped, then move the visited set to a Bloom filter as described in deduplicating URLs in a distributed crawl.

SQS redelivers URLs that were already fetched

The visibility timeout is shorter than the time a worker takes to fetch, score and ack a page. Set it from the observed p99 processing time with headroom, and extend it explicitly for long-running pages rather than raising the global value for everyone.

Per-host rate limiting stops working after a backend change

Politeness was implemented by sharding hosts across queues, and the new backend has one queue. Either shard on the new side too — one SQS queue per shard — or move per-host pacing into the worker, accepting that a worker now needs to know about hosts it does not own.

FAQ

What is the single biggest difference between the two?

Deduplication. A crawl frontier is a queue plus a visited set, and SQS only solves the queue — it has no answer to "has this URL been seen before". That means an SQS frontier is always two systems, so the operational burden it saves by being managed is partly given back by the dedup store it forces you to run. Redis covers both in one instance, which is why it remains the default for crawlers even though the queue itself is less capable.

Does SQS handle worker death better than Redis?

Yes, and it is the clearest advantage it has. The visibility timeout is built in: a message claimed and never deleted becomes visible again automatically. On Redis the same behaviour has to be built — an in-flight sorted set scored by expiry, plus a supervised reclaim loop that returns expired entries to the queue. That loop is a real process that has to run on a schedule, and the most common Redis frontier defect is having written the function and never scheduled it.

Can per-host politeness be preserved on either backend?

On Redis it is natural, because one list per host shard means the worker owning a shard sees every request to those hosts and can hold the token bucket. On SQS it requires one queue per shard, which is workable but multiplies queue count and cost, or moving pacing into the worker — at which point no single component sees the whole request rate for a host. Whichever backend is chosen, sharding by registered domain rather than by URL is what makes politeness enforceable at all.