A queue that survives a region
Facebook Ordered Queueing Service (FOQS) is the managed distributed priority queue behind reliable message delivery across Meta's apps and services—including safety check notifications after earthquakes. Given that role, FOQS must stay available when an entire data center or region goes dark, or during planned maintenance outages. The service started as a regional deployment, but operational lessons from Hurricane Florence in 2018 drove a migration to a globally distributed architecture that completes failure recovery in seconds with no client involvement.
Why regional fell short
The original FOQS, built in 2018 for Meta's Asynchronous computing platform (Async), ran on a three-region, semi-synchronously replicated MySQL topology. Queue nodes in each region were isolated from nodes in the others, with clients choosing the physical region they wanted to use.
This design pushed complexity to the customer: clients had to balance traffic and manage disaster recovery themselves. In normal operation, that was manageable. But the failure modes were severe:
- A primary replica loss in one region could trigger promotion of a replica in another region, forcing cross-region queries with latency spikes of hundreds of milliseconds.
- With complete network isolation of a region, MySQL primaries couldn't fail over outside the regional installation, leaving queue items "stuck" until connectivity returned.
- Customers had to explicitly shift traffic away from impacted regions, often leading to underutilized capacity and a need for spare buffer capacity elsewhere.
Hurricane Florence put all of this to the test in late 2018. FOQS faced a multiday disruption requiring manual traffic rebalancing, capacity additions, and direct coordination with customers to prevent substantial impact. It was clear this approach would not scale with the service.
Global architecture
The team redesigned FOQS around two principles: follow the MySQL primary wherever it fails over, and put an intelligent routing service between clients and the queue.
Following the primary after failover
Global installations lean on Shard Manager global primitives to colocate a queue node with the MySQL shard it manages, no matter which region that shard lands in after a failover. When a shard fails over from region X to region Y—typically within seconds—FOQS transitions management of that shard to a queue node in region Y automatically.
This avoids the two biggest regional-installation problems at once: items never get stuck because the primary is unavailable in its original region, and query latency doesn't balloon because the queue node moves with the database. The queue remains reachable behind a single global service ID, so clients need take no action during a disaster.
Routing service as the new front door
To keep end-to-end latency low in the global topology, FOQS introduced a routing service that proxies between clients and queue nodes. Physical routing decisions are fully abstracted away; clients express logical region preferences and the routing service handles where items actually land.
The enqueue distributor is the component responsible for data placement. It maintains in-memory state mapping logical regions to nearby MySQL shards, and builds the set of queue nodes eligible to accept an enqueue request based on the client's stated preference. No preference means items are routed within or near the region that sent the request.
Critically, global installations keep accepting enqueues that name a region that is currently unavailable—the request is just routed to the region now holding the associated MySQL capacity. From the client's perspective, nothing failed.
Dequeue distribution solves the discovery problem differently. Because queue items aren't stored at any fixed location, each routing service node keeps an in-memory heap cache of queue nodes that hold ready items, keyed by topic ID. The dequeue distributor consults the heap to direct requests to an appropriate host, allowing continued dequeues for a topic even when the physical region associated with its logical preference is down.
Migration pains: Async at scale
The architecture was sound, but putting it into production for FOQS's biggest customer—Async—surfaced new operational challenges.
The dequeue distributor's cache aggregation couldn't keep up at Async's scale. Replenishment latency was cut nearly in half by parallelizing the aggregation work, which also reduced routing to stale queue nodes.
With fresher caches, a second problem emerged. The default dequeue algorithm directed requests to the top-k queue nodes in each distributor's cache, which every routing node sorted similarly. Traffic spikes caused thundering herd conditions on the favored nodes and starvation for lower-ranked ones, particularly for cross-region requests where physical distance factored into ordering. Adding randomization into host selection among the already prioritized nodes spread requests more evenly and reduced queueing delay.
A zero-downtime cutover
Migrating Async's workload to a global installation was completed by mid-2021 with zero client downtime. The team credited four risk-mitigation practices:
- A shadow environment for load and stress testing the new architecture before production traffic arrived.
- A config-based rollout mechanism supporting rapid forward and backward steps with regular traffic increases.
- An aggressive posture toward investigating anomalies as they appeared, with retrospectives driving root-cause fixes.
- High-level dashboards with unambiguous metrics so all stakeholders could track migration health and status at a glance.
The result: FOQS is now a globally available distributed queue at Meta scale. Loss of an entire region is absorbed automatically in seconds, unbeknownst to clients, with essentially zero human involvement in the response.
