[면접 스터디] 개념정리: 4. 처리량 제한 알고리즘

『 가상 면접 사례로 배우는 대규모 시스템 설계 기초』 를 통해 시스템 설계 관련 질문을 준비해보는 스터디를 진행하기로 했다.

초기에는 간단하게 각자 책을 읽어오고 질문하기 였지만 조금 더 체계적으로 각자 정리하고

그 날 면접을 받을 사람을 랜덤으로 지정하는 방식으로 하기로 했다.
이미 1장부터 3장까지는 간략하게 했고 4장부터 시작이지만 1,2,3 역시 정리하기로 했다.

 

처리량 제한 장치

들어오는 요청의 수가 시스템이 감당할 수 있는 수준을 초과하지 않도록 제어하는 장치이다.

요청을 허용하거나 거부함으로써, 시스템 안정성 공정성 보장함

처리량을 제한하는 이유

• 시스템 보호
  • 순간적 트래픽으로 서버 과부화, 서버 다운을 방지함
• 공정한 자원 배분
  • 특정 사용자 혹은 클라이언트가 많은 요청을 보내 자원을 독점하는 걸 막음
• 비용 제어
  • 퍼블릭 클라우드를 사용 시 단기간 너무 많은 요청은 과도한 비용을 발생시키므로 제어가 필수
• 서비스 품질 유지
  • 대다수 사용자에게 일정 수준의 응답 시간과 안정성 제공할 수 있음
• DoS와 같은 공격 방어
  • 과도한 요청을 통해 서버 다운을 유도하는 방식의 공격을 막을 수 있음

처리량 제한 장치의 위치

• 클라이언트
  • 서버 부담은 없음 하지만 헤더 변조가 쉽기 때문에 신뢰성이 낮음
• 미들웨어
  • API Gateway, NGINX와 같은 프록시 서버
  • 서버에 부담이 가지 않고 분산 서비스 앞단에 효과적이다.
• 백엔드 서버
  • 비지니스 로직과 연계해 정교한 제어가 가능하다
  • 하지만 그 만큼 비지니스 로직에 사용할 자원이 사용된다.

대규모 트래픽 환경에서는 미들웨어에 Redis 기반 분산 환경이 최적이다.

 

 

 

 

처리량 제한 알고리즘

토큰 버킷

하나의 요청에 하나의 토큰을 소비하게 만들고, 버킷에 토큰이 없다면 요청이 버려지는 방식

필요 파라미터

• 버킷 크기
• 리필률(리필해줄 토큰 수, 리필 주기)

장점

• 구현 쉬움단지 여기서 요청 처리에 var = var -1 하면 끝

  if var < bucket_size
  	bucket = bucket + refill_size
  	if bucket > 10
  		bucket = bucket - (bucket % 10)
  

• 리필도 시간 기반으로 1분 마다 아래 코드 실행하면 됨
• 버킷이라고 해 봐야 그냥 변수 하나임
• 메모리 관리 쉬움
• 버킷 당 변수 몇 개라서 많아져도 큰 부담이 없음
• 짧은 시간 집중 트래픽 처리 가능사이즈가 1000이면 1000개의 요청을 1초 안에 처리가능
• 버킷 사이즈 만큼의 짧은 시간 트래픽을 감당가능

단점

• 간단한 만큼 제어할 수 있는 파라미터가 적어서 세밀한 조정이 불가능하다.

누출 버킷 알고리즘

버킷을 큐로 만든 알고리즘

요청이 들어오면 큐에 자리가 있는지 파악하고 없다면 버려짐

있으면 큐에 들어가고 고정된 처리량으로 큐가 비워짐

필요 파라미터

• 버킷 크기
• 처리율

장점

• 큐 크기 제한되어 있어 메모리 사용량이 정해져 있고, 효율적
• 고정된 처리율 → 안정적으로 동일한 출력이 필요한 경우 좋음

단점

• 단시간에 트래픽 몰리면 큐라는 특성 때문에 과거 요청들이 쌓이고 최신 요청이 버려지는 시간이 길다.
• 제어 인자가 적어 세밀 조정 불가

고정 윈도 카운터 알고리즘

고정된 타임라인 간격을 윈도로 나눔

각 윈도에 카운터를 유지

요청이 접수되고 그 요청에 맞는 윈도의 카운터가 -1

그 윈도의 임계치가 넘으면 요청 버려짐

장점

• 메모리 효율 좋음
  • 이것도 윈도 당 하나의 카운터를 유지하면 되기 때문
  • 그 전 윈도는 삭제 가능 TTL 활용 가능
  • 리필 구현 안해도 다음 타임라인에 새롭게 카운터 주면 됨
