Евдокимов А. В., к ф. м н




Скачать 470.86 Kb.
страница1/3
Дата04.08.2016
Размер470.86 Kb.
  1   2   3
Министерство образования и науки Российской Федерации

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ
(государственный университет)


ФАКУЛЬТЕТ РАДИОТЕХНИКИ И КИБЕРНЕТИКИ

КАФЕДРА ИНФОКОММУНИКАЦИОННЫХ СИСТЕМ И СЕТЕЙ

Key-Value системы и их применение к моделям с наследованием структуры данных
Выпускная квалификационная работа

студента 617 группы

Шевцова Андрея Викторовича

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

Евдокимов А.В., к.ф.-м.н., доцент
Научный консультант

Нарыжный И.Г.

г. Долгопрудный

2010

Содержание


Введение 4

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

2 Обзор источников 5

2.1 Базы данных 5

2.1.1 Классификация баз данных 6

2.1.2 Распределённые базы данных 7

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

2.1.4 Key-Value системы 29

2.2 Метамодели данных 29

3 Методика решения задачи 31

3.1 Project Voldemort 33

3.2 Проблема построения метамодели над key-value системой 34

3.3 Построение модели с наследованием структуры данных над key-value системой 35

3.4 Реализация хранения списков 36

4 Результаты измерений 37

4.1 Время создания нового объекта 38

4.2 Время загрузки объекта из базы 40

4.3 Время поиска объекта по его параметрам 40

4.5 Время модификации значения атрибута 41

4.6 Комбинированный тест 43

4.7 Анализ результатов 44

Заключение 44

Источники 46



Введение


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

Долгое время на рынке баз данных господствуют реляционные базы данных (далее РБД), и часто многие разработчики, не задумываясь, выбирают БД именно этого типа. Однако на рынке существуют и другие БД, особенно хочется отметить недавно появившиеся системы типа ключ-значение, или Key-Value (далее KV). Эти системы сейчас активно развиваются и не имеют еще устоявшегося названия, другие распространенные названия: распределенная хеш-таблица – Distributed Hash Table (далее DHT), документно-ориентированные БД – Document-Oriented Data Base. БД этого типа мало описаны в литературе и применяются пока в основном энтузиастами, поэтому исследование возможностей применения этих систем является актуальным.

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

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


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

Первой задачей работы является реализация модели с наследованием структуры данных с использованием KV-системы и проведение серии экспериментов для изменения качественных и количественных характеристик полученной системы. Второй задачей работы является сравнение выявленных характеристик с аналогичными характеристиками других моделей данных, использующих другие БД. Упомянутая модель с наследованием структуры данных является новой в мире баз данных, а KV-системы только начинают развиваться.


2 Обзор источников

2.1 Базы данных


Рассмотрение баз данных начнем с определения основных понятий. База данных – это набор постоянных (persistent) данных, используемых прикладными системами (1). Далее в понятие БД, кроме собственно данных, будут включаться и особенности структуры этих данных. Система управления базой данных – Data Base Management System (далее СУБД или DBMS) – набор программных средств, представляющих и регулирующих доступ к базе данных. Термин постоянные данные (persistent data) используется здесь в противовес другим более изменчивым данным. Второй основной функцией СУБД является обеспечение постоянности (persistence) данных в БД. То есть данные в БД должны оставаться неизменными после принятия их средствами СУБД для помещения в базу, и впоследствии изменены они могут быть только с помощью соответствующего явного запроса к базе (1).

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


2.1.1 Классификация баз данных


Так же как существует множество видов баз данных, существует множество способов их классификации. Далее будут рассмотрены основные из них (2).

Классификация по модели данных


Наиболее интересный с учетом цели данной работы способ классификации – это классификация по модели данных. Модель данных понимается как способ логического представления данных. Модель данных описывает используемые базой сущности для представления данных и возможные взаимоотношения между ними. Часто этот способ классификации называют классификацией по структуре хранимых данных.

