Facebook Ordered Queueing Service (FOQS)

High-Level FOQS Architecture

graph TD
    subgraph Clients
        Producer
        Consumer
    end

    subgraph FOQS_Stateless_Tier [FOQS Stateless Tier]
        Host1[FOQS Host]
        Host2[FOQS Host]
        Host3[...]
    end

    subgraph FOQS_Stateful_Tier [FOQS Stateful Tier]
        Shard1[MySQL Shard 1]
        Shard2[MySQL Shard 2]
        Shard3[...]
    end

    ShardManager

    %% Client and ShardManager Connections
    Producer -- Enqueue --> Host1
    Consumer -- Dequeue --> Host1
    ShardManager -- Dequeue --> Consumer
    ShardManager --> Host1
    ShardManager --> Host3

    %% Inter-Host and Host-to-Shard Connections
    Host1 -- Write --> Shard1
    Shard1 -- Read --> Host1
    Host1 -- Dequeue --> Host2

    Shard1 -- Read --> Host2
    Host2 -- Write --> Shard2
    Shard2 -- Read --> Host2

Single Host Architecture for Enqueue and Dequeue

graph TD
    subgraph "Client Requests"
        direction LR
        DequeueRequest
        EnqueueRequest
    end

    subgraph "FOQS Host"
        ApiLayer[API Layer]

        subgraph "Enqueue Path"
            Worker
            InMemoryBuffer[In-Memory Buffer]
        end

        subgraph "Dequeue Path"
            PrefetchWorker
            PrefetchBuffer
        end
    end

    subgraph "MySQL Shards"
        MySQL1[MySQL Shard 1]
        MySQL2[MySQL Shard 2]
    end

    %% Client and API Layer Connections
    DequeueRequest --> ApiLayer
    EnqueueRequest --> ApiLayer
    ApiLayer --> Worker
    Worker --> ApiLayer

    %% Enqueue Path Flow
    Worker -- "Buffers Request" --> InMemoryBuffer
    Worker -- "Reads from" --> InMemoryBuffer
    Worker -- "Inserts Item" --> MySQL1

    %% Dequeue Path Flow
    ApiLayer -- "Reads from" --> PrefetchBuffer
    PrefetchWorker -- "Fills" --> PrefetchBuffer
    InMemoryBuffer -- "k-way merge" --> PrefetchWorker
    MySQL2 -- "k-way merge" --> PrefetchWorker

    %% MySQL Shard-to-Shard Connection
    MySQL1 --> MySQL2

Client Interaction Sequence Diagram

sequenceDiagram
    participant Producer
    participant FOQS
    participant Consumer

    Producer->>FOQS: enqueue(item)
    FOQS-->>Producer: item_id

    loop Topic Discovery
        Consumer->>FOQS: getActiveTopics()
        FOQS-->>Consumer: list of topics
    end

    Consumer->>FOQS: dequeue(topic)
    FOQS-->>Consumer: item

    Consumer->>Consumer: Process item
    alt Processing Successful
        Consumer->>FOQS: ack(item_id)
    else Processing Failed
        Consumer->>FOQS: nack(item_id)
    end

Sources:

• FOQS: Scaling a distributed priority queue