angle-left

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

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

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

Коэффициент дедупликации — отношение выходного объема дедуплицированных даных (с устранением блоковой избыточности) к изначальному объему входных (недедуплицируемых данных).

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

Дедупликацию эффективно применяют в тех местах, где оперируют с большими объемами хранящихся данных. Наиболее часто она применяется в области хранения резервных копий (ввиду наличия большой избыточности, связанной с тем, что содержимое резервных копий одного и того же обьекта в большой степени идентично) и области виртуализации (избыточность возникает по причине большой идентичности образов виртуальных машин). В качестве конкретного примера приведу продукт Symantec NetBackup (включает компонент NetBackup Deduplication, позволяет производить дедупликацию над данными резервных копий).

Существуют два подхода обработки данных в процессе дедупликации :

  1.  Post-process метод 
  2.  In-line метод 

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


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

Надо понимать, что каждый из этих методов целесообразней использовать в определенных условиях, в которых каждый из них проявляет в свои особенности и достоинства. Например : in-line в процессе поступления данных на устройства, post-process при дедуплицировании уже записанных (существующих) данных на носителе.


Технически сверка блока данных осуществляется вычислением хеш-функций поданному блоку, и поиск на совпадение результата вычисленного хеша в существующем хранилище хешей. Ввиду того, что вероятность коллизий крайне мала (например для алгоритма SHA-256 ~ 2^-256), она не нулевая, значит она непременно когда-нибудь случится. Для предотвращения коллизий, после совпадения по результату хеша происходит блочное сравнение блоков. В случае коллизии для двух разных блоков будет один хеш, и один из блоков, который был обнаружен позже не будет обладать значением хеша, вследствии чего будет возникать избыточность при обнаружении идентичного блока. Решение данной проблемы заключается в использовании нескольких хеш-функций для каждого блока.

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