[Study] 4장) 처리율 제한 장치의 설계

처리율 제한 장치(rate limiter)?

• 네트워크 시스템에서 클라이언트 or 서비스가 보내는 트래픽의 처리율(rate)를 제어하기 위한 장치
• ex) HTTP
  - 특정 기간 내에 전송되는 클아이언트의 요청 횟수를 제한
  • API 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리가 중단됨
  • 사례
  1. 사용자는 초당 2회 이상 새 글을 올릴 수 없음
  2. 같은 IP 주소로 하루에 10개 이상의 계정 생성 불가
  3. 같은 디바이스로는 주당 5회 이상 리워드(reward) 요청 불가

이번 장에서는 이 처리율 제한 장치를 설계할 것

설계하기 전, API에 설계율 제한 장치를 두면 좋은 점
1. Dos(Denial of Service) 공격에 의한 자원 고갈(resource starvation) 방지
- 처리율 제한 장치가 추가 요청에 대해 처리를 중단함으로써 Dos 공격을 방지
- ex) 트위터 -> 3시간 동안 300개의 트윗만 올릴 수 있게 제한
- ex) 구글 독스 -> API를 사용자당 분당 300회의 read 요청만 허용함
2. 비용 절감
- 추가 요청에 대한 처리를 제한하면 서버가 많을 필요 x
- 우선순위가 높은 API에 더 많은 자원 할당 가능
- ex) 신용 확인, 신용카드 결제를 위해 호출하는 API에 대한 과금이 횟수에 따라 이뤄진다면 횟수를 제한해야 비용이 줄 것
3. 서버 과부하를 막음
- 봇(bot)에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러낼 떄 처리율 제한 장치 활용 가능

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

• 처리율 제한 장치를 구현할 때 여러 알고리즘을 사용할 수 있고 각각 장단점을 가지고 있기 때문에 면접관과의 소통을 통해 알맞은 제한 장치를 구현하자

  면접관과의 대화
  지원자: 어떤 종류의 처리율 제한 장치를 설계해야 하나요? 클라이언트 측 제한 장치입니까, 아니면 서버 측 제한 장치입니까?
  면접관: 좋은 질문이에요. 서버측 API를 위한 장치를 설계한다고 가정합시다.
  지원자: 어떤 기준을 사용해서 API 호출을 제어해야 할까요? IP 주소를 사용해야 하나요? 아니면 사용자 ID? 아니면 생각하는 다른 어떤 기준이 있습니까?
  면접관: 다양한 형태의 제어 규칙(throtling role)을 정의할 수 있도록 하는, 유연한 시스템이어야 합니다.
  지원자: 시스템 규모는 어느 정도여야 할까요? 스타트업 정도 회사를 위한 시스템입니까 아니면 사용자가 많은 큰 기업을 위한 제품입니까?
  면접관: 설계할 시스템은 대규모 요청을 처리할 수 있어야 합니다.
  지원자: 시스템이 분산 환경에서 동작해야 하나요?
  면접관: 그렇습니다.

  Interview -
  지원자: 이 처리율 제한 장치는 독립된 서비스입니까 아니면 애플리케이션 코드에 포함될 수도 있습니까?
  면접관: 그 결정은 본인이 내려주시면 되겠습니다.
  지원자: 사용자의 요청이 처리율 제한 장치에 의해 걸러진 경우 사용자에게 그
  사실을 알려야 하나요?
  면접관: 그렇습니다.

요구사항
1. 설정된 처리율을 초과하는 요청은 정확하게 제한

→ 이건 "처리율 제한 장치"라는 주제 자체에서 나오는 핵심 요구사항
"처리율 제한 장치 만들어주세요" = "정확하게 제한해주세요"

2. 낮은 응답 시간 -> 이 처리율 제한 장치는 HTTP 응답시간에 나쁜 영향을 주어선 안 됨

질문: "대규모 요청을 처리해야 하나요?"
답변: "그렇습니다"
→ 요구사항 2, 3번: 낮은 응답시간, 적은 메모리

