[대규모 시스템 설계 기초 정리] 처리율 제한 장치

가상 면접 사례로 배우는 대규모 시스템 설계 기초를 정리한 내용입니다.

처리율 제한 장치 (Rate Limiter)

---

클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치
ex) 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한

장점

---

• Dos 공격에 의한 자원 고갈을 방지
• 비용 절감
  • 특히 제3자 API에 사용료를 지불하고 있는 경우 매우 중요
• 서버 과부하 방지
  • Bot에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러내는데 활용

 

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

---

클라이언트 측에 두는 경우

• 일반적으로 클라이언트 요청은 쉽게 위변조가 가능해서 처리율 제한을 안정적으로 걸 수 있는 장소가 되지 못한다.

서버 측에 두는 경우

• API 서버에 두는 방법
• 처리율 제한 미들웨어를 만들어 해당 미들웨어로 하여금 API로 가능 요청을 통제하는 방법.
• 클라우드 마이크로서비스의 경우, 처리율 제한 장치는 보통 API Gateway라 불리는 컴포넌트에 구현된다.
  • API Gateway는 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등을 지원

 

처리율 제한 알고리즘

---

Token Bucket Algorighm

• 토큰 버킷은 지정된 용량(버킷 크기)을 갖는 컨테이너로, 사전 설정된 양의 토큰(토큰 공급률)이 주기적으로 채워진다.
  • 각 요청은 처리될 때 마다 하나의 토큰을 사용한다.
  • 요청이 들어오면 먼저 충분한 토큰이 있는지 검사한 후, 있는 경우 버킷에서 토큰 하나를 꺼낸 후 요청을 시스템에게 전달한다.
  • 만약 충분한 토큰이 없는 경우, 해당 요청은 버려진다.
  • 버킷 크기, 토큰 공급률
• 버킷 수는 통상적으로 API 엔드포인트마다 별도의 버킷을 둔다. (IP 주소 별로 처리율 제한을 적용해야 한다면 IP 주소마다 버킷을 하나씩 할당해야 하는 등 경우에 따라 다양하게 버킷 수를 사용해야 한다)

장점

• 구현이 쉬우며, 메모리 사용 측면에서 효율적.
• 짧은 시간에 집중되는 트래픽도 처리 가능.

단점

• 버킷 크기와 토큰 공급률이라는 두 개의 값을 적절하게 튜닝하는 것이 까다로움

Leacky Bucket Algorithm

• 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다르다.
• 보통 FIFO 큐로 구현
  • 요청이 도착하면 큐가 가득 차 있는지 확인 후(버킷 크기), 빈자리가 있는 경우 큐에 요청을 추가.
  • 큐가 가득 차 있는 경우, 새 요청은 버려지며, 지정된 시간마다 큐에서 요청을 꺼내어 처리한다. (처리율)
  • 버킷 크기, 처리율

장점

• 큐의 크기가 제한되어 있어 메모리 사용 측면에서 효율적
• 고정된 처리율을 갖고 있어 안정적 출력이 필요한 경우 적합

단점

• 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고, 그 요청들을 제때 처리하지 못하면 최신 요청들은 버려지게 된다.
• 버킷 크기와 처리율을 올바르게 튜닝하기가 까다로움

Fixed Window Counter Algorithm

• 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
• 요청이 접수될 때마다 이 카운터의 값은 1씩 증가한다.
• 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.

장점

• 메모리 효율이 좋고, 특정한 트래픽 패턴을 처리하기에 적합

단점

• 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 된다.

 

문제점 (시스템의 처리 한도보다 많은 양의 요청을 처리하는 케이스)

예를 들어 분당 최대 5개의 요청만을 허용하는 시스템으로, 카운터는 매 분마다 초기화된다고 가정하자

만약, 2:00:00와 2:01:00 사이에 다섯 개의 요청이 들어왔고, 2:01:00과 2:02:00 사이에 또 다섯 개의 요청이 들어왔다고 가정할때, 윈도 위치를 조금 옮겨 2:00:30 ~ 2:01:30 까지의 1분 동안을 보면 1분 동안 시스템이 처리한 요청은 10개로 허용 한도의 2배가 되는 문제가 존재한다.

 

Sliding Window Log Algorithm

고정 윈도 알고리즘의 중대한 문제인 윈도 경계 부근에 트래픽이 집중되는 경우 시스템에 설정된 한도보다 많은 요청을 처리하게 된다는 문제를 해결하는 알고리즘.

