Файл: Учебнопрактическое пособие Владимир 2021.pdf

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) для всей распределенной базы данных поддерживается единая таблица блокировок. Эта таблица, располагаемая в одном из узлов, находится под управлением единого менеджера блокировок. Менеджер блоки- ровок отвечает за установку и снятие блокировок от имени транзак- ций. Поскольку управление всеми блокировками сосредоточено на одном узле, то оно аналогично централизованному управлению одно-