• 처리율 제한 장치(Rate Limiter)란?
  • 처리율 제한 장치를 도입해야 하는 이유
• 1. 요구사항 파악
  • 1.1. 요구 사항
• 2. 처리율 제한 장치는 어디에 둘 것인가?
  • 2.1. 클라이언트 측에 두는 방안
  • 2.2. 서버 측에 두는 방안
  • 2.3. 미들웨어 또는 API 게이트웨이에 두는 방안
  • 2.4. 아키텍처 위치 선정을 위한 가이드라인
• 3. 처리율 제한 알고리즘
  • 3.1. 토큰 버킷(Token Bucket) 알고리즘
    • 💡IP는 수억 개가 있고 어떤 게 들어올 지 모르는데, 그걸 다 어떻게 버킷으로 만드나?
    • 💡시스템 전체 제한(초당 10,000개)와 유저별 기능 제한(하루 포스팅 1회, 친구 추가 100회 등)을 동시에 구현하려면 버킷을 어떻게 구성해야 할까?
    • 💡토큰 버킷이 ‘메모리 사용 측면에서 효율적’인 이유는 뭘까?
  • 3.2. 누출 버킷(Leaky Bucket) 알고리즘
    • 💡누출 버킷은 큐에 요청이 쌓이면 바로 처리하는 것이 아니라 지정된 시간마다 한 번에 모아서 처리하는 것인가?
    • 💡단시간에 트래픽이 몰리면 최신 요청들이 버려지는 것은 토큰 버킷도 동일한 것 아닌가?
  • 3.3. 고정 윈도 카운터(Fixed Window Counter) 알고리즘
    • 💡윈도가 닫히는 시점에 카운터를 초기화하는 방식이 특정한 트래픽 패턴 처리에 적합한 이유는?
  • 3.4. 이동 윈도 로깅(Sliding Window Logging) 알고리즘
    • 💡’요청이 거부되어도 타임스탬프는 로그에 남는다’의 의미는 이 거부된 요청들이 나중에 처리되는 걸까?
  • 3.5. 이동 윈도 카운터(Sliding Window Counter) 알고리즘
    • 💡’이전 시간대의 평균 처리율에 따라 상태를 계산하는 것’과 ‘짧은 시간에 몰리는 트래픽(버스트)에 잘 대응하는 것’은 무슨 상관일까?
• 4. 개략적 아키텍처
• 5. 처리율 제한 장치 상세 설계
  • 5.1. 처리율 제한 규칙
  • 5.2. 처리율 한도 초과 트래픽의 처리
    • 5.2.1. HTTP 응답 헤더 설계: 클라이언트와의 소통
  • 5.3. 종합 상세 설계 및 데이터 플로우
  • 5.4. 분산 환경에서의 처리율 제한 장치
    • 5.4.1. 경쟁 조건(Race Condition)
    • 5.4.2. 동기화 이슈
    • 5.4.3. 성능 최적화
    • 5.4.4. 모니터링
• 6. 마무리
• 참고 사이트 & 함께 보면 좋은 사이트

처리율 제한 장치(Rate Limiter)란?

처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 송신율(Rate)를 제어하기 위한 인프라 및 애플리케이션 보안 장치이다.

시스템이 사전에 정의한 임계치(Threshold)를 넘어서는 과도한 HTTP 요청을 전면에서 차단하거나 지연시켜 시스템 전체의 가용성과 안정성을 보장하는 역할을 한다.

• 사용자는 초당 2회 이상 글을 올릴 수 없음
• 동일한 IP 주소로는 하루에 10개 이상 계정 생성 불가

처리율 제한 장치를 도입해야 하는 이유

대규모 시스템 아키텍처에서 처리율 제한 장치는 단순히 ‘요청을 막는 것’ 이상의 기술적, 비즈니스적 이점을 제공한다.

• DoS(Denial of Service, 서비스 거부 공격)/DDos(Distributed Denial of Service, 분산 서비스 거부 공격) 공격에 의한 자원 고갈 방지
  • 가장 본질적인 목표이다.
  • 악의적인 Bot이나 해커가 서버의 CPU, 메모리, 네트워크 대역폭을 고갈시키기 위해 무차별적인 요청을 할 때, 이를 유저 인입 단계에서 걸러낸다.
  • 실제 Google Docs API의 경우, 내부 인프라 자원 보호를 위해 사용자당 분당 300회의 Read 요청만 허용하도록 처리율 제한을 적용하고 있다.
• 인프라 비용 절감
  • 처리율 제한 장치를 두면 비정상적인 트래픽을 선제적으로 걷어낼 수 있어 불필요한 서버 Scale-out을 방지한다.
  • Third-party API 과금 방어:
    • 신용 확인, 본인 인증 등 호출 횟수당 과금되는 외부 서비스를 연동할 때 필수적이다.
    • 처리율 제한이 없다면 버그나 공격으로 인해 순식간에 비용이 증가할 수 있다.
• 서버 과부하 차단 및 가용성 확보
  • 트래픽 스파이크가 발생하거나 사용자의 잘못된 패턴으로 유발된 트래픽을 통제한다.
  • 이를 통해 핵심 비즈니스 로직을 처리하는 API 서버가 완전히 다운되는 상황을 막고, 우선순위가 높은 정상 유저의 요청에 자원을 할당한다.

1. 요구사항 파악

• 제한 장치 종류
  • Q: 어떤 종류의 처리율 제한 장치를 설계해야 하는가? 클라이언트 측인가, 서버 측인가?
  • A: 서버측 API를 보호하기 위한 처리율 제한 장치를 설계해야 한다.
• 제한 기준
  • Q: 어떤 기준을 사용하여 API 호출을 제어해야 하는가? IP 주소인가? 사용자 ID 인가?
  • A: IP, 사용자 ID 등 다양한 형태의 제어 규칙을 유연하게 정의할 수 있는 시스템이어야 한다.
• 시스템 규모
  • Q: 시스템 규모는 어느 정도인가? 스타트업 수준인가, 대기업 제품 수준인가?
  • A: 대규모 요청을 안정적으로 처리할 수 있는 대기업 급 인프라를 타깃으로 한다.
