[API] Rate Limiting & Resource ID 난독화

API 요청량 제한 관련 정보 - 출처 블로그.

https://www.mimul.com/blog/about-rate-limit-algorithm/

https://github.com/appkr/l5essential/blob/master/lessons/49-rate-limit.md

 

---

rate limiting과 rate shaping은 대표적인 혼잡 제어 기법이다. rate limiting은 policing(보안 정책)이라고도 하는데, 말그대로 traffic rate을 제한 하는 것이다. traffic rate를 제한하는 이유는 여러가지가 있을 수 있는데, 근본적인 이유는 과도한 트래픽이 네트웍 장비 안으로 들어오게 되면 시스템 전체의 성능을 떨어뜨리게 되며 심한 경우는 시스템을 정지시키게도 된다. 

 

반면에 traffic shaping은 traffic을 특정 모양, 즉 특정 대역폭으로 만들어 주는 것이다. 이를 위해서는 트래픽을 메모리에 저장해 두었다가 목표로하는 대역폭(traffic rate)으로 패킷/데이터를 내보내주면 된다. (Leaky Bucket 알고리즘을 사용하면 구현 가능하다.)

 

rate limiting은 네트워크 장비의 입력포트에서 구현이 되며, rate shaping은 네트워크 장비의 출력 포트 쪽에서 구현이 된다. 

---

1. API Rate Limit

API 엔드포인트의 사용량을 제한하는 이유는 여러가지 이다.

   - DDoS 공격으로 부터 서비스를 보호한다.

   - API 클라이언트 간에 API Resource의 사용에 공평성을 제공한다. 가령, 소수의 Heavy 클라이언트로 인해 다른 선량한 클라이언트가 피해를 입지 않도록 말이다.

   - API를 통해 받는 데이터 자체가 돈과 직결되는 경우, 그 비즈니스 모델로서의 역할을 한다.

 

테스트를 위해 1분에 3번 요청을 허용하도록 설정했다고 가정하다. 4번째 요청에서는 클라이언트는 아래와 같은 응답을 받고, 1분 후에 다시 사용 가능한 상태가 되는 것을 확인할 수 있다.

HTTP/1.1 429 Too Many Requests
Host: api.myprofject.dev:8000
# ...
Retry-After: 60
X-RateLimit-Limit: 3
X-RateLimit-Remaining: 0

상용에서는 서비스를 하면서 여러가지 통계 정보들에 기반하여 클라이언트 당 허용할 적절한 Rate Limit 값을 정해야 한다.

---

서비스를 운영하다보면 서비스의 가용성(API레벨, 네트워크 레벨, 컨테이너 레벨, CPU 레벨이든)을 유지하기 위해서 클라이언트의 과도한 사용에 대해 스스로를 보호해야 한다. 간과하기 쉽지만, 서비스의 가용성을 유지하기 위한 노력은 클라이언트에도 같이 설계를 해주는 것이 바람직하다. 서비스를 보호해주는 수단으로 Rate Limit 알고리즘을 적용하는데, 이를 효과적으로 적용하기 위해서는 알고리즘에 대한 이해도를 높일 필요가 있고, 서비스의 트래픽 특성도 파악해둘 필요가 있다. 여기에서는 Rate Limit 알고리즘을 정리하는 것을 목표로하고 간단한 알고리즘을 구현함으로써 이해도를 높일 수도 있다.

 

왜 Rate Limit 알고리즘이 필요할까?

  - 과도한 트래픽으로부터 서비스를 보호

  - Resource 사용에 대한 공정성과 합리성 유도.

  - 트래픽 비용이 서비스 예산을 넘는 것을 방지.

  - Rate에 대해 과금을 부과하는 Business Model로 활용.

 

Rate Limit 알고리즘 종류

알고리즘의 종류를 이해하고, 서비스의 트래픽 패턴도 파악하여, 서비스 가용성에 문제가 되기전에 적절한 알고리즘을 선택해서 트래픽 제어를 할 필요가 있다. 기본 window 단위는 초기반이다.

 

1) Leaky Bucket

