[keyword] 2~4장 키워드 정리

[wooyounggggg]

주제

2~4장을 읽고 내용을 요약하거나,
중요✨ 하다고 생각하는 키워드 및 관련 설명을 코멘트로 달아주세요

연관 챕터

10

@caffeine-library/readers-system-design-interview

[wooyounggggg]

4장 처리율 제한 장치의 설계

처리율 제한 장치의 필요성

• DoS 공격에 의한 컴퓨팅 자원 고갈 방지
• 비용 절감 처리. 특히 유료 서드파티 앱을 사용하는 경우 큰 비용 절감 가능성이 있음
• 서버 과부하 방지

API 게이트웨이의 기능

• 처리율 제한
• SSL 종단
• 사용자 인증
• IP 허용 목록 관리 등

처리율 제한 알고리즘

• 토큰 버킷(Token Bucket)
• 누출 버킷(Leaky bucket)
• 고정 윈도 카운터(Fixed window counter)
• 이동 윈도 로그(Sliding window log)
• 이동 윈도 카운터(Sliding window counter)

[binchoo]

Redis Sorted Set + Race Condition 해소

[참고자료] rolling-rate-limiter (블로그) 이동 윈도 로깅 알고리즘을 Redis 저장소의 Sorted Set으로 구현한 내용입니다.

Redis Sorted Set 구조

ZSET 혹은 SortedSet이라 일컫는 자료구조의 모습입니다. Key, Member, Score로 구성됩니다. 특이사항은 매핑들이 Score 기반으로 정렬된다는 점입니다.

Key	ZSET 하나에 부여되는 식별자입니다. 처리율 제한기에서 각 유저마다 고유한 버킷을 할당하고자 한다면, 유저마다 ZSET을 할당하면 된다는 걸 의미합니다.
Member	Map에서의 Key와 같습니다. ZSET에서 유일한 값이며 O(1) 시간복잡도로 대응하는 값에 접근합니다.
Score	Map에서의 Value와 같습니다. 처리율 제한기 구현에서는 요청마다 이 부분에 타임스탬프를 저장합니다

MULTI 명령어

트랜잭션 블럭을 생성한 후 커맨드들을 큐잉한다음 EXEC 명령어로 이들을 아토믹하게 수행합니다.

알고리즘

아래를 과정을 한 트랜잭션 블럭에 담고 수행한다.

1. ZSET에서 [0, now() - interval] 범위의 스코어(타임스탬프)를 갖는 자료들은 무효하므로 삭제한다.
2. ZSET에 now() 시각의 타임스탬프를 추가한다.
3. ZSET에서 타임스탬프들을 읽어들인다.

읽어들인 타임스탬프의 수가 임계치를 넘으면 요청의 처리를 제한한다.

(소개된 코드는 시간당 허용 횟수와 더불어, 요청 간 최소 간격도 고려합니다.)

async limitWithInfo(id: Id): Promise<RateLimitInfo> {
  const timestamps = await this.getTimestamps(id, true);
  return this.calculateInfo(timestamps);
}

protected async getTimestamps(
  id: Id,
  addNewTimestamp: boolean,
): Promise<Array<Microseconds>> {
  const now = getCurrentMicroseconds();
  const key = this.makeKey(id);
  const clearBefore = now - this.interval;

  const batch = this.client.multi();
  batch.zremrangebyscore(key, 0, clearBefore);
  if (addNewTimestamp) {
    batch.zadd(key, String(now), uuid());
  }
  batch.zrange(key, 0, -1, 'WITHSCORES');
  batch.expire(key, this.ttl);

  return new Promise((resolve, reject) => {
    batch.exec((err, result) => {
      if (err) return reject(err);

      const zRangeOutput = (addNewTimestamp ? result[2] : result[1]) as Array<unknown>;
      const zRangeResult = this.getZRangeResult(zRangeOutput);
      const timestamps = this.extractTimestampsFromZRangeResult(zRangeResult);
      return resolve(timestamps);
    });
  });
}

private calculateInfo(timestamps: Array<Microseconds>): RateLimitInfo {
  const numTimestamps = timestamps.length;
  const currentTimestamp = timestamps[numTimestamps - 1];
  const previousTimestamp = timestamps[numTimestamps - 2];

  const blockedDueToCount = numTimestamps > this.maxInInterval;
  const blockedDueToMinDifference =
    previousTimestamp != null &&
    currentTimestamp - previousTimestamp < this.minDifference;

  const blocked = blockedDueToCount || blockedDueToMinDifference;

  // Always need to wait at least minDistance between consecutive actions.
  // If maxInInterval has been reached, also check how long will be required
  // until the interval is not full anymore.
  const microsecondsUntilUnblocked =
    numTimestamps >= this.maxInInterval
      ? (timestamps[Math.max(0, numTimestamps - this.maxInInterval)] as number) -
        (currentTimestamp as number) +
        (this.interval as number)
      : 0;

  const microsecondsUntilAllowed = Math.max(
    this.minDifference,
    microsecondsUntilUnblocked,
  ) as Microseconds;

  return {
    blocked,
    blockedDueToCount,
    blockedDueToMinDifference,
    millisecondsUntilAllowed: microsecondsToMilliseconds(microsecondsUntilAllowed),
    actionsRemaining: Math.max(0, this.maxInInterval - numTimestamps),
  };
}

기존 알고리즘과 차이점

기존 알고리즘

• 유저마다 2개 키를 보유함: 최신 타임스탬프, 토큰 버킷 수량(Integer)
• ① 최근 타임스탬프를 읽어들이고 ② 현재 시각과 차이를 토대로 토큰 버킷 수량을 계산하여 갱신하는 과정 이 아토믹하게 수행 불가능 하다고 한다.

rolling-rate-limiter

• ZSET 자료구조를 사용하면 토큰 버킷 수량을 직접 계산하지 않게 된다. 현재 자료구조의 크기와 임계값을 비교하면 됨.
• ZSET 관련 명령어들을 아토믹하게 조합하여 사용 가능함.

결론: ZSET 자료구조 도입> 토큰 버킷 수량을 계산하는 커스텀 연산의 배제> 오로지 Redis 명령어로 트랜잭션을 구성> 따라서 Race Condition을 막았다는 내용입니다.