Implementing Change Data Capture

Объяснение алгоритма FastCDC

FastCDC представляет собой алгоритм для разбиения данных на "куски" (чанки) на основе их содержания, что позволяет экономить пространство в хранилищах. Этот метод быстрее и эффективнее традиционных подходов, таких как Rabin или Gear.

Шаг 1: Что Такое Content-Defined Chunking (CDC) и Зачем Это Нужно?

Рассмотрим большой файл, например, видео или архив. При изменении нескольких байт весь файл может восприниматься как новый, что приводит к записи дубликатов и потере места. CDC решает эту проблему: данные разбиваются на переменные куски (чанки) не по фиксированной длине (например, 8 КБ), а по содержанию. При небольших изменениях большинство чанков остаются неизменными и не требуют перезаписи.

Проблема с фиксированным разбиением (Fixed-Size Chunking): Вставка байта в начало сдвигает все чанки, и система считает весь файл новым.
Как работает базовый CDC: Производится "скольжение" окна по байтам файла, вычисляется хэш (отпечаток), и определяются "границы" чанков, где хэш соответствует условию (например, заканчивается нулями).

FastCDC является оптимизированной версией Gear-based CDC. Gear применяет быстрый хэш, но работает медленнее из-за частых проверок и неравномерных чанков. FastCDC ускоряет процесс в 3–5 раз, сохраняя высокую эффективность.

Шаг 2: Три Ключевые "Фишки" FastCDC

FastCDC использует три основных улучшения для достижения скорости и эффективности:

Оптимизация Проверки Хэша (Simplified and Enhanced Hash Judgment):
- В традиционных методах проверка хэша сложна (например, через деление modulo). FastCDC упрощает процесс с помощью побитового AND (&) с маской (фильтром из бит).
- Аналогия: Вместо проверки делимости числа на 100 используется проверка на окончание двумя нулями — это быстрее для вычислений.
- Дополнительно: Расширяется "окно" хэша до 48 бит с нулями в маске, что обеспечивает равномерность чанков и снижает коллизии позиций.
Пропуск Границ для Маленьких Чанков (Sub-Minimum Chunk Cut-Point Skipping):
- Если потенциальный чанк меньше минимального порога (например, 2 КБ), возможная граница игнорируется, и вычисление хэша продолжается.
- Аналогия: При чтении книги конец абзаца пропускается, если абзац короче двух страниц, чтобы избежать траты времени на мелкие фрагменты.
- Это ускоряет алгоритм, хотя может слегка снизить эффективность дедупликации (на 15%), делая некоторые чанки крупнее.
Нормализация Размеров Чанков (Normalized Chunking):
- Для компенсации пропусков применяются разные маски: "строгая" (MaskS, с большим количеством '1' бит — реже границы) для маленьких чанков и "слабая" (MaskL, с меньшим количеством '1' бит — чаще границы) для больших.
- Аналогия: Для маленького чанка фильтр ужесточается, чтобы позволить рост; для большого — ослабляется, чтобы timely разрезать. В результате чанки группируются вокруг идеального размера (например, 8 КБ), с распределением близким к нормальному.
- Уровень нормализации: 1–3 (количество бит для изменения в масках).

Шаг 3: Параметры — Что Настраивать?

Ожидаемый размер чанка (Expected/Average Size, avg): Обычно 8 КБ (8192 байт). Это целевой размер для нормализации.
Минимальный размер (MinSize): 2 КБ, 4 КБ или 8 КБ. Ниже этого порога проверки пропускаются.
Максимальный размер (MaxSize): 64 КБ. При достижении происходит принудительное разбиение.
Маски (Masks): Битовые фильтры. Пример для avg=8 КБ:
- MaskS (строгая): 15 бит '1' (реже срабатывает).
- MaskA (базовая): 13 бит '1'.
- MaskL (слабая): 11 бит '1'.
Gear-таблица: Массив из 256 случайных 64-битных чисел для хэша.

Шаг 4: Как Работает Алгоритм — Пошагово

