처리율 제한 장치(Rate limiter)
- 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치
장점
- DoS (Denial of Service) 공격 방지
- 비용 절감
- 서버 과부하를 방지
1단계 문제 이해 및 설계 범위 확정
- 클라이언트 측 제한 장치인가? 서버 측 제한 장치인가?
- 어떤 기준을 통해 호출을 제한하는가? 어떤 제어 규칙을 사용하는가?
- 시스템 규모는 어떻게 되는가?
- 분산된 환경을 고려해야하는가?
- 처리율 제한 장치가 독립된 서비스로 동작하는가? 서비스 코드에 포함되는가?
- 제한된 경우, 클라이언트에게 알려주어야 하는가?
고려해야할 점
- 처리율 초과하는 요청은 정확하게 제한
- 낮은 응답시간 : 응답시간에 나쁜 영향을 주면 안됨
- 적은 메모리 사용
- 분산형 처리율 제한 : 분산형 구조에서 Rate limiter 또는 현재 상황을 공유할 수 있어야 함
- 예외 처리 : 요청이 제한된 경우, 클라이언트가 알 수 있어야 함
- 높은 Fault tolerance : 제한 장치에 장애가 생겨도, 전체 시스템에 영향을 주면 안됨
2단계 개략적 설계안 제시 및 동의 구하기
처리율 제한 장치는 어디에 둘 것인가?
- 클라이언트?
- 별로 좋지 않다. 위변조 가능
- 서버
- 서버에 붙여두는 것
- 미들웨어
- 요청이 서버에 들어가기 이전 미들웨어에서 먼저 통제
- 제한된 요청이라고 판단되면 서버에 안보내고, 미들웨어 단에서 HTTP 429 (Too many requests) 반환
- API Gateway : 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등
고려해야할 점
- 프로그래밍 언어, 캐시 서비스 등 기술 스택 점검 → 현재 서버 측 언어를 통해 구현이 가능한가? 충분한가?
- 현재 비즈니스에 맞는 처리율 제한 알고리즘 찾기 → 미들웨어 및 제 3자가 서비스하는 Gateway를 사용한다면 적절한 알고리즘이 있는지 확인.
- MSA 구조를 사용하고 있어 이미 API Gateway 사용하고 있다면, 기존 API Gateway에 Rate limiter 포함시키는 것 고려
처리율 제한 알고리즘
토큰 버킷(Token Bucket)
- 지정된 용량을 갖는 컨테이너인 토큰 버킷.
- 토큰 공급기(refiller)에 의해 사전 설정된 양의 토큰이 주기적으로 채워짐. 버킷이 가득 차면 추가로 공급된 토큰은 버려짐.
각 요청은 처리될 때마다 하나의 토큰을 사용. 즉, 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사. 토큰이 없으면 해당 요청은 버려짐(dropped)
2개의 파라미터
- 버킷 크기: 버킷에 담을 수 잇는 토큰의 최대 개수
- 토큰 공급률(refill rate): 초당 몇 개의 토큰이 버킷에 공급되는가
장점
- 구현이 쉬움
- 메모리 사용측면에서도 효율적
- Burst of traffic 의 경우에도 처리가 가능. 버킷에 남은 토큰이 있기만 하면 요청은 시스템에 전달 될 것.
단점
- 파라미터를 비즈니스 및 상황에 맞게 적절히 튜닝해야 하는 것이 까다로움.
누출 버킷(Leaky bucket)
- 요청이 도착하면
큐가 가득 차 있는지본다.빈 자리가 있는 경우에는 큐에 요청 추가 - 큐가 가득 차 있는 경우 새 요청 버림
- 지정된 시간마다 큐에서 요청을 꺼내어 처리
2개의 파라미터
- 버킷 크기: 큐 사이즈 값
- 처리율(outflow rate): 지정된 시간 당 몇 개의 항목을 처리할 것인가? (보통 초 단위)
장점
- 큐의 크기가 제한되어있어 메모리 사용량에서 효율적
- 고정된 처리율 → 안정적 출력(stable outflow rate)이 필요한 경우 적합
단점
- 단시간에 트래픽이 몰리는 경우(Burst of traffic), 큐에는 오래된 요청이 쌓임
- 제때 처리 못하면 최신 요청들 버려짐
- 토큰 버킷과 마찬가지로 튜닝하는게 까다로울 수 있다.
고정 윈도 카운터(Fixed window counter)
- 타임라인을 고정된 간격의 윈도로 나누고 각 윈도마다 카운터를 붙인다.
- 요청이 접수 → 카운터의 값 +1
- 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.
장점
- 메모리 효율이 좋다. 이해하기 쉽다.
- 윈도가 열릴 때 카운터가 초기화되는 방식은 특정 트래픽 패턴을 처리하기 적합함
단점
윈도 경계부분에 요청이 몰리면,제한하고 싶은 한도보다 많은 요청을 처리할 수 있음
이동 윈도 로그(Sliding window log)
요청의 타임스탬프를 추적. 타임스탬프 로그를 레디스 또는 정렬 집합 같은 캐시에 저장- 새 요청이 왔을 때, 캐시에 저장된 타임스탬프 중 만료된 타임스탬프는 제거.
- 새 요청의 타임스탬프를 로그(캐시)에 추가.
- 로그의 양이 허용치보다 같거나 작으면 요청을 수행. 허용치보다 많은 경우, 요청 처리 거부.
장점
- 정교하다. 모든 시점에서 시스템의 처리율 한도를 넘지 않는다.
단점
- 다량의 메모리 사용
- 거부된 요청의 타임스탬프도 보관하기 때문
이동 윈도 카운터(Sliding window counter)
현재 윈도우와 현재 시간을 보고, 들어온 요청의 비율을 따져서처리할지 판단하는 알고리즘.- ex) 윈도우 크기 1분일 때
- 현재 1분간의 요청 수 + 직전 1분간의 요청 수 * 이동 윈도(현재 요청으로부터 1분 간)와 직전 1분이 겹치는 비율
- ex) 윈도우 크기 1분일 때
장점
- 이전 윈도의 평균 처리율과 현재 윈도 상태를 측정해 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응
- 메모리 효율 좋다.
단점
- 직전 윈도(시간)에 도착한 요청이 균등하게 분포되어있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다.
- 클라우드플레어에서 수행한 실험에 의하면 이런 경우는 0.003%에 불과했다고 함.
카운터 저장 장소
DB는 디스크 접근 때문에 느림 → 메모리상에서 동작하는 캐시가 바람직
- Redis → INCR, EXPIRE 명령어 지원
- INCR: 메모리에 저장된 카운터 1증가
- EXPIRE: 카운터에 저장한 타임아웃 값 설정 → 만료되면 자동으로 삭제고정 윈도 카운터 알고리즘
3단계 상세 설계
처리율 한도 초과 트래픽의 처리
- 처리율 한도 초과 트래픽 처리HTTP 429 응답 (Too many requests): 어떤 요청이 한도 제한에 걸릴때 응답경우에 따라서 한도 제한에 걸린 메시지를 나중에 처리하기 위해 큐에 보관할 수 있다.
- 처리율 제한 장치가 사용하는 HTTP 헤더클라이언트가 자기 요청이 처리율 제한에 걸리고 있는지에 대한 정보를 아래 HTTP 헤더를 통해 전달한다.
처리율 제한 장치가 사용하는 HTTP Header
- X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청의 수
- X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
- X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림
분산 환경에서의 처리율 제한 장치 구현
- 경쟁 조건 (Race Condition) 발생 가능
- 경쟁 조건 문제를 해결할 수 있는 가장 쉬운 방법은 Lock이지만, 성능 이슈가 커진다.
- 이를 해결할 수 있는 다른 방안은
루아 스크립트와sorted set레디스 자료구조이다.- sorted set으로 어떻게 해결할 수 있을까?
- sorted set 에 특별한 기능이 있어서 경쟁 이슈를 해결하는 것은 아니다.
- Redis 의 경우 자료구조가
Atomic하기 때문에, 해당 Race Condition 을 피할 수 있다.
- sorted set으로 어떻게 해결할 수 있을까?
- 동기화
- 여러 대의 처리율 제한 장치를 사용할 경우 요청이 분산될 수 있다.
- 고정 세션 (sticky session)으로 해결할 수 있지만, 확장 가능하지 않고 유연하지 않기 때문에 권장하지 않는다.
- 성능 최적화
- 에지 서버로 트래픽 분산
- 최종 일관성 모델 사용
- 데이터 변경이 발생했을 때, 시간이 지남에 따라 여러 노드에 전파되면서 당장은 아니지만 최종적으로 일관성이 유지되는 것
- 동시성을 제공하지 않고 일관성을 갖는다.
- 모니터링
- 채택된 처리율 제한 알고리즘이 효과적인지?
- 정의한 처리율 제한 규칙이 효과적인지?
4단계 마무리
경성 또는 연성 처리율 제한
- 경성 처리율 제한 : 요청의 개수는 임계치를 절대 넘어설 수 없다.
- 연성 처리율 제한 : 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.
다양한 계층에서의 처리율 제한
- 애플리케이션 계층(OSI 7번 계층)에서의 처리율 제한 외에도 다른 계층에서 제어
- ex) Iptables를 사용하여 IP(OSI 3번 계층) 주소에 처리율 제한을 적용
처리율 제한을 회피하는 방법
- 클라이언트 측 캐시를 사용하여 API 호출 횟수 줄이기
- 처리율 제한의 임계치 이해, 짧은 시간 동안 너무 많은 메시지를 보내지 않도록 한다.
- 예외나 에러를 처리하는 코드를 도입하여, 클라이언트가 예외적 상황으로부터 우아하게 복구될 수 있도록 한다.
- 재시도 로직을 구현할 때는 충분한 백오프 시간을 두도록 한다.
참고
시도하고 More Do하는 백엔드 개발자입니다.