4. Rate Limiter

처리율 제한 장치의 설계

처리율 제한 장치란 무엇인가?

처리율 제한 장치(Rate Limiter)는 주로 대규모 시스템에서 클라이언트가 서버에 보내는 요청의 양을 제어하여 서버의 과부하를 방지하고, 자원을 효율적으로 관리하기 위한 중요한 도구입니다. 이는 특정 시간 동안 허용되는 요청 수를 제한함으로써, 서비스의 품질을 유지하고, 악의적인 요청 혹은 과도한 요청으로부터 시스템을 보호할 수 있도록 합니다.

처리율 제한 장치의 필요성

대규모 시스템 설계에서 요청의 폭증은 흔한 문제입니다. 특정 이벤트나 상황에서 트래픽이 급증하면, 시스템은 과부하로 인해 다운되거나 성능이 급격히 저하될 수 있습니다. 이를 방지하기 위해 처리율 제한 장치가 필요합니다.

• 안정성 유지: 과도한 요청이 서버에 도달하는 것을 방지하여 서버 다운타임을 줄입니다.

• 공평한 자원 분배: 제한된 리소스를 모든 사용자가 공평하게 사용할 수 있도록 합니다.

• 서비스 품질 보장: 악의적인 사용자가 시스템을 악용하는 것을 방지하여 다른 사용자에게 미치는 영향을 최소화합니다.

처리율 제한 장치의 기본 설계 방법

처리율 제한 장치는 여러 방법으로 설계할 수 있으며, 각각의 방법은 특정 시나리오에 더 적합합니다.

토큰 버킷 (Token Bucket)

토큰 버킷 알고리즘은 일정한 비율로 생성되는 토큰을 통해 요청을 처리합니다. 요청을 처리하기 위해서는 일정 수의 토큰이 필요하며, 토큰이 부족할 경우 요청이 지연되거나 거부됩니다. 이 알고리즘은 일관된 비율의 요청 처리를 유지하면서도 잠시 동안의 요청 급증을 허용할 수 있어 유연합니다.

• 특징: 초당 일정 수의 토큰이 생성되고, 요청이 처리될 때 토큰이 소비됨.

• 장점: 급증하는 트래픽을 잠시 동안 허용할 수 있으며, 유연한 처리율 제어가 가능. (이전과 최대 토큰 크기 제한)

• 단점: 구현의 복잡성과 토큰 관리가 필요.

Example

• 1초에 5개의 토큰이 생성되도록 설정한 시스템이 있다고 가정해봅시다.

• 첫 번째 1초 동안 3개의 요청이 들어와서 3개의 토큰을 사용했다면, 2개의 토큰이 남아 있게 됩니다.

• 이 2개의 남은 토큰은 다음 시간 구간으로 넘어가서 사용할 수 있습니다. 즉, 다음 1초 동안 5개의 새로운 토큰이 추가로 생성되므로, 총 7개의 토큰(이전에서 남은 2개 + 새로 생성된 5개)이 사용 가능하게 됩니다.

• 이 방식은 시스템이 요청량이 적을 때는 토큰을 쌓아두고, 갑작스럽게 요청이 급증할 때는 쌓인 토큰을 사용하여 더 많은 요청을 처리할 수 있는 유연성을 제공합니다.

누출 버킷 (Leaky Bucket)

누출 버킷 알고리즘은 고정된 속도로 물이 빠져나가는 버킷에 비유할 수 있습니다. 요청이 들어오면 버킷에 물이 채워지고, 물이 넘치는 경우 초과된 요청이 버려집니다. 이는 일정한 처리율을 유지하며, 급격한 요청의 폭증을 완화하는 데 효과적입니다.

• 특징: 고정된 속도로 요청이 처리되며, 버킷이 넘치면 초과된 요청이 거부됨.

• 장점: 안정적인 요청 처리율을 유지하며, 트래픽의 균일한 처리가 가능.

• 단점: 갑작스러운 요청 증가를 효과적으로 처리하지 못할 수 있음.

Example

• 고정된 요청 처리 속도: 요청이 들어오면 버킷에 채워지고, 일정한 속도로 요청이 처리됩니다. 예를 들어, 초당 5개의 요청을 처리하도록 설정할 수 있습니다.

