LS-Sb90335

МИНОБРНАУКИ РОССИИ

–––––––––––––––––––––––––––––––––

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

–––––––––––––––––––––––––––––––––––––––

А. В. БОГДАНОВ Е. Н. СТАНКОВА ТХУРЕИН КИАВ ЛИН

РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ

Учебное пособие

Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ»

2013

УДК 004.65 ББК 32.973

В24

Богданов А. В., Станкова Е. Н., Тхурейн Киав Лин

В24 Распределенные базы данных: Учеб. пособие. СПб.: Изд-во СПбГЭТУ

«ЛЭТИ», 2013. 48 с.

ISBN 978-5-7629-1417-8

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

Предназначено для магистров, обучающихся по программе «Распределенные интеллектуальные системы и технологии».

УДК 004.65 ББК 32.973

Рецензенты: проф. С. Н. Андрианов – зав. каф. КМ и МС (СПбГУ);

канд.техн. наук В. П. Руковчук – ген. дир. «Computational Servies Alliance»

Утверждено редакционно-издательским советом университета

в качестве учебного пособия

ISBN 978-5-7629-1417-8	© СПбГЭТУ «ЛЭТИ», 2013
	2

ПРЕДИСЛОВИЕ

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

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

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

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

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

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

Системы докуметооборота, системы ECM (Enterprise Content Management), ERP (Enterprise Resourse Planning) и BPM (Business Process Management)

строятся на основе современных производительных баз и хранилищ данных и требуют развитых средств для их (данных) оперативного анализа.

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

3

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

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

1. ЭВОЛЮЦИЯ ПРИНЦИПОВ ОБРАБОТКИ ДАННЫХ

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

Развитие принципов обработки данных можно разделить на несколько этапов.

1.Обрабатываемые данные – часть программы. Сначала данные входили

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

4

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

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

3. Перенос описания данных в массив данных (полная независимость от программы) – базы данных (БД).

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

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

Работа с данными в файловой системе предполагает установление связи между именем файла и адресом данных; в базе данных управление информацией осуществляется на содержательном уровне: устанавливается связь между содержанием и адресом данных.

Кроме того, базы данных позволяют интегрировать данные многих приложений, но одного назначения, а также восстанавливать данные после технических сбоев.

Если в файловых системах общий доступ к файлу является проблемой, то базы данных предназначены для совместного использования многими

5

пользователями единожды введенных данных.

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

Основным принципом организации баз данных является совместное хранение данных и их описания (метаданных). Метаданные хранятся в той части базы данных, которая называется каталогом или словаремсправочником данных (ССД), и позволяет запрашивать и изменять данные без написания дополнительных программ.

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

ианализа. Основными функциями СУБД являются:

−непосредственное управление данными во внешней памяти;

−управление транзакциями;

−журнализация – ведение журнала изменений БД для обеспечения надежности хранения данных во внешней памяти;

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

−обеспечение доступа к информации, расположенной в БД.

Первые СУБД появились в 60-е гг. ХХ в. К настоящему времени разработано огромное количество СУБД, основанных на различных принципах организации структуры данных и способах манипулирования ими.

Обычно выделяют два этапа развития (два поколения) СУБД. К первому поколению (60-е – начало 70-х гг. XX в.) относят иерархические и сетевые СУБД, ко второму – реляционные.

Однако в настоящее время объективно реализуется третье поколение СУБД, которое можно обобщенно назвать постреляционным, хотя к нему можно отнести не только те СУБД, которые обычно называют постреляционными (объектно-реляционные СУБД, многомерные базы данных), но и СУБД, основанные на концепции NoSQL (no-SQL или Not Only SQL), к которым обычно причисляют графовые, документоориентированные, а также

6

базы данных ключ-значение. К постреляционным можно условно отнести и объектно-ориентированные СУБД.

В настоящее время перед разработчиками СУБД стоят следующие вызовы:

−создание оптимальных архитектур для хранения и обработки сверхбольших объемов распределенных данных;

−размещение баз данных и СУБД на гетерогенных аппаратных комплексах, которые организуются по иерархическому признаку.

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

−нулевой уровень – Grid система, состоящая из связанных гетерогенных вычислительных систем;

