📕 목차

1. 처리율 제한 장치(Rate Limiter)
2. 토큰 버킷 알고리즘
3. 누출 버킷 알고리즘
4. 고정 윈도 카운터 알고리즘
5. 이동 윈도 로깅 알고리즘
6. 이동 윈도 카운터 알고리즘
7. 개략적인 설계
8. 분산 환경 처리율 제한 장치
9. 추가로 고려해볼 것들

1. 처리율 제한 장치(Rate Limiter)

 

📌 필요성
  • DoS(Denial of Service) 공격에 의한 자원 고갈 방지
  • 불필요하게 서버를 많이 두지 않아도 되므로 비용 절감
    • 특히 유료 외부 API 호출하는 API에 대해서 과금 횟수 절감
  • 서버 과부화 방지

 

나도 전화번호로 인증 코드를 송신하는 API가 있는데, 해당 API에 처리율 제한 장치를 마련해두었다.

 

📌 일반적인 요구 사항
  • 설정된 처리율을 초과하는 요청은 정확하게 제한한다.
  • 낮은 응답 시간
  • 가능한 한 적은 메모리 사용
  • 분산형 처리율 제한: 하나의 처리율 제한 장치를 여러 서버, 혹은 프로세스에서 공유 가능해야 한다.
  • 예외 처리: 요청이 제한되면 사용자에게 분명히 보여주어야 한다.
  • 높은 결함 감내성(fault tolerance): 제한 장치에 장애가 생겨도 전체 시스템에 영향을 주지 않아야 한다.

 

📌 처리율 제한 장치를 어디에 둘 것인가?
💡 정답이 없다. 프로젝트 기술 스택, 엔지니어링 인력, 우선순위, 목표에 따라 달라진다.

클라이언트 측에서도 쓰로틀링이나 디바운스를 사용해 처리율 제한을 걸긴 하지만, 클라이언트 요청은 쉽게 위변조가 가능하며, 모든 클라이언트 구현을 통제하긴 힘들다.

 

서버 측에 처리율 제한 장치

  • 프로그래밍 언어, 캐시 서비스 등 현재 사용 중인 기술 스택이 서버 측 구현을 지원하기 충분할 정도로 효율이 높은지 검토해야 한다.
  • 처리율 제한 알고리즘을 자유롭게 선택할 수 있다.
  • 충분한 개발 인력과 시간이 있는지 고려해야 한다.
  • (내 생각) API에 비지니스 로직이 아닌 처리율 제한 로직이 포함되는 게 올바른지 모호하다.

 

미들웨어에 처리율 제한 장치

  • 마이크로서비스 기반의 설계이며, 사용자 인증과 IP 허용 목록 관리 등을 처리하기 위해 API GW를 이미 설계에 포함시켰다면, 처리율 제한 기능 또한 GW에 포함시켜야 할 수도 있다.
    • API Gateway: 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 등을 지원하는 완전 위탁 관리형 서비스 (클라우드가 유지 보수 담당)
  • 구현이 간단하고 쉽지만, 선택지는 제한될 수 있으며 세부적인 알고리즘을 구현하기 힘들다.
  • 추가 비용이 들어감

 

실제로 내가 만들던 서비스도 IP와 전화번호에 대해 5회 이상 요청 시, 24시간 이후에 요청이 가능하게 만들고 싶었는데 AWS API Gateway는 이렇게 디테일한 설정을 못 하는 것 같다.

내가 못 찾은 걸 수도...

 

📌 처리율 제한 알고리즘
  • 토큰 버킷(token bucket)
  • 누출 버킷(leaky bucket)
  • 고정 윈도 카운터(fixed window counter)
  • 이동 윈도 로그(sliding window log)
  • 이동 윈도 카운터(sliding window counter)

 

🤔 궁금한 점 

찾아보니 Ngnix로도 처리율 제한이 가능하다고 한다.

AWS Api GW는 토큰 버킷 알고리즘을 사용하는데 반해, Ngnix는 누출 버킷 알고리즘을 사용한다고 한다.

