《互联网产品的客户端架构·内容、社交与实时互动》2.2 去重、插入与位置保持

// file: src/feed/window.ts
// tier: L2
// verify: node --test --test-concurrency=1 test/feed/window.test.ts
import type { ContentItem } from "../core/content-model.ts";

export interface WindowPage {
  items: ContentItem[];
  nextCursor: string | null;
}

export interface ApplyResult {
  added: number;
  duplicates: number;
  stale: boolean;
  anchorIndex: number;
}

export type Clock = () => number;

export class FeedWindow {
  #items: ContentItem[] = [];
  #seen = new Set<string>();
  #anchorId: string | null = null;
  #cursor: string | null = null;
  #epoch = 0;
  #lastAppliedAt = Number.NEGATIVE_INFINITY;
  #limit: number;
  #now: Clock;

  constructor(now: Clock = () => Date.now(), limit = 100) {
    if (!Number.isInteger(limit) || limit < 1) throw new Error("limit 必须是正整数");
    this.#now = now;
    this.#limit = limit;
  }

  get size(): number {
    return this.#items.length;
  }

  get anchorId(): string | null {
    return this.#anchorId;
  }

  get cursor(): string | null {
    return this.#cursor;
  }

  get lastAppliedAt(): number {
    return this.#lastAppliedAt;
  }

  ids(): string[] {
    return this.#items.map((item) => item.id);
  }

  indexOf(id: string): number {
    return this.#items.findIndex((item) => item.id === id);
  }

  markAnchor(id: string): boolean {
    if (!this.#seen.has(id)) return false;
    this.#anchorId = id;
    return true;
  }

  // 每次刷新开始递增 epoch；旧 epoch 的响应即使后到也会被丢弃。
  beginRefresh(): number {
    this.#epoch += 1;
    return this.#epoch;
  }

  applyRefresh(epoch: number, page: WindowPage): ApplyResult {
    if (epoch !== this.#epoch) {
      const duplicates = page.items.filter((item) => this.#seen.has(item.id)).length;
      return this.#result(0, duplicates, true);
    }
    const fresh = this.#takeFresh(page.items);
    this.#items = [...fresh, ...this.#items].sort((a, b) => this.#compare(a, b));
    this.#trimTail();
    this.#cursor = page.nextCursor;
    this.#lastAppliedAt = this.#now();
    return this.#result(fresh.length, page.items.length - fresh.length, false);
  }

  appendOlder(page: WindowPage): ApplyResult {
    const fresh = this.#takeFresh(page.items);
    // 服务端页内已经有序，追加即可；不重排，避免把旧页内容插回顶部。
    this.#items = [...this.#items, ...fresh];
    this.#trimHead();
    this.#cursor = page.nextCursor;
    this.#lastAppliedAt = this.#now();
    return this.#result(fresh.length, page.items.length - fresh.length, false);
  }

  insertLive(items: ContentItem[]): ApplyResult {
    const fresh = this.#takeFresh(items);
    if (fresh.length > 0) {
      this.#items = [...fresh, ...this.#items].sort((a, b) => this.#compare(a, b));
      this.#trimTail();
      this.#lastAppliedAt = this.#now();
    }
    return this.#result(fresh.length, items.length - fresh.length, false);
  }

  #compare(a: ContentItem, b: ContentItem): number {
    if (a.createdAt !== b.createdAt) return b.createdAt - a.createdAt;
    return b.id.localeCompare(a.id);
  }

  #takeFresh(items: ContentItem[]): ContentItem[] {
    const fresh: ContentItem[] = [];
    for (const item of items) {
      if (this.#seen.has(item.id)) continue;
      this.#seen.add(item.id);
      fresh.push(item);
    }
    return fresh;
  }

  // 滑得更深时从头部释放内存：丢掉最早加载的那批，滚回顶部可以重新拉。
  #trimHead(): void {
    while (this.#items.length > this.#limit) {
      const victim = this.#items.findIndex((item) => item.id !== this.#anchorId);
      if (victim === -1) break;
      this.#dropAt(victim);
    }
  }

  // 刷新或实时插入后从尾部释放内存：保留最新内容，丢掉最旧的。
  #trimTail(): void {
    while (this.#items.length > this.#limit) {
      let victim = -1;
      for (let i = this.#items.length - 1; i >= 0; i -= 1) {
        if (this.#items[i].id !== this.#anchorId) {
          victim = i;
          break;
        }
      }
      if (victim === -1) break;
      this.#dropAt(victim);
    }
  }

  // 淘汰条目时必须同时移出去重集合，否则它再次出现时会被误判为重复。
  #dropAt(index: number): void {
    const [removed] = this.#items.splice(index, 1);
    this.#seen.delete(removed.id);
  }

  #result(added: number, duplicates: number, stale: boolean): ApplyResult {
    return { added, duplicates, stale, anchorIndex: this.indexOf(this.#anchorId ?? "") };
  }
}

$ node --test --test-concurrency=1 test/feed/window.test.ts
✔ 旧 epoch 的刷新响应后到时被丢弃 (1.046375ms)
✔ 刷新把新内容插到顶部并保持锚点 id (0.172458ms)
✔ 实时插入去重，锚点下标随之上移但内容不变 (0.575833ms)
✔ 加载更旧一页跳过已见条目并更新游标 (0.187584ms)
✔ 超过上限从头部淘汰，并允许它重新出现 (0.211792ms)
✔ 锚点是被淘汰的最旧条目时也不被移除 (0.105666ms)
✔ 未加载过的 id 不能设为锚点 (0.071041ms)
✔ 实时插入的同一毫秒条目按 id 倒序稳定排列 (8.29925ms)
ℹ tests 8
ℹ suites 0
ℹ pass 8
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 125.138208