네트워크로의 데이터 주입 속도의 상한을 정해 제어하고 네트워크에서 트래픽 체증을 일정하게 유지한다. 일정한 유출 속도(유출 속도는 고정된 값)를 제한하여 버스트 유입 속도를 부드럽게 한다.

   - 고정 용량의 버킷에 다양한 유량의 물이 들어오면 버킷에 담기고 그 담긴물은 일정량 비율로 떨어진다.

   - 들어오는 물의 양이 많아 버킷의 용량을 초과하게 되면 그 물은 버린다.

   - 입력 속도가 출력 속도보다 크면 버킷에서 누적이 발생하고 누적이 버킷 용량보다 큰 경우 오버플로가 발생하여 데이터 패킷 손실이 발생할 수 있다.

public class LeakyBucket extends RateLimiter {
    private final long capacity;
    private long used;
    private final long leakInterval;
    private long lastLeakTime;
    
    protected LeakyBucket(int maxRequestPerSec) {
        super(maxRequestPerSec);
        this.capacity = maxRequestPerSec;
        this.used = 0;
        this.leakInterval = 1000 / maxRequestPerSec;
        this.lastLeakTime = System.currentTimeMillis();
    }
    
    @Override
    boolean allow() {
        leak();
        synchronized (this) {
            this.used++;
            if (this.used >= this.capacity) {
                return false;
            }
            return true;
        }
    }
    private void leak() {
        final long now = System.currentTimeMillis();
        if (now > this.lastLeakTime) {
            long millisSinceLastLeak = now - this.lastLeakTime;
            long leaks = millisSinceLastLeak / this.leakInterval;
            if (leaks > 0) {
                if (this.used <= leaks) {
                    this.used = 0;
                } else {
                    this.used -= (int) leaks;
                }
                this.lastLeakTime = now;
            }
        }
    }
}

채용 플랫폼: Amazon MWS, NGINX, Uber-go rate limiter, Shopify, Guava RateLimiter

 

2) Token Bucket

일시적으로 많은 트래픽이 와도 토큰이 있다면 처리가 가능하면서 토큰 손실 처리를 통해 평균 처리 속도를 제한할 수 있다. 즉, 평균 유입 속도를 제한하고 처리 패킷 손실없이 특정 수준의 버스트 요청을 허용할 수 있다.

  - 토큰은 정해진 비율로 토큰 버킷에 넣는다.

  - 버킷은 최대 n개의 토큰을 저장하며, 버킷이 가득차면 새로 추가된 토큰은 삭제되거나 거부된다.

  - 토큰 버킷은 토큰이 배치되는 속도를 기반으로 액세스 속도를 제어한다.

  - 전송 횟수를 누적할 수 있으며, 버킷이 가득차면 패킷 손실 없이 토큰이 손실된다.

public class TokenBucket extends RateLimiter {
    private int tokens;
    private int capacity;
    private long lastRefillTime;
    
    public TokenBucket(int maxRequestPerSec) {
        super(maxRequestPerSec);
        this.tokens = maxRequestPerSec;
        this.capacity = maxRequestPerSec;
        this.lastRefillTime = scaledTime();
    }
    
    @Override
    public boolean allow() {
        synchronized (this) {
            refillTokens();
            if (this.tokens == 0) {
                return false;
            }
            this.tokens--;
            return true;
        }
    }
    
    private void refillTokens() {
        final long now = scaledTime();
        if (now > this.lastRefillTime) {
            final double elapsedTime = (now - this.lastRefillTime);
            int refill = (int) (elapsedTime * this.maxRequestPerSec);
            this.tokens = Math.min(this.tokens + refill, this.capacity);
            this.lastRefillTime = now;
        }
    }
    
    private long scaledTime() {
        return System.currentTimeMillis() / 1000;
    }
}

채용 플랫폼 - AWS(API Gateway, EC2, EBS, CPU Credit), Spring Cloud Netflix Zuul, Bucket4j

 

3) Fixed Window Counter

정해진 시간 단위로 window가 만들어지고 요청 건수가 기록되어 해당 window의 요청 건수가 정해진 건수보다 크면 해당 요청은 처리가 거부된다. 이 알고리즘을 사용하면 경계의 시간대(12:59, 13:01초에 몰리면)에 요청이 오면 두배의 부하를 받게 된다. 즉, 구현은 쉽지만, 기간 경계의 트래픽 편향문제가 발생된다.

  - 버킷에는 정해진 시간 단위의 window(window 1번은 12:00 - 13:00, window 2번은 13:00 - 14:00)가 존재.

  - 시간 단위의 각 window는 요청이 오면 요청 건수가 기록된다.

  - 시간당 정해진 요청 건수가 초과(여기서는 분당 4건이 상한)되는 9번의 요청은 거부된다.

