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