• 인프라환경
  • Q: 분산 환경에서 동작해야 하는가?
  • A: 그렇다. 여러 서버와 데이터 센터에 분산된 환경을 고려해야 한다.
• 아키텍처 형태
  • Q: 이 장치는 독립된 서비스인가, 애플리케이션 코드 내부에 포함되는가?
  • A: 설계 유연성과 유지보수성을 위해 애플리케이션 전면에서 트래픽을 제어하는 독립된 미들웨어(API 게이트웨이 형태)로 한다.
• 사용자 알림
  • Q: 요청이 처리율 제한 장치에 의해 걸러진 경우, 사용자에게 그 사실을 알려야 하는가?
  • A: 그렇다. 요청이 제한되었음을 HTTP 상태 코드와 헤더를 통해 명확하게 알려야 한다.

1.1. 요구 사항

위의 요구사항 파악을 바탕으로 도출된 기술적 요구사항들이다.
이 요구사항들은 본 설계 전체를 관통하는 핵심 KPI(Key Performance Indicator, 핵심 성과 지표)가 된다.

• 정확한 트래픽 제한
  • 설정된 처리율 임계치를 초과하는 요청은 한 치의 오차도 없이 정확하게 차단해야 함
• 낮은 지연시간
  • 처리율 제한 장치는 API 서버 바로 전면에 위치하므로, 유저의 HTTP 요청 처리에 주는 영향(오버헤드)이 최소화되어야 함
• 메모리 최적화
  • 대규모 유저를 커버해야 하므로, 제한 장치가 사용하는 메모리 양이 가능한 적어야 함
• 분산형 처리율 제한
  • 여러 대의 제한 장치 서버와 프로세스가 존재하더라도 카운터 데이터 등을 실시간으로 공유하고 동기화할 수 있어야 함
• 높은 결함 감내성(Fault Tolerance)
  • 처리율 제한 장치 자체에 장애가 생기더라도, 전체 백엔드 시스템이 마비되어서는 안됨

2. 처리율 제한 장치는 어디에 둘 것인가?

2.1. 클라이언트 측에 두는 방안

실무에서는 거의 채택되지 않는 방식이다.

서버 자원을 전혀 쓰지 않으므로 구현 비용이 낮지만, 클라이언트 측 요청은 위변조가 너무 쉽다.
위변조 클라이언트 패킷이나 악의적인 해커의 역공학(Reverse Engineering) 공격에 무방비로 노출되므로, 보안 목적의 처리율 제한에는 전혀 적합하지 않다.

2.2. 서버 측에 두는 방안

처리율 제한 로직을 API 백엔드 서버 내부에 직접 구현하는 방식이다.

• 장점
  • 현재 애플리케이션의 비즈니스 로직 및 사용하는 기술 스택 안에서 세밀하고 정교한 제어가 가능하다.
  • 데이터베이스나 내부 캐시와의 연동이 직관적이다.
• 단점
  • 처리율 제한을 위한 연산이 API 서버의 CPU와 메모리 자원을 사용하게 된다.

2.3. 미들웨어 또는 API 게이트웨이에 두는 방안

API 서버 전면에 독립적인 미들웨어를 구축하여 API 서버로 향하는 모든 트래픽을 통제하는 방식이다.

대규모 시스템 아키텍처에서는 이 미들웨어 기능을 API 게이트웨이 컴포넌트에 통합하여 처리하는 것이 일반적이다.
API 게이트웨이는 처리율 제한 뿐만 아니라 아래와 같은 범용적인 기능을 지원한다.

• SSL 종단(Termination)
• 사용자 인증 및 인가(Authentication/Authorization)
• IP 허용 목록(Whitelist) 및 차단 목록 관리

2.4. 아키텍처 위치 선정을 위한 가이드라인

처리율 제한 장치를 어디에 둘지에 대한 절대적인 정답은 없다. 상황과 인프라 구조에 따라 유연하게 선택해야 한다.

• 현재 엔지니어링 리소스(인원)가 부족한가?
  • 직접 처리율 제한 미들웨어를 개발하는 데는 시간이 많이 소요된다.
  • 인력이 부족하다면 클라우드 사업자(AWs, GCP 등)가 제공하는 상용 API 게이트웨이를 도입하는 것이 바람직하다.
• 회사의 아키텍처가 MSA인가?
  • 이미 사용자 인증, 로깅 등을 위해 전면에 API 게이트웨이를 두고 있다면, 처리율 제한 기능 역시 게이트웨이에 포함시키는 것이 관리 측면에서 유리하다.
• 직접 알고리즘을 완벽하게 커스텀해야 하는가?
  • 상용 게이트웨이를 쓰면 구현 속도는 빠르지만 선택할 수 있는 알고리즘이나 유연성이 다소 제한된다.
  • 비즈니스 특성 상 매우 독특한 처리율 제한 알고리즘이 필요하다면 서버 측이나 자체 미들웨어로 구현해야 한다.

3. 처리율 제한 알고리즘

처리율 제한을 실현하기 위한 알고리즘은 다양하다.
각 알고리즘은 작동 방식과 자원 사용량, 트래픽 패턴에 따른 대응 능력이 다르다.

업계에서 많이 사용되는 5개 알고리즘을 간략히 살펴보자.

3.1. 토큰 버킷(Token Bucket) 알고리즘

기업들이 가장 보편적으로 채택하고 있는 알고리즘이다.
AWS와 스트라이프(Stripe) 등이 API 요청 통제(Throttling)를 위해 이 알고리즘을 사용한다.

토큰 버킷은 지정된 용량을 가진 가상의 컨테이너이다.
이 버킷에는 사전에 설정된 공급률(Refill Rate)에 따라 주기적으로 토큰이 채워지며, 버킷이 가득 차면 더 이상의 토큰은 채워지지 않고 버려진다.

아래 그림은 용량이 4인 버킷이고, 토큰 공급기(refiler)는 이 버킷에 매초 2개의 토큰을 추가한다.
버킷이 가득 차면 추가로 공급된 토큰은 버려진다.

