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

// Comparing Backoff Strategies
 
function linearBackoff(attempt: number, base: number): number {
  return base * attempt;  // 100, 200, 300, 400, 500...
}
 
function polynomialBackoff(attempt: number, base: number, power: number = 2): number {
  return base * Math.pow(attempt, power);  // 100, 400, 900, 1600, 2500...
}
 
function exponentialBackoff(attempt: number, base: number, multiplier: number = 2): number {
  return base * Math.pow(multiplier, attempt - 1);  // 100, 200, 400, 800, 1600...
}
 
// Compare total load over 10 retries for 1000 concurrent clients
function calculateRetryLoad(
  backoffFn: (attempt: number, base: number) => number,
  clients: number,
  maxRetries: number,
  base: number
): { attemptLoads: number[]; totalLoad: number } {
  const attemptLoads: number[] = [];
  let totalLoad = 0;
  
  // Assume all clients start at t=0 and fail
  // Each retry spreads based on delay
  for (let attempt = 1; attempt <= maxRetries; attempt++) {
    const delay = backoffFn(attempt, base);
    // Load contribution inversely proportional to delay
    // (more spread = less instantaneous load)
    const instantaneousLoad = clients / (delay / 100);  // Normalize to base
    attemptLoads.push(instantaneousLoad);
    totalLoad += clients;  // Each client retries once
  }
  
  return { attemptLoads, totalLoad };
}
 
// Demonstration
const clients = 1000;
const base = 100;  // ms
const maxRetries = 5;
 
console.log("Linear:      ", linearBackoff(5, base));      // 500ms
console.log("Polynomial:  ", polynomialBackoff(5, base));  // 2500ms
console.log("Exponential: ", exponentialBackoff(5, base)); // 1600ms
 
// Exponential is the "Goldilocks" choice:
// - Not too fast (linear starts too aggressive)
// - Not too slow (polynomial takes too long for quick failures)
// - Just right for the distribution of real-world failure durations

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

/**
 * Production-Grade Exponential Backoff Implementation
 */
 
interface BackoffConfig {
  /** Initial delay in milliseconds (default: 100) */
  baseDelayMs: number;
  
  /** Multiplier for each attempt (default: 2 for true exponential) */
  multiplier: number;
  
  /** Maximum delay between retries in milliseconds (default: 30000) */
  maxDelayMs: number;
  
  /** Maximum number of retry attempts (default: 5) */
  maxAttempts: number;
  
  /** Whether to add jitter to prevent thundering herd (default: true) */
  useJitter: boolean;
  
  /** Jitter type: 'full' (0 to delay) or 'decorrelated' (delay to 3*delay) */
  jitterType: "full" | "equal" | "decorrelated";
}
 
const DEFAULT_CONFIG: BackoffConfig = {
  baseDelayMs: 100,
  multiplier: 2,
  maxDelayMs: 30000,
  maxAttempts: 5,
  useJitter: true,
  jitterType: "equal",
};
 
class ExponentialBackoff {
  private config: BackoffConfig;
  
  constructor(config: Partial<BackoffConfig> = {}) {
    this.config = { ...DEFAULT_CONFIG, ...config };
    this.validateConfig();
  }
  
  private validateConfig(): void {
    if (this.config.baseDelayMs <= 0) {
      throw new Error("baseDelayMs must be positive");
    }
    if (this.config.multiplier < 1) {
      throw new Error("multiplier must be >= 1");
    }
    if (this.config.maxDelayMs < this.config.baseDelayMs) {
      throw new Error("maxDelayMs must be >= baseDelayMs");
    }
    if (this.config.maxAttempts < 1) {
      throw new Error("maxAttempts must be >= 1");
    }
  }
  
  /**
   * Calculate the raw exponential delay for a given attempt.
   * Attempt is 1-indexed (first retry = attempt 1).
   */
  calculateRawDelay(attempt: number): number {
    // delay = base × multiplier^(attempt-1)
    const exponentialDelay = this.config.baseDelayMs * 
      Math.pow(this.config.multiplier, attempt - 1);
    
    // Apply maximum cap
    return Math.min(exponentialDelay, this.config.maxDelayMs);
  }
  
