가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 4장

🔖 4장 : 처리율 제한 장치의 설계

읽은 날짜 : 2024.08.20

지은이 : 알렉스 쉬

출판사 : 인사이트

 

기억하고 싶은 내용

처리율 제한 장치를 두면 좋은 점

• DoS(Denial of Service) 공격에 의한 자원 고갈 방지
• 서버 개수나 서드 파티 API 사용료에 대한 비용 절감
• 봇(bot)에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽으로 인한 서버 과부하 방지

 

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

• 클라이언트 측 제한 장치인가, 서버 측 제한 장치인가?
• 서버 측이라면 API 호출을 제어하는 기준은? - IP 주소, 사용자 ID 등
• 시스템의 규모는?
• 시스템이 분산 환경에서 동작해야 하는가?
• 처리율 제한 장치는 독립적인 서비스인가, 애플리케이션 코드에 포함될 수 있는가?
• 사용자의 요청이 처리율 제한 장치에 의해 걸러진 경우, 사용자에게 그 사실을 알려야 하는가?

 

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

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

• 클라이언트 보다는 서버 측 또는 별도의 미들웨어로 구현하는 것이 효과적이다.
  • 클라이언트의 요청은 쉽게 위변조가 가능하기 때문이다.
  • 다양한 클라이언트가 있을 수 있고 모두 통제하는 게 어렵다.
• 클라우드 MSA의 경우 API 게이트웨이에 구현한다.
  
  • 클라우드 업체에서 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리를 지원한다.
• 서버에 두어야 할까, API 게이트웨이에 둬야 할까? 
  • 현재의 기술 스택(프로그래밍 언어, 캐시 서비스 등)을 점검하여 서버 측 구현을 지원하기 충분한지 확인한다.
  • 사업에 맞는 처리율 제한 알고리즘을 찾는다. 다만, 서드파티 API 게이트웨이를 사용한다면 선택지는 제한될 수 있다. 
  • MSA를 기반하고 있고 API 게이트웨이를 이미 설계에 포함시켰다면, API 게이트웨이에 포함시켜야 할 수도 있다.
  • 처리율 제한 장치를 구현할 인력이 부족하다면 서드파티 API 게이트웨이를 쓰는 게 좋을 것이다.

처리율 제한 알고리즘

• 토큰 버킷(token bucket)
  
  • 동작 원리
    • 사전 설정된 양의 토큰이 주기적으로 채워지고, 각 요청이 처리될 때마다 하나의 토큰을 사용한다.
    • 충분한 토큰이 있으면 버킷에서 토큰을 하나 꺼낸 후 시스템에 요청을 전달한다.
    • 충분한 토큰이 없으면 해당 요청은 버려진다.
  • 장점
    • 구현이 쉽다.
    • 메모리 사용 측면에서 효율적이다.
    • 짧은 시간에 집중되는 트래픽도 처리 가능하다. 
  • 단점
    • 버킷 크기와 토큰 공급률 인자를 적절하게 튜닝하는 것이 까다롭다.
• 누출 버킷(leaky bucket)
  
  • 동작 원리
    • 요청이 도착하면 큐를 확인하여, 큐에 빈자리가 있으면 요청을 추가한다.
    • 큐가 가득 차 있으면 새 요청은 버린다.
    • 지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
  • 장점
    • 메모리 사용 측면에서 효율적이다.
    • 고정된 처리율을 갖고 있어, 안정적 출력이 필요한 경우 적합하다.
  • 단점
    • 단 시간에 많은 트래픽이 몰리면 큐에 오래된 요청이 쌓이고, 그 요청을 제때 처리 못하면 최신 요청은 버려진다.
    • 버킷 크기, 처리율 인자를 적절하게 튜닝하는 것이 까다롭다.
• 고정 윈도 카운터(fixed window counter)
  • 동작 원리 
    • 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
    • 요청이 접수될 때마다 이 카운터의 값은 1씩 증가한다.
    • 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.
  • 장점
    • 메모리 사용 측면에서 효율적이다.
    • 이해하기 쉽다.
    • 윈도가 닫히는 시점에 카운터를 초기화하는 방식 -> 특정한 트래픽 패턴을 처리하기에 적합하다.
  • 단점
    • 윈도 경계 부근에서 트래픽이 집중되는 경우 시스템에 설정된 처리 한도보다 많은 요청을 처리하게 된다.
• 이동 윈도 로그(sliding window log)
  • 동작 원리
    • 요청의 타임스탬프를 추적한다. (타임스탬프는 보통 레디스의 sorted set 같은 캐시에 보관)
    • 새 요청이 오면 만료된 타임스탬프는 제거한다.
    • 새 요청의 타임스탬프를 로그에 추가한다.
    • 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우 처리를 거부한다.
  • 장점
    • 어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
  • 단점
    • 거부된 요청의 타임스탬프로 보관하기 때문에 메모리를 많이 사용한다.
• 이동 윈도 카운터(sliding window counter)
  • 동작 원리
    • 현재 윈도에 [ 현재 1분간의 요청수 + 직전 1분간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율 ] 개의 요청이 온 것으로 보고 다음 요청을 처리할지 말지 결정한다.
  • 장점
    • 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산 -> 짧은 시간대에 몰리는 트래픽에 잘 대응한다.
    • 메모리 사용 측면에서 효율적이다.
  • 단점
    • 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다.

개략적인 아키텍처