Итак, по модели данных базы данных делятся на следующие виды:



  1. Иерархические.
    В иерархической модели данных сущностью является вершина с набором атрибутов. Все вершины связаны между собой отношениями типа (родитель, ребёнок). Причем у каждой вершины, кроме корневой, не имеющей родителя, имеется ровно один родитель. В таких условиях все вершины с учетом их взаимоотношения образуют иерархическую структуру – дерево.

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

  3. Реляционные.
    Основаны на реляционной модели данных. Сущностью является соотношение, связывающее вместе конечный набор значений. Визуально соотношение представляется строкой в таблице. Для работы с такими базами данных используется язык запросов SQL (Structured Query Language).

  4. Объектно-ориентированные.
    В объектно-ориентированной модели данных основной сущностью является объект. Каждый объект обладает типом, описывающим возможности объекта, и классом, реализующим возможности объекта. Внутренним языком таких баз данных является какой-либо объектно-ориентированный язык программирования. Фундаментальной идеей ООБД является повышение уровня абстракции.

  5. Объектно-реляционные.
    Объединяют в себе возможности реляционных БД и объектно-ориентированных БД. Как правило, построены на основе РБД с добавлением некоторых возможностей ООБД.

Классификация по содержимому


  1. Географические

  2. Исторические

  3. Научные

  4. Мультимедийные.

Классификация по степени распределенности


  1. Централизованные (сосредоточенные)

  2. Распределённые

2.1.2 Распределённые базы данных


Уделим особое внимание рассмотрению распределенных баз данных, поскольку именно таковыми и являются рассматриваемые далее KV-системы.

Распределенная БД состоит из множества узлов, каждый из которых сам по себе является полноценной базой данных. Узлы распределенной БД соединены между собой коммуникационной сетью. Коммуникационные связи между узлами позволяют пользователю произвольного узла получать доступ к данным, хранящимся на любом другом узле, как будто они находятся на его собственном узле. Из сказанного следует, что распределенная БД является виртуальной базой данных, компоненты которой физически хранятся в реальных БД на нескольких узлах, то есть является логическим объединением нескольких реальных баз данных (1). Всю распределенную систему баз данных можно рассматривать как некоторое партнерство между отдельными локальными СУБД на отдельных локальных узлах. Новый программный компонент на каждом узле — логическое расширение локальной СУБД — предоставляет необходимые функциональные возможности для организации подобного партнерства. Именно этот компонент вместе с существующими СУБД составляет то, что обычно называется распределенной системой управления базами данных (РСУБД).

Чаще всего предполагается, что узлы разделены физически (а возможно, и территориально), хотя в действительности достаточно того, чтобы они были разделены логически. Два узла могут даже сосуществовать на одном и том же физическом компьютере (в особенности на начальном этапе тестирования). Главная цель создания распределенных систем со временем изменялась. В ранних исследованиях в основном предполагалась территориальная распределенность, но в большинстве первых коммерческих реализаций предполагалось локальное распределение, когда несколько узлов размещалось в одном здании и соединялось с помощью локальной сети (ЛВС). Однако позже стремительное распространение глобальных сетей снова пробудило интерес к использованию территориального распределения. В любом случае это не имеет большого значения с точки зрения системы баз данных — решать в основном требуется одни и те же технические проблемы.

Требования к распределенным системам


Рассмотрим основные требования к распределенным системам. Фундаментальный принцип создания распределенной системы: для пользователя распределенная система должна выглядеть так же, как нераспределенная система. Другими словами, пользователи распределенной системы должны иметь возможность действовать так, как если бы система не была распределена. Все проблемы распределенных систем относятся или должны относиться к внутренним проблемам (проблемам реализации), а не к внешним проблемам (проблемам пользовательского уровня).

Сформулированный выше фундаментальный принцип имеет следствием определенные дополнительные правила или цели. Таких целей всего двенадцать:



  1. Локальная независимость.

  2. Отсутствие зависимости от центрального узла.

  3. Непрерывное функционирование.

  4. Независимость от расположения.

  5. Независимость от фрагментации.

  6. Независимость от репликации.

  7. Обработка распределенных запросов.

  8. Управление распределенными транзакциями.

  9. Аппаратная независимость.

  10. Независимость от операционной системы.

  11. Независимость от сети.

  12. Независимость от типа СУБД.

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

