#04. 처리율 제한 장치의 설계

4장. 처리율 제한 장치의 설계

처리율 제한 장치

• rate limiter
• 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치
• ex. HTTP: 특정 기간 내에 전송되는 클라이언트의 요청 횟수 제한. (정해진 임계치 넘어서면 추가로 도달한 모든 호출은 처리 중단block)

API에서 처리율 제한 장치를 두면 좋은 점

• DoS(Denial of Service) 공격에 의한 resource starvation 방지
  • 추가 요청에 대한 처리를 중단함으로써 Dos 방지
• 비용 절감
  • 우선순위가 높은 API에 더 많은 자원 할당 가능
  • third-party API에 사용료를 지불하고 있는 회사들에게 아주 중요
• 서버 과부하 방지
  • bot에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽 방지

1. 1단계 문제 이해 및 설계 범위 확정

예제. 요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한
• 낮은 응답시간: 처리율 제한 장치는 HTTP 응답시간에 나쁜 영향을 주어선 X
• 가능한 한 적은 메모리
• 분산형 처리율 제한(distributed rate limitimg)
  • 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 함
• 예외 처리
  • 요청이 제한되었을 때 그 사실을 사용자에게 분명하게 표시
• 높은 결함 감내성(fault tolerance)
  • 제한 장치에 장애가 생겨도 전체 시스템에 영향을 주어선 X

2. 2단계 개략적 설계안 제시 및 동의 구하기

처리율 제한 장치는 어디에 둘 것인가?

• 클라이언트 측
  • 클라이언트는 일반적으로 처리율 제한을 안정적으로 걸 수 있는 장소가 X
  • 클라이언트 요청은 쉽게 위변조가 가능
  • 모든 클라이언트의 구현을 통제하는 것이 어려움
• 서버 측
• 처리율 제한 middleware
  • middleware로 하여금 API 서버로 가는 요청을 통제
  • ex. 클라우드 마이크로서비스 API gateway: SSL termination, authentication, IP허용 목록(whitelist) 관리 등을 지원하는 완전 위탁관리형 서비스
• 정답은 X
  • 회사의 현재 기술 스택이나 엔지니어링 인력, 우선순위, 목표에 따라 달라질 수 있음

처리율 제한 알고리즘

• 토큰 버킷 알고리즘
  • 간단, 높은 이해도, 보편적 사용(ex. 아마존, 스트라이프)
  • 토큰 버킷: 지정된 용량을 갖는 컨테이너
  • 토큰 공급기(refiller): 사전 설정된 양의 토큰을 주기적으로 버킷에 추가
  • 토큰이 꽉 찬(overflow) 버킷에는 더 이상 토큰 추가 X
  • 각 요청은 처리될 때마다 하나의 토큰을 사용
    • 충분한 토큰이 있는 경우, 버킷에서 토큰 하나 꺼낸 후 요청을 시스템에 전달
    • 토큰이 없는 경우, 해당 요청은 dropped
  • 2개의 parameter
    • 버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수
    • 토큰 공급률(refill rate): 초당 몇 개의 토큰이 버킷에 공급되는가
  • 몇 개의 버킷 사용?
    • 통상적으로 API endpoint마다 별도의 버킷을 둠
    • IP 주소별로 처리율 제한을 적용해야한다면, IP 주소마다 버킷을 하나씩 할당
    • 처리율을 초당 N개 요청으로 제한하고 싶다면, 모든 요청이 하나의 버킷을 공유해야함
  • 장점
    • 간단한 구현, 효율적인 메모리 사용
    • 짧은 시간에 집중되는 트래픽(burst of traffic)도 처리 가능
  • 단점
    • 버킷 크기, 토큰 공급률 두 개의 parameter를 적절하게 튜닝하는 것이 까다로움
