О способах компактной передачи данных люди задумывались давно — еще в середине XIX века американцы Самюэль Морзе и Альфред Вейл первыми применили точки и тире для записи символов, однако код, принятый в 1948 году в качестве международного стандарта, изобрел немец Фридрих Герке, которому принадлежит идея компактности передачи. Герке использовал короткие кодовые последовательности для часто употребляемых букв и более длинные для редких. Позже, в первой половине XX века, основное внимание было сосредоточено на оптимизации передачи аналоговых сигналов, тогда в этой области работали такие выдающиеся ученые, как Генри Найквист, Клод Шеннон и Владимир Котельников.

В середине 80-х годов возобновился интерес к оптимизации хранения символьных данных, вызванный весьма скромными на тот момент размерами дисков. Попытки сократить объемы сохраняемых и передаваемых данных на корпоративном уровне известны с середины 90-х, когда была предложена свободно распространяемая утилита rsync, предназначенная для Unix-подобных систем. Свои коммерческие продукты раньше других предложили две компании: для систем хранения — Data Domain, купленная несколько лет назад корпорацией EMC, и для передачи данных по глобальным сетям — компания Riverbed.

К сегодняшнему дню сложились три основных подхода к сокращению объема хранимых символьных данных: компрессия с вариациями — без потери и с частичной, но искажающей потерей данных; хранение единственного образца (Single-Instance Storage, SIS); дедупликация. В первом случае в пределах одного файла длинные последовательности заменяются короткими, дополненными тегами, которые будут понятны программе, выполняющей декомпрессию. Известно несколько десятков так называемых программ-архиваторов, позволяющих существенно сократить размер файлов, собирать их в один файл-архив для экономии дискового пространства и сокращения трафика. Исторически первыми были PkZip, ARJ, и заметного успеха добился Евгений Рошаль из Челябинска с программой RAR. В таких программах чаще всего используют алгоритм префиксного кодирования, предложенный Дэвидом Хаффманом в 1952 году, плюс к нему добавляется множество специфических усовершенствований, внесенных каждым из авторов. В популярных форматах DVD и MP3 с потерей данных идея сжатия другая: здесь выбрасываются те фрагменты данных, которые представляются ненужными, в расчете на то, что слушатели или зрители могут не заметить этих потерь.

Международная организация по стандартизации SNIA определяет SIS как замену повторяющихся файлов или других объектов ссылками на них. Технологии SIS исключают повторное хранение одних и тех же файлов, обеспечивая возможность использования одного контента разными пользователями. Таким образом, создаются в полном смысле этого слова архивы документов и в ряде случаев удается на порядок уменьшить общий объем хранения. Идея SIS не нова — ее предпосылки удается обнаружить еще в системе Word Perfect Office, работавшей под управлением DOS, — но у нее серьезное будущее, и особенно в контексте облачных систем хранения данных, для сокращения используемого дискового пространства и трафика.

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

Имеется несколько основных подходов к дедупликации. Все они за исключением одного попадают в категорию hash based — «нарезки» файлов данных на блоки (ломти, chunks) с последующим присвоением каждому из них собственного хеш-кода. Уникальный метод, не использующий хеширование, был разработан израильской компанией Diligent и заключается в распознавании образов в данных. Технологию дедупликации с хешированием реализуют среди прочих компании EMC, NetApp, FalconStor, HP и Quantum, расходясь на три направления по способу деления на блоки: блоки фиксированной, переменной длины, а также промежуточные паллиативные решения. Блоки дедупликации не имеют прямого отношения к физическим или логическим блокам дисков, однако с точки зрения работы с устройствами удобнее, если эти блоки будут кратны ломтям нарезки, поэтому во многих случаях предпочтение отдается делению на блоки фиксированной длины. Описанные далее методы обычно реализуются аппаратно-программными средствами и доступны пользователям в виде специализированных машин (appliance).

