Jitter to Prevent Thundering Herd

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

// Jitter strategy implementations
type JitterStrategy = 'none' | 'full' | 'equal' | 'decorrelated';
 
interface JitterConfig {
    strategy: JitterStrategy;
    baseDelayMs: number;
    multiplier: number;
    maxDelayMs: number;
}
 
class JitterCalculator {
    private previousDelay: number;
    
    constructor(private config: JitterConfig) {
        this.previousDelay = config.baseDelayMs;
    }
    
    /**
     * Calculate jittered delay for the given attempt
     */
    calculateDelay(attemptIndex: number): number {
        switch (this.config.strategy) {
            case 'none':
                return this.noJitter(attemptIndex);
            case 'full':
                return this.fullJitter(attemptIndex);
            case 'equal':
                return this.equalJitter(attemptIndex);
            case 'decorrelated':
                return this.decorrelatedJitter();
        }
    }
    
    /**
     * No jitter: pure exponential backoff
     */
    private noJitter(attemptIndex: number): number {
        const delay = this.config.baseDelayMs * 
            Math.pow(this.config.multiplier, attemptIndex);
        return Math.min(delay, this.config.maxDelayMs);
    }
    
    /**
     * Full jitter: random between 0 and exponential delay
     * Most aggressive spread, but may allow very short delays
     */
    private fullJitter(attemptIndex: number): number {
        const exponentialDelay = this.config.baseDelayMs * 
            Math.pow(this.config.multiplier, attemptIndex);
        const cappedDelay = Math.min(exponentialDelay, this.config.maxDelayMs);
        
        // Random between 0 and capped delay
        return Math.random() * cappedDelay;
    }
    
    /**
     * Equal jitter: half guaranteed, half random
     * Balanced approach with guaranteed minimum
     */
    private equalJitter(attemptIndex: number): number {
        const exponentialDelay = this.config.baseDelayMs * 
            Math.pow(this.config.multiplier, attemptIndex);
        const cappedDelay = Math.min(exponentialDelay, this.config.maxDelayMs);
        const halfDelay = cappedDelay / 2;
        
        // Guaranteed half + random half
        return halfDelay + Math.random() * halfDelay;
    }
    
    /**
     * Decorrelated jitter: based on previous delay
     * Self-regulating growth with natural randomization
     */
    private decorrelatedJitter(): number {
        const minDelay = this.config.baseDelayMs;
        const maxDelay = this.previousDelay * 3;
        
        // Random between base and 3x previous
        const delay = minDelay + Math.random() * (maxDelay - minDelay);
        
        // Cap and store for next iteration
        this.previousDelay = Math.min(delay, this.config.maxDelayMs);
        return this.previousDelay;
    }
    
    /**
     * Reset state (for decorrelated jitter)
     */
    reset(): void {
        this.previousDelay = this.config.baseDelayMs;
    }
}
 
// Demonstration function
function demonstrateJitterSpread() {
    const config: Omit<JitterConfig, 'strategy'> = {
        baseDelayMs: 100,
        multiplier: 2,
        maxDelayMs: 30000,
    };
    
    const strategies: JitterStrategy[] = ['none', 'full', 'equal', 'decorrelated'];
    const clientCount = 1000;
    const attemptIndex = 3; // 4th retry attempt, exponential delay = 800ms
    
    for (const strategy of strategies) {
        const calculator = new JitterCalculator({ ...config, strategy });
        const delays: number[] = [];
        
        for (let i = 0; i < clientCount; i++) {
            delays.push(calculator.calculateDelay(attemptIndex));
            if (strategy === 'decorrelated') {
                calculator.reset();
            }
        }
        
        const avgDelay = delays.reduce((a, b) => a + b) / delays.length;
        const minDelay = Math.min(...delays);
        const maxDelay = Math.max(...delays);
        const stdDev = Math.sqrt(
            delays.reduce((sum, d) => sum + Math.pow(d - avgDelay, 2), 0) / delays.length
        );
        
        console.log(`${strategy}: avg=${avgDelay.toFixed(0)}ms, ` +
                                        `min=${minDelay.toFixed(0)}ms, max=${maxDelay.toFixed(0)}ms, ` +
                                    `stddev=${stdDev.toFixed(0)}ms`);
    }
}

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152

