Распределение данных по сети

Распределенная база данных – это совокупность логически взаимосвязанных баз данных, распределенных в компьютерной сети. Распределенная система управления базой данных определяется как программная система, которая позволяет управлять распределенной базой данных таким образом, чтобы ее распределенность была прозрачна для пользователей. В этом определении следует уточнить две отличительных архитектурных особенности. Первая из них заключается в том, что система состоит из (возможно, пустого) множества узлов приема запросов (query site) и непустого множества узлов данных (data site). Узлы данных обладают средствами для хранения данных, а узлы приема запросов – нет. В узлах приема запросов лишь выполняются программы, реализующие пользовательский интерфейс для доступа к данным, хранящимся в узлах данных. Вторая особенность состоит в том, что узлы логически представляют собой независимые компьютеры. Следовательно, у такого узла имеется собственная основная и внешняя память, установлена собственная операционная система (может быть, одна и та же на всех узлах, а возможно, и нет) и имеется возможность выполнять приложения. Узлы связаны компьютерной сетью, а не входят в мультипроцессорную конфигурацию. Важно подчеркнуть слабую связанность процессоров, которые обладают собственными операционными системами и функционирует независимо.

Основная задача при проектировании распределенной БД - распределение данных по сети. Способы решения этой задачи:

Распределенная обработка данных требует решения вопросов:

Рассмотрим архитектуру однородных распределенных БД.

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

Поддержание копий данных в нескольких узлах сети

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

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

Фрагментация объектов БД

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

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

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

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

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

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

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

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

В то же время недостатки рассматриваемой стратегии связаны именно с локальным расположением данных. Естественно, что объем базы данных ограничен емкостью запоминающих устройств центрального узла. К тому же запросы на операции над данными должны направляться только в этот узел со всеми вытекающими транспортными издержками. Центральный узел становится узким местом всей сети по следующим причинам: Во-первых, скорость обработки данных ограничивается его быстродействием; во-вторых, БД становится недоступной для других узлов при появлении неисправностей в сети передачи данных и полностью отказывает при выходе из строя центрального узла.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткая характеристика этапов проектирования РБД

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глобальный логический уровень представления данных. Этот уровень подобен концептуальному уровню представления концепции ANSI. Используется для описания логической структуры всей распределенной базы данных, то есть в представлении администратора РБД. При описании РБД этому уровню ставится в соответствие глобальная представляющая схема. Существование третьего и четвертого уровней объясняется распределенной природой РБД.

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

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

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

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

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

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

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

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

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

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

Выводы