• 누출 버킷 알고리즘 leaky bucket
  • 토큰 버킷 알고리즘과 달리, 요청 처리율이 고정
  • FIFO Queue로 구현
  • 동작 원리
    • 요청이 도착하면 Queue가 가득 차 있는지 확인.
    • 빈자리가 있는 경우에는 Queue에 요청 추가
    • Queue가 가득 차 있는 경우에는 새 요청은 버림
    • 고정된 속도로 Queue에서 요청을 꺼내어 처리
  • 2개의 parameter
    • 버킷 크기: 큐 사이즈
    • 처리율(outflow rate): 지정된 시간당 몇 개의 항목을 처리할지 지정 (초 단위)
  • ex. Shopify
  • 장점
    • Queue의 크기 제한됨. 효율적인 메모리 사용량
    • 고정된 처리율: 안정적 출력(stable outflow rate)이 필요한 경우에 적합
  • 단점
    • 단시간에 많은 트래픽이 몰리는 경우 Queue에는 오래된 요청들이 쌓임.
    • 요청을 제때 처리 못하면 최신 요청들 버려짐
    • 두 개의 인자 튜닝 까다로움
• 고정 윈도 카운터 알고리즘 fixed window counter
  • 동작 원리
    • timeline을 고정된 간격의 window로 나눔
    • 각 window마다 counter를 붙임
    • 요청이 접수될 때마다 counter++
    • counter값이 사전에 설정된 threshold에 도달 시, 새로운 요청은 새 windowr가 열릴 때까지 버려짐
  • 장점
    • 메모리 효율 굳, 이해하기 쉬움
    • window가 닫히는 시점에 counter를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합
  • 단점
    • window의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우, window에 할당된 양보다 더 많은 요청이 처리될 수 있음
• 이동 윈도 로깅 알고리즘
  • 고정 윈도 카운터 알고리즘의 문제점 해결
  • 동작 원리
    • 요청의 timestamp 추적
    • 현재 window의 시작 지점보다 오래된 timestamp를 가졌을 경우, 만료
    • 새 요청이 오면 만료된 timestamp 제거
    • 새 요청의 timestamp를 log에 추가
    • log의 크기 <= 허용치, 요청 시스템에 전달
    • log의 크기 > 허용치, 처리 거부
  • 장점
    • 정교한 알고리즘
    • 어느 순간의 window를 보더라도 허용되는 요청의 개수가 시스템의 처리율 한도를 초과 X
  • 단점
    • 다량의 메모리 사용
    • 거부된 요청의 timestamp도 보관하기 때문
• 이동 윈도 카운터 알고리즘 sliding window counter
  • fixed window counter + sliding window logging
  • 현재 window에 온 요청 수 계산법
    • 현재 1분간의 요청 수 + (직전 1분간의 요청수 x 이동 window와 직전 1분이 겹치는 비율)
  • 장점
    • 이전 시간대의 평균 처리율에 따라 현재 window의 상태를 계산 → 짧은 시간에 몰리는 트래픽에도 잘 대응
    • 좋은 메모리 효율
  • 단점
    • 직전 시간대에 도착한 요청이 균등하게 분포되어있다고 가정한 상태에서 추정치 계산 → 다소 느슨
    • but, 위 단점이 생각만큼 심각하지 않음: Cloudflare의 실험에 따르면 40억 개의 요청 가운데 시스템의 실제 상태와 맞지 않게 허용되거나 버려진 요청은 0.003%에 불과했음

개략적인 아키텍처

• 얼마나 많은 요청이 접수되었는지를 추적할 수 있는 counter를 추적 대상별로 두고
  • 추적 대상: 사용자, IP 주소, API endpoint, 서비스
• 이 counter의 값이 어떤 한도를 넘어서면 한도를 넘어 도착한 요청은 거부
• counter는 어디에 보관?
  • DB: 디스크 접근 때문에 느림
  • 메모리상에서 동작하는 캐시가 바람직 (빠름, 시간에 기반한 만료 정책 지원)
  • ex. Redis: INCR, EXPIRE 두 가지 명령어 지원
    • INCR: 메모리에 저장된 카운터의 값 1씩 증가
    • EXPIRE: 카운터에 타임아웃 값 설정, 설정된 시간 지나면 카운터 자동으로 삭제
