[CH4] 처리율 제한 장치의 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

처리율 제한 장치 (rate limiter)

💡 클라이언트 또는 서비스가 보내는 트래픽 처리율을 제어하기 위한 장치

0️⃣ 왜 필요한가?

• Dos 공격에 의한 자원 고갈 (resource starvation)을 방지할 수 있다.
• 처리를 제한함으로써 서버를 많지 않게 두거나, 우선 순위가 높은 API에 더 높은 자원을 할당하는 식으로 비용을 절감할 수 있다.
• 잘못된 이용 패턴으로 유발된 트래픽을 막는 등 서버 과부하를 방지할 수 있다.
• 예시
  • HTTP : 특정 기간 내 전송되는 클라이언트 요청 횟수를 제한
    • 요청 횟수가 threshold를 넘어서면 추가로 요청된 호출은 모두 block
  • 사용자는 초당 2회 이상 새 글을 올릴 수 없다
  • 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다

1️⃣ 문제 이해 및 설계 범위 확정 :: 필요한 알고리즘 특정

• 요구에 따라 알고리즘의 장단점을 따지며 뭘 쓸지 고민해보자
  • 이런 질문을 해보자
    • 어떤 종류의 처리율 제한 장치? 서버? 클라이언트?
    • 어떤 기준? IP 주소? 사용자 ID?
    • 시스템 규모? 스타트업? 대규모 요청?
    • 환경? 분산 환경? 모놀리틱?
    • 독립적? 코드에 종속?
    • 사용자 요청이 걸러진 경우 그 사실을 알려야 하는가?

2️⃣ 개략적인 설계안 제시 및 동의 구하기

• 처리율 제한 장치를 어디에 둘건가?
  • 클라이언트측 : 위변조가 쉽고, 모든 구현을 통제하기 어렵기에 일반적으로 안정적이지 못하다.
  • 미들웨어측 : 처리율 제한 미들웨어를 만들어 거기서 API 서버로의 요청을 통제하게 만들자.
    • API gateway가 이를 지원해준다.
    • 만약 마이크로서비스이고, API 게이트웨이를 이미 설계에 포함했거나, 또는 처리율 제한 장치 구현 인력이 부족하다면 API 게이트웨이를 이용하는게 바람직하다.
  • 서버측 : 프로그래밍 언어 등이 서버측 구현을 지원할만큼 효율이 높은지 검토해보자. 만약 서버에서 직접 구현할 경우 알고리즘은 자유롭게 선택 가능

• 처리율 제한 알고리즘

  • 토큰 버킷 : 간단하고, 세간의 이해도도 높아 폭넓게 사용되는 중
    • 버킷이 꽉 찼다면 추가로 공급된 토큰은 추가되지 않고 버려진다 (overflow)
    • 요청은 처리할 때마다 토큰을 사용한다. 토큰이 있으면 꺼내고 요청을 전달하고, 없으면 요청을 버리는 방식
    • 장점
      • 구현쉽고, 메모리 효율적이고, 짧은 시간에 집중되는 (burst of traffic)도 커버 가능하고, 버킷에 토큰 남아 있으면 요청은 무조건 시스템에 전달된다.
    • 단점
      • 버킷 크기와 토큰 공급률을 정하기가 까다롭다.
        • 보통 API endpoint마다 버킷을 둔다.
        • 만약 IP주소마다 처리율을 제한해야 한다면 IP주소마다 버킷을 둬야 하고, 초당 요청으로 제한하고 싶다면 모든 요청이 하나의 버킷을 쓰게 해야 한다.
  • 누출 버킷 : 요청 처리율 고정되어 있는 토큰 버킷 알고리즘, FIFO 큐로 구현
    • 동작 원리
      • 큐에 빈 자리가 있는지 확인
      • 가득 찼으면 새 요청을 버리고, 빈 자리가 있으면 큐에 요청 추가
      • 지정된 시간마다 큐에서 요청 꺼내서 처리
    • 장점
      • 큐 크기 제한적이라 메모리 효율적, 고정된 처리율이라 안정적 출력(stable outflow rate)이 필요할 때 적합
    • 단점
      • 단시간에 많은 트래픽 몰리면 큐에 오래된 요청이 쌓여지고, 그 요청 제때 처리 못하면 새 요청이 버려짐
      • 버킷 크기 (= 큐 사이즈), 처리율(= 정해진 시간에 몇 개 처리?) 인자를 관리하기 힘듬
  • 고정 윈도 카운터
    • 동작 원리
      • 타임라인을 고정 간격의 윈도로 나누고, 윈도마다 카운터 붙인다
      • 요청 접수된 카운터 += 1
      • 카운터 값이 사전 정의된 임계에 도달하면 새 요청은 새 윈도 열릴 때까지 버려진다
    • 장점
      • 메모리 효율 좋고, 이해하기 쉽고, 특정 트래픽 패턴 처리에 적합
    • 단점
      • 윈도 경계 부근에서 일시적인 트래픽이 몰려들 때, 기대했던 처리 한도보다 많은 양의 요청을 처리하게 됨
  • 이동 윈도 로깅 : 고정 윈도의 윈도 부근 트래픽 문제를 해결
    • 동작 방식
      • 요청 타임스탬프 추적 (보통 레디스 등 캐시에 보관)
      • 새 요청이 오면 만료된 타임스탬프(= 윈도 시작 시점보다 오래된 것) 제거
      • 새 요청 타임스탬프를 로그에 추가
      • 로그 크기가 허용치보다 같거나 작으면 요청 전달, 아니면 처리 거부
    • 장점
      • 어느 순간의 윈도도 허용 요청 개수는 시스템 처리 한도를 넘지 않음
    • 단점
      • 거부된 요청의 타임스탬프도 보관 ⇒ 메모리 많이 잡아먹음
  • 이동 윈도 카운터 : 고정 윈도 카운터 + 이동 윈도 로깅
    • 장점
      • 이전 시간대 평균 처리율에 따라 윈도 상태 계산 → 짧은 시간 트래픽 대응 O
      • 메모리 효율 굿
    • 단점
      • 직전 시간대 요청이 균등히 분포되어 있다고 가정 → 느슨
        • 실험 결과 그렇게 심각하지 않음

