Rate Limiting: 개념, 알고리즘 및 분산 과제

Source: Dev.to

번역을 진행하려면 번역이 필요한 전체 텍스트(코드 블록을 제외한 본문)를 제공해 주시겠어요? 텍스트를 받는 대로 한국어로 번역해 드리겠습니다.

Source: …

소개

API나 백엔드 서비스를 구축해 본 적이 있다면, 다음과 같은 문제들을 겪어봤을 가능성이 높습니다:

• 한 사용자가 너무 많은 요청을 보냄
• 봇이 엔드포인트를 악용함
• 트래픽 급증으로 서비스가 중단됨
• 재시도나 크론 작업이 실수로 시스템에 과부하를 줌

이 블로그는 **속도 제한(rate limiting)**에 관한 것으로, 시스템을 이러한 문제로부터 보호하기 위해 사용되는 간단하지만 중요한 기술을 다룹니다.

이번 포스트에서 우리는:

• 속도 제한이 왜 필요한지 이해하기
• 일반적인 속도 제한 알고리즘이 어떻게 동작하는지 배우기
• 실제 시스템에서 속도 제한이 어디에 적용되는지 살펴보기

속도 제한에 대한 사전 지식은 필요하지 않습니다. 기본적인 API와 요청에 대해 이해하고 있다면 충분히 따라올 수 있습니다.

목차

• Rate Limiting이 해결하는 문제
• Rate Limiting이 실제로 하는 일
• 일반적인 Rate Limiting 알고리즘
  • 고정 윈도우 카운터
  • 슬라이딩 윈도우
  • 토큰 버킷
  • 리키 버킷
• 알고리즘 비교
• Rate‑Limiting 알고리즘 개요
• 분산 시스템에서의 도전 과제
• 핵심 요약

레이트 리밋팅이 해결하는 문제

요청이 서버에 도달하면 CPU 시간, 메모리, 데이터베이스 연결, 네트워크 대역폭 등 다양한 자원을 소비합니다. 일반적인 사용량에서는 문제가 없지만 동시에 너무 많은 요청이 들어올 때 문제가 발생합니다.

일반적인 원인

• 한 사용자가 짧은 간격으로 반복해서 요청을 보냄
• 공개 엔드포인트를 노린 봇
• 적절한 백오프(back‑off) 없이 재시도 메커니즘 사용
• 릴리스나 프로모션 후 갑작스러운 트래픽 급증

서버는 모든 요청을 동일하게 바라보며, 어떤 요청이 중요한지, 어떤 요청이 해로운지 구분하지 못합니다.

왜 이것이 심각한 문제가 되는가

요청량이 제한 없이 계속 증가하면:

• 응답 시간이 늘어남
• 데이터베이스가 느려짐
• 타임아웃이 증가
• 오류율이 급증
• 결국 서비스가 모든 사용자에게 중단됨

왜 “서버를 확장”만으로는 안 되는가

보통의 반응은 “서버를 더 추가하자”입니다. 확장은 도움이 되지만 근본적인 문제를 해결하지는 못합니다:

• 무제한 요청은 결국 어떤 시스템도 감당할 수 없게 됨
• 확장은 비용을 증가시킴
• 데이터베이스와 서드‑파티 API는 같은 방식으로 확장되지 않을 수 있음

계속해서 확장만 하면 실패를 미룰 뿐입니다.

시스템이 실제로 필요로 하는 것

• 요청이 허용되는 속도를 제어하는 방법
• 실수이든 의도이든 남용을 방지하는 보호 장치
• 한 사용자가 다른 사용자를 압도하지 못하도록 하는 공정성

이것이 바로 레이트 리밋팅이 설계된 문제입니다.

실제로 레이트 리밋이 하는 일

핵심적으로, 레이트 리밋은 주어진 시간 동안 행동이 허용되는 빈도를 제어합니다. 가장 흔히 제어되는 행동은 API 요청입니다.

레이트 리밋은 보통 다음과 같이 표현됩니다:

• 사용자당 분당 100 요청 허용
• IP당 초당 10 요청 허용
• 민감한 엔드포인트에 대해 초당 1 요청 허용

제한에 도달하면, 충분한 시간이 경과할 때까지 시스템은 추가 요청을 처리하지 않습니다.

제한을 초과했을 때 발생하는 일

• 요청이 거부됩니다
• 서버가 즉시 응답합니다
• 다른 사용자들을 위해 리소스가 보존됩니다

HTTP 기반 시스템에서는 일반적으로 429 Too Many Requests 응답으로 반환됩니다. 조기 거부는 데이터베이스 조회나 외부 API 호출과 같은 불필요한 작업을 방지합니다.

레이트 리밋이 보장하는 것

• 공정한 사용 – 한 사용자가 다른 모든 사용자를 위한 리소스를 소모할 수 없습니다
• 예측 가능한 성능 – 시스템은 부하가 걸려도 응답성을 유지합니다
• 제어된 버스트 – 일부 알고리즘은 짧은 버스트를 허용하면서도 장기 제한을 강제합니다
• 시스템 보호 – 실수로 발생한 버그나 비정상적인 클라이언트를 조기에 차단합니다

레이트 리밋이 하지 않는 일

• 인증 (사용자가 누구인지 확인하지 않음)
• 완전한 보안 솔루션
• 적절한 입력 검증을 대체하는 것

레이트 리밋은 트래픽 제어 메커니즘이며, 보안 게이트가 아닙니다.

공통 속도 제한 알고리즘

시스템마다 필요에 따라 서로 다른 속도 제한 알고리즘을 사용합니다. 어느 알고리즘도 보편적으로 “최고”는 아니며, 단순성, 정확성, 유연성 사이에서 각각 다른 트레이드오프를 합니다.

