처리율 제한(Rate Limiting)에 관하여

처리율 제한 장치란?

• 클라이언트 or 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다
• 예시 : HTTP의 경우 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한하며 API 요청 횟수가 제한 장치에 정의돈 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단 된다

장점

• DoS 공격, 봇에서 오는 트래픽, 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러 자원 고갈을 방지하고 서버 과부화를 막는다
• 서버를 많이 두지 않고 우선순위에 따라 자원을 할당할 수 있어 비용을 절감한다

고려해야 하는 점

• 어디에 제한? 서버 or 클라이언트
• 어느 기준으로? 다양한 형태의 제어 규칙을 정의 할 수 있는 유연한 시스템
• 시스템 규모는? 스타트업 or 사용자가 많은
• 어떤 환경? 단일 or 분산환경 / 독립된 서비스 or 애플리케이션 코드에 포함
• 예외처리 : 차단된 경우 사용자에게 알림
• 설정된 처리율을 초과하는 요청 정확하게 제한, 낮은 응답시간, 적은 메모리 사용
• 분산형 처리율 제한(distributed rate limiting) : 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유
• 높은 결함 감내성(fault tolerance) : 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어선 안됨

어디에 제한?

• 클라이언트 : 쉡게 위변조가 가능하고 모든 클라이언트 통제가 어려울 수 있다
• 서버 : API 서버에 두거나 처리율 제한 미들웨어인 API 게이트웨이를 두어 API 서버로 가는 요청을 통제하도록 해야 한다
  • 이때, 프로그래밍 언어, 캐시 서비스등 사용하고 있는 기술 스택을 고려하고 필요에 맞는 처리율 제한 알고리즘을 찾아야 한다

처리율 제한 알고리즘

토큰 버킷 알고리즘

• 토큰 버킷 : 지정된 용량을 갖는 컨테이너
• 사전 설정된 양의 토큰이 주기적으로 채워지며 꽉 찬 버킷에는 더 이상의 토큰이 추가되지 않고 버려진다(overflow)
• 처리될 때마다 요청당 하나의 토큰을 사용하며 요청 도착시 버킷에 충분한 토큰이 있는지 검사한다
  • 충분한 토큰이 있는 경우 : 버킷에서 토근을 꺼내 요청을 시스템에 전달함
  • 충분한 토큰이 없는 경우 : 요청은 버려짐
• 파라미터
  • 버킷 크기 : 최대로 담을 수 있는 토큰의 개수
  • 토큰 공급률 : 초당 몇개의 토큰이 버킷에 공급되는지
• 적용 기준
  • API 앤드포인트 or IP 주소 or 시스템의 처리율(모든 요청이 하나의 버킷 공유)
• 장점
  • 구현이 쉽다
  • 버킷 크기가 정해져 있어 효율적으로 메모리를 사용할 수 있다
  • 버킷에 남은 토큰이 있다면 시스템에 전달됨으로 짧은 시간에 집중되는 트래픽 처리가 가능하다
• 단점
  • 버킷 크기와 토큰 공급률을 튜닝하기가 어렵다

누출 버킷 알고리즘

• 요청 처리율이 정해져 있으며 요청이 도착하면 큐가 가득 차 있는지 확인 후 있다면 큐에 요청을 추가, 없다면 새 요청은 버린다
• 보통 FIFO로 구현하며 정해진 시간마다 요청을 꺼내어 처리한다
• 파라미터
  • 버킷 크기 : 처리될 항목들이 보관된 큐의 크기
  • 처리율 : 보통 초 단위로 표현되는 시간당 몇 개의 항목을 처리할 지에 대해 정해진 값
• 장점
  • 큐의 크기가 제한되어 있어 메모리를 효율적으로 사용할 수 있다
  • 고정된 처리율을 가지고 있어 안정적인 출력이 가능하다
• 단점
  • 단시간에 트래픽이 몰리고 제때 처리하지 못한다면 오래된 요청은 남고 최신 요청들은 버려진다
  • 버킷 크기와 처리율을 튜닝하기가 어렵다

고정 윈도우 카운터 알고리즘

• 타임라인을 고정된 간격의 윈도우로 나누고 각 윈도우에 카운터를 붙인다
• 요청이 접수될 때마다 카운터의 값을 1씩 증가하고 임계치에 도달하면 새로운 요청은 새 윈도우가 열릴 때 까지 버려진다
• 장점
  • 메모리 효율이 좋고 이해하기 쉽다
• 단점
  • 윈도우 경계 부근에 많은 트래픽이 갑자기 몰리면 할당된 양보다 더 많은 요청이 처리 될 수 있다

이동 윈도우 로깅 알고리즘

• 요청의 타임스탬프를 추적해 캐시(보통 Redis의 sorted set)에 보관하여 로그를 남긴다
• 새 요청이 오면 현재 윈도의 시작 시점보다 오래된 타임스탬프는 제거한다
• 로그의 크기가 허용치 보다 같거나 작으면 요청을 시스템에 전달하고 그렇지 않으면 처리를 거부한다
• 장점
  • 윈도우 경계 부근에 트래픽이 집중되는 경우에도 정교하게 처리율 제한이 넘지 않을 수 있다
• 단점
  • 모든 요청을 로깅함으로 다량의 메모리를 사용한다

이동 윈도우 카운터 알고리즘

• 고정 윈도우 알고리즘과 이동 윈도우 로깅 알고리즘을 결합하여 문제점을 보완한 것
• 현재 1분간의 요청 수 + 직전 1분간의 요청 수 * 이동 윈도우와 직접 1분이 겹치는 비율
• 카운터의 경우 메모리상에서 동작하는 캐시가 빠르고 만료 정책을 지원함으로 여기에 저장하자
• 장점
  • 짧은 시간에 몰리는 트래픽 대응이 가능하다
  • 메모리 효율이 높다

출저
알렉스 쉬 Alex Xu, 『가상 면접 사례로 배우는 대규모 시스템 설계 기초』, 이병준 옮김, 인사이트(2021), p51-74.