각 HTTP 요청은 처리될 때마다 하나의 토큰을 사용한다. 요청이 도착하면 버킷 내부를 확인한다.

• 토큰이 충분한 경우: 버킷에서 토큰을 하나 꺼낸 후 요청을 API 서버로 전달
• 토큰이 없는 경우: 해당 요청은 즉시 버려지거나 거부됨

아래 그림은 크기가 4이고, 공급률이 분당 4인 토큰 버킷의 실제 흐름이다.

토큰 버킷 알고리즘은 버킷 크기(최대 토큰 개수)와 토큰 공급률(초당 공급 개수)이라는 두 개의 인자를 받아 튜닝한다.

‘버킷을 총 몇 개나 생성하고 어떻게 관리해야 하는가?’는 서비스의 ‘공급 제한 규칙(비즈니스 정책)’에 따라 달라진다.

• API 엔드포인트 및 사용자별 독립 버킷(가장 보편적)
  • 통상적으로 유저가 행하는 액션의 종류(API 엔드포인트)마다 별도의 버킷을 할당한다.
  • 예) 사용자마다 하루에 단 1번만 포스팅 가능, 친구 추가는 하루에 최대 100명만 가능, 좋아요 버튼은 분당 5번까지만 가능
  • 이 경우 시스템은 사용자 한 명당 총 3개의 독립된 버킷을 생성하고 관리해야 한다. 서비스에 가입한 유저가 100만 명이라면, 이론적으로 총 300만 개의 버킷이 동적으로 움직이게 된다.
• IP 주소별 처리율 제한
  • 특정 IP에서 DDoS 공격을 감행하거나 비정상적인 스크래핑을 시도할 때 이를 IP 기준으로 차단하는 방식이다.
  • 이 경우 각 IP 주소마다 버킷을 하나씩 할당해야 한다.
• 시스템 전체 기준 공유 버킷(Global Shared Bucket)
  • 보안이나 특정 유저의 어뷰징 방지가 아니라, 백엔드 인프라 전체가 다운되지 않도록 방어막을 칠 때 사용하는 방식이다.
  • 어떤 유저든, 어떤 IP든 상관없이 모든 HTTP 요청이 단 하나의 대형 글로벌 버킷을 공유하도록 설계한다.
  • 이 공유 버킷의 토큰이 바닥나면 모든 요청을 응답을 거부한다.

공급 제한 규칙별 버킷 예시

• 장점
  • 구현이 직관적이고 메모리 효율이 극대화된다.
  • 버킷에 토큰이 남아있기만 하다면 단시간에 집중되는 트래픽 버스트도 유연하게 수용할 수 있다.
• 단점
  • 버킷 크기와 공급률이라는 두 파라미터를 유기적으로 결합하여 적절하게 튜닝하는 과정이 까다롭다.

💡IP는 수억 개가 있고 어떤 게 들어올 지 모르는데, 그걸 다 어떻게 버킷으로 만드나?

전 세계 모든 IP의 버킷을 서버 메모리에 미리 만들어두는 것이 아니라, 레디스와 같은 인메모리 Key-Value 데이터베이스의 동적 생성(On-Demand)와 TTL 메커니즘을 활용하여 이 문제를 우아하게 해결한다.

• 동적 생성
  • 1:00:00 에 111.111.111.111 이라는 IP 에서 첫 요청이 들어오면, 처리율 제한 미들웨어는 레디스에 ratelimit:111.111.111.111 이라는 키가 있는지 조회
• 초기화
  • 키가 없다면 그 순간 레디스에 해당 키를 새로 생성하고, 최초 설정된 토큰 개수(예: 10개)와 함께 TTL을 1분이나 1일 등으로 짧게 설정
• 자동 삭제
  • 만일 해당 IP가 공격을 멈추고 한동안 요청을 보내지 않아 설정된 TTL 시간이 지나면, 레디스는 해당 IP의 버킷 데이터를 자동으로 소멸시킴

결과적으로 시스템은 현재 실시간으로 요청을 보내고 있는 Active IP의 버킷만 캐시에 유지하므로 대규모 환경에서도 메모리를 소량만 사용하며 방어할 수 있다.

💡시스템 전체 제한(초당 10,000개)와 유저별 기능 제한(하루 포스팅 1회, 친구 추가 100회 등)을 동시에 구현하려면 버킷을 어떻게 구성해야 할까?

이를 다중 레이어 처리율 제한(Multi-tier Rate Limiting) 구조라고 한다.
단 하나의 버킷으로 해결하는 것이 아니라 하나의 요청이 통과해야 하는 버킷 체인을 만든다.

• 1단계: 글로벌 버킷(전체 트래픽이 공유하는 크기 10,000 버킷)
• 2단계: 유저 ID별 버킷(특정 유저 전용 버킷)
• 3단계: 유저 ID + 액션 종류별 버킷(user124:post, user123:add_friend 등)

클라이언트 요청은 이 모든 버킷에서 각각 토큰을 1개씩 확보해야만 최종적으로 API 서버에 도달할 수 있다.
중간에 하나의 버킷이라도 토큰이 고갈되면 HTTP 429 에러가 반환된다.

💡토큰 버킷이 ‘메모리 사용 측면에서 효율적’인 이유는 뭘까?

뒤에 나올 ‘이동 윈도 로깅’ 알고리즘은 유저의 모든 요청 타임스탬프를 배열이나 리스트로 다 저장해야 한다.
반면 토큰 버킷은 레디스에 유저/IP 별로 현재 남은 토큰 개수(Integer)와 마지막으로 토큰을 충전한 시간(Timestamp), 딱 두 개의 데이터만 저장하면 된다.
수백만 명의 유저가 인입되어도 Key 당 수십 byte면 충분하므로 메모리 효율성이 압도적이다.

3.2. 누출 버킷(Leaky Bucket) 알고리즘

누출 버킷 알고리즘은 토큰 버킷과 유사해보이지만, 트래픽의 출력 처리율이 고정되어 있다는 점이 다르다.
주로 FIFO 큐를 이용하여 구현한다.