Общим для всех трех случаев служит то, что каждый блок хешируется — ему назначается уникальный хеш-код, или просто хеш. При сохранении производится проверка хешей на совпадение, и если вновь вычисленный равен уже существующему, то вместо такого блока записывается ссылка на его эквивалент. Преобразования входного массива данных произвольной длины в выходную строку фиксированной длины называются хеш-функциями или функциями свертки. Технология хеширования проста и удобна, но ей присуща одна врожденное слабость, от которой теоретически невозможно избавиться. Если двум строкам присвоены разные хеш-коды, то гарантированно, что эти строки различаются, но если у двух строк хеш-коды одинаковые, то строки с большой вероятностью совпадают, однако нет стопроцентной гарантии их тождественности. То есть остается незначительная возможность коллизии — ситуации, когда два разных блока получат один и тот же хеш со всеми вытекающими отсюда неприятными последствиями, например при попытке восстановить сохраненные данные. Однако вероятность коллизии очень мала, и при использовании алгоритма SHA 1 (Secure Hash Algorithm 1) размер хеша составляет 160 битов, в таком случае на системе хранения емкостью 16 Пбайт вероятность коллизии составляет 10-24. Но еще есть и другая, преодолимая проблема — сложность оптимизации разделения файла на блоки.

Проще всего «нарезать» файл данных на равные порции (Fixed-Block Deduplication), и обычно размер блока выбирается заранее, в пределах от 4 до 64 Кбайт (в большую или меньшую сторону — определяется природой данных). Вычисление хешей для таких блоков не требует больших процессорных ресурсов — в этом очевидное достоинство фиксированного подхода. К тому же проще происходит соотнесение с логическими блоками устройств, проще индексация и репликация. Казалось бы, все хорошо, но и тут есть свои проблемы. Оказывается, что при любой попытке внести изменения в файл ранее созданные деления на блоки «поплывут» и всю работу по хешированию придется выполнять заново. Эту неизбежную в процессе работы ситуацию называют проблемой сдвига данных.

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

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

Специалисты из компании Arkeia тоже нашли компромисс между переменным и фиксированным делением, но иной: технология Progressive Deduplication, которую изначально разрабатывала компания Kadena, приобретенная Arkeia в 2009 году, уходит корнями в утилиту rsync и имеет много общего с приемом, известным как «скользящее окно» (sliding window). В Kadena этот метод так и назывался — fixed-length, sliding window. Уплотняемый файл просматривается окном, размер которого выбирается в соответствии с природой файла, то есть для изображений оно шире, а для таблиц баз данных — уже. Если обнаруживается ранее известное окно, то оно пропускается необработанным, а для нового считается новый кеш.

Упомянутые слабости отсутствуют в продуктах серии IBM ProtecTier, построенных по технологии HyperFactor, которая разработана компанией Diligent, в 2009 году приобретенной IBM. Отметим, что HyperFactor — это полностью программная технология, которая может работать на любом Linux-сервере и, в отличие от конкурентов, не нуждается в специализированных машинах. Все используемые для дедупликации метаданные и индексы хранятся непосредственно в оперативной памяти этого сервера, что обеспечивает высокое быстродействие и возможность для масштабирования в широких пределах. Для систем управления резервным копированием (Symantec NetBackup, IBM Tivoli Storage Manager, EMC Legato Networker и др.) ProtecTier представляется как обычный накопитель. Работа HyperFactor с выходными данными начинается с их анализа и поиска схожести с уже имеющимися в репозитории данными. Если обнаружено совпадение, то дальше начинается побайтовое сравнение с содержимым репозитория. При обнаружении нового компонента данных он заносится в репозиторий, после этого индекс обновляется, создается таблица содержания, основа метаданных. Несмотря на кажущуюся сложность поддерживается скорость обработки данных от 200 Мбайт/с на один узел. Индекс требуется только во время накопления данных, для восстановления используется асимметричное решение, основанное на прямом доступе к памяти по методу списка рассеяния/сборки (scatter-gather), оптимизирующему доступ к адресам, не являющимся непрерывными.

Качество дедупликации DR (Deduplication Ratio) измеряется отношением исходного объема к результату. Однако надо иметь в виду, что это отношение не вполне адекватно отражает реальный результат, на самом деле не стоит бороться за избыточно большое значение. Сравним сохранение 1 Тбайта с отношениями 10:1 и 20:1. В первом случае вместо исходных 1024 Гбайт приходится хранить 102,4, а во втором — 51,2. Разница не столь велика, и не всегда за нее стоит биться. Значение DR на практике зависит не только от использованных алгоритмов, но и от охвата данных: если копируется один уникальный набор, то в нем повторений, естественно, меньше, а если множество близких — то больше. Есть данные, дедупликация которых не дает заметных результатов, — их называют 3М (Media, Mother Nature и Mystery). Медийные файлы в форматах mp3, jpg и других по определению уже компрессированы, а данные научных наблюдений или экспериментов требуют более тонких аналитических методов. Зашифрованные данные, и в этом суть криптографии, тоже на первый взгляд кажутся случайными наборами, в них нет каких-то схожих фрагментов.