[TIL - 231212] Javascript Map 활용, Cache를 활용한 Rate Limit

오늘 한 일

• 코딩 과제 진행 중 Map을 활용한 성능 개선
• Cache를 활용하여 Rate Limit 구현

Map을 활용한 성능 개선

• Javascript Data Type 중 하나인 Map을 이용한 성능 개선 진행
• Map은 Key-Value 형태로 이루어진 자료구조이다.
• Map의 특징 중 하나는, 해시 테이블 알고리즘을 통해 구현한다는 점이다.

Javascript의 데이터 타입 중 하나인 Map을 활용하여 성능 개선을 진행했습니다.

코딩 과제의 목표는 크롤링한 데이터의 상품 카테고리 매칭 혹은 단어 치환입니다.

카테고리 혹은 단어 치환 List를 Map을 통해 성능 개선하였는데, 이때 Map은 해시 테이블 알고리즘으로 구현되어 있어서 어떤 데이터를 참조할 경우 시간복잡도가 O(1)이라는 것입니다.

// 특정 단어 조회 후 치환 작업
optionList.forEach((data, _) => {
  translationMap.forEach((value, key) => {
    data.name = data.name.replaceAll(key, value);
  });
});

기존 코드의 경우 Array의 forEach 메서드를 통해 구현하였으며, 시간 복잡도가 O(N^2)였습니다.

그러나 Map을 통해서 구현한 결과 코드가 더욱 간결해지고, 속도 또한 빨라졌습니다.

// Map으로 변환
const translationMap = new Map<string, string>();
translateWordList.forEach((value, _) => {
  translationMap.set(value.src, value.dest);
});

const start = Date.now();

// 특정 단어 조회 후 치환 작업
optionList.forEach((data, _) => {
  // 공백을 통해 단어 구분
  const words = data.name.split(' ');
  // 단어 치환 작업 진행
  const translatedWords = words.map(
    // 단어가 있을 경우 치환하고, 없는 경우 기존 단어로 사용
    (word) => translationMap.get(word) || word,
  );
  data.name = translatedWords.join(' ');
});

const end = Date.now();

자료구조 Map에 대한 정리는 내일 다시 할 예정입니다.

https://www.jiwon.me/v8-deep-dives-understanding-map-internals/

[번역] [V8 Deep Dives] Javascript Map을 파헤쳐보자

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map

Map - JavaScript | MDN

Cache를 활용하여 Rate Limit 구현

• Rate Limit을 사용하지 않고, Rate Limit 진행하는 방법 
• Cache를 활용하여 Cache Data가 있는 경우, Delay를 거는 방법으로 적용
• 재귀 함수를 통해 Cache가 없는 경우 Request 진행하도록 구현
• 단, Request의 순서와 처리 순서를 보장할 수 없다는 단점이 존재한다.

과제 중, 중계 서버에서 Rate Limit을 구현하는 과제가 있었습니다.

단, 실제로 Rate Limit을 거는 것이 아닌, Request를 지연하는 방식이였습니다.

간단한 방식으로 Cache에 TTL을 걸고, Id 별로 Cache를 저장한 뒤, Cache Data가 있는 경우 지연시키는 방법이였습니다.

export class RateLimitInterCeptor implements NestInterceptor {
  constructor(@Inject(CACHE_MANAGER) private cacheManager: Cache) {}
  async intercept(
    context: ExecutionContext,
    next: CallHandler<any>,
  ): Promise<Observable<any>> {
    // Context를 통해 Request.headers.id를 받아옵니다.
    const httpContext = context.switchToHttp();
    const req: Request = httpContext.getRequest();
    const id = req.headers.id as string;

    const user = await this.cacheManager.get(id);
    if (user) {
      await this.delayRequest(id, 100);
      return next.handle();
    } else {
      await this.cacheManager.set(id, 1, 100);
      return next.handle();
    }
  }

  /**
   * Cache 값이 있을 시, 0.1초간 delay해주는 함수 구현
   * 재귀함수를 통해 트래픽이 몰려도, 0.1초간 delay를 해주는 기능
   * 단, Request 순서에 따라 처리 순서가 보장되어 있지 않음
   * @param {string} id Header에 들어가는 UserID
   * @param {number} ms ms로 delay 시간을 입력받는다.
   * @returns
   */
  private async delayRequest(id: string, ms: number): Promise<void> {
    await new Promise((resolve) => setTimeout(resolve, ms));
    const checkId = await this.cacheManager.get(id);
    if (checkId) return await this.delayRequest(id, ms);
    await this.cacheManager.set(id, 1, ms);
    return;
  }
}

이러한 방식의 문제점은 아래와 같습니다.

• 대용량 트래픽이 들어왔을 시, Request가 들어오는 순서와 처리 순서가 동일하게 보장되지 않는다는 단점

따라서, 간단히 생각해본 결과, Queue를 통해 구현하는 방법 또한 나쁘지 않다고 생각되며, 추후 구현해 볼 예정입니다.