Тема: Исследование возможности сжатия хеш-значений при дедупликации данных
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
1. Постановка задачи 5
2. Предварительная работа 6
3. Идентификаторы блоков 8
4. Представление хеш-значений 9
5. Коллизия хеш-функций 10
6. Обработка коллизий 11
7. Результаты эксперимента с данными 13
8. Заключение 14
Список литературы
📖 Введение
Дедупликация - это метод сжатия массива данных, при котором находятся и удаляются дубликаты данных. Сначала данные разбиваются на блоки, по которым считаются хеш-значения, а затем эти хеш-значения сравниваются, и только при совпадении уже сравниваются сами блоки данных.
В процессе дедупликации генерируется большой массив хеш-значений. Например, для блоков по 4 Кб на 4 Тб данных потребуется 8 Гб памяти только для хеш-значений (если брать алгоритм, в котором 1 хеш занимает 8 байт). Кроме того, требуется память для хранения идентификаторов блоков и других метаданных.
Одной из стадий дедупликации является сравнение полученных хеш-значений с теми, которые уже хранятся в базе данных. Для ускорения процесса сравнения можно хранить список хешей в in-memory базе данных. Но такой способ подходит не для всех хранилищ, т.к. размер in-memory баз данных намного меньше обычных. Поэтому для расширения границ ее использования можно применить сжатие к хеш-значениям перед хранением.
✅ Заключение
• Изучение литературы по алгоритмам хеширования и компрессии;
• Разработка структуры данных для дедупликации, которая позволит хранить хеш-таблицу к более компактному виду;
• Разработка программного кода и проведение экспериментов на его основе;
• Сравнение результатов для разных алгоритмов сжатия;
Результаты эксперимента (параграф 7) показывают, что уменьшение затрат на хранение таких метаданных, как хеш-значения и идентификаторов блоков, действительно возможно, и умеренно увеличивает время процесса дедупликации.
В качестве продолжения работы можно предложить реализацию, в которой при переполнении имеющейся in-memory базы данных, часть хеш-значений отправляется во вторичную память.