Học từ web lớn #44: LRU cache theo 3 cách (Apple, Similarweb, Outlook)

Cache trong trình duyệt nào cũng cần một giới hạn. Không giới hạn thì tab mở cả ngày sẽ giữ mọi thứ từng tải. Giới hạn thì phải chọn xoá cái gì khi đầy. Lựa chọn phổ biến nhất là LRU (least recently used): xoá thứ lâu nhất chưa được dùng tới.

Đọc code của ba trang lớn, mình gặp ba cách cài LRU khác nhau, mỗi cách một bài học:

• Apple (apps.apple.com) dựa vào tính chất ít người để ý của Map: luôn giữ thứ tự chèn. Code ngắn nhất.
• Similarweb viết danh sách liên kết đôi + Map, kiểu sách giáo khoa: mọi thao tác O(1).
• Outlook dùng mảng và indexOf, chậm hơn, nhưng có một tính năng hai bên kia không có: ghim những key đang hiển thị để chúng không bao giờ bị đẩy ra.

▶ Mở demo toàn màn hình ↗ · Sửa code trên StackBlitz ↗ · Xem source trên GitHub ↗

Thử ở mục 1: mở A, B, C, ghim A, mở D. Cache đầy, B (lâu nhất chưa dùng mà không bị ghim) bị đẩy ra, A ở lại dù cũ nhất. Mục 2 cho thấy cạm bẫy của Map.set. Mục 3 đo 100.000 lần đọc/ghi.

#Apple: dựa vào thứ tự chèn của Map

Code ở apps.apple.com/shared/utils/src/lru-map.ts, kế thừa thẳng Map (rút gọn):

export class LruMap<K, V> extends Map<K, V> {
  get(key: K): V | undefined {
    let value: V | undefined;
    if (this.has(key)) {
      value = super.get(key);
      // Map entries are always in insertion order. So
      // readding, pushes this entry to the top of the LRU.
      this.delete(key);
      super.set(key, value!);
    }
    return value;
  }

  set(key: K, value: V): this {
    super.set(key, value);
    this.prune();
    return this;
  }

  private prune(): void {
    while (this.size > this.sizeLimit) {
      const leastRecentlyUsedKey = this.keys().next().value;
      this.delete(leastRecentlyUsedKey);
    }
  }
}

Ý tưởng gọn: đặc tả ECMAScript bảo đảm Map duyệt theo thứ tự chèn, nên key đầu tiên của keys() luôn là key được chèn (hoặc chèn lại) lâu nhất. "Dùng tới" một key bằng cách xoá rồi chèn lại nó ở cuối. Không cần cấu trúc phụ nào, và cả delete lẫn set của Map đều nhanh.

LruMap được dùng trong shared/utils/src/history.ts để nhớ state và vị trí cuộn của 10 trang gần nhất (HISTORY_SIZE_LIMIT = 10), phục vụ nút Back.

#Cạm bẫy: set() một key đã có

Nhìn lại set: nó gọi super.set không xoá trước. Theo đặc tả, Map.prototype.set với key đã tồn tại chỉ thay giá trị, giữ nguyên vị trí cũ. Hệ quả: cập nhật một key không làm nó "mới".

const lru = new LruMap<string, number>(3);
lru.set('a', 1).set('b', 1).set('c', 1);
lru.set('a', 2); // vừa cập nhật a
lru.set('d', 1); // đầy, phải đẩy key cũ nhất ra
[...lru.keys()]; // ['b', 'c', 'd'] : a bị đẩy ra dù vừa được cập nhật

Trong history.ts lỗi này không lộ ra, vì mọi chỗ set một key cũ đều get nó ngay trước đó (updateState, beforeTransition), và get đã đưa key lên cuối. Nhưng ai dùng lại class này cho việc khác sẽ gặp. Sửa bằng một dòng: this.delete(key) trước super.set.

Cũng trong thư mục đó có memoize.ts giới hạn 5 kết quả, dùng cùng mẹo cache.keys().next().value để xoá. Nhưng lần đọc trúng cache không xoá rồi chèn lại, nên đó là FIFO (vào trước ra trước), không phải LRU: kết quả được dùng liên tục vẫn bị đẩy ra khi tới lượt.

#Similarweb: danh sách liên kết đôi + Map

Code ở pro.similarweb.com/scripts/common/services/lruCache.ts, dùng cho appInfoService.ts (cache thông tin ứng dụng, mặc định 20 mục). Đây là cách cài trong sách giáo khoa:

• Map<key, node> để tìm node trong O(1).
• Danh sách liên kết đôi giữ thứ tự: head là mới dùng nhất, tail là lâu nhất.
• Đọc: tháo node khỏi chỗ cũ, gắn lên đầu. Đầy: tháo tail.

Có hai chi tiết nhỏ: get() gọi lại put(key, value) nên mỗi lần đọc tạo một node mới thay vì di chuyển node cũ (vẫn O(1), chỉ tốn thêm rác cho GC), và mỗi lần trượt cache in console.log ra console. Class có sẵn *[Symbol.iterator]() để duyệt bằng for…of.

#Outlook: mảng + ghim key đang dùng

Code ở outlook.live.com/src/modules/owa-mru-cache/src/MruCache.ts. Thứ tự giữ bằng một mảng mruList, chạm vào key là indexOf + splice + push: O(n) mỗi lần. Với cache hội thoại 50 mục (owa-mail-store/src/store/conversationCache.ts) thì không đáng kể.

Điểm đáng học là tham chiếu (reference):

registerReference(reference: ReferenceGetter) {
  this.references.push(reference);
}

private purgeTillSize(size: number) {
  let i = 0;
  while (this.mruList.length > size && i < this.mruList.length) {
    const key = this.mruList[i];
    if (this.isReferenced(key)) i++; // đang được dùng: bỏ qua, xét key kế tiếp
    else this.removeItemAtIndex(i);
  }
}

Khung đọc thư đăng ký một hàm trả về danh sách hội thoại đang mở (owa-mail-reading-pane-store/src/store/Store.ts):

conversationCache.registerReference(() => [...store.loadedConversationReadingPaneViewStates.keys()]);

Thư đang hiển thị không bao giờ bị đẩy ra, kể cả khi nó là thư cũ nhất trong cache. Nếu mọi key đều đang được dùng, cache chấp nhận vượt giới hạn thay vì xoá thứ trên màn hình. Đây đúng là điểm yếu của LRU thuần mà bài #43 nói tới: LRU không biết cái gì đang hiển thị.

Outlook còn có owa-nested-mru-cache: cache hai tầng (ví dụ tầng một là người gửi, tầng hai là người nhận) cho mail tips, mỗi mục có hạn 2 giờ, tổng tối đa 300 mục, đầy thì sắp xếp toàn bộ theo thời gian tạo và xoá 50 mục cũ nhất một lượt. Có một chỗ đáng để ý: hàm dọn so tổng số mục với hằng CACHE_LIMIT thay vì giới hạn truyền vào constructor.

#Bên trong: vì sao Map đủ dùng làm LRU?

Map trong V8 (và các engine khác) được cài bằng bảng băm có thứ tự (ordered hash table): các mục nằm trong một mảng theo thứ tự chèn, bảng băm trỏ vào mảng đó. Xoá một mục chỉ đánh dấu ô là trống; khi quá nhiều ô trống thì bảng được dựng lại. Vì vậy:

flowchart LR
  subgraph M["Map: mảng mục theo thứ tự chèn"]
    direction LR
    A["a"] --> B["b"] --> C["c"]
  end
  G["get b: delete b rồi set b"] --> M2
  subgraph M2["sau khi đọc b"]
    direction LR
    A2["a"] --> C2["c"] --> B2["b"]
  end
  M2 --> E["đầy: keys().next() là a, xoá a"]

• delete + set là hai thao tác O(1) trung bình.
• keys().next() lấy mục đầu, nhưng nếu đầu mảng toàn ô đã xoá thì phải bỏ qua chúng. Engine dọn lại bảng định kỳ nên chi phí trung bình vẫn thấp.

Danh sách liên kết đôi thì O(1) chắc chắn, nhưng mỗi mục là một object riêng (tốn bộ nhớ hơn, nhiều việc cho GC hơn). Trong số đo ở dưới, cả hai cách đều nhanh; mảng + indexOf mới là cách chậm hẳn khi cache lớn.

#Viết lại

Code ở src/lib/lruCache.ts. Bản dựa trên Map, đã sửa cạm bẫy set và thêm ghim:

  set(key: K, value: V): this {
    // Map.set với key đã có KHÔNG đổi vị trí của nó, phải xoá rồi chèn lại
    this.map.delete(key);
    this.map.set(key, value);
    this.prune();
    return this;
  }

  delete(key: K) {
    return this.map.delete(key);
  }

  /** Từ cũ nhất tới mới nhất. */
  keys() {
    return [...this.map.keys()];
  }

  private prune() {
    const { max, isPinned, onEvict } = this.options;
    if (this.map.size <= max) return;
    for (const [key, value] of this.map) {
      if (this.map.size <= max) break;
      if (isPinned?.(key)) continue; // đang dùng: bỏ qua, xét key kế tiếp
      this.map.delete(key);
      onEvict?.(key, value);
    }
  }
}