3. 가능한 한 적은 메모리

질문: "대규모 요청을 처리해야 하나요?"
답변: "그렇습니다"
→ 요구사항 2, 3번: 낮은 응답시간, 적은 메모리

4. 분산형 처리율 제한(distributed rate limiting): 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 함

질문: "분산 환경에서 동작해야 하나요?"
답변: "그렇습니다"
→ 요구사항 4번: 분산형 처리율 제한

5. 예외 처리 -> 요청이 제한되었을 땐 그 사실을 사용자에게 정확하게 보여 줘야 함

질문: "서버측 API를 위한 장치인가요?"
답변: "그렇습니다"
→ 요구사항 5번: 예외 처리 필요 (서버가 클라이언트에게 응답해야 함)

6. 높은 결함 감내성(fault tolerance) -> 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주면 안 됨

→ "대규모" + "분산 환경" 답변에서 추론
큰 시스템에서는 장애 격리가 필수

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

• 일을 복잡하게 만드는 것은 피하고, 기본적인 클라이언트-서버 통신 모델을 사용하자

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

직관적으로 보자면

• 클라이언트 측에 두기: 일반적으로 클라이언트는 처리율 제한을 안정적으로 걸 수 있는 장소 X <- 클라이언트 요청은 쉽게 위변조가 가능하고, 모든 클라이언트의 구현을 통제하기도 어려움

• 서버 측에 두기
  - 1번: 서버 측에 제한 장치 두기
  

  • 2번: API 서버에 두는 대신 처리율 제한 미드웨어를 만들어 요청 통제하기
    

  • 2번의 설계에서 처리율 제한이 동작하는 그림
    

  • 세 번째의 요청만 처리율 제한 미들웨어에 막히고, 클라이언트에서 HTTP 상태 코드 429(사용자가 너무 많은 요청을 보내려고 함)을 반환

  • 폭넓게 채택된 기술인 클라우드 마이크로서비스 => 처리율 제한 장치는 보통 API 게이트웨이라는 컴포넌트에 구현됨
    API 게이트웨이?

  • 클라우드 업체가 유지 보수(처리율 제한 SSL 종단, 사용자 인증, IP 허용 목록 관리 지원 - 완전 위탁관리형 서비스) 담당하는 서비스

  • 처리율 제한을 지원하는 미들웨어라고 기억하자

처리율 제한 장치의 위치는 설계의 중요한 부분
=> 그렇다면 어떻게 판단해야 하는가?

몇 가지 판단 지침

• 현재 사용하고 잇는 기술 스택을 점검 => 현재 사용하는 프로그래밍 언어가 서버 측 구현을 지원하기 충분할 정도로 효율이 높은지
• 사업 필요에 맞는 처리율 제한 알고리즘 찾기 => 서버에 구현하면 자유롭지만, 게이트웨이를 쓴다면 선택지가 제한됨
• 설꼐가 마이크로서비스를 기반으로 하고, API 게이트웨이를 설계에 포함시켰다면 처리율 제한 기능도 게이트웨이에 포함시켜야 할 수 있음
• 처리율 제한 서비스를 직접 만드는 건 시간이 든다 => 구현할 인력이 없다면 그냥 API 게이트웨이를 쓰는 게 답일 수 있음

처리율 제한 알고리즘

• 널리 알려진 인기 알고리즘을 설명

토큰 버킷

• 폭넓게 이용되는 알고리즘 => 간단하고, 알고리즘에 대한 세간의 이해도가 높고, 인터넷 기업들이 보편적으로 사용함

동작 원리
1. 일단 토큰 버킷이 용량이 있는 컨테이너

• 사전 설정된 양의 토큰이 주기적으로 채워지고, 토큰 버킷이 꽉 찼을 땐 토큰이 추가되지 않음
  => 용량이 4인 물컵(토큰 버킷)에 토큰 공급기(refiler)가 매초 2개의 물(토큰)을 추가하고, 물컵이 가득 차면 추가로 공급된 물(토큰)은 버려짐(overflow)

