새로운 내용을 공부할 때
새로운 내용의 공부를 시작할 때 용어의 정의를 이해하지 못하거나 정확하게 알지 못한다면 그 용어가 포함된 문장을 이해하지 못합니다.
작은 단어 하나가 내용을 이해하지 못하게 하기 때문에 용어를 정확하게 이해하는 것이 중요합니다.

3 분 소요

시스템 안정성과 과도한 트레픽을 제어하고 보안 및 사용자의 빠른 응답을 제공하는 것이 백엔드 개발자의 중요한 숙제라고 생각이 들었습니다.

Ratelimit(속도 제한)은 API서버에서 과도한 요청으로 서버를 보호하고 제한된 자원을 공정하게 분배하기 위한 기술이므로 학습하려고 합니다.

상황정의Permalink

서버에 로그인 API가 있다.

같은 사용자가 1분 안에 5번 이상 로그인 요청을 보내면 더 이상 허용하지 않고 차단해야 한다.

Step 1. 어떤 정보가 필요할까?Permalink

이 문제를 해결하기 위해 서버는 어떤 정보를 기억하고 있어야 할까?

  1. 같은 사용자의 요청인지 구분할 수 있는 식별자 정보를 가지고 있어야한다.(인증)
  2. 사용자의 요청 시간과 요청 리소스 주소를 누적으로 저장할 수 있어야한다.
  3. 같은 사용자의 누적된 요청 시간중 처음 요청과 5번째 요청 사이의 시간이 1분 이내로 횟수를 계산할 수 있어야한다.
  4. 횟수를 계산하여 5회 이상인 경우 사용자가 요청할 수 없는 차단 상태라는 것을 서버나 클라이언트에 저장해야한다.

GPT 답Permalink

  1. 사용자마다 따로 기록해야한다 → 사용자 식별자 기반의 분리된 공간 필요.
  2. 요청 시간들을 저장해야 한다. → 시계열 데이터
  3. 최근 요청 중 5번째 요청의 시간과 처음의 시간을 비교해야한다. → 시간 간격 판단이 가능해야한다.
  4. 첫번째 요청 시간 - 5번째 요청시간 < 1분이라면 차단할 수 있다.

Step 2.구조를 어떻게 잡을까?Permalink

사용자별로 요청 시간들을 저장하고, 그 중 “가장 오래된 5번째 요청 시간”을 빠르게 찾고,

새 요청이 오면 제일 오래된 걸 지우고 새로운 걸 넣어야 한다면,

어떤 특징을 가진 자료구조를 쓰면 좋을까?

  1. 사용자 별로 요청 시간을 저장하고, 삭제, 탐색해야한다.
  2. 새 요청이 오면 제일 오래된 것을 지워야한다.
  3. 첫번째와 다섯번째 요청의 자료를 빠르게 찾을 수 있어야한다,

큐(Queue)가 이상황에서 제일 적합하다.

FIFO 구조로 → 가장 오래된 요청이 항상 맨 앞에 있다.

배열 기반이 아닌 연결 리스트 기반 큐라면 삽입, 삭제가 O(1) 이다.

순서가 보장이 필요하므로 최적이다.

Step 3. 클래스 뼈대 설계Permalink

LoginRateLimiter 클래스 뼈대를 만들기

  • boolean isAllowed(String userId)

→ 이 사용하의 요청이 허용되는지 판단하고, 허용되면 시간을 기록해야한다.

클래스 안에 어떤 필드를 만들어야 할까

  1. 사용자 별로 요청 기록을 저장해야한다.

  2. 사용자가 첫번째 요청과 5번째 요청의 시간의 차이를 알 수 있어야한다.

#### 사용자를 조회하는 방법

식별된 사용자를 저장하고 탐색하는 과정을 메모리 위에서 사용할 효율적인 자료구조가 필요합니다.

여러 가지 자료구조 중에서 다음과 같은 방안을 고민해볼 수 있습니다.

