지수 백오프는 왜 지수인가

들어가며

이 문제는 어디서 나타나는가

• API rate limit (HTTP 429): 서버 초당 1,000 req 제한인데 2,000개가 들어옴. 앞 1,000개는 성공, 뒤 1,000개는 429. 실패한 1,000개가 동시에 백오프하고 동시에 재시도. 다시 429.
• DB 커넥션 풀 고갈: 풀 사이즈 100, 트래픽 스파이크로 200개 요청. 앞 100개는 커넥션 잡고 성공, 뒤 100개는 타임아웃. 풀이 회복 중에 100개가 동시 재시도하면 또 풀이 막힘.
• 낙관적 동시성 제어 (OCC): 같은 레코드를 여러 클라이언트가 동시에 업데이트. UPDATE ... WHERE version = ? 같은 버전 체크가 있어서 하나만 성공하고 나머지는 충돌. 실패한 요청들이 동시 재시도. 또 하나만 성공.

naive한 방법들

즉시 재시도

while (true) {
  try {
    await call();
    break;
  } catch {
    // 즉시 재시도
  }
}

고정 시간 대기 후 재시도

while (true) {
  try {
    await call();
    break;
  } catch {
    await sleep(1000);
  }
}

선형 증가 후 재시도

let attempt = 0;
while (true) {
  try {
    await call();
    break;
  } catch {
    attempt += 1;
    await sleep(1000 * attempt);
  }
}

무작위 대기 후 재시도

const windowMs = 1000; // 분산할 시간 범위
while (true) {
  try {
    await call();
    break;
  } catch {
    await sleep(Math.random() * windowMs);
  }
}

분산에 필요한 공간은 $N^2$만큼 크다

• 3개 → 3쌍
• 4개 → 6쌍
• 10개 → 45쌍
• 100개 → 4,950쌍

윈도우를 키우는 두 가지 방식

선형 증가

지수 증가

그러면 너무 오래 기다리는 거 아닌가?

두 장점이 함께 작동한다

• 빠르게 분산되어야 서버가 회복할 시간을 얻음
• 누적 시간이 유한해야 클라이언트가 포기하지 않을 만큼만 기다림

base는 꼭 2여야 할까?

• 비트 시프트(<< 1)로 단순한 구현
• 너무 빠르지도 너무 느리지도 않은 속도
• 1976년 이더넷 논문(Metcalfe & Boggs)에서 시작된 binary exponential backoff의 관성

지수 백오프의 또 다른 핵심: 지터(jitter)

• 1차 재시도: 모두 $\text{base} \times 2$초 후 깨어남 → 다시 동시 충돌
• 2차 재시도: 모두 $\text{base} \times 4$초 후 깨어남 → 다시 동시 충돌
• 3차 재시도: 모두 $\text{base} \times 8$초 후 깨어남 → 다시 동시 충돌

// 결정론적: 윈도우만 커지고 분산은 0
const delay = base * Math.pow(2, n);

// Full Jitter: 0과 base × 2^n 사이에서 무작위 선택
const delay = Math.random() * base * Math.pow(2, n);

• 무작위 선택: 클라이언트를 실제로 서로 다른 시점으로 분산시킴
• 윈도우의 지수 증가: 분산할 공간이 충돌 횟수에 맞춰 적절한 속도로 자라게 함

실전 코드

async function retryWithBackoff<T>(
  fn: () => Promise<T>,
  options: {
    maxRetries: number;
    baseMs: number;
    capMs: number;
  },
): Promise<T> {
  const { maxRetries, baseMs, capMs } = options;

  for (let attempt = 0; attempt <= maxRetries; attempt++) {
    try {
      return await fn();
    } catch (error) {
      if (attempt === maxRetries) throw error;

      // 지수 증가에 cap 적용
      const expDelay = Math.min(baseMs * 2 ** attempt, capMs);

      // Full Jitter
      const delay = Math.random() * expDelay;

      await new Promise((res) => setTimeout(res, delay));
    }
  }
  throw new Error("unreachable");
}

• cap (capMs): 지수는 빠르게 커지므로 상한이 없으면 곧 비현실적인 대기 시간이 됨
• maxRetries: 무한 재시도는 의존 시스템이 영구 장애일 때 클라이언트도 함께 다운시킴
• 재시도 가능한 에러만 재시도: 4xx 같은 클라이언트 에러는 재시도해도 동일하게 실패함. 5xx, 429, 네트워크 타임아웃처럼 다시 시도하면 성공할 가능성이 있는 에러만 재시도해야 함

백오프가 만능은 아니다

The only way to deal with long-term overload is to reduce load.

(번역) 장기 과부하를 해결하는 유일한 방법은 부하를 줄이는 것이다.

• 지수 백오프: 재시도 간격 분산
• 지터: 동기화 깨기
• cap과 max retries: 무한 대기/재시도 방지
• circuit breaker: 의존 시스템에 장애가 발생했을 때 재시도 자체를 멈춤
• 토큰 버킷: 재시도 폭발 제한

참고

• Marc Brooker, Exponential Backoff And Jitter, AWS Architecture Blog, 2015 (2023 업데이트).
• Marc Brooker, Timeouts, retries, and backoff with jitter, Amazon Builders' Library.
• Marc Brooker, What is Backoff For?, 2022.
• Exponential backoff - Wikipedia.
• R. M. Metcalfe and D. R. Boggs, Ethernet: Distributed packet switching for local computer networks, Communications of the ACM, Vol. 19, No. 7, 1976. (지수 백오프의 기원)