Design Rate Limiter

처리율 제한 장치(rate limiter)는 특정 시간 당 처리할 수 있는 요청의 수를 제한하는 장치로, 아래와 같은 이유로 사용된다.

• DoS(Denial of Service) 공격에 의한 자원 고갈 방지

• 과도한 서드 파티 API 과금 방지

• 봇이나 잘못된 이용 패턴으로 인한 서버 과부하 방지

요구 사항

• 처리율을 초과하는 요청을 정확하게 제어

• 낮은 응답 시간 및 적은 메모리 사용

• 분산형 처리율 제한(분산 환경에서도 동작)

• 요청 제한 시 사용자에게 알림

• 높은 결함 감내성(제한 장치에 장애가 발생해도 전체 서비스에 영향을 주지 않음)

설계에는 정답이 존재하지는 않지만, 현재 기술 스택 / 요구 사항 / 목표 / 우선 순위에 따라 다양한 방법으로 설계할 수 있다.

처리율 제한 장치 위치

1. 클라이언트: 쉽게 위변조가 가능해 보안에 취약하여 일반적으로 사용하지 않음

2. 서버: 서버 측에 제한 장치를 두어 처리율을 제한하는 방식

3. 미들웨어: API 서버로 가는 요청을 통제하는 미들웨어 추가

4. API 게이트웨이: SSL 종단 / 사용자 인증 / IP 허용 목록 등을 관리하기 위해 이미 API 게이트웨이를 사용 중이라면 여기에 추가

처리율 제한 알고리즘

처리율 제한 알고리즘은 이미 여러 가지가 존재하며, 각기 다른 장단점이 존재한다.

1. 토큰 버킷 알고리즘

처리율 제한에 폭 넓게 이용되고 있으며, 간단하고 보편적으로 사용하고 있다.(아마존, 스트라이프 등)

• 지정된 용량을 가진 토큰 버킷 존재

• 사전 설정된 양의 토큰이 주기적으로 채워짐

• 각 요청을 처리할 때마다 하나의 토큰 사용(토큰이 없으면 요청 처리 X)

• 통상적으로 API 엔드포인트마다 별도의 버킷을 두어 처리율 제한을 적용

• IP 주소별로 처리율 제한을 적용해야 한다면 IP 주소별로 별도의 버킷을 둠

구현하기 쉽고, 메모리 사용 측면에서 효율적이면서 단기간 집중되는 트래픽 처리도 가능한 장점이 있지만, 버킷 크기와 토큰 공급률이라는 두 가지 인수를 적절하게 튜닝하는 것이 중요하다.

2. 누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정 되어 있는 점이 다르며, 보통 FIFO 큐로 구현한다.

• 요청이 도착하면 큐가 꽉 차 있는지 확인

• 빈자리가 있는 경우엔 큐에 요청을 추가(빈자리가 없으면 요청 처리 X)

• 지정된 시간마다 큐에서 요청을 꺼내어 처리

큐의 크기가 제한되어 있어 메모리 사용 측면에서 효율적이고, 고정된 처리율로 안정적 출력에 적합하다는 장점이 있지만, 단기간 트래픽이 몰리는 경우 큐에 요청이 쌓여 처리하지 못하는 요청이 많아질 수 있다. 마찬가지로 버킷 크기(큐 사이즈)와 누출 속도(처리율)를 적절하게 튜닝하는 것이 중요하다.

3. 고정 윈도 카운터 알고리즘

특정 시간 동안 처리할 수 있는 요청의 수를 제한하는 방식으로, 동작 방식은 다음과 같다.

• 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 둠

• 요청이 올 때마다 카운터의 값을 1씩 증가

• 해당 카운터의 값이 설정된 임계치를 초과하면 요청 처리 X

• 새 윈도가 시작되면 카운터를 초기화

메모리 효율이 좋고, 설계하기 쉽고, 특정한 트래픽 패턴을 처리하기에 적합하다는 장점이 있지만, 윈도 경계 부근에서 많은 트래픽이 몰리는 경우, 기대했던 처리 한도보다 많은 양의 요청을 처리하게 될 수 있다.

4. 이동 윈도 로깅 알고리즘

고정 윈도 카운터 알고리즘에는 윈도 경계 부근에서 트래픽이 몰리는 문제가 있어, 이를 해결하기 위해 이동 윈도 로깅 알고리즘을 사용할 수 있다.

• 요청의 타임스탬프를 로그에 추가(보통 레디스의 Sorted Set 같은 캐시에 보관)

• 새 요청이 오면 현재 윈도의 시작 지점보다 오래된 타임스탬프 제거(ex. 시간 단위 1분 / 새 요청 시각 1:01:40 인 경우 1:00:40 이전 로그 제거)

• 로그의 크기가 설정된 수치를 초과하면 요청 처리 X(처리하지 않지만 로그에는 추가)