이 외에도 Spring Boot와 같은 애플리케이션 단에서 라이브러리를 활용해 직접 알고리즘을 구현하는 경우도 흔하게 볼 수 있었다.

 

그럼 각각의 '장/단점이 무엇이 있을까?'에 대한 질문이 남았는데, 아래 블로그에서 친절히 설명해주고 있다.

 

처리율 제한 장치 붙이기 여정

운영 업무만 처리하고 있던 기간에 처리율 제한 장치 업무가 들어왔다.팀에서 사용하지 않았던 기술이라 검토부터 적용까지 스스로 해나아간 과정들이 즐거워서 실수들이 있었지만 배포가 끝

velog.io

  AWS API Gateway Ngnix Reverse Proxy Opensource API Gateway Application Level Gateway
기능 • 아마존에서 제공하는 완전 관리형 서비스
• 수신한 API 호출과 전송한 데이터 양에 대해서 과금
• 토큰 버킷 알고리즘		 • Ngnix conf 파일 설정
• 누출 버킷 알고리즘		 • 오픈 소스 API 사용
• MSA 관리 서비스도 제공
 • 애플리케이션에서 라이브러리 활용
• 토큰 버킷 알고리즘
추가 비용 ✅ ❌ 추가 인스턴스 비용 (+ 라이브러리 비용) Redis 비용
장점 • 쉽게 구현 • 설정 단순
 • 설치가 쉽고, 확장 용이
• 다양한 공개 플러그인 지원
 • 추가 서버 구축 불필요
• 단순 처리율 제한인 경우
단점 • 비용 추가
• 람다 scaling 지연에 따른 오류 발생 가능성
 • 세밀한 제어 힘듦 • 인스턴스 최소 요구사항: 4core, 16GB RAM • 분산 시스템이면 외부 cache 저장소 필요
• 참고할 레퍼런스 적음
• WAS 운영 코드에 처리율 제한 관심사 포함됨
라이브러리     Kong, KrakenD, Tyk Bucket4J, Guava, RateLimitJ

 

  • Gateway를 쓸까? LoadBalancer를 쓸까?
    • GW는 보안 및 전달이 목적이고, LB는 성능 및 가용성이 목적이라 이것만 따지면 GW가 맞지 않을까 싶다.

 

2. 토큰 버킷 알고리즘

 

📌 원리

  • 가장 보편적으로 사용되는 방법
  • 버킷에 토큰을 주기적으로 채우고, 요청을 처리하려면 토큰이 존재해야 함.
    • 요청 한 개를 처리하면 토큰도 한 개 소모
    • 토큰이 없으면 요청은 버려짐

 

📌 버킷 사용 기준
  • 통상적으로, API 엔드포인트마다 별도의 버킷을 둔다.
  • IP 주소별로 처리율 제한을 적용해야 하면, IP 주소마다 버킷을 하나씩 할당한다.
  • 시스템 전체 처리율을 제한하고 싶다면, 하나의 버킷을 공유하도록 한다.

 

📌 장점
  • 구현 쉬움
  • 효율적인 메모리 사용
  • 짧은 시간에 집중되는 트래픽(burst of traffic)도 처리 가능

 

📌 단점
  • 버킷 크기와 토큰 공급률이라는 두 개의 인자를 적절하게 튜닝하는 게 까다로울 수 있다.

 

🤔 궁금한 점 
  • 만약 하나의 API에 두 개의 조건이 필요하다면, 버킷도 두 개의 조건 별로 따로 만들고 모두에게서 토큰을 발급 받아야 하는 건지?
    • ex. IP 혹은 전화번호 일일 5회 이상 요청 제한
  • 토큰을 정기적으로 채우지 않고, 특정 시점에 채울 수는 없는지? (아니면 다른 알고리즘이 더 효과적이려나?)
    • 토큰이 모두 소모되지 않은 경우엔 24시간마다 공급
    • 토큰이 모두 소모된 경우에는 마지막으로 토큰이 소비된 시점에서 24시간 후에 공급

 

3. 누출 버킷 알고리즘

 

📌 원리

  • 요청 처리율이 고정 → FIFO 큐로 구현
  • 큐에 공간이 있으면 큐에 삽입하고 없으면 버린다. → 지정된 시간마다 큐에서 요청을 꺼내서 처리

 