• 버킷이 넘칠 경우: 요청이 너무 많이 들어와 버킷이 넘치게 되면, 초과된 요청은 버려지거나 거부됩니다.

• 일관된 처리 속도: 요청이 급증하더라도, 요청 처리 속도는 항상 일정하게 유지됩니다.

고정 윈도우 카운터 (Fixed Window Counter)

고정 윈도우 카운터는 시간 단위를 고정된 윈도우로 나누고, 각 윈도우 내에서 발생하는 요청 수를 제한하는 방식입니다. 이 알고리즘은 구현이 간단하고 효율적이지만, 특정 시간 경계에서 트래픽이 집중되는 경계 효과(Boundary Effect)가 발생할 수 있습니다.

• 특징: 시간 간격을 고정하고, 각 간격 내에서 허용되는 요청 수를 제한.

• 장점: 구현이 단순하며, 일정한 시간 간격에서의 요청 수 제한이 명확.

• 단점: 시간 경계에서 트래픽 집중이 발생할 수 있음.

Example

• 1분 구간 설정: 00:00에서 00:01까지 100개의 요청을 처리

• 처리 과정: 00:00에서 00:01 사이에 100개의 요청이 들어왔다면, 추가 요청은 거부됩니다.

• 윈도우 리셋: 00:01이 되면 카운터가 0으로 초기화되어 다시 100개의 요청을 처리할 수 있게 됩니다.

경계 효과(Boundary Effect)란?

시간 구간의 경계에서 트래픽이 몰릴 때 발생하는 문제입니다. 이는 특정 시간대에 요청이 집중될 수 있고, 그로 인해 실제로는 더 많은 요청이 허용되는 상황이 발생할 수 있습니다.

Example:

• 00:00:59 - 00:01:00 사이에 100개의 요청이 들어왔고, 00:01:01 - 00:01:02에 새로운 요청이 100개 더 들어온다고 가정

• 이 경우 1분(00:00 - 00:01) 동안 100개, 그 다음 1분(00:01 - 00:02) 동안 100개의 요청이 처리됩니다.

• 하지만 실제로는 00:00:59 - 00:01:01 사이에 200개의 요청이 집중적으로 처리된 것이 됩니다. 즉, 경계 시간에서 요청이 몰리면 짧은 시간 내에 허용된 요청 수보다 더 많은 요청이 처리되는 현상이 발생하는 것이 경계 효과입니다.

이동 윈도우 로그(Sliding Window Log)

이동 윈도우 로그는 요청의 타임스탬프를 기록하고, 최근 일정 기간 내의 요청 수를 제한하는 방식입니다. 고정 윈도우 카운터의 경계 효과 문제를 해결할 수 있지만, 요청 타임스탬프를 기록하고 관리해야 하므로 메모리 사용량이 많아질 수 있습니다.

• 특징: 각 요청의 타임스탬프를 기록하여 최근 일정 기간의 요청 수를 기준으로 제한.

• 장점: 트래픽 패턴의 유연한 처리가 가능하며, 경계 효과 문제를 최소화.

• 단점: 요청 로그를 저장하고 관리해야 하므로 메모리 사용량 증가.

Example

• 1초에 5개의 요청을 허용하는 시스템

• 00:00:00.1에 첫 번째 요청이 발생 → 저장된 타임스탬프: [00:00:00.1]

• 00:00:00.1에 두 번째 요청이 발생 → 저장된 타임스탬프: [00:00:00.1, 00:00:00.1]

• 00:00:00.5에 세 번째 요청이 발생 → 저장된 타임스탬프: [00:00:00.1, 00:00:00.1, 00:00:00.5]

• 00:00:00.8에 네 번째 요청이 발생 → [00:00:00.1, 00:00:00.1, 00:00:00.5, 00:00:00.8]

• 00:00:00.9에 다섯 번째 요청청이 발생 → [00:00:00.1, 00:00:00.1, 00:00:00.5, 00:00:00.8, 00:00:00.9]

이 상황에서 00:00:01.0에 여섯 번째 요청이 들어오면, 최근 1초 내의 요청 수는 이미 5개이므로 요청이 거부.

하지만, 00:00:01.2에 새 요청이 들어오면, 이제 1초 내 요청 기록 중 00:00:00.1에 발생한 요청은 1초 범위를 벗어나므로 삭제

