[가상 면접 사례로 배우는 대규모 시스템 설계기초] 4장 처리율 제한 장치의 설계

글의 시작

• 처리율 제한 장치(rate limiter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치다. 예를 들자면 특정 기간 내에 전송되는 http 프로토콜로 요청하는 클라이언트의 요청 횟수 제한한다.api 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리가 중단(block)된다.

관련 내용

처리율 제한 장치 알고리즘

• 토큰 버킷(token bucket)
  - 토큰 버킷이라는 지정된 용량을 같은 컨테이너가 있고 이 버킷은 사전 설정된 양의 토큰이 주기적으로 채워진다. 토큰이 꽉찬 버킷은 더 이상 추가 되지 않고 요청이 될때마다 하나의 토큰을 사용하고 요청이 도착할때 마다 검사하여 요청을 처리하거나 버리는 방식
  • 토큰 버킷 알리고리즘 2개의 인자를 받는다.
    - 버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 갯수
    • 토큰 공급률(refill rate): 초당 몇개의 토큰이 버킷에 공급 되는가
  • 장점
    - 구현이 쉽다.
    • 메모리 사용 측면에서 효율적
    • 짧은 시간에 집중되는 트래픽도 처리 가능
  • 단점
    - 버킷크기와 토큰 공급률이라는 두개의 인자를 가지고 적절하게 튜닝하는 것은 어렵다.
    

• 누출 버킷(leaky bucket)
  - 동작원리
  - FIFO로 구현
  - 요청이 도착하면 큐가 가ㅣ득 차 있는지 확인 후 빈자리가 있는 경우 큐에 요청 추가
  - 큐가 가득 차 있는 경우에는 새 요청은 버린다.
  - 지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
  • 2개의 인자 사용
    - 버킷 크기: 큐 사이즈와 같은 값, 큐에서는 처리될 항목들이 보관
    • 처리율(outflow rate): 지정된 시간당 몇개의 항목을 처리할지 지정되는 값(보통 초단위)
  • 장점
    - 큐의 크기가 제한됨, 메모리 사용량 측면에서 효율적
    • 고정된 처리율을 갖고 있으므로 안정적 출력에 적합
  • 단점
    - 단시간에 많은 트래픽이 몰리는 경우 큐에 오래된 요청이 쌓이고, 지연시 최신 요청은 버려짐
    - 2개의 인자로 튜닝하기 어려움
    

• 고정 윈도 카운터(fixed window counter)

  • 동작원리
    - 타임라인(timeline)을 고정된 간격의 윈도우(window)로 나누고, 각 윈도우마다 카운터(counter)를 붙인다.
    - 요청이 접수 될때 마다 해당 시점에 맞는 타임라인의 counter의 값이 증가된다.
    - 해당 시점에 맞는 타임라인의 counter의 값이 임계치(threshold)에 도달하면 새로운 요청은 새 타임라인 윈도우가 열릴때까지 버려진다.
    

  • 단점
    - 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도우에 할당된 양보다 더 많은 요청이 처리 될수 있다. (예들 들어 1분 단위 기준으로 처리 할때 운이 안좋으면 00:01:00 ~ 00:02:00과 00:02:00 ~ 00:03:00은 각각 5건씩 처리해 10건이지만, 00:01:30 ~ 00:02:30 으로 생각한다면 10건이 모두 해당 시간 처리로 될수 있는 케이스 )
    

  • 장점
    - 메모리 효율이 좋다.

    • 이해하기 쉽다.
    • 윈도우가 닫히는 시점에 카운터를 초기화 하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.

• 이동 윈도 로그(sliding window log)

  • 고정 윈도 카운터의 단점을 해결하기 위한 방식
  • 동작원리
    • 요청의 타임스탬프를 추적하기 떄문에 타임스탬프의 데이터를 보통 레디스의 sorted set 같은 캐시에 보관
    • 새 요청이 오면 만료된 타임스탬프는 제거한다. 만료된 타임스램프 그 값이 현재 윈도의 시작시점보다 오래된 타임스탬프를 말함
    • 새 요청의 타임스탬프를 로그에 추가한다.
    • 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우에는 처리 거부
      
  • 장점
    - 처리율 제한 메커니즘이 정교하다.
  • 단점
    - 다량의 메모리 사용(거부된 요청의 타임스탬프로 보관하기 때문)
    

• 이동 윈도 카운터(sliding window counter)

  • 고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘 결합한 것
  • 현재 1분간 요청수 + 직전 1분간 요청수 * 이동 윈도우와 직전 1분이 겹치는 비율
  • 장점
    - 이전 시간대의 평균 처리율에 따라 현재 윈도우의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
    • 메모리 효율이 좋다.
  • 단점
    • 지적 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다. 하지만 일반적으로 오차범위가 크지 않다.