Рассмотрим подробно эти требования.


Локальная независимость

Узлы в распределенной системе должны быть независимы, или автономны. Локальная независимость означает, что все операции на узле контролируются этим узлом. Никакой узел не должен зависеть от некоторого другого узла, чтобы успешно функционировать (иначе, если какой-либо узел будет отключен, другой узел не сможет функционировать, даже если на самом нем будет все в порядке; возникновение таких ситуаций, безусловно, нежелательно). Локальная независимость также означает, что локальные данные имеют локальную принадлежность, управление и учет. Все данные реально принадлежат одной и той же локальной базе данных, даже если доступ к ней осуществляется с других, удаленных узлов. Следовательно, такие вопросы, как безопасность, целостность, защита и представление локальных данных на физическом устройстве хранения, остаются под контролем и в пределах компетенции локального узла.

В действительности, локальная независимость не вполне достижима — есть множество ситуаций, в которых один узел должен отказываться в определенной степени от контроля в пользу другого узла. Поэтому цель достижения локальной независимости точнее можно было бы сформулировать так: узлы должны быть независимыми в максимально возможной степени.


Отсутствие зависимости от центрального узла

Локальная независимость предполагает, что все узлы в распределенной системе должны рассматриваться как равные. Поэтому, в частности, не должно быть никаких обращений к центральному, или главному, узлу для получения некоторой централизованной услуги. Не должно быть, например, централизованной обработки запросов, централизованного управления транзакциями или централизованной службы присваивания имен, поскольку в таких случаях система в целом будет зависимой от центрального узла. Таким образом, вторая цель на самом деле является следствием первой цели — если первая цель достигнута, то вторая цель также заведомо достигается. Но достижение цели "Отсутствие зависимости от центрального узла" полезно само по себе, даже если полная локальная независимость узлов не будет достигнута. Поэтому отдельная формулировка данной цели также важна.

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


Непрерывное функционирование

В общем случае преимущество распределенных систем состоит в том, что они должны предоставлять более высокую степень надежности и доступности. Надежность понимается как высокая степень вероятности того, что система будет работоспособна и будет функционировать в любой заданный момент. Надежность распределенных систем повышается за счет того, что они не опираются на принцип "все или ничего"; распределенные системы могут непрерывно функционировать (по меньшей мере, в сокращенном варианте) даже в случаях отказов части их компонентов, таких как отдельный узел. Доступность понимается как высокая степень вероятности того, что система окажется исправной и работоспособной и будет непрерывно функционировать в течение определенного времени. Доступность, как и надежность распределенных систем также повышается — частично по тем же причинам, а также благодаря возможности дублирования данных. Предыдущие рассуждения относятся к случаям незапланированного отключения системы, т.е. к аварийным ситуациям, которые могут возникнуть в системе в любой момент. Незапланированные отключения системы, безусловно, нежелательны, но их трудно предупредить! Планируемые отключения системы, напротив, никогда не должны быть необходимыми, т.е. никогда не должна возникать необходимость отключить систему, чтобы выполнить какую-либо задачу, например, добавить новый узел или заменить на уже существующем узле текущую версию СУБД ее новой реализацией.
Независимость от расположения

Основная идея независимости от расположения, или так называемой прозрачности расположения, проста. Пользователи не должны знать, где именно данные хранятся физически и должны поступать так (по крайней мере, с логической точки зрения), как если бы все данные хранились на их собственном локальном узле. Благодаря независимости от расположения упрощаются пользовательские программы и терминальные операции. В частности, данные могут быть перенесены с одного узла на другой, и это не должно требовать внесения каких-либо изменений в использующие их программы или действия пользователей. Такая переносимость желательна, поскольку она позволяет перемещать данные в сети в соответствии с изменяющимися требованиями к эффективности работы системы.
Независимость от фрагментации

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

