🚦 대규모 시스템 설계 기초 1권 – 4장: 처리율 제한 (Rate Limiting)

1. 처리율 제한(Rate Limiting)이란?

일정 시간 동안 처리할 수 있는 요청 수를 제한하는 기법입니다.

• 과도한 요청(정상적이든 공격이든)으로부터 시스템 자원을 보호, 안정성 보장
• API 또는 서비스에 대한 공정한 사용량 배분 가능
• API abuse, DDoS, 과도한 트래픽 등으로부터 시스템을 보호하는 데 필수적

2. 왜 Rate Limiting이 중요한가?

✅ 서버 과부하 방지

✅ 악의적 사용자/버그로 인한 폭주 대응

✅ 비용 관리 (클라우드 API 호출 등 과금 최소화)

✅ 서비스 품질(QoS) 유지 및 SLA 보장

✅ 공정성 (특정 사용자 독점 방지)

3. 처리율 제한 알고리즘

1️⃣ Token Bucket (🌟실무 인기)

• 일정 속도로 토큰을 생성하여 버킷에 채우고, 요청 시 토큰을 하나 씩 소모
• 토큰이 있으면 허용, 없으면 제한
• 장점: 속도 제한과 burst 처리 허용
• 단점: 토큰 보충 주기나 스케줄링 등 최적의 값을 찾아내는 부분이 까다로움 (구현이 다소 복잡할 수 있음)
• 실제 사용 예시: Google API, AWS API Gateway, Stripe, Twitter 등

2️⃣ Leaky Bucket

• 요청을 큐 (FIFO)에 저장하고, 일정 속도로만 소비, 큐가 넘치면 요청은 차단
• 장점: 고정 속도 유지 (흐름 제어에 유리)
• 단점: burst 요청 처리 불가 (일정 속도로만 요청을 처리하므로)

3️⃣ Fixed Window Counter

• 고정된 시간 구간(예: 1분)마다 요청 수를 카운트하고, 해당 윈도우에서 요청이 limit을 초과하면 요청 차단
  
  • 예: "매 1분당 100건 요청 허용" → user:202406191230이라는 Redis 키로 1분 단위 카운트 저장
• 장점: 구현이 매우 간단
• 단점: 윈도우 경계 시간에 폭발적 요청 (burst) 발생 가능 (59초에 100건 + 다음 초에 또 100건)

4️⃣ Sliding Window Log

• 모든 요청 타임스탬프를 로그로 저장하고, 윈도우 크기만큼의 시간 이전의 로그를 삭제
• 윈도우 크기만큼의 시간 내에서의 요청 수를 체크
• 장점: 가장 정확한 방식으로, 요청 간 간격과 분포까지 확인 가능
• 단점: 로그를 저장하므로 많은 메모리를 사용, 단순한 카운트 증가가 아니므로 성능은 낮다.

3️⃣ Sliding Window Counter

• Fixed Window와 Sliding Window Log 방식의 장점을 취합한 방법
• 슬라이딩 윈도우를 여러 구간으로 나눠, 각 윈도우 내의 개수 합산
  • 최근 10초간 요청 수 합산 = user:{timestamp} 10개 키의 합
• 적절한 정밀도와 성능의 균형

방식	윈도우 경계 문제	정밀도	구현 난이도	메모리 사용
Fixed Window	❌ 있음	보통	쉬움	적음
Sliding Window Log	✅ 없음	매우 높음	높음	높음 (로그 저장)
Sliding Window Counter	✅ 없음	높음	중간	중간 (카운터 합산)

 

 

✅ Redis 를 이용한 알고리즘 구현

• 분산 환경에서 여러 서버가 동일한 Rate Limit 정책을 공유해야 할 때 Redis가 표준처럼 사용됨 
  • 웹 계층은 stateless 하기 때문에, 각 요청에 대해 상태(기록)를 저장하지 않음.
  • 그래서 어떤 사용자의 첫 번째 요청은 서버 A로 가고, 두 번째 요청은 서버 B로 갈 수 있음.
  • 이 경우 서버 A는 사용자의 요청 수를 모르고, 서버 B도 마찬가지여서
    → Rate Limit이 제대로 적용되지 않음 (누적 요청 수 추적 불가)
  • 중앙 Redis를 사용해서 모든 요청 카운트를 하나의 위치에서 관리하면
    → 서버 A든 B든 관계없이 항상 동일한 기준으로 Rate Limit 판단 가능
• 빠른 속도, atomic 연산, 다양한 자료구조, key 만료 기능 등 실무에 적합

 1) Fixed Window Counter

val now = Instant.now().epochSecond
val window = now / windowSeconds
val key = "fixed_rate_limit:$clientId:$window"
val current = redisTemplate.opsForValue().increment(key)
if (current == 1L) redisTemplate.expire(key, Duration.ofSeconds(windowSeconds))