고정 윈도우 카운터

가장 단순한 형태의 속도 제한입니다.

작동 방식

1. 시간을 고정된 윈도우(예: 1분, 1시간)로 나눕니다.
2. 각 사용자마다 현재 윈도우에 대한 카운터를 유지합니다.
3. 들어오는 요청이 있을 때마다 이 카운터를 증가시킵니다.
4. 카운터가 제한에 도달하면 이후 요청을 거부합니다.
5. 윈도우가 끝나면 카운터를 0으로 초기화합니다.

예시

• 제한: 분당 5 요청
• 윈도우: 12:00 – 12:01

사용자가 12:00:59에 5개의 요청을 보내면 → 모두 허용됩니다.
카운터는 12:01:00에 초기화되어 → 또 다른 5개의 요청이 허용됩니다.

이는 사용자가 1초에 10개의 요청을 한 것과 동일한 효과를 가집니다.

고정 윈도우가 실패하는 이유

• 사용자가 윈도우 경계 시점을 이용해 우회할 수 있습니다.
• 트래픽이 매우 버스트하게 변합니다.
• 백엔드 서비스가 갑작스러운 급증을 겪을 수 있습니다.
• 부하가 걸릴 때 시스템이 불공정해집니다.

고정 윈도우가 허용될 수 있는 경우

• 트래픽이 매우 적은 시스템.
• 내부 도구.
• 프로토타입이나 데모.
• 정확성보다 단순함이 더 중요한 경우.

대부분의 프로덕션 API에서는 고정 윈도우를 보통 피합니다.

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 현재 시점부터 지난 N 초를 기준으로 보면서 고정 윈도우의 버스트 문제를 해결합니다.

작동 방식

1. 시스템은 항상 현재 시점부터 지난 N초를 살펴봅니다.
2. 각 요청은 이 롤링 윈도우에 대해 평가됩니다.
3. 시스템은 지난 N초 동안 발생한 요청 수를 셉니다.
4. 카운트가 제한을 초과하면 요청을 거부합니다.

예시

제한: 60초당 100 요청

• 언제든지 시스템은 지난 60초 동안 몇 개의 요청이 있었는지 확인합니다.
• 윈도우가 리셋될 때 발생하는 급증을 방지하고, 요청이 시간에 걸쳐 보다 고르게 분산됩니다.

장점

• 요청 분배가 훨씬 공정합니다.
• 트래픽 스파이크가 자연스럽게 감소합니다.
• 윈도우 경계에서 발생하는 버스트 문제가 없습니다.

단점

• 시스템이 요청 타임스탬프를 저장해야 합니다.
• 트래픽이 많아질수록 메모리 사용량이 증가합니다.
• 요청당 계산량이 늘어납니다.

토큰 버킷

엄격한 제한과 좋은 사용자 경험을 동시에 제공하기 때문에 프로덕션에서 가장 많이 사용되는 알고리즘 중 하나입니다.

작동 방식

• 각 사용자마다 토큰을 담는 버킷이 있습니다.
• 토큰은 고정된 비율로 버킷에 추가됩니다.
• 각 요청은 하나의 토큰을 소비합니다.
• 토큰이 남아 있지 않으면 요청이 거부됩니다.
• 버킷에는 최대 용량이 있어 토큰이 무한히 쌓이지 않습니다.

예시

버킷 크기: 10 토큰
리필 속도: 초당 1 토큰

Source: ds.s3.amazonaws.com/uploads/articles/umlnz48uisqgwkyl5e9o.jpg)

왜 잘 작동하는가

• 시스템을 중단하지 않고 짧은 폭발적인 트래픽을 허용합니다.
• 장기적인 속도 제한을 강제합니다.
• 사용자 경험을 향상시킵니다.
• 구현이 간단하고 효율적입니다.

이러한 특성 때문에 Token Bucket은 종종 API의 기본 선택이 됩니다.

Leaky Bucket

부드럽고 안정적인 출력 속도를 제공하는 데 중점을 둡니다.

작동 방식

• 들어오는 요청을 큐(버킷)에 넣습니다.
• 요청은 일정하고 고정된 속도로 큐를 빠져나갑니다.
• 큐가 가득 차면 새로운 요청은 버려집니다.

예시

1. 많은 요청이 한 번에 도착합니다.
2. 시스템은 일정한 속도로 요청을 처리합니다.
3. 큐가 가득 차면 초과 요청이 버려집니다.

장점

• 하위 시스템을 매우 잘 보호합니다.
• 예측 가능한 처리 속도를 보장합니다.
• 갑작스러운 트래픽 급증을 방지합니다.

사용자 대상 API에 대한 단점

• 폭발적인 요청이 지연되거나 버려집니다.
• 부하가 걸릴 경우 지연 시간이 증가합니다.
• 사용자 경험이 저하될 수 있습니다.

Leaky Bucket은 인터랙티브 API보다 백그라운드 작업 및 파이프라인에 더 적합합니다.

알고리즘 비교

The goal here is to understand which algorithm fits which situation.
여기서 목표는 어떤 알고리즘이 어떤 상황에 적합한지를 이해하는 것입니다.

고수준 비교

속도 제한 알고리즘 개요

트래픽 패턴, 공정성 요구사항 및 운영 제약 조건에 가장 잘 맞는 알고리즘을 선택하세요.

Challenges in Distributed Systems

지금까지 논의한 모든 내용은 단일 서버를 전제로 합니다. 실제 애플리케이션에서는 이것이 거의 드물며, 대부분의 시스템은 로드 밸런서 뒤에서 multiple servers(다수의 서버)로 운영됩니다. 이는 여러 중요한 과제를 야기합니다.