Rate Limiter 설계

Rate Limiter 장치란:

• 트래픽의 처리율을 제한하는 장치
• 예로 HTTP 트래픽을 분당 몇 건만 처리할 수 있도록 하고, 이걸 넘어서는 요청은 버리도록 하는 시스템임.
• 많은 시스템이 Rete Limiter 를 사용한다. Google Docs API 는 분당 300 건의 읽기 요청만 허용하고, 트위터는 3시간 동안 300개의 트윗만 올릴 수 있도록 제한한다.

 

 

Rate Limiter 의 장점:

• Rate Limiter 를 통해서 DoS (Denial of Service) 공격에 대응할 수 있음
• 서버 과부하를 막을 수 있음.

 

 

Rate Limiter 문제 이해 및 설계 범위 확정:

• 다음은 이제 면접관과 소통하면서 어떤 Rate Limiter 를 설계해야하는지 파악하는 시나리오를 보자.
• 지원자: 어떤 종류의 Rate Limiter 를 설계해야할까요? 클라이언트 측 Rate Limiter 입니까? 아니면 서버 측 Rate Limiter 입니까?
  • Rate Limiter 도 종류가 있기 때문에 이걸 보다 명확하게 하기 위함임.
  • 클라이언트 측 Rate Limiter:
    • 특징: 애플리케이션이나 서비스를 사용하는 클라이언트에서 구현이 됨
    • 목적: 애초에 발생하는 네트워크 트래픽 양을 줄여서 서버 부하를 줄이기 위함임.
    • 예시: 모바일 앱 or Jquery API 호출 제한 (많은 앱들이 백엔드 API 를 호출할 때 Rate Limiter 를 사용하긴 함),
  • 서버 측 Rate Limiter:
    • 특징: API 게이트웨이, 로드 밸런서, 어플리케이션 서버, 별도의 서버 컴포넌트로 구현됨.
    • 예시: API Gateway, NGINX 와 같은 웹서버, Spring 과 같은 웹프레임워크, 클라우드 서비스 (Cloudflare의 Rate Limiting), 데이터베이스 시스템, 로드 밸런서, Istio
    • 계층별로 Rate Limiter 를 적용할 수 있고, 실제로 적용할 때는 여러 계층의 Rate Limiter 를 조합해서 사용하는게 일반적이다.
    • API Gateway 에서의 Rate Limiter:
      • 장점:
        • 중앙에서 관리할 수 있음.
        • 어플리케이션 코드 없이 관리 가능
        • 일관된 Rate Limiter 정책 사용
        • 쉽게 Rate Limiter 를 사용할 수 있음
        • 인증과 같은 API 관리 기능을 추가할 수 잇음.
      • 단점:
        • 추가적인 인프라 계층을 사용해야함.
        • API 마다 세밀한 Rate Limiter 를 적용하기가 어려울 수 있음
    • 웹 서버 (NGINX)
      • 특징: 일반적으로 API Gateway 와 같이 애플리케이션 서버 앞에 위치하여 트래픽을 필터링을 함. API Gateway 에서의 매커니즘과 유사함.
      • 장점:
        • 어플리케이션 코드 없이 적용 가능
      • 단점:
        • 웹 서버에 대한 지식 필요
        • Rate Limiter 에 대한 세밀한 제어 할 수 없음.
      • 웹 어플리케이션 프레임워크 (Spring)
        • 장점:
          • 유연하고 세밀한 Rate Limiter 로직 적용
        • 단점:
          • 분산 환경에서 적용하는게 어려움. 확장된 다른 서버들과 통계를 내서 Rate Limiter 를 적용하기 어려우므로.
      • 데이터베이스 시스템 (Redis)
        • 장점:
          • 분산 시스템에서 일관된 Rate Limiter 구현이 가능
          • 어플리케이션과 연계해서 세밀한 제어 가능
          • 높은 성능과 확장성 제공
        • 단점:
          • 복잡성이 있음
      • 클라우드 서비스 (Cloudflare):
        • 장점:
          • 대규모 DDOS 와 같은 보안 기능 제공
          • 글로벌 네트워크를 통한 트래픽 관리 기능 제공
        • 단점:
          • 서비스 비용 발생
          • 벤더 종속성 발생
      • 로드 밸런서:
        • 장점:
          • 트래픽 분산에서 Rate Limiter 적용 가능
          • 네트워크 레벨에서 가능
        • 단점:
          • 세밀한 제어 불가능
          • 세션 인식 불가능
      • 주로 Cloudflare 와 같은 대규모 DDoS 공격을 막는 Rate Limiter 를 설정하고, API Gateway 에서 일관된 Rate Limiter 를 적용한 후, 어플리케이션 계층 쪽에서 구체적으로 Rate Limiter 를 설정하는 방법을 많이 사용함.