글로벌 이커머스 플랫폼인 쇼피파이(Shopify)가 API의 안정적인 처리를 위해 이 누출 버킷 알고리즘을 사용하고 있다.

누출 버킷 알고리즘은 시스템 튜닝을 위해 아래 2개의 인자를 사용한다.

• 버킷 크기
  • 큐의 사이즈와 같은 값이다.
  • 큐에는 서버가 처리하기 전까지 대기해야 할 항목(요청)들이 보관된다.
• 처리율(Outflow Rate)
  • 지정된 시간당 몇 개의 항목을 처리할 지 지정하는 값이며, 보통 초 단위(포함된 요청 수/sec)로 표현한다.

<동작 원리>

• 요청이 도착하면 큐가 가득 차 있는지 확인한다. 빈자리가 있다면 큐에 요청을 추가한다.
• 큐가 가득 차 있다면 새로운 요청은 즉시 버린다.
• 지정된 시간 주기마다 큐에서 일정한 개수의 요청을 꺼내어 백엔드로 전달하고 처리한다.

• 장점
  • 큐의 크기가 고정되어 있어 메모리가 안전하게 관리되며, 백엔드 서버가 감당할 수 있는 일정한 처리 속도(고정 출력율)를 강제할 수 있어 로드 밸런싱과 인프라 안정성에 매우 유리하다.
• 단점
  • 단시간에 많은 트래픽이 몰릴 경우 큐에 오래된 요청들이 쌓여 응답 지연이 발생하고, 제때 처리되지 못한 최신 요청들이 무조건 드롭되는 현상이 발생한다.
  • 또한, 토큰 버킷과 마찬가지고 두 개 인자를 올바르게 튜닝하기 어렵다.

💡누출 버킷은 큐에 요청이 쌓이면 바로 처리하는 것이 아니라 지정된 시간마다 한 번에 모아서 처리하는 것인가?

‘한 번에 모아서 배치 처리한다’라기 보다는, 출력의 속도를 일정하게 흐르도록 제어하는 것이다.

예를 들어 처리율이 초당 10개로 고정되어 있다면 백그라운드 프로세스가 100ms마다 큐에서 정확히 1개씩 요청을 꺼내 처리한다.
0.001초 사이에 100개의 요청이 한꺼번에 몰려와 큐에 쌓이더라도, 시스템으로 전달되는 요청은 정확히 100ms에 1개씩 고른 간격으로 ‘누출(Leak)’된다.

💡단시간에 트래픽이 몰리면 최신 요청들이 버려지는 것은 토큰 버킷도 동일한 것 아닌가?

핵심 차이는 이미 인입된 트래픽이 시스템에 주는 지연시간과 버려지는 시점에 있다.

• 토큰 버킷
  • 순간적으로 100개의 요청이 몰려도 토큰이 100개 있으면 지연 시간 없이 100개 모두 즉시 서버로 전달된다.
  • 토큰이 다 떨어지는 순간 그 이후에 들어오는 최신 요청이 바로 버려진다.
• 누출 버킷
  • 100개의 요청이 몰리면 일단 큐에 순서대로 쌓인다.
  • 백엔드는 이를 고정 속도(예: 100ms에 2개)로 처리하므로, 큐의 맨 뒤에 있는 최신 요청은 앞의 요청들이 다 빠질 때까지 큐 안에서 대기해야 하므로 엄청난 응답 지연을 겪게 된다.
  • 그러다 큐의 용량(버킷 크기)을 초과하는 순간 들어오는 최신 요청이 버려진다.
  • 즉, 누출 버킷은 서버를 안정적인 속도로 보호하는 대신 유저 요청의 가용성과 응답 속도를 일부 희생한다.

3.3. 고정 윈도 카운터(Fixed Window Counter) 알고리즘

타임라인을 고정된 시간 간격(윈도)로 분할하고, 각 윈도마다 독립된 카운터를 배치하는 방식이다.

• 요청이 접수될 때마다 현재 시간대가 속한 윈도의 카운터를 1씩 증가시킨다.
• 카운터 값이 한계치에 도달하면 해당 윈도가 닫히고 다음 시간대 윈도가 열릴 때까지 모든 요청을 거부한다.

아래 그림의 타임라인의 시간 단위는 2초이다.
시스템은 초당 3개까지만 요청을 허용하며, 매초 열리는 윈도에 3개 이상의 요청이 밀려오면 초과분(회색 박스)은 버려진다.

• 장점
  • 메모리 효율이 좋다.
  • 직관적이고 구현이 매우 간단하다.
  • 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 패턴을 처리하기에 적합하다.
• 단점
  • 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 된다.

💡윈도가 닫히는 시점에 카운터를 초기화하는 방식이 특정한 트래픽 패턴 처리에 적합한 이유는?

비즈니스 요구사항 중에 특정 주기마다 명확하게 리셋되는 할당량(Quota) 정책이 있는 트래픽 패턴에 완벽하게 들어맞기 때문이다.
예1) 모든 유저는 매달 1일 자정에 무료 API 호출 크레딧 100회가 새로 충전된다.
예2) 보안을 위해 비밀번호 찾기 이메일은 매 정각마다 최대 5번가지만 발송 가능하다.

이러한 비즈니스 패턴은 정해진 시각에 카운터가 0으로 딱 떨어져야 정상이므로, 레디스의 EXPIRE 명령어로 특정 시간에 카운터를 만료시키는 고정 윈도 방식이 가장 단순하고 부하가 적은 최적의 아키텍처 솔루션이 된다.

이 알고리즘은 경계면 트래픽 집중 문제가 있다.

구체적인 수치로 살펴보자.
아래 그림은 분당 최대 5개의 요청만을 허용하는 시스템이며, 카운터는 매분마다 초기화된다.

