처리율 제한 장치, Rate Limiter

처리율 제한 장치 설계

네트워크 시스템에서 처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다.

역할

• Dos 공격에 의한 자원 고갈을 방치
• 더 많은 서버를 두지 않아도 되어 비용 절감
• 서버 과부하를 방지

범위 설정

• 클라이언트 측 제한 장치인지, 서버 측 제한 장치인지
  • 서버 측 제한 장치를 설계해야 함
• 어떤 기준으로 API 호출을 제어해야할지 (IP 주소, 사용자 ID )
  • 다양한 제어 규칙을 정의할 수 있도록 해야하는지
• 시스템 규모는 어느정도를 감안해야 하는지
  • 대규모 요청을 처리할 수 있어야 함
• 시스템이 분산환경에서 동작해야 하는지
  • 분산 환경에서 동작해야 함
• 처리율 제한 장치는 독립된 서비스인지, 애플리케이션 코드에 포함되어야 하는지
• 사용자의 요청이 처리율 제한 장치에 걸러진 경우, 사용자에게 그 사실을 알려야하는지
  • 429 Too Many Request

요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한한다
• 낮은 응답 시간 : 응답시간에 영향을 주면 안된다
• 가능한 적은 메모리를 사용해야 한다
• 분산형 처리율 제한 : 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 한다
• 예외 처리 : 요청이 제한되었을 때 사용자에게 알려야 한다
• 높은 결함 감내성 : 제한 장치에 장애가 생기더라도, 전체 시스템에 영향을 주면 안된다

접근

• 일반적으로 rate limiter는 API Gateway라고 불리는 컴포넌트에서 구현됨
• rate limiter를 API Gateway에 두어도 되고, 직접 서버에 추가해도 됨
• 외부 시스템을 사용하는 경우, 어떤 알고리즘을 사용할지 선택지가 제한될 수 있음

알고리즘

token bucket

• 지정된 용량을 가지는 컨테이너
• 사전 설정된 양의 토큰이 주기적으로 채워짐
• 버킷의 최대 용량, 일정한 주기마다 추가되는 일정한 갯수의 토큰
• 최대 용량을 넘어가는 토큰은 버려짐
• 각 요청은 하나의 토큰을 사용함
• 요청이 들어오면, 토큰이 충분한지 확인하고, 하나를 꺼내고, 요청을 시스템에 전달함
• 토큰이 없는 경우, 해당 요청은 버려짐
• 인자 2가지
  • 최대 토큰 갯수
  • 초당 몇 개의 토큰이 추가되는지
• 적용
  • 일반적으로 API Endpoint마다 별도의 토큰을 둔다
  • 시스템 전체의 처리율을 10,000개로 제한하고 싶다면, 모든 요청이 하나의 토큰을 공유하도록 처리한다
• 장점
  • 단순하고, 메모리 사용이 호율적이고
  • 짧은 시간에 집중되는 트래픽 대응 가능leaky bucket
• 주로 FIFO Queue로 구현한다
• 요청이 도착하면 큐가 가득 차 있는지 확인한다
• 빈 자리가 있는 경우에는 큐에 요청을 추가한다
• 큐가 가득 차 있는 경우는 새 요청은 버린다
• 지정된 시간마다 큐에서 요청을 꺼내어 처리한다
• 인자
  • 최대 토큰 갯수 = Queue Size
  • 초당 몇 개의 요청을 처리하는지 (고정된 값)
• 장점
  • 제한된 큐의 사이즈로 메모리 사용량이 효율적이다
  • 고정된 처리율을 가지고 있어, 안정적으로 출력할 수 있다
• 단점
  • 단시간에 많은 트레픽이 몰리는 경우, 최신 요청들은 모두 버려진다.

fixed window counter

• 타임라인을 고정된 간격의 윈도우로 나누고, 각 윈도우마다 counter를 붙인다
• 요청이 접수되면 이 카운터의 값은 1씩 증가한다
• 카운터의 값이 임계치에 도달하면 새로운 요청은 임계치가 열릴 때까지 버려진다
• 단점
  • 타임라인 윈도우의 경계부근에서는, 각 윈도우의 counter * 2에 가까운 요청이 몰린다

sliding window log

• 새 요청이 들어오면 timestamp를 추적함
• timestamp는 redis의 sorted set으로 저장함
• 새 요청이 들어오면 만료된 타임스템프를 제거함
• 만료의 기준 : 현재의 타임 윈도우보다 오래된 시간에 들어온 요청
• 장점
  • 어느 순간도 허용된 크기 이상의 요청을 처리하지 않음
• 단점
  • timestamp를 저장해서 메모리 사용량이 증가함

sliding window counter

• fixed window counter + sliding window log
• fixed에서 단위 시간당 처리량을 비율로 계산함
  • 현재 단위 시간의 요청 수 + 직전 1분간 요청수 * 직전 1분과 겹치는 비율
• 장점
  • timestamp를 기준으로 저장하지 않아서 메모리 사용량이 좋고
  • timestamp 기준 시간이 바뀌는 구간에서도 처리율이 안정된다
• 단점
  • 비율에 기반한 다소 느슨한 처리방식

구현

• IP 주소 별 또는 API Endpoint 별로 처리율을 제한해야 함
• counter 정보를 DB가 아닌 메모리에 저장해야 빠르며, 보통 Redis를 사용해서 구현함
• Redis는 2가지 명령어를 제공함
  • increase : 메모리에 저장된 카운터 1 증가
  • expire : counter에 timeout 설정. timeout이 지나면 자동으로 삭제.
• 클라이언트 - Rate Limiter(Redis) - My Service

429 Too Many Request

• 요청이 거절된 경우, 헤더에 정보 추가
  • x-rate-limit-remaining : 남은 요청 수
  • x-rate-limit-limit : 매 윈도우마다 클라이언트가 처리할 수 있는 수
  • x-rate-limit-retry-after : 몇 초 뒤에 다시 요청을 보내야 하는지

경쟁 조건

• 동시성 문제가 발생할 수 있음
• 락으로 해결할 수 있지만, 락을 걸면 시스템 성능이 상당히 나빠짐
• 대안 2가지
  • 루아 스크립트
  • redis : sorted set 사용

동기화

• 여러 대의 처리율 제한 장치 사이의 동기화
• 쉬운 방법 : sticky session
  • 규모에서 확장가능하지 않고, 유연하지 않음
• 적절한 대안 : 여러개의 처리율 제한 장치에서 중앙 집중된 redis를 사용하기

TODO

• rate limiter의 알고리즘은 파악함
• 동시성과 동기화의 문제를 모두 redis에 위임함

Reference

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초 4장