133 lines
11 KiB
Markdown
133 lines
11 KiB
Markdown
# 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. **Повтор**: Применить цикл к оставшимся данным до конца файла.
|
||
|
||
```mermaid
|
||
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].
|
||
|
||
```d
|
||
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 с дедупликацией).
|