• 2:00:30~2:01:00 사이에 5개의 요청이 들어왔고, 윈도가 바뀐 직후인 2:01:00~2:01:30 사이에 또 5개의 요청이 들어왔다.
• 각 고정 윈도 단위(2:00:00~2:01:00, 2:01:00~2:02:00)로 보면 각각 5개씩만 처리했으므로 제한 장치는 요청을 모두 통과시킨다.
• 하지만 윈도 위치를 조금 이동해서 두 윈도의 경계면인 2:00:30 ~ 2:01:30 까지의 1분 동안을 살펴보면, 시스템이 처리한 요청은 10개이다.
  • 이는 허용 한도의 2배를 처리하게 되어 백엔드 서버가 과부하로 다운될 수 있는 약점이 될 수 있다.

3.4. 이동 윈도 로깅(Sliding Window Logging) 알고리즘

고정 윈도 카운터의 ‘경계면 트래픽 집중 문제’를 원천적으로 해결하기 위해 등장한 알고리즘이다.

이 알고리즘은 단순히 숫자를 올리는 카운터 대신 요청이 들어온 개별 ‘타임스탬프’를 로그로 기록하고 추적한다.
일반적으로 레디스의 정렬 집합(Sorted Set)을 활용한다.

• 새로운 요청이 들어오면 현재 시간 기준으로 ‘윈도 시작점보다 오래된 만료 타임스탬프’를 로그에서 완전히 제거한다.
• 현재 요청의 타임스탬프를 로그에 추가한다.
• 로그의 전체 크기(요청 횟수)를 확인하여 허용 한도 이내이면 요청을 통과시키고, 초과하면 거부한다.

아래 그림의 처리율 제한기는 분당 최대 2회의 요청만 처리하도록 설정되어 있다.

• ① 1:00:01 요청 도착
  • 로그가 비어있는 상태이므로 요청이 허용된다.
  • 타임스탬프 1:00:01이 로그에 기록된다. (로그 크기: 1)
• ② 1:00:30 요청 도착
  • 해당 타임스탬프가 로그에 추가된다.
  • 추가 직후 로그의 크기는 2이며, 허용 한도(2회)보다 크지 않은 값이므로 요청이 허용된다. (로그 크기: 2)
• ③ 1:00:50 요청 도착
  • 해당 타임스탬프가 로그에 추가된다.
  • 추가 직후 로그의 크기는 3이 되어 허용 한도보다 큰 값이 된다.
  • 따라서 타임스탬프는 로그에 남지만 요청은 거부된다. (HTTP 429 반환)
• ④ 1:01:40 요청 도착
  • 새로운 요청이 1:01:40에 도착하면서 현재 유효한 1분 윈도의 범위는 1:00:40~1:01:40으로 이동한다.
    • 이 시점의 윈도 시작점인 1:00:40보다 이전의 타임스탬프들은 전부 만료된 값으로 판정된다.
    • 따라서 로그에 쌓여있던 2개의 만료된 타임스탬프(1:00:01, 1:00:30)를 로그에서 삭제한다.
    • 삭제 직후 로그에 남은 크기는 정확히 2(1:00:50 거부 내역 + 신규 1:01:40)가 된다.
    • 로그의 크기가 허용 한도(2회)와 같으므로 1:01:40의 신규 요청은 최종적으로 허용된다.
• 장점
  • 허용 한도가 경계선에 구애받지 않고 유연하게 이동하므로, 어떤 임의의 시간 범위를 긁어서 보다라도 허용 처리율 제한을 절대 초과하지 않아 매우 정교하다.
• 단점
  • 메모리 소모가 심각하다.
    • 거부된 요청을 포함하여 모든 타임스탬프를 저장해야 하므로, 대규모 시스템에서 분당 수만 건의 트래픽 폭주가 발생하면 레디스 메모리가 순식간에 고갈될 수 있다.

💡’요청이 거부되어도 타임스탬프는 로그에 남는다’의 의미는 이 거부된 요청들이 나중에 처리되는 걸까?

아니다. 거부된 요청은 즉시 버려지며(HTTP 429 응답), 나중에 재처리되지 않는다.

로그에 타임스탬프를 남겨두는 이유는 무차별적인 공격을 차단하기 위함이다.
만일 거부된 요청을 로그에 남기지 않는다면, 한도 초과 이후 악의적인 유저가 초당 1,000번씩 요청을 날려도 로그는 늘 깨끗한 상태를 유지하게 되어, 유저가 공격을 멈춘 직후 0.001초 뒤에 보내는 요청은 바로 통과할 수 있게 된다.

거부된 내역까지 로그에 남겨두어야만, 진정한 의미의 ‘이동 유동 시간 범위’ 내에서의 엄격한 빈도 제어가 완성된다.

3.5. 이동 윈도 카운터(Sliding Window Counter) 알고리즘

고정 윈도 카운터의 메모리 효율성과 이동 윈도 로딩의 경계선 방어 능력을 결합한 알고리즘이다.

이 알고리즘은 과거의 모든 타임스탬프를 로깅하는 대신, ‘직전 윈도의 카운터 값’과 ‘현재 윈도의 카운터 값’을 기반으로 현재 시점의 트래픽을 수학적으로 추정한다.

임의의 시점에 들어온 새 요청에 대해 현재 윈도 내부의 총 요청 수를 계산하는 공식은 아래와 같다. \[\text{현재 윈도 내 추정 요청 수} = \text{현재 윈도의 카운터 값} + \left( \text{직전 윈도의 카운터 값} \times \text{이동 윈도와 직전 윈도가 겹치는 비율} \right)\]

아래 그림은 허용 한도가 분당 7개인 시스템에서 직전 1분 동안 5개, 현재 1분 동안 3개의 요청이 들어왔고, 현재 윈도의 30% 지점에 새 요청이 인입된 경우이다.

• 이동 윈도와 직전 1분이 겹치는 비율은 \(100% - 30% = 70%\)
• 3 + (5 * 70%) = 3 + 3.5 = 6.5
• 현재 추정치(6개)는 제한 한도(7개)보다 작으므로, 이번 신규 요청은 통과된다.

• 하지만 그 직후에는 한도에 도달했기 때문에 더 이상의 요청은 받을 수 없을 것이다.

