Delay, Not Loss: FOQS, Meta's Trillion-Item Priority Queue

The Facebook ecosystem runs on thousands of distributed systems and microservices, and a large share of their work is better done asynchronously — deferred to off-peak hours for better resource utilization, scheduled for a future date, or passed dependably between services. What all of those cases share is the need for a queue: a place to store work that must happen later, or elsewhere. FOQS — Facebook Ordered Queueing Service — is that place for hundreds of use cases: Async, Facebook's general-purpose asynchronous compute platform, leans on FOQS's ability to hold large backlogs to defer delay-tolerant work to off-peak hours; video uploads are broken into components stored in FOQS for later encoding; language translation splits computationally expensive jobs into parallel work items.

The scale sets the terms of the problem. FOQS processes close to a trillion items a day, and its backlogs have reached hundreds of billions of items — a number the post cites with pride, because a queue's backlog capacity is precisely its ability to absorb widespread downstream failure. When consumers break, the queue is the component that must not: producers keep enqueueing, items persist, and the failure surfaces as delay rather than loss.

But a priority queue makes a promise that gets harder as it scales on sharded storage. Items carry a user-specified 32-bit priority and a deliver_after timestamp, and dequeue must return the most important, oldest-ready work first — while the items live as rows scattered across MySQL shards, each shard owned by one host and aware only of its own contents. And MySQL itself pushes back against the queue's mechanics: the background operations that run FOQS — making deferred items deliverable, expiring leases, purging TTL'd items — are timestamp scans, and MySQL retains old row versions in a history list whose length degrades read performance. The deeper the backlog, the longer the history, the slower the very queries that drain it. The queue's core engineering problem is keeping its performance independent of how full it is.

An item in FOQS is one row in a MySQL table: namespace, topic, priority (lower is more urgent), an immutable payload up to 10Kb, mutable metadata, a deliver_after timestamp, a lease duration, a TTL, and a FOQS-assigned ID that encodes the shard ID plus a 64-bit primary key — so every item's location is readable from its name. Topics are logical priority queues, dynamic and free: enqueue to a topic and it exists; drain it and it ceases to. Namespaces are the multitenancy unit, each with guaranteed capacity in enqueues per minute, mapped to a tier — an ensemble of FOQS hosts and MySQL shards. Shard Manager assigns each shard to exactly one host.

The enqueue path is buffered: a request lands on a host, returns a promise, and a per-shard worker drains the buffer into MySQL rows, fulfilling the promise when the insert completes. In front of each shard sits a circuit breaker — the post cites the pattern by name — that marks a shard unhealthy on slow queries or elevated error rates over a rolling window, and stops the worker from feeding it until it recovers: FOQS does not continue to overload already-unhealthy shards with new items. If an enqueue lands on an overloaded host, enqueue forwarding routes it to a host with capacity.

Dequeue is where the priority promise is kept. The API takes (topic, count) pairs and returns items ordered by priority, ties broken by older deliver_after. Because a host's items are spread across the shards it owns, it must run a reduce across them to find the globally highest-priority work — so each shard maintains an in-memory index of the primary keys of ready-to-deliver items sorted by priority, and a Prefetch Buffer performs a k-way merge across those indexes in the background, selects the winning rows, marks them delivered to prevent double delivery, and stages them for the dequeue API to read. The buffer replenishes in proportion to observed per-topic demand: topics being drained faster get more items staged. Delivery is leased — dequeue starts a clock, and an item neither acked nor nacked within its lease is redelivered (at-least-once) or deleted (at-most-once), per the topic's policy, so a consumer crashing mid-processing costs a redelivery rather than a loss. Acks delete the row; nacks update deliver_after — with optional client-supplied delay for exponential backoff — and can update metadata, letting a failing consumer store partial results in the item itself. Lost acks are safe by construction: the lease expires and redelivery handles it.

FOQS is pull-based, a decision the post defends with a workload census: end-to-end delay needs spanning milliseconds to days, consumption rates from tens of items a minute to more than ten million, per-topic and per-item priorities, and region affinity for data locality. Push would make the queue responsible for not overrunning every kind of consumer; pull keeps the queue layer simple and moves pacing to consumers, paying a discoverability cost that FOQS answers with the getActiveTopics API and a routing layer.

Two mechanisms keep the queue fast and durable at depth. Checkpointing bounds the timestamp scans: instead of selecting every row with timestamp ≤ now — which forces MySQL to walk a history list proportional to everything pending — background queries carry a lower bound too, the last checkpoint processed, so the where clause is bounded on both sides and read performance stays flat as backlogs grow. And for disaster readiness, every MySQL shard is replicated asynchronously to two additional regions, with the binlog persisted synchronously to another building in the same region; draining a datacenter means a few milliseconds of read-only while a replica catches up, promotion, and Shard Manager reassigning the shard to a FOQS host in the new primary's region to minimize expensive cross-region traffic. Namespace rate limits are enforced globally rather than per-region — the post is direct that regional guarantees are impossible — with traffic-pattern-driven colocation of capacity as the mitigation.