참고
처리율 제한 장치(rate limiter)란?
NOTE
클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치!
•
HTTP의 경우, 특정 기간 내에 전송되는 요청 횟수를 제한한다.
•
API 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리 중단된다.
예시
•
사용자는 초당 2회 이상 새 글을 올릴 수 없다.
•
같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
•
같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.
처리율 제한장치를 왜 두는가?
NOTE
•
Dos(Denial of Service) 공격에 의한 자원고갈을 방지할 수 있다.
◦
대형 기업 IT들이 공개한 API는 대부분 처리율 제한장치를 가지고 있다.
◦
ex) 트위터 → 3시간 동안 300개의 트윗만 올릴 수 있음
◦
ex) 구글 독스 → 사용자당 분당 300회의 read 요청만 허용된다.
•
비용을 절감한다.
◦
추가 요청에 대한 처리를 제한하면 서버를 많이 두지 않아도 된다.
◦
우선순위가 높은 API에 더 많은 자원을 할당할 수 있다.
•
서버 과부하를 막는다.
◦
봇(bot)에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러낼 수 있다.
처리율 제한 장치 설계
NOTE
처리율 제한 장치는 여러가지 알고리즘을 사용할 수 있고, 고유한 장단점이 있기 때문에 잘 선택해야 한다!
•
제한 장치를 서버와 클라이언트중 어디에 둘것인가?
•
API 호출제어 기준은 IP인가 사용자 ID인가?
•
시스템의 규모는 얼마나 되는가?
•
분산환경을 고려해야하는가?
•
요청이 거부당한 사용자에게 그 사실을 알려야 하는가?
•
제한 장치에 장애가 생기더라도 시스템에 영향을 주어서는 안된다.
처리율 제한 장치의 위치
NOTE
클라이언트 vs 서버
클라이언트는 쉽게 위변조가 가능하고, 클라이언트의 유형이 다양해 제한 장치를 두기에 적합하지 않다.
⇒ 서버에 둔다!
미들웨어 방식
미들웨어로 인해 block된 요청은 HTTP 상태코드 429가 반환된다.
•
대표적인 미들웨어 방식은 API 게이트웨이가 있다.
•
API 게이트웨이는 처리율 제한, 사용자 인증, SSL 종단 등을 지원하는 완전 관리형 서비스이다.
처리율 제한 알고리즘
토큰 버킷 알고리즘
NOTE
간단하고 알고리즘에 대한 이해도가 높기 떄문에 보편적으로 사용된다!
토큰만 존재한다면 요청을 어떻게든 처리할 수 있다!
•
통상적으로 API 엔드포인트마다 별도의 버킷을 둔다.
•
IP 주소별로 처리율 제한을 적용한다면, IP 주소마다 버킷을 하나씩 할당해야 한다.
장점
•
구현이 쉽다.
•
메모리 사용 측면에서 효율적이다.
•
짧은 시간에 집중되는 트래픽도 처리가 가능하다.
단점
•
버킷 크기와, 토큰 공급률을 적절하게 튜닝하는것이 어렵다.
누출 버킷 알고리즘
NOTE
큐에 담겨있는 요청을 지정시간마다 꺼내어서 처리한다!
토큰 버킷과 비슷하지만 요청 처리율이 고정되어 있다.
장점
•
큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다,
•
고정도니 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우에 적합하다.
단점
•
단시간에 많은 트래픽이 몰리는 경우 오래된 요청들이 쌓이고, 그 요청들을 빨리 처리하지 못하면 최신 요청들을 버리게 된다.
•
토큰 버킷과 마찬가지로 큐의 크기나, 처리율 튜닝하기가 까다롭다.
고정 윈도 카운터 알고리즘
NOTE
특정 시간간격마다 임계값을 설정해서 처리한다!
1초마다 3개씩의 요청을 처리한다. (3개를 넘어선 요청은 버려짐)
해당 알고리즘은 순간적으로 많은 트래픽이 몰리면 문제가 생긴다.
⇒ 그림과 같이 분당 5개를 처리하도록 설계했는데, 경계부근으로 인해 1분에 10개처리를 해버림!
장점
•
메모리 효율이 좋다.
•
이해하기 쉽다.
•
윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.
단점
•
윈도 경계 부근에 일시적으로 많은 트래픽이 몰리면, 예상보다 많은 요청을 처리하게된다.
이동 윈도 로깅 알고리즘
NOTE
고정 윈도 카운터 알고리즘의 문제를 해결하기 위해 나온 알고리즘!
4번의 로직을 자세히 보자
⇒ 1분 40초 요청이 들어옴 ( 40초 ~ 1분 40초 범위가 1분윈도, 40초 이전은 만료된것)
따라서 앞의 1초, 30초 요청이 삭제된다.
•
요청의 타임스탬프를 추적한다. 타임 스탬프 데이터는 보통 레디스의 정렬집합과 같은 캐시에 보관한다.
장점
•
아주 정교한 메커니즘이다.
•
어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
단점
•
다량의 메모리가 사용된다. 거부된 요청의 타임스탬프도 보관하기 때문
이동 윈도 카운터 알고리즘
NOTE
고정 윈도 카운터 + 이동 윈도 로깅 알고리즘을 결합한 방식!
현재 1분간의 요청수 ⇒ 직전 1분간의 요청수 * 이동 윈도와 직전 1분이 겹치는 비율
⇒ 3 + 5 * 70% = 6.5개
•
요청의 타임스탬프를 추적한다. 타임 스탬프 데이터는 보통 레디스의 정렬집합과 같은 캐시에 보관한다.
장점
•
이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽도 잘 대응한다.
•
메모리 효율이 좋다.
단점
•
직전 시간대에 도착한 요청이 균등하게 분포되어 있다는 가정하게 계산하기 때문에 다소 느슨하다.
•
하지만 실제 클라우드플레어의 실험에 따르면 40억개의 요청중 실제 상태와 맞지않거나 버려진건 0.03%에 불과하다.
처리율 제한 상세 설계
NOTE
클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치!
처리율 제한 장치를 설계한 아키텍쳐.
•
Redis를 활용해서 처리율 제한장치의 카운터를 구현한다.
◦
INCR : 메모리에 저장된 카운터의 값을 1 증가시킨다.
◦
EXPIRE : 카운터에 타임아웃 값을 설정한다. (설정시간이 지나면 자동삭제)
•
어떤 요청이 한도제한에 걸리면 429 응답(too many requests)을 클라이언트에게 보낸다,
•
경우에 따라서는 한도제한에 걸린 요청을 나중에 처리하기 위해 큐에 보관하거나 버릴수 있다.
◦
ex) 주문 시스템의 경우, 해당 주문을 보관했다가 나중에 처리해준다.
•
HTTP 응답 헤더에 처리율 제한이 걸리고 있는지에 대한 정보를 보낼 수 있다.
◦
X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능의 요청 수
◦
X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
◦
X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야하는지 알림.
분산 환경에서의 처리율 제한 장치의 구현
NOTE
경쟁조건(race condition)과 동기화(synchronization) 문제를 해결해야한다!
경쟁조건
redis의 카운터가 동시에 읽히고 수정하려하면 한번만 증가하는 경우가 발생한다.
•
해당 문제를 해결하기 위해선 락(Lock)을 사용해야한다.
•
하지만 락은 시스템의 성능을 떨어트릴 수 있으므로, 다른 해결책을 사용하자.
1.
루아 스크립트
2.
Redis의 정렬집합 자료구조 사용
동기화 이슈
처리율 제한 장치를 여러대 사용하는 경우
동기화 역시 하나의 중앙 집중형 DB를 사용하는것이 좋다.
sticky session역시 해결책중 하나지만 별로 권장하지 않는다.
성능 최적화, 모니터링
NOTE
•
성능 최적화
◦
여러 데이터 센터를 지원해서 latency를 줄이자.
•
모니터링
◦
채택한 알고리즘이 효율적인지, 정의했던 제한 규칙이 효과적인지 알아보자.