대규모 시스템 설계 기초 책 정리하기 : 4-2 처리율 제한 장치의 설계

읽을때 마다 새로운 지식을 알게되는 책이지만, 다음 챕터로 넘어 갈수록 너무 어려워져서 손이가지 않는 책으로 최대한 많이 이해하고 완독을 목표로 정리를 하기위해서 글을 작성하게 되었다.

처음에는 2부 부터 읽다가 왜 1을 읽지 않느냐는 질문을 받고 1부를 읽게되었고 1부 부터 읽는게 필수라고 할정도로 난이도 차이가 있다.

잘근잘근 씹어먹듯, 많은 지식을 남길 수 있도록 열심히 정리해보자!
가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 예스24

처리율 제한 알고리즘

지난 글에 이어서 처리율 제한 3번째 알고리즘부터 정리하고자 한다.
이전 알고리즘과 처리율 제한이 궁금하면 이전 글을 참고하길 바란다.

3. 고정 윈도 카운터 알고리즘

해당 알고리즘은 다음과 같이 동작한다.
1. 타임라인을 고정된 간격의 윈도우로 나누고, 각 윈도우 마다 카운터를 붙인다.
2. 요청이 접수될 때마다 이 카운터의 값은 1씩 증가한다.
3. 이 카운터의 값이 설정된 임계치에 도달하면 새로운 요청은 윈도가 열릴때까지 버려진다.

장점

• 효율성에서도 좋고 이해하기도 쉽다.
• 특정 트래픽에맞게 패턴을 만들어 처리학에도 좋다.

단점

• 경계 부근에 일시적으로 많은 트래픽이 생겼을때, 기대했던 시스템의 처리량보다 더 많은 양의 요청을 처리하게 되는 큰 단점이 존재한다.

가령 1분에 5개를 처리하기를 원했던 시스템이 있는데, 특정 시간(경계 부분)에 트래픽이 몰려 1분동안 10개의 요청이 처리되게 되어야하는 문제점이 생긴다.

4. 이동 윈도 로깅 알고리즘

3번의 고정 윈도 카운터 알고리즘을 해결한 알고리즘이다. 해당 알고리즘에서는 요청의 타임스템프를 로깅하는 방식으로 추적하여 처리된다.

1. 새요청이 오면 만료된 (오래된) 타임스템프는 제거된다. (제한 기간이 지난 요청)
2. 새요청의 타임스템프 로그를 추가한다.
3. 로그 크기가 허용치보다 같거나 작으면 요청처리 적으면 요청을 거부한다.

+) 새요청이 허용되거나, 거부되었을때 모두 요청에 대한 타임스템프 로그를 추가한다.

 장점
1. 정교하게 설계되어 요청의 처리율 한도는 시스템의 한도를 넘지 않는다.

단점
2. 실패한 메모리도 저장하기때문에 메모리를 많이 사용한다는 단점이 존재한다.

5. 이동 윈도 카운터 알고리즘

해당 알고리즘은 고정 윈도 카운터 알고리즘 + 이동 윈도 로그 알고리즘을 합쳐서 생성한 알고리즘이다.

처리되는 방식은 다음과 같다.
한도와 처리되는 방식은 고정 윈도 카운터와 동일하나, 해당 요청이 진입되는 시점에 이전 타임의 비율로 요청 처리수량을 계산해서 해당 요청의 처리유무를 분석한다.

가령 한도가 분당 7개의 요청인 시스템이 있다고 하자.
직전 1분의 요청수가 7개고, 현재 구간의 이전 요청이 3개가 있다면,
1분의 30% 시점의 요청은 처리가 가능한지 분석이 필요하다.

현재 구간(1분x30%)에 들어온 요청수 + 직전 1분의 요청수 x 아동 윈도와 직전 1분이 겹치는 비율 (70%)

$3+7*(0.7) = 6.5$

해당 시스템에서는 내림을 기준으로 데이터를 처리한다고 가정했을때, 처리된 요청은 6으로 적용되고, 해당 새로운 요청은 처리가 가능한 상태가 될 것이다.

그 이후에 바로 들어온 요청은 처리량을 넘었으니 처리되지 않고 요청은 제외될 것이고, 비율이 줄어들면서 처리가능한 수량이 다시 늘어날 것이다.

