▲

GN⁺: Rate Limit 알고리듬을 시각화해서 알아보기

 (smudge.ai)
35P by neo 2달전 | favorite | 댓글 2개

왜 Rate Limit(사용량 제한)이 필요한가?

  • 많은 참여자가 있는 트위치 채팅에서 스패머 한 명이 있을 때, 사용량 제한이 없다면 스패머가 대화를 지배할 수 있음.
  • 사용량 제한을 통해 각 사용자가 공정하게 참여할 기회를 가질 수 있음.
  • Rate Limiter(사용량 제한기)는 특정 기간 동안 설정된 한도를 초과하는 요청을 차단하여 서비스의 트래픽을 제어함. 이는 채팅에서의 스팸 조절 외에도 유용함
  • 예를 들어, 로그인 폼에서 사용량 제한을 통해 브루트 포스 공격을 억제하면서도 소량의 잘못된 추측을 허용할 수 있음
  • API 엔드포인트도 종종 사용량 제한이 적용되어 단일 사용자가 리소스를 독점하지 못하게 함
    • 사용자가 비싼 API 엔드포인트를 분당 100번만 호출할 수 있도록 하면 카운터를 사용하여 분당 100번의 히트를 추적하고, 그 후의 요청은 차단
    • 이는 가장 간단한 사용량 제한 알고리듬 중 하나인 고정 윈도우 제한기(Fixed Window Limiter)임
    • 서비스 트래픽을 제어하는 일반적인 방법

Fixed windows 알고리듬

  • 고정된 시간 창(window) 내에서 요청 수가 제한됨
  • 각 시간 창의 시작에 요청 카운터가 0으로 재설정됨
  • 장점
    • 구현과 이해가 쉬움
    • 사용자에게 예측 가능함
  • 단점
    • 시간 창 끝 무렵에 요청이 시작되면 제한의 최대 2배까지 요청 폭증(burst)이 허용될 수 있음
  • 실제 사례: GitHub API는 시간당 5,000개의 요청을 허용하는 고정 시간 창 속도 제한기를 사용함
  • 시간 창의 시작 시간을 고정된 간격으로 설정하는 대신, 각 시간 창은 해당 시간 창 내에서 사용자의 첫 번째 요청 시점에 생성될 수 있음
  • 이 접근 방식에서는 다음 시간 창까지 남은 시간을 사용자에게 알려주는 것이 특히 중요함

슬라이딩 윈도우(Sliding windows) 알고리듬

  • 용량을 한 번에 모두 새로 고치는 대신, 슬라이딩 윈도우는 한 번에 하나의 요청씩 용량을 채움
  • 장점
    • 요청 트래픽의 분포를 부드럽게 함
    • 높은 부하에 적합함
  • 단점
    • 고정 시간 창보다 사용자에게 예측 가능성이 떨어짐
    • 각 요청의 타임스탬프를 저장하는 것은 리소스 집약적임
  • 높은 트래픽 시나리오에서 슬라이딩 윈도우가 가장 유용하기 때문에, 기본 알고리듬이 리소스 집약적이라는 사실은 역효과를 낳음
  • 따라서 대부분의 실제 슬라이딩 윈도우 속도 제한기는 근사 방식(approximation)을 사용함
  • 근사 방식은 이전 고정 시간 창에서 허용된 요청 수와 현재 고정 시간 창에서 허용된 요청 수를 계산하고, 이전 시간 창의 허용된 요청을 현재 시간에 끝나는 부동 시간 창과의 중첩에 비례하여 가중치를 부여함
  • 이 근사 방식은 요청을 거의 동일한 비율로 제한하지만 훨씬 더 효율적임
  • 실제 사례: Cloudflare의 구성 가능한 속도 제한기는 근사 슬라이딩 윈도우를 사용함

