Исследовательские проблемы - Distributed and parallel database systems

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

...

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

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

Для обеспечения атомарности и долговечности необходимы атомарные протоколы фиксации (atomic commitment protocol) и протоколы распределенного восстановления (distributed recovery protocol) . Наиболее популярным протоколом атомарной фиксации является протокол двухфазной фиксации транзакций (two-phase commit) . Протоколы восстановления надстраиваются над протоколами локального восстановления, которые зависят от режима взаимодействия СУБД с операционной системой.

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

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

В простейшем варианте работа 2PC выглядит следующим образом. В узле, где инициируется транзакция, создается процесс- координатор (coordinator) ; во всех прочих затрагиваемых ею узлах создаются процессы- участники (participant) . Вначале координатор рассылает участникам сообщение "приготовиться", и каждый из них независимо решает, может ли транзакция завершиться на данном узле. Участники, которые готовы завершить транзакцию, посылают координатору сообщение "голосую за фиксацию". Участники, не имеющие возможности зафиксировать свою часть транзакции, возвращают сообщение "голосую за аварийное завершение". Проголосовавший участник не может изменить свое решение. Координатор, собрав голоса участников, решает судьбу транзакции согласно правилам 2PC. Если он принимает решение зафиксировать транзакцию, то всем участникам рассылается сообщение "глобальная фиксация". Если решено завершить транзакцию аварийным образом, то участникам, проголосовавшим за ее фиксацию, посылается сообщение "глобальное аварийное завершение". Участникам, проголосовавшим за прерывание, сообщение посылать не нужно, поскольку они сами способны принять решение, исходя из правил 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, если в период сбора голосов сбой происходит и на координирующем узле, и на одном из участников, оставшиеся узлы не способны решить между собой судьбу транзакции и вынуждены оставаться в заблокированном состоянии, пока не восстановится либо координатор, либо отказавший участник. В этот период невозможно снять установленные транзакцией блокировки, что снижает доступность базы данных.

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

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

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

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

Протоколы репликации

В распределенных базах данных с поддержкой репликации ²⁾ каждому логическому элементу данных соответствует несколько физических копий. Так, размер зарплаты некоторого служащего ( логический элемент данных ) может храниться на трех узлах ( физические копии ). В такого рода системах возникает проблема поддержкой согласованности копий. Наиболее известным критерием согласованности является критерий полной эквивалентности копий (one copy equivalence) , который требует, чтобы по завершении транзакции все копии логического элемента данных были идентичны.

