WWW.KN.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные ресурсы
 


«Правительство Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный ...»

Правительство Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский государственный университет»

Кафедра информационно-аналитических систем

Гусева Мария Максимовна

Исследование возможности сжатия хеш-значений

при дедупликации данных

Бакалаврская работа

Допущена к защите

И. о. заведующего кафедрой:

к. ф.-м. н., доцент Е. Г. Михайлова

Научный руководитель:

старший преподаватель Д. В. Луцив

Рецензент:

к. ф.-м. н., доцент Е. Г. Михайлова Санкт-Петербург 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 Оглавление Введение

Постановка задачи

1.

Предварительная работа

2.

Идентификаторы блоков

3.

Представление хеш-значений

4.

Коллизия хеш-функций

5.

Обработка коллизий

6.

Результаты эксперимента с данными

7.

Заключение

8.

Список литературы

Введение Регулярное резервное копирование является обычной практикой для защиты от аппаратных сбоев и ошибок пользователей. Сжатие данных перед передачей может помочь существенно увеличить пропускную способность[1]. Действенным методом для эффективного уменьшения передаваемых данных является дедупликация[2].

Дедупликация – это метод сжатия массива данных, при котором находятся и удаляются дубликаты данных. Сначала данные разбиваются на блоки, по которым считаются хеш-значения, а затем эти хеш-значения сравниваются, и только при совпадении уже сравниваются сами блоки данных.

В процессе дедупликации генерируется большой массив хеш-значений. Например, для блоков по 4 Кб на 4 Тб данных потребуется 8 Гб памяти только для хеш-значений (если брать алгоритм, в котором 1 хеш занимает 8 байт). Кроме того, требуется память для хранения идентификаторов блоков и других метаданных.

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

1. Постановка задачи Цель данной работы – создание структуры данных для дедупликации для получения существенной экономии памяти, выделенной для хранения метаданных.

Рисунок 1. Компрессия блока хеш-значений в процессе дедупликации.

–  –  –

На вход подаются хеш-значения, полученные из данных (одно хеш-значение на каждые 4 Кб данных). После того, как набирается 64 Кб хеш-значений, требуется произвести компрессию. То есть компрессия производится не над одним хеш-значением, а над блоком размера 64 Кб, состоящим из хеш-значений.

В памяти будет храниться какое-то количество блоков сжатых хеш-значений разного размера (т.





к. не все блоки одинаково поддаются сжатию). Хеш-таблица – это структура данных, обладающая свойством амортизированной сложности доступа, которая достигается при надлежащем подборе параметров (то есть в среднем поиск элемента имеет временную сложность. О(1))[3]. Соответственно, хотелось бы сохранить это свойство даже после сжатия, чтобы не приходилось разжимать всю хеш-таблицу на стадии сравнения хеш-значений во время дедупликации. То есть требуется разжимать только тот сжатый блок, где, вероятно, лежит такое же хеш-значение, а не все блоки.

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

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

–  –  –

Ссылки могут быть двух видов:

Путь к файлу вида "C:\...", "/mnt/..." и т.д. в виде строки;

Уникальный идентификатор файла на партиции (например, номер первого NTFS extent (Microsoft Windows)[10] или inode (UNIX-системы)[11]);

Рассмотрим ссылки второго вида, т.к. они являются шестнадцатеричными числами, которые и до, и после сжатия имеют меньший объем по сравнению с ссылками первого вида. Проверим, насколько они поддаются сжатию.

–  –  –

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

Допустим, мы имеем 128-битную хеш-функцию (рисунок 2). Соответственно, каждое хеш-значение состоит из 128 бит, что равно 32 байтам. Предлагается разделить каждый хеш на три части (количество уровней дерева может варьироваться, как и размер частей): 16 байт, 8 байт и 8 байт. Далее у каждого узла сохраняются лишь уникальные потомки.

–  –  –

… 16 … 23 16 … 23 0 … 15 … К примеру, если взять 128-битную хеш-функцию MD5 и представить ее в виде такого дерева (2 уровня: 8 байт и 24 байта), то для 6 миллионов хешей экономия места составит 0,4% лишь на том, что мы по-другому представили хеш-таблицу. Стоит отметить, что этот процент будет расти в зависимости от количества хеш-значений – при увеличении количества хеш-значений растет количество повторов их частей.

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

Оценим вероятность возникновения коллизий при дедупликации. Для удобства будем считать, что коллизии не вызываются искусственно, а значит, можно считать, что значения хеш-функции распределены равномерно. Пусть N – количество блоков в хранилище (напомним, что при записи файлы разбиваются блоки, по которым считаются хеш-значения), H = 2h – количество значений хеш-функции (h – размер хеш-значения в битах), 2-h – вероятность коллизии для двух блоков, P(N, H) – вероятность отсутствия коллизий. Тогда 1 2 1 !

(, ) = 1 (1 ) (1 ) … (1 ) = ( )!

–  –  –

1 2 (+1) (, ) … = 2 (, ) 1 – Таким образом, вероятность коллизии приближенно квадратично зависит от размера хранилища и примерно экспоненциально от размера хеша[12].

Рассмотрим конкретный пример:

–  –  –

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