  /**
   * Calculate delay with optional jitter applied.
   */
  calculateDelay(attempt: number): number {
    const rawDelay = this.calculateRawDelay(attempt);
    
    if (!this.config.useJitter) {
      return rawDelay;
    }
    
    return this.applyJitter(rawDelay, attempt);
  }
  
  /**
   * Apply jitter to prevent thundering herd.
   * Different jitter strategies trade off between spread and predictability.
   */
  private applyJitter(delay: number, attempt: number): number {
    switch (this.config.jitterType) {
      case "full":
        // Full jitter: random between 0 and delay
        // Maximum spread, but can result in very short delays
        return Math.random() * delay;
      
      case "equal":
        // Equal jitter: delay/2 + random(delay/2)
        // Balanced approach - ensures minimum delay while adding spread
        return (delay / 2) + (Math.random() * delay / 2);
      
      case "decorrelated":
        // Decorrelated jitter: based on previous delay, not attempt
        // Best for very high contention scenarios
        // temp = min(maxDelay, random_between(base, prev * 3))
        const prevDelay = attempt > 1 
          ? this.calculateRawDelay(attempt - 1) 
          : this.config.baseDelayMs;
        const minDelay = this.config.baseDelayMs;
        const maxDelay = Math.min(prevDelay * 3, this.config.maxDelayMs);
        return minDelay + Math.random() * (maxDelay - minDelay);
      
      default:
        return delay;
    }
  }
  
  /**
   * Get the full retry schedule (all attempts and delays).
   * Useful for logging, debugging, and understanding behavior.
   */
  getSchedule(): Array<{ attempt: number; delay: number; cumulative: number }> {
    const schedule: Array<{ attempt: number; delay: number; cumulative: number }> = [];
    let cumulative = 0;
    
    for (let attempt = 1; attempt <= this.config.maxAttempts; attempt++) {
      const delay = this.calculateDelay(attempt);
      cumulative += delay;
      schedule.push({ attempt, delay: Math.round(delay), cumulative: Math.round(cumulative) });
    }
    
    return schedule;
  }
  
  /**
   * Calculate maximum total time for all retries.
   * Useful for setting overall timeout budgets.
   */
  getMaxTotalTime(): number {
    let total = 0;
    for (let attempt = 1; attempt <= this.config.maxAttempts; attempt++) {
      total += this.calculateRawDelay(attempt);  // Use raw (max) for budget
    }
    return total;
  }
  
  /**
   * Check if more retries are allowed.
   */
  shouldRetry(currentAttempt: number): boolean {
    return currentAttempt < this.config.maxAttempts;
  }
  
  /**
   * Sleep for the calculated delay.
   * Returns the actual delay slept.
   */
  async sleep(attempt: number): Promise<number> {
    const delay = this.calculateDelay(attempt);
    await new Promise(resolve => setTimeout(resolve, delay));
    return delay;
  }
}
 
// =========================================
// Usage Examples
// =========================================
 
// Basic usage
const backoff = new ExponentialBackoff();
console.log("Schedule:", backoff.getSchedule());
// [
//   { attempt: 1, delay: ~75-100, cumulative: ~75-100 },
//   { attempt: 2, delay: ~150-200, cumulative: ~225-300 },
//   { attempt: 3, delay: ~300-400, cumulative: ~525-700 },
//   ...
// ]
 
// Aggressive backoff for quick failures
const aggressiveBackoff = new ExponentialBackoff({
  baseDelayMs: 50,
  maxAttempts: 3,
  maxDelayMs: 1000,
});
 
// Conservative backoff for external APIs
const conservativeBackoff = new ExponentialBackoff({
  baseDelayMs: 1000,
  multiplier: 3,  // Slower growth
  maxAttempts: 5,
  maxDelayMs: 60000,
});
 
