Дедупликация и сжатие: две концепции сокращения объема данных

По данным компании IDC, занимающейся исследованием рынка, объем данных, существующих в мире, удваивается каждые 24 месяца. При таких темпах к 2020 году объем цифровой вселенной достигнет 44 зеттабайт. Эта цифра рассчитывается путем пересчета 44 триллионов гигабайт данных, произведенных или скопированных за один год. Такое развитие событий в первую очередь влияет на методы хранения, процедуры резервного копирования и системы восстановления, которые должны быть способны переносить и обрабатывать огромные объемы данных. Концепция технического внедрения сосредоточена на сокращении физически хранимой информации, тем самым снижая затраты на управление данными. В основе этих методов лежат две концепции: сжатие данных и дедупликация. В то время как сжатие без потерь использует избыточность внутри файла для сжатия данных, алгоритмы дедупликации зеркально отображают данные в разных файлах, чтобы избежать дублирования. Поэтому основным применением дедупликации является резервное копирование данных.

Дедупликация — это процесс уменьшения объема данных, который основан на предотвращении избыточности данных в системе хранения. Для этого используется механизм дедупликации, который генерирует специальные алгоритмы для выявления и устранения избыточных файлов и блоков данных. Он может быть интегрирован в программное обеспечение для резервного копирования или аппаратное обеспечение, используемое для хранения информации, или реализован в виде промежуточного устройства.

Цель дедупликации в технологиях хранения данных — записать на энергонезависимый носитель только столько информации, сколько необходимо для того, чтобы можно было восстановить файл без потерь. Чем больше дубликатов удаляется, тем меньше становится объем данных, которые необходимо хранить или передавать. Выявление дубликатов может осуществляться на уровне файлов, например, с помощью Git или Dropbox. Однако более эффективным методом является использование алгоритмов дедупликации, которые работают на уровне подфайлов. Для этого файлы сначала разбиваются на блоки данных (чанки) и им присваиваются уникальные контрольные суммы, или хэш-значения. База данных отслеживания, в которой хранится каждая контрольная сумма, выступает в качестве центрального контролирующего органа.

Методы дедупликации на основе блоков можно разделить на две разновидности:

• Дедупликация с фиксированным размером блока: при дедупликации с фиксированным размером блока алгоритм делит файлы на участки одинаковой длины. Обычно это основано на размере кластера файла или RAID-системы (обычно 4 КБ), но иногда может быть настроено вручную. В этом случае индивидуально настроенный размер блока принимается в качестве стандартного размера для всех блоков данных.

• Дедупликация с переменным размером блока: при дедупликации с переменным размером блока, с другой стороны, конкретный стандартный размер не определяется. Вместо этого алгоритм делит данные на различные блоки, длина которых зависит от типа данных, подлежащих обработке.

Тип разделения блоков оказывает огромное влияние на эффективность дублирования данных. Это особенно заметно при последующем изменении дедуплицированных файлов.

Если блок данных с фиксированными границами блока расширяется дополнительной информацией, содержимое всех последующих блоков обычно также перемещается относительно фиксированных границ блока. Хотя изменения затрагивают только один блок данных, все последующие сегменты файла также будут классифицироваться как новые из-за изменения границ блока алгоритмом дедупликации. Если измененные байты не являются в точности кратными фиксированному размеру блока. Поскольку они сохраняются как новые переклассифицированные блоки данных, в случае резервного копирования с дедупликацией с фиксированным размером блока увеличиваются как вычислительные усилия, так и пропускная способность канала.

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