Система, которая поддерживает фрагментацию данных, должна поддерживать и независимость от фрагментации (иногда это свойство называют прозрачностью фрагментации). Другими словами, пользователи должны иметь возможность работать точно так, по крайней мере, с логической точки зрения, как если бы данные в действительности были вовсе не фрагментированы. Независимость от фрагментации (как и независимость от расположения) — это весьма желательное свойство, поскольку позволяет упростить разработку пользовательских программ и выполнение терминальных операций. В частности, это свойство гарантирует, что в любой момент данные могут быть заново восстановлены (а фрагменты перераспределены) в ответ на изменение требований к эффективности работы системы, причем ни пользовательские программы, ни терминальные операции при этом не затрагиваются. Таким образом, если обеспечивается независимость от фрагментации, пользователи получают данные в виде некоторого представления, в котором фрагменты логически скомбинированы с помощью соответствующих операций соединения и объединения.


Независимость от репликации

Система поддерживает репликацию данных, если данный хранимый объект может быть представлен несколькими отдельными копиями, или репликами, которые хранятся на нескольких отдельных узлах.

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

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

Обработка распределенных запросов

Поскольку данные, необходимые для выполнения пользовательского запроса, реально могут быть реплицированы, фрагментированы и распределены по множеству узлов, выполнение запроса требует взаимной работы нескольких узлов сети. Система должна иметь возможность оптимизировать и выполнить запрос так, как будто все данные находятся на одном узле.
Управление распределенными транзакциями

Как известно, существует два главных аспекта управления транзакциями, а именно: управление восстановлением и управление параллельностью обработки. Оба этих аспекта имеют расширенную трактовку в среде распределенных систем. Чтобы разъяснить особенности этой расширенной трактовки, сначала необходимо ввести новое понятие — агент. В распределенной системе отдельная транзакция может потребовать выполнения кода на многих узлах, в частности, это могут быть операции обновления, выполняемые на нескольких узлах. Поэтому говорят, что каждая транзакция содержит несколько агентов, где под агентом подразумевается процесс, который выполняется для данной транзакции на отдельном узле. Система должна знать, что два агента являются элементами одной и той же транзакции, например, два агента, которые являются частями одной и той же транзакции, безусловно, не должны оказываться в состоянии взаимной блокировки.

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



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

По этому вопросу фактически нечего сказать — заголовок раздела говорит сам за себя. Парк вычислительных машин современных организаций обычно включает множество разных компьютеров. Поэтому действительно существует необходимость интегрировать данные всех этих систем и предоставить пользователю "образ единой системы". Следовательно, желательно иметь возможность эксплуатировать одну и ту же СУБД на различных аппаратных платформах и, более того, добиться, чтобы различные компьютеры участвовали в работе распределенной системы как равноправные партнеры.
Независимость от операционной системы

Достижение этой цели частично зависит от достижения предыдущей и также не требует дополнительного обсуждения. Очевидно, что необходимо иметь не только возможность обеспечить функционирование одной и той же СУБД на различных аппаратных платформах, но и обеспечить ее функционирование под управлением различных операционных систем для многих платформ — включая различные операционные системы на одном и том же оборудовании. Например, чтобы версия СУБД для операционной системы Solaris, версия для UNIX и версия для Windows могли совместно использоваться в одной и той же распределенной системе.
Независимость от сети

Здесь, опять же, нечего добавить. Если система имеет возможность поддерживать много принципиально различных узлов, отличающихся оборудованием и операционными системами, безусловно, необходимо, чтобы она также поддерживала ряд типов различных коммуникационных сетей.
Независимость от типа СУБД

В этом разделе мы рассмотрим, с чем приходится сталкиваться при отказе от требования строгой однородности системы. Необходимость такого сильного ограничения вызывает сомнения. Действительно, кажется, все, что необходимо, — так это то, чтобы экземпляры СУБД на различных узлах все вместе поддерживали один и тот же интерфейс, и совсем не обязательно, чтобы это были копии одной и той же версии СУБД. Например, СУБД Postgre и Oracle обе поддерживают официальный стандарт языка SQL, а значит, можно добиться, чтобы узел с СУБД Postgre и узел с СУБД Oracle обменивались между собой данными в рамках распределенной системы. Иными словами, распределенные системы вполне могут быть, по крайней мере, в некоторой степени, неоднородными. Поддержка неоднородности весьма желательна. На практике современное программное обеспечение обычно используется не только на многих различных компьютерах и в среде многих различных операционных систем. Оно довольно часто используется и с различными СУБД, и было бы очень удобно, если бы различные СУБД можно было каким-то образом включить в распределенную систему. Иными словами, идеальная распределенная система должна обеспечивать независимость от СУБД.

