系統設計

1import { sha256 } from "@noble/hashes/sha2.js";
2import { bytesToHex } from "@noble/hashes/utils.js";
3 
4const WINDOW = 16, MIN = 64, MAX = 1024;
5 
6// Cut where the sum of the last 16 bytes ends in 255 (mod 256): the cuts
7// follow the content, so an insert moves only the cuts around it.
8function chunk(data: Uint8Array): Uint8Array[] {
9  const out: Uint8Array[] = [];
10  let start = 0, sum = 0;
11  for (let i = 0; i < data.length; i++) {
12    sum += data[i];
13    if (i >= WINDOW) sum -= data[i - WINDOW];
14    const length = i + 1 - start;
15    if ((length >= MIN && sum % 256 === 255) || length >= MAX) {
16      out.push(data.subarray(start, i + 1));
17      start = i + 1;
18    }
19  }
20  if (start < data.length) out.push(data.subarray(start));
21  return out;
22}
23 
24const hashOf = (bytes: Uint8Array) => bytesToHex(sha256(bytes));
25 
26type FileMeta = { version: number; chunks: string[]; device: string };
27type Change = { path: string; version: number; device: string; account: string };
28 
29class SyncServer {
30  blocks = new Map<string, Uint8Array>();   // block store: hash -> bytes
31  files = new Map<string, FileMeta>();      // metadata database
32  queue: Change[] = [];                     // change events
33  devices = new Map<string, string>();      // device -> account
34 
35  missing(hashes: string[]): string[] {
36    return [...new Set(hashes)].filter((h) => !this.blocks.has(h));
37  }
38 
39  putBlock(bytes: Uint8Array): void {
40    this.blocks.set(hashOf(bytes), bytes);
41  }
42 
43  metadata(account: string, path: string): FileMeta | undefined {
44    return this.files.get(JSON.stringify([account, path]));
45  }
46 
47  commit(device: string, account: string, path: string, base: number, hashes: string[]) {
48    if (this.devices.get(device) !== account) throw new Error("Unknown device/account");
49    const current = this.metadata(account, path);
50    const conflict = current !== undefined && current.version !== base;
51    if (conflict) {
52      const copy = `${path} (conflicted copy from ${device})`;
53      path = copy; let suffix = 2;
54      while (this.metadata(account, path)) path = `${copy} ${suffix++}`;
55    }
56    const version = (this.metadata(account, path)?.version ?? 0) + 1;
57    this.files.set(JSON.stringify([account, path]), { version, chunks: hashes, device });
58    this.queue.push({ path, version, device, account });
59    return { path, version, conflict };
60  }
61 
62  deliver(): string[] {
63    const notices: string[] = [];
64    for (const c of this.queue.splice(0)) {
65      for (const [d, account] of this.devices) {
66        if (d !== c.device && account === c.account) notices.push(`${d} ${c.path} v${c.version}`);
67      }
68    }
69    return notices;
70  }
71}
72 
73class Device {
74  files = new Map<string, { version: number; data: Uint8Array }>();
75  blocks = new Map<string, Uint8Array>();
76  constructor(public name: string, public account: string, public server: SyncServer) {
77    server.devices.set(name, account);
78  }
79 
80  save(path: string, data: Uint8Array) {
81    const chunks = chunk(data);
82    const hashes = chunks.map(hashOf);
83    const need = new Set(this.server.missing(hashes));
84    let uploaded = 0;
85    chunks.forEach((c, i) => {
86      if (need.delete(hashes[i])) { this.server.putBlock(c); uploaded += c.length; }
87      this.blocks.set(hashes[i], c);
88    });
89    const base = this.files.get(path)?.version ?? 0;
90    const result = this.server.commit(this.name, this.account, path, base, hashes);
91    this.files.set(result.path, { version: result.version, data });
92    return { ...result, uploaded };
93  }
94 
95  pull(path: string): number {
96    const meta = this.server.metadata(this.account, path);
97    if (!meta) throw new Error("File not found in this account");
98    let downloaded = 0;
99    const parts = meta.chunks.map((h) => {
100      if (!this.blocks.has(h)) {
101        const bytes = this.server.blocks.get(h)!;
102        this.blocks.set(h, bytes);
103        downloaded += bytes.length;
104      }
105      return this.blocks.get(h)!;
106    });
107    const data = new Uint8Array(parts.reduce((n, p) => n + p.length, 0));
108    let offset = 0;
109    for (const p of parts) { data.set(p, offset); offset += p.length; }
110    this.files.set(path, { version: meta.version, data });
111    return downloaded;
112  }
113}