처리율제한장치의설계

1. 처리율 제한 장치 (Rate Limiter) 개요

네트워크 시스템에서 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하는 장치입니다. 요청 횟수가 정의된 **임계치(threshold)**를 넘어서면 추가 호출은 처리가 중단(block)됩니다.

• 사용 목적
  • DoS(Denial of Service) 공격에 의한 자원 고갈 방지 (예: 트위터, 구글 독스 API 제한).
  • 비용 절감 (서버 감소, 제3자 API 사용료 관리).
  • 서버 과부하 방지 (봇이나 잘못된 이용 패턴으로 인한 트래픽 걸러내기).

1단계: 문제 이해 및 설계 범위 확정

시스템 요구사항

• 설정된 처리율을 정확하게 제한.
• 낮은 응답시간 유지.
• 가능한 한 적은 메모리 사용.
• 분산형 처리율 제한 지원 (여러 서버/프로세스 공유).
• 예외 처리: 요청 제한 시 사용자에게 분명하게 알림 (예: HTTP 429 응답).
• 높은 결함 감내성: 제한 장치 장애가 전체 시스템에 영향을 주면 안 됨.

2. 개략적 설계안 제시 및 동의 구하기

처리율 제한 장치의 위치

클라이언트 요청은 쉽게 위변조가 가능하므로, 처리율 제한 장치는 일반적으로 서버 측에 두어야 합니다.

• API 서버 자체: 서버 측 구현.
• 처리율 제한 미들웨어(rate limiter): API 서버로 가는 요청을 통제하도록 합니다.
• API 게이트웨이: 클라우드 마이크로서비스 환경에서 처리율 제한, 인증, IP 허용 목록 등을 지원하는 컴포넌트
  • 기능 중 하나가 rate limiter가 된다.
  • graphql https://tech.kakao.com/posts/364
    • restful은 항상 동사다 delete.. ⇒ 엔드포인트가 여러개다 → 공통으로 무엇인가를 잡을 수 없다
    • POST /graphql 형식으로 쿼리문을 떤진다! ⇒ 엔드 포인트가 하나다
      • 무한제귀로 돌 수 있는 가능성이 있으므로 rate limit을 기능으로 넣어두었다. lib를 봐라
      • 이 외에도 time limit 등이 있다.
  • 사용 환경 : 데이터를 명확히 넘겨줄 수 없을 때, 클라와 서버간의 조율을 줄이기 위함이다. ⇒ restful은 정확히 소통해야 함

처리율 제한 알고리즘

정리

알고리즘 동작 원리 장점 단점

토큰 버킷 (Token Bucket)	주기적으로 토큰이 채워지는 버킷을 사용하며, 요청마다 토큰 1개 사용.	구현이 쉽고, 메모리 효율적이며, 짧은 시간에 집중되는 트래픽(burst) 처리가 가능함.	버킷 크기/토큰 공급률 튜닝이 까다로움.
누출 버킷 (Leaky Bucket)	FIFO 큐를 사용하며, 요청 처리율이 고정되어 있음.	메모리 사용량 효율적, 고정된 처리율(안정적 출력)이 필요할 때 적합.	단시간 트래픽 집중 시 오래된 요청이 쌓여 최신 요청이 버려질 수 있음.
고정 윈도 카운터 (Fixed Window Counter)	고정된 시간 간격(윈도)마다 카운터를 사용/초기화.	메모리 효율 좋고 이해하기 쉬움.	윈도 경계 부근 트래픽 집중 시 허용 한도보다 더 많은 요청이 처리될 수 있는 중대한 문제.
이동 윈도 로깅 (Sliding Window Log)	요청의 타임스탬프를 추적하고 만료된 타임스탬프를 제거.	아주 정교한 처리율 제한 메커니즘 제공.	거부된 요청 포함 다량의 타임스탬프를 보관하여 많은 메모리를 사용함.
이동 윈도 카운터 (Sliding Window Counter)	이전 시간대 요청 수와 현재 윈도의 겹치는 비율을 계산하여 추정.	짧은 시간에 몰리는 트래픽에 잘 대응하며 메모리 효율이 좋음.	추정치 계산에 기반하므로 다소 느슨함.

