Share
Sign In
시리즈

처리율 제한 장치

개요

클라이언트 또는 서비스가 보내는 트래픽이 임계치를 넘어서면 추가 트래픽은 차단하는 장치

예시

사용자는 초당 2회 이상 새 글을 올릴 수 없다.
같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.

장점

DoS 공격에 의한 자원 고갈을 방지한다.
추가적인 API 요청이나 서버 자원을 아껴 비용을 절감한다.
봇이나 잘못된 트래픽에서 오는 트래픽으로 인한 서버 과부화를 막는다.

처리율 제한 알고리즘

토큰 버킷 알고리즘

동작 원리
요청은 버킷에 있는 토큰을 하나 가져가 실행을 인가받는다.
버킷에 남아있는 토큰이 없다면 해당 요청은 폐기한다.
토큰 공급기(refiller)는 매초마다 n개씩 버킷에 토큰을 채워넣는다.
단, 버킷에 있는 토큰의 수가 최대치를 넘으면 더이상 담을 수 없다.
인자(parameter)
버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 개수
토큰 공급률 : 초당 몇 개의 토큰이 버킷에 공급되는가
사례
통상적으로 API 엔드포인트마다 별도의 버킷을 둔다. ⇒ 즉, 사용자 혹은 IP 주소을 기준으로 둘 수 있다.
전체 시스템 처리율을 제한하고 싶다면 모든 요청이 하나의 버킷을 공유하도록 해야 할 것이다.
장점
구현이 쉽고 메모리 사용이 효율적이다.
트래픽 버스트를 처리할 수 있다.
단점
버킷 크기와 토큰 공급률을 튜닝하기가 어렵다.

누출 버킷 알고리즘

과 유사하지만 버킷 대신 FIFO 큐를 사용해 요청 처리율을 고정시킨다.
동작 원리
요청은 큐에 빈자리가 있는지 확인하고, 빈자리가 있으면 큐에 요청을 추가한다.
빈자리가 없으면 폐기한다.
지정된 시간마다 큐에서 요청을 꺼내 처리한다.
인자(parameter)
버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 개수. 즉 큐의 사이즈
처리율(outflow rate) : 일정 시간동안 몇 개의 요청을 처리할 것인가
장점
큐의 크기가 제한되어 있어 메모리 사용이 효율적이다.
처리율이 고정되어 있어 요청을 안정적으로 처리할 수 있다.
단점
트래픽 버스트가 발생할 경우 최신 요청은 무더기로 버려질 수 있다.

고정 윈도우 카운터 알고리즘

동작 원리
시간(timeline)을 고정된 크기(window)로 나누고 윈도우마다 카운터(counter)를 0으로 초기화한다.
요청이 들어오면 윈도우의 카운터는 1씩 증가한다.
카운터의 값이 임계치에 도달하면 다음 윈도우가 열릴 때까지 새로운 요청을 폐기한다.
장점
메모리 효율이 좋다
특정한 트래픽 패턴을 처리하기에 적합하다.
단점
윈도우 경계 부분에 요청이 몰린다면 실질적인 처리량은 임계치의 2배까지 올라갈 수 있다.

이동 윈도우 로깅 알고리즘

동작 원리
모든 요청의 타임스탬프를 로그에 추가한다. 폐기한 요청도 로그에 남긴다.
로그를 살펴 일정 시간동안 들어온 요청이 임계치보다 높으면 앞으로 들어올 요청은 폐기한다.
로그는 레디스의 정렬 집합(sorted set)과 같은 캐시에 저장한다.
장점
매우 세밀하게 시스템 처리율을 조절한다.
단점
거부된 요청의 타임스탬프도 저장하기 때문에 메모리를 많이 쓴다.

이동 윈도우 카운터 알고리즘

