가상 면접 사례로 배우는 대규모 시스테 설계 기초 #4 (처리율 제한 장치의 설계)

처리율 제한 장치란?

• 클라이언트 또는 서비스가 보내는 트래픽 처리율을 제어하기 위한 장치이다.
• 예를 들면 특정 기간내에 전송되는 클라이언트의 요청 횟수를 제한한다.
• 추가로 도달한 모든 호출은 block 된다.

처리율 제한 장치의 장점

• dos공격에 의한 자원 고갈을 방지할 수 있다.
• 비용을 절감할 수 있다.
  • 추가 요청 처리를 위한 서버를 많이 두지 않아도 되기 때문에.
  • api 사용에 대한 과금이 횟수 기반이라면 그 회수를 제한할 수 있어야 비용을 절감할 수 있을 것이기 때문에.
• 서버 과부화를 막는다. 봇이나 잘못된 패턴으로 유발된 트래픽을 걸러낼 수 있기 때문이다.

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

• 어떤 종류의 처리율 제한 장치가 필요? (서버 또는 클라이언트?)
  • 서버
• 어떤 기준으로 api 호출을 제한? ( ip, 사용자 id 등)
  • 다양한 형태의 제어 규칙을 포함할 수 있는 유연한 형태
• 시스템 규모는?
• 분산환경에서 동작해야 하나?
• 독립적인 서비스 인가? 아니면 어플리케이션 코드에 포함 될 수 있나?
• 사용자 요청이 제한 장치에 의해 걸러질 경우 알려야 하나?

위에 질문으로 정리된 요구사항

• 처리율을 초과하는 요청은 정확하게 제한
• 낮은 응답시간 즉 http응답시간에 나쁜 영향을 주지 말아야 한다
• 가능한 적은 메모리 사용
• 분산형 처리율 제한 장치여야 한다. 즉 하나의 장치를 여러 서버나 프로세스가 공유할 수 있어야 한다.
• 요청이 제한될시에 사용자에게 분명하게 보여주어야 한다
• 높은 fault tolerance를 가져야 한다. 즉 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주지 말아야 한다.

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

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

• 클라언트?
  • 처리율 제한을 안정적으로 걸 수 없다. 모든 클라이언트의 구현을 통제하는 것도 어려울 수 있다.
• 서버?
  • api 서버에 포함시키는 방법과 middleware를 만들어 middleware로 하여금 api 서버로 요청을 통제하는 방법이 있다.
  • 두개 중 어떤게 좋은지에 대한 답은 없다 하지만 아래의 몇 가지 지침을 고려해 볼 수는 있다.
    • 현재 사용하는 프로그래밍 언어가 서버 측 구현을 지원하기 충분히 효율적인가?
    • 적절한 처리율 제한 알고리즘 찾아라 만약 서버측에서 모두 구현한다면 자유롭게 선택 가능 하지만 제3 사업자가 제공하는 게이트웨이를 사용한다면 제한될 수 있다.
    • 이미 서비스가 마이크로 서비스에 기반하고 사용자 인증, ip 허용목록 관리 등을 처리하기 위해 api 게이트웨이가 설계에 포함된다면 처리율 제한 기능 또한 포함 시킬 수 있다.
    • 직접 구현 하기에 충분한 인력이 없다면 상용 api 게이트 웨이를 쓰는게 바람직하다.

처리율 제한 알고리즘

• 토큰 버킷
• 누출 버킷
• 고정 원도 카운터
• 이동 윈도 로그
• 이동 윈도 카운터

계락적인 아키텍처

• 처리율 제한 알고리즘은 기본적으로 추적 대상별(ip, api엔드포인트, 사용자별)로 추적할 수 있는 카운터를 두고 카운터 값이 한도를 넘어서면 한도를 넘어서 도착한 요청은 거부하는 것이다.
• 카운터는 어디에 보관해야 할까? 카운터는 빠르고 시간에 기반한 만료정책을 지원하는 메모리 캐시가 적당하다. (레디스가 보편적이다)

3단계 상세 설계

처리율 제한 규칙은 어떻게 만들고 어디에 저장?

• 보통 설정 파일 형태로 디스크에 저장한다.
• 예시로 처리율 제한 규칙은 디스크에 보관하고 작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐싱하도록 한다.

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

• 요청 한도 제한이 거리면 429응답을 클라이언트에 보낸다. 그리고 한도 제한에 걸린 요청은 2가지 방법으로 처리할 수 있다.
  • 버림
  • 큐에 보관하여 나중에 처리
• 다음과 같은 http헤더를 추가적으로 반환할 수 있다.
  • X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청 수
  • X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수.
  • X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

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

다음 두가지 문제를 해결해야 한다.

경쟁 조건

레디스는 싱글 스레드에 동시성을 보장한다. 그래서 여러 요청이 counter에 값을 읽어 처리한다면 문제가 생길 수 있다. 예) 두개 요청이 counter를 읽는다. 그리고 counter +1 을 한다. counter읽는 작업과 counter+1을 하는 작업의 순서가 뒤섞일 수 있다. 하지만 정확한 처리를 위해서는 각 요청마다 counter를 읽는 작업과 +1하는 작업이 순서대로 이루어 져야 한다.

• 해결방법
  • lock
    가장 널리 알려진 해결책 이지만 시스템 성능을 상당히 떨어뜨린다. 왜일까 단순히 lock을 대기하게 하기 때문에?
  • lua 스크립트
    atomic을 보장하는 스크립트를 루아로 작성하여 실행시킨다.
  • 정렬 집합
  • transaction?
    여러개의 명령어를 큐에 집어 넣은다음에 한번에 실행 하는 방법.

동기화 이슈

처리율 제한 장치 서버가 여러개가 되면 동기화가 필요해진다.