Подготовка: Взять буфер данных (файл как массив байт, длиной n). Установить параметры. Инициализировать хэш (fp = 0) и позицию (i = MinSize — для пропуска мелких фрагментов).
Проверка краёв: Если n ≤ MinSize — весь буфер считается одним чанком. Если n > MaxSize — обрезать до MaxSize. Если n < avg — установить avg = n.
Цикл для маленьких чанков (до avg, строгая маска):
- Для каждой позиции i от MinSize до avg-1:
  - Обновить хэш: fp = (fp << 1) + Gear[src[i]] (сдвиг влево плюс значение из таблицы).
  - Проверить: если (fp & MaskS) == 0 — найдена граница. Вернуть i как размер чанка.
- Это способствует росту чанков, снижая частоту разбиения.
Цикл для больших чанков (от avg до MaxSize, слабая маска):
- Для i от avg до MaxSize-1:
  - Обновить хэш аналогично.
  - Проверить: если (fp & MaskL) == 0 — найдена граница. Вернуть i.
- Это увеличивает частоту разбиения, предотвращая перерост.
Если граница не найдена: Вернуть MaxSize (принудительная граница).
Повтор: Применить цикл к оставшимся данным до конца файла.

flowchart TD
    A("Начало: Входные данные, min/avg/max размеры, маски S/L") --> B{"Достигнут конец данных?"}
    B -- Да --> Z("Конец: Последний чанк")
    B -- Нет --> C("Инициализировать hash fp=0, позиция i=min")
    C --> D{"Чанк < min?"}
    D -- Да --> E("Пропустить проверку: i++, обновить hash fp = (fp << 1) + Gear[byte]")
    E --> D
    D -- Нет --> F{"Чанк < avg?"}
    F -- Да --> G("Проверить cut-point: fp & MaskS == 0?")
    G -- Да --> H("Разбить чанк на i, начать новый")
    G -- Нет --> I("i++, обновить hash")
    I --> F
    F -- Нет --> J("Проверить cut-point: fp & MaskL == 0?")
    J -- Да --> H
    J -- Нет --> K("i++, обновить hash")
    K --> L{"Чанк >= max?"}
    L -- Да --> H
    L -- Нет --> F
    H --> B

Шаг 5: Псевдокод — В Стиле Языка D

Ниже приведен псевдокод в стиле языка программирования D. Предполагается, что Gear — это готовый массив ulong[256].

ulong fastcdc(ubyte[] src, size_t n, size_t minSize, size_t maxSize, size_t normalSize, ulong maskS, ulong maskL, ulong[256] gear) {
    if (n <= minSize) return n;
    if (n > maxSize) n = maxSize;
    if (n < normalSize) normalSize = n;

    ulong fp = 0;
    size_t i = minSize;  // Пропуск мелких

    // Цикл до normalSize (строгая маска)
    while (i < normalSize) {
        fp = (fp << 1) + gear[src[i]];
        if ((fp & maskS) == 0) {
            return i;
        }
        i++;
    }

    // Цикл после (слабая маска)
    while (i < n) {
        fp = (fp << 1) + gear[src[i]];
        if ((fp & maskL) == 0) {
            return i;
        }
        i++;
    }

    return n;  // Достигнут max
}

Этот псевдокод можно использовать в цикле для обработки всего файла, собирая чанки.

Шаг 6: Пример в Действии

Предположим файл размером 20 КБ, avg=8 КБ, min=2 КБ, max=64 КБ.

Старт с i=2 КБ.
Вычисление хэша до 8 КБ с MaskS — без срабатывания, продолжение.
С 8 КБ применение MaskL — срабатывание на 10 КБ. Первый чанк: 10 КБ.
Повтор для оставшихся 10 КБ. Результат: Чанки примерно 8–16 КБ, с быстрыми вычислениями.

Шаг 7: Преимущества и Когда Использовать

Плюсы: В 3 раза быстрее Gear, в 10 раз быстрее Rabin; коэффициент дедупликации близок к оптимальному (падение менее 15%).
Минусы: Эффективность зависит от данных; пропуски могут снижать производительность для очень похожих файлов.
Применение: В системах типа IPFS, резервных копиях (Duplicati), хранилищах (S3 с дедупликацией).

11 KiB Raw Permalink Blame History Unescape Escape