가상 면접 사례로 배우는 대규모 시스템 설계 기초의 내용을 정리했습니다.
클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치
예를 들어 특정 기간 내에 전송되는 클라이언트의 HTTP 요청 횟수를 제한
- 트위터는 3시간동안 300개의 트윗을 올릴 수 있도록 제한
- 구글 독스 API는 사용자당 분당 300회의 read 요청만 허용
- DoS 공격에 의한 자원 고갈 방지
- 비용 절감
- 서버 과부하 예방
처리율 제한 장치를 서버에 둘 수도, 클라이언트에 둘 수도 있음
- 하지만 클라이언트에 위치한 경우 위/변조가 쉽게 위변조 가능하고, 모든 클라이언트를 통제하는 데 어려움이 있기 때문에 서버에 위치하는 것을 권장
서버에 위치시키더라도 API 서버에 위치시킬 것인지, 앞단의 미들웨어로 둘 것인지 고민할 수 있음
- 개별 API 서버가 관리하는 것보다는 앞단의 컴포넌트에 구현(e.g. API Gateway)하면 관리 용이
- 다만 정답은 없음. 현재 기술 스택에 따라 적절하게 선택
- 프로그래밍 언어, 캐시 등을 고려하여 현재 사용하는 언어가 서버 측 구현을 지원하기 충분한지
- 적용하는 처리율 제한 알고리즘에 따라
- monolithic service vs micro service
- 개발 공수
처리율 제한을 실현하는 알고리즘은 여러 가지이고, 각각 장단점이 있기 때문에 상황에 알맞는 적절한 알고리즘 선택
널리 알려진 알고리즘은 아래와 같음
- 토큰 버킷 (token bucket)
- 누출 버킷 (leaky bucket)
- 고정 윈도 카운터 (fixed window counter)
- 이동 윈도 로그 (sliding window log)
- 이동 윈도 카운터 (sliding window counter)
3.1. 토큰 버킷 알고리즘
토큰의 수를 이용해서 통해 요청 수를 제어
- 버킷 크기와 토큰 공급률을 통해 요청을 제한
- 버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수 = 동시에 처리할 수 있는 최대 요청 수
- 토큰 공급률: 초당 몇 개의 토큰이 버킷에 공급되는가
- 통상적으로 API 엔드포인트 별로 별도의 버킷 존재
- 사용자별로 제어하는 경우, 사용자 별로 제한하고자 하는 엔드포인트의 수만큼 버킷 생성
- 시스템의 처리율로 제어하는 경우, 모든 요청이 하나의 버킷을 공유
처리율 제한에 폭넓게 이용되고 있고, 간단한 편이라 기업들이 보편적으로 사용
- 아마존, 스트라이프가 API 요청을 스로톨링하기 위해 활용
- 토큰 버킷은 지정된 용량을 갖는 컨테이너, 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워짐
- 토큰이 가득 찬 버킷에는 더 이상 토큰이 추가되지 않음
- 버킷이 가득 차면 추가되는 토큰은 버려짐
- 각 요청은 처리될 때마다 하나의 토큰을 사용
- 요청이 오면 버킷에 토큰이 있는지 확인하고, 토큰 하나를 꺼낸 후 요청을 시스템에 전달
- 토큰이 없는 경우 해당 요청은 버림
장점:
- 구현이 쉬움
- 메모리 사용 측면에서 효율적
- 짧은 시간에 집중되는 트래픽 처리 가능
단점:
- 처리율 제한을 위해 버킷 크기와 토큰 공급률이라는 두 개의 인자를 가지고 있는데, 이 값을 적절하게 튜닝하는 것이 까다로움
토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정, 보통 FIFO 큐로 구현
- 버킷 크기와 처리율을 통해 요청을 제한
- 버킷 크기: 큐 사이즈
- 처리율: 단위 시간 별로 몇 개의 요청을 처리할지(dequeue)할지 지정하는 값, 보통 초 단위로 표현
- 쇼피파이(전자상거래 기업)에서 활용
- 요청이 도착하면 큐가 가득 찼는지 확인
- 빈 자리가 있는 경우 큐에 요청 추가
- 큐가 가득 차 있는 경우 새 요청은 버려짐
- 지정된 시간마다 큐에서 요청을 꺼내어 처리
장점:
- 큐의 크기 제한되어 있어 메모리 사용 측면에서 효율적
- 고정된 처리율을 갖고 있기 때문에 안정적 출력(stable outflow rate)이 필요한 경우 적합
단점:
- 단시간에 많은 트래픽이 몰리는 경우 큐에 오래된 요청이 적재, 해당 요청을 제때 처리 못하면 최신 요청들은 계속 버려짐
- 토큰 버킷과 마찬가지로 요청을 제어하기 위한 인자(버킷 크기, 처리율)을 적합한 값으로 튜닝하는데 어려움 존재
윈도우 별로 구간을 나눠서 구간 별 요청 수를 제한
- 타임라인을 고정된 간격의 윈도(window)로 나누고, 각 윈도마다 카운터(counter)를 붙임
- 요청이 올 때마다 카운터의 값을 1씩 증가
- 카운터의 값이 사전에 설정된 임계치(threshold)에 도달하면 새로운 요청은 새로운 윈도가 열릴 때까지 버려짐
장점:
- 메모리 효율이 좋음
- 이해하기 쉬움
- 윈도가 닫히는 시점에 카운터를 초기화하기 때문에 특정한 트래픽 패턴을 처리하기 용이
단점:
- 윈도 경계 부근에 일시적으로 많은 트래픽이 몰리는 경우, 기대했던 시스템의 처리 한도보다 더 많은 요청을 처리해야할 수 있음
고정 윈도의 경우 경계 부근에 과도한 트래픽이 몰리는 경우 제어하기 어려움
- 요청의 타임스탬프를 추적
- 타임스탬프는 redis의 sorted set에 보관
- 새 요청이 오면 만료된 타임스탬프는 제거
- 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 의미
- 새 요청의 타임스탬프를 로그에 추가
- 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달
- 큰 경우 요청은 거부됨 (로그에는 남지만 요청은 거부)
장점:
- 처리율 제한 메커니즘이 정교함, 어느 순간의 윈도라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않음
단점:
- 다량의 메모리를 사용, 거부된 요청의 타임스탬프도 보관
고정 윈도 카운터와 이동 윈도 로깅을 결합한 알고리즘
- 현재 단위 시간의 요청 수 + 직전 단위 시간의 요청수 X 이동 윈도와 직전 단위 시간이 겹치는 비율을 계산
- 위 그림에서 단위 시간이 1분, 분당 7개의 요청을 설정했다면 3(현재 1분간 요청 수) + 5(직전 1분간 요청 수) X 70%(이동 윈도와 직전 1분간 겹치는 비율) = 6.5개
- 이 값을 반올림 또는 내림해서 사용, 만약 내림하면 값은 6
- 이 값을 단위 시간동안 설정한 처리량과 비교
장점:
- 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하기 때문에 짧은 시간에 몰리는 트래픽에 대응이 유연함
- 메모리 효율이 좋음
단점:
- 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨함
- 근데 이 단점은 크게 심각하지 않음
- cloudflare에서 실시했던 40억개의 요청 가운데 시스템의 실제 상태와 맞지 않게 허용하거나 버려진 요청은 0.003%에 불과
어떤 요청이 한도 제한에 걸리면 API는 HTTP 429 코드(too many request)을 클라이언트에게 전송
- X-Ratelimit-Remaining : 윈도 내에 남은 처리 가능 요청의 수
- X-Ratelimit-Limit : 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
- X-Ratelimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림