Data Structures & AlgorithmsCommon Queue Patterns & Problem Types

Common Queue Patterns & Problem Types

LevelIntermediate

Duration90 mins

TopicCommon Queue Patterns & Problem Types

4 / 4

First-Come-First-Serve Processing

The Universal Principle of Fairness

Stand in any line—at a supermarket checkout, a coffee shop, a bank, or a theme park ride—and you're participating in one of humanity's most fundamental fairness mechanisms: First-Come-First-Serve (FCFS). The person who arrived first gets served first. No exceptions. No favoritism.

This simple principle, encoded naturally in the queue data structure, extends far beyond physical lines. It governs how web servers handle requests, how databases process transactions, how networks route packets, and how message systems deliver notifications. Understanding FCFS processing patterns gives you insight into how fairness and order are maintained across countless systems.

In this page, we explore FCFS as a universal pattern—its guarantees, its limitations, its mathematical properties, and its countless applications in software engineering.

What You Will Master

By the end of this page, you will deeply understand FIFO ordering as a design principle, recognize when FCFS is the right choice (and when it isn't), grasp basic queue theory concepts, and see how FCFS patterns manifest in real-world systems from web APIs to streaming platforms.

FCFS as a Fairness Guarantee

Fairness in computing systems means that entities (requests, tasks, users) are treated equitably according to some defined criterion. FCFS implements one specific notion of fairness: arrival-order fairness.

What FCFS guarantees:

Order preservation: If request A arrives before request B, A will be processed before B
No starvation: Every request eventually gets processed (assuming finite processing time)
Predictable waiting: Waiting time is determined solely by arrivals before you
Simplicity: No complex priority calculations or policy decisions

fcfs-guarantee.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// FCFS Processing with Fairness Guarantees
 
interface Request {
    id: string;
    arrivalTime: number;
    processTime: number;
}
 
interface ProcessedRequest extends Request {
    startTime: number;
    endTime: number;
    waitingTime: number;
}
 
class FCFSProcessor {
    private queue: Request[] = [];
    private currentTime = 0;
    private processed: ProcessedRequest[] = [];
    
    // FCFS Guarantee: Enqueue maintains arrival order
    enqueue(request: Request): void {
        this.queue.push(request);  // Add to back
    }
    
    // FCFS Guarantee: Process front of queue
    processNext(): ProcessedRequest | null {
        if (this.queue.length === 0) return null;
        
        const request = this.queue.shift()!;  // Remove from front
        
        // If request arrived in the future, jump time forward
        if (request.arrivalTime > this.currentTime) {
            this.currentTime = request.arrivalTime;
        }
        
        const startTime = this.currentTime;
        const endTime = startTime + request.processTime;
        const waitingTime = startTime - request.arrivalTime;
        
        this.currentTime = endTime;
        
        const processed: ProcessedRequest = {
            ...request,
            startTime,
            endTime,
            waitingTime
        };
        
        this.processed.push(processed);
        return processed;
    }
    
    // Process all queued requests
    processAll(): ProcessedRequest[] {
        while (this.queue.length > 0) {
            this.processNext();
        }
        return this.processed;
    }
    
    // FAIRNESS CHECK: Verify FCFS property holds
    verifyFCFS(): boolean {
        for (let i = 1; i < this.processed.length; i++) {
            const prev = this.processed[i - 1];
            const curr = this.processed[i];
            
            // If curr arrived before prev, but was processed after
            // that's ONLY okay if curr arrived after prev started
            if (curr.arrivalTime < prev.arrivalTime && 
                curr.startTime > prev.startTime) {
                // FCFS violation! (unless curr arrived during prev's processing)
                if (curr.arrivalTime < prev.startTime) {
                    return false;
                }
            }
        }
        return true;
    }
}
 
/*
Example:
Requests arrive at: [0, 2, 4, 6]
Process times:      [3, 3, 3, 3]
 
FCFS Processing:
Request 1: arrives 0, starts 0, ends 3, waits 0
Request 2: arrives 2, starts 3, ends 6, waits 1
Request 3: arrives 4, starts 6, ends 9, waits 2
Request 4: arrives 6, starts 9, ends 12, waits 3
 
Order preserved: 1 → 2 → 3 → 4 ✓
No starvation: All requests processed ✓
Deterministic: Same inputs always produce same order ✓
*/

Fairness vs Optimality

FCFS is fair in the arrival-order sense but not necessarily optimal for metrics like average waiting time. As we saw with the convoy effect, FCFS can lead to poor performance when task sizes vary significantly. Fairness and efficiency are often in tension.

FCFS in Service Systems

Service systems—from customer support to web servers—are natural applications of FCFS. Understanding the patterns helps in system design.

Common Service System Patterns:

service-systems.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// Service System Patterns with FCFS
 
// Pattern 1: Single-Server Queue (M/M/1 model)
// Classic FCFS: one server, one queue
class SingleServerQueue<T> {
    private queue: { item: T; arrivalTime: number }[] = [];
    private serverBusy = false;
    
    async enqueue(
        item: T,
        process: (item: T) => Promise<void>
    ): Promise<void> {
        const arrivalTime = Date.now();
        this.queue.push({ item, arrivalTime });
        
        if (!this.serverBusy) {
            await this.processQueue(process);
        }
    }
    
    private async processQueue(
        process: (item: T) => Promise<void>
    ): Promise<void> {
        this.serverBusy = true;
        
        while (this.queue.length > 0) {
            const { item, arrivalTime } = this.queue.shift()!;
            const waitTime = Date.now() - arrivalTime;
            console.log(`Processing after ${waitTime}ms wait`);
            await process(item);
        }
        
        this.serverBusy = false;
    }
}
 
// Pattern 2: Multi-Server Queue (M/M/c model)
// Multiple servers pulling from single FCFS queue
class MultiServerQueue<T> {
    private queue: T[] = [];
    private activeServers = 0;
    private maxServers: number;
    
    constructor(servers: number) {
        this.maxServers = servers;
    }
    
    async enqueue(
        item: T,
        process: (item: T) => Promise<void>
    ): Promise<void> {
        this.queue.push(item);
        this.tryProcess(process);
    }
    
    private async tryProcess(
        process: (item: T) => Promise<void>
    ): Promise<void> {
        if (this.activeServers >= this.maxServers) return;
        if (this.queue.length === 0) return;
        
        this.activeServers++;
        const item = this.queue.shift()!;  // FCFS: always front
        
        try {
            await process(item);
        } finally {
            this.activeServers--;
            this.tryProcess(process);  // Check for more work
        }
    }
    
    getQueueLength(): number {
        return this.queue.length;
    }
    
    getActiveServers(): number {
        return this.activeServers;
    }
}
 
// Pattern 3: Buffer-Limited Queue
// FCFS with capacity limit (drops when full)
class BoundedFCFSQueue<T> {
    private queue: T[] = [];
    private capacity: number;
    private dropped = 0;
    
    constructor(capacity: number) {
        this.capacity = capacity;
    }
    
    enqueue(item: T): boolean {
        if (this.queue.length >= this.capacity) {
            this.dropped++;
            return false;  // Queue full, item dropped
        }
        this.queue.push(item);
        return true;
    }
    
    dequeue(): T | undefined {
        return this.queue.shift();
    }
    
    getDropRate(): number {
        const total = this.queue.length + this.dropped;
        return total > 0 ? this.dropped / total : 0;
    }
}
 
/*
Real-world examples:
 
Single-Server: Small business with one cashier
Multi-Server: Bank with multiple tellers
Bounded Queue: Network buffer with packet drops
*/

Service System Queue Configurations
Configuration	Real-World Example	Trade-offs
Single queue, single server	Doctor's waiting room	Simple, fair, but slow
Single queue, multiple servers	Bank tellers	Fair and parallel, best of both
Multiple queues, multiple servers	Supermarket checkouts	Fast for some, unfair (luck-based)
Priority queue, single server	Hospital ER	Efficient for urgent cases, possible starvation

The Single Queue Advantage

Studies show that a single shared queue with multiple servers (like at banks) is both fairer AND more efficient than multiple independent queues (like at supermarkets). No one gets stuck behind a slow customer while another line zooms past.

Queue Theory Fundamentals

Queue theory (also called queueing theory) is the mathematical study of waiting lines. While a full treatment requires probability and statistics, understanding the basic concepts helps in system design.

Key Concepts:

Arrival Rate (λ): Average number of arrivals per time unit
Service Rate (μ): Average number of completions per time unit
Utilization (ρ): λ/μ — fraction of time the server is busy
Stability Condition: ρ < 1 (arrivals must be slower than service on average)

queue-theory-metrics.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// Queue Theory Metrics Calculation
 
interface QueueMetrics {
    utilization: number;         // ρ = λ/μ
    avgQueueLength: number;      // L_q (average items waiting)
    avgSystemLength: number;     // L (average items in system)
    avgWaitingTime: number;      // W_q (average time waiting)
    avgSystemTime: number;       // W (average time in system)
}
 
/**
 * Calculate M/M/1 queue metrics
 * M/M/1 = Markovian arrivals, Markovian service, 1 server
 * 
 * @param arrivalRate λ - average arrivals per time unit
 * @param serviceRate μ - average services per time unit
 */
function calculateMM1Metrics(
    arrivalRate: number,  // λ
    serviceRate: number   // μ
): QueueMetrics | null {
    const utilization = arrivalRate / serviceRate;  // ρ
    
    // Stability check: must have μ > λ
    if (utilization >= 1) {
        console.error("Queue is unstable! Arrival rate >= service rate");
        return null;
    }
    
    // M/M/1 formulas (assuming exponential distributions)
    // Average number in queue: L_q = ρ² / (1 - ρ)
    const avgQueueLength = 
        (utilization * utilization) / (1 - utilization);
    
    // Average number in system: L = ρ / (1 - ρ)
    const avgSystemLength = utilization / (1 - utilization);
    
    // Little's Law: L = λ * W
    // Therefore: W = L / λ
    const avgSystemTime = avgSystemLength / arrivalRate;
    
    // Waiting time: W_q = L_q / λ (also by Little's Law)
    const avgWaitingTime = avgQueueLength / arrivalRate;
    
    return {
        utilization,
        avgQueueLength,
        avgSystemLength,
        avgWaitingTime,
        avgSystemTime
    };
}
 
// Example: Web server analysis
const webServerMetrics = calculateMM1Metrics(
    80,   // 80 requests per second
    100   // Can handle 100 requests per second
);
 
console.log("Web Server Queue Analysis:");
console.log(`Utilization: ${(webServerMetrics!.utilization * 100).toFixed(1)}%`);
console.log(`Avg queue length: ${webServerMetrics!.avgQueueLength.toFixed(2)} requests`);
console.log(`Avg waiting time: ${(webServerMetrics!.avgWaitingTime * 1000).toFixed(1)}ms`);
console.log(`Avg total time: ${(webServerMetrics!.avgSystemTime * 1000).toFixed(1)}ms`);
 
/*
Output:
Web Server Queue Analysis:
Utilization: 80.0%
Avg queue length: 3.20 requests
Avg waiting time: 40.0ms
Avg total time: 50.0ms (waiting + service)
 
Key insight: At 80% utilization, you still have significant queuing!
At 90% utilization, queue length would be 8.1 (more than double).
*/
 
// Demonstrate utilization impact
console.log("
Impact of Utilization:");
for (const util of [0.5, 0.7, 0.8, 0.9, 0.95, 0.99]) {
    const λ = util * 100;  // Adjust arrival rate
    const metrics = calculateMM1Metrics(λ, 100);
    console.log(
        `ρ=${(util * 100).toFixed(0)}%: ` +
                                        `Queue=${metrics!.avgQueueLength.toFixed(1)}, ` +
                                    `Wait=${(metrics!.avgWaitingTime * 1000).toFixed(0)}ms`
    );
}
 
/*
Impact of Utilization:
ρ=50%: Queue=0.5, Wait=5ms
ρ=70%: Queue=1.6, Wait=16ms
ρ=80%: Queue=3.2, Wait=32ms
ρ=90%: Queue=8.1, Wait=81ms
ρ=95%: Queue=18.1, Wait=181ms
ρ=99%: Queue=98.0, Wait=980ms
 
As utilization approaches 100%, queues explode!
This is why we don't run servers at 100% capacity.
*/

Little's Law

L = λ × W (Average number in system = arrival rate × average time in system). This fundamental law applies to ANY stable queueing system, regardless of arrival distribution or service discipline. It's invaluable for back-of-envelope capacity calculations.

Practical Implications:

Never run at 100% capacity — As utilization approaches 100%, queue length approaches infinity. Real systems need headroom.
The 80% rule — Many systems are designed to run at ~70-80% utilization under normal load, leaving room for traffic spikes.
Tail latencies matter — Average waiting time might be 50ms, but the 99th percentile could be 500ms. FCFS doesn't protect against outliers.
Adding servers helps nonlinearly — Going from 1 to 2 servers can reduce queue length dramatically (more than 50%).

FCFS in Distributed Systems

Distributed systems present unique challenges for FCFS ordering. When messages traverse networks with variable latency, when clocks are unsynchronized, and when multiple servers process requests, maintaining strict FCFS becomes complex—and sometimes impossible.

distributed-fcfs.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// FCFS Challenges in Distributed Systems
 
// Challenge 1: Clock Skew
// Different servers have different clock times
interface TimestampedRequest {
    id: string;
    clientTimestamp: number;  // Client's view of time
    serverReceiveTime: number;  // Server's view of arrival
}
 
// Whose timestamp do we trust for FCFS?
function orderByClientTime(
    requests: TimestampedRequest[]
): TimestampedRequest[] {
    // Client timestamps can be manipulated or skewed
    return [...requests].sort((a, b) => 
        a.clientTimestamp - b.clientTimestamp
    );
}
 
function orderByServerTime(
    requests: TimestampedRequest[]
): TimestampedRequest[] {
    // Server time is trustworthy but may not reflect true order
    // (Network delays can reorder packets)
    return [...requests].sort((a, b) => 
        a.serverReceiveTime - b.serverReceiveTime
    );
}
 
// Solution: Lamport Timestamps or Vector Clocks
// (covered in distributed systems courses)
 
// Challenge 2: Multi-Leader / Partitioned Queues
// How to maintain global FCFS across partitions?
 
interface PartitionedQueue {
    partitions: Map<string, Request[]>;
}
 
function globalFCFSFromPartitions(
    pq: PartitionedQueue
): Request[] {
    // Problem: each partition has its own order
    // Merging them requires a global timestamp
    
    const allRequests: Array<{
        partition: string;
        request: Request;
    }> = [];
    
    for (const [partition, requests] of pq.partitions) {
        for (const request of requests) {
            allRequests.push({ partition, request });
        }
    }
    
    // Sort by global timestamp (requires synchronized clocks!)
    return allRequests
        .sort((a, b) => a.request.arrivalTime - b.request.arrivalTime)
        .map(item => item.request);
}
 
interface Request {
    id: string;
    arrivalTime: number;
}
 
// Challenge 3: Exactly-Once Delivery
// Retries can violate FCFS appearance
 
class IdempotentQueue {
    private queue: Request[] = [];
    private processedIds = new Set<string>();
    
    enqueue(request: Request): boolean {
        // Deduplicate: same request might arrive multiple times
        if (this.processedIds.has(request.id)) {
            return false;  // Already handled
        }
        this.queue.push(request);
        return true;
    }
    
    dequeue(): Request | undefined {
        const request = this.queue.shift();
        if (request) {
            this.processedIds.add(request.id);
        }
        return request;
    }
}
 
/*
Key insights for distributed FCFS:
 
1. "Arrival time" is ambiguous across machines
2. Network delays can reorder messages
3. Partitioning trades strict order for scalability
4. "Close enough" ordering is often acceptable
5. Message queues like Kafka provide per-partition ordering
*/

FCFS Ordering Guarantees in Distributed Systems
System Type	Ordering Guarantee	Trade-off
Single-partition Kafka	Strict FIFO within partition	Limited scalability per partition
AWS SQS Standard	Best-effort FIFO	Occasional reordering for performance
AWS SQS FIFO	Strict FIFO	Lower throughput, higher cost
Redis Streams	Strict per-stream	Single-node bottleneck for strict ordering
Google Pub/Sub	Best-effort	Optimized for throughput, not order

When Strict Order Matters

Not all applications need strict FCFS. Email can arrive slightly out of order. But financial transactions, audit logs, and event sourcing often require strict ordering. Choose your messaging system based on actual requirements, not theoretical perfection.

Request Queuing in Web Systems

Every web server, API gateway, and load balancer implements some form of request queuing. Understanding these patterns helps in capacity planning and performance optimization.

web-request-queue.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// Web Request Queuing Patterns
 
interface HttpRequest {
    id: string;
    path: string;
    method: string;
    timestamp: number;
}
 
interface HttpResponse {
    status: number;
    body: string;
    processingTime: number;
    queueTime: number;
}
 
// Pattern: Request Queue with Backpressure
class BackpressureQueue {
    private queue: HttpRequest[] = [];
    private maxQueueSize: number;
    private processing = false;
    private concurrency: number;
    private activeRequests = 0;
    
    constructor(
        maxQueueSize: number,
        concurrency: number
    ) {
        this.maxQueueSize = maxQueueSize;
        this.concurrency = concurrency;
    }
    
    async handleRequest(
        request: HttpRequest,
        handler: (req: HttpRequest) => Promise<HttpResponse>
    ): Promise<HttpResponse> {
        const arrivalTime = Date.now();
        
        // Backpressure: reject if queue too long
        if (this.queue.length >= this.maxQueueSize) {
            return {
                status: 503,  // Service Unavailable
                body: "Server overloaded, try again later",
                processingTime: 0,
                queueTime: 0
            };
        }
        
        // Enqueue and wait for processing
        return new Promise((resolve) => {
            const queuedRequest = {
                request,
                resolve,
                arrivalTime
            };
            this.queue.push(queuedRequest as any);
            this.tryProcess(handler);
        });
    }
    
    private async tryProcess(
        handler: (req: HttpRequest) => Promise<HttpResponse>
    ): Promise<void> {
        while (
            this.activeRequests < this.concurrency &&
            this.queue.length > 0
        ) {
            const item = this.queue.shift() as any;
            this.activeRequests++;
            
            const startTime = Date.now();
            const queueTime = startTime - item.arrivalTime;
            
            try {
                const response = await handler(item.request);
                item.resolve({
                    ...response,
                    queueTime
                });
            } catch (error) {
                item.resolve({
                    status: 500,
                    body: "Internal server error",
                    processingTime: Date.now() - startTime,
                    queueTime
                });
            } finally {
                this.activeRequests--;
                this.tryProcess(handler);
            }
        }
    }
    
    getMetrics(): {
        queueLength: number;
        activeRequests: number;
        capacity: number;
    } {
        return {
            queueLength: this.queue.length,
            activeRequests: this.activeRequests,
            capacity: this.maxQueueSize - this.queue.length
        };
    }
}
 
// Usage: Express.js middleware example
/*
const requestQueue = new BackpressureQueue(1000, 10);
 
app.use(async (req, res, next) => {
    const response = await requestQueue.handleRequest(
        { id: uuid(), path: req.path, method: req.method, timestamp: Date.now() },
        async (request) => {
            // Your actual handler logic
            return { status: 200, body: "OK", processingTime: 50, queueTime: 0 };
        }
    );
    
    res.status(response.status).send(response.body);
});
*/
 
/*
Key patterns demonstrated:
1. FCFS ordering of requests
2. Backpressure (503 when overloaded)
3. Concurrency limiting
4. Queue time tracking for observability
5. Graceful degradation under load
*/

The Request Queue Hierarchy:

In a typical web stack, requests pass through multiple queues:

OS Socket Queue — Kernel buffers incoming TCP connections
Web Server Accept Queue — Server's pending connection queue
Worker Thread Pool Queue — Jobs waiting for worker threads
Application Queue — Your own queuing logic
Database Connection Pool Queue — Queries waiting for DB connections

Each level can become a bottleneck. Understanding where queuing happens helps diagnose latency issues.

Measure Queue Time

Separate your latency metrics into queue time (waiting) and processing time (actual work). A request taking 500ms might be 400ms queuing and 100ms processing—very different problems with very different solutions.

Stream Processing and Event Queues

Modern systems increasingly deal with continuous streams of events: user clicks, sensor readings, financial transactions, log entries. Event queues and stream processing apply FCFS principles at massive scale.

event-stream-processing.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// Event Stream Processing with FCFS Ordering
 
interface Event {
    id: string;
    timestamp: number;
    type: string;
    data: Record<string, any>;
    partition?: string;  // For partitioned processing
}
 
// Pattern: Ordered Event Stream
class OrderedEventStream {
    private events: Event[] = [];
    private consumers: ((event: Event) => void)[] = [];
    private offset = 0;  // Current read position
    
    // Append-only: maintains temporal order
    publish(event: Event): number {
        const position = this.events.length;
        this.events.push(event);
        
        // Notify consumers
        for (const consumer of this.consumers) {
            consumer(event);
        }
        
        return position;  // Return offset for acknowledgment
    }
    
    // Read from specific offset (replayability!)
    readFrom(offset: number, count: number): Event[] {
        return this.events.slice(offset, offset + count);
    }
    
    // Subscribe to new events
    subscribe(consumer: (event: Event) => void): () => void {
        this.consumers.push(consumer);
        return () => {
            const idx = this.consumers.indexOf(consumer);
            if (idx >= 0) this.consumers.splice(idx, 1);
        };
    }
    
    // Consumer group pattern: each event processed once per group
    createConsumerGroup(
        groupId: string,
        handler: (event: Event) => Promise<void>
    ): EventConsumer {
        return new EventConsumer(this, groupId, handler);
    }
}
 
class EventConsumer {
    private stream: OrderedEventStream;
    private groupId: string;
    private handler: (event: Event) => Promise<void>;
    private committedOffset = 0;
    private running = false;
    
    constructor(
        stream: OrderedEventStream,
        groupId: string,
        handler: (event: Event) => Promise<void>
    ) {
        this.stream = stream;
        this.groupId = groupId;
        this.handler = handler;
    }
    
    async start(): Promise<void> {
        this.running = true;
        
        while (this.running) {
            const events = this.stream.readFrom(this.committedOffset, 10);
            
            for (const event of events) {
                await this.handler(event);
                this.committedOffset++;  // Move forward after success
            }
            
            if (events.length === 0) {
                await sleep(100);  // No events, wait a bit
            }
        }
    }
    
    stop(): void {
        this.running = false;
    }
    
    getOffset(): number {
        return this.committedOffset;
    }
}
 
async function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}
 
// Usage example: Event sourcing
/*
const eventStream = new OrderedEventStream();
 
// Publish events
eventStream.publish({
    id: "evt-1",
    timestamp: Date.now(),
    type: "user_registered",
    data: { userId: "u123", email: "user@example.com" }
});
 
eventStream.publish({
    id: "evt-2", 
    timestamp: Date.now(),
    type: "order_placed",
    data: { orderId: "o456", userId: "u123", total: 99.99 }
});
 
// Consumer processes in order
const consumer = eventStream.createConsumerGroup(
    "order-processor",
    async (event) => {
        console.log(`Processing: ${event.type}`);
        // FCFS: events processed in publish order
    }
);
 
consumer.start();
*/
 
/*
This pattern mirrors Apache Kafka, AWS Kinesis, etc.
Key properties:
1. Append-only log = natural FCFS ordering
2. Offsets enable replay from any point
3. Consumer groups enable parallel processing
4. Partitioning enables horizontal scaling
*/

Event Streaming Platforms

•Apache Kafka: Distributed commit log with strict per-partition ordering. Industry standard for high-throughput event streaming.
•AWS Kinesis: Managed streaming with shards (partitions). Strict per-shard ordering.
•Apache Pulsar: Multi-layer architecture separating compute and storage. Flexible ordering guarantees.
•Redis Streams: Lightweight event streaming built into Redis. Great for simpler use cases.
•Google Pub/Sub: Global message delivery. Ordering is optional and per-key.

When FCFS is Wrong

While FCFS provides fairness, it's not always the right choice. Understanding when to deviate from FCFS is crucial for system design.

Use FCFS When

•All requests have similar importance
•All requests have similar processing times
•Fairness is more important than efficiency
•Ordering has semantic meaning (logs, transactions)
•Simplicity is paramount
•Debugging/auditing requires clear order

Avoid FCFS When

•Requests have vastly different priorities
•Processing times vary significantly (convoy effect)
•Real-time deadlines must be met
•Some requests can be batched together
•Responsiveness matters more than fairness
•Short jobs should not wait behind long jobs

Alternative Strategies:

Priority Queuing: Urgent requests jump ahead. Risk: starvation of low-priority items.
Shortest Job First (SJF): If you know processing time, serve shortest first. Optimal for average waiting time but unfair.
Weighted Fair Queuing: Each flow gets fair share, but VIP flows get larger shares.
Deadline-Based: Tasks with nearest deadlines processed first. Essential for real-time systems.
Round-Robin with Priorities: Multiple priority levels, round-robin within each level.

The Hospital Exception

Hospital emergency rooms don't use FCFS—a heart attack patient doesn't wait behind someone with a sprained ankle. Triage prioritizes by severity. Similarly, your systems may need prioritization when not all requests are equally important.

Summary: FCFS Processing Mastered

First-Come-First-Serve processing is one of the most fundamental patterns in computing. Let's consolidate the key insights:

Key Takeaways

•FCFS guarantees arrival-order fairness — First to arrive is first to be served, ensuring no starvation and predictable behavior.
•Queue theory provides mathematical foundations — Utilization, Little's Law, and arrival/service rate analysis guide capacity planning.
•Never run at 100% utilization — As utilization approaches capacity, queue lengths and wait times grow exponentially.
•Distributed FCFS is challenging — Clock skew, network delays, and partitioning complicate strict ordering across machines.
•Request queuing happens at multiple levels — From OS sockets to application logic, understand where your queues are.
•Event streaming applies FCFS at scale — Append-only logs with consumer offsets enable massive ordered event processing.
•FCFS isn't always right — When priorities, deadlines, or efficiency matter more than strict fairness, consider alternatives.

Module Complete:

With this page, you've completed the Common Queue Patterns & Problem Types module. You now understand:

Level-order processing (tree/hierarchy traversal)
BFS intuition (wave expansion, shortest paths)
Task scheduling simulation (FCFS, round-robin, multi-level)
FCFS processing principles (fairness, queue theory, real-world systems)

These four patterns form the foundation of queue-based problem solving. You're equipped to recognize when a problem calls for a queue and to apply the appropriate pattern effectively.

Module Complete

Congratulations! You've mastered the common queue patterns: level-order traversal, BFS exploration, task scheduling, and FCFS processing. These patterns appear throughout computing—from operating systems to distributed systems, from web servers to streaming platforms. You now have the intuition to recognize and apply queue-based solutions effectively.

4 / 4

Loading learning content...

Data Structures & AlgorithmsCommon Queue Patterns & Problem Types

Common Queue Patterns & Problem Types

LevelIntermediate

Duration90 mins

TopicCommon Queue Patterns & Problem Types

4 / 4

First-Come-First-Serve Processing

The Universal Principle of Fairness

In this page, we explore FCFS as a universal pattern—its guarantees, its limitations, its mathematical properties, and its countless applications in software engineering.

What You Will Master

FCFS as a Fairness Guarantee

What FCFS guarantees:

Order preservation: If request A arrives before request B, A will be processed before B
No starvation: Every request eventually gets processed (assuming finite processing time)
Predictable waiting: Waiting time is determined solely by arrivals before you
Simplicity: No complex priority calculations or policy decisions

fcfs-guarantee.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// FCFS Processing with Fairness Guarantees
 
interface Request {
    id: string;
    arrivalTime: number;
    processTime: number;
}
 
interface ProcessedRequest extends Request {
    startTime: number;
    endTime: number;
    waitingTime: number;
}
 
class FCFSProcessor {
    private queue: Request[] = [];
    private currentTime = 0;
    private processed: ProcessedRequest[] = [];
    
    // FCFS Guarantee: Enqueue maintains arrival order
    enqueue(request: Request): void {
        this.queue.push(request);  // Add to back
    }
    
    // FCFS Guarantee: Process front of queue
    processNext(): ProcessedRequest | null {
        if (this.queue.length === 0) return null;
        
        const request = this.queue.shift()!;  // Remove from front
        
        // If request arrived in the future, jump time forward
        if (request.arrivalTime > this.currentTime) {
            this.currentTime = request.arrivalTime;
        }
        
        const startTime = this.currentTime;
        const endTime = startTime + request.processTime;
        const waitingTime = startTime - request.arrivalTime;
        
        this.currentTime = endTime;
        
        const processed: ProcessedRequest = {
            ...request,
            startTime,
            endTime,
            waitingTime
        };
        
        this.processed.push(processed);
        return processed;
    }
    
    // Process all queued requests
    processAll(): ProcessedRequest[] {
        while (this.queue.length > 0) {
            this.processNext();
        }
        return this.processed;
    }
    
    // FAIRNESS CHECK: Verify FCFS property holds
    verifyFCFS(): boolean {
        for (let i = 1; i < this.processed.length; i++) {
            const prev = this.processed[i - 1];
            const curr = this.processed[i];
            
            // If curr arrived before prev, but was processed after
            // that's ONLY okay if curr arrived after prev started
            if (curr.arrivalTime < prev.arrivalTime && 
                curr.startTime > prev.startTime) {
                // FCFS violation! (unless curr arrived during prev's processing)
                if (curr.arrivalTime < prev.startTime) {
                    return false;
                }
            }
        }
        return true;
    }
}
 
/*
Example:
Requests arrive at: [0, 2, 4, 6]
Process times:      [3, 3, 3, 3]
 
FCFS Processing:
Request 1: arrives 0, starts 0, ends 3, waits 0
Request 2: arrives 2, starts 3, ends 6, waits 1
Request 3: arrives 4, starts 6, ends 9, waits 2
Request 4: arrives 6, starts 9, ends 12, waits 3
 
Order preserved: 1 → 2 → 3 → 4 ✓
No starvation: All requests processed ✓
Deterministic: Same inputs always produce same order ✓
*/

Fairness vs Optimality

FCFS in Service Systems

Service systems—from customer support to web servers—are natural applications of FCFS. Understanding the patterns helps in system design.

Common Service System Patterns:

service-systems.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// Service System Patterns with FCFS
 
// Pattern 1: Single-Server Queue (M/M/1 model)
// Classic FCFS: one server, one queue
class SingleServerQueue<T> {
    private queue: { item: T; arrivalTime: number }[] = [];
    private serverBusy = false;
    
    async enqueue(
        item: T,
        process: (item: T) => Promise<void>
    ): Promise<void> {
        const arrivalTime = Date.now();
        this.queue.push({ item, arrivalTime });
        
        if (!this.serverBusy) {
            await this.processQueue(process);
        }
    }
    
    private async processQueue(
        process: (item: T) => Promise<void>
    ): Promise<void> {
        this.serverBusy = true;
        
        while (this.queue.length > 0) {
            const { item, arrivalTime } = this.queue.shift()!;
            const waitTime = Date.now() - arrivalTime;
            console.log(`Processing after ${waitTime}ms wait`);
            await process(item);
        }
        
        this.serverBusy = false;
    }
}
 
// Pattern 2: Multi-Server Queue (M/M/c model)
// Multiple servers pulling from single FCFS queue
class MultiServerQueue<T> {
    private queue: T[] = [];
    private activeServers = 0;
    private maxServers: number;
    
    constructor(servers: number) {
        this.maxServers = servers;
    }
    
    async enqueue(
        item: T,
        process: (item: T) => Promise<void>
    ): Promise<void> {
        this.queue.push(item);
        this.tryProcess(process);
    }
    
    private async tryProcess(
        process: (item: T) => Promise<void>
    ): Promise<void> {
        if (this.activeServers >= this.maxServers) return;
        if (this.queue.length === 0) return;
        
        this.activeServers++;
        const item = this.queue.shift()!;  // FCFS: always front
        
        try {
            await process(item);
        } finally {
            this.activeServers--;
            this.tryProcess(process);  // Check for more work
        }
    }
    
    getQueueLength(): number {
        return this.queue.length;
    }
    
    getActiveServers(): number {
        return this.activeServers;
    }
}
 
// Pattern 3: Buffer-Limited Queue
// FCFS with capacity limit (drops when full)
class BoundedFCFSQueue<T> {
    private queue: T[] = [];
    private capacity: number;
    private dropped = 0;
    
    constructor(capacity: number) {
        this.capacity = capacity;
    }
    
    enqueue(item: T): boolean {
        if (this.queue.length >= this.capacity) {
            this.dropped++;
            return false;  // Queue full, item dropped
        }
        this.queue.push(item);
        return true;
    }
    
    dequeue(): T | undefined {
        return this.queue.shift();
    }
    
    getDropRate(): number {
        const total = this.queue.length + this.dropped;
        return total > 0 ? this.dropped / total : 0;
    }
}
 
/*
Real-world examples:
 
Single-Server: Small business with one cashier
Multi-Server: Bank with multiple tellers
Bounded Queue: Network buffer with packet drops
*/

Service System Queue Configurations
Configuration	Real-World Example	Trade-offs
Single queue, single server	Doctor's waiting room	Simple, fair, but slow
Single queue, multiple servers	Bank tellers	Fair and parallel, best of both
Multiple queues, multiple servers	Supermarket checkouts	Fast for some, unfair (luck-based)
Priority queue, single server	Hospital ER	Efficient for urgent cases, possible starvation

The Single Queue Advantage

Queue Theory Fundamentals

Key Concepts:

Arrival Rate (λ): Average number of arrivals per time unit
Service Rate (μ): Average number of completions per time unit
Utilization (ρ): λ/μ — fraction of time the server is busy
Stability Condition: ρ < 1 (arrivals must be slower than service on average)

queue-theory-metrics.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// Queue Theory Metrics Calculation
 
interface QueueMetrics {
    utilization: number;         // ρ = λ/μ
    avgQueueLength: number;      // L_q (average items waiting)
    avgSystemLength: number;     // L (average items in system)
    avgWaitingTime: number;      // W_q (average time waiting)
    avgSystemTime: number;       // W (average time in system)
}
 
/**
 * Calculate M/M/1 queue metrics
 * M/M/1 = Markovian arrivals, Markovian service, 1 server
 * 
 * @param arrivalRate λ - average arrivals per time unit
 * @param serviceRate μ - average services per time unit
 */
function calculateMM1Metrics(
    arrivalRate: number,  // λ
    serviceRate: number   // μ
): QueueMetrics | null {
    const utilization = arrivalRate / serviceRate;  // ρ
    
    // Stability check: must have μ > λ
    if (utilization >= 1) {
        console.error("Queue is unstable! Arrival rate >= service rate");
        return null;
    }
    
    // M/M/1 formulas (assuming exponential distributions)
    // Average number in queue: L_q = ρ² / (1 - ρ)
    const avgQueueLength = 
        (utilization * utilization) / (1 - utilization);
    
    // Average number in system: L = ρ / (1 - ρ)
    const avgSystemLength = utilization / (1 - utilization);
    
    // Little's Law: L = λ * W
    // Therefore: W = L / λ
    const avgSystemTime = avgSystemLength / arrivalRate;
    
    // Waiting time: W_q = L_q / λ (also by Little's Law)
    const avgWaitingTime = avgQueueLength / arrivalRate;
    
    return {
        utilization,
        avgQueueLength,
        avgSystemLength,
        avgWaitingTime,
        avgSystemTime
    };
}
 
// Example: Web server analysis
const webServerMetrics = calculateMM1Metrics(
    80,   // 80 requests per second
    100   // Can handle 100 requests per second
);
 
console.log("Web Server Queue Analysis:");
console.log(`Utilization: ${(webServerMetrics!.utilization * 100).toFixed(1)}%`);
console.log(`Avg queue length: ${webServerMetrics!.avgQueueLength.toFixed(2)} requests`);
console.log(`Avg waiting time: ${(webServerMetrics!.avgWaitingTime * 1000).toFixed(1)}ms`);
console.log(`Avg total time: ${(webServerMetrics!.avgSystemTime * 1000).toFixed(1)}ms`);
 
/*
Output:
Web Server Queue Analysis:
Utilization: 80.0%
Avg queue length: 3.20 requests
Avg waiting time: 40.0ms
Avg total time: 50.0ms (waiting + service)
 
Key insight: At 80% utilization, you still have significant queuing!
At 90% utilization, queue length would be 8.1 (more than double).
*/
 
// Demonstrate utilization impact
console.log("
Impact of Utilization:");
for (const util of [0.5, 0.7, 0.8, 0.9, 0.95, 0.99]) {
    const λ = util * 100;  // Adjust arrival rate
    const metrics = calculateMM1Metrics(λ, 100);
    console.log(
        `ρ=${(util * 100).toFixed(0)}%: ` +
                                        `Queue=${metrics!.avgQueueLength.toFixed(1)}, ` +
                                    `Wait=${(metrics!.avgWaitingTime * 1000).toFixed(0)}ms`
    );
}
 
/*
Impact of Utilization:
ρ=50%: Queue=0.5, Wait=5ms
ρ=70%: Queue=1.6, Wait=16ms
ρ=80%: Queue=3.2, Wait=32ms
ρ=90%: Queue=8.1, Wait=81ms
ρ=95%: Queue=18.1, Wait=181ms
ρ=99%: Queue=98.0, Wait=980ms
 
As utilization approaches 100%, queues explode!
This is why we don't run servers at 100% capacity.
*/

Little's Law

Practical Implications:

Never run at 100% capacity — As utilization approaches 100%, queue length approaches infinity. Real systems need headroom.
The 80% rule — Many systems are designed to run at ~70-80% utilization under normal load, leaving room for traffic spikes.
Tail latencies matter — Average waiting time might be 50ms, but the 99th percentile could be 500ms. FCFS doesn't protect against outliers.
Adding servers helps nonlinearly — Going from 1 to 2 servers can reduce queue length dramatically (more than 50%).

FCFS in Distributed Systems

distributed-fcfs.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// FCFS Challenges in Distributed Systems
 
// Challenge 1: Clock Skew
// Different servers have different clock times
interface TimestampedRequest {
    id: string;
    clientTimestamp: number;  // Client's view of time
    serverReceiveTime: number;  // Server's view of arrival
}
 
// Whose timestamp do we trust for FCFS?
function orderByClientTime(
    requests: TimestampedRequest[]
): TimestampedRequest[] {
    // Client timestamps can be manipulated or skewed
    return [...requests].sort((a, b) => 
        a.clientTimestamp - b.clientTimestamp
    );
}
 
function orderByServerTime(
    requests: TimestampedRequest[]
): TimestampedRequest[] {
    // Server time is trustworthy but may not reflect true order
    // (Network delays can reorder packets)
    return [...requests].sort((a, b) => 
        a.serverReceiveTime - b.serverReceiveTime
    );
}
 
// Solution: Lamport Timestamps or Vector Clocks
// (covered in distributed systems courses)
 
// Challenge 2: Multi-Leader / Partitioned Queues
// How to maintain global FCFS across partitions?
 
interface PartitionedQueue {
    partitions: Map<string, Request[]>;
}
 
function globalFCFSFromPartitions(
    pq: PartitionedQueue
): Request[] {
    // Problem: each partition has its own order
    // Merging them requires a global timestamp
    
    const allRequests: Array<{
        partition: string;
        request: Request;
    }> = [];
    
    for (const [partition, requests] of pq.partitions) {
        for (const request of requests) {
            allRequests.push({ partition, request });
        }
    }
    
    // Sort by global timestamp (requires synchronized clocks!)
    return allRequests
        .sort((a, b) => a.request.arrivalTime - b.request.arrivalTime)
        .map(item => item.request);
}
 
interface Request {
    id: string;
    arrivalTime: number;
}
 
// Challenge 3: Exactly-Once Delivery
// Retries can violate FCFS appearance
 
class IdempotentQueue {
    private queue: Request[] = [];
    private processedIds = new Set<string>();
    
    enqueue(request: Request): boolean {
        // Deduplicate: same request might arrive multiple times
        if (this.processedIds.has(request.id)) {
            return false;  // Already handled
        }
        this.queue.push(request);
        return true;
    }
    
    dequeue(): Request | undefined {
        const request = this.queue.shift();
        if (request) {
            this.processedIds.add(request.id);
        }
        return request;
    }
}
 
/*
Key insights for distributed FCFS:
 
1. "Arrival time" is ambiguous across machines
2. Network delays can reorder messages
3. Partitioning trades strict order for scalability
4. "Close enough" ordering is often acceptable
5. Message queues like Kafka provide per-partition ordering
*/

FCFS Ordering Guarantees in Distributed Systems
System Type	Ordering Guarantee	Trade-off
Single-partition Kafka	Strict FIFO within partition	Limited scalability per partition
AWS SQS Standard	Best-effort FIFO	Occasional reordering for performance
AWS SQS FIFO	Strict FIFO	Lower throughput, higher cost
Redis Streams	Strict per-stream	Single-node bottleneck for strict ordering
Google Pub/Sub	Best-effort	Optimized for throughput, not order

When Strict Order Matters

Request Queuing in Web Systems

Every web server, API gateway, and load balancer implements some form of request queuing. Understanding these patterns helps in capacity planning and performance optimization.

web-request-queue.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// Web Request Queuing Patterns
 
interface HttpRequest {
    id: string;
    path: string;
    method: string;
    timestamp: number;
}
 
interface HttpResponse {
    status: number;
    body: string;
    processingTime: number;
    queueTime: number;
}
 
// Pattern: Request Queue with Backpressure
class BackpressureQueue {
    private queue: HttpRequest[] = [];
    private maxQueueSize: number;
    private processing = false;
    private concurrency: number;
    private activeRequests = 0;
    
    constructor(
        maxQueueSize: number,
        concurrency: number
    ) {
        this.maxQueueSize = maxQueueSize;
        this.concurrency = concurrency;
    }
    
    async handleRequest(
        request: HttpRequest,
        handler: (req: HttpRequest) => Promise<HttpResponse>
    ): Promise<HttpResponse> {
        const arrivalTime = Date.now();
        
        // Backpressure: reject if queue too long
        if (this.queue.length >= this.maxQueueSize) {
            return {
                status: 503,  // Service Unavailable
                body: "Server overloaded, try again later",
                processingTime: 0,
                queueTime: 0
            };
        }
        
        // Enqueue and wait for processing
        return new Promise((resolve) => {
            const queuedRequest = {
                request,
                resolve,
                arrivalTime
            };
            this.queue.push(queuedRequest as any);
            this.tryProcess(handler);
        });
    }
    
    private async tryProcess(
        handler: (req: HttpRequest) => Promise<HttpResponse>
    ): Promise<void> {
        while (
            this.activeRequests < this.concurrency &&
            this.queue.length > 0
        ) {
            const item = this.queue.shift() as any;
            this.activeRequests++;
            
            const startTime = Date.now();
            const queueTime = startTime - item.arrivalTime;
            
            try {
                const response = await handler(item.request);
                item.resolve({
                    ...response,
                    queueTime
                });
            } catch (error) {
                item.resolve({
                    status: 500,
                    body: "Internal server error",
                    processingTime: Date.now() - startTime,
                    queueTime
                });
            } finally {
                this.activeRequests--;
                this.tryProcess(handler);
            }
        }
    }
    
    getMetrics(): {
        queueLength: number;
        activeRequests: number;
        capacity: number;
    } {
        return {
            queueLength: this.queue.length,
            activeRequests: this.activeRequests,
            capacity: this.maxQueueSize - this.queue.length
        };
    }
}
 
// Usage: Express.js middleware example
/*
const requestQueue = new BackpressureQueue(1000, 10);
 
app.use(async (req, res, next) => {
    const response = await requestQueue.handleRequest(
        { id: uuid(), path: req.path, method: req.method, timestamp: Date.now() },
        async (request) => {
            // Your actual handler logic
            return { status: 200, body: "OK", processingTime: 50, queueTime: 0 };
        }
    );
    
    res.status(response.status).send(response.body);
});
*/
 
/*
Key patterns demonstrated:
1. FCFS ordering of requests
2. Backpressure (503 when overloaded)
3. Concurrency limiting
4. Queue time tracking for observability
5. Graceful degradation under load
*/

The Request Queue Hierarchy:

In a typical web stack, requests pass through multiple queues:

OS Socket Queue — Kernel buffers incoming TCP connections
Web Server Accept Queue — Server's pending connection queue
Worker Thread Pool Queue — Jobs waiting for worker threads
Application Queue — Your own queuing logic
Database Connection Pool Queue — Queries waiting for DB connections

Each level can become a bottleneck. Understanding where queuing happens helps diagnose latency issues.

Measure Queue Time

Stream Processing and Event Queues

event-stream-processing.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// Event Stream Processing with FCFS Ordering
 
interface Event {
    id: string;
    timestamp: number;
    type: string;
    data: Record<string, any>;
    partition?: string;  // For partitioned processing
}
 
// Pattern: Ordered Event Stream
class OrderedEventStream {
    private events: Event[] = [];
    private consumers: ((event: Event) => void)[] = [];
    private offset = 0;  // Current read position
    
    // Append-only: maintains temporal order
    publish(event: Event): number {
        const position = this.events.length;
        this.events.push(event);
        
        // Notify consumers
        for (const consumer of this.consumers) {
            consumer(event);
        }
        
        return position;  // Return offset for acknowledgment
    }
    
    // Read from specific offset (replayability!)
    readFrom(offset: number, count: number): Event[] {
        return this.events.slice(offset, offset + count);
    }
    
    // Subscribe to new events
    subscribe(consumer: (event: Event) => void): () => void {
        this.consumers.push(consumer);
        return () => {
            const idx = this.consumers.indexOf(consumer);
            if (idx >= 0) this.consumers.splice(idx, 1);
        };
    }
    
    // Consumer group pattern: each event processed once per group
    createConsumerGroup(
        groupId: string,
        handler: (event: Event) => Promise<void>
    ): EventConsumer {
        return new EventConsumer(this, groupId, handler);
    }
}
 
class EventConsumer {
    private stream: OrderedEventStream;
    private groupId: string;
    private handler: (event: Event) => Promise<void>;
    private committedOffset = 0;
    private running = false;
    
    constructor(
        stream: OrderedEventStream,
        groupId: string,
        handler: (event: Event) => Promise<void>
    ) {
        this.stream = stream;
        this.groupId = groupId;
        this.handler = handler;
    }
    
    async start(): Promise<void> {
        this.running = true;
        
        while (this.running) {
            const events = this.stream.readFrom(this.committedOffset, 10);
            
            for (const event of events) {
                await this.handler(event);
                this.committedOffset++;  // Move forward after success
            }
            
            if (events.length === 0) {
                await sleep(100);  // No events, wait a bit
            }
        }
    }
    
    stop(): void {
        this.running = false;
    }
    
    getOffset(): number {
        return this.committedOffset;
    }
}
 
async function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}
 
// Usage example: Event sourcing
/*
const eventStream = new OrderedEventStream();
 
// Publish events
eventStream.publish({
    id: "evt-1",
    timestamp: Date.now(),
    type: "user_registered",
    data: { userId: "u123", email: "user@example.com" }
});
 
eventStream.publish({
    id: "evt-2", 
    timestamp: Date.now(),
    type: "order_placed",
    data: { orderId: "o456", userId: "u123", total: 99.99 }
});
 
// Consumer processes in order
const consumer = eventStream.createConsumerGroup(
    "order-processor",
    async (event) => {
        console.log(`Processing: ${event.type}`);
        // FCFS: events processed in publish order
    }
);
 
consumer.start();
*/
 
/*
This pattern mirrors Apache Kafka, AWS Kinesis, etc.
Key properties:
1. Append-only log = natural FCFS ordering
2. Offsets enable replay from any point
3. Consumer groups enable parallel processing
4. Partitioning enables horizontal scaling
*/

Event Streaming Platforms

•Apache Kafka: Distributed commit log with strict per-partition ordering. Industry standard for high-throughput event streaming.
•AWS Kinesis: Managed streaming with shards (partitions). Strict per-shard ordering.
•Apache Pulsar: Multi-layer architecture separating compute and storage. Flexible ordering guarantees.
•Redis Streams: Lightweight event streaming built into Redis. Great for simpler use cases.
•Google Pub/Sub: Global message delivery. Ordering is optional and per-key.

When FCFS is Wrong

While FCFS provides fairness, it's not always the right choice. Understanding when to deviate from FCFS is crucial for system design.

Use FCFS When

•All requests have similar importance
•All requests have similar processing times
•Fairness is more important than efficiency
•Ordering has semantic meaning (logs, transactions)
•Simplicity is paramount
•Debugging/auditing requires clear order

Avoid FCFS When

•Requests have vastly different priorities
•Processing times vary significantly (convoy effect)
•Real-time deadlines must be met
•Some requests can be batched together
•Responsiveness matters more than fairness
•Short jobs should not wait behind long jobs

Alternative Strategies:

Priority Queuing: Urgent requests jump ahead. Risk: starvation of low-priority items.
Shortest Job First (SJF): If you know processing time, serve shortest first. Optimal for average waiting time but unfair.
Weighted Fair Queuing: Each flow gets fair share, but VIP flows get larger shares.
Deadline-Based: Tasks with nearest deadlines processed first. Essential for real-time systems.
Round-Robin with Priorities: Multiple priority levels, round-robin within each level.

The Hospital Exception

Summary: FCFS Processing Mastered

First-Come-First-Serve processing is one of the most fundamental patterns in computing. Let's consolidate the key insights:

Key Takeaways

•FCFS guarantees arrival-order fairness — First to arrive is first to be served, ensuring no starvation and predictable behavior.
•Queue theory provides mathematical foundations — Utilization, Little's Law, and arrival/service rate analysis guide capacity planning.
•Never run at 100% utilization — As utilization approaches capacity, queue lengths and wait times grow exponentially.
•Distributed FCFS is challenging — Clock skew, network delays, and partitioning complicate strict ordering across machines.
•Request queuing happens at multiple levels — From OS sockets to application logic, understand where your queues are.
•Event streaming applies FCFS at scale — Append-only logs with consumer offsets enable massive ordered event processing.
•FCFS isn't always right — When priorities, deadlines, or efficiency matter more than strict fairness, consider alternatives.

Module Complete:

With this page, you've completed the Common Queue Patterns & Problem Types module. You now understand:

Level-order processing (tree/hierarchy traversal)
BFS intuition (wave expansion, shortest paths)
Task scheduling simulation (FCFS, round-robin, multi-level)
FCFS processing principles (fairness, queue theory, real-world systems)

These four patterns form the foundation of queue-based problem solving. You're equipped to recognize when a problem calls for a queue and to apply the appropriate pattern effectively.

Module Complete

4 / 4