CDCSync.js

import FastCDC from './FastCDC.js';
import CDCStore from './CDCStore.js';
import CDCManifest from './CDCManifest.js';

/**
 * Content-defined delta sync — dedup-friendly building block used by `DoubleSync`.
 *
 * High-level protocol between a *receiver* (has old data + a CAS of past chunks) and a
 * *sender* (has new data):
 *
 *   1. Sender splits new data into content-defined chunks, hashes each one, and emits a
 *      manifest: an ordered list of `(hash, length)` entries describing the new bytes.
 *
 *   2. Receiver compares manifest hashes against its local `CDCStore`. The missing
 *      hashes are the only bytes that actually need to cross the wire.
 *
 *   3. Sender transmits just the missing chunks. Receiver inserts them into its store.
 *
 *   4. Receiver reconstructs the new data by concatenating store chunks in manifest order.
 *
 * The killer property: dedup is automatic and cross-file. If the same 8KB chunk appears
 * in 50 different files, it's stored once and transferred once. Inserting one byte at the
 * start of a file only changes the chunk surrounding the insertion — every other chunk
 * keeps its identity, so its hash matches and no bytes are transferred for it.
 *
 * @example
 * const cdc = new CDCSync({ avgSize: 8192 });
 *
 * // Sender side
 * const { manifest, chunks } = cdc.split(newData);
 *
 * // Receiver side
 * const receiverStore = new CDCStore();
 * // ... (receiver has accumulated chunks over time)
 * const missing = cdc.missingChunks({ manifest, store: receiverStore });
 *
 * // Sender packages the missing chunks; receiver inserts them into its store:
 * for (const { hash, bytes } of senderProvidesMissing(missing, chunks)) {
 *     receiverStore.putWithHash(hash, bytes);
 * }
 *
 * // Reconstruct
 * const rebuilt = cdc.reconstruct({ manifest, store: receiverStore });
 */
export default class CDCSync {
    /**
     * @param {Object} [params]
     * @param {number} [params.avgSize=8192] - target average chunk size in bytes (power of 2)
     * @param {number} [params.minSize]      - lower clamp; defaults to avgSize/4
     * @param {number} [params.maxSize]      - upper clamp; defaults to avgSize*8
     */
    constructor(params = {}) {
        /** @type {FastCDC} */
        this.cdc = new FastCDC(params);
    }

    get avgSize() { return this.cdc.avgSize; }
    get minSize() { return this.cdc.minSize; }
    get maxSize() { return this.cdc.maxSize; }

    /**
     * Split `data` into content-defined chunks, hash each chunk, and produce a manifest
     * along with the raw chunks themselves.
     *
     * The returned `chunks` array is in manifest order — `chunks[i]` corresponds to
     * the `i`th manifest entry. `bytes` is a zero-copy `Uint8Array` view into `data`.
     *
     * @param {Uint8Array} data
     * @returns {{manifest: Uint8Array, chunks: Array<{hash: Uint8Array, bytes: Uint8Array}>}}
     */
    split(data) {
        if (!(data instanceof Uint8Array)) throw new Error('CDCSync.split: data must be Uint8Array');

        const chunks = [];
        const entries = [];
        for (const { offset, length } of this.cdc.chunks(data)) {
            const bytes = data.subarray(offset, offset + length);
            const hash = CDCStore.hashOf(bytes);
            entries.push({ hash, length });
            chunks.push({ hash, bytes });
        }

        const manifest = CDCManifest.encode({ entries });
        return { manifest, chunks };
    }

    /**
     * Convenience: split `data`, insert every chunk into `store`, and return the manifest.
     * Use this when the sender is also the local store for those chunks (e.g. you're
     * snapshotting your own data over time and want to dedup against past snapshots).
     *
     * @param {Object} params
     * @param {Uint8Array} params.data
     * @param {CDCStore} params.store
     * @returns {Uint8Array} the manifest document
     */
    splitInto({ data, store }) {
        const { manifest, chunks } = this.split(data);
        for (const { hash, bytes } of chunks) {
            store.putWithHash(hash, bytes);
        }
        return manifest;
    }

    /**
     * Inspect a manifest and return the list of chunk hashes the receiver's store does
     * NOT yet have — i.e. the bytes that need to actually cross the wire.
     *
     * Order matches manifest order. Duplicates within the manifest are deduplicated in
     * the returned list (the same chunk only needs to be transferred once even if it
     * appears multiple times in the file).
     *
     * @param {Object} params
     * @param {Uint8Array|CDCManifest} params.manifest
     * @param {CDCStore} params.store
     * @returns {Array<{hash: Uint8Array, length: number}>}
     */
    missingChunks({ manifest, store }) {
        const m = manifest instanceof CDCManifest ? manifest : new CDCManifest(manifest);

        /** @type {Set<string>} */
        const seen = new Set();
        /** @type {Array<{hash: Uint8Array, length: number}>} */
        const missing = [];

        for (const { hash, length } of m.entries()) {
            const key = CDCStore.hashToHex(hash);
            if (seen.has(key)) continue;
            if (store.has(hash)) continue;
            seen.add(key);
            missing.push({ hash: hash.slice(), length });
        }
        return missing;
    }

    /**
     * Reconstruct the original bytes by concatenating `store` chunks in manifest order.
     *
     * @param {Object} params
     * @param {Uint8Array|CDCManifest} params.manifest
     * @param {CDCStore} params.store - must contain every chunk referenced by the manifest
     * @returns {Uint8Array}
     * @throws {Error} if a referenced chunk is missing or its actual length differs from
     *                 the manifest entry (corruption check)
     */
    reconstruct({ manifest, store }) {
        const m = manifest instanceof CDCManifest ? manifest : new CDCManifest(manifest);

        const out = new Uint8Array(Number(m.totalLength));
        let cur = 0;
        for (const { hash, length } of m.entries()) {
            const bytes = store.get(hash);
            if (!bytes) {
                throw new Error(`CDCSync.reconstruct: missing chunk ${CDCStore.hashToHex(hash)}`);
            }
            if (bytes.length !== length) {
                throw new Error(
                    `CDCSync.reconstruct: chunk ${CDCStore.hashToHex(hash)} length mismatch (` +
                    `manifest=${length}, store=${bytes.length})`,
                );
            }
            out.set(bytes, cur);
            cur += length;
        }
        if (cur !== out.length) {
            throw new Error(`CDCSync.reconstruct: rebuilt ${cur} bytes, expected ${out.length}`);
        }
        return out;
    }
}