Your crawler has two data structures. seen = set() and pending = []. You pop() from one end, you append() discovered links to the other, and you check membership before enqueueing. It is forty lines of Python and it works beautifully.
Then, fourteen hours in, the container gets rescheduled onto a different node. Both structures were in memory. The crawl restarts from the seed URL, and fourteen hours of polite, rate-limited fetching against the target is simply repeated.
That is the moment the frontier stops being a data structure and becomes a component.
What a Frontier Has to Do
- Dedupe. A URL discovered from forty pages gets crawled once, with a membership test that stays fast at tens of millions of entries.
- Prioritise. A category page yielding two hundred product links is worth more than the two hundred and first paginated review page.
- Respect per-host politeness. One request per second to a host means one, across the whole fleet, not one per worker.
- Survive restarts. Pending and seen both have to outlive any single process.
- Distribute. N workers pull work without pulling the same work, and without one worker monopolising one host.
Those five are what separate a queue from a frontier. Most brokers give you two of them.
Politeness Belongs in the Frontier
The common mistake is rate limiting in the fetcher, a time.sleep() or a token bucket inside the worker. It cannot work: each worker's limiter only knows its own requests, so twenty workers with a one-second delay produce twenty requests per second at the host. A correct limiter has to be shared, and the frontier is the one component every worker already talks to.
So the frontier's real job is not "give me a URL." It is "give me a URL I am allowed to fetch right now." That reframing is the whole design.
Redis: the Frontier You Can Actually Build
Redis has exactly the right primitives. A SET for the seen fingerprints. One sorted set per host as the priority queue, popped with ZPOPMIN. And one global sorted set mapping each host to the timestamp at which it may next be touched, queried with ZRANGE ... BYSCORE.
The politeness logic is a read-then-write, so it has to be atomic or two workers will both decide a host is ready. Lua scripts are the mechanism: Redis executes a script as a single unit, so no other command interleaves.
import hashlib
import time
from urllib.parse import urlsplit, urlunsplit
import redis # tested with redis-py 7.x
SEEN, HOSTS, INFLIGHT, QPREFIX = (
"frontier:seen", "frontier:hosts", "frontier:inflight", "frontier:q:",
)
# Atomically: dedupe by fingerprint, enqueue at a priority, register the host.
PUSH_LUA = """
local fp, url, host = ARGV[1], ARGV[2], ARGV[3]
local score, now = tonumber(ARGV[4]), tonumber(ARGV[5])
if redis.call('SADD', KEYS[1], fp) == 0 then return 0 end
redis.call('ZADD', KEYS[2] .. host, 'NX', score, url)
redis.call('ZADD', KEYS[3], 'NX', now, host)
return 1
"""
# Atomically: find a host whose politeness window has opened, take its best URL,
# push that host's next allowed time forward, and lease the URL to this worker.
POP_LUA = """
local now, delay, lease = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local ready = redis.call('ZRANGE', KEYS[1], '-inf', now, 'BYSCORE', 'LIMIT', 0, 1)
if #ready == 0 then return nil end
local host = ready[1]
local qkey = KEYS[2] .. host
local popped = redis.call('ZPOPMIN', qkey, 1)
if #popped == 0 then
redis.call('ZREM', KEYS[1], host)
return nil
end
if redis.call('ZCARD', qkey) > 0 then
redis.call('ZADD', KEYS[1], now + delay, host)
else
redis.call('ZREM', KEYS[1], host)
end
redis.call('ZADD', KEYS[3], now + lease, popped[1])
return popped[1]
"""
def canonical(url: str) -> str:
p = urlsplit(url)
return urlunsplit((p.scheme.lower(), p.netloc.lower(), p.path or "/", p.query, ""))
class Frontier:
def __init__(self, client, delay=1.0, lease=120.0):
self.r = client
self.delay, self.lease = delay, lease
self._push = client.register_script(PUSH_LUA)
self._pop = client.register_script(POP_LUA)
def add(self, url: str, priority: float = 0.0) -> bool:
c = canonical(url)
fp = hashlib.sha256(c.encode()).hexdigest()[:20]
host = urlsplit(c).netloc
return bool(self._push(
keys=[SEEN, QPREFIX, HOSTS],
args=[fp, c, host, priority, time.time()],
))
def lease_one(self):
"""Returns a URL that is polite to fetch now, or None."""
url = self._pop(
keys=[HOSTS, QPREFIX, INFLIGHT],
args=[time.time(), self.delay, self.lease],
)
return url.decode() if url else None
def done(self, url: str) -> None:
self.r.zrem(INFLIGHT, url)
def recover_expired(self, limit: int = 500) -> int:
"""Re-queue leases whose worker died. Run this on a timer."""
stale = self.r.zrangebyscore(INFLIGHT, "-inf", time.time(), start=0, num=limit)
for raw in stale:
url = raw.decode()
host = urlsplit(url).netloc
pipe = self.r.pipeline()
pipe.zadd(f"{QPREFIX}{host}", {url: 0.0}, nx=True)
pipe.zadd(HOSTS, {host: time.time()}, nx=True)
pipe.zrem(INFLIGHT, url)
pipe.execute()
return len(stale)
if __name__ == "__main__":
f = Frontier(redis.Redis(), delay=1.0)
f.add("https://example.com/", priority=0.0)
f.add("https://example.com/page/2", priority=10.0)
print(f.lease_one()) # example.com/ — highest priority
print(f.lease_one()) # None — example.com is not polite to hit yetTwo honest caveats. QPREFIX is a prefix, not a key, so the script derives a key name at runtime, fine on a single instance, not safe on Redis Cluster, where you would hash-tag keys by host and shard the frontier per host bucket instead. And SPOP is the right primitive when you want an arbitrary URL from an unordered pool rather than the best one; BRPOPLPUSH is the classic reliable-queue pattern but has been deprecated since Redis 6.2.0 in favour of BLMOVE, so reach for that if you want blocking pops instead of the poll above.
Redis: What You Lose on Restart
This is the part that decides whether Redis is acceptable. Redis persistence has two modes and neither is free:
- RDB takes point-in-time snapshots. The docs are blunt: "you should be prepared to lose the latest minutes of data."
- AOF logs every write. With the default
appendfsync everysecyou "may lose 1 second of data if there is a disaster."appendfsync alwaysis safe and, per the docs, "very very slow."
For a frontier, losing a second of writes means re-crawling a handful of URLs, harmless, because dedupe is idempotent. The Redis docs recommend running both RDB and AOF for durability "comparable to what PostgreSQL can provide," and for a frontier that is the right default.
Budget memory honestly: 30 million 20-character fingerprints in a plain SET is roughly 2–3 GB once per-entry overhead is counted. That is an estimate — measure yours with MEMORY USAGE. If it does not fit, a Bloom filter (BF.ADD / BF.EXISTS) cuts it by an order of magnitude in exchange for a small false-positive rate, which means occasionally skipping a URL you never actually crawled.
SQS: Visibility Timeouts Are the Retry Mechanism
SQS gives you durability and zero operations, and it gives you a very specific delivery model.
Standard queues are at-least-once: a message can arrive more than once, so dedupe has to be authoritative rather than decorative. Retry is not something you configure, it is the visibility timeout. A received message is hidden for that long; delete it and it is gone, crash before deleting and it reappears. Default 30 seconds, minimum 0, maximum 12 hours. Set it longer than your slowest fetch or a healthy worker's page is handed to a second worker.
Failures route via a redrive policy with maxReceiveCount , the number of receives before SQS moves the message to a dead-letter queue. That is your poison-URL handling, and it is better than the try/except: pass you would otherwise write.
For ordering, FIFO queues require a MessageGroupId, and messages within a group are delivered in order and, crucially, a group's next message is withheld while one of its messages is in flight. Keying the group by hostname therefore gives you exactly one in-flight request per host for free. The cost is throughput: outside high-throughput mode each FIFO partition is limited to 300 transactions per second per API action, or 3,000 messages per second with ten-message batching. Standard queues now accept MessageGroupIdtoo, for fair queues, without the strict ordering guarantee.
The old 256 KB message limit is gone, SQS raised the maximum payload to 1 MiB in August 2025. Billing still counts each 64 KB chunk as one request, so a 1 MiB message bills as 16. Beyond 1 MiB, the Extended Client Libraries put the payload in S3 and send a reference, up to 2 GB. For a frontier that rarely matters; push fetched HTML through a queue and it matters immediately.
Cost, worked: 30 million URLs a month at one send, one receive and one delete each is 90 million requests. Minus the 1 million free per month, at $0.40 per million for standard queues: 89 × $0.40 = $35.60/month, or 89 × $0.50 = $44.50 on FIFO rates. An estimate, but the shape is the point — SQS at frontier volumes is cheap, and the thing it cannot do at any price is priority.
Kafka: A Log Wearing a Queue's Clothes
Kafka's parallelism unit is the partition. Within a consumer group each partition is consumed by at most one consumer, so your effective worker count is capped by partition count. Producing with the hostname as the message key sends every URL for a host to the same partition, which gives you per-host ordering and per-host serialisation as a side effect of the partitioner, genuinely elegant for politeness.
Then the problems start.
Kafka is a log, not a queue. Consumers track an offset, and committing one says "I have processed everything up to here." A classic consumer group has no per-message acknowledgement, so one poisoned URL means blocking the partition or committing past it and losing it. There is no arbitrary priority: order is append order, and a high-priority URL discovered now sits behind everything already written. And rebalancing pauses consumption across the group on every scale event or worker crash.
Worth being current: KIP-932 share groups add per-record acknowledgement and delivery counts, previewed in Kafka 4.1 and generally available alongside Kafka 4.2. That closes the ack gap. It does not add priority, and it does not make Kafka a sensible first frontier, but if Kafka is already your event backbone, it is no longer disqualifying.
The Comparison
Choosing
- Under ~50 million URLs, priority matters, you already run Redis, Redis. The code above is the whole thing, and nothing else gives you priority for free.
- You want to stop operating a queue, SQS. Accept at-least-once, make dedupe authoritative, use FIFO message groups keyed by host, and give up priority.
- The frontier feeds other consumers too, Kafka, keyed by host. Consider share groups if you are on 4.2 or later.
- Billions of URLs, none of the three alone. The seen set moves to a disk-backed store or a Bloom filter and the queue becomes per-host shards.
Mistakes That Waste Time
- Rate limiting in the fetcher. Twenty workers × one request per second = twenty per second at the host. Shared state or nothing.
- Deduping on the raw URL string.
?utm_source=and a trailing slash will double or triple your crawl. Canonicalise before you fingerprint. - Setting the visibility timeout to the average fetch time. Set it against the slow tail, and extend it explicitly for genuinely long jobs.
- No in-flight recovery. Leases with no expiry sweep mean every crashed worker silently drops its URL. The
recover_expiredtimer is not optional.
Wrapping Up
Pick the backend on the two things that actually differ: whether you need priority, and who operates it. Redis is the only one of the three with native priority, and the only one you have to keep alive yourself. SQS trades priority away for someone else's pager.
Whichever you choose, put the per-host rate limit in the frontier and make the pop return only URLs it is polite to fetch now. That single decision is the difference between a crawler that is a good citizen at two hundred workers and one that is only a good citizen at one.
