Правительство Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Санкт-Петербургский государственный университет»
Кафедра информационно-аналитических систем
Гусева Мария Максимовна
Исследование возможности сжатия хеш-значений
при дедупликации данных
Бакалаврская работа
Допущена к защите
И. о. заведующего кафедрой:
к. ф.-м. н., доцент Е. Г. Михайлова
Научный руководитель:
старший преподаватель Д. В. Луцив
Рецензент:
к. ф.-м. н., доцент Е. Г. Михайлова
Санкт-Петербург
2016
Saint-Petersburg State University
Department of Analytical Information Systems
Guseva Maria
Investigation of hash value compression
in data deduplication
Bachelor's Thesis
Admitted for defence
Acting Head of Department:
Associate Professor E. G. Mikhailova
Scientific Supervisor:
D. V. Luciv
Reviewer:
Associate Professor E. G. Mikhailova
Saint-Petersburg
2016
Оглавление
Введение .........................................................................................................................................4
1.
Постановка задачи ..................................................................................................................5
2.
Предварительная работа ........................................................................................................6
3.
Идентификаторы блоков .......................................................................................................8
4.
Представление хеш-значений ...............................................................................................9
5.
Коллизия хеш-функций .......................................................................................................10
6.
Обработка коллизий .............................................................................................................11
7.
Результаты эксперимента с данными .................................................................................13
8.
Заключение ...........................................................................................................................14
Список литературы ......................................................................................................................15
3
Введение
Регулярное резервное копирование является обычной практикой для защиты от
аппаратных сбоев и ошибок пользователей. Сжатие данных перед передачей может
помочь существенно увеличить пропускную способность[1]. Действенным методом для
эффективного уменьшения передаваемых данных является дедупликация[2].
Дедупликация – это метод сжатия массива данных, при котором находятся и
удаляются дубликаты данных. Сначала данные разбиваются на блоки, по которым
считаются хеш-значения, а затем эти хеш-значения сравниваются, и только при
совпадении уже сравниваются сами блоки данных.
В процессе дедупликации генерируется большой массив хеш-значений. Например,
для блоков по 4 Кб на 4 Тб данных потребуется 8 Гб памяти только для хеш-значений
(если брать алгоритм, в котором 1 хеш занимает 8 байт). Кроме того, требуется память для
хранения идентификаторов блоков и других метаданных.
Одной из стадий дедупликации является сравнение полученных хеш-значений с
теми, которые уже хранятся в базе данных. Для ускорения процесса сравнения можно
хранить список хешей в in-memory базе данных. Но такой способ подходит не для всех
хранилищ, т.к. размер in-memory баз данных намного меньше обычных. Поэтому для
расширения границ ее использования можно применить сжатие к хеш-значениям перед
хранением.
4
1.
Постановка задачи
Цель данной работы – создание структуры данных для дедупликации для
получения существенной экономии памяти, выделенной для хранения метаданных.
Рисунок 1. Компрессия блока хеш-значений в процессе дедупликации.
Data
Hash1
Hash2
64 Кб
Hashn
List of
hashes
Описание задачи:
На вход подаются хеш-значения, полученные из данных (одно хеш-значение на
каждые 4 Кб данных). После того, как набирается 64 Кб хеш-значений, требуется
произвести компрессию. То есть компрессия производится не над одним хеш-значением, а
над блоком размера 64 Кб, состоящим из хеш-значений.
В памяти будет храниться какое-то количество блоков сжатых хеш-значений
разного размера (т.к. не все блоки одинаково поддаются сжатию). Хеш-таблица – это
структура данных, обладающая свойством амортизированной сложности доступа, которая
достигается при надлежащем подборе параметров (то есть в среднем поиск элемента
имеет временную сложность. О(1))[3]. Соответственно, хотелось бы сохранить это
свойство даже после сжатия, чтобы не приходилось разжимать всю хеш-таблицу на
стадии сравнения хеш-значений во время дедупликации. То есть требуется разжимать
только тот сжатый блок, где, вероятно, лежит такое же хеш-значение, а не все блоки.
Таким образом, требуется найти оптимальный способ хранения хеш-значений, а
также наиболее подходящий по времени работы и степени сжатия алгоритм. Кроме того,
необходимо произвести предварительное исследование возможности сжатия обычного
списка хеш-значений (грубая оценка степени сжатия).
5
2.
Предварительная работа
Перед решением поставленной задачи необходимо выяснить есть ли вообще смысл
сжимать хеш-значения. Для ответа на этот вопрос было произведено предварительное
исследование возможности сжатия (грубая оценка степени сжатия без учета времени)
обычного списка хеш-значений, полученных разными алгоритмами. Под степенью сжатия
подразумевается размер данных до сжатия, деленный на размер данных после сжатия.
Общие начальные данные:
Размер данных: ~ 85 Гб;
Количество файлов: ~ 62 600;
Размер кусков: 4 Кб;
Алгоритмы хеширования:
1. MD5[4]
2. SHA-256[5]
3. Murmur[6]
4. Adler-32[7]
Алгоритмы компрессии[8][9]:
1. bzip2
2. DEFLATE
3. DEFLATE64
4. LZMA
5. PPMd
Таблица 1. Алгоритм хеширования – MD5. Размер хеш-значений до сжатия – 617 МБ
(647 999 967 байт).
Метод сжатия
Размер после сжатия
bzip2
306 МБ
байт)
320 МБ
байт)
316 МБ
байт)
315 МБ
байт)
310 МБ
байт)
DEFLATE
DEFLATE64
LZMA
PPMd
6
(321 709 088
Степень
сжатия
49,65%
(336 216 050
51,89%
(332 074 713
51,25%
(330 878 400
51,06%
(325 753 173
50,27%
Таблица 2. Алгоритм хеширования – SHA-256. Размер хеш-значений до сжатия – 1,16 ГБ
(1 254 291 295 байт).
Метод сжатия
Размер после сжатия
bzip2
602 МБ
байт)
644 МБ
байт)
611 МБ
байт)
612 МБ
байт)
608 МБ
байт)
DEFLATE
DEFLATE64
LZMA
PPMd
(631 597 675
Степень
сжатия
50,35%
(675 293 074
53,84%
(641 635 478
51,16%
(642 071 349
51,19%
(638 177 962
50,88%
Таблица 3. Алгоритм хеширования – Murmur. Размер хеш-значений до сжатия – 217 МБ
(228 084 578 байт).
Метод сжатия
Размер после сжатия
Степень
сжатия
bzip2
84,1 МБ (88 259 695
38,70%
байт)
DEFLATE
92,4 МБ (96 975 855
42,52%
байт)
DEFLATE64
92,1 МБ (96 580 039
42,34%
байт)
LZMA
83,9 МБ (88 030 687
38,60%
байт)
PPMd
83,3 МБ (87 392 776
38,32%
байт)
Таблица 4. Алгоритм хеширования – Adler-32. Размер хеш-значений до сжатия – 235 МБ
(246 453 959 байт).
Метод сжатия
Размер после сжатия
bzip2
82,6
байт)
87,7
байт)
87,7
байт)
84,0
байт)
82,5
байт)
DEFLATE
DEFLATE64
LZMA
PPMd
МБ
(86 663 017
Степень
сжатия
35,16%
МБ
(92 063 117
37,36%
МБ
(92 038 539
37,35%
МБ
(88 153 004
35,77%
МБ
(86 585 177
35,13%
7
3.
Идентификаторы блоков
Кроме хеш-значений, нам требуется хранить некоторые метаданные: ссылки на
файлы, по которым посчитаны хеши, а также номер блока файла, по которому посчитано
данное хеш-значение. Получается, что ко всем хеш-значениям одного файла, будет
относиться одна и та же ссылка – разница будет лишь в номере блока.
Ссылки могут быть двух видов:
Путь к файлу вида "C:\...", "/mnt/..." и т.д. в виде строки;
Уникальный идентификатор файла на партиции (например, номер первого
NTFS extent (Microsoft Windows)[10] или inode (UNIX-системы)[11]);
Рассмотрим ссылки второго вида, т.к. они являются шестнадцатеричными числами,
которые и до, и после сжатия имеют меньший объем по сравнению с ссылками первого
вида. Проверим, насколько они поддаются сжатию.
Таблица 5. Степень сжатия ссылок – уникальных идентификаторов файла на партиции.
Метод сжатия
bzip2
DEFLATE
DEFLATE64
LZMA
PPMd
Степень сжатия
32,16%
34,25%
34,25%
33,12%
31,89%
8
4.
Представление хеш-значений
Перед тем, как сжимать хеш-значения, можно представить их в более удобном и
компактном для нас виде. Можно разделить каждое хеш-значение на несколько частей
фиксированного размера, а затем представлять список хеш-значений в виде дерева без
повторов. То есть при совпадении одной части у нескольких хешей, она записывается
лишь один раз, а остальные части этих хешей станут ее потомками.
Допустим, мы имеем 128-битную хеш-функцию (рисунок 2). Соответственно,
каждое хеш-значение состоит из 128 бит, что равно 32 байтам. Предлагается разделить
каждый хеш на три части (количество уровней дерева может варьироваться, как и размер
частей): 16 байт, 8 байт и 8 байт. Далее у каждого узла сохраняются лишь уникальные
потомки.
Рисунок 2. Представление списка хеш-значений 128-битной хеш- функции в виде
дерева без повторов.
24 … 31
…
16 … 23
0 … 15
16 … 23
…
К примеру, если взять 128-битную хеш-функцию MD5 и представить ее в виде
такого дерева (2 уровня: 8 байт и 24 байта), то для 6 миллионов хешей экономия места
составит 0,4% лишь на том, что мы по-другому представили хеш-таблицу. Стоит
отметить, что этот процент будет расти в зависимости от количества хеш-значений – при
увеличении количества хеш-значений растет количество повторов их частей.
9
5.
Коллизия хеш-функций
В хеш-функциях, которые возвращают хеш-значение постоянной длины, коллизий
невозможно полностью избежать, поскольку хотя бы для одного значения хеш-функции
соответствующее ему множество входных данных будет бесконечно, и любые два набора
данных из этого множества образуют коллизию.
Оценим вероятность возникновения коллизий при дедупликации. Для удобства
будем считать, что коллизии не вызываются искусственно, а значит, можно считать, что
значения хеш-функции распределены равномерно. Пусть N – количество блоков в
хранилище (напомним, что при записи файлы разбиваются блоки, по которым считаются
хеш-значения), H = 2h – количество значений хеш-функции (h – размер хеш-значения в
битах), 2-h – вероятность коллизии для двух блоков, P(N, H) – вероятность отсутствия
коллизий. Тогда
𝑃(𝑁, 𝐻 ) = 1 (1 −
1
2
𝑁−1
𝐻!
) (1 − ) … (1 −
)= 𝑁
𝐻
𝐻
𝐻
𝐻 (𝐻 − 𝑁 )!
Пусть N << H. При малых x можно считать, что 1 + x ≈ ex. Тогда получаем
1
2
𝑁
𝑃(𝑁, 𝐻 ) ≈ 𝑒 −𝐻 𝑒 −𝐻 … 𝑒 −𝐻 = 𝑒 −
𝑃(𝑁, 𝐻 ) ≈ 1 –
𝑁(𝑁+1)
2𝐻
𝑁2
2𝐻
Таким образом, вероятность коллизии приближенно квадратично зависит от
размера хранилища и примерно экспоненциально от размера хеша[12].
Рассмотрим конкретный пример:
Размер хранилища – 128 Тб;
Размер блока – 4 Кб;
Размер хеша – 256 бит;
N = 235;
H = 2256;
𝑃(𝑁, 𝐻 ) ≈ 1 –
270
2257
≈ 1 – 5,1 * 10−56
10
6.
Обработка коллизий
Размеры хранилищ данных могут сильно варьироваться. Исходя из этого, для
экономии памяти на хеш-значениях при возможности стоит либо выбирать хеш-функции
разных размеров для разных хранилищ, либо использовать лишь часть байтов от
имеющихся хеш-значений. Для этого достаточно знать примерный размер хранилища
данных, а также вероятность коллизии, которая нас устроила бы. Затем по приведенной в
предыдущем параграфе формуле, нужно высчитать подходящий размер хеша.
Исходя из того, что мы сами выбираем удовлетворяющую нас вероятность
коллизии (мы хотим сделать эту вероятность достаточно маленькой, но не слишком,
чтобы не тратить чересчур много памяти на хранение хешей), а также при условии, что
коллизии не вызываются искусственно, можно вместо сложной обработки коллизий
использовать следующий метод:
При возникновении коллизии вместо идентификатора блока будем хранить нулевое
значение. А для всех таких хеш-значений, у которых на месте идентификатора нулевое
значение,
дополнительно
создается
таблица
с
двумя
полями:
хеш-значение и
идентификатор. Но в данной таблице хеш-значения уже необязательно должны быть
уникальны. То есть в случае совпадения хеш-значений двух разных блоков в основной
хеш-таблице будет храниться это хеш-значение и нулевой идентификатор, а в
дополнительной хеш-значение и два разных идентификатора, которые указывают место
хранения этих двух блоков.
Приведем блок-схему (рисунок 3) данного алгоритма, где a и b – блоки данных;
h(a) – новое хеш-значение, посчитанное по блоку a; h(b) – старое хеш-значение, с которым
сравниваем, посчитанное по блоку b; i(a) – идентификатор блока a; i(b) – идентификатор
блока b).
11
Рисунок 3. Блок-схема алгоритма обработки коллизий при дедупликации.
12
7.
Результаты эксперимента с данными
Процесс дедупликации был реализован на языках программирования Java и C.
Вычислительная машина имела следующие характеристики:
Процессор: Intel(R) Core(TM) i3 2.3GHz;
Оперативная память: 8GB;
Операционная система: Windows 7 Home Basic;
Размер данных для эксперимента ~ 200 Гб. Далее при упоминании хеш-значений
без сжатия имеется в виду обычная хеш-таблица. А после сжатия хеш-таблица уже имеет
вид, предложенный в параграфе 4.
Алгоритм хеширования – MD5; Размер хеш-значений без сжатия ~ 1300 Мб;
Размер идентификаторов блоков ~ 350 Мб;
a. Алгоритм сжатия – bzip2; Размер хеш-таблицы после сжатия ~ 737 Мб;
Дополнительное время, которое потребовалось на сжатие и разжатие
блоков при дедупликации ~ 342 сек;
b. Алгоритм
сжатия
–
DEFLATE;
Размер
хеш-таблицы
после
сжатия ~ 766 Мб; Дополнительное время, которое потребовалось на
сжатие и разжатие блоков при дедупликации ~ 155 сек;
c. Алгоритм сжатия – LZMA; Размер хеш-таблицы после сжатия ~ 754 Мб;
Дополнительное время, которое потребовалось на сжатие и разжатие
блоков при дедупликации ~ 355 сек;
Рисунок
3. Гистограмма зависимости
дополнительного времени процесса
дедупликации и размера хеш-таблицы от алгоритмов компрессии.
1400
1200
1000
800
Размер хеш-таблицы
(Мб)
600
Дополнительное
время (сек)
400
200
0
Без сжатия
bzip2
DEFLATE
13
LZMA
8.
Заключение
В данной работе была рассмотрена задача сжатия хеш-значений в процессе
дедупликации. В ходе решения данной задачи были произведены следующие работы:
Изучение литературы по алгоритмам хеширования и компрессии;
Разработка структуры данных для дедупликации, которая позволит хранить
хеш-таблицу к более компактному виду;
Разработка программного кода и проведение экспериментов на его основе;
Сравнение результатов для разных алгоритмов сжатия;
Результаты эксперимента (параграф 7) показывают, что уменьшение затрат на
хранение таких метаданных, как хеш-значения и идентификаторов блоков, действительно
возможно, и умеренно увеличивает время процесса дедупликации.
В качестве продолжения работы можно предложить реализацию, в которой при
переполнении имеющейся in-memory базы данных, часть хеш-значений отправляется во
вторичную память.
14
Список литературы
[1] P. Shilane, M. Huang, G. Wallace, and W. Hsu. WAN Optimized Replication of Backup
Datasets Using Stream-Informed Delta Compression. In Backup Recovery Systems Division
EMC Corporation
[2] Data deduplication. http://www.emc.com/corporate/glossary/data-deduplication.htm
[3] Ахо, Хопкрофт и Ульман. Структуры данных и алгоритмы. 2003. С. 116-121
[4] R. Rivest. The MD5 Message-Digest Algorithm. MIT Laboratory for Computer Science
and RSA Data Security, Inc. 1992
[5] Penard W, Werkhoven T. On the secure hash algorithm family. 2008
[6] MurmurHash. http://murmurhash.googlepages.com/
[7] Theresa Maxino. Revisiting Fletcher and Adler Checksums Carnegie. Mellon University
Student Forum. 2006
[8] Алгоритмы сжатия данных без потерь. http://habrahabr.ru/post/231177/
[9] Алгоритмы сжатия данных без потерь. Часть 2. http://habrahabr.ru/post/235553/
[10] Understanding
Pages
and
Extents.
https://msdn.microsoft.com/en-
us/library/ms190969.aspx
[11] Richard E. Smith. Elementary Information Security. 2013. С. 203-205
[12] А. Кладов. Презентация “Надежность хеша для однозначной идентификации
данных при дедупликации”. 2011
15
Отзывы:
Авторизуйтесь, чтобы оставить отзыв