Если поддерживается прозрачность реплицирования, то транзакция будет выдавать операции чтения-записи, относящиеся к логическому элементу данных x . Протокол управления репликами отвечает за отображение операций над x в операции над физическими копиями x ( x ₁ , x ₂ ,..., x _n ). Типичный протокол управления репликами, следующий критерию полной эквивалентности копий, известен под названием ROWA ( Read-Once/Write-All – чтение из одной копии, запись во все копии). Протокол ROWA отображает чтение x [Read( x )] в операцию чтения какой-либо из физических копий x _i [Read( x _i ). Из какой именно копии будет производиться чтение, неважно – этот вопрос может решаться из соображений эффективности. Каждая операция записи в логический элемент данных x отображается на множество операций записи во все физические копии x .

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

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

Идея, согласно которой для завершения транзакции достаточно модифицировать некоторое подмножество копий, легла в основу механизма голосования на основе кворума, используемого в протоколах управления репликами. Алгоритм консенсуса большинства можно сформулировать немного с другой точки зрения: каждой копии данных приписывается одно и то же число голосов, и транзакция, изменяющая логический элемент данных, может успешно завершиться, если она наберет большинство голосов. На той же идее основан ранний алгоритм голосования на основе кворума (quorum-based voting 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]. Однако этот протокол исходит из совершенно нереалистичных предположений о свойствах коммуникационной системы. Базовые требования состоят в том, что всем узлам немедленно становится известно об отказах, приводящих к изменениям в топологии сети, и каждый узел располагает представлением той части сети, где содержатся узлы, с которыми он взаимодействует. В общем случае невозможно гарантировать выполнимость этих требований. Таким образом, протокол полной эквивалентности копий является ограничительным с точки зрения доступности системы, а протоколы, основанные на голосовании, слишком сложны, и с ними связаны высокие накладные расходы. Поэтому в современных промышленных распределенных СУБД ни один из этих методов не используется. Для практического применения были исследованы некоторые более гибкие технологии репликаций, где тип согласования копий находится под контролем пользователя. На основе этого принципа уже создано или создается несколько разновидностей серверов репликации . К сожалению, в настоящее время не существует стройной теории, которая бы позволяла судить о согласованности реплицированной базы данных в условиях, когда применяются относительно нестрогие политики репликаций. Исследования в этой области находятся лишь в зачаточном состоянии.

Исследовательские проблемы

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

Размещение данных

В параллельной системе баз данных правильное размещение данных имеет решающее значение для обеспечения балансировки нагрузки. В идеале можно полностью избежать интерференции между одновременно выполняемыми параллельными операциями, если каждая из них будет работать с независимым набором данных. Независимые наборы данных получаются путем декластеризации (declustering) (горизонтального разделения) отношений на основе функции (хэш-функции или интервального индекса), применяемой к одному или более атрибутам, и размещения каждого раздела на отдельном диске. Как и в случае горизонтальной фрагментации в распределенных базах данных, декластеризация полезна для достижения межзапросного параллелизма, когда независимые запросы работают с разными фрагментами, а также внутризапросного параллелизма, когда операции, относящиеся к одному запросу, выполняются одновременно над различными фрагментами. Декластеризация может проводиться по одному или по нескольким атрибутам. В последнем случае [Ghandeharizadeh et al., 1992] запрос с условием сравнения по равенству для этих атрибутов может обрабатываться в одном узле без коммуникаций с другими узлами. Выбор между хэшированием и интервальной индексацией делается на этапе проектирования: хэширование требует меньше памяти, но поддерживает только запросы с условием сравнения по равенству, а интервальной индексация поддерживает также интервальные запросы. Декластеризация, которая вначале была предложена для систем без разделения ресурсов, оказалась полезной и для систем с разделяемой памятью, поскольку она способствует снижению конфликтности при доступе к памяти [Bergsten et al., 1991].

Полная декластеризация, когда каждое отношение разделяется по всем узлам системы, вызывает проблемы при работе с небольшими отношениями, а также в системах с очень большим числом узлов. Более удачен подход переменной декластеризации (variable declustering) , при котором каждое отношение хранится в некотором числе узлов, которое является функцией от размера отношения и частоты доступа к нему [Copeland et al., 1988]. Этот подход может сочетаться с совместной кластеризацией нескольких отношений, что позволяет избежать избыточных коммуникаций при выполнении бинарных операций.

Когда критерии, используемые для размещения данных, приводят к существенной деградации балансировки нагрузки, требуется произвести динамическую реорганизацию базы. Очень важно, чтобы реорганизацию можно было проводить в оперативном режиме (не прекращая текущей обработки транзакций), причем достаточно эффективно (применяя методы параллелизма). Существующие СУБД способны производить реорганизацию баз данных только статически [Shasha, 1992]. Статическая реорганизация проводится периодически и служит для изменения размещения данных либо в связи с увеличением размера базы данных, либо из-за изменения характера доступа к данным. В отличие от статической, динамическая реорганизация базы данных не требует остановки работы системы и обеспечивает плавный переход к новому размещению данных. Существенно, чтобы реорганизация была прозрачна для откомпилированных программ, работающих в параллельной системе. В частности, она не должна приводить к необходимости перекомпиляции программ. Это значит, что откомпилированные программы не должны зависеть от размещения данных. Отсюда следует, что оптимизатору не должно быть известно фактическое местоположение дисков, на которых хранится то или иное отношение, а также узел, где будет выполняться конкретная операция. Множество узлов, где хранится отношение в момент выполнения некоторой операции, называется домашним множеством отношения . Множество узлов, на которых выполняется операция, называется домашним множеством операции. Оптимизатор, тем не менее, должен обладать некоторым абстрактным знанием о структуре домашнего множества (например, "отношение R хэшировано на 20 узлах по атрибуту A"), а система поддержки времени выполнения производит ассоциирование между абстрактным домашним множеством и реальными узлами.

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

Еще один фактор, усложняющий задачу размещения данных, – это репликация данных для обеспечения высокого уровня доступности. Наивный подход здесь заключается в том, чтобы иметь две копии одних и тех же данных – первичную и резервную – на двух отдельных узлах. Но в случае отказа одного узла нагрузка на второй удвоится, что приведет к нарушению балансировки нагрузки. Для решения этой проблемы в последнее время было предложено несколько стратегий репликации для поддержки высокого уровня доступности, сравнительный анализ которых приведен в [Hsiao and DeWitt, 1991]. Интересный подход, который можно назвать расслоенной (interleaved) декластеризацией, применен в Teradata, где резервная копия декластеризуется между несколькими узлами. В случае отказа первичного узла его нагрузка распределяется между узлами, содержащими резервную копию. Однако реконструкция первичной копии из фрагментов ее резервной копии может оказаться дорогостоящей операцией. Существенны также затраты, требуемые на поддержание согласованного состояния резервной копии в нормальном режиме. Более разумное решение, названное цепочной (chained) декластеризацией, применено в Gamma, где первичная и резервная копии хранятся на двух соседних узлах. В режиме сбоя загрузка отказавшего узла распределяется между всеми остальными узлами, которые используют копии данных как первичного, так и вторичного узла. Поддержание согласованных копий в этом случае обходится дешевле. Открытым остается вопрос о процедуре размещения данных с учетом их реплицирования. Так же, как и размещение фрагментов в распределенных базах данных, эта проблема должна рассматриваться как одна из проблем оптимизации.

Проблемы сетевой масштабируемости

Исследовательское сообщество не располагает достаточно полным представлением о том, как связана производительность баз данных с разнообразными сетевыми архитектурами, которые развиваются вместе с современными распределенными СУБД. Возникает, в частности, вопрос о масштабируемости некоторых протоколов и алгоритмов в условиях, когда системы становятся географически распределенными [Stonebraker, 1989], или возрастает число отдельных системных компонентов [Garcia-Molina and Lindsay, 1990]. Важное значение имеет проблема пригодности механизмов для распределенной обработки транзакций в распределенных системах на базе глобальных сетей (WAN). Как упоминалось выше, работа этих протоколов связана с высокими накладными расходами, и реализация их на медленной сети WAN сильно затруднена [Stonebraker, 1989].

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

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

Распределенная и параллельная обработка запросов

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

Стоимостная модель – центральное звено глобальной оптимизации запросов, поскольку она предоставляет необходимую абстракцию среды выполнения распределенной СУБД в терминах методов доступа, а также абстракцию самой базы данных в терминах информации об ее физической схеме и соответствующей статистики. Стоимостная модель используется для предсказания затрат на выполнение альтернативных планов запроса. Со стоимостными моделями зачастую связан ряд серьезных ограничений, которые снижают эффективность оптимизации, направленной на улучшение общей пропускной способности системы. Полезными здесь могут быть работы по созданию расширенных алгоритмов оптимизации на основе параметризуемой стоимостной модели [Freytag, 1987], которую можно настраивать экспериментальным способом. Хотя языки запросов становятся все более развитыми (новые версии SQL), на стадии глобальной оптимизации применяется весьма ограниченное их подмножество, а именно, подмножество, позволяющее формулировать SPJ-запросы (select-project-join – селекция-проекция-соединение) с конъюнктивными предикатами. Это важный класс запросов, для которого существуют развитые методы оптимизации. Разработаны, в частности, различные теории оптимального упорядочения соединений и полусоединений. В то же время, имеются и другие важные классы запросов, для которых еще предстоит создать соответствующие методы оптимизации: запросы с дизъюнкциями, объединениями, фиксированными точками (fixpoint), агрегацией и сортировкой. Многообещающий подход к этой проблеме заключается в отделении чисто языковые аспекты от собственно оптимизации, которую можно доверить нескольким "экспертам оптимизации".

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

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

Критически важной проблемой с точки зрения стратегии поиска является проблема упорядочения соединений, которая является NP-полной от числа отношений [Ibaraki and Kameda, 1984]. Типичный подход к решению этой задачи – применение динамического программирования [Selinger et al., 1979], которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных. Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений. Однако уже для 5-7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomized strategy) , которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации – применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов [Ioannidis and Wong, 1987, Swami and Gupta, 1988, Ioannidis and Kang, 1990].

Распределенная обработка транзакций

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

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

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

В дополнение к репликации и в связи с ней необходимо также исследовать более сложные модели транзакций, в частности такие, в которых возможно использование семантики приложения [Elmagarmid, 1992, Weihl, 1989]. Подобные модели послужили бы достижению более высокой производительности и надежности, а также снижению конкуренции. По мере того как базы данных внедряются во все новые прикладные области, такие как инженерное проектирование, программные разработки, офисные информационные системы, видоизменяются и сама сущность транзакций, и предъявляемые к их обработке требования. Это означает, что следует выработать более изощренные модели транзакций, а также критерии корректности, отличные от сериализуемости.

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

продолжение следует...

Продолжение:

Часть 1 Distributed and parallel database systems
Часть 2 Исследовательские проблемы - Distributed and parallel database systems
Часть 3 Объект и предмет исследования. - Distributed and parallel database systems