허용되는 요청의 개수는 시스템의 처리율 한도를 항상 넘지 않게 되는 장점이 있지만, 거부된 요청의 타임스탬프도 보관하기 때문에 많은 메모리를 사용하게 될 수 있다.

5. 이동 윈도 카운터 알고리즘

고정 윈도 카운터 알고리즘과 이동 윈도 카운터 알고리즘을 결합한 것으로, 동작 방식은 다음과 같다.

• 현재 윈도 요청 수 + 직전 윈도우 요청 수 * 이동 윈도와 직전 윈도우 겹치는 부분의 비율

• ex. 현재 윈도 요청 수 50 / 직전 윈도 요청 수 150 / 겹치는 부분 비율 50% -> 50 + 150 * 0.5 = 125

이전 시간대를 고려하여 현재 윈도 상태를 계산하므로 단기간 집중 트래픽도 잘 대응하고, 메모리 사용 측면에서 효율적이다. 하지만 직전 윈도 요청을 균등하게 분포되어 있다고 가정하기 때문에 실제 상태와 맞지 않게 허용되거나 거부되는 요청이 발생할 수 있다.(클라우드플레어에서 실험에 따르면 0.003%)

카운터 보관 장소

데이터베이스는 디스크 접근 속도 문제로 사용되지 않고, 접근 속도가 빠르고, 시간 기반 만료 정책을 지원하기 때문에 캐시 저장소를 사용하는 것이 일반적이다. 실제로 레디스를 처리율 제한 장치를 구현할 때 자주 사용되는데, 두 가지 명령어로 처리율 제한 장치를 구현할 수 있다.

• INCR: 메모리에 저장된 카운터 값을 1만큼 증가

• EXPIRE: 카운터에 타임아웃 값 설정

상세 설계

처리율 제한 규칙

처리율 제한 규칙은 보통 설정 파일 형태로 디스크에 보관 되어, 캐시에 로드되어 사용된다. 아래 예시는 마케팅 세미지의 최대치를 5로 설정한 규칙이다.

domain: messaging
descriptors:
  - key: message_type
    Value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

한도 초과된 요청 처리 방법

한도 제한에 걸리게 되면 API는 보통 HTTP 429 Too Many Requests 상태 코드를 클라이언트에게 반환하게 된다. 추가적으로 HTTP 헤더에 한도 제한에 대한 정보를 포함하여 클라이언트가 이를 이해하고 적절히 대응할 수 있도록 할 수 있다.

• X-RateLimit-Limit: 매 윈도 전송할 수 있는 요청의 수

• X-RateLimit-Remaining: 윈도 내에 남은 요청의 수

• X-RateLimit-Retry-After: 다음 요청까지 대기해야 하는 시간(초)

처리가 제한된 요청은 정책에 따라서는 요청된 처리를 무시하거나, 나중에 처리하기 위해 큐에 보관할 수도 있다.

요청 처리 프로세스

1. 클라이언트 서버에 요청하게 되면, 해당 요청은 처리율 제한 미들웨어에 도착

2. 캐시된 규칙과 카운터 및 마지막 요청의 타임스탬프 조회

3. 처리 알고리즘에 따라 처리

   • 제한에 걸리지 않은 경우: API 서버로 요청 전달

   • 제한에 걸린 경우: 클라이언트에 에러 응답(429 Too Many Requests), 버려진 요청은 정책에 따라 무시하거나 메시지 큐에 보관

분산 환경에서의 처리율 제한

분산 환경에서는 처리율 제한을 위해 여러 서버와 병렬 스레드를 지원하기 위해 아래 두 가지 문제를 고려해야 한다.

1. 경쟁조건

   • 여러 서버가 동시에 동일한 요청을 처리하려고 할 때 발생하는 문제

   • 해결 방법: 루아 스크립트 혹은 레디스 정렬 집합 자료구조 사용

2. 동기화

   • 처리율 제한 장치가 여러 대 두게 됐을 때, 각 제한 장치의 카운터가 동기화되어야 하는 문제

   • 해결 방법: 고정 세션을 활용해 항상 동일한 제한 장치로 요청을 보내거나, 레디스 같은 중앙 집중형 저장소 사용

추가적인 성능 최적화 방법

• 다양한 계층에서의 처리율 제한

  • 애플리케이션 계층뿐만 아니라, 네트워크 계층인 Iptables를 사용하여 IP 주소에 처리율 제한할 수 있다.

• 클라이언트 측에서 처리

  • 캐시를 사용해 API 호출 횟수 감소

  • 처리율 제한의 임계치를 고려해, 단기간 많은 요청을 보내지 않도록 클라이언트 측에서 제한

  • 재시도 로직에서 충분한 백오프 시간을 둠

참고자료

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초