• 개략적인 아키텍처

  • 얼마나 많은 요청이 접수되었는지 추적할 수 있는 카운터를 추적 대상별로 생성 → 카운터 값이 한도를 넘어서면 요청 거부
    • 카운터를 어디에 보관할건지?
      • DB는 디스크 접근이라 느리니까 안됨
      • 캐시가 적절 : 빠르고 시간에 기반한 만료 정책 쓰기 때문
        • redis : 클라이언트가 처리율 제한 미들웨어에게 요청을 보내면, 미들웨어는 레디스 지정 버킷에서 카운터를 가져와 한도 도달 여부를 확인한다.

3️⃣ 상세 설계

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되나?
  • 보통 오픈소스 등을 활용할 수 있고, 설정 파일 형태로 디스크에 저장된다.
• 처리가 제한된 요청들은 어떻게 처리하나? (= 처리율 한도 초과 트래픽 처리 = throttle)
  • HTTP 429 응답만 보내거나
    • HTTP 응답 헤더로 확인할 수도 있다.
      • X-Ratelimit-Remaining
      • X-Ratelimit-Limit
      • X-Ratelimit-Retry0After
  • 또는 나중에 처리하기 위해 큐에 보관한다.
• 분산 환경에서의 처리율 제한 장치의 구현
  • 여러대의 서버와 병렬 스레드 지원하도록 시스템 확장하기.
  • 경쟁 조건 (race condition)
    • 요청을 처리하는 스레드가 병렬로 레디스에서 값을 읽었다면, 그리고 둘 중 어느쪽도 아직 변경 값을 저장하지 않았다면 카운터가 이상하게 작동한다.
    • 락을 걸어 해결할 수 있지만, 성능 이슈가 있다.
      • 이 경우 루아 스크립트 또는 정렬 집합 자료구조를 이용해 해결할 수 있다.
  • 동기화 (synchronization)
    • 처리율 제한 장치 서버가 여러 대인 경우 동기화가 필요하다.
    • 고정 세션 (sticky session)을 활용해 같은 클라이언트 요청을 같은 장치로 보내게 만들 수 있다.
      • 확장이 불가능하고 유연하지 않아 비추천
    • 레디스같은 중앙 집중형 데이터 저장소를 쓸 수 있다.
• 성능 최적화
  • 데이터 센터 지원
    • 에지 서버를 이용해 트래픽 전달 지연 시간을 줄인다.
  • 제한 장치 간 데이터 동기화에 최종 일관성 모델 사용 (eventual consistency model)
• 모니터링
  • 아래를 모니터링을 통해 확인한다
    • 채택된 처리율 제한 알고리즘이 효과적인지
    • 정의한 처리율 제한 규칙이 효과적인지

4️⃣ 마무리 :: 설계에 대한 후속 질문 및 추가 논의

• 경성 (hard) 또는 연성 (soft) 처리율 제한
  • 경성 처리율 제한 : 요청 개수는 임계치를 절대 못 넘는다
  • 연성 처리율 제한 : 요청 개수는 잠시 동안은 임계치를 넘을 수 있다
• 다양한 계층에서의 처리율 제한
  • OSI 계층 어디에서나 처리율 제한이 가능하다
• 처리율 제한을 회피하는 방법
  • 클라이언트를 어떻게 설계할 것인가?
    • 캐시 사용으로 API 호출 횟수 줄이기
    • 짧은 시간에 너무 많은 메시지 보내지 말기
    • 예외나 에러 처리 코드를 도입해 클라이언트가 예외 상황에서 복구될 수 있게 하기
    • 재시도 로직 구현에는 충분한 백오프 시간을 두기