• 면접자: 서버측 API 를 위한 장치를 설계한다고 가정해보자.
• 지원자: 어떤 기준을 사용해서 API 호출을 제어해야할까요? IP 주소를 사용해야하나요? 아니면 사용자 ID? 아니면 생각하는 다른 기준이 있습니까?
  • API 호출 제어에 대해서 사용하는 기준은 다음과 같다:
  • IP 주소:
    • 장점: 구현이 간단하며, 익명 사용자에 대해 효과적
    • 단점: 여러 사용자가 같은 IP 를 사용하는 문제도 있을 수 있음.
  • 사용자 ID:
    • 장점: 개별 사용자 단위로 정확한 제어가 가능
    • 단점: 인증된 사용자에게만 가능
  • API Key:
    • 장점: 애플리케이션 또는 서비스 단위로 제어가 가능
    • 단점: 키 관리를 해야하는 문제가 생김. 키 가 노출되는 경우
  • API 엔드포인트:
    • 장점: 특정 API 엔드포인ㅌ에 대한 제어를 하는 것
    • 단점: 복잡성 및 전체 시스템 관점에서의 제어는 아님.
• 면접관: 다양한 형태의 제어 규칙throttling rules) 를 정의할 수 있도록 하는 유연한 시스템이어야한다.
• 지원자: 시스템 규모는 어느 정도이어야 할까요? 스타트업 정도 회사인가? 아니면 대규모 기업을 위한 제품인가?
• 면접관: 설계할 시스템은 대규모 요청을 처리할 수 있어야한다.
• 지원자: 시스템이 분산 환경에서 동작해야하는건가?
  • 아무래도 어플리케이션 계층에서 설게를 해야하는건가, 아닌가? 이런 걸 명확하게 하려고 한 질문임.
• 면접관: 그렇다.
• 지원자: 이 Rate Limiter 는 어플리케이션 코드에 포함되어야하는가? 아니면 독립된 서비스로 구성되어야 하는가?
• 면접관: 그 결정은 본인이 알아서 하세요.
• 지원자: 사용자의 요청이 처리율 제한 장치에 의해 걸러진 경우, 사용자에게 알려줘야하는가?
  • 응답이 나가서 사용자에게 표시되는 것까지 생각해야함.
• 면접관: 그렇다.

 

 

요구사항을 정리해보자:

• 면접관의 질문읉 통해서 파악한 것:
  • Distributed Rate Limiter 를 만들어야함. 그러니까 하나의 Rate Limiter 가 여러 서비스나 프로세스에 공유될 수 있어야함.
  • 예외 처리가 필요함. Rate Limiter 에 의해 걸러진 요청에서는 응답을 보여줘야함.
  • 대규모 사용자를 위해서 적은 리소스로 관리할 수 있도록 해야함.
  • 서버 측 Rate Limiter 를 이용해야함.
  • 다양한 제한 규칙을 적용할 수 있어야하고, 유연해야한다.
• Rate Limtier 자체에서 중요한 요구사항:
  • Latency 를 길게 만들면 안됨.
  • Fault tolerance 가 있어야함. Rate Limiter 에 장애가 생기더라도 어플리케이션에 영향을 주면 안됨.
    • Fault Tolerance 는 시스템의 일부가 장애가 생기더라도 전체 시스템이 계속해서 정상적으로 작동함을 말함.
  • Reliability: Rate Limiter 의 기능인 핕터링을 온전히 잘 수행해야함.

 

 

Rate Limiter 알고리즘:

• 토큰 버킷 알고리즘:
  • 폭넓게 사용되는 알고리즘임. 아마존에서도 이를 사용함.
  • 토큰 버킷은 지정된 용량을 가지는 컨테이너이고, 지정된 양의 토큰이 주기적으로 다시 채워진다.
  • 꽉 찬 토큰은 추가로 오버해서 채워지지는 않음.
  • 각 요청은 처리될 때마다 하나의 토큰을 사용함.
  • 요청이 도착하면 해당 토큰이 있는지 검사하게 됨. 토큰이 있다면 토크을 하나 쓰게되고, 토크닝 없다면 해당 요청은 버려짐.
  • 이 알고리즘의 인자(parameter) 는 2개임:
    • 버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수
    • 토큰 공급률: 초 당 토큰이 버킷에 공급되는 개수
  • 통상적으로는 API 엔드포인트마다 별도의 버킷을 두는 식으로 사용됨.
  • IP 주소마다 이를 적용해야한다면, IP 주소마다 버킷을 하나씩 할당해야함.
  • 전체 시스템의 처리율을 제한하고 싶다면 하나의 버킷만 쓰면 됨.
  • 장점:
    • 구현이 쉽다.
    • 메모리 사용 측면에서도 효율적임.
    • 짧게 집중되는 트래픽에서도 처리 가능함.
  • 단점:
    • 버킷 크기와 토큰 공급률을 적절하게 튜닝하는 건 어렵다.
• 누출 버킷 알고리즘:
  • 요청을 담는 큐가 있음.
  • 큐에서 일정 시산마다 처리율에 따라서 요청을 꺼냄.
  • 큐가 가득차면 요청은 버려진다.
  • 인자는 두 개임:
    • 버킷 크기: 큐의 크기
    • 토큰 처리율: 초 당 몇개의 요청을 꺼내서 처리할지
  • 장점:
    • 큐로 제한이 되어 있기 때문에 메모리도 적게 씀.
    • 안정된 출력을 기대할 수 있음.
  • 단점:
    • 큐에 누적된 후 처리율에 따라서 요청을 처리해나가는 구조라서, Latency 가 길어질 수 있음.
    • 버킷 크기와 토큰 처리율을 올바르게 튜닝하는 건 어렵다.
• 고정 윈도 카운터 알고리즘:
  • 타임라인을 윈도우로 나뉜다. 그리고 각 윈도우마다 카운터가 붙음.
  • 카운터가 임계값만큼 올라가면, 새로 들어오는 요청은 거절됨. 새로운 윈도우가 다음 시간대에 만들어질 떄까지
  • 장점:
    • 간단하다.
  • 단점:
    • 윈도우 경계 부분에서 트래픽이 몰리면 주어진 시간에 기대했던 트래픽 처리 양보다 많게 처리함.
    • 예를 들면 1분마다 윈도우가 생기는 시스템이라고 가정해보자.
    • 1분이 되기 전에 트래픽이 쏠리고, 1분이 된 이후에 또 트래픽이 쏠리면 갑자기 두 배의 처리를 하게 되는거임.
• 이중 윈도 로깅 알고리즘:
  • 고정 윈도 카운터 알고리즘에서 윈도우 경계 부분에서 많은 트래픽이 발생하는 문제를 해결한 알고리즘임.
  • 매커니즘은 다음과 같다:
    • 모든 요청에는 타임스탬프 값이 붙는다.
    • 그리고 요청은 로그에 기록된다. 로그에 기록되어야지 요청을 처리할 수 있는거임.
    • 로그가 가득차게되면 요청을 거부된다.
    • 새로운 요청이 오면 지정된 윈도우 값에 따라서 이전의 요청들은 만료될 수 있다.
    • 새로운 요청이 와도 이전 요청이 만료되지 않으면 로그에 기록되지 않을 수 있음.
    • 윈도우 경계에서 요청이 폭증하게 되면, 로그가 가득차게 되고, 시간이 어느정도 지나야 만료되기 때문에 지정된 한계만 처리할 수 있음.
  • 장점:
    • 정교한 매커니즘 때문에 지정된 한계 내에서만 요청을 처리하도록 만들 수 있음.
  • 단점:
    • 오래된 메시지들도 만료되기 전까지 가지고 있고, 타임스탬프 값도 추가로 가지고 있기 때문에 메모리를 보다 많이 사용한다.
• 이중 윈도 카운터 알고리즘:
  • 두 가지 윈도우를 합해서 쓰는 기법임.
  • 원래 이를 구현하는 방법은 두가지가 있다고 함. 하나만 여기서 소개
  • 매커니즘은 다음과 같다:
    • 윈도우를 1분이라고 가정했을 때 두 가지의 윈도우를 쓴다.
    • 현재 시점의 윈도우와, 바로 직전의 윈도우.
    • 그리고 현재 시간을 기준으로 현재 시점의 윈도우와 직전 윈도우를 합쳐서 처리할 수 있는 개수를 계산한다.
    • 예시: 직전의 윈도우가 이렇고 [0, 1], 현재의 윈도우가 [1, 2] 범위라면 1분 20초 쯤에 계산되는 범위는 [0.33, 1.33] 이 될거임.
    • 그래서 이 범위 내에서 요청이 한계값을 넘지 않았더라면 요청은 수락되고, 아니라면 거절될 것.
  • 장점:
    • 이중 윈도 로깅 알고리즘보다 메모리 효율이 좋음.
      • 윈도우 경계 내에서도 지정한 한계 값만큼 잘 처리함.
  • 단점:
    • 다소 느슨하게 계산하기 때문에 약간의 오차는 발생함.
    • 큰 문제는 아니라고 함.

 

 

