[Medium] 手寫 Cache

題目描述

限流 (Rate-limiting) 是一種控制特定使用者或 IP 位址，在給定時間範圍內向 API 發出請求的頻率的方式。限流有助保護服務免於被濫用、DoS 攻擊等，讓運算資源能更均衡地被使用。

給定你要為一個有一定流量的後端服務增加限流功能，來確保運算資源不會被濫用。在這個限流功能中，你要設計一個名為 Cache 的 JavaScript class，該 class 將成為我們的限流做快取。該快取需要支援過期窗口 (expiration window) 請求計數的儲存和管理，來追蹤個別使用者的限流狀況。

具體來說，這個 Cache 應該要具有以下方法

• 快取的基本 setter 和 getter。
• isBlocked(identifier) 方法會接受一個 identifier (例如一個 IP 位址)，並判斷相關的請求計數，是否在限流時間範圍內超過某個門檻值。
  • 如果是，則回傳 blocked: true與要封鎖到什麼時候 (reset)；
  • 如果否，則回傳 blocked: false。
• blockUntil(identifier: string, reset: number) 方法，該方法接收一個identifier ，並基於此來設定該 identifier 要被限流多久 (reset 是指要封鎖到什麼時候)。
• incr(key: string) 方法接受一個鍵 (key)，並將對應鍵的值增加 1，然後回傳新的值。如果該鍵不存在，則將其初始化為 1。

class Cache {
  constructor(cache) {}

  isBlocked(identifier) {}

  blockUntil(identifier, reset) {}

  set(key, value) {}

  get(key) {}

  incr(key) {}
}

分析與思路

在 Cache 當中先用 JavaScript 的 Map 來創建一個 cache。Map 資料結構能有效地將鍵與值建立關聯，這邊我們的鍵是 identifier 而值則會是 reset。

在建構式 (constructor) 中，用 this.cache = cache; 來建立 cache。而 getter 方法中，透過 this.cache.get(key) || null; 取得對應鍵的值。在 setter 方法中，則用 this.cache.set(key, value); 來為鍵設定值。

isBlocked 方法是限流的核心。它會先檢查 identifier 是否在 cache 當中。如果不在，表示沒有被封鎖；如果在，則比較 reset 時間與當前時間 (Date.now() )。如果 reset 時間已過，我們移除封鎖狀態 (從 cache 中刪除) 並回傳已解封狀態。如果 reset 的時間還沒過，表示仍被限制，這時回傳 blocked: true 以及被封鎖的 reset 時間。

blockUntil 方法是用來對 identifier 設置封鎖的時間，將 identifier 與 reset 建立鍵值對的關聯。這樣之後就可以查看該 identifier 的封鎖時間是什麼。

incr 方法用於增加 cache 中與某個鍵所對應的值。它會先根據鍵來獲取對應的值，然後將該值遞增。遞增後，會先透過 this.cache.set(key, value); 來更新 cache。最後回傳 value。

class Cache {
  cache = new Map();

  constructor(cache) {
    if (cache) {
      this.cache = cache;
    }
  }

  isBlocked(identifier) {
    if (!this.cache.has(identifier)) {
      return { blocked: false, reset: 0 };
    }

    const reset = this.cache.get(identifier);
    if (reset < Date.now()) {
      this.cache.delete(identifier);
      return { blocked: false, reset: 0 };
    }

    return { blocked: true, reset: reset };
  }

  blockUntil(identifier, reset) {
    this.cache.set(identifier, reset);
  }

  set(key, value) {
    this.cache.set(key, value);
  }

  get(key) {
    return this.cache.get(key) || null;
  }

  incr(key) {
    let value = this.cache.get(key) || 0;
    value += 1;
    this.cache.set(key, value);
    return value;
  }
}