삭제 후, 현재 1초 내 남아 있는 타임스탬프는 [00:00:00.5, 00:00:00.8, 00:00:00.9, 00:00:01.2]

이동 윈도우 카운터(Sliding Window Counter)

이동 윈도우 카운터는 이동 윈도우 로그의 메모리 사용 문제를 해결한 방식으로, 작은 고정된 시간 윈도우를 사용하여 그 합을 계산하는 방법입니다. 이는 경계 효과를 줄이면서도 메모리 사용을 최소화할 수 있습니다.

• 특징: 작은 고정된 시간 윈도우의 합을 계산하여 처리율을 제한.

• 장점: 경계 효과를 줄이면서도 메모리 사용을 효율적으로 관리.

• 단점: 구현이 비교적 복잡할 수 있음.

작동 과정

1. 작은 시간 윈도우 설정:

   • 전체 시간 구간을 여러 개의 작은 고정된 시간 윈도우로 나눕니다.

   • 예를 들어, 1초를 100밀리초씩 나누어 10개의 작은 윈도우로 설정할 수 있습니다.

   • 각 작은 윈도우에서 요청 수를 카운트하고 저장합니다.

2. 요청 발생 시 작은 윈도우 카운터 업데이트:

   • 요청이 발생할 때마다 해당 요청이 속한 작은 시간 윈도우의 카운터를 증가시킵니다.

   • 각 윈도우별로 요청 수를 기록하여, 어느 윈도우에서 몇 개의 요청이 있었는지 추적합니다.

3. 총 요청 수 계산:

   • 새로운 요청이 들어올 때, 설정된 전체 시간 구간(예: 1초) 내의 작은 윈도우들의 카운트 합을 계산합니다.

   • 예를 들어, 최근 1초 동안의 요청 수를 계산하기 위해 현재 시점 기준으로 해당하는 여러 작은 윈도우들의 카운트 값을 더합니다.

4. 요청 허용 여부 결정:

   • 총 요청 수가 허용된 최대 요청 수(예: 1초에 100개)를 넘지 않으면 요청을 처리합니다.

   • 만약 최대 요청 수를 초과하면, 새로운 요청은 거부됩니다.

5. 시간이 지나면 이전 윈도우 무효화:

   • 시간이 지나면 가장 오래된 작은 윈도우의 카운터 값은 제거되거나 무효화됩니다.

   • 최신 윈도우의 카운터 값만 유지하여 최근 요청 수를 기반으로 처리율 제한을 계산합니다.

Example

• 1초에 10개의 요청을 허용한다고 가정하고, 1초를 100밀리초씩 나누어 10개의 작은 윈도우를 설정

• 첫 번째 100밀리초 동안 3개의 요청이 발생 → 윈도우 1의 카운터: 3

• 두 번째 100밀리초 동안 2개의 요청이 발생 → 윈도우 2의 카운터: 2

• 세 번째 100밀리초 동안 4개의 요청이 발생 → 윈도우 3의 카운터: 4

이때 300밀리초가 지난 시점에 총 요청수는 (3+2+4) 9가 됩니다.

이제 4번째 100밀리초 구간에서 2개의 요청이 추가로 발생하면, 총 요청 수는 (3+2+4+2) 11개가 되고, 이때 10이 초과되기때문에 11번째 요청부터는 무효화됩니다.

111100밀리초 부터는 첫번쨰 100 밀리초동안의 3개의 요청이 삭제되어서, 추가적으로 3개까지의 요청을 받을 수 있게됩니다.

처리율 제한 알고리즘의 선택 기준

각 알고리즘은 특정 상황에서 더욱 효과적입니다. 시스템 설계 시 다음과 같은 요소를 고려하여 적절한 알고리즘을 선택해야 합니다.

• 트래픽 패턴: 요청이 일정하게 들어오는지, 아니면 특정 시간대에 급증하는지에 따라 알고리즘을 선택합니다.

• 메모리 사용: 로그나 타임스탬프를 관리해야 하는 알고리즘은 메모리 사용량이 많아질 수 있으므로, 시스템의 자원 제약을 고려합니다.

• 유연성: 급증하는 트래픽에 대해 어떻게 대응할지에 따라 알고리즘을 선택합니다.