Выявление избыточных блоков основано на предположении, что блоки данных с одинаковыми хэш-значениями содержат идентичную информацию. Чтобы отфильтровать избыточные блоки, алгоритму дедупликации достаточно синхронизировать вновь вычисленные хэш-значения с базой данных отслеживания. Если он находит идентичные контрольные суммы, избыточные блоки заменяются путем определения места хранения идентичного блока данных с помощью указателя. Такой указатель занимает гораздо меньше места, чем сам блок данных. Чем больше фрагментов в файле может быть заменено указателями, тем меньше места в памяти требуется. Однако эффективность сокращения данных не может быть предсказана алгоритмами дедупликации, поскольку она сильно зависит от выходного файла и его структуры данных. Кроме того, дедупликация подходит только для незашифрованных данных. В системах шифрования намеренно избегают избыточности; это делает невозможным любое распознавание образов.

Дедупликация может осуществляться как в месте назначения хранилища, так и в источнике данных.

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

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

Целевая дедупликация — это когда процесс сокращения данных происходит вне источника данных. Механизм дедупликации либо интегрируется в аппаратный массив, либо устанавливается в качестве независимого устройства. В обоих случаях целевая дедупликация уменьшает требуемую емкость хранилища, но в отличие от дедупликации источника целевая дедупликация не влияет на объем данных, передаваемых во время резервного копирования от системы-источника к месту назначения хранения по локальной или глобальной сети. В зависимости от того, какая структура выбрана для целевой дедупликации, существует два типа целевой дедупликации: дедупликация после обработки и поточная дедупликация.

• Дедупликация после обработки: если механизм дедупликации встроен в массив, то сначала на устройстве хранения сохраняется немодифицированная версия данных резервного копирования, а затем выполняется дедупликация. Это называется постпроцессной дедупликацией. Преимущество такого вида дедупликации заключается в относительно быстрой передаче данных на устройство хранения. Однако после переноса данные не сразу становятся доступными, поскольку перед устранением избыточности необходимо завершить процесс резервного копирования. К данным на жестком диске обращаются три раза, прежде чем они становятся доступными для репликации или извлечения. Это увеличивает нагрузку на систему памяти. Кроме того, система резервного копирования должна сначала обеспечить две отдельные зоны памяти: одну для выходных данных и другую для дедуплицированных данных. Это требует гораздо больше физической памяти, чем при поточной дедупликации. В отличие от этого, дедупликация после процесса позволяет более эффективно сокращать данные на основе переменных блоков данных.

• Поточная дедупликация: если механизм дедупликации расположен перед носителем, можно удалять избыточные данные непосредственно во время передачи, еще до их записи на носитель. Это снижает пропускную способность записи и ограничивает дедупликацию блоками данных с фиксированным размером. Но это также значительно сокращает необходимый объем физической памяти на целевой системе по сравнению с дедупликацией после обработки. Кроме того, данные, которые были дедуплицированы в режиме inline, сразу же становятся доступными, например, для восстановления данных или репликации.

При сжатии данных файлы преобразуются в альтернативный формат, который является более эффективным, чем исходный. Целью этого процесса является уменьшение требуемого объема памяти, а также времени передачи данных. Подобное усиление кодирования может быть достигнуто с помощью двух различных подходов:

• Сжатие с избыточностью: в случае сжатия без потерь, основанного на сокращении избыточности, данные могут быть декомпрессированы именно после сжатия. Таким образом, входные и выходные данные идентичны. Этот вид сжатия возможен только в том случае, если файл содержит избыточную информацию.

• Сжатие без потерь: в случае сжатия с потерями для сжатия файла удаляется неактуальная информация. Это всегда сопровождается потерей данных. Исходные данные могут быть восстановлены только приблизительно после сжатия без релевантности. Данные, которые классифицируются как нерелевантные, являются произвольными. Например, при сжатии звука в формате MP3 удаляются те частотные шаблоны, которые, как предполагается, почти или совсем не слышны человеку.

Хотя сжатие на уровне системы хранения данных по существу происходит без потерь, потери данных в других областях, таких как передача изображений, видео и аудио, сознательно допускаются для уменьшения размера файла.

Как кодирование, так и декодирование требуют вычислительных затрат. Это в первую очередь зависит от используемого метода сжатия. В то время как одни методы предназначены для наиболее компактного представления выходных данных, другие направлены на сокращение требуемого времени вычислений. Поэтому выбор метода сжатия всегда зависит от требований приложения.