📌 장점
  • 큐의 크기가 제한되어 있어 메모리 사용량 효율 향상
  • 고정된 처리율을 갖고 있으므로 안정적 출력(stable outflow rate)이 필요한 경우 적합

 

📌 단점
  • 단시간에 많은 트래픽이 몰려 큐의 오래된 요청을 빠르게 처리하지 못하면, 최신 요청은 모두 버려진다.
  • 두 개의 인자(버킷 크기, 처리율)를 올바르게 튜닝하는 게 까다로울 수 있다.

 

🤔 궁금한 점 
  • API를 경량화해서 요청을 처리하는 속도를 더 빠르게 만드는 게 아니라, 요청이 진입하는 속도를 늦추면 리스크가 크지 않을까? 언제 이런 방식이 효과적일지 잘 모르겠다.

 

4. 고정 윈도 카운터 알고리즘

 

📌 원리

  • 타임라인을 고정된 간격으 윈도(window)로 나누고, 각 윈도마다 카운터를 센다.
    • 요청이 접수될 때마다 카운터 1씩 증가
    • 현재 카운터의 값이 사전 설정된 임계치(threshold)에 도달하면, 새로운 요청은 다음 윈도가 열릴 때까지 버려진다.
  • 윈도 경계 부근에 순간적으로 많은 트래픽이 집중되면, 할당된 양보다 더 많은 요청이 처리될 수 있다는 문제가 있다.
    • 위 그림처럼 5개/분의 처리 윈도우에서 2:00:30~2:31:30 사이에 10개/분의 처리 속도를 보인다.
    • 이동 윈도 로깅 알고리즘에서 해결

 

📌 장점
  • 메모리 효율 증가
  • 이해 쉬움
  • 윈도우가 닫히는 시점에 카운터 초기화 하는 방식은 특정 트래픽 패턴을 처리하기 적합

 

📌 단점
  • 윈도 경계 부근에서 일시적으로 트래픽이 많이 몰리면, 예상 시스템 처리 한도보다 많은 양을 처리해야 함

 

🤔 궁금한 점 
  • 특정 트래픽 패턴이 어떤 경우를 말하는 거지?
    • 아마도 트래픽이 몰릴 경우를 예상해 잠깐 동안은 임계치를 살짝 넘어서도록 조정한다던가..그런 게 아닐까

 

5. 이동 윈도 로깅 알고리즘

 

📌 원리

  • 요청의 타임스탬프 추적 → 캐시 저장(레디스의 정렬 집합)
  • 새 요청이 오면 만료된 타임스탬프(현재 윈도 시작 시점보다 오래된 값) 제거
  • 로그 크기가 허용치보다 같거나 작으면 요청을 시스템으로 전달하고, 아니면 버림

 

📌 장점
  • 어느 순간 윈도를 보더라도, 허용되는 요청 개수는 시스템 처리율 한도를 넘지 않는다.

 

📌 단점
  • 거부된 요청의 타임스탬프도 보관하므로, 다량의 메모리를 사용한다.

 

🤔 궁금한 점 
  • 거부된 요청의 타임스탬프는 왜 보관하지?
    • 알고리즘 상으론 필요없지만, 요청 패턴 분석과 같은 정보를 위해 수집하는 게 아닐까 싶다.
    • 그런데 그건 다른 알고리즘도 마찬가지 아닌가..?
    • 알고리즘을 다시 살펴보니 1:00:50을 타임스탬프에 기록은 하지만 요청을 제한한다. 그렇다고 1:01:40이 들어왔을 때 해당 요청을 승인해주는 것도 아님. 이렇게 되면 정상적인 요청이 실패할 수도 있는데 왜 기록하는 거지?

 

 

From the AskComputerScience community on Reddit: Rate limiting - why log rejected requests' timestamps in Sliding window log alg

Explore this post and more from the AskComputerScience community

www.reddit.com

한참을 고민해도 모르겠어서 찾아보니 Redit에서도 저자가 실수한 게 아닐까란 의견이 지배적이었다.

 

