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

네트워크 시스템에서 처리율 제한 장치(rate limiter) 는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치

• ex) 특정 기간 내에 전송되는 클라이언트 HTTP 요청 횟수를 제한
• ex) API 요청 횟수가 정의된 임계치를 넘어서면 추가 호출은 처리가 중단(block)

 

👍 좋은 점

• DoS(Denial of Service) 공격에 의한 자원 고갈(resource starvation)을 방지
• 비용을 절감. 추가 요청에 대한 처리를 제한하면 서버를 많이 두지 않아도 됨
• 서버 과부하를 막는다. 봇(bot)에서 오는 트래픽이나 사용자의 잘못된 이용패턴으로 유발된 트래픽을 걸러내는데 처리율 제한 장치를 활용 가능

 

🤔 처리율 제한 장치를 어디에 둘 것인가

클라이언트 측에 둘 수도 서버 측에 둘 수 있다.

 

1️⃣ 클라이언트 측

일반적으로 클라이언트는 처리율 제한을 안정적으로 처리할 수 있는 장소가 되지 않는다.

• 클라이언트 요청은 쉽게 위변조가 가능
• 모든 클라이언트의 구현을 통제하는 것이 어렵기 때문

 

2️⃣ 서버 측

서버측에 제한 장치를 두는 방법

 

위 그림처럼 서버 측에 제한장치를 두는 방법이 있다.

또 다른 방법으로 처리율 제한 장치를 API 서버에 두는 대신 처리율 제한 미들웨어를 만들어 해당 미들웨어에서 API 서버로 가는 요청을 통제할 수도 있다.

 

클라우드 마이크로서비스인 경우 처리율 제한 장치는 보통 API 게이트웨이(gateway) 라 불리는 컴포넌트에 구현

• 처리율 제한, SSL 종단(termination), 사용자 인증(authentication), IP 허용 목록(whitelist) 관리 등을 지원하는 완전 위탁관리형 서비스

 

🤖 처리율 제한 알고리즘

처리율 제한 알고리즘은 여러가지 (각각 다른 장단점)

• 토큰 버킷(token bucket)
• 누출 버킷(leaky bucket)
• 고정 윈도 카운터(fixed window counter)
• 이동 윈도 로그(sliding window log)
• 이동 윈도 카운터(sliding window counter)

 

🪣 토큰 버킷 (token bucket)

토큰 버킷은 지정된 용량을 가진 컨테이너로 사전 설정된 양의 토큰이 주기적으로 채워진다.

• 꽉 찬 상태라면 더 이상 토큰이 추가되지 않는다.

각 요청이 처리될 때마다 하나의 토큰이 사용되고 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사

• 충분한 토큰이 있다면 버킷에서 토큰을 하나 꺼낸 후 요청을 시스템에 전달
• 충분한 토큰이 없다면 해당 요청은 버려진다(dropped)

 

📍 토큰 버킷 알고리즘의 2가지 파라미터

1. 버킷 크기	버킷에 담을 수 있는 토큰의 최대 개수
2. 토큰 공급률 (refill rate)	초당 몇 개의 토큰이 버킷에 공급되는지

 

 

🔢 버킷은 몇 개나 사용해야 하나?

• API 엔드포인트마다 별도의 버킷을 두고 사용
• ex) 사용자마다 하루에 한 번만 포스팅 가능, 친구는 150명까지 추가, 좋아요 버튼은 5번만 가능
  • 사용자마다 3개의 버킷이 필요!

 

✅ 장 단점

장점	단점
구현이 쉽다	버킷 크기, 토큰 공급률 값을 적절하게 튜닝하기 어렵다.
메모리 사용 측면에서 효율적이다
짧은 시간에 집중되는 트래픽 (burst of traffic) 처리 가능 (남은 토큰이 있다면)

 

🪣 누출 버킷 (leaky bucket)

토큰 버킷과 비슷하지만 요청 처리율이 고정되어 있는 알고리즘

• 보통 FIFO 큐로 구현

 

요청이 도착하면 큐가 가득 차 있는지 확인

• 빈자리가 있는 경우 큐에 요청 추가
• 큐가 가득 차 있는 경우 새 요청은 버리게 됨.
• 지정된 시간마다 큐에서 요청을 꺼내어 처리

 

📍 누출 버킷 알고리즘의 2가지 파라미터

버킷 크기	큐 사이즈와 같은 크기. 처리될 항목들이 큐에 보관
처리율(outflow rate)	지정된 시간당 몇 개의 항목을 처리할지 지정

 

 

✅ 장 단점

장점	단점
메모리 사용 측면에서 효율적이다(큐의 크기가 제한)	짧은 시간에 트래픽이 많이 몰릴 경우 큐에 오래된 요청들이 쌓이고 제때 처리하지 못해 최신 요청들이 버려진다.
고정된 처리율을 가져 안정적인 출력(stable outflow rate)가 필요한 경우 적합	두 개의 인자를 적절히 튜닝하기 어려움

 