1. 토큰 버킷 (Token Bucket)
   • 일정 시간마다 토큰을 채워주는 방식으로 동작
   • 간단하고 폭넓게 이용되며, 짧은 시간에 집중되는 트래픽(burst of traffic) 처리 가능하다는 장점이 있습니다.
   • 버킷 크기와 토큰 공급률이라는 두 인자를 튜닝하는 것이 까다롭다는 단점이 있습니다.
   • https://etloveguitar.tistory.com/128
2. 누출 버킷 (Leaky Bucket)
   • 토큰 버킷과 비슷하지만 요청 처리율이 고정되어 있습니다.
   • 고정된 처리율이 필요하거나 메모리 사용량 측면에서 효율적이지만, 단시간에 트래픽이 몰리면 오래된 요청이 쌓여 최신 요청이 버려질 수 있습니다.
   • https://etloveguitar.tistory.com/127
3. 고정 윈도 카운터 (Fixed Window Counter)
   1. 버킷에는 정해진 시간 단위로 window가 만들어진다.
   2. window에 요청 건수가 기록된다
   3. 해당 window의 요청 건수가 정해진 건수보다 크면 해당 요청은 처리가 거부된다.
   • 타임라인을 고정된 간격의 윈도로 나누고 카운터를 사용합니다.
   • 윈도 경계 부근에 트래픽이 집중될 경우 허용 한도보다 더 많은 요청이 처리될 수 있다는 중대한 문제가 있습니다.
   • https://etloveguitar.tistory.com/129
4. 이동 윈도 로깅 (Sliding Window Log)
   1. 이 알고리즘은 도착하는 모든 요청의 타임스탬프(timestamp)를 추적하여 로그(log)에 보관합니다. 이 데이터는 보통 레디스(Redis)의 정렬 집합(sorted set) 같은 캐시에 보관됩니다.
   2. 새 요청이 오면, 먼저 현재 윈도의 시작 시점보다 오래된 만료된 타임스탬프는 로그에서 제거합니다.
   3. 이후 새 요청의 타임스탬프를 로그에 추가합니다.
   4. 로그의 크기(현재 윈도 내 요청 수)가 허용치보다 같거나 작으면 요청을 전달하고, 크면 요청 처리를 거부합니다
   • 요청의 타임스탬프를 추적하여 고정 윈도 카운터의 문제를 해결합니다.
   • 아주 정교한 처리율 제한이 가능하지만, 거부된 요청의 타임스탬프까지 보관하기 때문에 다량의 메모리를 사용한다는 단점이 있습니다.
   • https://etloveguitar.tistory.com/130
   • 질문: 외부 서비스(트위터, 카카오페이..)는 알아서 rate limit을 이미 설정이 되어있다.
     • https://developer.x.com/en/docs/x-api/v1/rate-limits
   • 그치만 내부 서비스도 당연히 rate limit을 설정해놓아야 한다. 왜냐하면 외부 서비스에 rate limit이 걸리면 내부 서비스도 망가지는 경우가 있다.
   • 근데? 이 정도로 빡빡하게 내부 서비스에서도 rate limit을 관리..해야되나? → 마무리에 경성 처리율 제한과 연성 처리율 제한을 참고하면 됨!
   • + 질문할 때 전제조건을 제시하면 더 적합한 답변이 나올 수 있다.
     • 어뷰징이라는 게 있기 때문에.. 커머스에서는 웬만하면 다 해야한다
5. 이동 윈도 카운터 (Sliding Window Counter)
   1. 현재 시간(Current Time)이 직전 윈도(Previous Window)와 현재 윈도(Current Window) 사이에 있다고 가정합니다.
   2. 새 요청이 현재 윈도에 도착했을 때, 시스템은 다음과 같은 공식을 사용하여 현재 윈도에 들어 있는 요청 수를 추정합니다
   • 추정 요청 수=(현재 1분간의 요청 수)+(직전 1분간의 요청 수)×(이동 윈도와 직전 1분이 겹치는 비율)
   3. 이 추정 요청 수가 처리율 제한 한도를 넘지 않으면 요청을 시스템으로 전달합니다
   • 고정 윈도 카운터와 이동 윈도 로깅을 결합한 것입니다.
   • 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에 잘 대응하며 메모리 효율이 좋습니다.
   • https://medium.com/@avocadi/rate-limiter-sliding-window-counter-7ec08dbe21d6

개략적인 아키텍처

처리율 제한 장치의 카운터는 메모리 기반 캐시(예: Redis)에 보관하는 것이 바람직합니다.

Redis는 INCR (카운터 증가)과 EXPIRE (타임아웃 설정) 명령어를 지원하여 카운터를 추적합니다.