−первый уровень – многопроцессорная система (набор однородных вычислительных модулей, соединенных высокоскоростной сетью);

−второй уровень – вычислительный модуль (многопроцессорная система с разделяемой памятью);

−третий уровень – многоядерный процессор.

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

2. КЛАССИФИКАЦИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ НА ОСНОВЕ ТЕОРЕМЫ CAP (ТЕОРЕМЫ БРЮЕРА)

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

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

7

сделать распределенность прозрачной (для конечного пользователя РаспБД должна выглядеть как нераспределенная система).

В июле 2000 г. профессор Калифорнийского университета в Беркли Эрик Брюер сформулировал принцип, касающийся ключевых свойств распределенных систем, который впоследствии был назван теоремой CAP (Consistency-Availability-Partition tolerance) или теоремой Брюера.

Сформулировать теорему можно следующим образом: в любой распределенной системе возможно реализовать обеспечение не более двух из трех следующих свойств: согласованность данных (consistency), доступность

(availability) и устойчивость к сбоям узлов (partition tolerance). Рассмотрим все три свойства подробнее.

Согласованность данных подразумевает, что во всех вычислительных узлах в один и тот же момент времени данные не противоречат друг другу. В дальнейшем при математическом обосновании теоремы CAP «согласованность» в смысле теоремы CAP была соотнесена с выполнением первых двух требований ACID1 – атомарности и согласованности.

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

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

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

В реальности можно построить распределенную систему, реализующую только два из трех указанных свойств – одним обязательно приходится пожертвовать. Рассмотрим эти системы.

Системы CP (Consistency + Partition tolerance). Система состоит из не-

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

1 Акроним ACID описывает требования к транзакционной системе (например, к СУБД), обеспечивающие наиболее надежную и предсказуемую ее работу. Требования

ACID: Atomicity – Атомарность, Consistency – Согласованность, Isolation – Изолирован-

ность, Durability – Надежность.

8

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

Системы CA – это системы, во всех узлах которых данные согласованы и обеспечена доступность, но недостижима устойчивость к сбою отдельных узлов. Такие системы рассчитаны на то, что сеть абсолютно надежна и, благодаря этому, может обеспечить согласованность данных на всех работающих узлах. В вырожденном случае, когда система СА состоит из одного узла, несогласованности данных быть не может, и она доступна всегда, когда доступен ее узел. Другими словами, на практике таких систем или не существует, или они не являются распределенными.

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

В противопоставление ACID был сформулирован подход BASE (Basically Available, Soft-state, Eventually consistent). Он допускает, что распределен-

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

9

гласованность же должна обеспечиваться на конечном этапе, достигаемом в практически обозримое время.

Ксистемам типа CP относят распределенные реляционные базы данных,

ксистемам АP – базы данных, основанные на концепции NoSQL. Остановимся подробно на обоих типах распределенных систем.

2.1. Реляционные базы данных (РБД)

Реляционные базы данных строятся на так называемой реляционной модели данных (РМД). Под моделью данных обычно понимают формальное описание структуры, методов манипулирования и способов оценки целостности данных.

Реляционная модель является наиболее широко распространенной и единственной, для которой разработан теоретический базис с использованием теории множеств. Она была предложена математиком Эдгаром Коддом (Codd E. F.) в 1970 г. и с тех пор является доминирующей.

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

Если в качестве примера рассмотреть домены – « множество должностей», «множество окладов» и «множество надбавок», то штатное расписание, в котором каждой должности будут соотвествовать определенные (но не все возможные) значения окладов и надбавок, будет являться отношением, т. е. подмножеством декартова произведения этих доменов.

Отношение удобно представлять как таблицу, в которой каждый столбец является доменом, а строка – записью (кортежем). Каждый кортеж соответствует одному экземпляру данных, характеризуемых набором определенных свойств – атрибутов. Атрибуты являются элементами кортежа (полями таблицы). Например, рассмотрим отношение (таблицу) «Студенты». В качестве доменов этой таблицы будем рассматривать столбцы: (фамилия, имя, отчество, № зачетной книжки, № группы, дата рождения). Строки таблицы (кор-

10