🧩 고정 윈도 카운터 알고리즘 (fixed window counter)

타임라인을 고정된 간격의 윈도(window)로 나누고 각 윈도마다 카운터를 붙인다.

• 요청이 올 때마다 카운터 값은 1씩 증가
• 카운터 값이 사전에 설정된 임계치에 도달시 새로운 요청은 새 윈도가 열릴 때까지 버려짐

 

⚠️ 문제

윈도 경계 부근에 순간적으로 많은 트래픽이 집중되면 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다.

 

ex) 분당 최대 5개의 요청만 허용하는 시스템

• 2:00:00 ~ 2:01:00 → 5개의 요청
• 2:01:00 ~ 2:02:00 → 5개의 요청
• 2:00:30 ~ 2:01:30 ⇒ 1분동안 살표본다면 10개의 요청…!? ⇒ 임계치의 2배

 

✅ 장 단점

장점	단점
메모리 효율이 좋다	윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우 기대했던 시스템의 처리 한도(임계치)보다 많은 양의 요청을 처리하게 됨
이해하기 쉽다
윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.

 

🚗 이동 윈도 로깅 알고리즘 (sliding window log)

 

고정 윈도 카운터 알고리즘 의 문제인 윈도 경계 부분에서 트래픽이 집중되는 경우 설정된 한도보다 많은 요청을 처리하는 문제를 해결.

 

1️⃣ 요청의 타임스탬프를 추적

• 보통 레디스의 정렬 집합(sorted set) 같은 캐시에 보관

 

2️⃣ 새 요청이 오면 만료된 타임스탬프 제거

• 현재 윈도의 시작 시점보다 오래된 타임스탬프

 

3️⃣ 새 요청 타임스탬프를 로그에 추가

• 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달
• 그렇지 않으면 처리를 거부

 

✅ 장 단점

장점	단점
어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템 처리율 한도를 넘지 않음	다량의 메모리를 사용함. 거부된 요청의 타임스탬프도 보관

 

 

🚌 이동 윈도 카운터 알고리즘 (sliding window counter)

고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 형태

 

현재 1분간의 요청 수 + 직전 1분간의 요청수 x 이동 윈도와 직전 1분이 겹치는 비율

 

 

✅ 장 단점

장점	단점
이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 대응	직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨
메모리 효율이 좋음

 

 

단점(문제)는 생각보다 심각하지 않음.

• 클라우드페어(Cloudfare)가 실시했던 실험에 따르면 40억 개의 요청 가운데 시스템의 실제 상태와 맞지 않게 허용되거나 버려진 요청은 0.003%

 

⚙️ 개략적인 아키텍처

얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적할 대상별로 두고 해당 카운터 값이 한계를 넘어서면 도착한 요청을 거부한다!

• 사용자별로 추적?
• IP 주소별로 추적?
• API 엔드포인트 / 서비스 단위?

 

🤔 카운터는 어디에 보관..?

DB - 디스크 접근으로 인해 느리다.

메모리상으로 동작하는 캐시가 바람직 → Redis

 

레디스는 처리율 제한 장치를 구현할 때 자주 사용하는 메모리 기반 저장장치로 INCR와 EXPIRE 두 가지 명령어를 지원

 

명령어	설명
INCR	메모리에 저장된 카운터의 값을 1 증가
EXPIRE	카운터에 타임아웃 값 설정. 설정된 시간이 지나면 자동 삭제

 

 

 

 

🏄‍♂️ 동작 과정

1. 클라이언트가 처리율 제한 미들웨어에 요청을 보냄
2. 처리율 제한 미들웨어는 레디스의 특정 버킷에서 카운터를 가져와 한도에 도달했는지 아닌지를 검사
   • 한도에 도달하지 않았다면 요청은 API 서버로 전달
     • 미들웨어는 카운터의 값을 증가 후 레디스에 다시 저장
   • 한도에 도달했다면 요청은 거부

 

👷‍♂️ 상세 설계

이와 같은 개략적인 설계만 봐서는 아래와 같은 사항들은 알 수 없다!

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장?!?
• 처리가 제한된 요청들은 어떻게 처리?!

 

🚨 처리율 제한 규칙

Lyft 는 처리율 제한에 오픈 소스를 사용하고 있다.

 

domain: messaging
descriptors:
  - key: message_type
    value: marketing
    descriptors:
      - key: to_number
        rate_limit:
          unit: day
          requests_per_unit: 5

 --------------
domain: auth
descriptors:
    - key: auth_type
      Value: login
      rate_limit:
          unit: minute
        requests_per_unit:5

• 마케팅 메시지의 최대치를 하루 5개로 제한
• 클라이언트가 분당 5회 이상 로그인 할 수 없도록 제한

🚘 Lyft

미국 차량 공유 서비스

 

☑️ 처리율 한도 초과 트래픽 처리