• 기본 흐름: 클라이언트 요청 → 처리율 제한 미들웨어 → Redis (카운터 검사) → (한도 초과 시 거부) / (한도 내 시 API 서버 전달 및 카운터 증가).

 

3. 상세 설계

처리율 제한 규칙 및 처리 전략

• 규칙 저장: 규칙은 보통 설정 파일(configuration file) 형태로 디스크에 저장되며, 작업 프로세스가 읽어 캐시에 저장합니다.
  • 레디스의 경우 루아 스크립트로 작성하여 디스크에 저장된다
• 한도 초과 처리: 클라이언트에게 HTTP 429 (Too many requests) 응답을 반환하며, 때로는 제한된 메시지를 나중에 처리하기 위해 큐에 보관할 수 있습니다.
  • 클라이언트 통신 (HTTP 헤더):
    • X-Ratelimit-Remaining: 남은 요청 수.
    • X-Ratelimit-Limit: 윈도당 허용 요청 수.
    • X-Ratelimit-Retry-After: 재시도까지 대기 시간 (초 단위).

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

분산 환경에서는 경쟁 조건과 동기화 이슈를 해결해야 합니다.

1. 경쟁 조건 (Race Condition): 병행성(concurrency)이 심한 환경에서 카운터 읽기/증가 시 부정확한 값이 발생할 수 있습니다.
   • 해결: 성능 저하를 일으키는 락(lock) 대신, 루아 스크립트(Lua script)나 정렬 집합(sorted set)과 같은 레디스 자료구조를 활용할 수 있습니다.
   • → 레디스가 싱글 스레드라서 락을 신경 쓸 필요가 없기 때문에 해결이라고 보기 어렵다
2. 동기화 (Synchronization): 여러 대의 제한 장치 서버가 있을 때, 요청이 분산되면 동기화 없이는 올바른 제한을 수행할 수 없습니다.
   • 해결: 레디스와 같은 중앙 집중형 데이터 저장소를 사용하는 것이 규모 확장 가능하고 유연한 해결책입니다 (고정 세션은 비추천).
   • 알아두면 좋은 레디스가 제공하는 레드락https://mangkyu.tistory.com/311
   • https://hstory0208.tistory.com/entry/%EB%B6%84%EC%82%B0%EB%9D%BD%EC%9D%84-%EC%A0%81%EC%9A%A9%ED%95%B4-%EB%8F%99%EC%8B%9C%EC%84%B1-%EB%AC%B8%EC%A0%9C-%ED%95%B4%EA%B2%B0%ED%95%98%EA%B8%B0

dynamo DB → key value 데이터 베이스이고, 메모리 캐시보다는 영속성이 있다! 

document DB → 몽고DB다

성능 최적화 및 모니터링

• 성능 최적화: 지연시간(latency)을 줄이기 위해 사용자와 가장 가까운 위치에 있는 에지 서버(edge server)로 트래픽을 전달합니다. 또한, 제한 장치 간 데이터 동기화 시 최종 일관성 모델(eventual consistency model)을 고려할 수 있습니다.
• 모니터링: 알고리즘과 규칙이 효과적인지 확인하기 위해 데이터를 수집합니다. (예: 유효 요청이 너무 많이 버려진다면 규칙 완화, 트래픽 급증 시 토큰 버킷으로 알고리즘 변경 등).

4. 마무리

시간이 허락한다면 다음과 같은 추가적인 논의를 언급할 수 있습니다.

• 경성(hard) vs. 연성(soft) 처리율 제한
  • 경성은 임계치를 절대 넘지 못하게 하고, 연성은 잠시 동안 임계치를 넘어설 수 있도록 허용합니다.
  • hard limit, soft limit
• 다양한 계층에서의 제한
  • 애플리케이션 계층(HTTP/OSI 7번 계층)뿐만 아니라, IP 주소(OSI 3번 계층)에도 Iptables를 사용하여 제한을 적용할 수 있습니다.
    • ip 주소나 mac 주소로 걸기도 함
    • Iptables로 제한을 걸진 않음
    • 솔루션 적으로 ip를 막는 방식을 선택하기도 함
• 클라이언트 측 처리율 제한 회피 전략
  • 클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄임.
  • 처리율 제한 임계치를 이해하고 메시지 전송을 조절.
  • 재시도(retry) 로직 구현 시 충분한 백오프(back-off) 시간을 둠.