현재 윈도우의 요청 수 = 현재 윈도우의 요청 수 + 직전 윈도우의 요청 수 x 직전 윈도우가 차지하는 비율
⇒ 위 그림에서 현재 윈도우의 요청 수 = 2 + 4 x 30% = 3.2
결과값을 내림해도 무방하다.
⇒ \left \lfloor 3.2 \right \rfloor= 3
장점
평균 처리율을 잘 계산하기 때문에 짧은 시간에 몰리는 트래픽도 잘 계산한다.
메모리 효율이 좋다.
단점
윈도우 내의 요청이 균등하다고 가정하기 때문에 느슨하다. 하지만 예측을 벗어나 허용되거나 버려진 요청은 0.003%에 불과하다.

의사결정

처리율 제한 장치의 위치

클라이언트 : 쉽게 위변조가 가능해서 부적절하다.
미들웨어 : 클라이언트와 서버 사이의 트래픽을 한 번 거르는 역할
API Gateway
rate limit, SSL termination, authentication, IP whitelist 등을 지원하는 완전 관리형 서비스
AWS는 WAF가 IP당 처리율을 제한한다!
Untitled

한도 초과 트래픽 처리

어떤 요청이 한도 제한에 걸리면 HTTP 249 응답(too many requests)을 보낸다.
혹은 제한이 걸린 메시지를 큐에다 담고 나중에 처리할 수도 있다.
처리율 제한 장치는 아래 HTTP 헤드를 클라이언트에게 보낸다.
X-Ratelimit-Remaining : 윈도우 내에 남은 처리 가능 요청 수
X-Ratelimit-Limit : 매 윈도우마다 클라이언트가 전송할 수 있는 요청 수
X-Ratelimit-Retry-After : 한도 제한이 걸리지 않으려면 몇 초 뒤에 요청을 보내야 하는가
이중 한도 초과가 나면 429 응답과 X-Ratelimit-Retry-After 헤더를 함께 반환한다.

분산 환경에서의 이슈

경쟁 상황(Race condition)

하나의 클라이언트가 동시에 여러 요청을 보내면 프로세스 동기화에서 언급한 경쟁 상황이 발생해 카운터 값이 이상해질 수 있다. 해결 방법은 두 가지가 있다.
Lua script
Redis의 sorted set
별개로 Redis에서 INCR 등의 명령은 atomic하다.

동기화(Synchronization)

여러 대의 처리율 제한 장치를 둔다면 클라이언트는 요청을 분산해서 보낼 것이다. 그러면 클라이언트별로 정확한 윈도우 측정이 어려워진다. 해결 방법은 아래와 같다.
sticky session : 추천하지 않는다.
Redis 같은 DB를 중앙 집중형 데이터 저장소로 쓴다.

성능

latency를 줄이기 여러 대의 edge server를 둔다.
제한 장치 간에 데이터를 동기화 할 때 최종 일관성 모델을 사용한다.

모니터링

처리율 제한 알고리즘과 정책들(파라미터)이 효과적인지 확인한다.
상황에 따라 대처한다. 트래픽 버스트가 발생한다면 토큰 버킷이 적합할 것이다.

발전하기

hard/soft 처리율 제한
hard : 요청의 개수는 임계치를 절대 넘을 수 없다.
soft : 요청의 개수는 잠시 임계치를 넘을 수 있다.
L7 뿐만 아니라, Iptables를 사용해 L3에서 IP 주소를 제한하는 등 다른 계층에서도 적용이 가능하다.
처리율 제한을 회피하는 방법
클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄인다.
너무 짧은 시간 동안 많은 메시지를 보내지 않는다.
예외나 에러를 처리하는 코드를 작성하여 우아하게 복구하도록 한다.
재시도 로직을 구현한다면 충분한 백오프(back-off) 시간을 둔다.

설계

책에 있는 방법
AWS에서 이렇게 하면 어떨까 생각한 방법

출처

1.
AWS API Gateway 처리량 향상을 위해 API 요청 조절 - https://www.nclouds.com/blog/security-apps-aws-web-application-firewall
3.
Rate limiting for distributed systems with Redis and Lua - https://blog.callr.tech/rate-limiting-for-distributed-systems-with-redis-and-lua
4.
Better Rate Limiting With Redis Sorted Sets - https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
5.
Scaling your API with rate limiters - https://stripe.com/blog/rate-limiters
Made with SlashPage