public class FixedWindowCounter extends RateLimiter {
    private final ConcurrentMap<Long, AtomicInteger> windows = new ConcurrentHashMap<>();
    private final int windowSizeInMs;
    
    protected FixedWindowCounter(int maxRequestPerSec, int windowSizeInMs) {
        super(maxRequestPerSec);
        this.windowSizeInMs = windowSizeInMs;
    }
    
    @Override
    boolean allow() {
        long windowKey = System.currentTimeMillis() / windowSizeInMs;
        windows.putIfAbsent(windowKey, new AtomicInteger(0));
        return windows.get(windowKey).incrementAndGet() <= maxRequestPerSec;
    }
    
    public String toString() {
        StringBuilder sb = new StringBuilder("");
        for (Map.Entry<Long, AtomicInteger> entry: windows.entrySet()) {
            sb.append(entry.getKey());
            sb.append(" --> ");
            sb.append(entry.getValue());
            sb.append("\n");
        }
        return sb.toString();
    }
}

 

4) Sliding Window Log

Fixed window counter의 단점인 기간 경계의 편향에 대응하기 위한 알고리즘이다. 하지만, window의 요청건에 대한 로그를 관리해야 하기 때문에 구현과 메모리 비용이 높은 문제점이 있다.

  - 분당 2건의 요청을 처리한다면 12초와 24초에 온 요청은 허용이 되고 36초에 온 요청 분당 2건처리 원칙에 의해 거부되고

  - 1분 24초의 요청이 들어오면 12초와 24초에 온 요청 로그를 pop해서 꺼내 없애고 남은 건 바로 전 요청인 36초에 온거 하나만 있어서 1분 25초에 들어온 요청은 처리가 된다.

public class SlidingWindowLog extends RateLimiter {
    private final Queue<Long> windowLog = new LinkedList<>();
    
    protected SlidingWindowLong(int maxRequestPerSec) {
        super(maxRequestPerSec);
    }
    
    @Override
    boolean allow() {
        long now = System.currentTimeMillis();
        long boundary = now - 1000;
        sychronized (windowLog) {
            while (!windowLog.isEmpty() && windowLog.element() <= boundary) {
            }
            windowLog.add(now);
            log.info("current time={}, log size={}", now, windowLog.size());
            return windowLog.size() <= maxRequestPerSec;
        }
    }
}

 

5) Sliding Window Counter

Fixed window counter의 경계 문제와 Sliding window log의 로그 보관 비용 등의 문제점을 보완할 수 있는 알고리즘이다.

  - 분당 10건 처리한다면 1분안에 9건의 요청이 오고 1분과 2분 사이에는 5건의 요청이 온다고 가정.

  - 1분 15초에 요청이 왔는데 1분 15초 지점은 1분과 2분 사이에서 25% 지점, 이전 기간은 1 - 0.25 = 75% 비율로 계산해서 9 * 0.75 + 5 = 14.75 > 10 으로 한도를 초과했기 때문에 요청은 거부된다. 즉, 이전 window와 현재 window의 비율값으로 계산된 합이 처리 건수를 초과하면 거부된다.

  - 1분 30초 시점에 요청이 온다면 이전 기간은 50%, 9 * 0.5 + 5 = 9.5 < 10 이므로 해당 요청은 처리된다.

 

Sliding Window Counter는 window의 비율이 소수점이 나오게 되면 정확성이 떨어질 수는 있으나, Fixed window counter의 경계 문제와 Sliding window log의 로그 보관 비용 등의 문제점을 개선하게 된다.

 

채용 플랫폼: RateLimitJ

---

Rate Limit을 적용하려면 RFC 6585에 429 Too Many Request HTTP 상태 코드가 제시되어 있고 RateLimit Header Fields for HTTP RFC 초안에도 나와있듯이, RateLimit-Limit(허용되는 요청의 최대수), RateLimit-Remaining(남은 요청 수), RateLimit-Reset(요청 최댓값이 재설정될때까지의 시간) 정보를 Header에 같이 보내주면 좋다.