Исходя из того, что мы сами выбираем удовлетворяющую нас вероятность коллизии (мы хотим сделать эту вероятность достаточно маленькой, но не слишком, чтобы не тратить чересчур много памяти на хранение хешей), а также при условии, что коллизии не вызываются искусственно, можно вместо сложной обработки коллизий использовать следующий метод:

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

Приведем блок-схему (рисунок 3) данного алгоритма, где a и b – блоки данных;

h(a) – новое хеш-значение, посчитанное по блоку a; h(b) – старое хеш-значение, с которым сравниваем, посчитанное по блоку b; i(a) – идентификатор блока a; i(b) – идентификатор блока b).

Рисунок 3. Блок-схема алгоритма обработки коллизий при дедупликации.

7. Результаты эксперимента с данными Процесс дедупликации был реализован на языках программирования Java и C.

Вычислительная машина имела следующие характеристики:

–  –  –

Рисунок 3. Гистограмма зависимости дополнительного времени процесса дедупликации и размера хеш-таблицы от алгоритмов компрессии.

–  –  –

8. Заключение В данной работе была рассмотрена задача сжатия хеш-значений в процессе дедупликации. В ходе решения данной задачи были произведены следующие работы:

Изучение литературы по алгоритмам хеширования и компрессии;

Разработка структуры данных для дедупликации, которая позволит хранить хеш-таблицу к более компактному виду;

Разработка программного кода и проведение экспериментов на его основе;

Сравнение результатов для разных алгоритмов сжатия;

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

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

Список литературы [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/enus/library/ms190969.aspx [11] Richard E. Smith. Elementary Information Security. 2013. С. 203-205 [12] А. Кладов. Презентация “Надежность хеша для однозначной идентификации




Похожие работы:

«Приложение № 1 к приказу РГСУ от "_" 20 г. № _ Положение об организации и проведении Олимпиады в 2017 году по направлению подготовки "Социальная работа" Общие положения 1.1.1. Настоящее Положение об организации и проведении всер...»

«ЗУБОВРАЧЕБНЫЕ ЗАМЕТКИ Нью-Йорк, № 79 Др. Евгений Иоффе, DDS, PhD © C o p yr i g h t 2 0 1 2 Починка фарфора. Многообразие и единообразие. Я не помню ни одной из своих лекций, на которой мне бы не задавали вопрос о починке фарфора....»

«Ольга Н. Воскресенская Последствия выбора Серия "Выбор решает все", книга 2 Текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=3523155 Последствия выбора: Альфа-книга; Москва; 2012 ISBN 978-5-9922-1170-2 Аннотация Обстоятельства сложились так, что несколько месяцев назад Ройс был вынужден выбрать б...»

«Адреса Центров Продаж Herbalife АЛЬМЕТЬЕВСК АНГАРСК Альметьевск, ул. Р.Фахретдина, д.37 Ангарск, 29-й Микрорайон, д. 28 Телефон: +7 8553 44-14-10 Телефон: +7 (3955) 97-00-09 Рабочие дни: 10:30-19:00 Рабочие дни: 12:00-19:00 Суббота, за исключением последней в месяце: 10:30-19:00 Последняя суббот...»

«1. Общие положения 1.1. Региональный этап Всероссийского конкурса "Доброволец России – 2017" (далее – Конкурс) направлен на повышение социальной активности молодежи и престижа добровольческой деятельности среди населения Волгоградской области, обобщения и передачи добровольческого опыта...»

«§5.3. Секстан Краткая теория и устройство навигационного секстана Для решения полярного треугольника необходимо знать любые три его элемента. Одним из этих элементов является высота светила. Рис. 5.3 1 – рама секстана, 2 – лимб, 3 – алидада, 4 – зрительная труба, 5 – большое зеркало, 6 – малое зеркало, 7 – обойма зри...»

«СОВЕТ ГОРОДСКОГО ОКРУГА Г. УФА РЕСПУБЛИКИ БАШКОРТОСТАН РЕШЕНИЕ от 24 ноября 2010 г. N 30/8 ОБ УТВЕРЖДЕНИИ УСЛОВИЙ ПРИЕМА СТОЧНЫХ ВОД И ЗАГРЯЗНЯЮЩИХ ВЕЩЕСТВ В СИСТЕМУ КОММУНАЛЬНОЙ КАНАЛИЗАЦИИ ГОРОДА УФЫ...»

«ПРОГРАММА ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ "ТВОРЧЕСКИЙ КОНКУРС" для поступающих на 1-й курс на основную образовательную программу подготовки "ХУДОЖНИК МУЛЬТИПЛИКАЦИОННОГО ФИЛЬМА" (специальность 54.05.03."ГРАФИКА") Раздел I. Организационно-методический. Для абитуриентов, поступающих на обучение по специальности 54.05.03. "...»

«11 июня 2017 го да. Неде ля 1 по Пятидеся тнице, всех святых. Глас 8. ВЕЛИКАЯ ВЕЧЕ РНЯ ВСЕНО ЩНОЕ БДЕ НИЕ Воста ните! Благослови.Диа кон: Хор: Иере й: Сла ва Святе й, и Единосу щней, и Животворя щей, и Неразде льней Тро ице всегда, ныне Ами нь. и при сно, и во ве ки веко в. Хор: Священн...»








 
2017 www.kn.lib-i.ru - «Бесплатная электронная библиотека - различные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.