Распределенные и параллельные СУБД
Авторы: M. TAMER OZSU, PATRICK VALDURIEZ
Перевод: Сербин О.Н.
Оригинал: http://www.geocities.ws/dfajardod/articulos/p125-ozsu5.pdf
Авторы: M. TAMER OZSU, PATRICK VALDURIEZ
Перевод: Сербин О.Н.
Оригинал: http://www.geocities.ws/dfajardod/articulos/p125-ozsu5.pdf
Возникновение технологии систем управления базами данных (СУБД) совпало со значительными событиями в развитии распределенных вычислений и параллельных технологий обработки. Конечным результатом является появление распределенных и параллельных систем управления базами. Эти системы стали доминирующими инструментами управления данными для очень ресурсоемких приложений.
Распределенная база данных (РБД, DDB – A distributed database) представляет собой набор из нескольких, логически взаимосвязанных баз данных, распределенных по компьютерной сети. Распределенная система управления базами данных (распределенная СУБД) определяется как программная система, которая позволяет управлять распределенными базами данных и делает распределение прозрачно для пользователей [Ozsu и Valduriez 1991].
Существует множество возможных альтернативных реализаций распределенной СУБД. Архитектуры типа «клиент/сервер» [Orfali соавт.1994], где несколько клиентов имеют доступ к одному серверу баз данных, являются самыми простыми. Архитектуры типа «множество клиентов / множество серверов» являются более гибкими, потому что база данных распределена по нескольким серверам. Каждая клиентская машина имеет «домашний» сервер, на который она направляет запросы пользователей. Связи между серверами для выполнения пользовательских запросов и обменов являются прозрачными для пользователей. Большинство современных систем управления базами данных реализуют оба типа клиент-серверной архитектуры.
По-настоящему распределенная СУБД не делает различия между клиентскими и серверными машинами. В идеальном случае каждый сайт может выполнять функциональность клиента и сервера. Такая архитектура, называемая peer-to-peer (PtP), требует сложных протоколов для управления данными, распределенными по нескольким сайтам. Сложность необходимого программного обеспечения задержала рост использования peer-to-peer распределенных СУБД.
База данных физически распределены между сайтами путем фрагментации и репликации данных. Учитывая схему реляционной базы данных, фрагментация подразделяет каждое соотношение в горизонтальные (по выбору эксплуатации) или вертикальные (по проекту эксплуатации) разделы. Фрагментации желательны, поскольку они делают возможными размещение данных в непосредственной близости от места их использования, что потенциально снижает стоимость передачи и уменьшает размер участвующих пользовательских запросов.
На основании паттернов пользовательского доступа, каждый из фрагментов также может быть дублирован. Это предпочтительно, когда одни и те же данные доступны из приложений, работающих на множестве сайтов. В этом случае это может быть экономически более эффективным – дублировать данные на множество сайтов, а не непрерывно передавать их между ними.
Параллельные СУБД [Valduriez 1993] могут быть определены, как СУБД, реализованные на тесно связанных многопроцессорных системах. Различия между параллельными и распределенными СУБД несколько неясны. В частности, нераспределенные параллельные архитектуры СУБД, которые мы обсудим далее, не очень похожи на слабо взаимосвязанных распределенных систем. Возможно, важным отличием является то, что распределенные СУБД используются в системах со слабой связью между процессорами, которые имеют свои собственные операционные системы и работают самостоятельно. Параллельные СУБД используют современные компьютерные многопроцессорные архитектуры в целях создания высокой производительности и высокой доступности серверов баз данных при более низкой цене, чем эквивалентные мейнфреймы.
Системы с параллельными архитектурами разделяются по двум особенностям – без совместного использования ресурсов, с разделяемой памятью и с общим диском. В типе архитектуры «без совместного использования», каждый процессор имеет эксклюзивный доступ к своей основной памяти и дисковому блоку. Таким образом, каждый узел можно рассматривать как локальный участок (с собственной базой данных и программным обеспечением) в распределенной СУБД. В архитектуре «с общей памятью» любой процессор имеет доступ к любому модулю памяти или дисковому устройству через быстрое соединение (например, высокоскоростная шина). В архитектуре «с общим диском» любой процессор имеет доступ к любому диску устройства через соединение, однако имеет эксклюзивный (не общий) доступ к основной памяти. Каждый процессор может получить доступ к базе данных на общем диске и скопировать данные в свой собственный кэш. Для исключения конфликта доступа к одной и той же странице используются протоколы, поддерживающие когерентность кэша.
Распределенные и параллельные СУБД обеспечивают такую же функциональность, как и централизованные СУБД в среде, где данные распределены по различным местам в компьютерной сети или между узлами многопроцессорной системы. Эта функциональность обеспечивается прозрачно, поэтому пользователи не должны беспокоиться о распределении данных, фрагментации и репликации. Поддержание этой точки зрения ставит серьезные проблемы на системные функции, которые мы определим в дальнейшем.
В распределенной СУБД, обработка запросов и методы оптимизации должны решать трудности, возникающие из-за фрагментации и распределения данных. Для решения проблемы фрагментации, методы локализации данных используются тогда, когда алгебраические запросы, указанные на глобальных уровнях, превращаются в одну компоненту, которая работает на фрагментном уровне, а не глобальном. В процессе, возможности для параллельного выполнения идентифицированы (потому что фрагменты хранятся в разных местах) и ненужная работа устранена (потому что некоторые из фрагментов не участвуют в запросе). Локализация требует оптимизации глобальных операций, которая осуществляется в рамках глобальной оптимизации запроса. Глобальная оптимизация запроса подразумевает перестановку порядка операций в запросе, определения мест для выполнения различных распределенных операций, а также выявления лучших алгоритмов распределенного выполнения распределенных операций (особенно операции соединения).
Оптимизация параллельных запросов использует преимущества как внутриоперационной параллельности, так и межоперационного параллелизма. Внутриоперационный параллелизм достигается за счет выполнения операции на нескольких узлах многопроцессорной машины. Оптимизация использования внутриоперационного параллелизма может использовать некоторые из методов, разработанных для распределенных баз данных. Inter-операция параллелизма происходит, когда две или более операции выполняются параллельно, либо в виде потока данных, либо независимо друг от друга. Мы обозначаем поток данных, как форму параллелизма. Независимый параллелизм происходит, когда операции выполняются одновременно или в произвольном порядке. Независимый параллелизм возможен только при операции, не связанной с теми же данными.
В распределенных СУБД проблема в синхронизации параллельных транзакций пользователей является расширением аргумента сериализуемости и алгоритмов управления одновременным исполнением транзакций распределенной среды. В этих системах операции могут выполняться на нескольких площадках, где они получают доступ к данным. Таким образом, глобальная сериализуемость требует:
(а) выполнение сериализации множества операций на каждом участке и
(б) сериализации идентичного порядка этих операций на всех сайтах.
Если на основе этих алгоритмов используется залочивание (locking), блокировка таблиц и управление этими блокировками может быть централизованным или распределенным.
В дополнение к транзакции, системные сбои носителей, которые могут возникнуть в централизованной СУБД, распределенная СУБД должна также защищать данные, вплоть до обрыва связи. В частности, наличие системных и коммуникационных сбоев представляет осложнения, потому что не всегда возможно провести различие между ними. Распределенная СУБД позволяет разрешать эту неопределенность.
Протоколы надежности распределенного обмена соблюдают атомарность (all-or-nothing property) транзакций по реализации атомных протоколов, таких как протокл двухфазной фиксации (2PC) [Gray 1979]. 2PC распространяет действие локальной атомной организации операций распределенных транзакций, определяя то, что все сайты, участвующие в выполнении распределенных транзакций, согласны совершить транзакцию, прежде чем её последствия становятся постоянными (то есть все сайты расторгнут транзакцию в том же порядке).
Обратной является операция восстановления. Протоколы распределенного восстановления справляются с проблемой восстановления данных на сайте, когда не удалось выполнить транзакцию и необходимо этот сайт восстановить после сбоя.
В репликации распределенных баз данных каждый логический элемент данных имеет ряд физических свойств. Проблемой в этом типе систем баз данных является поддержание некоторого представления о последовательности физических копий, например, когда пользователь прозрачно обновляет логические элементы данных. Простым критерием согласованности является эквивалентность одной копии, которая утверждает, что значения всех физических копий логического элемента данных должны быть идентичны, когда транзакция завершается. Типичные протоколы репликации контролируют одну копию сериализуемости, известную как Read-One/Write-All (ROWA) протокол. ROWA протокол прост и прямолинеен, но он требует, чтобы все копии всех логических элементов данных, которые обновляются в транзакции, были доступны при остановке транзакции. Выход из строя одного сайта может заблокировать транзакцию и снизит доступность баз данных.
Был предложен ряд альтернативных алгоритмов, которые снижают требования в завершении транзакции при обновлении всех копий логических элементов. Они ослабляют ROWA путем отображения в каждой записи только подмножества физических копий. Один известный подход базируется на основе голосования, при котором копии присваиваются голоса и операции чтения и записи должны собрать голоса при достижении кворума для чтения / записи данных.
Технологии распределенных и параллельных СУБД развились до такой степени, что достаточно сложные и надежные коммерческие системы стали доступными. Как и ожидалось, ряд вопросов до сих пор не решен. Они касаются разногласиями при размещении данных в параллельных СУБД, сетевых проблем масштабирования (в частности, калибровки распределенной СУБД для конкретных характеристик новых коммуникационных технологий, таких как широкополосный доступ в сетях и мобильных и сотовых сетей), передовые модели транзакций (в настоящее время обычно называются рабочим процессом) [Elmagarmid 1992], мультисистем, их взаимодействия [Sheth и Larson 1990] и распределенных объектов управления [Dogac соавт. 1994; Ozsu соавт. 1994 год].