• 균등하게 들어오는 트래픽에 매우 효율적

단점

• 윈도가 바뀌는 타이밍에 요청이 몰리면 그 때는 정해둔 처리량을 넘길 수 있다.

 

이동 윈도 로깅 알고리즘

요청이 올 때마다 타임스탬프를 로그에 기록

윈도 크기 기준으로 최근 요청 로그만 유지

로그에는 지금 윈도에 관한 로그만 남은 새로운 윈도가 열리면 그 전 요청 로그는 삭제

→ 여기서 밀리초 단위로 움직이게 됨

기존 방식(고정 윈도 카운터 알고리즘)은 윈도가 바뀌면서 새로운 카운터가 만들어지는 방식이라 처리량 몰릴 수 있음

하지만 이동 윈도 로깅 방식은 카운터가 새로 만들어지는게 아닌 유지시간이 지난 로그를 점차 지워 공간을 만들어주는 방식이라 정해진 처리량을 지킬 수 있음

이전 방식이 이산적이었다면, 이 방식은 연속

장점

• 급격한 트래픽에서도 처리량을 넘는 요청을 처리하지 않는다.

단점

• 다량의 메모리를 사용한다.
• 하나의 윈도에서 거부된 요청도 로깅해야한다.

이동 윈도 카운터 알고리즘

이동 윈도 로깅의 단점인 메모리를 많이 쓰는 문제를 해결하면서 고정 윈도 카운터의 처리량 넘어서는 문제도 해결한 방식

일단 윈도는 이산적으로 사용

하지만 윈도를 2개를 보고 보간법으로 슬라이딩 하는 방식처럼 연속을 흉내

현재 얼만큼 진행 됐는지 파악

경과시간 / 전체 윈도 시간 = w

보간 계산

이전에 5개 현재 30초에 2개가 왔다고 한다면

1-w5 + w2 = 3.5

이전 까지 3.5개의 요청이 왔다고 판단하는것

여기서 올림 내림은 정해야하는거고

한 마디로 고정 윈도 카운터의 단점인 이전 것을 전혀 보지 않아 트래픽을 넘는 타이밍이 생길 수 있다는 점을

그 전 윈도를 보며 계산을 하기 때문에 경계에서 제한치를 넘는 경우를 막을 수 있다. 하지만 완전히 막지는 못한다.

완전히 막지 못하는 경우

직전 윈도 경계에서 10건이 들어옴

새 윈도 시작 후 9건이 들어옴

이런 경우는 매우 짧은 시간에 19건이 들어올 수 있음

그래서 깐깐하게 체크하려면 로깅을 사용해야함

장점

• 메모리 효율성
  • 카운터(현재 + 이전 윈도)
• 트래픽 몰릴 때 대응력 높아짐
  • 이전 윈도 카운터를 통해

단점

• 직전 시간대 요청이 균등하게 분포되었다는 가정으로 계산한 것이기에 느슨하다.

카운터 값이나 타임스탬프를 기록할 저장소가 필요

→ 레디스와 같은 인메모리 저장소가 유리

HTTP 헤더를 활용해 정보를 제공하자

• 윈도 내에 남은 처리 가능 요청 수
• 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

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

분산 처리 시 아래의 두 문제를 처리해야한다.

• 경쟁 조건
  • 카운터를 동시에 읽어와 서로 1 증가시키면 2가 아닌 1만 증가된다.
  • 해결법으로는 lock이 있다. 누가 카운터를 사용중일 때는 못 건들게 하는 것이다. 이 방식은 성능저하가 심하긴하다
  • 다른 방식으로는
    • 루아 스크립트: 여러 작업들을 원자적으로 수행 가능
    • 정렬 집합: 타임스탬프 기준으로 정렬
• 동기화
  • 여러 대의 처리율 제한 장치를 사용 시 서로 간의 동기화가 이뤄져야 한다.
  • 무상태성이기 때문에 이전 처리 관련 정보가 없는 다른 제한 장치에서는 동기화가 없다면 이전 내용을 모른다.
  • 이걸 해결하기 위해 내가 처리하던 곳에서만 처리하게 하는 스티키 세션이 있다.
  • 하지만 이건 유연하지도 않고 확장도 힘들다.
  • 이것의 해결법은 레디스와 같은 하나의 중앙 데이터 저장소를 사용해 상태를 저장하는 것이다.

더 생각해볼거

• 경성/연성 처리율 제한
• 제한을 정확히 지킬지 어느정도는 봐줄지
• 다양한 계층에서의 처리율 제한
• 처리율 제한을 회피하는 방법
  • 클라이언트에서 이걸 회피하는 방법은 없는가