[대규모 시스템 설계 기초] 4장 처리율 제한 장치의 설계

네트워크 시스템에서 처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치 입니다.

API 요청 횟수가 제한 장치에 정의된 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단이 됩니다.

이는 Dos를 통한 자원 고갈을 방지 하기 위해서 입니다.

 

이러한 처리율 제한 장치를 클라이언트에 둔다면, 쉽게 위조변조가 가능해서 통제하는 것이 어렵습니다.

그리하여 다른 방법이 존재하는데 

 

처리율 제한 장치를 API 서버에 두는 대신, 처리율 제한 미들웨어를 만들어 해당 미들웨어로 하여금 API 서버로 가는 요청을 통제하는 방식입니다.

 

 

 

이러한 처리율 제한 장치의 알고리즘은 여러개가 존재하는데 해당 알고리즘들에 대해서 알아보겠습니다.

 

1. 토큰 버킷 (버킷에 담겨져 있는 토큰의 갯수 만큼 처리)
2. 누출 버킷 (버킷, 큐를 사용하여 요청을 처리)
3. 고정 윈도 카운터
4. 이동 윈도 로그
5. 이동 윈도 카운터

 

토큰 버킷 알고리즘

토큰 버킷 알고리즘은 처리율 제한에 폭넓게 이용되고 있습니다.

알고리즘에 대한 세간의 이해도도 높은 편이며 인터넷 기업들이 보편적으로 사용하고 있다.

아마존, 스트라이프 api 통제 하기 위해 해당 알고리즘을 사용합니다.

이런 형식으로 토큰에 정해둔 갯수가 채워진 상태에서 요청이 들어오면 버킷에서 토큰 하나을 꺼내어 해당 요청을 시스템에 전달 합니다.

충분한 토큰이 없는 경우, 해당 요청들은 버려지게 됩니다.

 

버킷은 몇 개나 사용해야 되나면 API 엔드 포인트마다 별도의 버킷을 두는 것 입니다.

만약 시스템의 처리율을 초당 10,000개로 제한하고 싶다면, 모든 요청이 하나의 버킷을 공유하도록 해야 될 것입니다.

 

장점으로는 구현하기 쉽고, 짧은 시간에도 집중되는 트래픽도 처리할 수 있습니다.

단점으로는 이 알고리즘은 버킷 크기와 토큰 공급률이라는 두 개의 인자를 적절하게 튜닝하는 것이 까다롭습니다.

 

누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만, 요청 처리율이 고정되어 있다는 점이 다릅니다. 누출 버킷 알고리즘은 보통은 FIFO 큐로 구현되어 있습니다.

요청이 도착하면 큐가 가득 차 있는지 봅니다. 빈자리가 있는 경우에는 큐에 요청을 추가 합니다.

 

여기서 처리율은 큐에서 처리 되는 곳을 이야기 합니다.

 

버킷 크기 - 큐 사이즈와 같은 값입니다. 큐에는 처리될 항목들이 보관합니다.

장점으로는 큐의 크기가 제한되어 있어, 메모리 사용량 측면에서 효율적입니다.

고정된 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우가 적합 합니다.

단점으로는 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고, 그 요청들을 제때 처리 못하면 최신 요청들은 버려진다. 이 알고리즘도 적절하게 튜닝하기 어렵습니다.

 

고정 윈도 카운터 알고리즘

타임라인을 고정된 간격의 윈도우로 나누고, 각 윈도우 마다 카운터를 붙이게 됩니다.

요청이 접수 될때 마다 카운터+1

카운터 값이 임계치에 도달하면 새로운 요청은 새 윈도우가 열릴 때 까지 버려지게 됩니다.

 

이렇게 윈도우를 3개로 설정을 해두면 3개 이후에 새로운 윈도우가 생길 때 까지 나머지는 버려지게 됩니다.

 

이 알고리즘의 문제점은 그 사이에 순간적으로 많은 트래픽이 집중될 경우, 윈도우에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것 입니다.

장점으로는 메모리 효율이 좋고, 이해하기 쉽습니다. 윈도우가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합합니다.

 

이동 윈도우 로깅 알고리즘

고정 윈도우는 앞선 문제들이 있었고, 윈도우 경계 부근에 트래픽이 집중이되는 경우 시스템에 설정된 한도보다 많은 요청을 처리하게 된다는 것 이다. 이동 윈도우 로깅 알고리즘은 이 문제를 해결합니다.

 

이 알고리즘은 타임스탬프를 추적합니다. 타임스탬프 데이터는 레디스의 정렬 집합 같은 캐시에 보관하게 됩니다.

새 요청이 오면 만료된 타임스탬프는 제거하고, 만료된 타임스탬프는 그 값이 현재 윈도우의 시작 시점보다 오래된 타임스탬프를 말합니다.