• 복잡성: 구현과 유지 관리가 용이한 알고리즘을 선택하는 것도 중요합니다.

분산 환경에서의 처리율 제한

분산 환경에서 처리율 제한기를 관리하는 이유는 일관성 있는 성능과 안정성을 유지하기 위해서입니다. 대규모 시스템에서 여러 서버(또는 인스턴스)에 걸쳐 트래픽을 분산합니다. 이는 일관성 있는 성능과 안정성을 유지하기 위해서입니다.

분산 시스템에서 처리율 제한을 구현하는 것은 단일 서버 환경에서보다 훨씬 더 복잡합니다. 여러 인스턴스가 동시에 동일한 서비스를 제공하는 분산 시스템에서는, 요청이 어느 인스턴스로 전달되더라도 일관된 처리율 제한을 유지해야 합니다. 이는 여러 인스턴스에 걸쳐 처리율 제한 상태를 동기화하는 문제를 포함하며, 잘못 구현될 경우 각 인스턴스가 독립적으로 처리율 제한을 적용해 오히려 요청의 허용치가 예상보다 높아질 수 있습니다.

API 서버 인스턴스 또는 저장소가 많은 이유

성능, 확장성, 가용성을 높이기 위해서 사용합니다. 고가용성을 유지하고 대규모 트래픽을 효율적으로 처리하기 위한 전략입니다.

분산 환경에서의 처리율 제한 구현 방법

분산 환경에서 일관된 처리율 제한을 구현하기 위해, 중앙 집중식 저장소를 활용한 여러 가지 접근법이 있습니다. 여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 추가적인 문제가 발생합니다.(경쟁 조건, 동기화)

경쟁 조건(Race Condition), 동기화 문제

경쟁 조건 문제:

여러 프로세스나 스레드가 동시에 동일한 자원에 접근하거나 수정할 때 발생

분산 환경에서는 여러 서버 인스턴스가 중앙 집중식 저장소(예: Redis) 또는 데이터베이스에 동시에 요청을 처리하려고 할 때, 동일한 처리율 제한 카운터를 동시에 업데이트하려 할 수 있습니다. 이 과정에서 요청이 거의 동시에 처리된다면 서버 간의 카운터 값이 일관되지 않게 업데이트되는 상황이 발생

• 두 대의 서버 A와 B가 있다고 가정. 서버 A와 B는 동일한 Redis에 연결되어 있고, 처리율 제한 카운터를 참조.

• 서버 A가 현재 카운터 값을 읽고 1 증가시키는 동시에, 서버 B도 동일한 카운터 값을 읽고 1 증가시키려고 합니다.

• 이때 경쟁 조건이 발생하면, 서버 A와 B가 카운터 값을 동시에 읽고 증가시키기 때문에, 두 요청 중 하나의 업데이트가 덮어쓰여 최종 카운터 값이 일관되지 않게 됩니다.

동기화 문제:

여러 프로세스나 서버 인스턴스가 공유 자원에 접근하는 동안 일관성을 유지하기 위한 동작을 보장하지 못할 때 발생

분산 환경에서는 여러 서버가 동시에 처리율 제한 카운터를 읽고 쓰면서 각 서버가 서로의 업데이트를 제대로 반영하지 못할 수 있습니다.

해결:

• 분산 락(Distributed Lock) 사용 한 번에 하나의 서버만 자원에 접근. Redlock알고리즘 은 여러 Redis 인스턴스를 사용하는 분산 환경에서 락(lock)을 제공.

• CAS(Compare-And-Set) 기법 사용 저장소에 값을 쓰기 전에, 현재 저장된 값과 내가 기대한 값이 동일한지 확인하는 기법

• Sharding (분할) 기법 사용 요청을 처리하는 서버가 여러 대일 때 각 서버가 자신에게 할당된 요청만 처리하도록 분할하면, 경쟁 조건이 발생할 확률이 줄어듭니다.

분산 환경에서 처리율 제한기를 구현하였을때 문제 해결방법:

• Lua Script: 여러 명령어를 하나의 트랜잭션처럼 실행할 수 있습니다. 예를 들어, GET과 SET 명령어를 동시에 사용해야 할 때, Lua Script를 사용하면 경쟁 조건을 피할 수 있습니다. Lua Script는 원자적 연산을 보장하므로, 여러 클라이언트가 동시에 Redis에 접근하더라도 데이터의 일관성을 유지할 수 있습니다.

