《移动游戏产品的架构·网络、资源与热更新》9.2 分包与按需下载的调度

// file: src/resource/on-demand.ts
// tier: L1
// verify: node --test test/resource/on-demand.test.ts

export type Priority = "blocking" | "prefetch" | "idle";

export interface DownloadRequest {
  readonly id: string;
  readonly bytes: number;
  readonly priority: Priority;
  readonly dependsOn: readonly string[];
  readonly deadlineMs: number;
  readonly cellularAllowed: boolean;
}

export interface ScheduledItem {
  readonly id: string;
  readonly priority: Priority;
  readonly wave: number;
  readonly startMs: number;
  readonly finishMs: number;
  readonly missedDeadline: boolean;
}

export interface DeferredItem {
  readonly id: string;
  readonly reason: "cellular-policy" | "dependency-deferred";
}

export interface DownloadSchedule {
  readonly network: "wifi" | "cellular";
  readonly items: readonly ScheduledItem[];
  readonly deferred: readonly DeferredItem[];
  readonly waves: readonly (readonly string[])[];
  readonly totalBytes: number;
  readonly totalMs: number;
  readonly missed: readonly string[];
}

export const MB = 1024 * 1024;

const PRIORITY_RANK: Record<Priority, number> = {
  blocking: 0,
  prefetch: 1,
  idle: 2,
};

function stageRequests(requests: readonly DownloadRequest[]): Map<string, number> {
  const byId = new Map<string, DownloadRequest>();
  for (const request of requests) {
    if (byId.has(request.id)) throw new Error(`duplicate request: ${request.id}`);
    if (!Number.isInteger(request.bytes) || request.bytes <= 0) {
      throw new Error(`invalid bytes for ${request.id}: ${request.bytes}`);
    }
    if (!Number.isInteger(request.deadlineMs) || request.deadlineMs < 0) {
      throw new Error(`invalid deadline for ${request.id}: ${request.deadlineMs}`);
    }
    byId.set(request.id, request);
  }

  const stage = new Map<string, number>();
  const visiting = new Set<string>();

  const stageOf = (id: string): number => {
    const cached = stage.get(id);
    if (cached !== undefined) return cached;
    if (visiting.has(id)) throw new Error(`dependency cycle at ${id}`);
    visiting.add(id);
    const request = byId.get(id);
    if (request === undefined) throw new Error(`unknown request: ${id}`);
    let value = 0;
    for (const dependency of request.dependsOn) {
      if (!byId.has(dependency)) {
        throw new Error(`unknown dependency: ${id} -> ${dependency}`);
      }
      value = Math.max(value, stageOf(dependency) + 1);
    }
    visiting.delete(id);
    stage.set(id, value);
    return value;
  };

  for (const request of requests) stageOf(request.id);
  return stage;
}

export function planDownloads(
  requests: readonly DownloadRequest[],
  options: {
    readonly concurrency: number;
    readonly bandwidthBps: number;
    readonly network: "wifi" | "cellular";
  },
): DownloadSchedule {
  const { concurrency, bandwidthBps, network } = options;
  if (!Number.isInteger(concurrency) || concurrency < 1) {
    throw new Error(`invalid concurrency: ${concurrency}`);
  }
  if (!Number.isFinite(bandwidthBps) || bandwidthBps <= 0) {
    throw new Error(`invalid bandwidth: ${bandwidthBps}`);
  }

  const stage = stageRequests(requests);
  const ordered = [...requests].sort(
    (a, b) => (stage.get(a.id) ?? 0) - (stage.get(b.id) ?? 0),
  );

  const deferred = new Map<string, DeferredItem>();
  const active: DownloadRequest[] = [];
  for (const request of ordered) {
    const policyBlocked =
      network === "cellular" &&
      !request.cellularAllowed &&
      request.priority !== "blocking";
    if (policyBlocked) {
      deferred.set(request.id, { id: request.id, reason: "cellular-policy" });
      continue;
    }
    const blockedBy = request.dependsOn.find((dependency) => deferred.has(dependency));
    if (blockedBy !== undefined) {
      deferred.set(request.id, { id: request.id, reason: "dependency-deferred" });
      continue;
    }
    active.push(request);
  }

  const waves: string[][] = [];
  const items: ScheduledItem[] = [];
  const finishById = new Map<string, number>();
  const maxStage = active.reduce(
    (max, request) => Math.max(max, stage.get(request.id) ?? 0),
    -1,
  );
  let clock = 0;

  for (let index = 0; index <= maxStage; index += 1) {
    const layer = active
      .filter((request) => stage.get(request.id) === index)
      .sort((a, b) => {
        const rank = PRIORITY_RANK[a.priority] - PRIORITY_RANK[b.priority];
        if (rank !== 0) return rank;
        if (a.deadlineMs !== b.deadlineMs) return a.deadlineMs - b.deadlineMs;
        if (a.bytes !== b.bytes) return b.bytes - a.bytes;
        return a.id < b.id ? -1 : a.id > b.id ? 1 : 0;
      });

    for (let offset = 0; offset < layer.length; offset += concurrency) {
      const wave = layer.slice(offset, offset + concurrency);
      const startMs = wave.reduce((max, request) => {
        let value = clock;
        for (const dependency of request.dependsOn) {
          value = Math.max(value, finishById.get(dependency) ?? 0);
        }
        return Math.max(max, value);
      }, clock);
      const share = bandwidthBps / wave.length;
      let waveEnd = startMs;

      for (const request of wave) {
        const finishMs = startMs + Math.round((request.bytes / share) * 1000);
        finishById.set(request.id, finishMs);
        waveEnd = Math.max(waveEnd, finishMs);
        items.push({
          id: request.id,
          priority: request.priority,
          wave: waves.length,
          startMs,
          finishMs,
          missedDeadline: finishMs > request.deadlineMs,
        });
      }

      waves.push(wave.map((request) => request.id));
      clock = waveEnd;
    }
  }

  const totalBytes = active.reduce((sum, request) => sum + request.bytes, 0);

  return {
    network,
    items,
    deferred: [...deferred.values()],
    waves,
    totalBytes,
    totalMs: items.reduce((max, item) => Math.max(max, item.finishMs), 0),
    missed: items
      .filter((item) => item.missedDeadline)
      .map((item) => item.id),
  };
}

export function formatSchedule(schedule: DownloadSchedule): string {
  const lines = ["request\tpriority\twave\tstart\tfinish\tstatus"];
  for (const item of schedule.items) {
    lines.push(
      `${item.id}\t${item.priority}\t${item.wave}\t${item.startMs}ms\t${item.finishMs}ms\t${item.missedDeadline ? "late" : "ok"}`,
    );
  }
  for (const item of schedule.deferred) {
    lines.push(`${item.id}\tdeferred\t-\t-\t-\t${item.reason}`);
  }
  lines.push(
    `summary\t${schedule.network}\twaves=${schedule.waves.length}\titems=${schedule.items.length}\tdeferred=${schedule.deferred.length}\ttotal=${schedule.totalMs}ms`,
  );
  return lines.join("\n");
}

request	priority	wave	start	finish	status
base	blocking	0	0ms	200ms	ok
idle-tip	idle	0	0ms	100ms	ok
battle	blocking	1	200ms	400ms	ok
voice	prefetch	2	400ms	800ms	ok
summary	wifi	waves=3	items=4	deferred=0	total=800ms