제한 정보	응답 정보 (HTTP Status)	응답 정보 (Header)
Twitter Rate Limits - 1일 100트윗	429 Too Many Requests	x-rate-limit, x-rate-limit-remaining, x-rate-limit-reset
Github Rate Limits - Basic Authentication or OAuth 활용한 API는 시간당 5000건, 미인증 API는 시간당 60건	403 Forbidden	X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
Slack Rate Limits - 메시지 게시는 초당 1회, 다른 Web API methods는 분당 1~100회, Events는 시간당 30,000	429 Too Many Requests	Retry-After
Facebook Rate Limits - Applications은 시간당 유저수 * 200	403 Forbidden	callcount, totalcputime, total_time
Shopify Rate Limits - 40 Bucket size는 초당 2건, 80 Bucket size는 초당 4건	429 Too Many Requests	X-Shopify-Shop-Api-Call-Limit: 40/40, Retry-After: 2.0

 - Rate Limit 알고리즘은 트래픽 패턴을 잘 분석한 다음 적합한 알고리즘을 선택해야 한다. 유료 서비스가 트래픽 체증에 민감해하지 않다면(관대한) Token Bucket 알고리즘을 선택하고 그 외에는 Fixed Window나 Sliding Window 알고리즘을 선택한다.

 - 기본적으로 서비스 인프라 트래픽을 수용할 수 없는 시점에 도달했을 때 Rate Limit을 적용해야 하며, 외부 서비스에 영향을 쵯고화하는 노력(Common한 API는 Rate Limit에 걸리지 않을 정도로 상한값을 높게 잡음)을 한 다음 Rate Limit을 적용하는게 좋다.

 - 외부 개발자들에게 Rate Limit 정보를 명확하게 알려하고, API 응답에도 요청 정보와 남은 정보 등 트래픽이 초과했을때 오류값 등을 명확히 정의해야 한다.

 

---

2. 리소스 id 난독화

대부분의 서비스들이 기본적으로 자동 증가 ID를 PRIMARY KEY로 사용한다. 그런데, 어떨때는 PRIMARY KEY가 예측이 불가능한 것이 더 나은 경우가 있다. 예를 들어 식당을 예약하고 예약 내용을 얻어 오는 API를 서비스한다고 가정하자. API 클라이언트가 예약 API를 호출했고, 해당 클라이언트를 소유한 사용자의 예약 id인 15번을 담은 JSON을 응답했다고 가정해보자. 인증이나 권한 부여가 없는 API 서비스였다면, 이 클라이언트는 14번 예약을 읽어볼 수도 있고, 16번 예약을 변경하거나 삭제할 수도 있게 된다.

 

id++ 이용해서 API 데이터 전체를 훔칠 수 있다. 가령, /users/{id} 처럼 사용자 profile에 대해 API 요청을 할 수 있다면 사용자 정보를 훔칠 수도 있고, 경쟁자가 서비스의 전체 사용자 수도 카운트할 수 있다. 대형 서비스에서 자동 증가 ID를 절대 사용하면 안되는 이유이다.

 

해결 방법)

  1. DB에 기록할 때 Auto-increment ID를 사용하지 않고, 난수화된 ID로 기록하는 방법

  2. DB 기록은 Auto-increment ID를 사용하되, 사용자에게 전달될때는 난수화하여 전달하는 방법

 

MongoDB와 같은 NoSQL Document DB를 선택했다면, 이 문제는 처음부터 없었을 것이다. 하지만 MySql을 사용하고 있다면 두번째 방법을 이용할 것을 권장한다. 

 

난독화 패키지 정합)

프로젝트 요구에 맞도록 아래와 같이 동작구조를 디자인한다.

   - 난독화 기능을 쉽게 사용할 수 있도록 Service Provider를 만든다.

   - API 에서만 난독화를 적용한다.

   - JSON 응답을 내보낼때, Transformer에서 id를 난독화한다.

   - URL을 통해서 넘어온 난독화된 id 값을 Route Middleware에서 해독한다.

 

API 뿐아니라 서비스 전체에 걸쳐 난독화된 ID를 사용하고 싶다면, Transformer보다는 모든 Model들이 상속받고 있는 추상 부모 클래스에 Accessor를 구현하는 것이 더 적절한 방법이라 생각된다. Transformer 혹은 Accessor를 이용해서 API 응답에만 난독화된 ID를 제공한다면, API 컨트롤러에서 모델에 대한 쿼리를 하기 전에 난독화된 ID를 해독해주면 된다.