• 동작 원리
  • 클라이언트가 rate limiting middleware에게 요청 보냄
  • 미들웨어는 Redis의 지정 버킷에서 counter 가져와서 한도에 도달했는지 검사
    • 한도에 도달했으면 요청 거부
    • 도달하지 않았다면 요청은 API 서버로 전달, 미들웨어는 카운터의 값 증가시킨 후 다시 Redis에 저장

3. 3단계 상세 설계

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되는가?
• 처리가 제한된 요청들은 어떻게 처리되는가?

처리율 제한 규칙

• Lyft의 처리율 제한 오픈 소스

  domain: messagaing
  descriptors:
    - key: message_type
      Value: marketing
      rate_limit:
        unit: day
        requests_per_unit: 5

• 이런 규칙들은 보통 configuration file 형태로 디스크에 저장

처리율 한도 초과 트래픽의 처리

• 어떤 요청이 한도 제한에 걸리면 API는 HTTP 429 응답 (too many requests)을 클라이언트에 보냄
• 한도 제한에 걸린 메시지를 나중에 처리하기 위해 큐에 보관할 수도
• 처리율 제한 장치가 사용하는 HTTP 헤더
  • 클라이언트가 자기 요청이 throttle 하는지 어떻게 감지?
  • 자기 요청이 처리율 제한에 걸리기까지 얼마나 많은 요청을 보낼 수 있는지 어떻게 감지?
  • X-Ratelimit-Remaining: window 내에 남은 처리 가능 요청의 수
  • X-Ratelimit-Limit: 매 window마다 클라이언트가 전송할 수 있는 요청의 수
  • X-RateLimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

분산 환경에서의 처리율 제한 장치의 구현

• 단일 서버를 지원하는 처리율 제한 장치를 구현하는 것은 어렵지 않다. but, 여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 어려움
  • race condition
  • synchronization
• race condition
  • 두 개 요청을 처리하는 thread가 병렬로 counter값 읽고 수정하는 경우
  • 해결책
    • lock → but, lock은 시스템의 성능을 상당히 떨어뜨림
    • 루아 스크립트(Lua Script)
    • 정렬 집합(sorted set)이라 불리는 레디스 자료구조 사용
• synchronization
  • 수백만 사용자를 지원하려면, 여러 대의 처리율 제한 장치 서버를 두어야함
    → 처리율 제한 장치 간 동기화 필요
  • 해결책
    • sticky session 활용하여 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치로 보낼 수 있도록 하는 것 (추천X, 확장 가능성X)
    • 중앙 집중형 데이터 저장소 사용 (ex. 레디스)
• 성능 최적화
  • 여러 데이터 센터를 지원
    • 사용자의 트래픽을 가장 가까운 edge server로 전달하여 latency 감소
  • 최종 일관성 모델 사용 eventual consistency model
    • 제한 장치 간에 데이터를 동기화할 때
    • 키-값 저장소 설계의 데이터 일관성
• 모니터링
  • 처리율 제한 장치가 효과적으로 동작하고 있는지
    • 채택된 처리율 제한 알고리즘이 효과적인지
    • 정의한 처리율 제한 규칙이 효과적인지

4. 4단계 마무리

• 추가적으로 언급할 부분
  • 경성(hard)/연성(soft) 처리율 제한
    • 경성 처리율 제한: 요청 개수는 임계치 초과 X
    • 연성 처리율 제한: 요청 개수는 잠시 동안은 임계치 초과 X
  • 다양한 계층에서의 처리율 제한
    • 애플리케이션 계층에서의 처리율 제한을 살펴본 것
    • 다른 계층에서도 처리율 제한이 가능
    • ex. Iptables: IP주소(OSI 3번 계층)에 처리율 제한 적용
  • 처리율 제한을 회피하는 방법
    • 클라이언트를 어떻게 설계하는 것이 최선?
    • 클라이언트 측 캐시를 사용해 API 호출 횟수 ⬇️
    • 예외나 에러를 처리하는 코드를 도입하여 클라이언트가 예외적 상황으로부터 gracefully 복구될 수 있도록
    • retry 로직을 구현할 때는 충분한 back-off 시간 두기