처리율 제한 장치
네트워크 시스템에서 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치
특정기간 내에 전송되는 클라이언트의 요청 횟수를 제한한다.
API 요청 횟수가 제한 장치에 정의된 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단된다.
DoS 공격에 의한 자원고갈을 방지
비용 절감:
- 우선순위가 높은 APi에 더 많은 자원을 할당할 수 있다.
- 처리율 체한은 외부 API에 이용료를 지불하고 있는 회사들에게 매우 중요하다.
- 서버 과부하를 막는다.
1단계: 문제 이해, 설계 범위 확정
처리율 제한 장치는 여러가지 알고리즘을 사용해서 구현할 수 있고 각각 고유한 장단점을 갖기 때문에, 어떤 알고리즘을 사용해야할지 면접관과 소통하며 결정을 내려야한다.
결론난 조건
- 서버 측 제한 장치
- Ip 주소, 사용자 ID 등 다양한 형태를 정의할 수 있는 유연한 시스템이어야함.
- 대규모, 분산 환경에서 작동해야 함.
- 처리율 제한 장치를 독립된 서비스 or 어플리케이션 코드에 포함 할지는 직접 결정하라.
- 요청이 거부당한 사용자에게 그 사실을 알려야한다.
- 설정된 처리율을 초과하는 요청은 정학하게 제한 해야 한다.
- HTTP 응답에 영향을 주는 것은 곤란하다.
- 가능한 적은 메모리
- 분산형 처리율 제한
- 예외 처리
- 높은 결함 감내성
2단계: 개략적 설계안 제시
처리율 제한 미들웨어
해당 미들웨어에서 API 서버로 가는 요청들을 제어한다.
만약 처리율 제한 미들웨어에 의해 요청이 가로막히면 클라이언트는 HTTP 상태코드 429(Too many requests) 를 받는다.
API 게이트웨이
API 게이트웨이는 다음과 같은 역할을 한다.
- 처리율 제한
- SSL termination
- authentication
- IP whitelist 관리
마이크로서비스에 기반해 답변할 경우, 본인 설계에 API 게이트웨이가 이미 포함돼있다면 처리율 제한 기능을 API 게이트웨이에 포함시켜야 할 수도 있다.
알고리즘
토큰 버킷 알고리즘
- 간단하다
- 알고리즘이 널리 알려져 있다.
요청이 도착하면 버킷에 충분한 토큰이 있는지 검사
- 토큰이 있는 경우 버킷에서 토큰 하나를 꺼낸 후 요청을 시스템에 전달
- 토큰이 없는 경우, 해당 요청 무시
알고리즘 파라미터
- 버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수
- 토큰 공급률: 단위시간 당 몇 개의 토큰이 공급되는가
- 버킷의 개수
API 엔드포인트 마다 별도의 버킷을 두는 경우
- 사용자마다 하루에 한 번 포스팅을 하고, 친구 추가를 150명까지 할 수 있고, 좋아요 버튼은 다섯 번까지만 누를 수 있다 => 사용자마다 3개의 버킷
모든 요청이 하나의 버킷을 공유하는 경우
- 시스템의 처리율을 초당 10,000개 요청으로 제한하고 싶은 경우.
장점
- 구현이 쉽다
- 메모리 사용 측면에서도 효율적이다
- 짧은 시간에 집중되는 트래픽도 처리 가능하다.
단점
- 버킷 크기, 토큰 공급률을 적절하게 튜닝하는 것이 어렵다.
누출 버킷 알고리즘
- 토큰 버킷 알고리즘과 비슷하다.
- 요청 처리율이 고정돼있다.
- 보통 큐로 구현한다.
요청이 도착하면 큐가 가득 차있는지 확인
- 빈자리가 있는 경우에는 큐에 요청을 추가한다.
- 큐가 가득 차 있는 경우에는 새 요청은 버린다.
지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
알고리즘 파라미터
- 버킷 크기
- 처리율: 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값.
장점
- 큐의 크기가 제한되어있어 메모리 사용량 측면에서 효율적이다.
- 고정된 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우에 적합하다.
단점
- 단시간에 많은 트래픽이 몰리는 경우 요청이 쌓이면서 최신 요청들이 버려질 수 있다.
- 인자들을 적절히 튜닝하기가 어렵다.
고정 윈도우 카운터 알고리즘
- 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
- 요청이 접수될 대마다 카운터의 값이 1씩 증가한다.
- 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 제한한다.
장점
메모리 효율이 좋다.
이해하기 쉽다.
윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.
단점
윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다.
고정 1초에 10개 제한이라고 했을때
(1:00:00:00 ~ 1:00:00:90) -> 3개
(1:00:00:90 ~ 1:00:01:00) -> 5개
(1:00:01:00 ~ 1:00:01:10) -> 7개-> 할당된 양보다 더 많은 요청이 처리되버림
이동 윈도 로깅 알고리즘
고정 윈도우 카운터 알고리즘의 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 문제를 해결한다.
요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 보통 레디스의 정렬집합같은 캐시에 보관한다.
- 새 요청이 오면 만료된 타임스탬프는 제거한다.
- 새 요청의 타임스탬프를 로그에 추가한다.
- 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다.
- 그렇지 않은 경우에는 처리를 거부한다.
장점
- 어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
단점
- 거부된 요청의 타임스탬프도 보관하기 때문에 다량의 메모리가 사용된다.
이동 윈도 카운터 알고리즘
고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘의 결합된 방식
시간에 따라 움직이는 윈도의 카운터 계산방법
현재 구간 요청수 + 직전 구간 요청 수 * 이동 윈도와 직전 구간 겹치는 비율
9 * 0.75 + 5 = 11.75 -> 요청 거부
개략적인 아키텍처
카운터를 어디에 보관할 것 인가
데이터베이스는 디스크 접근 때문에 느리므로 빠르고, 시간 기반 만료 정책을 지원해주는 캐시(레디스)를 사용하자.
- 클라이언트가 처리율 제한 미들웨어에게 요청을 보낸다.
- 처리율 제한 미들웨어는 레디스에서 카운터를 가져와 제한 대상인지 검사한다.
3단계: 상세 설계
처리율 제한 규칙
리프트의 ratelimit(오픈소스)을 사용하여 처리율 제한 규칙을 정의할 수 있다.
domain: messaging
descriptors:
- key: message_type
value: marketing
descriptors:
- key: to_number
rate_limit:
unit: day
requests_per_unit: 5처리할 수 있는 마케팅 메시지를 하루 최대 5개로 제한하고 있다.
처리율 한도 초과 트래픽의 처리
- 어떤 요청이 와도 한도 제한에 걸리면 HTTP 429 응답을 보낸다.
- 한도 제한이 걸린 메시지를 나중에 처리하기 위해 큐에 보관할 수 있다.
처리율 제한 장치가 사용하는 HTTP 헤더
- X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능의 요청 수
- X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
- X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야하는지 알림. (429 응답을 반환하는 경우 이 헤더를 함께 반환)
상세 설계
처리율 규칙은 디스크에 보관
작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐시에 저장
- 클라이언트 요청이 처리율 제한 미들웨어에 도달
- 제한 규칙을 캐시에서 가져옴
- 사용하는 알고리즘에 따라 카운터 또는 타임스탬프를 레디스 캐시에서 가져옴
- 알고리즘을 사용해 요청 전달 여부 결정
경쟁 조건
락(lock) : 시스템의 성능을 상당히 떨어뜨린다는 문제가 있다.
해결법 :
- 루아 스크립트
- 정렬 집합
동기화 이슈
수백만 사용자를 지원하기 위해 여러 서버가 있다.
요청을 각기 다른 제한장치로 보낼 수 있기 때문에 모든 처리율 제한 장치 서버의 동기화가 필요하다.
해결책 : redis 같은 중앙 집중형 데이터 저장소를 쓰는 것.
