[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;
  }
}