• 장점
  • 메모리 효율이 좋다.
    • 타임스탬프를 저장하지 않고, 직전 윈도와 현재 윈도의 카운터 숫자만 기억하므로 메모리 효율이 극도로 우수하며, 고정 윈도의 경계면 문제를 완벽히 보완한다.
  • 짧은 시간에 몰리는 트래픽에 효율적으로 대응
    • 이전 시간대의 평균 처리율을 가중치로 반영하므로 경계면의 트래픽 버스트 충격을 유연하게 흡수한다.
• 단점
  • 추정치가 다소 느슨하다.
    • 직전 시간대에 도착한 요청들이 시간축 위에 ‘균등하게 분포’되어 있다고 가정한 상태에서 계산하기 때문에 실제 값과 약간의 오차가 있을 수 있다.
  • 하지만 심각한 문제는 아니다.
    • 글로벌 CDN 기업인 Cloudflare가 수행한 실험에 따르면, 40억 개의 요청 중 실제 트래픽 상태와 맞지 않게 오판하여 허용되거나 버려진 요청은 0.003%에 불과할 정도로 미미하다.

💡’이전 시간대의 평균 처리율에 따라 상태를 계산하는 것’과 ‘짧은 시간에 몰리는 트래픽(버스트)에 잘 대응하는 것’은 무슨 상관일까?

고정 윈도처럼 경계면에서 카운터가 0으로 뚝 떨어지거나, 로깅 알고리즘처럼 수만 개의 데이터를 메모리에 올릴 필요 없이 직전 트래픽의 흐름(가중치)이 현재 시간대로 부드럽게 이어지기 때문이다.

만일 직전 시간대에 트래픽 폭주가 있었다면 가중치 분률(70%) 때문에 현재 시간대 초기에는 카운터가 높은 상태로 시작되어 버스트 트래픽을 자연스럽게 억제한다.
즉, 과거의 트래픽 기조를 기억하면서 메모리는 단 두 개의 카운터 숫자로만 유지하므로 대규모 스파이크 트래픽 상황에서 인프라의 연산 부담을 덜어준다.

4. 개략적 아키텍처

지금까지 살펴본 처리율 제한 알고리즘들의 기본 아이디어는 단순하다.

얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적 대상별(사용자별, IP별, API 엔드포인트별)로 두고, 이 카운터의 값이 임계치를 넘어서면 요청을 거부하는 것이다.

그렇다면 이 카운터 데이터는 어디에 보관해야 할까?
일반적인 RDB는 디스크 접근 오버헤드 때문에 연산 속도가 느려 대규모 트래픽 환경에서 절대 사용할 수 없다.
따라서 메모리상에서 동작하는 빠른 캐시 서버를 사용해야 한다.

실무에서는 처리율 제한 장치를 구현할 때 레디스를 자주 사용한다.
레디스는 메모리 기반 저장 장치이면서, 처리율 제한에 최적화된 두 가지 핵심 명령어를 지원하기 때문이다.

• INCR
  • 메모리에 저장된 카운터의 값을 1만큼 원자적으로 증가시킴
• EXPIRE
  • 카운터 키에 만료 시간을 설정하여, 지정된 시간이 지나면 메모리에서 자동으로 삭제되도록 관리

• 클라이언트가 처리율 제한 미들웨어에게 HTTP 요청을 보냄
• 미들웨어는 레디스의 해당 유저/IP 카운터를 조회하여 한도에 도달했는지 확인
  • 한도에 도달했다면: 요청을 즉시 거부하고 클라이언트에게 에러 반환
  • 한도에 도달하지 않았다면: 요청은 API 서버로 안전하게 전달됨, 이 때 미들웨어는 레디스에 보관된 카운터 값을 1만큼 증가시킨 후 다시 저장함

5. 처리율 제한 장치 상세 설계

개략적인 아키텍처를 잡았으니, 이제 구체적으로 알아보자.

여기서는 아래 두 가지 핵심 질문에 대해 다룬다.

• 처리율 제한 규칙(Rule)은 어떻게 만들어지고 어디에 저장되는가?
• 처리가 제한된 한도 초과 트래픽들은 구체적으로 어떻게 처리되는가?

5.1. 처리율 제한 규칙

실무에서 가장 널리 사용되는 리프트(Lyft)의 오픈소스 처리율 제한 컴포넌트인 Envoy의 규칙 정의 방식을 보자.

# [규칙 1] 마케팅 메시지 발송 한도를 하루 최대 5개로 제한
domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

---

# [규칙 2] 클라이언트의 분당 로그인 시도 횟수를 최대 5회로 제한
domain: auth
descriptors:
  - key: auth_type
    value: login
    rate_limit:
      unit: minute
      requests_per_unit: 5

이런 비즈니스 제약 규칙들은 보통 디스크 내의 설정 파일 형태로 보관한다.
서버가 매번 요청을 판정할 때마다 디스크를 읽으면 지연 시간이 치명적으로 늘어나므로, 백그라운드 워커가 이 규칙을 주기적으로 읽어 인메모리 캐시에 동기화해 두고 사용한다.

5.2. 처리율 한도 초과 트래픽의 처리

사용자의 요청이 사전에 정의한 임계치를 넘어 제한에 걸리면, 시스템은 HTTP 429 Too Many Requests 응답을 클라이언트에게 반환한다.

이 때 비즈니스 요구사항에 따라 한도 초과 트래픽을 처리하는 두 가지 옵션이 있다.

• 옵션 1: 요청 버림
  • 한도를 초과한 즉시 요청을 드롭하고 에러 응답만 보냄
• 옵션 2: 메시지 큐 보관
  • 당장 처리하지 못하더라도 나중에 반드시 처리해야 하는 중요한 요청(예: 주문, 결제, 이벤트 응모 등)이라면 메시지 큐(카프카, RabbitMQ 등)에 담아두고 백엔드가 순차적으로 소비하도록 구성

5.2.1. HTTP 응답 헤더 설계: 클라이언트와의 소통

클라이언트는 본인의 요청이 처리율 제한에 걸리고 있는지, 남은 쿼터가 얼마인지 알 수 있어야 유연하게 재시도 로직을 짤 수 있다.
여기서는 이를 위해 3개의 HTTP 응답 헤더를 반환한다.

