Дедублікація

Дедублікація (лат. deduplicatio — усунення дублів) — це процес, який направлений на виявлення та заміну цілком однакових за змістом блоків інформації одним їхнім примірником. Набув розповсюдження насамперед у зв'язку із розвитком резервного копіювання[1].

В дослідах виявилось, що резервні копії мають багато однакових областей даних. Обумовлено тим, що дані змінюються не по всьому масиву даних, які підлягають резервному копіюванні. Звідси, стає зрозумілим, що резервні копії мають однакові блоки даних, які можна замінити посиланням на раніше записані блоки даних.

В дедублікації весь масив даних поділяється на блоки фіксованого розміру. При збереженні наступного блоку процес перевіряє чи є вже в сховище такий самий:

• якщо є, то зберігається посилання на раніше збережений блок, замість самого блоку.
• якщо не має, то зберігається сам блок.

Процес отримання даних із Сховища, яке організовано таким чином, зводиться до отримання відповідного блоку даних.

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

Недоліком цього способу збереження даних є його висока вразливість від пошкодження даних — пошкоджений блок даних призведе до пошкодження й неможливості відновлення всіх файлів де він є.

Дедублікація використовується в:

• файлових системах, наприклад, ZFS[2], IPFS[3];
• системах збереження даних — дозволяє більш ефективно збергіати дані;
• системах віртуалізації — дозволяє прискорити операції збереження та відновлення snapshot-ів, зменшити потрібний обсяг даних для збереження станів віртуальних машин;
• системах передачі інформації — дозволяє за рахунок зменшення обсягу надсилаємих даних зменшити час на їх передачу.

Розрізняють дедублікацію на рівні:

• файлів;
• блоків;
• байтів.

Практична недоцільність дедублікації на байтовому рівні була доведена в дослідах при проектуванні файлової системи ZFS[4]. Дещо схожа ідея дедублікація на байтовому рівні втілена в алгоритмі стиснення RLE.

Дедублікацію на файловому рівні виконують багато утиліт, відомим прикладом є GNU-утиліта fdupes. Вона замінює винайдені однакові файли посиланням на один примірник.

На блочному рівні, для порівняння блоків між собою використовують наступні методи[5]:

• порівняння хеш сум (таких як, SHA-1, SHA-256, MD5) блоків між собою;
• побайтове порівняння;
• хешування алгоритмом Флетчера (fletcher4) з побайтовою верифікацією.