Bản danh sách liên kết đôi chỉ khác ở cách đưa node lên đầu và cách dọn từ đuôi:

  private moveToFront(node: Node<K, V>) {
    if (this.head === node) return;
    this.unlink(node);
    node.next = this.head;
    if (this.head) this.head.prev = node;
    this.head = node;
    this.tail ??= node;
  }

  private prune() {
    const { max, isPinned, onEvict } = this.options;
    let node = this.tail;
    while (this.nodes.size > max && node) {
      const prev = node.prev;
      if (!isPinned?.(node.key)) {
        this.unlink(node);
        this.nodes.delete(node.key);
        onEvict?.(node.key, node.value);
      }
      node = prev;
    }
  }
}

/**
 * Hai cách viết LRU cache không cần thư viện, cộng tính năng "ghim" key đang dùng.
 *
 * - LruMap: dựa vào việc Map luôn giữ thứ tự chèn (cách của Apple trên apps.apple.com).
 * - LinkedLru: danh sách liên kết đôi + Map, mọi thao tác O(1) (cách của Similarweb).
 * - isPinned: key đang được giao diện dùng thì không bị đẩy ra (ý tưởng từ MruCache của Outlook).
 */

export interface LruOptions<K, V> {
  max: number;
  /** key đang được dùng (vd thư đang mở) thì không bị đẩy ra, kể cả khi cache đã đầy */
  isPinned?: (key: K) => boolean;
  onEvict?: (key: K, value: V) => void;
}

function checkMax(max: number) {
  if (!Number.isInteger(max) || max < 0) throw new RangeError(`max phải là số nguyên ≥ 0, nhận ${max}`);
}

/** LRU dựa trên thứ tự chèn của Map: key đầu tiên luôn là key lâu chưa dùng nhất. */
export class LruMap<K, V> {
  private map = new Map<K, V>();
  private readonly options: LruOptions<K, V>;

  constructor(options: LruOptions<K, V>) {
    checkMax(options.max);
    this.options = options;
  }

  get size() {
    return this.map.size;
  }

  /** Đọc và đưa key lên "mới dùng nhất". */
  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key)!;
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  /** Đọc mà KHÔNG đổi thứ tự (dùng cho debug, hiển thị). */
  peek(key: K): V | undefined {
    return this.map.get(key);
  }

  has(key: K) {
    return this.map.has(key);
  }

  set(key: K, value: V): this {
    // Map.set với key đã có KHÔNG đổi vị trí của nó, phải xoá rồi chèn lại
    this.map.delete(key);
    this.map.set(key, value);
    this.prune();
    return this;
  }

  delete(key: K) {
    return this.map.delete(key);
  }

  /** Từ cũ nhất tới mới nhất. */
  keys() {
    return [...this.map.keys()];
  }

  private prune() {
    const { max, isPinned, onEvict } = this.options;
    if (this.map.size <= max) return;
    for (const [key, value] of this.map) {
      if (this.map.size <= max) break;
      if (isPinned?.(key)) continue; // đang dùng: bỏ qua, xét key kế tiếp
      this.map.delete(key);
      onEvict?.(key, value);
    }
  }
}

interface Node<K, V> {
  key: K;
  value: V;
  prev: Node<K, V> | null;
  next: Node<K, V> | null;
}

/** LRU bằng danh sách liên kết đôi: head = mới dùng nhất, tail = lâu chưa dùng nhất. */
export class LinkedLru<K, V> {
  private nodes = new Map<K, Node<K, V>>();
  private head: Node<K, V> | null = null;
  private tail: Node<K, V> | null = null;
  private readonly options: LruOptions<K, V>;

  constructor(options: LruOptions<K, V>) {
    checkMax(options.max);
    this.options = options;
  }

  get size() {
    return this.nodes.size;
  }

  get(key: K): V | undefined {
    const node = this.nodes.get(key);
    if (!node) return undefined;
    this.moveToFront(node);
    return node.value;
  }

  peek(key: K): V | undefined {
    return this.nodes.get(key)?.value;
  }

  has(key: K) {
    return this.nodes.has(key);
  }

  set(key: K, value: V): this {
    const existing = this.nodes.get(key);
    if (existing) {
      existing.value = value;
      this.moveToFront(existing);
    } else {
      const node: Node<K, V> = { key, value, prev: null, next: this.head };
      if (this.head) this.head.prev = node;
      this.head = node;
      this.tail ??= node;
      this.nodes.set(key, node);
      this.prune();
    }
    return this;
  }