Например, в случае передачи видео или звука в реальном времени рекомендуется использовать максимально быстрый метод сжатия и восстановления данных. В этом случае сравнительно небольшое усиление кодирования и возможные потери качества вполне оправданы. Совсем другое дело, когда файлы предоставляются большому количеству пользователей через файловый сервер. Здесь можно допустить больше времени на сжатие, поэтому можно использовать мощный алгоритм сжатия. Это позволяет добиться высокого коэффициента усиления кодирования без потерь качества.

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

Это показано в следующем примере:

Исходный текст: ABCDEABCEEABCEE

Кодирование:  ABC = 1; EE = 2

Сжатый текст: 1DE1212

Исходный текст длиной 15 символов может быть сокращен до 7 символов при таком кодировании; выигрыш в кодировании составляет более 50%. Однако предпосылкой для такого сжатия является то, что системы кодирования и декодирования распознают кодировку.

Большинство методов сжатия без потерь повторяют либо символы, либо их комбинации в пределах одного файла. Известные методы сжатия на основе повторения включают кодирование слов и метод Лемпеля-Зива (LZ77).

• Кодирование слов: методы сжатия, основанные на кодировании слов, лучше всего подходят для текстовых файлов. Основной принцип здесь заключается в замене слов более короткими представлениями. Для этого сначала создается список, и каждому слову в файле присваивается значение. Затем весь текст может быть преобразован в числа.

Исходный текст: быть или не быть

Кодирование: to = 1; be = 2; or = 3; not = 4

Сжатый текст: 123412

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

• Метод Лемпеля-Зива: метод Лемпеля-Зива — это метод, основанный на словаре, который позволяет сжимать символьные строки на основе избыточности. Для этого алгоритм сжатия использует содержимое, которое было прочитано, как словарь, поэтому его не нужно хранить отдельно. Ссылка на идентичную символьную строку в прочитанном потоке данных осуществляется с помощью так называемой тройки, которая кодирует позицию и длину копируемой части и первого не совпадающего символа. Сопоставление выполняется буфером поиска и буфером предварительного просмотра. Если для символа нет совпадения, то тройка принимает вид (0, 0, x), где x — соответствующий символ. В следующем примере показано LZ77-кодирование слова BANANA:

Символы или строки в буфере предварительного просмотра сравниваются с символами буфера поиска, которые уже были прочитаны. Если совпадения найдены, соответствующие символы заменяются ссылающейся тройкой в буфере предварительного просмотра.

В строке 4 символы ANA заменяются тройкой (2, 3, $), что означает:

2 = Заменить текущую строку строкой, начинающейся после позиции 2 в буфере поиска (A).

3 = Заменяющая строка имеет длину 3 символа. Поскольку она длиннее, чем оставшийся буфер поиска, содержащий символы A и N, заменяющая строка повторяется (A, N и снова A).

$ = После замены больше не следует символов, сжатие завершено.

Поскольку большинство данных может быть эффективно сжато с помощью LZ77, преемники этого алгоритма — такие как LZSS — сегодня очень широко используются, включая формат файлов zip, изображения PNG и PDF.

Наряду с методами, основанными на повторении, для сжатия без потерь также используются частотные методы, такие как кодирование по длине строки или кодирование Хаффмана.

• Кодирование по длине строки: кодирование по длине строки направлено на устранение избыточности, возникающей в результате последовательности одинаковых символов. Это иллюстрируется схематическим изображением одной строки изображения черно-белой графики.

Исходные данные: WWWWWBBBBWWBBWWBBWWBBWWBWWBBWWBWWBWWB .

Явное сокращение сохраняемых данных происходит за счет повторяющихся символов, которые записываются в виде пары значений символов и количества повторений.

Сжатые данные: 5W4B2W2B6W6B3W