// Production-ready jittered backoff implementation
interface JitteredBackoffConfig {
    baseDelayMs: number;
    maxDelayMs: number;
    multiplier: number;
    maxAttempts: number;
    jitter: 'none' | 'full' | 'equal';
    
    // Optional: minimum delay regardless of jitter
    minDelayMs?: number;
}
 
class JitteredExponentialBackoff {
    private attempt: number = 0;
    private totalWaitMs: number = 0;
    
    constructor(private config: JitteredBackoffConfig) {}
    
    /**
     * Get the next delay with jitter applied
     * Returns null if max attempts exceeded
     */
    nextDelay(): number | null {
        if (this.attempt >= this.config.maxAttempts) {
            return null;
        }
        
        // Calculate base exponential delay
        const exponentialDelay = this.config.baseDelayMs * 
            Math.pow(this.config.multiplier, this.attempt);
        
        // Apply cap
        const cappedDelay = Math.min(exponentialDelay, this.config.maxDelayMs);
        
        // Apply jitter
        let jitteredDelay: number;
        switch (this.config.jitter) {
            case 'full':
                jitteredDelay = Math.random() * cappedDelay;
                break;
            case 'equal':
                jitteredDelay = (cappedDelay / 2) + Math.random() * (cappedDelay / 2);
                break;
            case 'none':
            default:
                jitteredDelay = cappedDelay;
        }
        
        // Apply minimum if configured
        if (this.config.minDelayMs) {
            jitteredDelay = Math.max(jitteredDelay, this.config.minDelayMs);
        }
        
        this.attempt++;
        return Math.round(jitteredDelay);
    }
    
    recordWait(delayMs: number): void {
        this.totalWaitMs += delayMs;
    }
    
    get currentAttempt(): number {
        return this.attempt;
    }
    
    get totalWait(): number {
        return this.totalWaitMs;
    }
    
    reset(): void {
        this.attempt = 0;
        this.totalWaitMs = 0;
    }
}
 
/**
 * Higher-order function for retrying with jittered backoff
 */
async function withJitteredRetry<T>(
    operation: () => Promise<T>,
    config: JitteredBackoffConfig,
    isRetryable: (error: Error) => boolean = () => true
): Promise<T> {
    const backoff = new JitteredExponentialBackoff(config);
    let lastError: Error | undefined;
    
    for (let attempt = 0; attempt < config.maxAttempts; attempt++) {
        try {
            return await operation();
        } catch (error) {
            lastError = error as Error;
            
            if (!isRetryable(lastError)) {
                throw lastError;
            }
            
            const delay = backoff.nextDelay();
            if (delay === null) {
                break;
            }
            
            console.log(
                `Attempt ${attempt + 1}/${config.maxAttempts} failed. ` +
                                        `Retrying in ${delay}ms (jitter: ${config.jitter})...`
            );
            
            await sleep(delay);
            backoff.recordWait(delay);
        }
    }
    
    throw new Error(
        `Operation failed after ${backoff.currentAttempt} attempts ` +
                                    `(${backoff.totalWait}ms total wait): ${lastError?.message}`
    );
}
 
function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}
 
// Usage examples
async function examples() {
    // User-facing API call: fast retries with full jitter
    const userFacingConfig: JitteredBackoffConfig = {
        baseDelayMs: 50,
        maxDelayMs: 5000,
        multiplier: 2,
        maxAttempts: 4,
        jitter: 'full',
        minDelayMs: 10, // Never less than 10ms
    };
    
    // Background job: more retries with equal jitter
    const backgroundConfig: JitteredBackoffConfig = {
        baseDelayMs: 500,
        maxDelayMs: 60000,
        multiplier: 2,
        maxAttempts: 10,
        jitter: 'equal',
    };
    
    // External API: respect their rate limits more carefully
    const externalApiConfig: JitteredBackoffConfig = {
        baseDelayMs: 1000,
        maxDelayMs: 300000, // 5 minutes
        multiplier: 2,
        maxAttempts: 6,
        jitter: 'equal', // More predictable than full jitter
        minDelayMs: 500,  // Never hammer the API
    };
}

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
139
140

