Дедупликация

Дедупликация (от англ. deduplication — удаление дубликатов) — это процесс устранения избыточных копий данных с целью экономии дискового пространства, повышения эффективности хранения и снижения затрат на резервное копирование. В вычислительной технике дедупликация чаще всего применяется в системах хранения данных (СХД), файловых системах, базах данных и облачных сервисах. В отличие от сжатия, которое уменьшает размер данных за счёт перекодирования, дедупликация удаляет идентичные блоки или файлы, заменяя их ссылками на единственный экземпляр.

Принцип работы

Основная идея дедупликации заключается в том, что в массиве данных (например, при многократном резервном копировании одной и той же операционной системы) значительная часть информации повторяется. Вместо того чтобы хранить несколько копий одного и того же файла, система сохраняет только один экземпляр, а остальные копии заменяются ссылками (указателями) на него. При чтении данных система по ссылкам восстанавливает исходную структуру, подставляя уникальный блок на место каждой ссылки.

Технически процесс включает три этапа:

1. Разбиение — данные делятся на блоки фиксированного или переменного размера.
2. Хеширование — для каждого блока вычисляется криптографический хеш (например, SHA-1, SHA-256 или MD5).
3. Сравнение — хеши новых блоков сравниваются с хешами уже сохранённых блоков. Если хеш совпадает, блок считается дубликатом и не записывается.

Современные алгоритмы дедупликации также используют так называемое «слепое» сравнение (побитовое) для исключения коллизий хешей, хотя вероятность коллизии при использовании SHA-256 пренебрежимо мала.

Виды дедупликации

По уровню обработки

• Файловая (single-instance storage) — удаление дубликатов целых файлов. Система сравнивает файлы по имени, размеру или хешу и хранит только одну копию. Простейший и наименее эффективный метод, так как не учитывает частичное совпадение данных внутри файлов.
• Блочная — данные разбиваются на блоки (обычно от 4 до 64 КБ), и дубликаты ищутся на уровне блоков. Более эффективна, чем файловая, так как позволяет находить повторяющиеся фрагменты внутри разных файлов (например, одинаковые заголовки в разных документах).
• Байтовая (контентно-адресуемая) — разбиение на блоки переменного размера на основе содержимого (Content-Defined Chunking, CDC). Позволяет выявлять дубликаты даже при сдвиге данных (например, при добавлении строки в начало документа). Наиболее ресурсоёмкий, но и самый точный метод.

По времени выполнения

• Инлайн-дедупликация (inline) — выполняется в момент записи данных на диск. Данные проверяются на дубликаты до того, как будут записаны. Требует высокой производительности процессора и памяти, но сразу экономит место.
• Постпроцесс-дедупликация (post-process) — данные сначала записываются в исходном виде, а затем фоновый процесс анализирует хранилище и удаляет дубликаты. Меньше нагружает систему записи, но временно занимает больше места.

По масштабу

• Локальная — выполняется в пределах одного устройства или файловой системы.
• Глобальная — охватывает всё хранилище, включая несколько серверов и узлов. Используется в крупных дата-центрах и облачных платформах.

Применение

Резервное копирование

Дедупликация наиболее широко применяется в системах резервного копирования (backup). При ежедневном копировании одних и тех же данных (например, баз данных или образов виртуальных машин) объём дублирующейся информации может достигать 80–95%. Использование дедупликации позволяет сократить требуемое дисковое пространство в 10–20 раз, а также уменьшить трафик при передаче данных по сети.

Системы хранения данных (СХД)

Многие современные СХД (например, от компаний NetApp, Dell EMC, Hewlett Packard Enterprise) включают встроенную дедупликацию. Она применяется как для первичных данных (активных файлов), так и для архивов. В облачных хранилищах (Amazon S3, Google Cloud Storage, Microsoft Azure) дедупликация используется на уровне провайдера для снижения затрат на хранение.

Виртуализация

В средах виртуализации (VMware vSphere, Microsoft Hyper-V) дедупликация позволяет эффективно хранить образы виртуальных машин. Поскольку множество виртуальных машин могут использовать одну и ту же операционную систему и приложения, дедупликация блоков даёт значительную экономию места.

Базы данных

Некоторые СУБД (например, Oracle, PostgreSQL с расширениями) поддерживают дедупликацию на уровне таблиц или индексов. Это особенно полезно для систем, хранящих много повторяющихся записей (логи, телеметрия).

Преимущества и недостатки

Преимущества

• Экономия дискового пространства — основной эффект. В типовых сценариях резервного копирования экономия составляет от 50% до 95%.
• Снижение затрат — меньшее количество дисков и лент, меньшее энергопотребление и охлаждение.
• Ускорение резервного копирования — за счёт сокращения объёма передаваемых данных.
• Повышение эффективности сетевого трафика — при удалённом резервном копировании (WAN-оптимизация).

Недостатки

• Нагрузка на процессор — вычисление хешей и сравнение блоков требует значительных вычислительных ресурсов.
• Задержки при записи — при инлайн-дедупликации возможна задержка записи данных.
• Фрагментация — при удалении дубликатов данные могут стать фрагментированными, что снижает скорость чтения.
• Риск коллизий хешей — хотя вероятность крайне мала, теоретически возможно совпадение хешей для разных блоков, что приведёт к потере данных. Современные системы используют двойную проверку (хеш + побитовое сравнение).

Интересные факты

• Термин «дедупликация» вошёл в широкий обиход в середине 2000-х годов, когда компании Data Domain и NetApp начали массово внедрять эту технологию в системы резервного копирования.
• В 2010-х годах дедупликация стала стандартной функцией в большинстве enterprise-СХД и облачных платформ.
• Алгоритм Content-Defined Chunking (CDC) был впервые описан в 1990-х годах и до сих пор остаётся основой для многих систем дедупликации.
• В некоторых системах (например, ZFS) дедупликация может быть включена на уровне файловой системы, но требует большого объёма оперативной памяти для хранения таблицы хешей.

Критика и ограничения

Основная критика дедупликации связана с её ресурсоёмкостью. Для эффективной работы требуется значительный объём оперативной памяти (для хранения хеш-таблицы) и производительный процессор. В системах с высокой нагрузкой на запись (например, OLTP-базы данных) дедупликация может снижать производительность. Кроме того, дедупликация неэффективна для уже сжатых данных (JPEG, MP4, ZIP), так как в них практически нет повторяющихся блоков.

Источники

• De-duplication in storage systems: A survey / M. Fu, D. Feng, Y. Hua, et al. — ACM Computing Surveys, 2012.
• Data Domain: A High-Performance Deduplication File System / B. Zhu, K. Li, H. Patterson. — Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP), 2007.
• ZFS: The Last Word in File Systems / J. Bonwick, M. Ahrens, et al. — Sun Microsystems, 2005.
• ГОСТ Р ИСО/МЭК 27040-2016. Информационная технология. Методы и средства обеспечения безопасности. Безопасность систем хранения данных.