// Print schedules for comparison
console.log("
Aggressive schedule:");
console.log(aggressiveBackoff.getSchedule());
console.log("Max total time:", aggressiveBackoff.getMaxTotalTime(), "ms");
 
console.log("
Conservative schedule:");
console.log(conservativeBackoff.getSchedule());
console.log("Max total time:", conservativeBackoff.getMaxTotalTime(), "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

/**
 * Complete Retry-with-Backoff Implementation
 */
 
interface RetryOptions {
  maxAttempts: number;
  baseDelayMs: number;
  maxDelayMs: number;
  retryableErrors?: (error: Error) => boolean;
  onRetry?: (attempt: number, error: Error, delayMs: number) => void;
}
 
async function retryWithBackoff<T>(
  operation: () => Promise<T>,
  options: Partial<RetryOptions> = {}
): Promise<T> {
  const config: RetryOptions = {
    maxAttempts: 3,
    baseDelayMs: 100,
    maxDelayMs: 10000,
    retryableErrors: () => true,  // Retry all errors by default
    onRetry: () => {},
    ...options,
  };
  
  const backoff = new ExponentialBackoff({
    baseDelayMs: config.baseDelayMs,
    maxDelayMs: config.maxDelayMs,
    maxAttempts: config.maxAttempts,
    useJitter: true,
    jitterType: "equal",
  });
  
  let lastError: Error | null = null;
  
  for (let attempt = 1; attempt <= config.maxAttempts; attempt++) {
    try {
      // Execute the operation
      return await operation();
    } catch (error) {
      lastError = error as Error;
      
      // Check if we should retry this error
      if (!config.retryableErrors!(lastError)) {
        throw lastError;  // Non-retryable, fail immediately
      }
      
      // Check if we have retries remaining
      if (attempt === config.maxAttempts) {
        throw lastError;  // Exhausted all attempts
      }
      
      // Calculate and wait for backoff delay
      const delay = backoff.calculateDelay(attempt);
      config.onRetry!(attempt, lastError, delay);
      
      await backoff.sleep(attempt);
    }
  }
  
  // Should never reach here, but TypeScript needs this
  throw lastError || new Error("Retry failed");
}
 
// =========================================
// Usage Example: API Call with Retry
// =========================================
 
async function fetchUserWithRetry(userId: string): Promise<User> {
  return retryWithBackoff(
    async () => {
      const response = await fetch(`https://api.example.com/users/${userId}`);
      
      if (!response.ok) {
        const error = new Error(`HTTP ${response.status}`);
        (error as any).status = response.status;
        throw error;
      }
      
      return response.json();
    },
    {
      maxAttempts: 3,
      baseDelayMs: 200,
      maxDelayMs: 5000,
      
      // Only retry 5xx errors and network errors
      retryableErrors: (error) => {
        const status = (error as any).status;
        if (status && status >= 400 && status < 500) {
          return false;  // Don't retry 4xx
        }
        return true;  // Retry 5xx and network errors
      },
      
      // Log retry attempts
      onRetry: (attempt, error, delay) => {
        console.log(
          `Retry attempt ${attempt} after ${delay}ms due to: ${error.message}`
        );
      },
    }
  );
}
 
interface User {
  id: string;
  name: string;
  email: string;
}

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

/**
 * Pre-configured Backoff Strategies for Common Scenarios
 */
 
// Fast and aggressive for internal services
const INTERNAL_SERVICE_BACKOFF: Partial<BackoffConfig> = {
  baseDelayMs: 50,
  multiplier: 2,
  maxDelayMs: 2000,
  maxAttempts: 3,
  useJitter: true,
  jitterType: "equal",
};
// Schedule: ~50ms, ~100ms, ~200ms (max total ≈ 350ms)
 
// Patient strategy for external APIs
const EXTERNAL_API_BACKOFF: Partial<BackoffConfig> = {
  baseDelayMs: 1000,
  multiplier: 2,
  maxDelayMs: 30000,
  maxAttempts: 5,
  useJitter: true,
  jitterType: "decorrelated",  // Better for high-volume external calls
};
// Schedule: ~1s, ~2s, ~4s, ~8s, ~16s (max total ≈ 31s)
 
// Aggressive fail-fast for real-time UX
const REALTIME_UX_BACKOFF: Partial<BackoffConfig> = {
  baseDelayMs: 25,
  multiplier: 2,
  maxDelayMs: 200,
  maxAttempts: 2,
  useJitter: true,
  jitterType: "full",  // Maximum spread for UX predictability
};
// Schedule: ~25ms, ~50ms (max total ≈ 75ms)
 
// Very patient for background/batch jobs
const BATCH_JOB_BACKOFF: Partial<BackoffConfig> = {
  baseDelayMs: 2000,
  multiplier: 2,
  maxDelayMs: 300000,  // 5 minutes
  maxAttempts: 8,
  useJitter: true,
  jitterType: "decorrelated",
};
// Schedule: 2s, 4s, 8s, 16s, 32s, 64s, 128s, 256s (capped at 300s)
 
// Database connection retry
const DB_CONNECTION_BACKOFF: Partial<BackoffConfig> = {
  baseDelayMs: 100,
  multiplier: 2,
  maxDelayMs: 10000,
  maxAttempts: 5,
  useJitter: true,
  jitterType: "equal",
};
// Schedule: ~100ms, ~200ms, ~400ms, ~800ms, ~1600ms
 
/**
 * Factory function to get appropriate backoff for context
 */
function getBackoffForContext(context: string): Partial<BackoffConfig> {
  switch (context) {
    case "internal-service":
      return INTERNAL_SERVICE_BACKOFF;
    case "external-api":
      return EXTERNAL_API_BACKOFF;
    case "realtime":
      return REALTIME_UX_BACKOFF;
    case "batch":
      return BATCH_JOB_BACKOFF;
    case "database":
      return DB_CONNECTION_BACKOFF;
    default:
      return INTERNAL_SERVICE_BACKOFF;  // Sensible default
  }
}

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

/**
 * Truncated Exponential Backoff
 * 
 * The delay grows exponentially until hitting the ceiling,
 * then stays constant at the ceiling for all subsequent attempts.
 */
function truncatedExponentialBackoff(
  attempt: number,
  baseMs: number,
  multiplier: number,
  maxMs: number
): number {
  const exponentialDelay = baseMs * Math.pow(multiplier, attempt - 1);
  return Math.min(exponentialDelay, maxMs);
}
 
// With base=100ms, multiplier=2, max=5000ms:
// Attempt 1: 100ms
// Attempt 2: 200ms
// Attempt 3: 400ms
// Attempt 4: 800ms
// Attempt 5: 1600ms
// Attempt 6: 3200ms
// Attempt 7: 5000ms (capped)
// Attempt 8: 5000ms (capped)
// Attempt 9: 5000ms (capped)
// ...
 
/**
 * Capped Total Time Backoff
 * 
 * Instead of capping individual delays, cap the total retry time.
 * Useful when you have a hard deadline.
 */
class TotalTimeBudgetBackoff {
  private readonly baseMs: number;
  private readonly multiplier: number;
  private readonly totalBudgetMs: number;
  private usedTimeMs: number = 0;
  
  constructor(baseMs: number, multiplier: number, totalBudgetMs: number) {
    this.baseMs = baseMs;
    this.multiplier = multiplier;
    this.totalBudgetMs = totalBudgetMs;
  }
  
  getNextDelay(attempt: number): number | null {
    const remainingBudget = this.totalBudgetMs - this.usedTimeMs;
    
    if (remainingBudget <= 0) {
      return null;  // No more budget
    }
    
    const idealDelay = this.baseMs * Math.pow(this.multiplier, attempt - 1);
    const delay = Math.min(idealDelay, remainingBudget);
    
    this.usedTimeMs += delay;
    return delay;
  }
  
  reset(): void {
    this.usedTimeMs = 0;
  }
}
 
// Usage: 5 second total budget
const budgetBackoff = new TotalTimeBudgetBackoff(100, 2, 5000);
 
let attempt = 1;
let delay = budgetBackoff.getNextDelay(attempt);
while (delay !== null) {
  console.log(`Attempt ${attempt}: wait ${delay}ms`);
  attempt++;
  delay = budgetBackoff.getNextDelay(attempt);
}
// Output:
// Attempt 1: wait 100ms (remaining: 4900)
// Attempt 2: wait 200ms (remaining: 4700)
// Attempt 3: wait 400ms (remaining: 4300)
// Attempt 4: wait 800ms (remaining: 3500)
// Attempt 5: wait 1600ms (remaining: 1900)
// Attempt 6: wait 1900ms (remaining: 0)
// (stops - budget exhausted)

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

/**
 * AWS SDK-Style Retry with Full Jitter
 * 
 * AWS recommends: sleep = random_between(0, min(cap, base * 2 ** attempt))
 * 
 * This spreads retries uniformly between 0 and the exponential value,
 * maximizing de-correlation between clients.
 */
class AWSStyleBackoff {
  private readonly baseMs: number;
  private readonly capMs: number;
  
  constructor(baseMs: number = 100, capMs: number = 20000) {
    this.baseMs = baseMs;
    this.capMs = capMs;
  }
  
  getDelay(attempt: number): number {
    const exponentialDelay = this.baseMs * Math.pow(2, attempt);
    const cappedDelay = Math.min(exponentialDelay, this.capMs);
    
    // Full jitter: random between 0 and capped delay
    return Math.random() * cappedDelay;
  }
}
 
/**
 * Google Cloud-Style Retry with Randomization Factor
 * 
 * Uses a randomization factor to add controlled jitter:
 * delay = delay * (1 + randomization_factor * (random * 2 - 1))
 */
class GoogleCloudStyleBackoff {
  private readonly initialDelayMs: number;
  private readonly maxDelayMs: number;
  private readonly multiplier: number;
  private readonly randomizationFactor: number;
  
  constructor(
    initialDelayMs: number = 1000,
    maxDelayMs: number = 32000,
    multiplier: number = 2,
    randomizationFactor: number = 0.5
  ) {
    this.initialDelayMs = initialDelayMs;
    this.maxDelayMs = maxDelayMs;
    this.multiplier = multiplier;
    this.randomizationFactor = randomizationFactor;
  }
  
  getDelay(attempt: number): number {
    const exponentialDelay = this.initialDelayMs * Math.pow(this.multiplier, attempt - 1);
    const cappedDelay = Math.min(exponentialDelay, this.maxDelayMs);
    
    // Apply randomization: ±randomizationFactor
    const randomOffset = this.randomizationFactor * (Math.random() * 2 - 1);
    return cappedDelay * (1 + randomOffset);
  }
}
 
/**
 * Kubernetes-Style Backoff with Forgiveness
 * 
 * Kubernetes uses "rate limiters" that reset after a period
 * of no failures, implementing "forgiveness".
 */
class KubernetesStyleBackoff {
  private readonly baseDelayMs: number;
  private readonly maxDelayMs: number;
  private readonly multiplier: number;
  private readonly forgivenessMs: number;
  
  private currentDelay: number;
  private lastFailureTime: number = 0;
  
  constructor(
    baseDelayMs: number = 5,
    maxDelayMs: number = 1000000,  // 1000 seconds
    multiplier: number = 2,
    forgivenessMs: number = 120000  // 2 minutes
  ) {
    this.baseDelayMs = baseDelayMs;
    this.maxDelayMs = maxDelayMs;
    this.multiplier = multiplier;
    this.forgivenessMs = forgivenessMs;
    this.currentDelay = baseDelayMs;
  }
  
  getNextDelay(): number {
    const now = Date.now();
    
    // If enough time has passed since last failure, reset
    if (now - this.lastFailureTime > this.forgivenessMs) {
      this.currentDelay = this.baseDelayMs;
    }
    
    const delay = this.currentDelay;
    
    // Increase for next time (exponentially, capped)
    this.currentDelay = Math.min(
      this.currentDelay * this.multiplier,
      this.maxDelayMs
    );
    
    this.lastFailureTime = now;
    return delay;
  }
  
  reset(): void {
    this.currentDelay = this.baseDelayMs;
    this.lastFailureTime = 0;
  }
}