Проблемы распределенных систем


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

  1. Обработка запросов

  2. Управление каталогом

  3. Распространение обновлений

  4. Управление восстановлением

  5. Управление параллельностью.

Рассмотрим подробнее эти области.
Обработка запросов

Чтобы решить задачу минимизации использования сети, процесс оптимизации запросов должен быть распределенным, как и процесс выполнения запросов. Иначе говоря, в общем случае процесс оптимизации будет включать этап глобальной оптимизации, за которым последуют этапы локальной оптимизации на каждом участвующем узле. Время выполнения этого процесса сильно зависит от используемой модели данных. Например, в случае реляционной модели это может оказаться очень трудоемко. Но в случае использования простой модели key-value ситуация сводится к быстрому определению узлов, хранящих нужное значение. В большинстве систем для этого используется хеш от ключа. Это позволяет существенно повысить производительность простейших операций, как то: получение значения по ключу и присвоение значения ключу.
Управление каталогом

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

  1. Полностью централизованное хранение. Единственный общий каталог хранится на отдельном центральном узле. Недостатком подхода является нарушение принципа независимости от центрального узла.

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

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

  4. Централизованное хранение. Сочетание подходов 1 и 3. На каждом узле поддерживается свой локальный каталог, как предусмотрено в подходе 3. Кроме того, отдельный центральный узел поддерживает объединенную копию всех этих локальных каталогов, как предусмотрено в подходе 1. В этом случае для работы с нелокальными данными используется каталог, хранящийся на выделенном узле. Этот подход более эффективен по сравнению с предыдущим (для поиска удаленного объекта требуется доступ лишь к одному удаленному каталогу), но в этом случае вновь нарушается принцип отсутствия зависимости от центрального узла с полной версией каталога.

  5. Использование перманентных идентификаторов. Хотя детали реализации этой схемы и варьируются, она используется во многих системах. При создании в узле объекта данных ему присваивается логический идентификатор, содержащий идентификатор узла, где объект был создан – "место рождения". Этот идентификатор экспортируется в словари данных всех других узлов. Узел создания отслеживает, где в действительности хранится объект. При этом подходе для доступа к объекту необходимо обратиться не более чем к двум узлам - к узлу создания и к узлу, где объект находится в данный момент. Недостатком подхода является зависимость от узла создания.

Каждый подход имеет свои недостатки. Поэтому на практике в системах обычно не используется ни один из этих четырех подходов!
Распространение обновлений

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

  1. Одна копия для каждого реплицируемого объекта устанавливается как первичная копия, а все оставшиеся копии — как вторичные. Первичные копии различных объектов находятся на различных узлах (поэтому данная схема также является распределенной).

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

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

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

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

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


Управление восстановлением

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

  1. Принцип "отсутствия зависимости от центрального узла" предписывает, что функции координатора не должны назначаться одному выделенному узлу в сети, а должны выполняться на различных узлах для различных транзакций. Обычно управление транзакцией передается на тот узел, на котором она была инициирована. Поэтому каждый узел (как правило) должен быть способен выполнять функции координатора для некоторых транзакций и выступать в качестве участника выполнения остальных транзакций.

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

  3. Если узел Y является участником транзакции, выполняемой по протоколу двухфазной фиксации и координируемой узлом X, узел Y должен делать то, что предписывает ему узел X (фиксацию результатов транзакции или ее откат в зависимости от того, что именно потребуется), а это означает потерю (хотя и относительно не значительную) локальной автономности.
Управление параллельностью