// Combining Retry-After with jitter
interface RetryAfterConfig {
    // Jitter percentage by Retry-After duration tier
    shortWindowJitterPercent: number;   // <= 60s
    mediumWindowJitterPercent: number;  // 60s - 300s
    longWindowJitterPercent: number;    // > 300s
    
    // Caps
    maxAdditionalJitterMs: number;
}
 
const defaultRetryAfterConfig: RetryAfterConfig = {
    shortWindowJitterPercent: 20,
    mediumWindowJitterPercent: 30,
    longWindowJitterPercent: 50,
    maxAdditionalJitterMs: 60000, // Never add more than 1 minute
};
 
function calculateDelayWithRetryAfter(
    exponentialDelayMs: number,
    retryAfterMs: number | undefined,
    config: RetryAfterConfig = defaultRetryAfterConfig
): number {
    // If no Retry-After, use standard jittered exponential backoff
    if (!retryAfterMs) {
        return Math.random() * exponentialDelayMs;
    }
    
    // Use Retry-After as minimum, then add jitter
    const retryAfterSeconds = retryAfterMs / 1000;
    
    let jitterPercent: number;
    if (retryAfterSeconds <= 60) {
        jitterPercent = config.shortWindowJitterPercent;
    } else if (retryAfterSeconds <= 300) {
        jitterPercent = config.mediumWindowJitterPercent;
    } else {
        jitterPercent = config.longWindowJitterPercent;
    }
    
    // Calculate jitter to add
    const maxJitter = Math.min(
        retryAfterMs * (jitterPercent / 100),
        config.maxAdditionalJitterMs
    );
    
    const additionalJitter = Math.random() * maxJitter;
    
    return retryAfterMs + additionalJitter;
}
 
// Example: Parse Retry-After header and apply jitter
function parseAndApplyRetryAfter(
    response: Response,
    fallbackDelayMs: number
): number {
    const retryAfterHeader = response.headers.get('Retry-After');
    
    if (!retryAfterHeader) {
        // No Retry-After, fall back to jittered exponential
        return Math.random() * fallbackDelayMs;
    }
    
    let retryAfterMs: number;
    
    // Retry-After can be seconds (integer) or HTTP date
    const seconds = parseInt(retryAfterHeader, 10);
    if (!isNaN(seconds)) {
        retryAfterMs = seconds * 1000;
    } else {
        // Try parsing as HTTP date
        const date = new Date(retryAfterHeader);
        if (isNaN(date.getTime())) {
            // Invalid format, use fallback
            return Math.random() * fallbackDelayMs;
        }
        retryAfterMs = Math.max(0, date.getTime() - Date.now());
    }
    
    return calculateDelayWithRetryAfter(fallbackDelayMs, retryAfterMs);
}
 
// Production retry wrapper with Retry-After support
async function retryWithRetryAfterSupport<T>(
    operation: () => Promise<T>,
    config: {
        baseDelayMs: number;
        maxDelayMs: number;
        multiplier: number;
        maxAttempts: number;
    }
): Promise<T> {
    let lastError: Error | undefined;
    
    for (let attempt = 0; attempt < config.maxAttempts; attempt++) {
        try {
            return await operation();
        } catch (error) {
            lastError = error as Error;
            
            // Calculate fallback exponential delay
            const exponentialDelay = config.baseDelayMs * 
                Math.pow(config.multiplier, attempt);
            const cappedDelay = Math.min(exponentialDelay, config.maxDelayMs);
            
            // Check for Retry-After in error response
            const retryAfterMs = extractRetryAfterFromError(lastError);
            
            // Calculate actual delay with jitter
            const actualDelay = calculateDelayWithRetryAfter(
                cappedDelay,
                retryAfterMs
            );
            
            console.log(
                `Attempt ${attempt + 1} failed. ` +
                                        `Retry-After: ${retryAfterMs ? retryAfterMs + 'ms' : 'none'}. ` +
                                    `Actual wait: ${Math.round(actualDelay)}ms`
            );
            
            await sleep(actualDelay);
        }
    }
    
    throw lastError;
}
 
function extractRetryAfterFromError(error: Error): number | undefined {
    const response = (error as any).response;
    const header = response?.headers?.['retry-after'];
    if (typeof header === 'string') {
        const seconds = parseInt(header, 10);
        if (!isNaN(seconds)) return seconds * 1000;
    }
    return undefined;
}
 
