Размещение данных
В параллельной системе баз данных правильное размещение данных имеет решающее значение для обеспечения балансировки нагрузки. В идеале можно полностью избежать интерференции между одновременно выполняемыми параллельными операциями, если каждая из них будет работать с независимым набором данных. Независимые наборы данных получаются путем декластеризации (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, где первичная и резервная копии хранятся на двух соседних узлах. В режиме сбоя загрузка отказавшего узла распределяется между всеми остальными узлами, которые используют копии данных как первичного, так и вторичного узла. Поддержание согласованных копий в этом случае обходится дешевле. Открытым остается вопрос о процедуре размещения данных с учетом их реплицирования. Так же, как и размещение фрагментов в распределенных базах данных, эта проблема должна рассматриваться как одна из проблем оптимизации.