• 요청의 개수를 추적하는 대상 : 사용자, IP 주소 단위, API 엔드포인트 단위, 서비스 단위
• 카운터를 보관하는 장소 : 레디스와 같은 캐시(데이터베이스보다 빠름)
• 동작 원리
  • 클라이언트가 처리율 제한 미들웨어에게 요청을 보낸다. 
  • 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 아닌지 검사한다.
  • 한도에 도달하면 요청은 거부된다.
  • 한도에 도달하지 않았다면 요청은 API 서버로 전달된다. 미들웨어는 카운터의 값을 증가시킬 후 다시 레디스에 저장한다.

 

3단계 : 상세 설계

처리율 제한 규칙

• 예시 1 : 시스템이 처리할 수 있는 마케팅 메시지의 최대치는 하루 5개
• 예시 2 : 클라이언트가 분당 5회 이상 로그인 할 수 없도록 제한
• 이런 규칙들은 보통 설정 파일 형태로 디스크에 저장된다.

 

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

• 어떤 요청이 한도 제한에 걸리면 API는 429 응답(too many requests)을 클라이언트에 보낸다.
• 경우에 따라서는 한도 제한에 걸린 메시지를 나중에 처리하기 위해 큐에 보관한다. (e.g. 주문 시스템)
• 클라이언트는 HTTP 응답 헤더를 보고 제한에 걸릴 때까지 얼마나 많은 요청을 보낼 수 있는지 알 수 있다.
  • X-Ratelimit-Remaining : 윈도 내에 남은 처리 가능 요청의 수
  • X-Ratelimit-Limit : 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
  • X-Ratelimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 다시 시도해야 하는지

 

상세 설계

1. 처리율 제한 규칙은 디스크에 보관. 작업 프로세스는 수시로 규칙을 디스크에서 읽어서 캐시에 저장.
2. 클라이언트가 요청을 서버에 보내면 처리율 제한 미들웨어에 먼저 도달함
3. 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져옴. 카운터 및 마지막 요청의 타임스탬프를 레디스에서 가져옴.
   1. 처리율 제한에 걸리지 않으면 API 서버로 보냄
   2. 처리율 제한에 걸렸다면 429로 클라이언트에 응답하고, 메시지를 버리거나 메시지 큐에 보관

 

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

• 여러 대의 서버와 병렬 스레드를 지원하도록 확장할 때, 경쟁 조건과 동기화 이슈를 풀어야 한다.
• 경쟁 조건
  • 문제 : 서로 다른 요청을 처리하는 스레드가 병렬로 counter 값을 읽어서 변경하려는 경우
  • 해결 방법 :
    • 락(lock)은 시스템의 성능을 떨어뜨린다.
    • 레디스에서 루아 스크립트(Lua Script)를 돌려서, 스크립트가 실행되는 동안 다른 요청이 간섭하지 못하도록 한다.
    • 레디스의 정렬 집합(sorted set) 자료 구조 사용
• 동기화 이슈
  • 문제 : 여러 클라이언트가 여러 처리율 제한 장치로 요청을 보내게 되는 경우 동기화가 필요해짐
  • 해결 방법 :
    • 고정 세션을 활용하여 같은 클라이언트의 요청은 항상 같은 처리율 제한 장치로 보내게 한다. (규모 확장이 어렵고 유연성이 떨어짐)
    • 레디스와 같은 중앙 집중형 데이터 저장소를 쓴다.

 

오늘 읽은 소감

처리율 제한 장치는 서버측이나 별도의 미들웨어에 두며, 서비스/사용자/IP/API 단위로 제한할 수 있다는 것을 알게 되었습니다.

또한 레디스와 같은 캐시를 두어 요청 횟수를 저장하고, 한도에 다다르면 요청을 거부하거나 또는 메시지 큐에 저장하고 429 응답을 주면 된다는 것을 알게 되었습니다.

마지막으로 분산 환경에서 경쟁 조건 발생 시 루아스크립트 또는 레디스 정렬 집합 자료구조로 해결할 수 있다는 것을 알게 되었습니다.

별도의 미들웨어로 처리율을 제한하는 방법에 대해 전반적으로 이해할 수 있었습니다.

 

 

궁금한 내용 & 잘 이해되지 않는 내용

루아 스크립트(Lua script)

• Lua라는 프로그래밍 언어로 작성된 스크립트. 
• 레디스 2.6 버전부터 루아 스크립트 엔진이 추가되어, 레디스 서버에서 루아 스크립트를 실행할 수 있습니다.
• 여러 레디스 명령어를 하나의 스크립트로 묶어 실행하고, 이는 원자적(atomic)으로 실행되어 중간에 다른 클라이언트가 동일 자원에 접근할 수 없습니다. 이로써 경쟁 조건 문제를 피할 수 있습니다.

레디스 정렬 집합(Sorted set)

• Set 자료구조에 Score를 추가로 기록하여 score가 낮은 순서부터 높은 순서대로 정렬되는 자료구조.
• Sorted Set 자체가 직접적으로 경쟁 조건을 해결하는 것은 아닙니다. score를 타임스탬프로 설정하여 공유 자원에 대한 변경의 순서를 파악할 수 있으므로 경쟁 조건을 완화할 수 있는 것입니다.

참고

https://dev.gmarket.com/69

https://redis.io/docs/latest/develop/data-types/sorted-sets/

https://velog.io/@hgs-study/redis-sorted-set

https://mahdie-asiyaban.medium.com/implementing-scalable-rate-limiting-in-a-distributed-environment-with-lua-scripts-and-redis-sorted-3d743ab8734a