새 요청의 타임스탬프를 로그에 추가한다.

로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달하게 됩니다. 그렇지 않은 경우에는 처리를 거부한다.

 

장점으로는 처리율 제한 매커니즘은 아주 정교하다, 어느 순간의 윈도우를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않습니다.

단점으로는 이 알고리즘은 다량의 메모리를 사용하는데, 거부된 요청의 타임스탬프도 보관하기 때문입니다.

 

이동 윈도우 카운터 알고리즘

이동 윈도우 카운터 알고리즘은 고정 + 이동 결합

 

처리율 제한 장치의 한도가 분강 7개로 설정 이전 1분 동안 5개의 요청이 그리고 현재 1분동안 3개의 요청이 왔다고 가정

현재 1분의 30% 시점에도 도착한 새 요청의 경우 현재 윈도우에 몇 개의 요청이 온것으로 보고 처리를 해야 하나?

 

현재 1분간의 요청수 + 직전 1분간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율이다.

6.5개 여기서 이건 올릴수도 내릴수도 있고, 여기서는 내려서 계산한다.

 

그래서 현재 1분의 30% 시점에 도착한 신규 오청은 시스템으로 전달 될것이고 그 직후에는 한도에 도달하였으므로 더 이상의 요청은 받지 못할 것이다. ← 7개가 제한 계산 결과 저기까지가6개

장점 - 이전 시간대의 평균 처리율에 따라 현재 윈도우의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응 한다.

메모리 효율이 좋다.

단점 - 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다. 하지만 이 문제는 생각한 만큼 심각하지는 않다.

 

이렇게 이러한 카운터를 이용해 처리하는 과정을 살펴 보았다.

이 카운터를 어떻게 관리하는지에 대해 알아본다.

여기서는 레디스의 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치로서 INCR,EXPIRE의 두 가지 명령어를 지원한다.

INCR : 메모리에 저장된 카운터의 값을 1만큼 증가

EXPIRE : 카운터에 타임아웃 값을 설정한다. 설정된 시간이 지나면 카운터는 자동 삭제

클라이언트 요청이 오면 미들웨어에서 지정된 버킷에서 카운터를 가져와 한계에 도달했는지 확인

1. 확인 결과 아직 괜찮다면 카운터 값을 하나 증가 시키고 해당 요청을 서버에게 전달
2. 한계에 도달 했을 경우 요청 거부

 

대략적인 시스템 설계 구조이다.

 

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

매번 분산환경에서 동기화 문제가 발생한다 스레드에 인하여 내가 보고 있는 것이 다른 한쪽에서도 동일하게 보고 있거나, 처리하는 과정이라 아직 연산 결과가 적용되지 않는 문제이다.

여기서 분산 환경을 시스템을 확장하기 위해서는

• 경쟁 조건
• 동기화

라는 문제들을 해결해야 된다.

동기화 문제를 해결하기 위해선 락을 통해 해결하지만 대신 시스템의 성능을 상당히 떨어트리는 다는 문제가 있다.

락 대신 → 루아 스크립트, 정렬 집합(레디스의 자료구조)

중앙 집중형 데이터 저장소를 쓰는 구조

 

 

결과

내가 만든 자바 백엔드 코드에 여기서 나온 버킷 알고리즘을 적용한 경험이 있다.

RAG 서비스를 이용할 때 백엔드 세션을 통해서 한 세션 당 5번의 요청 횟수를 제한하여 서비스를 하였다.

 

package Club.Trace.ClubTraceApp.infrastructure.config;

import io.github.bucket4j.*;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import java.time.Duration;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

@Configuration
public class BucketConfig {

    private final Map<String, Bucket> buckets = new ConcurrentHashMap<>();




    private BucketConfiguration createBucketConfiguration() {
        Refill refill = Refill.intervally(3, Duration.ofSeconds(60));
        Bandwidth limit = Bandwidth.classic(3, refill);
        return BucketConfiguration.builder().addLimit(limit).build();
    }


    public Bucket resolveBucket(String sessionId) {
        return buckets.computeIfAbsent(sessionId, id ->
                Bucket.builder()
                        .addLimit(createBucketConfiguration().getBandwidths()[0])
                        .build()
        );

    }
    // 요청 하나 소모
    public boolean tryConsume(String sessionId) {
        return resolveBucket(sessionId).tryConsume(1);
    }
}

if (!bucketConfig.tryConsume(sessionId)) {
            CompletableFuture<String> failedFuture = new CompletableFuture<>();
            failedFuture.completeExceptionally(
                    new RuntimeException(ErrorCode.FORBIDDEN_RATE_LIMIT.getMessage())
            );

        }