어떤 요청이 처리율 한도 제한에 걸리면 HTTP 429(too many requests)응답을 클라이언트에게 보낸다.

• 한도 제한에 걸린 요청(메시지)를 나중에 처리하기 위해 큐에 보관할 수도 있다.

 

↗️ 처리율 제한 장치가 사용하는 HTTP 헤더

클라이언트가 자신이 보낸 요청이 처리율 제한에 걸린 것을 어떻게 감지!?

자신의 요청이 처리율 제한에 걸리기까지 얼마나 많은 요청을 보낼 수 있는지 알 수 있나??

 

HTTP 응답 헤더를 통해 해결

• 처리율 제한 장치는 HTTP 헤더를 클라이언트에게 보내줌.

헤더	설명
X-Ratelimit-Remaining	윈도 내에 남은 처리 가능 요청의 수
X-Ratelimit-Limit	매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
X-Ratelimit-Retry-After	한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

 

 

이를 통해 사용자가 너무 많은 요청을 보내면 429 에러를 X-Ratelimit-Retry-After 헤더와 함께 반환

 

🖥️ 상세 설계 도면

 

1️⃣ 처리율 제한 규칙 은 디스크에 보관

• 작업 프로세스(workers)는 수시로 규칙을 디스크에서 읽어 캐시에 저장한다.

 

2️⃣ 클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달

 

3️⃣ 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져온다.

• 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져온다.

 

4️⃣ 가져온 값들을 토대로 미들웨어가 결정을 내린다.

• 요청이 처리율 제한에 걸리지 않았다면 API 서버로 보낸다.
• 제한에 걸렸다면 429 에러를 클라이언트에게 보낸다.
  • 요청은 버릴수도 메시지 큐에 보관할 수도 있다.

💡 정리

클라이언트 요청이 오면 처리율 제한 미들웨어가 규칙과 Redis 상태를 보고 허용/차단/지연(큐)에 넣는 결정을 한다.

 

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

단일 서버에서의 처리율 제한 장치를 구현하는 것은 어렵지 않다.

여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 두 가지 문제를 해결해야 한다.

 

1. 경쟁 조건 (race condition)
2. 동기화 (synchronization)

 

🏃‍♂️ 경쟁 조건

처리율 제한 조건은 아래 처럼 동작

• 레디스에서 카운터 값을 읽음
• count + 1 값이 임계치를 넘는지 확인
• 넘지 않는다면 레디스에 보관된 카운터 값을 1만큼 증가 후 저장.

 

⚠️ 이때, 병행성이 심한 환경에서는 경쟁 조건 이슈가 발생할 수 있음!!

 

 

🔒 경쟁 조건 문제를 해결하는 가장 널리 알려진 문제는 락(lock)

• 하지만 락은 시스템 성능을 상당히 떨어뜨리는 문제가 존재

 

💡 락 대신 사용할 수 있는 해결책 2가지

• 루아 스크립트
• Redis 자료구조인 정렬 집합 사용

 

🔄 동기화

분산환경에서 고려해야 할 중요한 요소중 하나가 동기화이다.

 

수백만 사용자를 지원하기 위해서는 한 대의 처리율 제한 장치 서버는 충분하지 않을 수 있고 여러 대를 두게 되면 동기화가 필요해진다.

 

클라이언트 A가 제한 장치 A` 에 요청을 보내고 클라이언트 B가 제한 장치 B` 에 요청을 보내고 있을 때

웹 계층은 무상태로 클라이언트는 다음 요청을 다른 제한 장치로 보낼 수 있을 수 있다.

• 동기화를 하지 않은 상태라면 제한장치 A``은 클라이언트 B`에 대해 아무것도 모르기 때문에 처리율 제한을 제대로 수행할 수 없다.

 

👻 고정 세션을 활용해 같은 클라이언트로부터 요청은 항상 같은 처리율 제한 장치로 보내기

• 확장 가능하지도 유연하지 않은 방법

 

💡 레디스..!

• 레디스 같은 중앙 집중형 데이터 저장소를 이용해 처리하기

 

🌈 성능 최적화

이 설계들은 2가지 지점에서 성능 개선이 가능

 

1️⃣ 여러 데이터센터를 지원하는 것은 처리율 제한 장치에 중요한 문제라는 것을 상기

• 사용자 트래픽을 가장 가까운 엣지서버로 전달하여 지연시간을 줄인다.

2️⃣ 제한 장치간 데이터를 동기화할 때 최종 일관성 모델 (eventual consistency model)을 사용

• 강한 일관성
• 약한 일관성
• 결과적 일관성

 

🖥️ 모니터링

처리율 제한 장치를 설치한 후 효과적으로 동작하는지 확인하기 위해 데이터를 모을 필요가 있다.

1. 채택된 처리율 제한 알고리즘이 효과적인지
2. 정의한 처리율 제한 규칙이 효과적인지

 

📚 Ref.

https://product.kyobobook.co.kr/detail/S000001033116

https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter

https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/