search

data-tech-newbie / system-design-interview

System Design Interview An Insider’s Guide by Alex Xu - Study
0 stars 0 forks source link

Chapter 4 #2

Open matteblack9 opened 1 year ago

matteblack9 commented 1 year ago

How we built rate limiting capable of scaling to millions of domains

http {
    limit_req_zone $binary_remote_addr zone=ratelimitzone:10m rate=15r/m;
    ...
    server {
        ...
        location /api/expensive_endpoint {
            limit_req zone=ratelimitzone;
        }
    }
}

Cloudflare edge 서버의 경우 NGINX로 동작하고 있고, 위와 같은, rate limiting moudule을 제공 하고 있다.

하지만, binary_remote_addr 라는 엔드포인트에 대해 요청 제한을 하고자 할 때, 이 엔드포인트에 대해서 10mb의 메모리를 사용하게 하고, 분당 15회 request 라는 제한을 두고 싶을 때, 어떻게 효율적으로 분당 요청 횟수를 counting 할 수 있는지 살펴보자.

image

cloudflare의 경우는 사용자의 요청이 가장 가까운 데이터 센터에 라우팅되게 되는데, 각 서버마다 burst 하게 API를 요청하는경우도 있고, 아닌 경우도 있는 다양한 상황이 연출됨. 그래서 burst한 요청을 하는 경우 대비하기 위해 rate limiting 을 더 효율적으로 할 필요성을 느꼈다.

우리는 memcached 데이터베이스를 분할하고, 각 데이터센터에서 각 요청에 대해 counting 할 수 있도록 데이터베이스를 설계하였다.

첫번째 방법, 간단한 방법인 bucket leak 알고리즘을 사용.

image

일정한 시간 주기마다 버킷에 토큰을 발급하고, 요청 시, 토큰을 소비하게 함. 버킷에 토큰이 없으면, 요청을 허용하지 아니한다.

단점:

두번째 방법,

고정 윈도우 알고리즘의 경우, 특정 시간대에만 counting이 reset 되기 때문에, 정확성이 떨어지고, 리셋 되기 직전 트래픽 급증을 하면, 급증한 트래픽이 백엔드 시스템으로 갈 수 있다.

세번째 방법

샘플링 기간동안, 얼마나 많은 요청이 수신되었는지 세는 방법 모든 타임스탬프를 저장하고, 카운터의 상태를 확인해야하기 때문에, 처리와 메모리 요구사항이 매우 큶.

네번째 방법

고정 윈도우 알고리즘 + async 한 카운팅

image

image

rate = 42 * ((60-15)/60) + 18
     = 42 * 0.75 + 18
     = 49.5 requests
gimmizz commented 1 year ago

Throttle API requests for better throughput

https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html

  • AWS 에서는 API Gateway 를 두고 있고, API Gateway는 요청에 대해 토큰이 계산되는 토큰 버킷 알고리즘을 사용하여 API에 대한 요청을 제한하고 있음

How throttling limit settings are applied in API Gateway : 어떤 기준을 사용해서 API 호출을 제어하고 있을까?

  1. AWS throttling limits : 리전의 모든 계정과 클라이언트에 적용
    • AWS 자체에서 설정하며, 개인이 수정할 수 없는 값
  2. Per-account limits : 사용자 계정당 limit
    • 지정된 리전에 있는 계정의 모든 API에 적용
    • 요청 시 늘릴 수 있는 값이지만, 1번의 AWS throttling limits 를 넘을 수 없다.
    • ex) Throttle quota per account, per Region across HTTP APIs, REST APIs, WebSocket APIs, and WebSocket callback APIs
      • 버킷 크기 (버킷에 담을 수 있는 토큰의 최대 개수) : maximum bucket capacity of 5,000 requests
      • 토큰 공급률 (refill rate, 초당 몇 개의 토큰이 버킷에 공급되는가) : 10,000 requests per second (RPS) + additional burst capacity
  3. Per-API, per-stage throttling limits: API 메서드 수준에서 적용
  4. Per-client throttling limits : API 키를 클라이언트 식별자로 사용하는 클라이언트에게 적용

Rate Limit vs Burst Limit