6. 이동 윈도 카운터 알고리즘

 

📌 원리

  • 고정 윈도 카운터 알고리즘 + 이동 윈도 로깅 알고리즘
  • 1분 단위로 잘리는 게 아니라, 현재 시점이 직전 1분과 현재 1분의 어느 시점에 있는 지 고려함
    • 현재 윈도의 요청 개수를 판단할 때, 분당 평균 처리율까지 계산
    • 공식: 현재 1분 간의 요청수 + 직전 1분 간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율
    • 위 예시에 따르면 3 + 5 * 70% = 6.5개이므로, 반올림하면 7개가 된다.

 

📌 장점
  • 이전 시간대 평균 처리율에 따라 현재 윈도 상태를 계산하므로, 짧은 시간에 몰리는 트래픽에도 잘 대응
  • 메모리 효율 좋음

 

📌 단점
  • 직전 시간대 도착한 요청이 균등하게 분포되어 있음을 가정하고 있어, 다소 느슨하다.
    • Cloudflare가 실시했던 실험에 따르면 시스템의 실체 상태와 맞지 않게 허용되거나 버려진 요청은 40억 개 중 0.003%에 불과해서 심각한 상황은 아니다.

 

🤔 궁금한 점 
  • 메모리 효율이 더 좋은 이유가 뭐지?
    • 이동 윈도 로깅 방식은 로그를 계속 기록했지만, 이동 윈도 카운터 방식은 고정 윈도 카운터 방식과 마찬가지로 count 값만 누적해주면 된다. (이전 윈도 요청 횟수, 현재 윈도 요청 횟수)
    • 현재 요청을 기반으로 이전 윈도 가중치만 계산해주면 분당 허용 개수를 쉽게 알아낼 수 있으므로 메모리 효율이 좋다고 판단하는 듯?

 

7. 개략적인 설계

 

📌 카운터 보관장소

 

  • 메모리상에서 동작하는 캐시가 빠르고 시간에 기반한 만료 정책(TTL)을 지원하므로 바람직하다.
  • Redis에서 두 가지 명령어를 제공해준다.
    • INCR: 메모리에 저장된 카운터 값을 1 증가
    • EXPIRE:  카운터에 타임아웃 값 설정

 

📌 처리율 제한 규칙
 

GitHub - pusher/lyft-ratelimit: Go/gRPC service designed to enable generic rate limit scenarios from different types of applicat

Go/gRPC service designed to enable generic rate limit scenarios from different types of applications. - pusher/lyft-ratelimit

github.com

domain: <unique domain ID>
descriptors:
  - key: <rule key: required>
    value: <rule value: optional>
    rate_limit: (optional block)
      unit: <see below: required>
      requests_per_unit: <see below: required>
    descriptors: (optional block)
      - ... (nested repetition of above)
  • Lyft의 처리율 제한 오픈 소스를 보면, 어떤 규칙들이 사용되는지 참고하기 좋다.
  • 이런 규칙들은 보통 설정 파일(configuration file) 형태로 디스크에 저장된다.

 

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

  • 사용자가 너무 많은 요청을 보내면 429 too many requests 응답에 헤더를 보내주는 게 좋다.
    • X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청 수
    • X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청 수
    • X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면, 몇 초 뒤에 요청을 다시 보내야 하는 지 알림
  • 작업 프로세스(workers)는 수시로 규칙을 디스크에서 읽어 캐시에 저장
  • 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져오고, 마지막 요청의 타임스탬프는 레디스 캐시에서 가져온다.
  • 처리율 제한에 걸린 요청을 버릴 수도 있고, 메시지 큐에 보관할 수도 있다.

 

🤔 궁금한 점 

 

8. 분산 환경 처리율 제한 장치

 