• X-Ratelimit-Remaining: 현재 시간대(윈도) 내에 최대로 더 보낼 수 있는 남은 요청의 개수
• X-Ratelimit-Limit: 매 윈도 주기마다 클라이언트가 전송할 수 있는 최대 요청의 한도 개수
• X-Ratelimit-Retry-After: 한도 제한에서 벗어나 정상 요청을 보내기 위해 클라이언트가 몇 초 뒤에 재시도해야 하는지 안내하는 타임아웃 정보

유저가 너무 많은 요청을 보내 한도를 초과하면, 제한 장치는 HTTP 429 오류 코드와 함께 X-Ratelimit-Retry-After 헤더를 담아서 즉시 리턴한다.

5.3. 종합 상세 설계 및 데이터 플로우

• 규칙 로드
  • 처리율 제한 규칙은 최초 디스크에 보관된다.
  • 내부 백그라운드 작업 프로세스(Worker)는 이 규칙 파일을 수시로 읽어 캐시 서버에 최신 규칙을 저장한다.
• 요청 인입
  • 클라이언트가 API 서버로 HTTP 요청을 보내면, 이 요청은 서버에 닿기 전 전면의 처리율 제한 미들웨어에 먼저 도달한다.
• 카운터 및 규칙 조회
  • 미들웨어는 캐시에서 해당 엔드포인트에 맞는 ‘제한 규칙’을 가져온다.
  • 이와 동시에 레디스 캐시로부터 해당 클라이언트의 ‘현재 카운터 값’과 ‘마지막 요청 타임스탬프’를 읽어온다.
• 판정 및 처리
  • 제한에 걸리지 않은 경우
    • 미들웨어는 요청을 API 서버로 정상 패스한다. 이와 동시에 레디스의 카운터 값을 1 증가시켜 업데이트한다.
  • 제한에 걸린 경우
    • 미들웨어는 API 서버로 요청을 보내지 않고 차단한 후, HTTP 429 에러를 응답 헤더 메타데이터와 함께 클라이언트에게 반환한다.
    • 이때 비즈니스 성격에 따라 요청을 완전히 버리거나(옵션 1), 메시지 큐에 보관(옵션 2)하여 사후 처리한다.

5.4. 분산 환경에서의 처리율 제한 장치

처리율 제한 장치를 단일 서버가 아닌, 여러 대의 서버와 병렬 스레드를 지원하도록 대규모 분산 환경으로 확장할 때는 반드시 해결해야 할 문제들이 존재한다.

• 경쟁 조건(Race Condition)
• 동기화

5.4.1. 경쟁 조건(Race Condition)

처리율 제한 미들웨어가 분산 환경에서 다중 요청을 처리할 때의 로직은 대략 아래와 같다.

• 레디스에서 카운터의 값을 읽어옴
• counter + 1의 값이 임계치를 넘는지 확인
• 넘지 않는다면 레디스에 보관된 카운터 값을 1만큼 증가시켜 저장

하지만 병행성(Concurrency)이 매우 심한 대규모 분산 환경에서는 아래 그림과 같은 경쟁 조건(Race Condition) 이슈가 발생할 수 있다.

• 문제 시나리오
  • 원래 counter의 값이 3인 상태에서 두 개의 요청(요청 1, 요청 2)이 거의 동시에 인입
  • 두 요청 스레드가 레디스로부터 counter 값을 읽었을 때 둘 다 3을 읽게 됨
  • 각자 임계치 체크를 통과한 후 값을 1씩 증가시키고 다시 레디스에 쓰는데, 두 스레드 모두 4를 기록함
• 결과
  • 원래 두 개의 요청이 정상 처리되었으므로 counter의 값은 5가 되어야 정상이지만, 경쟁 조건으로 인해 데이터 정합성이 깨져 4로 기록됨
  • 임계치보다 더 많은 트래픽이 시스템을 통과할 수 있는 허점이 생김

분산 환경에서 동시성 제어를 위해 가장 먼저 떠올리는 것은 Lock 메커니즘이지만, Lock은 시스템 전체의 처리 성능을 상당히 떨어뜨려 대규모 트래픽 미들웨어에는 적합하지 않다.
위와 같은 상황에서는 Lock 대신 아래 2가지 해결책을 쓸 수 있다.

• 루아 스크립트(Lua script)
  • 레디스는 싱글 스레드로 명령어를 실행한다.
  • ‘카운터 읽기 → 비교 → 카운트 증가’라는 일련의 로직을 루아 스크립트로 묶어서 레디스로 보내면, 레디스는 이 스크립트 전체를 하나의 원자적인 명령어로 실행하므로 Race Condition이 예방됨
• Sorted set
  • 이동 윈도 로깅 알고리즘에서 언급한 레디스의 Sorted Set 구조를 활용하면 원자적인 범위 연산이 가능해져 Race Condition 해결 가능

5.4.2. 동기화 이슈

분산 환경에서 수많은 요청을 감당하려면 처리율 제한 장치 서버를 여러 대 두어야 하고, 이 때 동기화 문제가 필연적으로 발생한다.

기본적으로 웹 계층은 Stateless 아키텍처로 설계된다.
로드 밸런서는 유저의 요청을 여러 대의 제한 장치 서버로 분산하여 보낸다.
만약 동기화 처리를 하지 않는다면 아래 그림과 같은 문제가 발생한다.

• 문제 상황
  • 클라이언트 1이 첫 번째 요청을 ‘처리율 제한 장치 1’로 보내고, 두 번째 요청은 ‘처리율 제한 장치 2’로 보낼 수 있다.
  • 이 때 두 제한 장치 간에 데이터 동기화가 없다면, 제한 장치 2는 클라이언트 1에 대해 아무것도 모르므로 처리율 제한을 올바르게 수행할 수 없음

이를 해결하기 위해 로드 밸런서 단에서 Sticky Session을 활용하여 동일한 클라이언트의 요청은 항상 동일한 처리율 제한 장치로 가도록 강제할 수 있다.
하지만 이 방법은 특정 서버에 트래픽이 몰릴 수 있고, 규모 확장성과 유연성을 저해하므로 추천하지 않는다.