2) Sliding Window Log (ZSet)

val now = System.currentTimeMillis()
val key = "zset_rate_limit:$clientId"
val member = "$now:${UUID.randomUUID()}"
redisTemplate.opsForZSet().add(key, member, now.toDouble())
redisTemplate.opsForZSet().removeRangeByScore(key, 0.0, (now - windowMillis).toDouble())
val count = redisTemplate.opsForZSet().size(key) ?: 0

 

3) Sliding Window Counter (1초 버킷 예시)

val now = Instant.now().epochSecond
val keys = (now - windowSeconds + 1..now).map { "rate_limit:$userId:$it" }
val counts = redisTemplate.opsForValue().multiGet(keys) ?: emptyList()
val total = counts.mapNotNull { it?.toIntOrNull() }.sum()
if (total < limit) {
    val currentKey = "rate_limit:$userId:$now"
    val count = redisTemplate.opsForValue().increment(currentKey)
    if (count == 1L) redisTemplate.expire(currentKey, Duration.ofSeconds(windowSeconds))
}

4) Token Bucket (Lua Script)

-- KEYS[1]: 토큰 개수 key, KEYS[2]: 마지막 리필 시각 key
-- ARGV[1]: capacity, ARGV[2]: refillInterval, ARGV[3]: refillTokens, ARGV[4]: now
local tokens = tonumber(redis.call('get', KEYS[1])) or tonumber(ARGV[1])
local last_refill = tonumber(redis.call('get', KEYS[2])) or tonumber(ARGV[4])
local elapsed = tonumber(ARGV[4]) - last_refill
if elapsed >= tonumber(ARGV[2]) then
    local refill_count = math.floor(elapsed / tonumber(ARGV[2]))
    tokens = math.min(tonumber(ARGV[1]), tokens + refill_count * tonumber(ARGV[3]))
    last_refill = last_refill + refill_count * tonumber(ARGV[2])
    redis.call('set', KEYS[1], tokens)
    redis.call('set', KEYS[2], last_refill)
end
if tokens > 0 then
    redis.call('decr', KEYS[1])
    return tokens - 1
else
    return -1
end

> Spring Data Redis에서 Lua Script를 실행하여 atomic하게 처리

전체 코드: https://github.com/eunhwa99/RealStudy/blob/main/src/main/kotlin/com/example/practice/rate-limit/service/RateLimiterService.kt

---

😬 Redis로 Rate Limiting 처리 시 경쟁 조건이 발생 가능

예: Fixed 또는 Sliding Counter에서 다음 순서로 처리할 때

1. GET key → 현재 count = 4
2. 요청 허용 판단 (limit = 5이므로 OK)
3. INCR key → count = 5
4. 동시에 다른 인스턴스도 GET → 4, INCR → 5
5. 두 요청 모두 허용되어 최대 허용 요청 수 초과 발생

이런 경우 동시 요청이 제한을 우회하는 문제가 발생하게 됩니다.

 

💡 해결 방법 1: Redis Lua 스크립트 (atomic 처리)

Redis는 하나의 Lua 스크립트를 단일 트랜잭션처럼 실행하므로
GET, INCR, EXPIRE를 하나의 원자적 블록으로 처리할 수 있어요.

💡 해결 방법 2: Redisson, Bucket4j (Java/Kotlin에서 atomic 처리 도와주는 라이브러리)

• RedissonRateLimiter는 내부적으로 Lua 스크립트를 사용해서 안전하게 처리합니다.
• Bucket4j는 in-memory 또는 Redis 기반 token bucket 구현체로 경쟁 조건 없이 처리 가능

💡 해결 방법 3: Sliding Window Log 에서 구현한 것처럼 정렬 세트 자료구조 사용

실제로 sliding windows log는 redis 정렬 세트로, 나머지 알고리즘은 lua script로 구현한다고 합니다.

 

---

✅ 그 외 실제 시스템 설계 시 팁

• 버스트 허용 필요 → Token Bucket 사용 추천 (유연성, 실무에서 가장 많이 사용)
• 사용자 등급별 제한 → premium: 1000/min, free: 60/min
• Sliding Window Counter/Log: abuse 방지, 로그인 시도 제한 등 정밀한 제한 필요 시
• Fixed Window: 간단한 내부 서비스, 구현이 매우 쉬움

---

참고 라이브러리
- [Bucket4j](https://github.com/bucket4j/bucket4j): Java/Kotlin에서 Token Bucket, Sliding Window 등 지원, Redis 연동 가능
- [Spring Cloud Gateway RateLimiter](https://docs.spring.io/spring-cloud-gateway/reference/spring-cloud-gateway/rate-limiter.html): Redis 기반 Rate Limiter 내장