function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}

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
139
140
141
142
143
144
145
146
147
148

// Jitter applied to various distributed systems contexts
 
// 1. Scheduled Job Jitter
class JitteredScheduler {
    /**
     * Add jitter to scheduled execution time
     * Spreads jobs configured for the same time across a window
     */
    getJitteredStartTime(
        scheduledTime: Date,
        scheduleIntervalMs: number,
        jitterPercent: number = 10
    ): Date {
        const jitterWindow = scheduleIntervalMs * (jitterPercent / 100);
        const jitterMs = Math.random() * jitterWindow;
        return new Date(scheduledTime.getTime() + jitterMs);
    }
}
 
// 2. Cache TTL Jitter
class JitteredCache<T> {
    constructor(
        private cache: Map<string, { value: T; expiresAt: number }> = new Map(),
        private jitterPercent: number = 20
    ) {}
    
    /**
     * Set with jittered TTL to prevent cache stampede
     */
    set(key: string, value: T, baseTTLMs: number): void {
        const jitter = baseTTLMs * (this.jitterPercent / 100);
        const jitteredTTL = baseTTLMs + Math.random() * jitter;
        
        this.cache.set(key, {
            value,
            expiresAt: Date.now() + jitteredTTL,
        });
    }
    
    get(key: string): T | undefined {
        const entry = this.cache.get(key);
        if (!entry) return undefined;
        
        if (Date.now() > entry.expiresAt) {
            this.cache.delete(key);
            return undefined;
        }
        
        return entry.value;
    }
}
 
// 3. Health Check Intervals
class JitteredHealthChecker {
    private intervalId?: ReturnType<typeof setTimeout>;
    
    constructor(
        private checkFn: () => Promise<boolean>,
        private baseIntervalMs: number,
        private jitterPercent: number = 30
    ) {}
    
    start(): void {
        const scheduleNext = () => {
            // Jitter each interval to desynchronize from other checkers
            const jitter = this.baseIntervalMs * (this.jitterPercent / 100);
            const nextInterval = this.baseIntervalMs + Math.random() * jitter;
            
            this.intervalId = setTimeout(async () => {
                await this.checkFn();
                scheduleNext();
            }, nextInterval);
        };
        
        // Also jitter initial startup
        const initialDelay = Math.random() * this.baseIntervalMs;
        setTimeout(scheduleNext, initialDelay);
    }
    
    stop(): void {
        if (this.intervalId) {
            clearTimeout(this.intervalId);
        }
    }
}
 
// 4. Connection Pool Reconnection
class JitteredConnectionPool {
    private connections: Connection[] = [];
    
    /**
     * When a connection fails, reconnect with jitter
     * Prevents all failed connections from reconnecting simultaneously
     */
    async handleConnectionFailure(conn: Connection): Promise<void> {
        // Base delay with exponential backoff
        const baseDelay = 1000 * Math.pow(2, conn.reconnectAttempts);
        const cappedDelay = Math.min(baseDelay, 60000);
        
        // Add full jitter
        const jitteredDelay = Math.random() * cappedDelay;
        
        console.log(
            `Connection ${conn.id} failed. ` +
                                        `Reconnecting in ${Math.round(jitteredDelay)}ms`
        );
        
        await sleep(jitteredDelay);
        await this.reconnect(conn);
    }
    
    private async reconnect(conn: Connection): Promise<void> {
        // Reconnection logic
    }
}
 
// 5. Batch Processing Staggering
class JitteredBatchProcessor<T> {
    /**
     * Process batches with jittered start times
     * Prevents synchronized batch processing across workers
     */
    async processBatchesWithJitter(
        batches: T[][],
        processor: (batch: T[]) => Promise<void>,
        maxJitterMs: number = 5000
    ): Promise<void> {
        const promises = batches.map(async (batch, index) => {
            // Stagger starts with jitter
            const jitter = Math.random() * maxJitterMs;
            await sleep(jitter);
            
            console.log(`Starting batch ${index} after ${Math.round(jitter)}ms jitter`);
            return processor(batch);
        });
        
        await Promise.all(promises);
    }
}
 
interface Connection {
    id: string;
    reconnectAttempts: number;
}
 
function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}