  delete(key: K) {
    const node = this.nodes.get(key);
    if (!node) return false;
    this.unlink(node);
    this.nodes.delete(key);
    return true;
  }

  /** Từ cũ nhất tới mới nhất, cùng thứ tự với LruMap.keys(). */
  keys() {
    const out: K[] = [];
    for (let node = this.tail; node; node = node.prev) out.push(node.key);
    return out;
  }

  private unlink(node: Node<K, V>) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;
    node.prev = node.next = null;
  }

  private moveToFront(node: Node<K, V>) {
    if (this.head === node) return;
    this.unlink(node);
    node.next = this.head;
    if (this.head) this.head.prev = node;
    this.head = node;
    this.tail ??= node;
  }

  private prune() {
    const { max, isPinned, onEvict } = this.options;
    let node = this.tail;
    while (this.nodes.size > max && node) {
      const prev = node.prev;
      if (!isPinned?.(node.key)) {
        this.unlink(node);
        this.nodes.delete(node.key);
        onEvict?.(node.key, node.value);
      }
      node = prev;
    }
  }
}

/** Ghi nhớ kết quả hàm, giới hạn số kết quả bằng LRU (Apple có hàm memoize tương tự, giới hạn 5). */
export function memoizeLru<A extends unknown[], R>(
  fn: (...args: A) => R,
  { max = 5, key = (...args: A) => JSON.stringify(args) }: { max?: number; key?: (...args: A) => string } = {},
) {
  const cache = new LruMap<string, R>({ max });
  return (...args: A): R => {
    const k = key(...args);
    if (cache.has(k)) return cache.get(k)!;
    const result = fn(...args);
    cache.set(k, result);
    return result;
  };
}

Khác bản gốc:

• LruMap không kế thừa Map mà bọc nó bên trong. Kế thừa thì mọi phương thức của Map (forEach, entries, set gọi từ constructor…) đều lộ ra ngoài và đi vòng qua logic LRU.
• set xoá key trước khi chèn: cập nhật giá trị cũng tính là "dùng tới".
• Thêm peek để đọc mà không đổi thứ tự (cho màn hình debug, log).
• Cả hai bản nhận isPinned (ý tưởng tham chiếu của Outlook) và onEvict (báo khi một key bị đẩy ra, để giải phóng tài nguyên đi kèm như object URL).
• memoizeLru là LRU thật: lần đọc trúng cũng đưa kết quả lên "mới nhất", khác memoize FIFO của Apple.

#Đi qua code

• prune của LruMap duyệt Map từ cũ tới mới và xoá trong lúc duyệt. Đặc tả cho phép xoá phần tử đang duyệt; vòng for…of vẫn đi tiếp đúng. Key bị ghim thì continue, xét key sau.
• prune của LinkedLru đi ngược từ tail về head, lưu prev trước khi tháo node. Cũng bỏ qua key bị ghim.
• Cache có thể vượt max khi số key bị ghim lớn hơn max. Đó là chủ ý: thà tốn thêm vài mục còn hơn xoá thứ đang hiển thị. Lần set tiếp theo sau khi bỏ ghim sẽ dọn về đúng giới hạn.
• keys() của cả hai bản trả về cùng thứ tự (cũ tới mới), nên demo kiểm tra được ba cách cho cùng kết quả trên cùng dãy thao tác.
• checkMax từ chối max không phải số nguyên không âm. Apple kiểm tra isFinite, vì Infinity làm vòng prune vô nghĩa.

#Tại sao không làm cách khác?

Tại sao không dùng mảng như Outlook? Với 50 mục thì mảng hoàn toàn ổn, và còn dễ đọc. Mục 3 của demo, trên Chromium, 100.000 lần đọc/ghi: sức chứa 500 thì ba cách gần như ngang nhau (khoảng 14 đến 24ms); 10.000 thì mảng mất khoảng 84ms, Map và danh sách liên kết khoảng 8 đến 13ms. Con số thay đổi theo máy, nhưng xu hướng thì rõ: chi phí của mảng tăng theo kích thước cache.

Tại sao không dùng WeakMap? WeakMap không có thứ tự, không đếm được kích thước, và key phải là object. Nó hợp cho việc "gắn dữ liệu phụ vào object, object mất thì dữ liệu mất theo", không phải cho cache có giới hạn.