📌 경쟁 조건
  • Redis는 싱글 스레드 환경(I/O 작업 등을 처리할 때만 백그라운드에서 멀티 스레딩)이라, 일반적으로 명령의 실행은 Atomic이 깨지지 않는다.
  • 그러나 counter를 조회하고 1 증가한 후에 덮어쓰는 작업을 하면, 병렬 스레드 환경에서 경쟁 조건이 발생할 수 있다.
  • Lock을 사용할 수도 있지만 성능 저하를 유발하니, 루아 스크립트(Lua Script)나, 레디스 자료 구조인 정렬 집합(sorted set)을 사용하면 된다.
    • 실제로 전에 분산락을 사용해봤는데, 처리 속도가 낙관적 락에 비해 6배나 오래 걸렸다.
    • 루아 스크립트를 사용하면 스크립트가 실행되는 동안 다른 명령어가 실행되지 않아, 경쟁 조건을 피할 수 있다. (참고 블로그) → 처리 속도가 늦어질 수 있긴 함. 따라서 짧게 끝나는 로직으로 작성하는 것이 중요
    • 정렬 집합을 사용하면 중복되지 않는 value로 score 순으로 데이터를 정렬할 수 있다. (참고 블로그)

 

📌 동기화
  • 처리율 제한 장치가 여러 대 있으면, 클라이언트가 다른 처리율 제한 장치로 요청이 갔을 때 올바르게 동작하지 않을 수 있다.
    • 고정 세션을 사용하면 구현은 쉽지만, 확장 가능하지도 않고 유연성도 떨어지며, LB 부하가 발생한다.
    • Redis같은 중앙 집중형 데이터 저장소를 사용하는 것이 낫다.

 

📌 성능 최적화

https://blog.cloudflare.com/counting-things-a-lot-of-different-things/

  • Edge Server: 서버를 지리적으로 가까운 곳에 두는 방법
  • 최종 일관성 모델(eventual consistency model)로 데이터 간의 정합성 보장
    • 최종 시점에는 항상 일관성이 맞는다는 의미

분산 시스템을 구성하려면 CAP 이론에 의해 일관성과 가용성 중 하나를 포기해야만 한다.

  • 클라이언트들이 변경된 데이터를 요청했을 때, 어떤 클라이언트는 최신 데이터, 어떤 클라이언트는 오래된 데이터를 받는 경우 (일관성이 깨짐)
  • 모든 서버가 동일한 데이터를 갖도록 동기화 하는 동안 클라이언트 접근을 막는 경우 (가용성 저하)

그런데 첫 번째 경우는 "언젠가 동기화가 되면", 모든 클라이언트가 동일한 데이터를 받을 수 있다.

즉, 최종 일관성이란 항목이 새롭게 업데이트되지 않는다는 전제가 있다면, 항목의 모든 읽기 작업이 최종적으로는 마지막으로 업데이트된 값을 반환함을 이론적으로 보장한다.

 

근데 이걸 만족시키기 위한 정답이 존재하질 않는다고 한다. ㅋ

 

📌 모니터링
  • 채택된 처리율 제한 알고리즘이 효과적인가
  • 정의한 처리율 제한 규칙이 효과적인가

만약, 트래픽이 급증했을 때 비효율적으로 동작한다면 트래픽 패턴에 따라 알고리즘을 변경할 것도 고려해봐야 한다.

 

8. 분산 환경 처리율 제한 장치

 

📌 경성(hard) 또는 연성(soft) 처리율 제한
  • 경성 처리율 제한: 요청 개수는 임계치를 절대 넘길 수 없다.
  • 연성 처리율 제한: 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.

 

📌 다양한 계층에서의 제한
  • Iptables를 사용하면 IP 주소에 처리율 제한을 적용할 수 있다. (OSI 3번 계층)

 

📌 처리율 제한 회피 방법 (클라이언트)
  • 클라이언트 측에 캐싱하여 API 호출 횟수를 줄이는 방법
  • 처리율 제한 임계치를 이해하고, 짧은 시간 동안 너무 많은 메시지를 보내지 않게 제한 (쓰로틀링, 디바운스)
  • 예외적인 상황으로부터 우아하게 복구될 수 있도록 처리
    • 예를 들어, 사본값을 가져오려다 실패하면 원본값을 가져오게 한다던가..뭐 그런 거 말하는 듯
  • 재시도 로직을 구현할 때는 충분한 백오프(back-off) 시간을 둔다.
저작자표시 비영리

티스토리툴바