사용자를 조회 및 관리하는 방법Permalink

  1. Red-Black Tree (TreeMap)
    • 데이터 삽입, 삭제, 탐색 모두 최악의 경우에도 O(log N)의 성능을 보장합니다.
    • 균형을 유지하기 위해 자동 리밸런싱이 수행되므로 데이터 크기가 커질수록 일관된 성능 유지에 적합합니다.
  2. Hash Table (HashMap)
  • 평균적으로 탐색과 삭제가 O(1)이지만, 해시 충돌이 많아지면 최악의 경우 O(N)이 될 수 있습니다.

  • 사용자 수가 적거나 해시 분포가 균일할 경우 매우 효율적입니다.
  • 사용자 수가 많고 예측 가능한 성능이 중요하다면 Red-Black Tree가 더 적합할 수 있습니다.

추가로 고려해볼 사항Permalink

멀티스레드 환경에서의 동시성 안전성Permalink
  • ConcurrentHashMap, ConcurrentSkipListMap과 같은 자바의 동시성 컬렉션 사용을 고려해야 합니다.
TTL(Time To Live)Permalink

사용자가 일정 시간 동안 요청을 하지 않을 경우 해당 요청 정보를 제거할 수 있어야 합니다.

TTL 은 “데이터가 얼마 동안 유효한지”를 의미합니다.

  • 캐시: 데이터 만료 시간
  • 네트워크: 패킷의 생존 시간
  • API: 클라이언트 캐시 제어
  • 세션/토큰: 인증 만료 시간

자바에서는 ScheduledExecutorService, Guava Cache, Caffeine 등을 활용하여 TTL을 관리할 수 있습니다.

사용자 수가 많을 경우 메모리 관리Permalink

회원 요청에 대한 관리를 하기 위해 전체 저장 용량을 제한해야할 때 사용할 수 있는 알고리즘으로 오래된 데이터, 사용하지 않는 데이터를 제거할 수 있습니다.

LRU( Least Recently Used )

가장 최근에 사용된것을 유지한다.

"”최근에 사용된 것일수록 다시 사용될 가능성이 높다”는 시간 기반 캐시 전략입니다.

사용될 때마다 최신으로 갱신하고, 가장 오래된 것부터 제거합니다.

구현이 간단하며 LinkedHashMap(accessOrder=true)을 사용하면 간단히 구현이 가능합니다.

  • 운영체제 메모리 테이블에서 사용하는 방식
  • 웹 브라우저의 방문 기록 캐시
  • 자바의 Guava, Caffeine 전략 중 하나

LFU( Least Frequently Used )

가장 여러번 사용한 것을 유지한다.

"”자주 사용되는 데이터일 수록 유지한다”는 횟수 기반 캐시 전략입니다.

접근 횟수를 따로 저장해서 가장 적게 사용된 항목부터 제거합니다.

구현 복잡도는 높습니다. Heap, TreeMap 등과 조합해 Count 기반으로 구현이 필요합니다.

메모리 관리에서 고려해야할 사항Permalink

LRU

데이터를 사용할 때마다 위치를 갱신해야한다.

LinkedHashMap : 맨 뒤로 이동 O(1) 으로 구현가능하지만 자주 데이터가 이동한다.

성능 저하 요소 : O(1) 이 자주 발생

LFU

데이터를 사용할 때마다 사용횟수를 갱신하고 정렬해야 한다

정렬 구조(Heap, TreeMap)에서 탐색 및 갱신 , 정렬이 필요하여 최소 O(log N)~O(N)이 필요하다.

성능 저하 요소 : O(log N) 이 필요

확장해볼만한 가능성Permalink

W-TinyLFU(Caffein 전략)

LFU의 문제는 정확한 사용 횟수를 계속 정렬하며 저장한다는 것

해결 방안

정확하게 세지 않고, “얼마나 많이 본 것 같다”는 것을 기반으로 근사치로 빠르게 계산한다.

댓글남기기