• 요청의 타임스탬프를 추적.
• 새 요청이 오면 만료된 타임스탬프는 제거한다.
• 새 요청의 타임스탬프를 로그에 추가.
• 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. (그렇지 않은 경우 처리 거부)

장점

• 어느 순간의 윈도에서도 허용되는 요청의 개수가 시스템의 처리율 한도를 넘지 않는다.

단점

• 다량의 메모리를 사용.

Sliding Window Counter Algorighm

• 고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것
• 현재 1분간의 요청 수 + 직전 1분간의 요청 수 * 이동 윈도와 직전 1 분위 겹치는 비율로 현재 윈도에 몇 개의 요청이 온 것인지 계산한다.

장점

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

개략적인 아키텍처

처리율 제한 알고리즘의 기본 아이디어는 얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적 대상별로 두고 이 카운터의 값이 어떤 한도를 넘어서면 한도를 넘어 도착한 요청은 거부하는 것이다.

• 이러한 카운터는 어디에 보관할 것인가?
  • DB는 디스크 접근 때문에 느리므로 메모리상에서 동작하는 캐시가 바람직하다. (빠름 + 시간에 기반한 만료 정책을 지원하기 때문)
  • 예를 들어, 레디스의 경우 INCR(메모리에 저장된 카운터 값을 1만큼 증가시킴), EXPIRE(카운터에 타임아웃을 설정, 설정된 시간이 지나면 자동으로 카운터가 삭제됨)을 이용할 수 있다.

개략적 구조

• 클라이언트가 처리율 제한 미들웨어에게 요청을 보낸다.
• 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지를 검사
  • 한도에 도달하면 요청은 거부되며, 그렇지 않은 경우 요청은 API 서버로 전달된다. (미들웨어는 카운터의 값을 증가시킨 후 다시 레디스에 저장)

상세 설계

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

• 어떤 요청이 한도 제한에 걸리면 API는 HTTP 429 응답을 클라이언트에게 보낸다.
• 경우에 따라서는 한도 제한에 걸린 메시지를 나중에 처리하기 위해 큐에 보관할 수도 있다.

처리율 제한 장치가 사용되는 HTTP 헤더

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

상세 설계

• 처리율 제한 규칙은 디스크에 보관하고, 작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐시에 저장한다.
• 클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달한다.
• 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져오고 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져온 후 다음을 결정한다.
  • 가져온 값들에 근거하여 API 서버로 보낼지 (제한에 걸리지 않는 경우)
  • 429 too many requests 에러를 클라이언트에 보낸 후 요청을 버릴지 or 메시지 큐에 보관할 지(제한에 걸릴지)

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

• 단일 서버를 지원하는 처리율 제한 장치를 구현하는 것은 어렵지 않다. 하지만 여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 또 다른 문제로, 다음 어려운 문제를 풀어야 한다.
  • 경쟁 조건 (Race condition)
  • 동기화 (Synchronization)

경쟁조건

• 병행성이 심한 환경에서는 경쟁 조건 이슈가 발생할 수 있다. (Lost update)
• 경쟁 조건 문제를 해결하는 가장 널리 알려진 해결책은 Lock이다.
  • 하지만 Lock은 시스템의 성능을 상당히 떨어트린다는 문제가 존재.
• 락 대신 쓸 수 있는 해결책으로는
  • 루아 스크립트
  • 레디스의 자료 구조인 정렬 집합 (Sorted Set)을 사용.

동기화 이슈

• 수백만 사용자를 지원하려면 한 대의 처리율 제한 장치 서버론느 충분하지 않을 수 있다. 그래서 처리율 제한 장치 서버를 여러 대 두게 되면 동기화가 필요해진다.
  • 클라이언트 1은 제한 장치 1에 요청을 보내고 클라이언트 2는 제한 장치 2에 요청을 보내고 있다고 가정할 때, 동기화를 하지 않는다면 제한 장치 1은 클라이언트 2에 대해 모르므로 처리율 제한을 올바르게 수행할 수 없을 것이다.

해결책

• Sticky Session을 통해 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치로 보낼 수 있도록 하는 것
  • 규모면에서 확장 가능하지도 않고, 유연하지도 않아 추천하지 않는 방법.
• 레디스와 같은 중앙 집중형 데이터 저장소를 쓰는 것.