해당 알고리즘의 장/단점은 다음과 같다.
장점
1. 이전시간대의 평균 처리도 잘해서 단기간 몰리는 트래픽 처리도 잘할 수 있다.
2. 메모리 효율도 꽤 좋다.

단점
1. 직전 시간대의 도착한 요청이 균등 분포 되어있다고 가정하고 추정치를 계산하므로 다소 느슨한 계산이 될 수 있다는 단점이 있다.

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

두가지 방법이 있을 수 있는데,

• API 는 429 응답을 전달하고 해당 요청을 거부처리하는 방법이다.
• 동일하게 API는 429 응답을 전달하되, 나중에 처리하게 위해 요청을 큐에저장 하는 방법이 존재한다.
  또한 각각 응답 헤더에는 처리율 한도처리 정보를 포함하여 전달한다.

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

하나의 환경에서는 문제가 되지 않았지만, 분산환경으로 해당 서비스가 분리가되면 처리해야할 문제가 생긴다.

각각 경쟁조건, 동기화 문제인데 다음과 같다.

경쟁 조건

우선 한마디로 정리해 보면 경쟁조건에서는, 처리 과정이 끝나지 않았는데 새로운 동작이 진행되어, 처리 데이터가 잘 못 설정되는 부분이다.

처리율 제한장치는 다음과 같이 동작한다.
1. 레디스에서 카운터의 값을 읽는다.
2. 카운터 + 1 = 임계치의 값이 넘는지 확인한다.
3. 넘지 않는다면, 레디스에 저장된 값을 1만큼 증가시키고 요청을 처리하한다.

다만, 병행성이 심환 환경에서는 아래와 같은 문제가 발생한다.
아래 이미지를 보면 요청 2가 끝나는 시점에서는 카운터가 5가 되어야하지만, 4로 남아 있는것을 확인할 수 있다.

이를 해결하기 위한 방법은

• lock 을 걸 수 있다. 다만 시스템의 성능이 매우 떨어지는 문제가 있다.

해당 방법 대신 쓸수 있는 방법도 있는데

• 루아 스크립트, 레디스 자료구조의 정렬 집합을 사용하면 해당 문제를 해결할 수 있다.
  (추후 정리 예정)

동기화 이슈

사용자 client 에 따른 제한이나 IP 와 같은 제한이 필요할때,
각 장치별로 정보를 공유하지않으면 처리율 제한이 잘 동작하지 않을 수 있다.

이를 해결하기 위한 방법은 다음과 같다.

1. 고정 세션을 이용한다.

• 클라이언트로 부터의 요청은 항상 같은 제한장치가 처리하도록 작업
• 다만 해당 방법은 확장성도 떨어지고, 유연하지 않는 문제가 발생한다.

2. 레디스와 같은 중앙집중형 데이터 저장소 사용

• 데이터 집합이 늘어나지만, 클라이언트 정보를 저장해 공유하는 방법으로 쉽게 동기화를 적용할 수 있다.

시스템 모니터링과 마무리

적용한 처리율 제한장치가 잘 동작하는지 확인하기 위해 데이터 확인과 필 수이다.

우선, 너무 빡빡하게 설정해 두어 버려지는 데이터가 많이 존재하는지 확인이 필요하다.
그렇다면 설정 값을 수정하여 데이터를 잘 처리할 수 있도록 조정이 필요하다.

트래픽이 급증할 때, 처리방법이 효율적인지 확인이 필요하다. 해당 부분이 문제가 된다면 처리하는 방법이 더 효율적이고 알맞는 알고리즘을 적용해야 될 수 있다.

마지막으로 고민해야 할 부분

1. 경성 / 연성 처리울 제한 설정

• 임계치를 넘어서 처리가 되었을때의 제한 조건이 세밀한지 여부를 확인해야한다.

1. 다양한 계층에서의 제한방법 처리

• 이번에 정리한 애플리케이션 계층의 제한 방법 이외에 다른 계층에서도 처리가 가능하니, 필요에 따라서 해당 방법도 고민해서 적용

1. 처리율 제한을 회파하는 방법은?

• 어떤 방법이. 최선인지 고민하고 확인해야 한다. 처리율 제한을 회피하는 클라이언트 단에서의 방법이 있을 수 있다. 필요에 따라 적용방식을 다르게 적용이 필요하다.