• 해결방법
  • sticky session을 활용하여 같은 클라이언트는 항상 같은 처리율 제한 장치가 처리하도록 한다. 하지만 이방법은 유연하지 않고 확장 하기도 어렵다.
  • 중앙 집중형 데이터 저장소를 활용해 모든 데이터를 한곳에서 관리 한다.

성능 최적화

• 데이터 센터에서 멀리 떨어진 사용자를 지원하면 latency가 증가하기 때문에 세계 곳곳에 엣지 서버를 심어놓는다.
• 분산된 제한 장치간에 데이터를 동기화할 때 최종성 일관성 모델을 사용한다.

모니터링

• 채택된 처리율 제한 알고리즘이 효과적인가? 특정 트래픽 급증 이벤트시에는 비효율적으로 작동한다면 다른 알고리즘을 고려해야한다.
• 처리율 제한 규칙은 효과적인가? 너무 많은 유효 요청이 버려지고 있다면 규칙완화가 필요하다.

4단계 마무리

추가적으로 언급해보면 좋은 토픽

경성 또는 연성 처리율 제한

• 경성 처리율 제한은 요청 개수는 임계치를 절대 넘을 수 없다.
• 연성 처리율 제한은 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.

다양한 계층에서의 처리율 제한

• application계층이 아닌 iptables를 사용하여 네트워크 계층에서 처리율 제한을 적용할 수 있다.

처리율 제한을 회피하는 방법. 클라이언트는 어떻게 설계하는 것이 최선인가?

• 클라이언트 측 캐시를 사용하여 api 호출 횟수를 줄인다.
• 처리율 제한 장치의 임계치에 맞게 짧은 시간동안 너무 많은 메시지를 보내지 않는다.
• 에러처리 코드를 도입하여 복구될수 있도록 한다.
• 재시도 로직 구현시 충분한 back-off시간을 둔다.

질문

중앙저장소가 항상 좋은 것일까?

해당 링크에 따르면 분산 인메모리 구조도 장점이 있다.

중앙 저장소 장점

• 요청을 분산할 필요없다.
• 처리율 한도를 최대한 사용할 수 있다.

중앙 저장소 단점

• 중앙 저장소 요청 때문에 지연시간 증가(네트워크 왕복)
• 확장하기 어렵다?? (한 처리율 제한 장치가 많은 요청을 보내기위해 redis를 쓰게된다면 나머지 처리율 제한장치에 요청은 밀리면서 병목이 일어나기 때문?)
• 단일 장애 지점 발생 (만약 장애시 failover 프로세스가 완료될때가지 api를 차단하는건 좋은 선택이 아님)

분산 인메모리 장점

• 높은 처리량을 제공할 수 있다.(병목이 일어나지 않기 때문?)
• 지연시간이 증가하지 않는다.(네트워크 통신이 필요없음으로)

분산 메모리 단점

• 트래픽이 균등하게 분산되지 않으면 처리 한도를 최대한 활용하지 못한다.
• 시스템 시계 동기화 필요 ?? 중앙일시에 필요없나?
• 여러 처리율 제한장치를 관리 하기 위해 추가 설정 시스템이 필요하다. ( 처리율 제한 장치 인스턴스마다 비율한도를 설정해지고 관리하고 업데이트 할 수있도록)

client처리율 제한 장치?

• 언제 사용할까? api 사용시 요금 과금을 막기 위해?
• 요금 과금이 없으시 만약 서버쪽에도 있다면 의미가 있나? 굳이 양쪽에 구현해서 얻는 장점은?
• 왜 쉽게 위변조 가능할까? 왜 안정적으로 걸 수 있는 장소가 안될까?

계락적인 아키텍처의 레디스 사용법이 모든 처리율 제한 알고리즘을 구현 가능할 걸까?

lock이 성능에 문제가 생기는 이유?

• lock이 걸린동안 다른 처리율 제한기는 대기 해야함으로?
• 스핀 락에 한정된 애기인가?
  링크

정렬 집합이 어떻게 해결해주나?

• 이동 윈도우 알고리즘 사용시 정렬집합을 사용하면 여러 요청이 동시 다발적을 들어오는 상황에서 동시성 문제없이 counter를 늘릴수 있다.
  1. limit을 두는 기준별로 (ip, userId 등) sorted set을 만든다. 예) key - ip value-현재 시각 score-현재 시각 ttl rate-limiting interval
  2. ZREMRANGEBYSCORE 명령어로 이전 interval의 모든 요청을 지운다.예) 현재 시각이1:01:40 이면 1:00:40 이전의 요청들은 다 지운다.
  3. ZADD로 현재 요청의 시각을 추가한다. 예) 현재 시각이1:01:40, 기준 아이피, 분당 10회 key - ip value-1:01:40 score-1:01:40 ttl-60
  4. 특정 기준에 해당하는 쌓인 요청의 갯수를 확인하여 limit 을 넘는지 확인 / 쌓인 요청중 가장 최신 요청의 값과 현재 시각을 비교해서 너무 크면 요청을 전달하지 않는다 (무슨의미지?)
     링크
     만약 삭제후 현재 요청을 기록할때까지 지연이 생긴다면 그래도 Limit가 제대로 작동할까? ttl이 있으니까 괜찮을까?
     예) 1분당 20회인데 1:02분 요청이 도착 -> 1:01분 요청 다지움 -> 1:02분 요청 기록하려고 했더니 1:03분이 되어도 괜찮나?

분산된 제한 장치간에 데이터를 동기화에 필요한 데이터란?

• 처리 규칙? 처리값 보관하는 레디스도 동기화 필요?
• 왜 eventual concsitency model이 적절한가?
• 그럼 실시간 데이터느 어떻게 동기화?