https://stackoverflow.com/questions/70423503/api-gateway-throttling-burst-limit-vs-rate-limit

hyeriful commented 1 year ago

What is edge computing

https://www.cloudflare.com/ko-kr/learning/serverless/glossary/what-is-edge-computing/

Edge computing?

대기 시간과 대역폭 사용을 줄이기 위해 데이터 소스와 가장 가까운 곳에서 컴퓨팅을 하게 하는 네트워킹 철학. edge computing은 클라우드에서 실행하는 프로세스를 줄이고 해당 프로세스를 사용자의 컴퓨터, IoT 장치, 에지 서버 등의 로컬 위치로 이동하는 것이다. 컴퓨팅을 네트워크의 에지로 가져오면, 클라이언트와 서버 사이에 필요한 장거리 통신의 양이 최소화된다.

다른 computing model 과의 차이

사례

장단점

장점

단점

Enoch-Kim commented 1 year ago

Better Rate Limiting With Redis Sorted Sets

https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/

다음과 같은 요구사항을 충족하는 rate limiter가 필요했음

token bucket

token bucket을 사용해봤으나 별로였음 -> 책 내용에 단점이 있으니.. 구현 방식은 생략. 유저당 하나의 카운터만 두면 되기 때문에 메모리 효율은 좋으나, 사용자가 많아지면 refill 동작에서 write가 너무 많이 생김 -> Redis에 맞지 않음.

이후 다음의 더 정교한 방법으로 token bucket을 구현

문제는 Redis는 하나의 동작에 대해 Atomic함을 유지하는데, 위의 작업은 두가지 동작을 실행. 두 동작을 보장하려면 luascripting을 사용하거나 해야하는데 사용해본 경험이 없고 Mock Test가 어려움 -> 위의 방법도 분산 환경에서 동작하지 않음 (race condition)

Sorted Sets

Redis가 race condition을 해결할 수 있는 Sorted Set을 구현해둠, 동작 원리는 다음과 같음

위의 동작이 MULTI 커맨드로 atomic하게 동작하기 때문에 race condition을 피할 수 있고, 분산환경에서 잘 동작함.. (그걸 어떻게 했는데..)

위의 방식은 자신들의 요구사항에 맞을 수 있으나 다른 사람들의 요구사항에 맞지 않을 수 있음. 모든 레디스 작업들이 처리된 후 사용자의 요청을 처리하기 때문 -> 즉 사용자가 계속 임계치를 넘는 요청을 하면 점차 허용되는 것이 아니라 무한정 버려짐

모듈 코드

NPM의 rolling-rate-limiter에 올려둠 -> Redis 말고 메모리 상에서도 동작시킬 수 있음

/*  Setup:  */

  var RateLimiter = require("rolling-rate-limiter");
  var Redis = require("redis");
  var client = Redis.createClient(config);

  var limiter = RateLimiter({
    redis: client,
    namespace: "UserLoginLimiter"
    interval: 1000
    maxInInterval: 10
    minDifference: 100
  });

  /*  Action:  */

  function attemptAction(userId, cb) {
    limiter(userId, function(err, timeLeft) {
      if (err) {

        // redis failed or similar.

      } else if (timeLeft > 0) {

        // limit was exceeded, action should not be allowed
        // timeLeft is the number of ms until the next action will be allowed
        // note that this can be treated as a boolean, since 0 is falsy

      } else {

        // limit was not exceeded, action should be allowed

      }
    });
  }

Express 미들웨어 쓰면 다음처럼도 가능

var limiter = RateLimiter({
    redis: redisClient,
    namespace: "requestRateLimiter",
    interval: 60000,
    maxInInterval: 100,
    minDifference: 100
  });

  app.use(function(req, res, next) {

    // "req.ipAddress" could be replaced with any unique user identifier
    limiter(req.ipAddress, function(err, timeLeft) {
      if (err) {
        return res.status(500).send();
      } else if (timeLeft) {
        return res.status(429).send("You must wait " + timeLeft + " ms before you can make requests.");
      } else {
        return next();
      }
    });

  });

추가 참고 사이트

gimmizz commented 1 year ago

Conflict-free replicated data type https://crdt.tech/