개략적인 아키텍처:

• 처리를 제한하는 카운터를 별도로 보관을 해야한다. 이건 디스크보다 메모리가 적합할 것이고, Redis 와 같은 도구를 쓰면 적합해보인다.
  • Redis 명령어의 INCR 은 메모리의 카운터 값을 1만큼 증가시킴.
  • Redis 명령어의 EXPIRE 은 타임아웃 값을 지정할 수 있음. 카운터에 타임아웃 값을 지정하는 것.
  • Q: Redis 에 카운터 값을 넣는 건 매 요청마다 보내는 거니까 Latency 문제를 증가시키지 않는가? (효율적으로 다루는 방법은 뭐가 있을까?)
    • 로컬 캐시를 쓰는 방법이 있다.
    • Rate Limiter 를 별도의 컴포넌트로 구현하다고 가정해보고, Redis Cluster 를 카운터를 저장하는 용도로 사용한다고 가정해보자.
    • Rate Limiter 는 Redis 와 통신해서 자신이 받을 수 있는 요청의 최대 할당량을 받아올거임.
    • 그리고 요청이 들어올 떄 이 값은 증가할거고, 특정 임계값에 도달하거나, 일정 시간이 지날때마다 Redis 와 통신을 하는 것.
    • 이렇게 하면 정확한 카운팅을 할 수 없긴하지만, 효율적인 통신을 만들 수 있다.
    • 그리고 이런 연산은 비동기로 통신을 해야 Latency 에 영향을 덜 줄듯하다.
    • Caffeine 을 이용해서 로컬 캐시를 구현할 수 있음.
• Rate Limtier 을 어플리케이션 앞단에 별도의 레이어로 두고, Redis 와 통신하도록 하고, 여기서 통과되면 어플리케이션 API 서버로 보내는 방식으로 하자:
  • Rate Limiter 는 Fault Tolerance 한가?
    • 여러대의 서버로 확장시켜놓으면 문제 없을 듯.
  • 분산 시스템에 적용할 수 있는가?
    • 가능하다.
  • 다양하고 유연한 로직을 넣는 것도 가능하다.
    • 이건 별도의 데이터베이스에 Rate Limiter 룰을 넣어야 함.
  • Latency 는 늘어나는 문제점이 있다.
• API 서버에서 내부적으로 Rate Limiter 구현 로직을 넣는 건 어떤가?
  • 유지보수가 많이 들어간다. 모든 어플리케이션마다 로직을 넣어야하니까. 그래서 비용이 비싼편
  • Latency 는 줄일 수 있다.
• Rate Limiter 를 API 서버 앞에 둬야할까? 뒤에 둬야할까?
  • API 서버 앞에 Rate Limiter 를 두게 되면 API 서버륿 보호시킬 수 있음.
  • 반면에 API 서버가 앞에 Rate Limiter 를 두게 되면 Rate Limiter 가 장애가 되더라도 API 서버는 요청이 처리 가능함.음.
  • 뭐가 더 중요한지 그리고 상황에 따라 다를 거 같다. 트래픽이 많은 어플리케이션에서는 API 서버 앞에 두는게 맞을듯.
  • Rate Limiter 에 설정하는 규칙들은 별도의 데이터베이스에 저장할 수 있도록 해야할 듯하다. 데이터베이스에 저장된 규칙대로 Redis 에서 저장할 수 있도록.
  • 장애 상황을 대비한 Fallback 전략을 구현해야 할 것:
    • Rate Limiter 가 장애가 발생한 경우:
      • Circuit Breaker 를 구현해야 함.
      • API 게이트웨이나 로드 밸런서 레벨에서 구현해서 Rate Limiter 서비스로의 호출을 차단하고 우회.
      • 고가용성을 위해 여러 인스턴스를 운영해야함.
    • Redis Cluster 가 장애가 발생한 경우:
      • Rate Limiter 서비스 내에 로컬 캐시를 구현하여 Redis와의 통신 실패 시 최근 결정을 사용
      • 여러 Redis Cluster를 구성하여 하나가 실패해도 다른 것으로 전환.

 

 

상세 설계

좀 더 디테일하게 들어가는 것:

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되는가?
• 처리가 제한된 요청들을은 어떻게 처리되는가?
• 분산 환경에서 처리율 제한 기법
• 구체적인 설계
• 성능 최적화 방안
• 모니터링 방안

 

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

• Envoy 프록시 + Lyft 의 ratelimit 라이브러리를 이용해서 Rate limiter 를 구현할 수 있음.
• ratelimit 를 이용하면 다음과 같이 설정 파일로 규칙을 정의해서 구현할 수 있다.
• rate limiter 가 적용될 도메인을 지정할 수 있고, 모든 요청에 대한 글로벌 제한, URL 경로 기반 제한, IP 기반 제한, 요청 헤더 기반 제한, 복합 규칙등을 지정할 수 있음.
• Runtime 중에 설정을 다시 로드할 수 있는 기능을 제공함.
• (쿠버네티스 환경에서는 ingress 수준에서 rate limiter 를 적용할 수 있다. 현재 v1.19 에서는 Gateway 라는 리소스가 베타 단계로 등장하긴 함. 여기에는 Rate limiter 기능이 없긴 하지만 커스텀 리소스 정의(CRD)를 통해 rate limiting 정책을 정의하는게 가능하다.)

domain: myapi
descriptors:
  # 전체 API에 대한 글로벌 제한
  - key: generic_key
    value: default
    rate_limit:
      unit: minute
      requests_per_unit: 100

  # 특정 엔드포인트에 대한 제한
  - key: path
    value: "/users"
    descriptors:
      - key: method
        value: POST
        rate_limit:
          unit: minute
          requests_per_unit: 5

  # IP 기반 제한
  - key: remote_address
    rate_limit:
      unit: second
      requests_per_unit: 10

  # 헤더 기반 제한 (예: API 키)
  - key: header_match
    value: "X-API-Key"
    descriptors:
      - key: generic_key
        value: api_key_limit
        rate_limit:
          unit: hour
          requests_per_unit: 1000

  # 복합 규칙
  - key: path
    value: "/search"
    descriptors:
      - key: query_param
        value: "category"
        descriptors:
          - key: remote_address
            rate_limit:
              unit: minute
              requests_per_unit: 5

  # 사용자 ID 기반 제한
  - key: header_match
    value: "X-User-ID"
    rate_limit:
      unit: day
      requests_per_unit: 1000

 

 

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

• HTTP 429 (Too many requests) 응답을 내보냄.
• 클라이언트는 HTTP 응답 헤더를 통해서 자신의 요청이 처리율 제한 장치에 걸렸다는 걸 알거임:
  • X-Ratelimit-Remaining: 윈도 내에 남은 처리 요청 가능 수
  • X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
  • X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 보내야하는지.
• 429 응답은 X-Ratelimit-Retry-After 와 같이 내보내야함.

 

 

상세 설계 도면:

 

 

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

• 두 가지 어려운 문제가 있을 것:
  • Race Condition (경쟁 조건)
  • Synchronization (동기화)
• Race Condition 문제:
  • 동시에 토큰 값을 증가시켜서 업데이트에 누락이 생기는 문제가 발생할 수 있음.
  • 이런 문제를 해결하기 위해서 Lock 을 쓴다고 하면 성능적으로 병목이 될 것.
  • 원자석 연산을 위해서 Redis 트랜잭션을 이용하거나, Lua 스크립트를 이용하면 됨.
• 동기화 이슈:
  • 여러개의 처리율 제한 장치를 사용한다고 했을 때 처리 제한을 동기화 시키는게 중요함.
  • 이 경우에는 Redis 같은 걸 이용해서 중앙식으로 관리하면 됨.
  • 동기화는 너무 빡빡하게 하기 보다는 최종 일관성 모델을 이용해서 주기적으로, 비동기적으로 동기화를 하도록 하고, 일정 처리 수는 넘겨도 상관없도록 하면 될 듯. 이걸 Soft Limit 라고도 함. Hard Limit 는 임계값을 절대 못넘도록 하는거.
• 성능 최적화:
  • edge 서버를 이용해서 latency 를 줄이기.