2. 각 요청은 처리될 때 하나의 토큰을 사용

• 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사하고 사용
  - 충분함 => 버킷에서 토큰을 하나 꺼내고 요청을 시스템에게 전달
  • 부족함 => 해당 요청은 버려짐(dropped)

3. 토큰을 어떻게 버킷에서 꺼내고, 토큰 공급기는 어떻게 동작하고, 처리 제한 로직은 어떻게 작동하는가?

• 그림에서 토큰 버킷 크기는 4, 토큰 공급률은 분당 4
  

토큰 버킷 알고리즘이 사용하는 두 인자

• 버킷 크기: 버킷에 담을 수 있는 토큰 최대 갯수
• 토큰 공급률: 초당 몇 개의 토큰이 버킷에 공급되는가?

버킷은 몇 개나 사용해야 하나? => 공급 제한 규칙에 따라 달라짐
사례 예시

• 통상적으로, API 엔드포인트마다 별도의 버킷을 둠
• IP 주소별로 처리율 제한을 적용해야 한다면 IP 주소마다 버킷을 하나씩 할당해야 할 것
• 시스템 처리율을 초당 10,000개 요청으로 제한하고 싶다면 => 모든 요청이 하나의 버킷을 공유하도록 할 것

장점

• 구현 쉬움
• 메모리 사용 측면 효율적
• 짧은 시간에 집중되는 트래픽 처리 가능 => 버킷에 남은 토큰이 있기만 하면 요청이 시스템에 전달될 것
  단점
• 버킷 크기, 토큰 공급률이라는 두 개의 인자를 적절하게 튜닝하기 어려움

누출 버킷

• 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정
• 보통 FIFO로 구현

동작 원리

• 요청이 도착하면 큐가 가득 차 있는지 확인 => 빈자리가 있으면 큐에 요청 추가
• 큐가 가득 차 있는 경우에 새 요청은 버림
• 지정된 시간마다 큐에서 요청을 꺼내 처리
  

누출 버킷 알고리즘이 사용하는 두 인자

• 버킷 크기: 큐 사이즈와 같은 값으로 큐에는 처리될 항목들이 보관됨
• 처리율(overflow rate): 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값으로, 보통 초 단위로 사용

장점

• 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적
• 고정된 처리율을 가져 안정적 출력이 필요한 경우 적합
  단점
• 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이고 => 그 요청들이 제때 처리되지 않으면 최신 요청들은 버려지게 됨
• 얘도 인자가 두 개라서 튜닝이 까다로움

고정 윈도 카운터

• 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도에 카운터를 붙임
• 요청이 접수될 때 이 카운터의 값은 1씩 증가
• 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려짐
• 원리 그림
  
• 문제점 그림: 윈도 경계 부근에 순간적으로 많은 트래픽이 집중되면 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있음
  

장점

• 메모리 효율 좋음
• 이해하기 쉬움
• 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합
  단점
• 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰리는 경우 => 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 됨

이동 윈도 로그

• 고정 우니도 카운터의 단점을 해결한 알고리즘

동작 원리

• 요청의 타임스탬프를 추적 -> 타임스탬프 데이터는 보통 레디스의 정렬 집합 같은 캐시에 보관함
• 새 요청이 오면 만료된 타임스탬프를 제거, 만료된 타임스탬프는 현재 윈도의 시작 시점보다 오래된 타임스탬프를 의미
• 새 요청의 타임스탬프를 로그에 추가
• 로그의 크기가 허용치보다 같거나 작을 경우 요청을 시스템에 전달, 그렇지 않을 경우 처리 거부
  

장점

• 해당 알고리즘이 구현하는 처리율 제한 메커니즘은 아주 정교함 => 어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘기지 않음
  단점
• 다량의 메모리를 사용하는데, 거부된 요청의 타임스탬프도 보관하기 때문

이동 윈도 카운터

• 고정 윈도 카운터 알고리즘 + 이동 윈도 로깅 알고리즘
• 두 가지 접근법이 있는데 하나만 설명하겠음
  

