Учебнопрактическое пособие Владимир 2021
 Скачать 7.94 Mb.
|
|
3.2. Системы распределенных вычислений Предпосылками развития систем распределенных вычислений являлись: Высокие требования к вычислительным мощностям для решения определенных задач; Высокая стоимость оборудования, необходимого для со- здания мощных вычислительных систем; Высокая стоимость машинного времени при использова- нии суперкомпьютеров. Решением вышеописанных проблем является использование си- стем распределенных вычислений, в основу которых положен прин- цип разбиения одной задачи на множество подзадач, с решением ко- торых легко справится среднестатистическая система. Данные, под- лежащие обработке, рассылаются по сети, обрабатываются и затем отсылаются на главный сервер, где происходит “сборка” результатов обработки. Преимуществами такого подхода являются: 181 легкая масштабируемость сети; производительность, соизмеримая с производительностью суперкомпьютеров; небольшая сумма вложенных средств. Системы распределенных вычислений применяются: в интернет-проектах, с использованием мощностей персо- нальных компьютеров интернет-пользователей для решения самых разнообразных задач; на уровне локальных сетей, например при сетевом ренде- ринге. Если требуется отрендерить много больших изображений, то данные рассылаются по сети и рендерингом занимаются сетевые компьютеры, а финальная картинка собирается на сервере. История развития систем распределенных вычислений Идея создания систем распределенных вычислений родилась в 1970 году. Первые эксперименты с сетевыми программами вылились в создание первого вируса, распространяющегося по сети под именем Creeper (“Вьюнок”), и последовавшим за ним его убийцы Reaper (“Жнец” или “Потрошитель”). Распространяясь по прародителю со- временного Интернета – сети ARPAnet, обе программки эффективно загружали память сетевых машин и отнимали драгоценное процес- сорное время. В 1973 году детище компании PARC (Xerox Palo Alto Research Center), являвшееся по своей сути первым “червем”, последовательно и обстоятельно загрузило 100 компьютеров в Ethernet-сети компании таким образом, что все свободное (!) процессорное время было отда- но под деятельность червя: создание и рассылку себе подобных. Та- кая на первый взгляд неполезная вещь, как вирус, дала идею для со- здания систем сетевого рендеринга на базе компьютеров Apple. Новый прорыв в области систем распределенных вычислений пришелся на период экспансии сети Интернет в начале 90-х. В первом проекте, получившем широкую огласку, были задействованы не- сколько тысяч компьютеров по всей глобальной Сети. Целью проекта 182 был взлом алгоритма шифрования методом прямого перебора. Но вторым и значительно более популярным проектом стал SETI@home. В дальнейшем возникла идея мета-компьютинга. Термин возник вместе с развитием высокоскоростной сетевой инфраструктуры в начале 90-х годов и относился к объединению нескольких разнород- ных вычислительных ресурсов в локальной сети организации для ре- шения одной задачи. Основная цель построения мета-компьютера в то время заключалась в оптимальном распределении частей работы по вычислительным системам различной архитектуры и различной мощности. В дальнейшем, исследования в области технологий мета- компьютинга были развиты в сторону однородного доступа к вычис- лительным ресурсам большого числа (вплоть до нескольких тысяч) компьютеров в локальной или глобальной сети. Компонентами мета- компьютера могут быть как простейшие ПК, так и мощные массивно- параллельные системы. Что важно, мета-компьютер может не иметь постоянной конфигурации - отдельные компоненты могут включать- ся в его конфигурацию или отключаться от нее; при этом технологии мета-компьютинга обеспечивают непрерывное функционирование системы в целом. Наилучшим образом для решения на мета-компьютерах подхо- дят задачи переборного и поискового типа, где вычислительные узлы практически не взаимодействуют друг с другом и основную часть ра- боты производят в автономном режиме. Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом мета- компьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вы- числительный узел передает обратно отчет о фактически проделан- ном переборе или сигнал о достижении цели поиска. Основные исследовательские проекты в области мета- компьютинга: 1) "Distributed.net". http://www.distributed.net/. 183 Одно из самых больших объединений пользователей Интернет, предоставляющих свои компьютеры для решения крупных перебор- ных задач. Основные проекты связаны с задачами взлома шифров (RSA Challenges). В частности, 19 января 1999 года была решена предложенная RSA Data Security задача расшифровки фразы, закоди- рованной с помощью шифра DES-III. В настоящее время в distributed.net идет работа по расшифровке фразы, закодированной с 64-битным ключом (RC5-64). С момента начала проекта в нем зареги- стрировались 191 тыс. человек. Достигнута скорость перебора, равная 75 млрд. ключей в секунду (всего требуется проверить 264 ключей). За решение этой задачи RSA предлагает приз в $10 тыс. 2) GIMPS – Great Internet Mersenne Prime Search. http://www.mersenne.org/ . Поиск простых чисел Мерсенна (т.е. простых чисел вида 2P-1). С начала проекта было найдено 4 таких простых числа. Организация Electronic Frontier Foundation предлагает приз в $100 тыс. за нахожде- ние простого числа Мерсенна с числом цифр 10 миллионов. 3) Проект SETI@home (Search for Extraterrestrial Intelligence) – поиск внеземных цивилизаций с помощью распределенной обработки данных, поступающих с радиотелескопа. Присоединиться может лю- бой желающий. Доступны клиентские программы для Windows, Mac, UNIX, OS/2 (клиент Windows срабатывает в качестве screen-saver'а). Для участия в проекте зарегистрировались около 920 тыс. человек. 4) Globus. http://www.globus.org. Разработка ПО для организации распределенных вычислений в Интернет. Проект реализуется в Argonne National Lab. Цель The Globus Project – построение т.н. "computational grids", включающих в себя вычислительные системы, системы визуализации, эксперимен- тальные установки. В рамках проекта проводятся исследовании по построению распределенных алгоритмов, обеспечению безопасности и отказоустойчивости мета-компьютеров. 5) Condor. http://www.cs.wisc.edu/condor/ . Система Condor разрабатывается в университете шт. Висконсин (Madison). Condor распределяет независимые подзадачи по суще- 184 ствующей в организации сети рабочих станций, заставляя компьюте- ры работать в свободное время (то есть в то время, когда они проста- ивали бы без своих пользователей). Программное обеспечение систе- мы Condor доступно бесплатно. В настоящее время поддерживаются платформы SGI, Solaris, Linux, HP-UX, и Digital Unix, однако плани- руется также поддержка Windows NT. 3.3. Особенности распределенных баз данных и СУБД Под распределенной базой данных(РБД) обычно подразумевают базу данных, включающую фрагменты из нескольких баз данных, ко- торые располагаются на различных узлах сети компьютеров, и, воз- можно управляются различными СУБД. С точки зрения пользователей и прикладных программ распре- деленная база данных выглядит как обычная локальная БД, ее «рас- пределенность» не заметна извне, она отражает лишь способ органи- зации БД. Кристофер Дейт, специалист в области реляционных баз дан- ных, выявил двенадцать основных свойств распределенных БД: • Локальная автономия (local autonomy); • Независимость узлов (no reliance on central site); • Непрерывные операции (continuous operation); • Прозрачность расположения (location independence); • Прозрачная фрагментация (fragmentation independence); • Прозрачное тиражирование (replication independence); • Обработка распределенных запросов (distributed query processing); • Обработка распределенных транзакций (distributed transaction processing); • Независимость от оборудования (hardware independence); • Независимость от операционных систем (operationg system independence); • Прозрачность сети (network independence); • Независимость от баз данных (database independence). 185 Локальная автономия. Согласно определению Дейта, это свой- ство РБД означает, что, несмотря на общую распределенность БД, управление данными на каждом из узлов выполняется локально. БД, расположенная на одном из элементов системы(узле), в то же время является важным составным элементом распределенной системы (РС). Однако локальная БД может полностью самостоятельно функ- ционировать и работать с данными внутри локального узла системы. Независимость от центрального узла. Если рассматривать иде- альную распределенную БД, то все узлы в такой системе должны яв- ляться независимыми от центрального узла, а каждая локальная БД является равноправным поставщиком данных в общую систему. При этом все БД в данной системе являются «самодостаточными». Непрерывные операции. Это свойство распределенных баз дан- ных заключается в возможности доступа к данным системы в любое время (24 часа в сутки в любой день в году). В идеале предполагают, что доступ к данным осуществляется постоянно, а операции над ними производятся непрерывно. Прозрачность расположения. Несмотря на название (прозрач- ность расположения) это свойство распределенной БД означает, что пользователь не должен ничего знать о физическом месте хранения данных и их расположения в узлах системы. Все запросы к данным осуществляются через прикладные программы по физическим кана- лам связи незаметно для конечного пользователя. Прозрачная фрагментация. Согласно этому свойству, в системе должна быть возможность распределенного размещения данных на разных узлах. Выделяют несколько видов фрагментации: горизон- тальная и вертикальная. При горизонтальной фрагментации строки одной логической таблицы могут храниться в идентичных таблицах на различных узлах РБД. При вертикальной фрагментации по узлам системы ведется распределение столбцов одной логической таблицы. Прозрачность тиражирования. В общем случае, тиражирование – это асинхронный процесс переноса изменений в объектах исходной БД в базы, которые расположены на других узлах РБД. Относительно распределенных баз данных данный аспект означает, что изменения в 186 структуре и содержании БД переносятся в локальные БД невидимо для конечного пользователя. Обработка распределенных запросов. Это свойство РБД тракту- ется как возможность выполнения операций выборки над распреде- ленной базой данных, сформулированных в рамках обычного запроса на языке SQL. То есть операцию выборки из РБД можно сформули- ровать с помощью тех же языковых средств, что и операцию над ло- кальной базой данных. Обработка распределенных транзакций. Это свойство заключа- ется в выполнении операций обновления вставки и удаления, не раз- рушая целостность и согласованность данных в РБД. Чаще всего эта цель достигается применением двухфазового или двухфазного прото- кола фиксации транзакций. Он стал фактическим стандартом обра- ботки распределенных транзакций. Применение данного протокола гарантирует согласованное изменение данных на нескольких узлах системы в рамках распределенной транзакции (ее так же иногда называют глобальной транзакцией). Независимость от оборудования. Согласно этому свойству, в качестве узлов системы могут использоваться компьютеры любых конструкций, как «мейнфреймы», так и обычные персональные ком- пьютеры. Независимость от операционных систем. Это свойство, означает что узлы, входящие в распределенную систему, могут находиться под управлением различных операционных систем. Прозрачность сети. Согласно этому свойству, доступ к любым БД осуществляется посредством сети. При этом перечень сетевых протоколов, поддерживаемых конкретной системой управления база- ми данных, не должен быть ограничением для систем с РБД. Это свойство можно переформулировать следующим образом: в распре- деленной системе возможны любые сетевые протоколы. Независимость от баз данных. Это свойство означает, что в РС могут мирно сосуществовать СУБД различных производителей, и возможны операции поиска и обновления в базах данных различных моделей и форматов. 187 Согласно определению Дэйта, распределенную базу данных можно рассматривать как слабосвязанную сетевую структуру, узлы которой представляют собой локальные базы данных. Локальные ба- зы данных автономны, независимы и самоопределены; доступ к ним обеспечиваются СУБД, в общем случае от различных поставщиков. Технологии распределенных и параллельных баз данных Распределенные и параллельные СУБД предоставляют ту же функциональность, что и централизованные СУБД, если не считать того, что они работают в среде, где данные распределены по узлам компьютерной сети или многопроцессорной системы. Как уже упо- миналось, пользователи могут вообще ничего не знать о распределе- нии данных. Таким образом, эти системы обеспечивают пользовате- лям логически интегрированное представление физически распреде- ленной базы данных. Поддержка подобного представления – источ- ник ряда сложных проблем, которые должны решаться системными функциями. Данный раздел посвящен обсуждению этих проблем. Предполагается, что читатель знаком с основными понятиями баз данных. Архитектурные проблемы Существует множество альтернатив распределенной обработки. Наиболее популярна в настоящее время архитектура клиент-сервер, когда множество машин-клиентов осуществляют доступ к одному серверу баз данных. В таких системах, которые можно определить, как системы типа много-клиентов/один-сервер, проблемы управления базой данных решаются относительно просто, поскольку вся она хра- нится на одном сервере. Задачи, с которыми приходится здесь стал- киваться, – это управление буферами клиентов, кэширование данных и, возможно, блокировки. Управление данными реализуется центра- лизованно на одном сервере. 188 Более распределенной и более гибкой является архитектура ти- па много-клиентов/много-серверов, когда база данных размещена на нескольких серверах, которым, для того чтобы вычислить результат пользовательского запроса или выполнить транзакцию, необходимо взаимодействовать друг с другом. Каждая клиентская машина имеет свой "домашний" сервер; ему она направляет пользовательские за- просы. Взаимодействие серверов друг с другом прозрачно для поль- зователей. В большинстве существующих СУБД реализован один из этих двух типов архитектуры клиент-сервер. В истинно распределенной СУБД клиентские и серверные ма- шины не различаются. В идеале каждый узел может выступать и как клиент, и как сервер. Такие архитектуры, тип которых определяют, как равный-к-равному (peer-to-peer), требуют сложных протоколов управления данными, распределенными по нескольким узлам. Пред- ложение продуктов такого вида задерживается из-за сложности необ- ходимого для их реализации программного обеспечения. Архитектуры параллельных систем варьируются между двумя крайними точками, называемыми архитектура без разделяемых ре- сурсов (shared-nothing) и архитектура с разделяемой памятью (shared- memory). Промежуточную позицию занимает архитектура с разделяе- мыми дисками (shared-disk). При использовании подхода без разделяемых ресурсов каждый процессор имеет мнопольный доступ к собственной оперативной па- мяти и к набору дисков. Таким образом, каждый узел можно рассмат- ривать как локальную машину (со своей базой данной и своим про- граммным обеспечением) в распределенной системе баз данных. Раз- ница между параллельными СУБД без разделяемых ресурсов и рас- пределенными СУБД, по существу, сводится к различию платформ реализации; поэтому большинство решений, разработанных для рас- пределенных баз данных, можно с успехом применять и для парал- лельных баз данных этого типа. Архитектуры без разделяемых ресур- сов обладают тремя важнейшими преимуществами: низкие затраты, расширяемость, высокая доступность. Наиболее существенные харак- 189 терные для них проблемы – сложность реализации и (потенциальные) трудности соблюдения балансировки нагрузки. Подход c разделяемой памятью заключается в том, что каждый процессор посредством быстрых линий связи (высокоскоростных шин или координатных коммутаторов) соединен со всеми модулями памяти и дисковыми устройствами. Две сильные стороны систем с разделяемой памятью – простота и хорошая балансировка нагрузки. Три наиболее существенные проблемы, связанные с этим подходом, – стоимость, ограниченная масштабируемость, невысокая надежность. В системах с разделяемыми дисками каждый процессор имеет доступ к любому дисковому устройству посредством специальных соединений и монопольный доступ к своей собственной оперативной памяти. Таким образом, каждый процессор может прочитать любые страницы базы данных и запомнить их в своем кэше. Во избежание конфликтов при доступе к одним и тем же страницам необходимы механизмы глобального блокирования и протоколы согласования кэшей. Подход, основанный на разделении дисков, имеет следующие преимущества: низкие затраты, масштабируемость, хорошая баланси- ровка нагрузки, высокая доступность, простота миграции с однопро- цессорных систем. В то же время с ними связаны и определенные трудности: сложность системы, потенциальные проблемы производи- тельности. Обработка и оптимизация запросов Обработка запроса (query processing) – это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня. Стандартным языком запросов, поддержи- ваемым современными СУБД, является SQL. Оптимизация запроса (query optimization) – это процедура выбора "наилучшей" стратегии выполнения запроса из множества альтернатив. Для централизованной СУБД весь процесс состоит обычно из двух шагов: декомпозиции запроса (query decomposition) и оптимиза- ции запроса. Декомпозиция запроса – это трансляция его с языка SQL 190 в выражение реляционной алгебры. В ходе декомпозиции запрос под- вергается семантическому анализу; при этом некорректные запросы отвергаются, а корректные упрощаются. Упрощение заключается, в частности, в исключении избыточных предикатов, которые могли быть привнесены за счет использования представлений, а также исхо- дя из ограничений безопасности и семантической целостности. Упрощенный запрос преобразуется в алгебраическую форму. Для заданного SQL-запроса существует более чем одно алгеб- раическое представление, причем некоторые из них могут быть "луч- ше" других. "Качество" алгебраического выражения определяется ис- ходя из объема затрат, необходимых для его вычисления. Традицион- ная процедура состоит в том, чтобы сначала оттранслировать SQL- запрос в какое-нибудь выражение, а затем, применяя правила эквива- лентных алгебраических преобразований, получать из него другие ал- гебраические преобразования, пока не будет найдено "наилучшее". При поиске "наилучшего" выражения используется функция стоимо- сти, в соответствии с которой вычисляется сумма затрат, необходи- мых для выполнения запроса. Этот процесс и называется оптимиза- цией запросов. В распределенной СУБД между шагами декомпозиции и опти- мизации запроса включаются еще два действия: локализация данных (data localization) и глобальная оптимизация запроса (global query optimization). Исходной информацией для локализации данных служит исход- ное алгебраическое выражение, полученное на шаге декомпозиции запроса. В исходном алгебраическом выражении фигурируют гло- бальные отношения без учета их фрагментации или распределения. Основная роль локализации данных заключается в том, чтобы лока- лизовать участвующие в запросе данные, используя информацию об их распределении. На этом шаге выявляются фрагменты, реально участвующие в запросе, и запрос преобразуется к форме, где опера- ции применяются уже не к глобальным отношениям, а к фрагментам. Как отмечалось выше, правила фрагментации выражаются посред- ством реляционных операций (селекции для горизонтальной фраг- 191 ментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагмента- ции. Это называется программой локализации. Программа локализа- ции для горизонтально (вертикально) фрагментированного отноше- ния представляет собой объединение (union) (соединение (join)) соот- ветствующих фрагментов. Таким образом, на шаге локализации дан- ных каждое глобальное отношение запрос заменяется его программой локализации, а затем результирующий фрагментный запрос упроща- ется и реструктурируется с целью получения другого "хорошего" за- проса. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и на шаге декомпози- ции, окончательный запрос над фрагментами может быть еще далек от оптимального; данный процесс лишь исключает "плохие" алгебра- ические запросы. Исходной информацией для третьего шага является фрагмент- ный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации – найти стратегию выполнения запроса, близкую к оптимальной. Напомним, что нахождение оптимальной стратегии – вычислительно трудноразрешимая задача. Стратегию вы- полнения распределенного запроса можно выразить в терминах опе- раций реляционной алгебры и коммуникационных примитивов (опе- раций send/receive), используемых для пересылки данных между уз- лами. На предыдущих шагах запрос уже был в определенной мере оп- тимизирован, в частности, за счет удаления избыточных выражений. Однако проведенная оптимизация не зависела от характеристик фрагментов, например их мощности. Кроме того, на предыдущих ша- гах еще не учитывались коммуникационные операции. Путем изме- нения порядка операций внутри одного фрагментного запроса можно получить много эквивалентных планов его выполнения. Оптимизация запроса заключается в нахождении "наилучшего" плана из множества возможных планов, исследуемых оптимизатором. Оптимизатор запросов обычно представляется в виде трех ком- понентов: пространство поиска, модель стоимости и стратегия поис- ка. Пространство поиска – это множество альтернативных планов вы- 192 полнения исходного запроса. Эти планы эквивалентны в том смысле, что они дают один и тот же результат, но различаются порядком и способами выполнения отдельных операций. Модель стоимости – это способ оценить стоимость данного плана выполнения запроса. Для достижения точности модель стоимости должна основываться на точных знаниях о среде параллельных вычислений. Стратегия поиска – это способ обхода пространства поиска и выбора наилучшего плана. Она определяет, какие планы и в каком порядке следует выбирать и оценивать. В распределенной среде функция стоимости, часто определяе- мая в единицах времени, оценивает затраты вычислительных ресур- сов, таких как дисковое пространство, число обменов с дисками, вре- мя центрального процессора, коммуникации и т.д. Обычно это неко- торая взвешенная сумма затрат ввода-вывода, центрального процес- сора и коммуникаций. В распределенных СУБД применяется упро- щенный подход, когда в качестве наиболее значимых рассматривают- ся лишь коммуникационные затраты. Это справедливо для глобаль- ных сетей, где из-за ограниченной пропускной способности линий связи пересылки данных обходятся значительно дороже, чем при ло- кальной обработке. Чтобы определить порядок выполнения операций, необходимо оценить стоимости выполнения планов с другим поряд- ком операций. Определение стоимости выполнения до реального вы- полнения запроса (статическая оптимизация) основано на статистике фрагментов и формулах для оценки мощности результатов реляцион- ных операций. Таким образом, решения, принимаемые в ходе опти- мизации, зависят от имеющейся статистики фрагментов. Важным аспектом оптимизации запросов является порядок вы- полнения соединений, поскольку его изменение может привести к ускорению на нескольких порядков. Базовый метод оптимизации по- следовательности распределенных операций соединения заключается в применении операции полусоединения (semijoin). Основное пре- имущество полусоединений в распределенной системе – это сокра- щение размеров операндов, участвующих в соединениях, и, следова- тельно, коммуникационных затрат. Однако в более современных ме- 193 тодах, учитывающих, наряду с коммуникационным расходами, также и затраты на локальную обработку, полусоединения не используются, поскольку они приводят к увеличению объема локальной обработки. Результатом работы глобального оптимизатора является оптимизиро- ванное алгебраическое выражение, включающее коммуникационные операции над фрагментами. Параллельная обработка запросов в целом подобна распреде- ленной обработке запросов. Она опирается на преимущества внутри- запросного параллелизма, который обсуждался выше, а также межо- перационного параллелизма. Внутриоперационный (intra-operation) параллелизм достигается за счет выполнения операции сразу на нескольких узлах многопро- цессорной машины. Для этого необходимо предварительное разбие- ние операндов, т.е. их горизонтальная фрагментация по узлам. Спо- соб разделения базового отношения относится к области физического проектирования базы данных. Обычно разделение производится пу- тем применения некоторой хэш-функции к тому атрибуту отношения, который будет часто являться атрибутом соединения. Набор узлов, в которых хранится отношение, называется домашним набором (home). Домашним набором узлов операции (home of an operation) называется набор узлов, в которых она выполняется; оно должно совпадать с до- машним набором узлов ее операндов, чтобы операция имела доступ к своим операндам. Это значит, что для бинарных операций, таких как соединения, может потребоваться переразделение (repartitioning) од- ного из операндов. В некоторых случаях оптимизатор, возможно, со- чтет целесообразным провести переразделение обоих операндов. Для реализации внутриоперационного параллелизма в параллельных СУБД применимы некоторые методы, разработанные для распреде- ленных баз данных. Межоперационный (inter-operation) параллелизм имеет место, когда одновременно выполняются две или более операции, независи- мые или связанные общим потоком данных. Термином поток данных (dataflow) мы обозначаем форму параллелизма, реализуемую метода- ми конвейерной обработки (pipelining). При независимом паралле- 194 лизме операции выполняются одновременно или в произвольном по- рядке. Независимый параллелизм возможен, только если операции не содержат в качестве операндов общих данных. Управление одновременным доступом Если несколько пользователей одновременно (concurrently) осуществляет доступ (на чтение и запись) к совместно используемой базе данных, то для поддержки согласованного состояния данных требуется синхронизовать доступ. Синхронизация достигается путем применения алгоритмов управления одновременным доступом (concurrency control algorithm), гарантирующих следование критери- ям корректности, таким как сериализуемость (serializability). Доступ пользователей к данным инкапсулируются в рамках транзакций, ко- торые на нижнем уровне выглядят как последовательности операций чтения и записи данных. Алгоритмы управления одновременным до- ступом обеспечивают соблюдение свойства изолированности выпол- нения транзакций, которое заключается в том, что воздействия одной транзакции на базу данных не будут зависеть (т.е. будут изолирова- ны) от других транзакций, пока эта первая транзакция не завершит свое выполнение. Наиболее популярные алгоритмы управления одновременным доступом основаны на механизме блокировок. В таких схемах всякий раз, когда транзакция пытается получить доступ к какой-либо едини- це памяти (как правило, странице), на эту единицу накладывается блокировка в одном из режимов – совместном (shared) или моно- польном (exclusive). Блокировки накладываются в соответствии с пра- вилами совместимости блокировок, исключающими конфликты чте- ние-запись, запись-чтение и запись-запись. Согласно известной тео- реме, сериализуемость транзакций заведомо гарантируется, если бло- кировки, относящиеся к одновременно выполняемым транзакциям, удовлетворяют простому правилу: "Ни одна блокировка от имени ка- кой-либо транзакции не должна устанавливаться после снятия хотя бы одной ранее установленной блокировки". Это правило известно 195 под названием двухфазной блокировки [Gray, 1979], поскольку тран- закция проходит при этом сначала фазу "роста", когда она устанавли- вает блокировки, а затем фазу "сжатия", когда блокировки снимают- ся. В общем случае снятие блокировок до завершения транзакции проблематично. Поэтому в большинстве алгоритмов управления од- новременным доступом применяется более жесткий подход, когда блокировки не снимаются до конца транзакции. Для распределенных СУБД возникает проблема распростране- ния свойства сериализуемости и алгоритмов управления одновремен- ным доступом на распределенную среду. В таких системах операции, относящиеся к одной транзакции, могут выполняться на нескольких узлах, где располагаются необходимые данные. В этом случае наибольшую сложность представляет обеспечение сериализуемости. Эта сложность связана с тем, что на разных узлах порядок сериализа- ции одного и того же множества транзакций может оказаться различ- ным. Поэтому выполнение множества распределенных транзакций является сериализуемым тогда и только тогда, когда: 1. Выполнение этого множества транзакций является сериа- лизуемым в каждом узле; 2. Порядок сериализации этих транзакций во всех узлах один и тот же. Алгоритмы управления распределенным одновременным до- ступом поддерживают это свойство, называемое глобальной сериали- зуемостью (global serializability). В алгоритмах, основанных на бло- кировках, для этого применяется один из трех методов: централизо- ванное блокирование, блокирование первичных копий и распреде- ленное блокирование. При централизованном блокировании (centralized locking) для всей распределенной базы данных поддерживается единая таблица блокировок. Эта таблица, располагаемая в одном из узлов, находится под управлением единого менеджера блокировок. Менеджер блоки- ровок отвечает за установку и снятие блокировок от имени транзак- ций. Поскольку управление всеми блокировками сосредоточено на одном узле, то оно аналогично централизованному управлению одно- 196 временным доступом, и глобальная сериализуемость обеспечивается достаточно легко. Соответствующие алгоритмы просты в реализации, но с ними связаны две проблемы. Во-первых, центральный узел мо- жет стать узким местом как из-за большого объема обработки дан- ных, так и из-за генерируемого вокруг него интенсивного сетевого трафика. Во-вторых, надежность такой системы ограничена, посколь- ку отказ или недоступность центрального узла приводит к выходу из строя всей системы. Блокирование первичных копий (primary copy locking) – это ал- горитм управления одновременным доступом, применяемый для баз данных с репликациями, где копии одних и тех же данных могут хра- ниться в нескольких узлах. Одна из таких копий определяется как первичная копия, и для доступа к любому элементу данных необхо- димо установить блокировку на его первичную копию. Множество первичных копий элементов данных известно всем узлам распреде- ленной системы, и запросы транзакций на блокирование направляют- ся в узлы, где хранятся первичные копии. Если в распределенной базе данных репликации не используются, то данный алгоритм сводится к алгоритму распределенного блокирования. Алгоритм блокирования первичных копий был предложен для прототипа распределенной вер- сии Ingres. Алгоритм распределенного (или децентрализованного) блоки- рования (distributed (decentralized) locking), предполагает распределе- ние обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакции необходимо участие и взаим- ная координация менеджеров блокировок в нескольких узлах. Блоки- ровки устанавливаются во всех узлах, данные которых участвуют в транзакции. Алгоритмам распределенного блокирования не свой- ственны издержки механизма централизованного блокирования, свя- занные с перегруженностью центрального узла. Однако алгоритмы этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок, выше. Алгоритмы распреде- ленного блокирования применяются в системах System R* и NonStop SQL. 197 Общий побочный эффект всех алгоритмов управления одновре- менным доступом посредством блокирования – возможность тупико- вых ситуаций (deadlock). Задача обнаружения и преодоления тупиков особенно сложна в распределенных системах. Тем не менее, благода- ря относительной простоте и эффективности алгоритмов блокирова- ния, они имеют значительно большую популярность, чем альтерна- тивные алгоритмы, основанные на временных метках (timestamp- based algorithms), а также алгоритмы оптимистического управления одновременным доступом (optimistic concurrency control). Алгоритмы, основанные на временных метках, выполняют конфликтующие опе- рации транзакций в соответствии с временными метками, назначае- мыми транзакциям при их поступлении в систему. Алгоритмы опти- мистического управления одновременным доступом исходят из пред- положения о том, что конфликты между транзакциями редки, и дово- дят транзакцию до конца, а затем производят проверку корректности. Если выясняется, что фиксация данной транзакции повлечет наруше- ние сериализуемости, то транзакция откатывается и запускается сно- ва. Протоколы обеспечения надежности Как отмечалось выше, распределенные СУБД потенциально бо- лее надежны в силу того, что системные компоненты в них дублиру- ются, и тем самым исключаются одиночные точки отказа. Для реали- зации этого потенциала необходима тщательная проработка структу- ры системы, а также соответствующие протоколы обработки систем- ных сбоев. В распределенной СУБД различаются четыре типа сбоев: сбой транзакции (transaction failure), сбой узла (системы) (site (system) failure), сбой носителя (диска) (media (disk) failure) и сбой коммуни- кационной линии (communication line failure). Причин сбоев транзакции может быть несколько: ошибки, вы- званные неверными входными данными, обнаружение возникшего или возможного тупика. Обычный способ обработки таких сбоев за- 198 ключается в том, чтобы прервать транзакцию и откатить базу данных к состоянию, предшествовавшему началу транзакции. Сбои узлов (систем) могут быть вызваны аппаратными отказами (процессора, оперативной памяти, питания) или программными ошибками (в системном или прикладном коде). Системные сбои при- водят к потере содержимого оперативной памяти. Поэтому в этом случае пропадут все элементы базы данных данных, находящиеся в буферах оперативной памяти (и называемые также неустойчивой ба- зой данных (volatile database)). В то же время данные, находящиеся во вторичной памяти (называемые также стабильной базой данных (stable database)), остаются в сохранности. Для поддержания сохран- ности данных обычно применяют протоколы журнализации (logging protocol), например, журнализация с упреждающей записью (Write- Ahead Logging), которые создают в системных журналах записи обо всех изменениях в базе данных и в подходящие моменты времени пе- ремещают журнальные записи, а также страницы неустойчивой базы данных в стабильную память. В распределенной базе данных пробле- ма системных сбоев выражается еще и в том, что отказавший узел не может участвовать в выполнении какой-либо транзакции. Сбои носителей – это сбои устройств вторичной памяти, на ко- торых хранится стабильная база данных. Обычно эта проблема реша- ется путем дублирования устройств вторичной памяти и поддержки архивных копий базы данных. Сбои носителей рассматриваются обычно как локальная проблема узла, и специальных механизмов для их обработки в распределенных СУБД не предусматривается. Рассмотренные выше три типа сбоев характерны и для центра- лизованных, и для распределенных СУБД. Коммуникационные сбои, напротив, являются специфической проблемой распределенных баз данных. Они подразделяются на несколько разновидностей, наиболее распространенными из которых являются ошибки в сообщениях, нарушение упорядоченности сообщений, потерянные (недоставлен- ные) сообщения, повреждения линий связи. Первые две из них отно- сятся к компетенции сетевых протоколов и не учитываются в реали- зациях распределенных СУБД. Последние же две находятся в ведении 199 СУБД и должны учитываться в протоколах обеспечения надежности. Если один узел ожидает сообщения от другого, а оно не поступает, то причин тому может быть несколько: (а) сообщение утрачено; (b) воз- никло повреждение на линии связи, соединяющей два эти узла; (c) узел, от которого ожидается сообщение, отказал. Таким образом, не всегда возможно отличить коммуникационный сбой от системного. Ожидающий узел по истечении определенного промежутка времени просто решает, что узел-партнер стал недоступен. Протоколы распре- деленных СУБД должны уметь адекватно реагировать на подобные неопределенные ситуации. Серьезным последствием повреждений на линиях связи может стать разделение сети (network partitioning), когда множество узлов распадается на группы, внутри которых имеется связь, а коммуникации между группами невозможны. В такой ситуа- ции исключительно сложно обеспечить доступ пользователей к си- стеме, гарантируя при этом ее согласованность. Протоколы обеспечения надежности поддерживают два свой- ства транзакций: атомарность (atomicity) и долговечность (durability). Атомарность означает, что выполняются либо все действия транзак- ции, либо не выполняется ни одно из них (принцип "все или ничего"). Таким образом, множество операций, составляющих транзакцию, рассматривается как неделимая единица. Атомарность гарантируется даже в условиях возможных отказов. Долговечность означает, что ре- зультат успешно завершенной (зафиксированной) транзакции сохра- няется даже при последующих сбоях. Для обеспечения атомарности и долговечности необходимы атомарные протоколы фиксации (atomic commitment protocol) и про- токолы распределенного восстановления (distributed recovery protocol). Наиболее популярным протоколом атомарной фиксации яв- ляется протокол двухфазной фиксации транзакций (two-phase commit). Протоколы восстановления надстраиваются над протокола- ми локального восстановления, которые зависят от режима взаимо- действия СУБД с операционной системой. Протокол двухфазной фиксации (2PC) – это простой и элегант- ный протокол, обеспечивающий атомарную фиксацию распределен- 200 ной транзакции. Он расширяет реализацию локальной атомарной фиксации на случай распределенной транзакции за счет того, что каждый участвующий в ней узел, прежде чем зафиксировать транзак- цию, подтверждает, что он готов сделать это. В результате на всех уз- лах транзакция заканчивается одинаково (либо фиксируется, либо за- вершается аварийным образом). Если все узлы соглашаются зафикси- ровать транзакцию, то все относящиеся к ней действия реально ока- зывают влияние на базу данных; если один из узлов отказывается за- фиксировать свою часть транзакции, то и все остальные узлы вынуж- даются завершить данную транзакцию аварийным образом. Таким образом, протокол 2PC опирается на следующие фундаментальные правила. 1. Если хотя бы один узел отказывается зафиксировать тран- закцию (голосует за ее аварийное завершение), то распределенная транзакция аварийно завершается во всех участвующих в ней узлах. 2. Если все узлы голосуют за фиксацию транзакции, то она фиксируется во всех участвующих в ней узлах. В простейшем варианте работа 2PC выглядит следующим обра- зом. В узле, где инициируется транзакция, создается процесс- координатор (coordinator); во всех прочих затрагиваемых ею узлах создаются процессы-участники (participant). Вначале координатор рассылает участникам сообщение "приготовиться", и каждый из них независимо решает, может ли транзакция завершиться на данном уз- ле. Участники, которые готовы завершить транзакцию, посылают ко- ординатору сообщение "голосую за фиксацию". Участники, не име- ющие возможности зафиксировать свою часть транзакции, возвра- щают сообщение "голосую за аварийное завершение". Проголосо- вавший участник не может изменить свое решение. Координатор, со- брав голоса участников, решает судьбу транзакции согласно прави- лам 2PC. Если он принимает решение зафиксировать транзакцию, то всем участникам рассылается сообщение "глобальная фиксация". Ес- ли решено завершить транзакцию аварийным образом, то участникам, проголосовавшим за ее фиксацию, посылается сообщение "глобаль- ное аварийное завершение". Участникам, проголосовавшим за преры- 201 вание, сообщение посылать не нужно, поскольку они сами способны принять решение, исходя из правил 2PC. Это называется односторон- ним выбором участником аварийного завершения (unilateral abort option). Протокол предполагает два "раунда" обмена сообщениями меж- ду координатором и участниками, отсюда название 2PC. Имеется не- сколько вариаций классического 2PC, таких как линейный 2PC и рас- пределенный 2PC, не получивших широкого признания среди по- ставщиков распределенных СУБД. Две наиболее важные разновидно- сти протокола – 2PC с предполагаемой фиксацией (presumed commit 2PC) и 2PC с предполагаемым аварийным завершением (presumed abort 2PC) [Mohan and Lindsay, 1983]. Их важность определяется тем, что они позволяют сократить число сообщений, которыми должны обменяться узлы, и число операций ввода-вывода. Протокол с пред- полагаемым прерыванием вошел в стандарт X/Open XA и принят как часть стандарта ISO для открытой распределенной обработки (Open Distributed Processing). Важной характеристикой протокола 2PC является его блокиру- ющий характер. Отказы могут происходить, в частности, на стадии фиксации транзакции. Как уже отмечалось, единственный способом выявления сбоев служит установка таймаутов при ожидание сообще- ния. Если время ожидания исчерпывается, то ожидавший сообщения процесс (координатор или участник) следует протоколу терминиро- вания (termination protocol), который предписывает, что нужно делать с транзакцией, находящейся середине процесса фиксации. Неблоки- рующий протокол фиксации – это такой протокол, терминирующая часть которого при любых обстоятельствах способна определить, что делать с транзакцией в случае сбоя. При использовании 2PC, если в период сбора голосов сбой происходит и на координирующем узле, и на одном из участников, оставшиеся узлы не способны решить между собой судьбу транзакции и вынуждены оставаться в заблокированном состоянии, пока не восстановится либо координатор, либо отказав- ший участник. В этот период невозможно снять установленные тран- закцией блокировки, что снижает доступность базы данных. 202 Предположим, что участник, уже отославший свой голос за фиксацию транзакции, не дождался в течение заданного времени со- общения от координатора об окончательном решении. В этом случае участник находится в состоянии готовности. Вот как выглядит его терминирующий протокол. Во-первых, отметим, что участник не мо- жет в одностороннем порядке принять решение о терминации. Раз он находится в состоянии готовности, то это означает, что ранее он про- голосовал за фиксацию и теперь не имеет права изменить свое реше- ние и завершить транзакцию аварийным образом. Принять односто- роннее решение о фиксации транзакции он также не может, посколь- ку кто-то из участников, возможно, проголосовал против. В такой си- туации участник вынужден оставаться в заблокированном состоянии, пока не узнает от кого-нибудь еще (координатора или других участ- ников) о судьбе данной транзакции. В условиях централизованной коммуникационной структуры, где участники не могут взаимодей- ствовать друг с другом, узел должен ждать сообщения от координа- тора. Поскольку координатор отказал, участник остается заблокиро- ванным. Разумного протокола терминирования в такой модели пред- ложить нельзя. Если участники способны взаимодействовать друг с другом, то можно разработать распределенный протокол терминирования. Участник, который не дождался сообщения от координатора, может просто обратиться за помощью в принятии решения к другим участ- никам. Если в ходе выполнения терминирующего протокола все участники придут к выводу, что отказал только координатор, то они могут избрать в качестве координатора другой узел, где будет переза- пущен процесс фиксации. Однако если отказ произошел не только на координаторе, но и на участнике, то возможна ситуация, когда участ- ник уже успел получить от координатора окончательное решение и завершил транзакцию соответствующим образом. Это решение еще не известно другим участникам, и, если они изберут другого коорди- натора, то есть опасность, что они завершат транзакцию не так, как это сделал отказавший участник. Приведенные примеры иллюстри- руют блокирующий характер 2PC. Предпринимались попытки созда- 203 ния неблокирующих протоколов фиксации (например, протокол трехфазной фиксации), но высокие накладные расходы, связанные с их выполнением, препятствуют их принятию. Обратной стороной терминирования является восстановление. Какие действия должен предпринять восстанавливающийся после сбоя узел, чтобы привести базу данных в согласованное состояние? Это относится к области компетенции протоколов распределенного восстановления. Рассмотрим данную процедуру для приведенного выше примера, когда координирующий узел возобновляет работу по- сле сбоя, и протокол восстановления должен принять решение о том, как следует поступить с транзакцией, которую координировал узел. Возможны следующие случаи. 1. Сбой координатора произошел до начала процедуры фик- сации. Тогда он может начать процесс фиксации после восстановле- ния. 2. Координатор отказал, находясь в состоянии готовности. Это значит, что он уже разослал команду "приготовиться". После вос- становления координатор может перезапустить процедуру фиксации и снова разослать участникам команду "приготовиться". Если участ- ники уже завершили транзакцию, то они сообщают об этом коорди- натору. Если они были заблокированы, то могут вновь отослать коор- динатору свои голоса и возобновить процесс фиксации. 3. Сбой произошел после того, как координатор сообщил участникам о глобальном решении и завершил транзакцию. В этом случае ничего делать не нужно. Протоколы репликации В распределенных базах данных с поддержкой репликации 2 каждому логическому элементу данных соответствует несколько фи- зических копий. Так, размер зарплаты некоторого служащего (логи- ческий элемент данных) может храниться на трех узлах (физические копии). В такого рода системах возникает проблема поддержкой со- гласованности копий. Наиболее известным критерием согласованно- 204 сти является критерий полной эквивалентности копий (one copy equivalence), который требует, чтобы по завершении транзакции все копии логического элемента данных были идентичны. Если поддерживается прозрачность реплицирования, то тран- закция будет выдавать операции чтения-записи, относящиеся к логи- ческому элементу данных x. Протокол управления репликами отвеча- ет за отображение операций над x в операции над физическими копи- ями x (x 1 , x 2 ,..., x n ). Типичный протокол управления репликами, сле- дующий критерию полной эквивалентности копий, известен под названием ROWA (Read-Once/Write-All – чтение из одной копии, за- пись во все копии). Протокол ROWA отображает чтение x [Read(x)] в операцию чтения какой-либо из физических копий x i [Read(x i ). Из ка- кой именно копии будет производиться чтение, неважно – этот во- прос может решаться из соображений эффективности. Каждая опера- ция записи в логический элемент данных x отображается на множе- ство операций записи во все физические копии x. Протокол ROWA прост и прямолинеен, но он требует доступно- сти всех копий элемента данных, чтобы транзакцию можно было тер- минировать. Сбой на одном из узлов приведет к блокированию тран- закции, что снижает доступность базы данных. Было предложено несколько альтернативных алгоритмов, направленных на смягчение требования о том, что для завершения транзакции необходимо внести изменения в каждую копию элемента данных. Все они ослабляют ROWA, сопоставляя операцию записи с некоторым подмножеством физических копий. Идея, согласно которой для завершения транзакции достаточно модифицировать некоторое подмножество копий, легла в основу ме- ханизма голосования на основе кворума, используемого в протоколах управления репликами. Алгоритм консенсуса большинства можно сформулировать немного с другой точки зрения: каждой копии дан- ных приписывается одно и то же число голосов, и транзакция, изме- няющая логический элемент данных, может успешно завершиться, если она наберет большинство голосов. На той же идее основан ран- ний алгоритм голосования на основе кворума (quorum-based voting 205 algorithm) [Gifford, 1979], который также присваивает копиям данных (возможно, не одно и то же) число голосов. Для выполнения любой операции чтения или записи элемента данных требуется получить кворум чтения (read quorum) (V r ) или кворум записи (write quorum) (V w ). Если элемент данных имеет в сумме V голосов, то при опреде- лении кворумов должны соблюдаться следующие правила. 1. V r + V w > V (две транзакции не могут одновременно читать и модифицировать один и тот же элемент данных во избежание кон- фликта чтение-запись); 2. V w > V/2 (две транзакции не могут одновременно производить запись одного и того же элемента данных во избежание конфликта запись-запись). Проблема, присущая этому подходу, состоит в том, что транзак- ция должна набрать кворум даже для чтения. Из-за этого существенно и неоправданно замедляется доступ к базе данных на чтение. Был предложен альтернативный протокол голосования на базе кворума, где этот серьезный недостаток преодолевается [Abbadi et al., 1985]. Однако этот протокол исходит из совершенно нереалистичных пред- положений о свойствах коммуникационной системы. Базовые требо- вания состоят в том, что всем узлам немедленно становится известно об отказах, приводящих к изменениям в топологии сети, и каждый узел располагает представлением той части сети, где содержатся уз- лы, с которыми он взаимодействует. В общем случае невозможно га- рантировать выполнимость этих требований. Таким образом, прото- кол полной эквивалентности копий является ограничительным с точ- ки зрения доступности системы, а протоколы, основанные на голосо- вании, слишком сложны, и с ними связаны высокие накладные расхо- ды. Поэтому в современных промышленных распределенных СУБД ни один из этих методов не используется. Для практического приме- нения были исследованы некоторые более гибкие технологии репли- каций, где тип согласования копий находится под контролем пользо- вателя. На основе этого принципа уже создано или создается не- сколько разновидностей серверов репликации. К сожалению, в насто- ящее время не существует стройной теории, которая бы позволяла 206 судить о согласованности реплицированной базы данных в условиях, когда применяются относительно нестрогие политики репликаций. Исследования в этой области находятся лишь в зачаточном состоя- нии. Теорема САР Теорема CAP (известная также как теорема Брюера) — эвристи- ческое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств: согласованность данных (англ. consistency) — во всех вы- числительных узлах в один момент времени данные не противоречат друг другу; доступность (англ. availability) — любой запрос к распре- делённой системе завершается корректным откликом, однако без га- рантии, что ответы всех узлов системы совпадают; устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций. Акроним CAP в наименовании теоремы сформирован из первых букв английских наименований этих трёх свойств. Принцип был предложен профессором Калифорнийского уни- верситета в Беркли Эриком Брюером в июле 2000 года и впослед- ствии получил широкую популярность и признание в среде специали- стов по распределённым вычислениям. Концепция NoSQL, в рамках которой создаются распределённые нетранзакционные системы управления базами данных, зачастую использует этот принцип в ка- честве обоснования неизбежности отказа от согласованности данных. С точки зрения теоремы CAP, распределённые системы в зави- симости от пары практически поддерживаемых свойств из трёх воз- можных распадаются на три класса — CA, CP, AP. В системе класса CA во всех узлах данные согласованы и обес- печена доступность, при этом она жертвует устойчивостью к распаду 207 на секции. Такие системы возможны на основе технологического программного обеспечения, поддерживающего транзакционность в смысле ACID, примерами таких систем могут быть решения на осно- ве кластерных систем управления базами данных или распределённая служба каталогов LDAP. Система класса CP в каждый момент обеспечивает целостный результат и способна функционировать в условиях распада, но дости- гает этого в ущерб доступности: может не выдавать отклик на запрос. Устойчивость к распаду на секции требует обеспечения дублирования изменений во всех узлах системы, в связи с этим отмечается практи- ческая целесообразность использования в таких системах распреде- лённых пессимистических блокировок для сохранения целостности. В системе класса AP не гарантируется целостность, но при этом выполнены условия доступности и устойчивости к распаду на секции. Хотя системы такого рода известны задолго до формулировки прин- ципа CAP (например, распределённые веб-кэши или DNS), рост по- пулярности решений с этим набором свойств связывается именно с распространением теоремы CAP. Так, большинство NoSQL-систем принципиально не гарантируют целостности данных, и ссылаются на теорему CAP как на мотив такого ограничения. Задачей при построе- нии AP-систем становится обеспечение некоторого практически це- лесообразного уровня целостности данных, в этом смысле про AP- системы говорят, как о «целостных в конечном итоге» (англ. eventually consistent) или как о «слабо целостных» (англ. weak consistent). Во второй половине 2000-х годов сформулирован подход к по- строению распределённых систем, в которых требования целостности и доступности выполнены не в полной мере, названый акронимом BASE (от англ. Basically Available, Soft-state, Eventually consistent — базовая доступность, неустойчивое состояние, согласованность в ко- нечном счёте), при этом такой подход напрямую противопоставляется ACID. Под базовой доступностью подразумевается такой подход к проектированию приложения, чтобы сбой в некоторых узлах приво- дил к отказу в обслуживании только для незначительной части сессий 208 при сохранении доступности в большинстве случаев. Неустойчивое состояние подразумевает возможность жертвовать долговременным хранением состояния сессий (таких как промежуточные результаты выборок, информация о навигации, контексте), при этом концентри- руясь на фиксации обновлений только критичных операций. Согласо- ванности в конечном счёте, трактующейся как возможность противо- речивости данных в некоторых случаях, но при обеспечении согласо- вания в практически обозримое время, посвящено значительное ко- личество самостоятельных исследований. |