더 나은 해결책은 아래 그림과 같이 레디스와 같은 중앙 집중형 데이터 저장소를 공유하는 것이다.

모든 분산 처리율 제한 장치 서버들이 로컬 메모리에 카운터를 두지 않고 공통의 글로벌 레디스를 바라보며 데이터를 읽고 쓰기 때문에, 유저가 어떤 제한 장치 서버로 인입되더라도 통제된 트레픽 제어가 가능해진다.

5.4.3. 성능 최적화

중앙 집중형 공유 저장소 구조까지 완성했다면, 이제 글로벌 대규모 인프라 관점에서 아래 두 가지 지점의 성능 개선을 도모할 수 있다.

• 에지 서버(Edge Server) 도입을 통한 지연 시간 단축
  • 전 세계 사용자를 대상으로 서비스를 운영할 때, 데이터 센터와 멀리 떨어진 사용자일수록 처리율 제한 장치를 거치는 과정에서 지연 시간이 증가할 수밖에 없다.
  • 대형 클라우드 기업들은 전 세계 곳곳에 구축된 에지 서버(CDN 등)에 처리율 제한 장치를 전진 배치하여 사용자와 가장 가까운 엣지 단에서 트래픽을 선제 제어하도록 아키텍처를 최적화한다.
• 최종 일관성 모델(Eventual Consistency Model) 채택
  • 제한 장치 간 혹은 분산 저장소 간에 데이터를 실시간으로 동기화(강한 일관성)하려다 보면 동기화 네트워크 비용 때문에 병목이 생긴다.
  • 분산 처리율 제한 장치에서는 실시간 정합성을 다소 양보하더라도 최종적으로 일관성이 맞춰지는 최종 일관성 모델을 사용하여 동기화 오버헤드를 줄이고 전체 성능을 극대화한다.

일관성 모델에 관해서는 추후 다룰 예정입니다. (p. 73)

5.4.4. 모니터링

처리율 제한 장치를 실무 인프라에 성공적으로 배포한 후에는, 지속적인 모니터링을 통해 아래 두 가지 사항을 검증하고 튜닝해야 한다.

• 현재 채택한 처리율 제한 알고리즘이 우리 서비스 트래픽 스타일에 정말 효과적인가?
• 정의한 처리율 제한 규칙(임계치 등)이 비즈니스 요구사항 대비 효과적인가?

만일 모니터링 중 처리율 제한 규칙이 필요 이상으로 너무 빡빡하게 설정되어 있다는 점이 발견된다면, 수많은 정상 유저의 유효한 요청들이 처리되지 못하고 버려질 것이다.
모니터링 지표를 기반으로 규칙을 유연하게 조정하는 데이터 기반 튜닝 프로세스가 수반되어야 한다.

6. 마무리

대규모 시스템의 안정성을 책임지는 다양한 처리율 제한 장치 아키텍처와 알고리즘에 대해 알아보았다.
마지막으로 아키텍트로서 고려해야 할 실무 팁 두 가지를 공유한다.

• 경성(Hard) 또는 연성(Soft) 처리율 제한의 선택
  • 경성 처리율 제한
    • 요청 개수가 사전에 정의한 임계치를 절대 단 한 번도 넘어설 수 없다.
  • 연성 처리율 제한
    • 트래픽이 일시적으로 스파이크를 치는 짧은 시간 동안만큼은 임계치를 잠시 넘어서는 것을 허용한다.
• 클라이언트의 처리율 제한 회피 및 상생 전략
  • 시스템이 처리율 제한 장치를 꼼꼼히 설계한 만큼, 클라이언트 측의 설계도 매우 중요하다.
  • 클라이언트 측 캐시를 적극적으로 활용하여 불필요한 API 호출 횟수 자체를 원천적으로 줄여야 한다.
  • HTTP 429 제한 오류를 만났을 때 짧은 시간 동안 무차별적인 무한 연타 재시도를 보내지 않도록, 재시도 로직을 설계할 때는 서버의 부하를 덜어주기 위해 대기 시간을 지수적으로 늘리는 충분한 백오프(Exponential Backoff)및 지터(Jitter) 알고리즘을 도입한다.

AWS, GCP 같은 퍼블릭 클라우드를 쓰고 있다면 설정값 입력만으로 분산 처리율 제한 장치가 완성된다.

• Cloud Managed API Gateway
  • AWS API Gateway
    • 내부적으로 토큰 버킷 알고리즘을 사용하며, 클라이언트별(API Key 기반) 또는 스테이지별 초당 요청 수와 버스트 값을 넣으면 분산 환경 동기화까지 AWS가 알아서 처리해줌
  • Azure API Management & Google Cloud Apigee
• Edge Security
  • 트래픽이 우리 서버에 오기도 전에, 전 세계에 퍼져 있는 Edge 서버 단에서 악의적인 요청을 선제로 막아주는 제품들
    • Cloudflare Advanced Rate Limiting
      • 앞서 오차율 0.003% 통계로 언급했던 바로 그 제품
      • 웹 방화벽(WAF)과 결합하여 악의적인 크롤링 봇이나 DDoS 공격성 연타 트래픽을 백엔드 서버의 자원을 쓰지 않고 전면에서 차단해줌

실무에서는 보통 Cloudflare(보안/에지 제한) + AWS API Gateway(비즈니스/유저별 제한)처럼 두 가지를 조합하는 Multi-tier 방식을 많이 사용한다.

참고 사이트 & 함께 보면 좋은 사이트

본 포스트는 알렉스 쉬 저자의 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 기반으로 스터디하며 정리한 내용들입니다.

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초
• 책에 나온 링크들 모음
• Google Cloud 공식 문서: 워크로드의 트래픽 및 부하 관리 가이드
• System Design — Rate limiter and Data modelling 심층 분석 가이드
• Envoy Proxy 공식 처리율 제한 오픈소스 레포지토리
• Redis를 활용한 Request Rate Limiter 루아 스크립트 레퍼런스 및 예시