Lua 스크립트(Lua Script)

Redis에서 여러 명령을 원자적으로 실행하기 위해 사용하는 스크립트 언어(경쟁 조건 문제를 방지하고, 원자성을 보장). Redis 내부에서 실행되어 복잡한 로직을 하나의 트랜잭션처럼 처리

• Red Lock: 다중 Redis 인스턴스에서 락을 관리하는 방법으로, 분산 환경에서 일관된 락 메커니즘을 제공합니다. 하지만 Red Lock은 복잡성이 높고 성능 오버헤드가 발생할 수 있기 때문에, 단일 Redis 인스턴스에서는 굳이 사용할 필요가 없습니다. 단일 인스턴스 환경에서는 경쟁 조건과 동기화 문제가 발생하지 않기 때문에, 더 간단한 처리율 제한 방법을 사용할 수 있습니다.

Redlock이 복잡하고 성능 오버헤드가 발생하는 이유

단순히 한 Redis 인스턴스에 락을 걸고 푸는 방식이 아니라, 여러 Redis 노드에 분산된 락을 관리하는 메커니즘입니디. 락을 다수의 Redis 노드에서 획득해야 락이 유효하게 설정됩니다. 이는 단일 노드가 아닌 여러 노드에서 일관성을 보장해야 하기 때문에 복잡성이 증가합니다.

그래서, 성능 오버헤드가 발생하는 주요 이유는 여러 노드에 분산된 락을 관리하는 과정에서의 네트워크 통신과 노드 간 동기화 때문입니다.

• 락 획득 시간이 증가: 해당 노드에서 락이 설정되어 있는지 확인, 락이 설정되는 순서를 관리)

• 락 재시도 오버헤드: 남은 노드에서 락을 재시도하거나 이미 설정된 락을 해제하는 재시도 과정

분산 캐시 기반 처리율 제한

Redis와 같은 분산 캐시 시스템을 사용하면, 분산 환경에서도 일관된 처리율 제한을 유지할 수 있습니다. Redis는 높은 성능과 확장성을 제공하는 인메모리 데이터베이스로, 여러 서버 인스턴스가 동일한 상태를 공유하고, 일관된 트래픽 제어를 가능하게 합니다.

• 작동 원리: 모든 서버 인스턴스가 동일한 Redis 데이터베이스를 참조하여, 요청이 발생할 때마다 Redis에 저장된 카운터를 업데이트합니다. 예를 들어, 특정 API에 대한 처리율 제한을 1초에 100개의 요청으로 설정했다고 가정해 보겠습니다. 모든 서버 인스턴스는 요청이 들어올 때마다 Redis의 카운터를 증가시키며, 해당 카운터가 100을 초과하면 요청을 거부하거나 지연시킵니다.

• 장점:

  • 일관성 유지: 모든 인스턴스가 동일한 Redis 키를 참조하기 때문에, 전체 시스템에서 일관된 처리율 제한을 유지할 수 있습니다.

  • 확장성: Redis는 클러스터링을 통해 확장성을 제공하므로, 많은 인스턴스가 동시에 요청을 처리할 수 있습니다.

  • 유연성: Redis의 다양한 데이터 구조(Set, Hash, List 등)를 사용하여 복잡한 처리율 제한 로직을 구현할 수 있습니다.

• 단점:

  • 네트워크 지연: Redis와의 네트워크 통신이 필수적이므로, Redis에 접근하는 데 소요되는 네트워크 지연 시간이 성능에 영향을 미칠 수 있습니다.

  • 단일 장애점: Redis가 단일 장애점(Single Point of Failure)으로 작용할 수 있습니다. 이를 해결하기 위해 Redis 클러스터링 또는 복제를 사용해 고가용성을 보장할 수 있습니다.

API Rate Limiting과 UX

리밋을 초과했을시에는 보통 429 Too Many Request 상태코드를 반환하거나, 지연처리를 통해 큐에 넣어서 일정 시간 이후 처리할 수도 있습니다. 또한, 단순히 요청을 버리는게 아닌, 다시 요청할 수 있는 시간이 얼마나 남았는지 안내하는 방법도 있습니다.