Tại sao không xoá theo thời gian (TTL)? TTL trả lời "dữ liệu này còn đúng không", LRU trả lời "bộ nhớ đã đầy chưa". Hai việc khác nhau; Outlook dùng cả hai trong nested cache (hạn 2 giờ + giới hạn 300 mục).

#Edge case và cạm bẫy

• Giá trị undefined. get trả undefined cho cả "không có" lẫn "có, giá trị là undefined". Cần phân biệt thì kiểm tra has trước (như memoizeLru).
• Key là object. Map so key theo tham chiếu: hai object { id: 1 } khác nhau là hai key. Dùng chuỗi ổn định (JSON.stringify với thứ tự key cố định) nếu cần so theo giá trị.
• Hàm ghim chạy mỗi lần dọn. Outlook gọi mọi hàm tham chiếu cho mỗi key được xét. Hàm ghim nên rẻ: tra một Set thay vì duyệt mảng.
• Tài nguyên đi kèm. Cache ảnh dạng object URL (URL.createObjectURL) phải revokeObjectURL trong onEvict, nếu không bộ nhớ của blob vẫn bị giữ.
• SSR. Cache cấp module trên server dùng chung giữa mọi request và sống suốt đời process. zappos.com/src/helpers/memoize.ts chỉ memoize khi chạy trên trình duyệt, trên server thì gọi thẳng hàm, vì cache chưa có giới hạn kích thước.

#Dùng trong dự án

import { LruMap } from './lruCache';

const openTabs = new Set<string>();

// Ảnh xem trước của tài liệu: giữ 30 ảnh gần nhất, ảnh đang mở thì không xoá
const thumbnails = new LruMap<string, string>({
  max: 30,
  isPinned: (docId) => openTabs.has(docId),
  onEvict: (_docId, objectUrl) => URL.revokeObjectURL(objectUrl),
});

async function getThumbnail(docId: string) {
  const hit = thumbnails.get(docId);
  if (hit) return hit;
  const blob = await fetch(`/api/docs/${docId}/thumbnail`).then((r) => r.blob());
  const url = URL.createObjectURL(blob);
  thumbnails.set(docId, url);
  return url;
}

#Kiểm thử

import { describe, expect, it } from 'vitest';
import { LinkedLru, LruMap, memoizeLru } from './lruCache';

describe.each([
  ['LruMap', LruMap],
  ['LinkedLru', LinkedLru],
] as const)('%s', (_name, Lru) => {
  it('đẩy key lâu nhất chưa dùng ra', () => {
    const lru = new Lru<string, number>({ max: 2 });
    lru.set('a', 1).set('b', 2);
    lru.get('a');
    lru.set('c', 3);
    expect(lru.keys()).toEqual(['a', 'c']);
  });

  it('cập nhật giá trị cũng tính là dùng tới', () => {
    const lru = new Lru<string, number>({ max: 3 });
    lru.set('a', 1).set('b', 1).set('c', 1);
    lru.set('a', 2);
    lru.set('d', 1);
    expect(lru.keys()).toEqual(['c', 'a', 'd']);
  });

  it('không đẩy key bị ghim, báo key bị đẩy', () => {
    const evicted: string[] = [];
    const lru = new Lru<string, number>({ max: 1, isPinned: (k) => k === 'a', onEvict: (k) => evicted.push(k) });
    lru.set('a', 1).set('b', 1);
    expect(lru.keys()).toEqual(['a']);
    expect(evicted).toEqual(['b']);
  });
});

it('memoizeLru: lần trúng cũng đưa lên mới nhất', () => {
  let calls = 0;
  const double = memoizeLru((x: number) => (calls++, x * 2), { max: 2 });
  [1, 2, 1, 3, 1, 2].forEach((x) => double(x));
  expect(calls).toBe(4); // FIFO như memoize của Apple sẽ là 5
});

#So với thư viện và chuẩn web

• lru-cache (isaacs) là thư viện phổ biến nhất, có TTL, giới hạn theo kích thước (không chỉ số mục), dispose khi xoá. Nó cài bằng các mảng định kiểu thay vì object cho từng node để giảm áp lực GC.
• quick-lru dùng hai Map luân phiên (thuật toán của hashlru): rất nhanh, nhưng là LRU xấp xỉ.
• Cache API của trình duyệt (caches.open) không có giới hạn theo LRU; trình duyệt chỉ xoá cả origin khi hết dung lượng. Cần LRU cho Cache API thì phải tự ghi thời điểm dùng và tự dọn (xem bài #37).

Bài này thuộc series Học từ mã nguồn các web lớn (65 bài, đọc theo thứ tự).

Code + demo: examples/web-patterns · Mở trên StackBlitz