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 использует три основных улучшения для достижения скорости и эффективности:

1. Оптимизация Проверки Хэша (Simplified and Enhanced Hash Judgment):

   • В традиционных методах проверка хэша сложна (например, через деление modulo). FastCDC упрощает процесс с помощью побитового AND (&) с маской (фильтром из бит).
   • Аналогия: Вместо проверки делимости числа на 100 используется проверка на окончание двумя нулями — это быстрее для вычислений.
   • Дополнительно: Расширяется "окно" хэша до 48 бит с нулями в маске, что обеспечивает равномерность чанков и снижает коллизии позиций.

2. Пропуск Границ для Маленьких Чанков (Sub-Minimum Chunk Cut-Point Skipping):

   • Если потенциальный чанк меньше минимального порога (например, 2 КБ), возможная граница игнорируется, и вычисление хэша продолжается.
   • Аналогия: При чтении книги конец абзаца пропускается, если абзац короче двух страниц, чтобы избежать траты времени на мелкие фрагменты.
   • Это ускоряет алгоритм, хотя может слегка снизить эффективность дедупликации (на 15%), делая некоторые чанки крупнее.

3. Нормализация Размеров Чанков (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: Как Работает Алгоритм — Пошагово

1. Подготовка: Взять буфер данных (файл как массив байт, длиной n). Установить параметры. Инициализировать хэш (fp = 0) и позицию (i = MinSize — для пропуска мелких фрагментов).

2. Проверка краёв: Если n ≤ MinSize — весь буфер считается одним чанком. Если n > MaxSize — обрезать до MaxSize. Если n < avg — установить avg = n.

3. Цикл для маленьких чанков (до avg, строгая маска):

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

4. Цикл для больших чанков (от avg до MaxSize, слабая маска):

   • Для i от avg до MaxSize-1:
     • Обновить хэш аналогично.
     • Проверить: если (fp & MaskL) == 0 — найдена граница. Вернуть i.
   • Это увеличивает частоту разбиения, предотвращая перерост.

5. Если граница не найдена: Вернуть MaxSize (принудительная граница).

6. Повтор: Применить цикл к оставшимся данным до конца файла.

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 с дедупликацией).