|
|
СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ #04/95
|
|
М. Рузинкевич
А. Цикоцки**)
Department of computer Science University of Houston Houston, TX 77204-3475
Система управления потоками работ должна обеспечивать спецификацию и планирование межзадачных зависимостей. Кроме того, могут поддерживаться восстановление и управление параллельным выполнением; в этом случае может быть возможной интеграция планировщика, поддерживающего соблюдение межзадачных зависимостей, с системой управления ослабленными транзакциями.
Система управления потоком работ состоит из планировщика и агентов задач. Агент задачи контролирует выполнение задачи обрабатывающим объектом; для каждой задачи существует один агент. Планировщик - это программа, которая обрабатывает потоки работ, запуская на выполнение различные задачи, обрабатывая различные события и оценивая условия, связанные с межзадачными зависимостями. Планировщик может представить задачу на выполнение (агенту задачи) или потребовать прекращения выполнения ранее запущенных задач. В случае транзакции, затрагивающей несколько баз данных, задачи являются подтранзакциями, а обрабатывающие объекты - это локальные СУБД. В соответствии со спецификацией потока работ, планировщик обеспечивает планирование зависимостей и является ответственным за обеспечение того, что все задачи достигнут приемлемого состояния завершения.
Существует три архитектурных подхода к построению систем управления потоками работ. При использовании централизованного подхода имеется один планировщик, который планирует задачи всех параллельно выполняющихся потоков работ. Частично распределенный подход предполагает наличие одного (экземпляра) планировщика для каждого потока работ. В случае, когда вопросы параллельного выполнения могут быть отделены от функции планирования, последний подход является более естественным. В случае полностью распределенного подхода планировщик отсутствует; агенты задач координируют свое выполнение, взаимодействуя друг с другом для разрешения межзадачных зависимостей и прочих требований выполнения потоков работ.
Вначале мы обсудим цели планировщика, а затем рассмотрим некоторые подходы и прототипы.
Основными целями планировщика является обеспечение следующего:
В литературе описаны несколько планировщиков транзакций мультибаз данных. Однако большинство из предлагаемых решений затрагивают только часть проблем, обозначенных выше. Поэтому такие планировщики могут быть полезны только в специальных, ограниченных случаях. За исключением [3], все планировщики разработаны в основном для транзакций мультибаз данных, специального типа потоков работ. Планировщик, основанный на модели предикатных сетей Петри (Predicate Petri Nets model) [16] был разработан для управления гибкими транзакциями (Flexible Transactions). Другой исполнитель гибких транзакций был разработан с использованием логического параллельного языка L.0 [6, 2]. Пример подхода к планировщику как к интерпретатору языка спецификаций транзакций мультибаз данных для гибких транзакций описан в [33], где для спецификации транзакций мультибаз данных используется язык Vienna Parallel Logic (VPL). Планировщик может также быть разработан как интерпретатор правил Событие-Условие-Действие (Event-Condition-Action - ECA), как это описывается в [11, 12]. Аналогичный подход обсуждается в [22], где межзадачные зависимости в транзакциях мультибаз данных реализуются с использованием правил ECA. Подход, согласно которому процесс планирования моделируется игрой планировщика против своего окружения, представленного локальными системами баз данных, описан в [46]. Планировщик может также использовать модель конечных автоматов [31] для анализа зависимостей между подтранзакциями и для определения достижимости приемлемых состояний посредством инструментов анализа протоколов. Еще один прототип, представленный в литературе [3], использует темпоральную пропозициональную логику для планирования и соблюдения межзадачных зависимостей.
Прототип частично распределенного планировщика потоков работ недавно был разработан в Университете Хьюстона. На Рис. 3 представлена общая архитектура этого планировщика. Основными частями системы являются:
Рисунок 3.
Архитектура Прототипа Планировщика Потока Работ.
Поскольку атомарность в связи со сбоями является важным аспектом выполнения потока работ, в этом прототипе поддерживается механизм прямого восстановления. Все сообщения при обмене между планировщиком и менеджерами задач журнализуются, равно как и изменения состояний и пересылки данных. Это позволяет планировщику реконструировать состояние потока работ и продолжать выполнение потока работ в случае возникновения отказа.
Мы предполагаем, что каждая задача потока работ выполняется под управлением своего обрабатывающего объекта (например, СУБД), что обеспечивает локальное управление параллельным выполнением в границах, требуемых семантикой каждой из задач. Это гарантирует, что каждая система обработки остается в (локально) согласованном состоянии; однако этого может быть недостаточно для гарантии глобальной корректности параллельного выполнения потоков работ.
В предположении, что каждый поток работ выполняется корректно, параллельное выполнение нескольких потоков является корректным, если оно, в некотором смысле, эквивалентно последовательному, без взаимного влияния, выполнению этих потоков. При отсутствии какой-либо дополнительной информации о существующих ограничениях, налагаемых на состояния множества систем, участвующих в выполнении потока работ, и о свойствах потоков работ, для достижения упомянутой эквивалентности требуется поддержка глобальной сериализуемости и глобальной фиксируемости (commitment) потоков работ. Если доступна дополнительная информация (например, требования атомарности в связи со сбоями и атомарности для обеспечения изолированности для каждого потока работ), могут быть применимы более слабые критерии корректности параллельного выполнения потоков работ.
Требования ослабленной глобальной сериализуемости. В дальнейшем обсуждении мы предполагаем, что спецификации потоков работ, предоставленные разработчиком, и их начальные параметры корректны, и, таким образом, изолированное выполнение потока работ не вызывает нарушения согласованности. Планировщик потока работ гарантирует, что каждый поток обрабатывается в соответствии со своими спецификациями, а локальные менеджеры параллельного выполнения гарантируют, что совместное выполнение задач не нарушает ограничения локальной согласованности. Механизм управления параллельным выполнением потока работ должен гарантировать корректность глобальных историй выполнения потоков работ, т. е. поддерживать мультисистемные ограничения согласованности. Ниже мы определяем класс глобальных историй, считающихся корректными в рамках описанной выше модели потока работ.
Задачи различных потоков работ требуют выполнения операций, которые могут локальным образом конфликтовать с операциями других потоков работ или локальными транзакциями. Порядок выполнения зафиксированных конфликтующих операций локальных транзакций или задач (в рамках общих транзакций) сказывается на порядке сериализации между транзакциями, от которых исходят эти операции (обозначается через <). Это отношение порядка сериализации между транзакциями является транзитивным и может быть использовано для определения М-сериализуемости - критерия корректности параллельного выполнения потоков работ.
Неформально, глобальная история является М-сериализуемой, если каждая локальная история является сериализуемой, и никакие два потока работ Wi и Wj не включают задачи Tik, Til, относящиеся к одной атомарной единице выполнения Wi, и задачи Tjk и Tjl, относящиеся к одной атомарной единице выполнения Wj, такие, что Tik<Tjk и Til<Tjl. Глобальная сериализуемость требует, чтобы порядок сериализации потока работ был бы совместимым для всех обрабатывающих объектов. Другими словами, если задача Ti потока Wi предшествует задаче Tj потока Wj в каком-либо обрабатывающем объекте, то ни в каком другом объекте задача потока Wj не может предшествовать задаче потока Wi. Для М-сериализуемости требуется только то, чтобы задачи, относящейся к одной атомарной единице выполнения потока работ, имели совместимый порядок сериализации во всех узлах, к которым они имеют доступ. М-сериализуемость допускает некоторые глобальные истории, которые были бы отвергнуты в случае глобальной сериализуемости. Это происходит вследствие того, что операции задачи Ti не связаны с операциями задач, которые относятся к атомарным единицам выполнения, отличающимся от той, к которой относится Ti. Следовательно, порядок сериализации задачи Ti влияет на порядок сериализации только тех задач, которые относятся к той же атомарной единице выполнения, что и Ti, а не всех задач потока Wi, как в случае глобальной сериализуемости.
В качестве примера рассмотрим историю, представленную на Рис. 4. Предположим, что каждый из двух идентичных потоков работ W1 и W2 состоит из двух атомарных единиц {T11,T12} и {T13} и {T21,T22} и {T23}, соответственно. Далее, пусть порядок сериализации между T11 и T21, установленный в узле Site1, не влияет на порядок сериализации в узле Site3. С другой стороны, поскольку задачи T12 и T22 конфликтуют, Т 22 должна быть выполнена раньше, чем T12. Формальное определение М-сериализуемости и механизм ее обеспечения представлены в [46].
Рисунок 4.
Глобальные механизмы управления параллельным выполнением. Предлагались различные алгоритмы, обеспечивающие управление параллельным выполнением на основе критерия глобальной корректности. В большинстве алгоритмов для достижения согласованного выполнения используются некоторые разновидности блокирования. Ниже мы описываем некоторые алгоритмы блокирования, разработанные для выполнения потоков работ.
Схема, основанная на альтруистическом блокировании (Altruistic locking) [48], была предложена в [31]. В этой схеме предполагается, что в каждый момент времени только один поток работ может иметь доступ к узлу обработки, и, следовательно, существует полная изолированность между сосуществующими потоками работ. Для достижения сериализуемого выполнения потокам работ предоставляются блокировки установок в одном и том же порядке на каждой установке. Таким образом, если блокировка установки S1 была предоставлена задаче из потока Wi прежде, чем задаче из потока Wj, то этот порядок должен сохраняться на каждой установке. Для предотвращения косвенных конфликтов локальных транзакций в связи с потоками работ требуется, чтобы локальные системы поддерживали строгое планирование, применяя, например, механизм строгих двухфазных блокировок при управлении параллельным выполнением [4].
Алгоритм альтруистического блокирования предполагает возможность конфликта между любыми двумя выполняемыми в одно и то же время потоками работ. Такое пессимистическое предположение уменьшает возможную степень параллельности при выполнении потока работ, уменьшая тем самым производительность системы. Тем не менее, если семантика всех задач известна заранее, может быть разработан механизм управления параллельным выполнением, учитывающий только существенные конфликты. Это может повысить эффективность системы. Семантическое управление параллельным выполнением предназначено для специфического семейства приложений, в которых ограничения корректности определяются отдельно для каждого класса задач. Некоторые задачи должны сериализоваться, другие могут допускать некоторую несогласованность и, тем самым, могут быть выполнены несериализуемым образом. Менеджер параллельного выполнения, имея информацию об этих ограничениях, предоставляет блокировки задачам таким образом, чтобы выполнялись критерии корректности. Алгоритм, реализующий семантическое управление параллельным выполнением для группы телекоммуникационных приложений, описан в [36].
Следует заметить, что если все задачи выполняемых потоков работ коммутативны, никакое управление параллельным выполнением не требуется. Большинство коммерческих продуктов выполнения потоков работ разработаны для потоков, задачи которых разрабатываются вручную и предполагаются коммутативными. Поэтому обычно в этих продуктах не реализуется какой-либо механизм управления параллельным управлением.
Целью восстановления после отказа при выполнении потоков работ является обеспечение атомарности потоков работ в связи со сбоями. Процедуры восстановления должны гарантировать, что в случае возникновения отказа в любом из компонентов, принимающих участие в обработке потока работ (включая планировщик), поток все равно достигнет приемлемого состояния - возможно, с использованием компенсации. Мы можем предположить, что обрабатывающие объекты, принимающие участие в выполнении потока работ, обладают своими собственными локальными системами восстановления и сами обрабатывают возникающие в них локальные отказы. Поэтому мы будем обсуждать только отказы менеджеров выполнения потока работ (планировщика(ов) и менеджера параллельного выполнения).
Чтобы восстановить контекст среды выполнения, процедура восстановления после отказа должна восстановить информацию о состоянии к моменту отказа, включая информацию о состоянии выполнения каждой задачи и информацию о зависимостях планирования для менеджера параллельного выполнения. Следовательно, соответствующая статусная информация должна журнализоваться на надежном запоминающем устройстве [30].
Отказ менеджера параллельного выполнения может быть обнаружен посредством механизмов временного контроля, а информация о состоянии может быть реконструирована путем просмотра журналов. В предположении возможности прямого восстановления [44] и идемпотентности обрабатывающих объектов, выполнение потока работ может быть продолжено простым перезапуском незавершенных задач.
Нам также требуется обращать внимание на содержимое очередей запросов. Если используется механизм, обеспечивающий функции стабильных программных каналов (например, в системе VMS компании DEC очереди могут быть реализованы c использованием почтовых ящиков - стабильных очередей сообщений, доступных как виртуальные устройства ввода/вывода), сообщения хранятся на постоянном запоминающем устройстве и не теряются в случае отказа. Если очереди хранятся на ненадежном запоминающем устройстве (например, в среде ОС UNIX очереди могут быть реализованы с использованием сокетов), вместо восстановления содержимого очередей можно пойти на то, чтобы планировщики повторно посылали свои запросы.
Во многих коммерческих продуктах для распределения задач по обрабатывающим станциям, ответственным за их выполнение, используются интерфейсы электронной почты. Это простое решение обладает преимуществами, проистекающими из относительной надежности существующих систем электронной почты и содержащихся в них возможностей по организации очередей и повторных посылок сообщений.
Для реализации управления потоками работ поставщики используют разнообразные подходы. Некоторые поставщики предлагают специализированное программное обеспечение управления потоками работ, другие включают функции управления потоками в существующие приложения, третьи же предлагают опорные программы, позволяющие пользователям спроектировать, наполнить и использовать простые формы. Ниже мы кратко опишем несколько известных продуктов, доступных на рынке.
Продукт Staffware, предлагаемый компанией Staffware, был первым программным продуктом, разработанным для автоматизации потоков работ. Staffware - это система, разработанная в технологии клиент/сервер и предназначенная для автоматизации хорошо определенных процедур, относящихся к интенсивному документообороту. Пакет поставляется для различных вариантов UNIX и Windows и может быть интегрирован с базами данных, системами электронной почты и системами обработки текста. Базовая часть Staffware содержит механизмы управления последовательным и параллельным управлением задач с зависимостями планирования, основанными на событиях, значениях данных и достигнутом времени выполнения. Набор графических интерфейсов позволяет пользователю определять и конфигурировать потоки работ и моделировать выполнение потока работ для обнаружения потенциальных узких мест.
Продукт InConcert, предлагаемый на рынке подразделением компании Xerox, является объектно-ориентированным средством создания и выполнения приложений, основанных на потоках работ. Возможности InConcert включают основанную на правилах спецификацию потока работ, триггеры событие-действие, временные и приоритетные зависимости и динамическую модификацию потока работ. InConcert является независимым от приложения и хранит всю информацию о потоке работ, как-то определение, атрибуты, информацию протоколирования и обеспечения безопасности, события и действия в SQL-ориентированной, совместимой со стандартом ANSI базе данных (например, Oracle или Sybase).
Рынок программного обеспечения автоматизации потоков работ быстро развивается, и сейчас доступно более 100 продуктов различных поставщиков. Недавно была образована организация поставщиков продуктов автоматизации потоков работ с целью разработки стандартов спецификаций потоков работ, что позволило бы обеспечить интероперабельность в среде различных продуктов.
По сравнению с коммерческими продуктами, в исследовательских прототипах большее внимание уделяется транзакционным свойствам (изолированность или восстановимость) потоков работ. Как правило, возможности, предоставляемые этими проектами, могут использоваться как для реализации управления ослабленными транзакциями, так и для обработки потоков работ. Примеры таких сред обеспечивают проекты Narada [29], Contracts [44], Interbase [15], Carnot [52] и Distributed Object Management (DOM) [22].
Работа по выполнению мультисистемных приложений в неоднородной вычислительной среде ведется в рамках проекта Omnibase в Хьюстонском университете с 1985 года [28]. Основным вкладом этого проекта в управление потоками работ была разработка языка спецификаций задач DOL и распределенной среды выполнения Narada. Архитектура программного обеспечения, основанная на языке спецификаций задач, в дальнейшем была использована и развита в ряде проектов, включая Ernie в Bellcore, Interbase в Purdue [47], Narada в Хьюстоне [26] и Carnot в MCC [55].
Система, основанная на DOL, состоит из каталога ресурсов, ядра DOL и набора Менеджеров Локального Доступа (Local Access Managers - LAM). Каталог ресурсов содержит актуальную информацию о всех службах, известных ядру DOL. Эта информация включает в себя физические адреса, протоколы связи, регистрационную информацию и информацию о методах передачи данных. Ядро DOL обеспечивает выполнение DOL-программ путем взаимодействия с различными службами. Ядро выполняет активизацию задач, синхронизацию задач, условное выполнение и обмен данными между LAM, а также управление фиксацией локальных и глобальных задач. Оно также отвечает за открытие и закрытие соединений с участвующими в работе LAM, устанавливая между ними каналы связи, посылая им их локальные команды и осуществляя наблюдение за состоянием выполнения. LAM работает как представитель пользователя в обрабатывающем объекте, которым он управляет, и обеспечивает абстракцию выполняемой им службы. LAM поддерживает автономность обрабатывающих объектов. Ядро DOL взаимодействует с LAM, который несет ответственность за выполнение затребованных локальных команд.
DOL-программы могут быть написаны непосредственно конечными пользователями или автоматически сгенерированы другими программными системами. Ядро DOL получает DOL-программу и вырабатывает план ее выполнения. Оно обращается к каталогу ресурсов для получения текущей информации о вызовах соответствующих LAM. Ядро DOL выполняет DOL-программу посредством вызова LAM, обеспечивающего соответствующие службы. Эти службы могут быть базами данных, системами, основанными на знаниях, программными пакетами или другими ядрами DOL. После успешного завершения выполнения каждым LAM своих задач, вывод может быть переадресован другому LAM. Ядро DOL взаимодействует со всеми LAM с использованием одного и того же высокоуровнего коммуникационного протокола. Это упрощает архитектуру и позволяет добавлять новые службы без модификации остальных модулей системы.
Проект Carnot, выполняемый в MCC, двигается дальше в развитии поддержки распределенных служб и приложений, включая ослабленные транзакции и потоки работ [55, 52]. В основном компоненте системы, называемом Расширяемым Переключателем Служб (Extensible Services Switch - ESS), используется язык Rosette, основанный на акторной модели. Rosette поддерживает интерпретируемое управление распределенными приложениями, высокую степень параллельности и сверхоблегченные процессы. Поскольку управление программами и сценариями является интерпретируемым, одна установка может переслать сценарий другой, чтобы повлиять на локальное управление распределенным приложением. Далее, ESS поддерживает множество абстракций распределенной обработки, в частности потоки байтов (ByteStreams) и пространства деревьев (TreeSpaces), для упрощения разработки и эффективной реализации управления потоками работ и ослабленными транзакциями. Существует прототип ESS, взаимодействующий с различными коммуникационными ресурсами (например TCP/IP, SNA, X.25), информационными ресурсами (например коммерческими реляционными и объектно-ориентированными СУБД) и службами приложений (например X.500, X.400).
Система управления распределенными объектами (Distributed Object Management System - DOMS) [27] является объектно-ориентированной средой, в которой автономные и неоднородные системы могут быть интегрированы посредством представления своих данных и функций как объектов. Клиентские приложения (задачи) могут получить доступ к этим объектам, не имея информации об их расположении, языке доступа или деталях представления данных систем более низкого уровня. Для обеспечения согласованности объектов при возникновении отказов или при параллельном выполнении в DOMS используются транзакции при доступе к объектам в системах, которые могут предоставлять или не предоставлять транзакционные возможности, и к объектам, поддерживаемым самой системой DOMS. Если система не обеспечивает необходимые операции, в DOMS используется собственный интерфейс с операциями управления транзакциями, поддерживаемыми менеджером транзакций системы.
Иерархические структуры расширенных моделей транзакций, таких как вложенные транзакции [42] и многоуровневые транзакции [53], часто являются слишком негибкими для приложений потоков работ. Основной проблемой, возникающей при разработке системы управления потоками работ в рамках данной модели транзакций, является то, что предопределенный набор свойств, обеспечиваемых моделью, может требоваться, а может и не требоваться семантикой потока работ. Например, межзадачные зависимости, требуемые семантикой потока работ, могут быть более сложными, чем те, которые поддерживаются данной моделью транзакций, или предоставляемые гарантии корректности (такие, как глобальная сериализуемость) могут быть более строгими, чем это требуется.
Другой проблемой выбора расширенных моделей транзакций для проектирования и реализации потоков работ является то, что системы, участвующие в обработке потока (обрабатывающие объекты), могут не предоставлять возможности, вытекающие из модели транзакции. Например, модели транзакций мультибаз данных ориентированы на применение таких обрабатывающих объектов, как СУБД, следовательно, они не применимы, если эти объекты не предоставляют возможностей локального управления транзакциями. Поскольку может возникнуть необходимость определения потоков работ, где обрабатывающими объектами являются не СУБД, очевидно, что такие системы потоков работ не могут обеспечить глобальную согласованность данных, гарантируемую транзакциями.
Мотивацией разработки моделей потоков работ является преодоление этих ограничений. По нашему мнению, развитая система транзакционных потоков работ должна поддерживать многозадачную, мультисистемную работу, причем (а) различные задачи при выполнении могут обладать различным поведением и различными свойствами, (б) задачи могут выполняться на различных обрабатывающих объектах, (в) обеспечивается определяемая приложением или пользователем координация выполнения различных задач, включая обмен данными, и (г) поддерживается определяемая приложением или пользователем атомарность в связи со сбоями и атомарность выполнения.
Основной тип систем транзакционных потоков работ использует транзакции как задачи и применяет предоставляемую системами поддержку выполнения транзакций (что похоже на расширение модели ослабленных транзакций межзадачными зависимостями). Потоки работ могут дополнительно требовать управления параллельным выполнением для поддержки атомарности выполнения при параллельном выполнении нескольких потоков работ. В случае, когда задачи являются транзакциями, и обрабатывающие их объекты являются системами управления базами данных, возможно и желательно использовать результаты обширных современных работ по расширенным и ослабленным моделям транзакций. Для тех случаев, когда задачи не являются транзакциями и/или обрабатывающие объекты не предоставляют средств выполнения транзакций, но для потока работ существуют требования атомарности по сбоям и атомарности выполнения, требуются дальнейшие исследования.
Несмотря на то, что некоторые критерии корректности можно выразить посредством межзадачных зависимостей, может быть желательным включить их в модель потока работ. В будущем мы ожидаем эволюцию в направлении моделей построения приложений, которые предоставляют расширенные возможности транзакций и потоков работ для удовлетворения потребностей сложных приложений при доступе к существующим неоднородным системам.
|
|