장점

• 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에 잘 대응함
• 메모리 효율 좋음
  단점
• 느슨한데 생각보다 심각한 문제는 아님

개략적인 아키텍처

• 기본 아이디어: 얼마나 많은 요청이 접수되었는지 추적할 수 있는 카운터를 추적 대상별로 두고, 이 카운터의 값이 어떤 한도를 넘어서면 한도를 넘어 도착한 요청은 거부하는 것
  => 그렇다면 이 카운터는 어디에 보관할 것인가?
• 데이터베이스: 디스크 접근 때문에 느리니까 사용 X
• 캐시: 빠르고 시간에 기반한 만료 정책을 지원해서 적합
• 레디스? 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치로, INCR과 EXPIRE 두 가지 명령어 지원
• INCR: 메모리에 저장된 카운터의 값을 1만큼 증가
• EXPIRE: 카운터에 타임아웃 값 설정 -> 설정된 시간이 지나면 카운터는 자동 삭제
• 처리율 제한 장치의 개략적 구조
  

1. 클라이언트가 처리율 제한 미들웨어에 요청을 보냄
2. 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 아닌지 검사
   • 한도에 도달했다면 요청 거부
   • 한도에 도달하지 않았다면 요청은 API 서버로 전달
   • 미들웨어는 카운터의 값을 증가시킨 후 다시 레디스에 저장

3단계 상세 설계

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되는가?
• 처리가 제한된 요청들은 어떻게 처리되는가?

처리율 제한 규칙과 처리

• 규칙 저장: 규칙은 보통 설정 파일 형태로 디스크에 저장
• 한도 초과 트래픽 처리: API는 클라이언트에게 HTTP 429 응답을 보내지만, 경우에 따라서 한도 제한에 걸린 메시지를 나중에 처리하기 위에 큐에 보관할 수 있음
• 클라이언트 통신 (HTTP 헤더):
  • X-Ratelimit-Remaining: 남은 요청 수
  • X-Ratelimit-Limit: 윈도당 허용 요청 수
  • X-Ratelimit-Retry-After: 재시도까지 대기 시간 (초 단위)
• 상세 설계 도면
  

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

• 단일 서버를 지원하는 처리율 제한 장치 구현은 어렵지 않음
• 여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 다음 문제를 해결해야 함

경쟁 조건

• 병행성이 심한 환경에서는 경쟁 조건 이슈 발생 가능
• 해결 방법
  1. 락: 시스템의 성능을 상당히 떨어뜨린다는 문제
  2. 루아 스크립트
  3. 정렬 집합 같은 레디스 자료구조

동기화 이슈

• 수백만 사용자를 지원할 때 한 대의 처리율 제한 장치 서버가 부족할 수 있음 => 이 경우 처리율 젷나 장치 서버를 여러 대 두게 될 떄 동기화가 필요해짐
• 해결 방법:
  1. 고정 세션(sticky session): 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치로 보낼 수 있게 함
  => 확장할 수 없고 유연하지 않아서 비추
  2. 레디스 같은 중앙 집중형 데이터 저장소 쓰기

성능 최적화

1. 여러 데이터센터를 지원하는 문제는 처리율 제한 장치에 중요한 문제

• 데이터센터에서 멀리 떨어진 사용자를 지원하려면 지연시간이 증가할 수밖에 없음
• 대부분의 클라우드 서비스는 세계 곳곳에 에지 서버를 심언 ㅗㅎ고 사용자의 트래픽을 가장 가까운 에지 서버로 전달해 지연시간을 줄임

2. 제한 장치 간에 데이터를 동기화할 떄 최종 일관성 모델(eventual consistency model)을 사용하는 것

모니터링

• 효과적으로 동작하고 있는지 데이터 모을 필요 있음
• 모니터링을 보는 이유

1. 채택된 처리율 제한 알고리즘이 효과적
2. 정의한 처리율 제한 규칙이 효과적

4단계 마무리