토큰 버킷(Token buckets) 알고리듬

  • 시간 창의 지속 시간 대신, 일정한 속도로 "토큰"으로 채워지는 버킷을 상상함
  • 각 요청은 이 버킷에서 하나의 토큰을 인출하고, 버킷이 비어 있으면 다음 요청이 차단됨
  • 버킷의 용량은 버스트가 지원할 수 있는 최대 요청 수를 나타냄
  • 보충 간격은 장기 평균 허용 요청 간격을 나타냄
  • 여러 개의 속도 제한기 없이 별개의 버스트 및 평균 용량을 가질 수 있다는 것이 이 알고리듬의 주요 이점 중 하나임
  • 장점
    • 높은 트래픽의 버스트를 허용하지만 장기 평균 요청 속도를 적용함
    • 사용자에게 더 유연하여 허용 가능한 범위 내에서 트래픽 급증을 허용함
  • 단점
    • 고정 시간 창보다 사용자에게 제한 사항과 보충 시간을 전달하기가 더 어려움
  • 실제 사례
    • Stripe는 사용자당 500개의 제한과 0.01초의 보충 간격을 가진 토큰 버킷을 사용하여 초당 100개의 요청을 지속적으로 허용하지만 최대 500개의 요청까지 버스트를 허용함
    • OpenAI의 GPT-3.5 무료 티어는 200개의 제한과 86400초/200의 보충 간격을 가진 토큰 버킷을 사용하여 하루에 200개의 요청으로 제한됨

레이트 리밋 적용 시 고려 사항

  • 레이트 리미터에 대한 영구 저장소를 만들어야 함
  • 영구 저장소에 대한 서버의 연결이 실패하면 요청을 차단하지 않고 모두 허용하도록 해야 함
  • 선택적으로 버스트 트래픽을 조절할 수 있음
  • 적절한 키를 선택해야 함 (사용자 ID, API 키 등)
  • 유용한 속도 제한 오류를 표시해야 함 (다음 요청까지 대기 시간, 429 HTTP 상태 코드, x-ratelimit-* 응답 헤더 등)
▲
humblebee 2달전  [-]

한글로 요약 된 글 읽고, '오케이 뭔지는 알겠는데 다 같은 내용 아닌가?' 라고 생각하며 원본 링크의 글을 읽으니 정말 잘 설명하고 시각화도 너무 만족스럽습니다! 👍👍👍

답변달기
▲
neo 2달전  [-]
Hacker News 의견

해커뉴스 댓글 모음 요약

  • 오랜 경험에서 얻은 추가 고려사항들:

    • Rate Limits: 백엔드 용량 문제를 해결하지 못함. 정책적 제한으로 간주해야 함.
    • Bad Traffic: 단순한 rate limits 외에 추가 조치를 고려해야 함. 인증 상태, 사용자/세션 우선순위 등을 기반으로 트래픽 우선순위를 정하는 것이 유용함.
    • Communication: 중요한 고객이나 내부 팀이 rate limits에 도달했을 때의 대응 방안을 준비해야 함.
    • Concertina Effects: 모든 고정 창 또는 많은 슬라이딩 창이 동시에 만료되는 것을 방지하기 위해 각 사용자/세션 창에 결정론적 오프셋을 추가해야 함.

  • 멀티테넌트 환경에서 DoS 공격을 방지하려면 공정 큐잉이 최적의 접근법임: 각 클라이언트에게 자체 큐를 할당하고, 백그라운드 루틴이 각 큐를 반복적으로 순회하며 요청을 처리함. 스팸 요청을 보내는 클라이언트는 자신의 큐만 혼잡하게 만듦.

  • 클라이언트 처리 코드 구현 경험: rate limit에 도달했을 때 최적의 백오프 전략에 대해 항상 궁금했음. 서비스 관점에서의 트레이드오프를 읽는 것이 흥미로웠음.

  • 축하 메시지: 짧은 콘텐츠에 대한 최고의 시각화로 매우 정보가 많고 요점이 잘 정리된 게시물임.

  • GCRA 알고리즘: rate limiting에 더 나은 알고리즘이라고 생각함. 더 널리 알려지고 사용되었으면 좋겠음.

  • 훌륭한 작업: 이 게시물에 많은 시간과 노력이 들어갔음을 느낄 수 있음. 잘했음.

  • AWS Lambda에서의 rate-limiting 문제: NodeJS에서 rate-limiting을 구현하려고 했으나, AWS Lambda에서는 타이머가 이상하게 작동하여 목표를 초과함. 로컬 테스트에서는 통과했지만 Lambda에서는 실패함. 타이머 문제인지 라이브러리 문제인지 불확실함.

  • Rate limiting 레이어가 포화 상태일 때의 대처: CF를 제외한 다른 옵션이 있는지 궁금함. 작은 VPS에서의 DoS 공격 방어에 nftable 규칙이 얼마나 효과적인지 궁금함.

  • 이 리소스가 필요했던 순간들: 경력 동안 여러 번 필요했던 리소스임. 이제 존재하게 되어 기쁨.

  • 데이터 시각화 팬: D3를 사용하고 있는지 궁금함.

답변달기