Key-Value системы и их применение к моделям с наследованием структуры данных Московский физико-технический институт Выпускная квалификационная работа студента гр.617 Шевцова А. В. Научный руководитель Евдокимов А.В., к.ф.-м.н., доцент Научный консультант Нарыжный И.Г.

Введение Предпосылки: Любому Enterprise-приложению необходима БД, позволяющая оперировать с данными и хранить их Кроме РБД, существует множество других БД различного рода Новый вид БД – Key-Value системы Необходимо выяснить, когда стоит использовать KV вместо РБД

Введение Цель: исследовать возможности практического применения KV, их преимущества и недостатки Задачи: реализовать модель с наследованием структуры данных, используя KV выяснить качественные и количественные характеристики полученной системы сравнить систему с другими по установленным параметрам

Распределенные хеш-таблицы (DHTs) Каждый узел имеет n-битный идентификатор Идентификаторы выстраивают в кольцо Ключи для поиска данных также n- битные – получаются хешированием реального ключа Идентификаторы узлов и ключи поиска находятся в одном пространстве Каждый узел отвечает за ближние ключи

Распределенные хеш-таблицы

Используют хеш ключа для разделения ответственности между узлами При перекрытии зон ответственности узлов система имеет возможность переживать отказы узлов без потери данных Эффективные алгоритмы маршрутизации позволяют находить узлы, ответственные за определенный ключ за время O(log N), где N – число узлов в системе Могут быстро находить данные на огромном количестве узлов по всей сети Интернет

Распределенные хеш-таблицы Преимущества: Масштабируемость Устойчивость к отказам Самоорганизация Удобны для работы с объектами с известными идентификаторами. Недостатки: Проблемы с поиском Проблемы с безопасностью и целостностью данных

Project Voldemort Key-Value система от LinkedIn – авторитетный разработчик В основе лежит DHT Богатый дополнительный функционал Множество сторонних проектов, расширяющих функционал Key-Value системы Основаны на DHT Дополнительная функциональность

Модель SN

SN over KV.data – основные параметры (идентификаторы родителя и шаблона, имя и адаптер).value – единичное значение.value.{ } – множественное значение.children.{ } – список дочерних объектов.successors.{ } – список наследников

Большие списки Реализована фрагментации списков, поскольку в Project Voldemort нет ее встроенной поддержки.{ } – последовательность фрагментов списка при достижении последним фрагментом определенного размера создается новый

Методика тестирования Большинство тестов проводится на специальных наборах данных для выделения необходимой характеристики системы Один тест проводится на реальных данных Исследуется производительность основных операций над объектами

Методика тестирования Каждая операция выполняется последовательно на 10 одинаковых объектах для получения среднего значения исследуемого времени Время выполнения операции измеряется при нескольких значениях параметра, от которого это время может зависеть

Результаты измерений РеализацияSN over VoldemortSN over RDBMetamodel classic over RDB Время, мс РеализацияSN over VoldemortSN over RDBMetamodel classic over RDB Время, мс Реализация Metamodel classic over RDB SN over RDB SN over Voldemort (BulkStore) SN over Voldemort Время загрузки в БД, с Время чтения из БД, с Чтение объекта из базы Установка значения атрибута Работа с структурой файловой системы

Создание дочернего объекта

Добавление значения атрибута

Поиск объекта по имени

Сводные результаты Metamodel classic SN over RDB SN over KV Работа с известным объектом/атрибутом с единичным значением 321 Работа с множественным атрибутом (N < 100)321 Работа с множественным атрибутом (N > 100)213 Создание дочернего объекта (N < 100)312 Создание дочернего объекта (N > 100)213 Поиск объекта по параметрам (N < 10)231 Поиск объекта по параметрам (N > 10)123

Выводы Применение KV нежелательно, если 1)требуется часто искать среди многих объектов по параметрам 2)имеется много одноуровневых сущностей Применение KV наиболее выгодно при работе с иерархическими структурами с низким коэффициентом ветвления

Дальнейшая работа Оптимизация работы с большими списками Исследование возможностей ускоренного поиска по параметрам с помощью индексирования Исследование вопроса безопасности в данной системе с разработкой методов обеспечения защищенности системы

Спасибо за внимание