Кодирование по длине строки используется в сжатии изображений, но теряет эффективность тем больше, чем больше цветовых состояний необходимо закодировать. Если черно-белые контуры могут быть созданы с двумя цветовыми состояниями, то для 8-битного полутонового изображения требуется 256 оттенков серого. Поэтому вероятность того, что более двух последовательных пикселей имеют одинаковое значение цвета, значительно снижается в сложных изображениях с тонкими градациями цвета. Поскольку кодирование в примере основано на парах двузначных значений, выигрыш в кодировании возникает только тогда, когда в последовательности следуют друг за другом не менее двух одинаковых символов. Модифицированная форма кодирования по длине строки является частью известного метода сжатия изображений JPEG.

• Кодирование Хаффмана: при сжатии данных кодирование Хаффмана сначала определяет частоту всех символов, встречающихся в файле. На следующем этапе символы переводятся в битовую последовательность, в которой длина представления определяется частотой. Графически кодирование Хаффмана представляется в виде дерева, листья которого образуют кодируемые символы. Это можно продемонстрировать на примере предложения «Это пример дерева Хаффмана».

Соответствующее двоичное кодирование символа является результатом пути, ведущего от корня к листу. Здесь 0 обозначает ответвление влево, а 1 — ответвление вправо.

Для символов приведенного в качестве примера предложения можно использовать следующий код:

Если часто встречающиеся символы, такие как пробел, a и e, в данном примере кодируются только 3 битами, то для менее используемых символов, таких как r, u и x, требуется 5 бит. Для сравнения, набор символов ASCII, например, использует 7 бит на символ. Однако в совместимых с ASCII наборах символов, таких как UTF-8 или ISO 8859-1 (Latin-1), обычно добавляется восьмой бит для современных компьютеров, которые работают с 8, 16, 32 или 64 битами. Это показывает, что тексты можно сохранять гораздо компактнее с помощью кодирования Хаффмана.

Следующая двоичная последовательность показывает пример предложения «Это пример дерева Хаффмана» в соответствии с кодированием Хаффмана:

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

Для сравнения, ниже приведена последовательность битов для того же содержимого в соответствии с кодировкой ASCII, с добавленным восьмым битом (первый ноль, соответственно):

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101

С помощью кодирования Хаффмана данные могут быть уменьшены до 1/3 от их первоначального размера, в зависимости от распределения частоты символов. Однако пользователи должны учитывать, что дерево должно быть сохранено для последующего декодирования.

Кодирование Хаффмана имеет и другие применения, помимо сжатия текстовых файлов; этот метод также может использоваться в процессе сжатия изображений JPEG и в формате zip, который представляет собой комбинацию LZSS и Хаффмана.

Если сжатие данных без потерь возможно только при обнаружении избыточности в файле, то сжатие данных с потерями, основанное на уменьшении избыточности, возможно всегда — если допускается потеря данных. Основным принципом сжатия данных с потерями всегда является принятие решения о том, какая часть исходных данных является ненужной. Теоретический предел максимального сжатия можно исследовать с помощью теории искажения скорости, которая описывает взаимосвязь между сжатием и качеством сигнала.

Методы сжатия с потерями обычно адаптированы к человеческому восприятию. Например, при сжатии аудиофайла (т.е. MP3, AAC или WMA) удаляются частотные компоненты, лежащие за пределами слухового диапазона человека. Одним из распространенных примеров уменьшения нерелевантности в области изображений является метод JPEG, который сочетает в себе методы сжатия без потерь и с потерями. Последний включает, например, преобразование цвета спектра RGB в цветовую модель YCbCr, дискретное косинусное преобразование (DCT), а также квантование.

Дедупликация обычно используется компаниями для реализации процедуры резервного копирования или для оптимизации методов хранения данных в стандартных файловых системах. Это связано с тем, что системы дедупликации работают чрезвычайно эффективно, если необходимо хранить идентичные файлы.

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