Управление параллельным доступом в большинстве распределенных систем строится на использовании механизма блокировки, т.е. точно так, как и в большинстве нераспределенных систем. Однако в распределенных системах запросы на проверку, установку и отмену блокировки становятся сообщениями (если считать, что рассматриваемый объект расположен на удаленном узле), а сообщения создают дополнительные издержки. Рассмотрим, например, транзакцию T обновления объекта, для которого существуют дубликаты на n удаленных узлах. Если каждый узел отвечает за блокировку объектов, которые на нем хранятся (как предполагается в соответствии с принципом локальной независимости), то непосредственная реализация будет требовать, по крайней мере, 5n таких сообщений:

  • n запросов на блокировку,

  • n разрешений на блокировку,

  • n сообщений об обновлении,

  • n подтверждений,

  • n запросов на снятие блокировки.

Безусловно, мы можем разумно воспользоваться комбинированными сообщениями. Например, можно объединить сообщение запроса на блокировку и сообщение об обновлении, а также сообщение о разрешении блокировки и сообщение о подтверждении. Но даже в этом случае общее время обновления может быть на порядок больше, чем в централизованной системе.

Для решения проблемы обычно выбирается стратегия первичной копии, описанная выше. Для данного объекта все операции блокировки будет обрабатывать узел, содержащий его первичную копию (напомним, что первичные копии различных объектов будут в общем случае размещаться на разных узлах). При использовании этой стратегии набор всех копий объекта с точки зрения блокировки можно рассматривать как единый объект, а общее количество сообщений будет сокращено с 5n до 2n+3 (один запрос блокировки, одно разрешение блокировки, n обновлений, n подтверждений и один запрос на снятие блокировки). Но обратите внимание на то, что это решение влечет за собой серьезную потерю независимости — транзакция может теперь не завершиться, если первичная копия окажется недоступной, даже если в транзакции выполнялось лишь чтение и локальная копия была доступна. Отметим, что в некоторых системах блокировка первичной копии требуется не только для операций обновления, но и для операций выборки. Таким образом, у стратегии первичной копии есть нежелательный побочный эффект — снижение уровня производительности и доступности, как для выборки, так и для обновления.

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

Отметим, что в действительности не все системы распознают состояние взаимоблокировки — некоторые вместо этого просто используют механизм тайм-аута. По очевидным причинам данное замечание относится, в частности, и к распределенным системам.


Преимущества от использования распределенных систем


Несмотря на имеющиеся проблемы, распределенные системы имеет ряд преимуществ по сравнению с локализованными системами (3). Перечислим их.

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

  2. Повышение производительности обработки данных. Вместо одной машины базу обслуживает несколько машин.

  3. Повышение надежности. Отсутствует зависимость от центрального узла. При сбое одной машины страдает только локальная база данных.

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

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


Распределенные хеш-таблицы – Distributed hash tables (DHTs) – класс децентрализованных распределенных систем, предоставляющих интерфейс взаимодействия похожий на хеш-таблицу. В DHT хранятся пары типа (ключ, значение), причем каждый узел может эффективно вычислить значение, ассоциированное с данным ключом. Все узлы системы совместно поддерживают соответствие между ключами и значениями таким образом, что изменения в наборе узлов вызывают минимальные возмущения в системе. Это позволяет масштабировать DHT до чрезвычайно большого количества узлов и обрабатывать постоянные присоединения, отключения и отказы узлов (4).

Характерными чертами DHT являются:



  1. Децентрализация – узлы вместе формируют систему без какого-либо центрального управления

  2. Масштабируемость – система способна эффективно функционировать даже, если состоит из тысячи или миллиона узлов

  3. Устойчивость к сбоям – система в некотором смысле остаётся надежной даже в условиях постоянных подключений, отключений и сбоев узлов

Ключевой прием, позволяющий достичь этих свойств, основан на том, что любому узлу достаточно взаимодействовать только с небольшим количеством других узлов в системе (чаще всего примерно O(log n) узлами, n – общее число узлов в системе). Благодаря этому, узлам необходимо сделать ограниченный набор действий при изменении состава системы.

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

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

Принципы работы DHT


Рассмотрим основную идею, лежащую в основе DHT. Главная проблема, встающая перед распределенной системой таких размеров – как быстро определить узел, ответственный за определенные данные? Для этого в DHT используется хеш от ключа. Для построения DHT выбирается хеш-функция, что задает длину хеш-значения и пространство этих значений. Каждый узел имеет свой идентификатор той же длины, что и хеш. Обычно предполагается, что идентификаторы узлов случайны, а потому равномерно распределены в пространстве хеш-значений, но на практике идентификатор вычисляется хешированием каких-либо уникальных данных. Это позволяет интерпретировать каждый узел как точку во введенном выше пространстве. Аналогично каждый ключ хешированием можно спроецировать на это пространство. После этого можно ввести принцип разделения данных между узлами: каждый узел отвечает за ближайшие к нему ключи. Где близость понимается в смысле малости расстояния между узла и проекцией ключа. Обычно близость в пространстве проекций понимается в том смысле, что проекция некого ключа ближе к узлу A, чем к B. Обычно узлы изображают точками на кольце, при этом зонам ответственности узлов обычно соответствуют дуги окружности, как изображено на рисунке.

d:\private\нир\dht_nodesring.png

Рис. . Кольцо узлов и их ответственность

Второй важной проблемой является вопрос, как быстро находить ответственный узел? Очевидно, подход, при котором каждому узлу известны все другие узлы, неприемлем. Это проблема маршрутизации. Существует два основных алгоритма маршрутизации (6):



  1. Предполагаем, что каждый узел знает своих ближайших соседей по кольцу (если в системе больше 2 узлов, то у каждого узла два таких соседа). Узел посылает сообщения своим соседям, каждый сосед действует также, пока не найдется узел с данными. Сложность такого алгоритма O(n), что при больших размерах системы плохо.

  2. Предполагаем, что каждый узел с номером a знает своих соседей с номерами a, a + 2, a + 4, a + 8, a + 16, ... a + 2k … (узлы пронумерованы в порядке возрастания их идентификаторов). Из перечисленных текущий узлов узел выбирает наиближайший к ключу и посылает ему сообщение. Следующий узел поступает также. В итоге сложность такого алгоритма O(log n).

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

  1. Определить свой идентификатор

  2. Установить связь с узлом, ответственным за ключ с хеш-значением равным идентификатору узла. Этот узел будет одним из ближайших соседей.

  3. Получить всю необходимую информацию от этого узла

  4. Разделение ответственности с соседями

Заметим, что этот алгоритм требует знания адреса хотя бы одного стартового узла системы заранее. На рисунке изображен результат включения нового узла в систему.

d:\private\нир\dht_addnewnode.png

Рис. . Добавление нового узла в систему

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



d:\private\нир\dht_nodefailure.png

Рис. . Отказ узла

Положительные черты DHT


  1. Высокая производительность при работе с объектами с заранее известными идентификаторами

  2. Высокая масштабируемость благодаря автоматическому распределению нагрузки

  3. Устойчивость к отказу узлов благодаря автоматическому распределению и репликации данных. Исключением являются стартовые узлы.

  4. Самоорганизация – нет необходимости в одном центральном узле.

Недостатки DHT


  1. Поиск. Проблемы с поиском являются следствием использования хеш-функции для распределения данных между узлами. К примеру, значения ключей “abc" и “abcd" хранятся на различных узлах. Эффективного алгоритма поиска по DHT не существует.

  2. Проблемы с безопасностью из-за сложности проверки целостности. Также открыт вопрос о безопасной маршрутизации.

2.1.4 Key-Value системы


Key-Value системы в их современном виде достаточно молоды и еще не имеют устоявшегося названия. Часто их также называют DHT (Distributed Hash Table), другое распространенное название – документно-ориентированные БД. Клиентское приложение для такой БД позволяет работать с ней как с простым соответствием ключа значению, что прямо следует из названия. Хотя из термина ‘key-value система’ прямо не следует распределенность системы, но обычно предполагается, что база данных является распределенной. Далее, чтобы избежать путаницы под key-value системой будет пониматься распределенная БД, основанная на DHT и предоставляющая дополнительный функционал работы со значениями, хранящимися в системе. К примеру, некоторые key-value системы поддерживают транзакции и версионирование, что не имеет уже прямого отношения к DHT.

Очевидно, key-value системы обладают всеми преимуществами и недостатками DHT.


  1   2   3


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница