Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen [original]

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

68 Datenbank-Spektrum 1/2001

Die Unterstützung unternehmensweiter

und -übergreifender Geschäftsprozesse

stellt für ein Workflow-Management-Sys-

tem (WfMS) eine besondere Herausforde-

rung dar. So sind Skalierbarkeit bei hoher

Last und die Möglichkeit, zur Ausfüh-

rungszeit eines Workflows (WF) dyna-

misch vom vormodellierten Ablauf abwei-

chen zu können, unbedingt erforderlich,

damit ein WfMS für ein breites Spektrum

von Anwendungen einsetzbar ist. Aller-

dings wurden diese beiden Aspekte in der

WF-Literatur bisher weitgehend getrennt

voneinander betrachtet. Dies ist äußerst

problematisch, da mit ihnen entgegenge-

setzte Anforderungen verbunden sind. So

wird zur Erzielung einer guten Skalier-

barkeit angestrebt, dass eine WF-Instanz

von mehreren WF-Servern – möglichst

unabhängig voneinander – kontrolliert

werden kann, wohingegen für dynamische

WF-Änderungen eine (logisch) zentrale

Kontrollinstanz benötigt wird, die den ak-

tuellen, globalen Zustand der WF-Instanz

kennt. In diesem Beitrag werden erstmals

Verfahren vorgestellt, die es erlauben, dy-

namische Änderungen in einem verteilten

WfMS durchzuführen. Besonders bemer-

kenswert ist dabei, dass es gelungen ist,

die volle aus dem zentralen Fall bekannte

Funktionalität zu realisieren, und trotz-

dem ein bezüglich der Kommunikations-

kosten äußerst günstiges Verhalten zu er-

zielen.

1 Einleitung

WfMS [JBS97, LR00, Obe96, RD00] er-

möglichen die rechnerunterstützte Aus-

führung von Geschäftsprozessen in einer

verteilten Systemumgebung. Der ent-

scheidende Vorteil solcher Systeme ist,

dass sie helfen, große vorgangsorientierte

Anwendungssysteme überschaubarer zu

gestalten. Dazu wird der applikationsspe-

zifische Code der verwendeten Anwen-

dungen von der Ablauflogik der unter-

stützten Geschäftsprozesse getrennt.

Diese Arbeit wurde teilweise im Rahmen des

Projektes »Skalierbarkeit in adaptiven Work-

flow-Management-Systemen« der Deutschen

Forschungsgemeinschaft (DFG) erstellt.

Anstelle eines großen monolithischen

Programmpakets erhält man nun einzelne

Aktivitäten, welche die Anwendungs-

programme repräsentieren. Ihre Ablauf-

logik wird in einer separaten Kon-

trollflussdefinition festgelegt, welche die

Ausführungsreihenfolge (Sequenz, Ver-

zweigung, Parallelität, Schleifen) der Ak-

tivitäten bestimmt. Das WfMS sorgt zur

Ausführungszeit dafür, dass nur solche

Aktivitäten einer WF-Instanz bearbeitet

werden können, die der Ablauflogik zu-

folge zur Ausführung anstehen. Diese

werden in die Arbeitslisten autorisierter

Bearbeiter eingefügt. Welche Benutzer

zur Bearbeitung einer bestimmten Aktivi-

tät autorisiert sind, wird meist durch eine

Rolle festgelegt, die auch den entspre-

chenden Bearbeitern zugeordnet ist.

Die Funktionalität heutiger WfMS ist

für viele der in der Praxis vorkommenden

prozessorientierten Anwendungen nicht

ausreichend. Ein Mangel ist insbesondere

die unzureichende Skalierbarkeit bei hoher

Last. Der Forderung nach Skalierbarkeit

kommen wir in ADEPT (ADEPT steht für

Application Development Based on

Encapsulated Pre-Modeled Process Tem-

plates) dadurch nach, dass ein WfMS aus

mehreren WF-Servern besteht. Um ein

günstiges Kommunikationsverhalten zu er-

zielen, kann eine einzelne WF-Instanz ab-

schnittsweise von verschiedenen WF-Ser-

vern kontrolliert werden [BD97, BD00].

Eine ebenfalls erkannte Schwachstel-

le existierender WfMS ist ihre unzurei-

chende Adaptivität. In ADEPT ist es

möglich, eine laufende WF-Instanz bei

Bedarf (z.B. in Ausnahmesituationen)

dynamisch zu verändern, so dass von

dem vormodellierten Ablauf abgewichen

wird. Im Gegensatz zu vielen anderen

Ansätzen wird die Konsistenz der WF-

Instanz auch nach der Änderung garan-

tiert, d.h. Laufzeitfehler (z.B. Verklem-

mungen in Folge zyklischer Reihenfolge-

beziehungen) sind ausgeschlossen

[RD98, Rei00]. In den bisherigen Veröf-

fentlichungen zu ADEPT haben wir,

ebenso wie die anderen uns bekannten

Gruppen, verteilte WF-Ausführung und

Adaptivität nur getrennt betrachtet. Das

Zusammenspiel dieser beiden für ein

WfMS essenziellen Aspekte wurde dabei

nicht systematisch untersucht. Dies ist

problematisch, weil mit den beiden

Aspekten entgegengesetzte Anforderun-

gen verbunden sind: Zur Durchführung

einer dynamischen Änderung wird eine

zentrale Kontrollinstanz benötigt [RD98].

Die Existenz einer solchen konterkariert

aber die durch verteilte WF-Ausführung

erzielten Errungenschaften, da eine zen-

trale Komponente die Verfügbarkeit des

WfMS verschlechtert und den Kommuni-

kationsaufwand erhöht. Ein Grund dafür

ist, dass eine solche Komponente über

jede Änderung des Zustands jeder WF-

Instanz informiert werden muss. Der Zu-

stand der zu modifizierenden WF-Instanz

wird benötigt, um entscheiden zu kön-

nen, ob eine geplante Änderung durch-

führbar ist [RD98].

Das Ziel des vorliegenden Beitrags

ist es, dynamische Änderungen in einem

verteilten WfMS zu ermöglichen. Dabei

soll die Adaptivität gegenüber der zentra-

len WF-Ausführung nicht eingeschränkt

sein, d.h. jede für den zentralen Fall er-

laubte dynamische Änderung muss im

verteilten Fall weiterhin zulässig sein.

Die Unterstützung solcher dynamischer

Abweichungen darf die Effizienz der ver-

teilten WF-Steuerung aber keinesfalls be-

einträchtigen. Insbesondere soll bei der

»normalen« WF-Ausführung kein großer

zusätzlicher Kommunikationsaufwand

notwendig werden. Außerdem sollen in

dem angestrebten System (verteilte) dy-

namische Änderungen auf möglichst effi-

ziente Art und Weise durchgeführt wer-

den können.

Zur Behandlung dieser Anforderun-

gen (siehe auch [RBD99]) ist zu untersu-

chen, mit welchen Servern des WfMS

eine dynamische Änderung synchroni-

siert werden muss. Vermutlich müssen

zumindest die aktuell an der WF-Instanz

beteiligten Server einbezogen werden, da

sie die resultierende Struktur und den Zu-

stand der WF-Instanz (sog. Ausführungs-

graph) benötigen, um diese korrekt steu-

ern zu können. Deshalb wird ein Verfah-

ren benötigt, mit dem die Menge dieser

Server ohne großen Aufwand ermittelt

werden kann. Außerdem ist zu klären,

wie diesen und anderen Servern der

durch die Änderung resultierende Aus-

führungsgraph der WF-Instanz übermit-

telt werden kann. Dabei ist essenziell,

Thomas Bauer, Manfred Reichert, Peter Dadam

Dynamische Ablaufänderungen in

verteilten Workflow-Management-Systemen

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

Datenbank-Spektrum 1/2001 69

dass kein inakzeptabel großer Kommuni-

kationsaufwand verursacht wird.

Im nachfolgenden Abschnitt wird auf

Grundlagen der verteilten WF-Ausfüh-

rung und der dynamischen Änderungen

in ADEPT eingegangen, die für das Ver-

ständnis dieser Arbeit notwendig sind.

Abschnitt 3 beschäftigt sich mit der

Durchführung von dynamischen Ände-

rungen in einem verteilten WfMS. In

Abschnitt 4 wird erläutert, wie dyna-

misch veränderte WF-Instanzen auch im

verteilten Fall effizient gesteuert werden

können. Eine Einordnung der entwickel-

ten Verfahren in die WF-Literatur findet

sich in Abschnitt 5. Der Beitrag schließt

mit einer Zusammenfassung und einem

Ausblick auf zukünftige Arbeiten.

2 Grundlagen

Im ADEPT-Projekt [DRK00, RD98,

RBFD01] betrachten wir Anforderungen,

die sich bei der Unterstützung unterneh-

mensweiter und -übergreifender WF-ba-

sierter Anwendungen ergeben. Im vorlie-

genden Abschnitt fassen wir die hieraus

hervorgegangenen Konzepte zur verteil-

ten WF-Steuerung und zu dynamischen

WF-Änderungen kurz zusammen.

2.1 Verteilte Workflow-Ausführung

in ADEPT

Aufgrund der großen Anzahl von Benut-

zern und gleichzeitig aktiven WF-Instan-

zen resultiert in unternehmensweiten An-

wendungen eine sehr hohe Last.1 Diese

kann dazu führen, dass Komponenten des

WfMS überlastet werden. Deshalb wird in

ADEPTdistribution, der verteilten Variante

von ADEPT, eine WF-Instanz nicht im-

mer von nur einem einzigen WF-Server

kontrolliert, sondern sie wird ggf. partiti-

oniert und abschnittsweise von verschie-

denen Servern gesteuert [BD97, Bau01]

(vgl. Abb. 1). Wird bei der Ausführung

von verteilt gesteuerten WF-Instanzen

das Ende einer Partition erreicht, so wird

die Kontrolle über diesen WF an den

nächsten WF-Server weitergereicht (Mig-

ration). Damit dies möglich ist, muss eine

Beschreibung des Zustands der WF-In-

stanz zu diesem Server transportiert wer-

1. In [KAGM96, SK97] werden Anwendungen

beschrieben, bei denen die Zahl der Benutzer

des WfMS bis auf einige zehntausend anwach-

sen kann oder mehrere zehntausend WF-In-

stanzen gleichzeitig im System sein können.

den. (Die WF-Vorlagen werden in

ADEPT repliziert bei allen (relevanten)

WF-Servern gespeichert.) Um unnötigen

Kommunikationsaufwand zwischen WF-

Servern zu vermeiden, erfolgt in ADEPT

die Steuerung von parallelen Zweigen un-

abhängig voneinander (wenn zur Zeit kei-

ne dynamische Änderung durchgeführt

wird). Im Beispiel aus Abb. 1 weiß der

WF-Server s3, der gerade die Aktivität e

kontrolliert, nicht, wie weit die Bearbei-

tung im oberen Zweig der Parallelität fort-

geschritten ist. Dies hat den Vorteil, dass

keine Synchronisation zwischen WF-Ser-

vern notwendig ist, die Aktivitäten paral-

leler Zweige steuern.

Die Partitionierung von WF-Graphen

und die verteilte WF-Steuerung werden

auch in anderen Ansätzen verwendet (z.B.

[CGP+96, MWW+98]). Wir verfolgen in

ADEPT zusätzlich das Ziel, die Kommu-

nikationskosten zu minimieren. Konkrete

Erfahrungen mit existierenden WfMS ha-

ben gezeigt, dass zwischen einem WF-

Server und seinen Clients sehr viel kom-

muniziert wird und zum Teil auch große

Datenmengen ausgetauscht werden müs-

sen. Dies kann dazu führen, dass das

Kommunikationssystem überlastet wird.

Deshalb werden in ADEPT die WF-Ser-

ver der Aktivitäten so festgelegt, dass der

Gesamtkommunikationsaufwand mini-

miert wird. Dazu wird der WF-Server für

eine Aktivität in der Regel so gewählt,

dass er im Teilnetz der Mehrzahl ihrer

potenziellen Bearbeiter liegt. Dadurch

wird in vielen Fällen eine teilnetzüber-

greifende Kommunikation zwischen dem

WF-Server und seinen Clients vermieden.

Außerdem werden die Antwortzeiten ver-

bessert und die Verfügbarkeit erhöht, da

bei der Ausführung von Aktivitäten kein

Gateway oder WAN (Wide Area Net-

work) zwischengeschaltet ist.

Bei diesem Ansatz wird bereits zur

Modellierungszeit eine (statische) Zuord-

nung von WF-Servern zu Aktivitäten

vorgenommen. Es gibt aber auch Fälle, in

denen diese Vorgehensweise nicht ausrei-

chend ist, um gute Resultate zu erzielen.

Dies ist der Fall, wenn bei der WF-Defi-

nition abhängige Bearbeiterzuordnungen

(z.B. »selber Bearbeiter wie Aktivität n«)

verwendet werden. Hier hängen die

potenziellen Bearbeiter einer Aktivität

vom Bearbeiter einer Vorgängeraktivität

ab. Da sich die Menge der potenziellen

Bearbeiter einer solchen Aktivität erst im

Verlauf der WF-Ausführung ergibt, ist es

vorteilhaft, ihren WF-Server ebenfalls

erst zur Ausführungszeit festzulegen. Der

Server kann dann in einem für die

entsprechenden Bearbeiter günstigen

Teilnetz gewählt werden. Zu diesem

Zweck wurde für ADEPTdistribution das

Konzept der variablen Serverzuordnun-

gen [BD99a, BD00] entwickelt. Hierbei

handelt es sich um Ausdrücke (z.B. »Ser-

ver im Teilnetz des Bearbeiters der Akti-

vität n«), die zur Ausführungszeit der

WF-Instanz ausgewertet werden. Da-

durch wird zur Ausführungszeit derjeni-

ge WF-Server ermittelt, der die zugehöri-

ge Aktivitäteninstanz kontrollieren soll.

2.2 Dynamische Workflow-

Änderungen in ADEPT

Um auf Ausnahmesituationen flexibel re-

agieren zu können, muss der Ausfüh-

rungsgraph einer WF-Instanz zur Ausfüh-

rungszeit modifiziert werden können. Das

ADEPTflex-Kalkül bietet z.B. die Mög-

lichkeit, Aktivitäten dynamisch einzufü-

gen oder zu löschen. Dabei sind auch sehr

komplexe Operationen realisierbar, wie

das Einfügen einer Aktivität, die erst nach

der Beendigung einer beliebigen Menge

von Aktivitäten ausführbar sein soll und

vor dem Starten einer anderen Menge von

Aktivitäten beendet sein muss. Auf die

Verfahren zur Durchführung solcher dy-

namischen Änderungen wird hier nicht

näher eingegangen, da dies für das weitere

Verständnis dieses Beitrags nicht notwen-

dig ist (für Details siehe [RD98, Rei00]).

Aus der Spezifikation einer Änderung

bestimmt das WfMS automatisch eine

Menge von

Basisoperationen

(z.B. Akti-

Partition 1

Partition 2

Partition 3

normaler Kontrollfluss

Kontrollfluss und Migration

von Aktivität x nach y

Mx,y

Mc,f

Ma,b

Ma,d

AND-Split AND-Join

Abb. 1: Partitionierung eines WF-Graphen und verteilte WF-Ausführung

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

70 Datenbank-Spektrum 1/2001

vitätenknoten einfügen, Kante einfügen),

die auf den Ausführungsgraphen der ent-

sprechenden WF-Instanz angewandt wer-

den. Wie in Abb. 2, c) dargestellt, werden

diese Basisoperationen zusammen mit der

Spezifikation der Änderung in einer

Än-

derungshistorie

vermerkt. Diese wird be-

nötigt, um im Falle des partiellen Zurück-

setzens einer WF-Instanz ggf. auch tem-

poräre Änderungsoperationen rückgängig

machen zu können (vgl. [DRK00]). Au-

ßerdem wird die dynamische Änderung in

der

Ablaufhistorie

der WF-Instanz ver-

merkt (Eintrag

DynModif

(1) in Abb. 2, b)

für die Änderung 1), in welcher ansonsten

für die WF-Ausführung benötigte Infor-

mationen, wie die Start-/Endzeitpunkte

und die Bearbeiter der Aktivitäten, proto-

kolliert werden.

Um eine robuste WF-Ausführung zu

ermöglichen, muss die Konsistenz eines

WF-Ausführungsgraphen jederzeit ga-

rantiert werden können. Prinzipiell kön-

nen aber durch eine dynamische Modifi-

kation Inkonsistenzen entstehen. So kön-

nen durch das Löschen einer Aktivität

evtl. Eingabedaten nachfolgender Aktivi-

täten nicht mehr vollständig versorgt

sein, oder nach dem Einfügen einer Kante

können Verklemmungen durch zyklische

Reihenfolgebeziehungen entstehen. Sol-

che Fälle sind in ADEPTflex ausgeschlos-

sen, weil das WfMS vor der Durchfüh-

rung einer Änderung stets prüft, ob der

resultierende Ausführungsgraph wieder

eine fehlerfreie WF-Ausführung garan-

tiert. Zu diesem Zweck wird analysiert,

ob die Änderung aufgrund des aktuellen

Zustands und der Struktur der WF-In-

stanz zulässig ist, d.h., ob die für die ent-

sprechenden Basisoperationen (formal)

definierten Vor- und Nachbedingungen

erfüllt sind. Nur wenn dies gegeben ist,

wird die Struktur und der Zustand des

Ausführungsgraphen entsprechend ver-

ändert.

3 Dynamische Änderungen in

verteilten WfMS

Prinzipiell laufen dynamische Änderun-

gen in einem verteilten WfMS ebenso ab,

wie in einem zentralen System: Anhand

der Struktur und des Zustands der WF-In-

stanz wird überprüft, ob die gewünschte

Änderung zulässig ist oder nicht. Falls

dem so ist, werden die zugehörigen Basis-

operationen ermittelt und der Ausfüh-

rungsgraph der WF-Instanz wird entspre-

chend modifiziert. Für die Überprüfung

der Zulässigkeit einer Änderung wird der

globale, aktuelle Zustand der WF-Instanz

benötigt. Um diesen Zustand zu ermitteln,

muss im Allgemeinen Zustandsinformati-

on von anderen Servern eingeholt werden

(wie die Übertragung eines Zustandes ef-

fizient möglich ist, wird in [BRD01] be-

schrieben). In diesem Abschnitt wird ein

Verfahren vorgestellt, mit dem die Menge

der WF-Server bestimmt werden kann,

von denen entsprechende Zustandsinfor-

mation benötigt wird. Im Gegensatz zum

zentralen Fall reicht es in einem verteilten

WfMS in der Regel nicht aus, den Ausfüh-

rungsgraphen der WF-Instanz nur auf

demjenigen Server zu modifizieren, der

die Änderung steuert. Deshalb wird in die-

sem Abschnitt geklärt, bei welchen Ser-

vern eine Änderung eingebracht werden

soll.

3.1 Synchronisation von Workflow-

Servern

Eine dynamische Änderung kann von ei-

nem beliebigen Server, der die betroffene

WF-Instanz gerade kontrolliert, initiiert

werden. Dieser WF-Server kann die Än-

derung im Allgemeinen aber nicht alleine

durchführen, sondern er muss für den Fall,

dass aktuell mehrere Server an der WF-

Kontrolle beteiligt sind (Parallelität), ggf.

Zustandsinformation von diesen einho-

len. Des Weiteren muss er veranlassen,

dass die Änderung auch in die von ande-

ren Servern verwalteten Ausführungsgra-

phen dieser WF-Instanz eingebracht wird.

Als naive Lösung könnten alle Server des

WfMS in eine Änderung mit einbezogen

werden, indem entsprechende Aufrufe per

Broadcast verbreitet werden. Dieser An-

satz scheidet aber aus, weil er in den meis-

ten Fällen zu einem unnötig hohen Auf-

wand führen würde, und außerdem eine

dynamische Änderung nur dann durch-

führbar wäre, wenn alle Serverrechner des

WfMS erreichbar sind. Deshalb werden

im Folgenden alternative Vorgehenswei-

sen untersucht.

Ansatz 1: Einbeziehung aller Server

der betroffenen Workflow-Instanz

Bei diesem Ansatz werden nur diejenigen

WF-Server bei der Änderung berücksich-

tigt, die bisher an der WF-Steuerung be-

teiligt waren bzw. es aktuell sind, oder die

zukünftig in die Steuerung der WF-In-

stanz involviert sein werden. Dadurch

wird der Kommunikationsaufwand ge-

genüber der oben erwähnten naiven Lö-

sung zwar merklich reduziert, er ist aber

immer noch unnötig groß. Diejenigen

Server, welche die WF-Instanz aus-

schließlich in der Vergangenheit kontrol-

liert haben, müssen nämlich nicht in die

Änderung einbezogen werden. Mit diesen

Servern ist keine Synchronisation not-

wendig und die von ihnen verwaltete Zu-

standsinformation wurde schon durch Mi-

grationen weitergegeben.

Ansatz 2: Einbeziehung der aktuellen

und zukünftigen Server der Workflow-

Instanz

Um eine WF-Instanz korrekt steuern zu

können, müssen dem zuständigen WF-

Server alle bisher erfolgten dynamischen

Änderungen bekannt sein. Deshalb ist

eine Änderung für alle WF-Server rele-

vant, welche die WF-Instanz aktuell kon-

trollieren oder zukünftig kontrollieren

werden. Darum scheint es naheliegend zu

sein, diese in die Änderungsoperation ein-

zubeziehen. Sollen aber die zukünftigen

Server berücksichtigt werden, so entsteht

Abb. 2: Beispiel für eine dynamische WF-Änderung mit a) Ausführungsgraph, b) Ablaufhistorie

und c) Änderungshistorie (vereinfacht dargestellt)

a b c

c) 1. InsertActivity x After {a} Before {c}:

_ChangeNodeType(a, AND-Split),

_ChangeNodeType(c, AND-Join),

_InsertNode(x), _InsertControlEdge(a,x),

_InsertControlEdge(x,c)

Start(a, ...), End(a, ...), DynModif(1)Start(a, ...), End(a, ...)

Aktivität x zwischen

a und c einfügen

∅

axc

AND-Split AND-Join

Vor der dynamischen Änderung: Nach der dynamischen Änderung:

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

Datenbank-Spektrum 1/2001 71

z.B. im Kontext von variablen Serverzu-

ordnungen (vgl. Abschnitt 2.1) ein Pro-

blem. Es kann nämlich im Allgemeinen

nicht ermittelt werden, welche Server die

WF-Instanz zukünftig steuern werden, da

die zur Auswertung der Serverzuord-

nungsausdrücke notwendigen Laufzeit-

daten der WF-Instanz evtl. noch nicht

existieren. So kann in Abb. 3 bei der Aus-

führung der Aktivität g der Server der Ak-

tivität j nicht ermittelt werden, da der Be-

arbeiter der Aktivität i noch nicht

feststeht. Eine Synchronisation mit zu-

künftigen Servern der WF-Instanz ist also

nicht möglich. Diese Server müssen auch

noch nicht über die Änderung informiert

werden, weil sie die WF-Instanz noch

nicht kontrollieren.

Ansatz 3: Einbeziehung nur der

aktuellen Server der Workflow-

Instanz

Eine Synchronisation mit allen aktuell an

der WF-Instanz beteiligten Servern ist

demnach die einzig akzeptable Lösung.

Es ist aber keineswegs trivial, diese Server

zu ermitteln, weil der Ausführungszu-

stand von parallel ausgeführten Aktivitä-

ten bei verteilter WF-Steuerung nicht be-

kannt sein muss. So weiß z.B. in Abb. 3

der Server s4, der die Aktivität g kontrol-

liert, nicht, ob die Migration Mc,d schon

ausgeführt worden ist, und damit, ob der

parallele Zweig vom Server s2 oder s3

kontrolliert wird. Außerdem ist es nicht

ohne weiteres möglich, den für einen pa-

rallelen Zweig zuständigen Server zu er-

mitteln, wenn variable Serverzuordnun-

gen verwendet werden. So referenziert in

Abb. 3 die Serverzuordnung der Aktivität

e den Bearbeiter der Aktivität c. Dieser ist

aber dem Server s4 nicht bekannt.

3.2 Bestimmung der aktuell an

einer Workflow-Instanz

beteiligten Server

Wie soeben erläutert, ist es einem WF-

Server im Allgemeinen nicht möglich, die

anderen aktuell an einer WF-Instanz be-

teiligten Server aus der lokal vorhandenen

Zustandsinformation zu ermitteln. Diese

durch einen Broadcast-Aufruf zu »su-

chen«, verbietet sich, da dann dieselben

Nachteile wie bei der eingangs von

Abschnitt 3.1 skizzierten naiven Lösung

entstehen. Deshalb muss ein Verfahren

entwickelt werden, bei dem die Menge der

an der Ausführung einer WF-Instanz ak-

tuell beteiligten Server explizit verwaltet

wird. Diese Verwaltung sollte aber nicht

durch einen festen (und damit zentralen)

Server erfolgen, da dieser die Verfügbar-

keit des gesamten WfMS beeinträchtigen

und einen potenziellen Flaschenhals dar-

stellen würde. Deshalb wird diese Menge

ActiveServers in ADEPT von einem WF-

instanzspezifischen ServerManager ver-

waltet. Als ServerManager wird norma-

lerweise jeweils derjenige Server verwen-

det, auf dem die entsprechende WF-

Instanz gestartet wurde.1 Dieser kann von

jedem an der WF-Instanz beteiligten Ser-

ver mit Hilfe der (lokal vorhandenen) Ab-

laufhistorie ermittelt werden und variiert

für verschiedene WF-Instanzen (auch

desselben Typs). Deshalb stellt er keinen

Flaschenhals dar. Im nun folgenden Ab-

schnitt wird beschrieben, wie die Menge

der aktuell für eine WF-Instanz aktiven

Server vom ServerManager verwaltet

wird. In Abschnitt 3.2.2 wird dann erläu-

tert, wie diese Menge bei dynamischen

Änderungen ermittelt und verwendet wer-

den kann.

3.2.1 Verwaltung der aktuell

an einer Workflow-Instanz

beteiligten Server

Um die Menge der an der Ausführung ei-

ner WF-Instanz aktuell beteiligten Server

verwalten zu können, wird ein Verfahren

benötigt, welches die aus einer Migration

resultierende Veränderung der Menge Ac-

tiveServers an den jeweiligen ServerMa-

nager meldet (siehe Algorithmus 1). Der

ServerManager verwendet wiederum ein

Verfahren, mit dem diese Menge manipu-

liert wird (Algorithmus 2). Bei der Reali-

sierung dieser beiden Verfahren muss be-

achtet werden, dass nicht mehrere

Migrationen derselben WF-Instanz belie-

big überlappend durchgeführt werden, da

1. Es kann Szenarien geben, bei denen sich durch

diese Strategie stets derselbe Server ergibt,

weil alle WF-Instanzen auf demselben WF-

Server instanziiert werden (z.B. dem Server,

der in einer Bank für die Terminals der Schal-

ter zuständig ist). In einem solchen Fall sollte

beim Erzeugen einer WF-Instanz z.B. ein zu-

fällig ausgewählter Server als ServerManager

festgelegt werden.

ansonsten Inkonsistenzen bei der Verän-

derung der Menge der aktuellen Server

entstehen können. Außerdem darf sich die

Menge ActiveServers während der Durch-

führung einer dynamischen Modifikation

nicht durch Migrationen verändern, um in

eine dynamische Änderung die richtigen

Server einbeziehen zu können. Dies wird

verhindert, indem von den beiden genann-

ten Verfahren und von dem im

Abschnitt 3.2.2 vorgestellten Verfahren

zur Durchführung von dynamischen Än-

derungen verschiedene Sperren verwen-

det werden. Ihr Zusammenspiel wird im

Folgenden erläutert.

Algorithmus 1 zeigt den Ablauf einer

Migration. Zuerst fordert der Migrations-

quellserver beim ServerManager eine

nicht exklusive Sperre an.2 Dann wird

eine exklusive Kurzzeitsperre angefor-

dert,3 durch die sichergestellt wird, dass

die Veränderung der Servermenge für

eine gegebene WF-Instanz nicht gleich-

zeitig für mehrere Migrationen paralleler

Zweige vorgenommen wird. Die bei ei-

ner Migration resultierende Änderung

der Servermenge wird vom Quellserver

an den ServerManager gemeldet. Dabei

wird angegeben, ob der Quellserver der

Migration weiterhin an der entsprechen-

den WF-Instanz beteiligt ist (Stay) oder

nicht (LogOff). Findet in dem Beispiel

aus Abb. 3 die Migration Mb,c vor Mf,g

statt, so wird bei Mb,c die Option Stay

verwendet, da der Server s1 diese WF-In-

stanz weiterhin kontrolliert. Dementspre-

chend erfolgt die später stattfindende Mi-

gration Mf,g mit der Option LogOff, weil

hiermit der letzte vom Server s1 kontrol-

lierte Zweig beendet wird. Dass die bei-

den Migrationen gleichzeitig ausgeführt

werden, ist wegen der zuvor gewährten

(exklusiven) Kurzzeitsperre ausgeschlos-

2. Die Sperre verhindert nicht, dass mehrere Mi-

grationen derselben WF-Instanz gleichzeitig

durchgeführt werden. Ihr Zweck wird im Zu-

sammenhang mit Algorithmus 3 klar.

3. Die beiden Sperranforderungen können auch

zu einem einzigen Aufruf zusammengefasst

werden, um so einen Kommunikationszyklus

einzusparen.

i j

Teilnetz(

Bearb(i))

Teilnetz(

Bearb(c))

Abb. 3 Einfügen der Aktivität x durch den Server s

zwischen den Aktivitäten g

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

72 Datenbank-Spektrum 1/2001

sen. Deshalb ist stets klar, ob ein WF-Ser-

ver nach Beendigung einer Migration

noch an der WF-Instanz beteiligt ist oder

nicht. Als nächstes werden die WF-In-

stanzdaten zum Migrationszielserver

übertragen. Da zu diesem Zeitpunkt die

exklusive Kurzzeitsperre schon freigege-

ben wurde (durch MigrateWorkflowIn-

stance), können weiterhin mehrere Mi-

grationen derselben WF-Instanz gleich-

zeitig durchgeführt werden. Der

Algorithmus endet damit, dass auch die

nicht exklusive Sperre wieder freigege-

ben wird.

Der Algorithmus 2 wird vom Server-

Manager verwendet, um die aktuell an ei-

ner bestimmten WF-Instanz beteiligten

Server zu verwalten. Um diese Aufgabe

erfüllen zu können, muss der ServerMa-

nager zusätzlich die erwähnten Sperren

verwalten. Wird die Funktion UpdateAc-

tiveServers mit der Option LogOff aufge-

rufen, so wird der Migrationsquellserver

aus der Menge ActiveServers(Inst) der

aktuellen WF-Server entfernt, weil dieser

Server dann nicht mehr an der WF-

Instanz beteiligt ist. Der Migrationsziel-

server wird stets in diese Menge aufge-

nommen, unabhängig davon, ob er schon

enthalten ist oder nicht, da die entspre-

chende Operation idempotent ist. Durch

die vom Algorithmus 1 vor dem Aufruf

von UpdateActiveServers angeforderte

Kurzzeitsperre wird schließlich verhin-

dert, dass der Algorithmus 2 für eine WF-

Instanz mehrfach parallel durchlaufen

wird, so dass Fehler durch das überlap-

pende Verändern der Menge ActiveSer-

vers(Inst) ausgeschlossen sind. Nach der

Anpassung dieser Menge wird die er-

wähnte Kurzzeitsperre wieder freigege-

ben.

3.2.2 Durchführung dynamischer

Änderungen

Im vorherigen Abschnitt wurde beschrie-

ben, wie der ServerManager die Menge

der aktuell an einer WF-Instanz beteilig-

ten Server verwaltet. Im Folgenden wird

erläutert, wie diese Menge bei der Durch-

führung einer dynamischen Änderung

verwendet wird. Zu diesem Zweck fordert

sie derjenige WF-Server, der eine Ände-

rung durchführen möchte, beim Server-

Manager an.

Wichtig ist, dass sich während der

Durchführung einer dynamischen Ände-

rung die Menge der an der betroffenen

WF-Instanz beteiligten Server nicht

durch Migrationen verändert, weil sonst

evtl. die falschen Server in die Änderung

einbezogen würden. Außerdem darf der

Ausführungsgraph einer WF-Instanz

nicht gleichzeitig durch mehrere Ände-

rungen umstrukturiert werden, da dies zu

einem unzulässigen Graphen führen

könnte. Um beides zu verhindern, fordert

der Algorithmus 3 beim ServerManager

eine exklusive Sperre an. Diese ent-

spricht einer Schreibsperre [GR93,

HR99] in einem Datenbanksystem und

ist mit Lesesperren (RequestSharedLock

aus Algorithmus 1) und weiteren

Schreibsperren derselben WF-Instanz

unverträglich. Dadurch wird verhindert,

dass für eine zu ändernde WF-Instanz

zeitgleich Migrationen stattfinden. Nach

Gewährung der Sperre wird die Menge

der für diese WF-Instanz aktiven Server

erfragt.1 Bei allen Servern der Menge Ac-

tiveServers wird nun eine Sperre angefor-

dert, die lokale Veränderungen des Zu-

stands der WF-Instanz verhindert. Be-

reits gestartete Aktivitäten können aber

weiterhin beendet werden, da die entspre-

chenden Zustände im ADEPTflex-Modell

äquivalent sind. Dann wird die (gesperr-

te) Zustandsinformation bei allen an der

1. Dies kann auch mit dem Anfordern der Sperre

zu einem einzigen Aufruf zusammengefasst

werden, um so einen Kommunikationszyklus

einzusparen.

Algorithmus 1 (Durchführung einer Migration)

input

Inst

: ID der zu migrierenden WF-Instanz

SourceServer

: Quellserver der Migration (führt diesen Algorithmus aus)

TargetServer

: Zielserver der Migration

begin

// Verwaltungsserver für die WF-Instanz aus Ablaufhistorie ermitteln

ServerManager = StartServer(Inst)

;

// nicht exklusive Sperre und exkl. Kurzzeitsperre beim

ServerManager

anfordern

// (

p()

→

bedeutet, dass die Prozedur

beim Server

aufgerufen wird)

RequestSharedLock(Inst)

→

ServerManager

;

RequestShortTermLock(Inst)

→

ServerManager

;

// Menge der aktuellen Server ändern (

UpdateActiveServers

, siehe Algorithmus 2)

LastBranch(Inst)

then

// die Migration erfolgt im letzten beim

SourceServer

aktiven

// Ausführungszweig der WF-Instanz

UpdateActiveServers(Inst, SourceServer, LogOff, TargetServer)

→

ServerManager

;

else

// ein weiterer Ausführungszweig ist bei

SourceServer

aktiv

UpdateActiveServers(Inst, SourceServer, Stay, TargetServer)

→

ServerManager

;

// eigentliche Migration durchführen und nicht exklusive Sperre freigeben

MigrateWorkflowInstance(Inst)

→

TargetServer

;

ReleaseSharedLock(Inst)

→

ServerManager

;

end.

Algorithmus 2 (

UpdateActiveServers:

Verwaltung der aktiven WF-Server)

input

Inst

: ID der betroffenen WF-Instanz

SourceServer

: Quellserver der Migration

Option

: gibt an, ob der Quellserver weiterhin in die WF-Instanz involviert ist (

Stay)

oder nicht (

LogOff

)

TargetServer

: Zielserver der Migration

begin

// Menge der für die WF-Instanz

Inst

aktiven WF-Server aktualisieren

Option = LogOff

then

ActiveServers(Inst) = ActiveServers(Inst) - {SourceServer}

;

ActiveServers(Inst) = ActiveServers(Inst)

∪

{TargetServer}

;

// die Kurzzeitsperre wieder freigeben

ReleaseShortTermLock(Inst)

;

end.

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

Datenbank-Spektrum 1/2001 73

WF-Instanz beteiligten Servern einge-

holt. Der hierdurch resultierende globale

und aktuelle Zustand einer WF-Instanz

wird benötigt, um prüfen zu können, ob

eine bestimmte Änderung zulässig ist

oder nicht. So ist in dem Beispiel aus

Abb. 3 dem Server s4, der gerade die Ak-

tivität g kontrolliert und eine Aktivität x

nach der Aktivität g und vor d einfügen

will, der aktuelle Zustand der Aktivität d

des parallelen Zweiges nicht bekannt.

Die dynamische Änderung ist aber nur

dann zulässig, wenn die Aktivität d zum

Zeitpunkt der Änderung noch nicht ge-

startet wurde [RD98]. Ist dies der Fall, so

wird sie bei allen an der WF-Instanz be-

teiligten Servern durchgeführt (Perform-

DynamicModification). Anschließend

werden die Sperren wieder freigegeben,

woraufhin blockierte Migrationen und

Änderungsoperationen durchgeführt

werden können.

4 Verteilte Ausführung

veränderter Workflow-

Instanzen

Bei einer Migration muss der aktuelle Zu-

stand der betroffenen WF-Instanz über-

mittelt werden. Dies geschieht in ADEPT-

distribution, indem die Ablaufhistorie

(partiell) übertragen wird [BRD01]. Au-

ßerdem werden die Werte von WF-rele-

vanten Daten transferiert. Im Falle von

dynamischen Änderungen muss der Mig-

rationszielserver zusätzlich den veränder-

ten Graphen der WF-Instanz kennen, da-

mit er diese korrekt steuern kann. Bei dem

im vorherigen Abschnitt vorgestellten

Verfahren werden nur die aktuell an der zu

verändernden WF-Instanz beteiligten

Server in die Änderung einbezogen. Die

Server nachfolgender Aktivitäten müssen

dagegen ggf. noch über die erfolgten Än-

derungen informiert werden. Die hierzu

erforderliche Informationsübermittlung

findet jeweils bei den Migrationen der

WF-Instanz zu diesen Servern statt. Da

Migrationen recht häufige Operationen

sind, muss die Übertragung der entspre-

chenden Information auf eine effiziente

Art und Weise erfolgen. Im Abschnitt 4.1

wird ein Verfahren vorgestellt, das diese

Bedingung schon recht gut erfüllt. Dieses

Verfahren wird in Abschnitt 4.2 noch op-

timiert, so dass redundante Datenübertra-

gungen völlig ausgeschlossen sind.

4.1 Effiziente Übermittlung von

dynamischen Änderungen

Im Folgenden wird untersucht, wie ein

veränderter WF-Ausführungsgraph dem

Zielserver einer Migration bekannt ge-

macht werden kann. Dabei wird ange-

strebt, ein bezüglich der Kommunika-

tionskosten möglichst effizientes Verfah-

ren zu erhalten.

Die einfachste Möglichkeit, um dem

Migrationszielserver den aktuellen Aus-

führungsgraphen bekannt zu machen, ist

natürlich, diesen vollständig zu übertra-

gen. Allerdings resultiert aus dieser Vor-

gehensweise eine unnötig hohe Belastung

für das Kommunikationssystem, da diese

Graphen viele Knoten und Kanten umfas-

sen können, weshalb ihre Beschreibung

sehr groß sein kann. Aus diesem Grund

scheidet dieser ineffiziente Ansatz aus.

Es ist auch nicht notwendig, den ge-

samten Ausführungsgraphen an den Ziel-

server einer Migration zu übertragen, da

dieser Server die zugehörige WF-Vorlage

schon kennt. Diese stimmt weitestgehend

mit dem aktuellen Ausführungsgraphen

der WF-Instanz überein, so dass es we-

sentlich effizienter ist, lediglich die ver-

hältnismäßig kleine Beschreibung der an-

gewandten Änderungsoperation(en) zu

übertragen. Die Verwendung der Ände-

rungshistorie bietet eine gute Möglich-

keit, um diese Idee umzusetzen. Diese

Historie wird im ADEPTflex-Modell vom

Migrationszielserver ohnehin benötigt

[RD98], so dass aus ihrer Übertragung

kein zusätzlicher Aufwand resultiert.

Werden die in der Änderungshistorie ver-

merkten Basisoperationen auf die ur-

sprüngliche WF-Vorlage angewandt, so

ergibt sich der benötigte aktuelle Graph

der WF-Instanz. Wir erhalten somit ein

einfach zu realisierendes Verfahren zur

Übermittlung eines Ausführungsgra-

phen, durch das der Kommunikationsauf-

wand drastisch reduziert wird. Da auf

eine einzelne WF-Instanz in der Regel

nur sehr wenige Änderungen angewandt

werden, ist der zum Berechnen des aktu-

ellen Ausführungsgraphen notwendige

Aufwand gering.

4.2 Optimiertes Verfahren

Im Allgemeinen kann derselbe WF-Ser-

ver mehrere Male an der Steuerung einer

WF-Instanz beteiligt sein. So gibt der Ser-

ver s1 in dem Beispiel aus Abb. 4 die Kon-

trolle nach Beendigung der Aktivität d ab,

erhält sie später aber zur Steuerung der

Aktivität f wieder zurück. Ein solcher Ser-

ver kennt deshalb bereits die Änderungs-

historieneinträge zu den von ihm selbst

durchgeführten Änderungen (da er die

Änderungshistorie solange aufbewahrt,

Algorithmus 3 (Durchführung einer dynamischen Änderung)

input

Inst

: ID der zu ändernden WF-Instanz

Modification

: Spezifikation der dynamischen Änderung

begin

// Verwaltungsserver für die WF-Instanz ermitteln

ServerManager = StartServer(Inst)

;

// Exklusive Sperre beim

ServerManager

anfordern und aktuelle Servermenge ermitteln

RequestExclusivLock(Inst)

→

ServerManager

;

ActiveServers = GetActiveServers(Inst)

→

ServerManager

;

// bei allen Servern Sperre anfordern, aktuellen Zustand ermitteln und ggf.

// Änderung durchführen

for

each Server

∈

ActiveServers

RequestStateLock(Inst)

→

;

GlobalState = GetLocalState(Inst)

;

for

each Server

∈

ActiveServers

LocalState = GetLocalState(Inst)

→

;

GlobalState = GlobalState

∪

LocalState

;

DynamicModificationPossible(Inst, GlobalState, Modification)

then

for

each Server

∈

ActiveServers

PerformDynamicModification(Inst, GlobalState, Modification)

→

;

// alle Sperren wieder freigeben

for

each Server

∈

ActiveServers

ReleaseStateLock(Inst)

→

;

ReleaseExclusivLock(Inst)

→

ServerManager

;

end.

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

74 Datenbank-Spektrum 1/2001

bis er über die Beendigung der entspre-

chenden WF-Instanz informiert wird).

Zusätzlich kennt er alle Änderungen, die

erfolgt sind, bevor er letztmals die WF-In-

stanz kontrolliert hat. Der zu solchen Än-

derungen gehörende Teil der Änderungs-

historie muss also nicht mehr zu diesem

Server übertragen werden, wodurch das

zur Migration des »aktuellen Aus-

führungsgraphen« notwendige Daten-

volumen weiter reduziert werden kann.

Dass die Migrationen gleichzeitig

durchgeführt werden, wird durch eine

vom Migrationszielserver gehaltene

Sperre verhindert. Diese sorgt dafür, dass

die zur selben WF-Instanz eingehenden

Migrationen serialisiert werden, d.h. die

Sperre wird ab dem Anstoßen der Migra-

tion, während dem Ermitteln und Über-

tragen der Änderungshistorieneinträge

(und der anderen WF-Daten [BRD01]),

bis zur Integration der Einträge in die Än-

derungshistorie gehalten. Diese Sperre

verhindert, dass Einträge redundant an-

gefordert werden, weil von veralteter lo-

kaler Information ausgegangen wird.1

4.2.1 Versenden von Änderungs-

historieneinträgen

Die nahe liegendeste Idee, um redundante

Übertragungen von Änderungshistori-

eneinträgen zu vermeiden, besteht darin,

dass der Migrationsquellserver aus der

ihm bekannten Ablaufhistorie ermittelt,

welche Änderungen dem Zielserver

schon bekannt sein müssen. Die entspre-

chenden Einträge werden dann nicht mehr

übertragen. So kann in dem in Abb. 4 dar-

gestellten Beispiel der Server s2 nach Be-

endigung der Aktivität e ermitteln, dass

der Migrationszielserver s1 die Änderun-

gen 1 und 2 schon kennen muss. Der

Grund dafür ist, dass sich in der Ablauf-

historie die Verweise (DynModif) auf die-

se Änderungen vor dem Eintrag für die

Beendigung der vom Server s1 kontrol-

lierten Aktivität d befinden. Deshalb muss

bei der Migration Me,f ausschließlich der

Änderungshistorieneintrag zur Änderung

3 übertragen werden.

Allerdings kann mit dem skizzierten

Verfahren eine redundante Übertragung

von Änderungshistorieneinträgen nicht

1. Bei verteilter WF-Steuerung wird in einer Ab-

laufhistorie, zusätzlich zu den in Abschnitt 2.2

beschriebenen Werten, in jedem Eintrag ver-

merkt, welcher Server die entsprechende Akti-

vität kontrolliert hat.

immer verhindert werden: Bei den Migra-

tionen

und

zum Server

müs-

sen prinzipiell die Einträge zu den Ände-

rungen 1, 2 und 3 übertragen werden, da

der Server

bisher nicht an der Ausfüh-

rung der WF-Instanz beteiligt war. Der

Migrationsquellserver

bzw.

kann

aber aus der bei ihm lokal vorhandenen In-

formation nicht ableiten, ob die jeweils

andere Migration schon erfolgt ist. Des-

halb muss bei beiden Migrationen die ge-

samte Änderungshistorie übertragen wer-

den. Durch das im nächsten Abschnitt vor-

gestellte Verfahren wird eine solch

redundante Datenübertragung vermieden.

4.2.2 Anfordern von Änderungs-

historieneinträgen

Um das im vorherigen Abschnitt be-

schriebene Problem zu lösen, wird nun ein

Verfahren vorgestellt, bei dem die noch

benötigten Änderungshistorieneinträge

durch den Migrationszielserver explizit

angefordert werden. Dieser teilt dem

Quellserver bei einer Migration mit, wel-

che Einträge ihm schon bekannt sind, so

dass die fehlenden Änderungshistori-

eneinträge gezielt übertragen werden

können. In ADEPTdistribution wird für die

Übertragung von Ablaufhistorien ein ähn-

liches Verfahren verwendet, das ebenfalls

auf dem Anfordern von noch benötigter

Information basiert (siehe [BRD01]). Das

Anfordern und Übertragen von Ände-

rungshistorieneinträgen kann im selben

Kommunikationszyklus erfolgen, so dass

hierfür keine zusätzliche Kommunikation

notwendig wird.

Das Anfordern des noch fehlenden

Teils der Änderungshistorie ist bei dem

hier beschriebenen Verfahren relativ ein-

fach und effizient implementierbar, da

stets jeder an einer WF-Instanz beteiligte

Server alle bis zum aktuellen Zeitpunkt

erfolgten Änderungen kennt. Deshalb ist

einem Migrationszielserver der »An-

fang« der Änderungshistorie bekannt,

d.h. er verfügt bis zu einer bestimmten

Stelle über alle Einträge und ab dieser

Stelle kennt er keine weiteren Einträge.

Zum Anfordern der fehlenden Teile der

Änderungshistorie genügt es folglich, die

ID des letzten bekannten Eintrags an den

Quellserver der Migration zu übertragen,

woraufhin dieser alle auf diesen Eintrag

folgenden Einträge übermittelt.

Das soeben angedeutete Verfahren

wird durch den Algorithmus 4 realisiert.

Dieser wird von dem Migrationsquellser-

ver als Teil der Prozedur MigrateWork-

flowInstance (vgl. Algorithmus 1) ausge-

führt, von der außerdem die Ablaufhisto-

rie und die WF-relevanten Daten

übertragen werden (siehe [BRD01]). Der

Algorithmus 4 stößt die Übertragung der

Änderungshistorie an, indem die ID des

neuesten beim Migrationszielserver be-

kannten Änderungshistorieneintrags er-

fragt wird. Ist diesem Server noch keine

Änderungshistorie zu dieser WF-Instanz

bekannt, so gibt er NULL zurück. In die-

sem Fall ist für ihn die gesamte am Quell-

server bekannte Änderungshistorie rele-

vant. Andernfalls ist für den Zielserver

die Änderungshistorie erst ab dem Histo-

rieneintrag relevant, der auf den zurück-

gemeldeten Eintrag folgt. Der jeweils re-

levante Teil der Änderungshistorie wird

in die Historie RelevantChangeHistory

kopiert und zum Zielserver übertragen.

Dies kann in einer einzigen Übertragung

gemeinsam mit den anderen oben er-

wähnten WF-Daten geschehen.

Die Funktionsweise des Algorith-

mus 4 soll an dem in Abb. 4 dargestell-

ten Beispiel verdeutlicht werden: Bei der

Migration Me,f kennt der Zielserver s1 die

dynamischen Änderungen 1 und 2. Des-

halb gibt er LastEntry = 2 zurück, wor-

aufhin der Migrationsquellserver die Än-

derungshistorieneinträge 1 und 2 igno-

riert und nur den Eintrag 3 überträgt.

Damit ergibt sich dasselbe Ergebnis, wie

bei dem im Abschnitt 4.2.1 vorgestellten

Ansatz. Für die Migrationen Mc,h und

Mf,g wird o.B.d.A. angenommen, dass

Mc,h zuerst durchgeführt wird.2 Da der

f g

s1s3

s1s2s1s4

b) Start(a, s1, ...), DynModif(1), End(a, s1, ...), DynModif(2), Start(d, s1, ...), End(d, s1, ...),

Start(e, s2, ...), DynModif(3), End(e, s2, ...)

Abb. 4 a) WF-Instanz und b) Ablaufhistorie

des Servers s

nach Beendigung der Aktivität e

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

Datenbank-Spektrum 1/2001 75

Server s4 noch über keine Änderungs-

historie zu dieser WF-Instanz verfügt, er-

gibt sich bei dieser Migration LastEntry

= NULL, weshalb die gesamte Historie

übertragen wird. Bei der anschließend

stattfindenden Migration Mf,g sind dem

Zielserver s4 die Historieneinträge 1 bis 3

bekannt, weshalb LastEntry den Wert 3

erhält. Beim Durchlaufen der While-

Schleife von Algorithmus 4 wird die Va-

riable Relevant erst dann auf True gesetzt,

nachdem die Einträge 1 bis 3 bearbeitet

wurden. Da keine weiteren Einträge in

der Änderungshistorie folgen, bleibt Re-

levantChangeHistory leer, so dass keine

Änderungshistorieneinträge übermittelt

werden. Das aus Abschnitt 4.2.1 bekann-

te Problem der redundanten Datenüber-

tragung wird hier also vermieden.

Mit den vorgestellten Verfahren ist es

nicht nur möglich, dynamische Änderun-

gen in einem verteilten WfMS effizient

durchzuführen (siehe Abschnitt 3), ver-

änderte WF-Instanzen können außerdem

mit sehr geringen Übertragungskosten

migriert werden. Insgesamt ergibt sich

dadurch das in Abb. 5 dargestellte Ver-

halten (zur Durchführung von dynami-

schen Änderungen siehe [RD98, Rei00]).

5 Diskussion

In der WF-Literatur finden sich zahlreiche

Arbeiten, die sich mit Skalierbarkeitsfra-

gestellungen und verteilter WF-Ausfüh-

rung beschäftigen (z.B. [AKA+94,

AMG+95, BMR96, CGP+96, GJS+99,

GT98, Jab97, MWW+98, SK97, SM96,

Wes99]). Einen umfassenden Überblick

bietet [BD99b]. Ebenso gibt es viele Ver-

öffentlichungen zu dem Thema dynami-

sche WF-Änderungen (z.B. [BPS97,

CCPP98, DMP97, EM97, HK96, HSS96,

JH98, KG99, KRW90, LP98, MR00,

Sie98, Wes98]), die in [Rei00] diskutiert

2. Dass die Migrationen gleichzeitig durchge-

führt werden, wird durch eine vom Migrati-

onszielserver gehaltene Sperre verhindert.

Diese sorgt dafür, dass die zur selben WF-In-

stanz eingehenden Migrationen serialisiert

werden, d.h. die Sperre wird ab dem Anstoßen

der Migration, während dem Ermitteln und

Übertragen der Änderungshistorieneinträge

(und der anderen WF-Daten [BRD01]), bis zur

Integration der Einträge in die Änderungs-

historie gehalten. Diese Sperre verhindert,

dass Einträge redundant angefordert werden,

weil von veralteter lokaler Information ausge-

gangen wird.

werden. Jedoch gibt es kaum Projekte, die

beide Aspekte gemeinsam betrachten –

insbesondere wird deren Zusammenspiel

nicht hinreichend gewürdigt. Es ist nicht

das Ziel dieser Projekte, ein bezüglich der

Kommunikationskosten effizientes WfMS

zu entwickeln, das skalierbar und flexibel

ist. Dieser Aspekt wird in der vorliegenden

Arbeit erstmalig systematisch untersucht.

WIDE erlaubt dynamische Änderun-

gen einer WF-Vorlage und deren Propa-

gierung auf laufende WF-Instanzen

[CCPP98]. Außerdem werden WF-In-

stanzen verteilt gesteuert [CGP+96], wo-

bei die Bearbeiter einer Aktivität den

WF-Server determinieren, der diese Ak-

tivität kontrolliert. Bei MOKASSIN

[GJS+99, JH98] und WASA [Wes98,

Wes99] wird die verteilte WF-Ausfüh-

rung durch eine zugrunde liegende COR-

BA-Infrastruktur realisiert. Außerdem

sind Änderungen auf Schema- und auf

Instanzebene möglich, wobei auch Kon-

sistenzfragestellungen betrachtet werden.

INCAs [BMR96] verwirklicht die Steue-

rung der WF-Instanzen durch Regeln, die

modifiziert werden können, um dynami-

sche Änderungen durchzuführen. Die

WF-Steuerung findet verteilt statt, wobei

eine WF-Instanz stets von dem Rechner

desjenigen Benutzers kontrolliert wird,

der die aktuelle Aktivität bearbeitet. Bei

all diesen Ansätzen wird aber nicht expli-

zit auf das Zusammenspiel der dynami-

schen Änderungen und der verteilten

WF-Ausführung eingegangen.

In der Literatur finden sich auch eini-

ge Ansätze für verteiltes WF-Manage-

ment, bei denen eine WF-Instanz wäh-

rend ihrer gesamten Lebenszeit von nur

einem einzigen WF-Server kontrolliert

wird (z.B. Exotica [AKA+94], MOBILE

[Jab97] – MOBILE wurde aber in

[SNS99] erweitert). Es finden also keine

Migrationen statt, unterschiedliche WF-

Instanzen können aber von verschiede-

nen Servern kontrolliert werden. Da für

jede WF-Instanz eine zentrale Kontroll-

instanz existiert, könnten dynamische

Änderungen bei diesen Ansätzen also ge-

nauso wie in einem zentralen WfMS

durchgeführt werden. Allerdings ist es

bei diesem Verteilungsmodell nicht mög-

lich, für jede einzelne Aktivität einen be-

züglich der Kommunikationskosten gün-

stigen WF-Server auszuwählen. Da des-

halb bei der »normalen WF-Ausführung«

höhere Mehrkosten entstehen, als die bei

den (verhältnismäßig seltenen) dynami-

schen Änderungen erzielten Einsparun-

gen, wurde für ADEPT kein solcher An-

satz gewählt.

Algorithmus 4 (Übermittlung einer dynamischen Änderung)

input

Inst

: ID der zu ändernden WF-Instanz

TargetServer

: Server, an den die Änderungshistorie übertragen wird

begin

// Übertragung der Änderungshistorie anstoßen, indem ID des letzten bekannten

// Eintrags erfragt wird

LastEntry = GetLastEntry(Inst)

→

TargetServer

;

// für Übertragung relevanten Teil der Änderungshistorie ermitteln

LastEntry = NULL

then

// am Zielserver ist Änderungshistorie überhaupt noch nicht bekannt

Relevant = True

;

else

// alle Einträge bis einschließlich

LastEntry

sind am Zielserver schon bekannt

Relevant = False

;

// Positionszähler für originale und zu erzeugende Änderungshistorie initialisieren

= 1;

// gesamte Änderungshistorie der WF-Instanz

Inst

durchlaufen

while

ChangeHistory(Inst)[i]

≠

EOF

Relevant = True

then

// Eintrag ggf. in Ergebnis übernehmen

RelevantChangeHistory[j] = ChangeHistory(Inst)[i]

;

+ 1;

// Prüfen, ob das Ende der am Zielserver bekannten Historie erreicht wurde

EntryID(ChangeHistory(Inst)[i]) = LastEntry

then

Relevant = True

;

+ 1;

// Übertragung der Änderungshistorie durchführen

TransmitChange(Inst, RelevantChangeHistory)

→

TargetServer

;

end.

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

76 Datenbank-Spektrum 1/2001

6 Zusammenfassung und

Ausblick

Verteilte WF-Ausführung und dynami-

sche Änderungen sind essenziell, um

WfMS auch zur Unterstützung von an-

spruchsvollen vorgangsorientierten An-

wendungssystemen einsetzen zu können.

Allerdings sind mit diesen beiden Aspek-

ten teilweise entgegengesetzte Anforde-

rungen und Ziele verbunden, da die für

dynamische Änderungen notwendige

zentrale Kontrollinstanz die Effizienz der

verteilten WF-Ausführung beeinträchtigt.

Deshalb können die beiden Themen nicht

getrennt voneinander betrachtet werden.

Ihre Wechselwirkungen werden in dieser

Arbeit erstmalig untersucht, mit dem Er-

gebnis, dass die beiden Aspekte durchaus

vereinbar sind. Es ist gelungen, dynami-

sche Änderungen in einem verteilten

WfMS auf effiziente Art und Weise zu

realisieren. Auch die verteilte Steuerung

einer zuvor veränderten WF-Instanz ist

äußerst effizient möglich, da zur Über-

mittlung des modifizierten Ausführungs-

graphen lediglich ein Teil der ohnehin

relativ kleinen Änderungshistorie über-

tragen werden muss. Dies ist besonders

wichtig, da Migrationen häufige Operati-

onen sind. Zusammenfassend lässt sich

feststellen, dass es gelungen ist, verteilte

WF-Ausführung und dynamische Ände-

rungen nahtlos in ein System zu integrie-

ren.

Alle in diesem Beitrag vorgestellten

Verfahren wurden in dem WfMS-Proto-

typen ADEPTworkflow implementiert

[HRB+00, Zei99]. Dieser Prototyp wurde

auf der CeBIT’2000, der EDBT’2000

[HRB+00] und der BIS’2000 [DRK00]

einem breiten Publikum präsentiert.

Durch die Implementierung konnte die

Umsetzbarkeit der Verfahren gezeigt

werden. Außerdem ist bei der Durchfüh-

rung von Migrationen zu erkennen, dass

nur moderate Datenmengen übertragen

werden müssen.

Optimierungspotenzial besteht noch

hinsichtlich der Wahl der WF-Server, die

in eine dynamische Änderung einbezo-

gen werden müssen: Betrifft eine Ände-

rung nur einen Ausschnitt des WF-Gra-

phen, so könnte eine Änderung auch nur

von einem Teil der aktuell in die WF-In-

stanz involvierten WF-Server durchge-

führt werden, wodurch der Synchronisa-

tions- und Kommunikationsaufwand re-

duziert wird. Im Extremfall wird nur ein

einziger Zweig einer Parallelität verän-

dert, weshalb eigentlich auch nur ein Ser-

ver für die Durchführung der Änderung

benötigt wird. Allerdings können Aktivi-

täten paralleler Ausführungszweige (z.B.

durch Abhängigkeiten im Datenfluss

oder durch entsprechend festgelegte tem-

porale Bedingungen) von dieser Ände-

rung betroffen sein, so dass die zugehöri-

gen Server in diesem Fällen doch einbe-

zogen werden müssen. Unsere bisherigen

Untersuchungen ergaben, dass eine sol-

che Optimierung deshalb eher selten ein-

gesetzt werden kann, so dass eine signifi-

kante Verbesserung des Systemverhal-

tens nicht zu erwarten ist. Dennoch bietet

dieser Aspekt Ansatzpunkte für weiterge-

hende Forschung.

Danksagung: Wir danken Thomas Fries, Cle-

mens Hensinger und Jochen Zeitler für die

anregenden Diskussionen.

Literatur

[AKA+94] G. Alonso, M. Kamath, D. Agrawal,

A. El Abbadi, R. Günthör und C. Mohan.

Failure Handling in Large Scale Workflow

Management Systems. Technical Report

RJ9913, IBM Almaden Research Center, No-

vember 1994.

[AMG+95] G. Alonso, C. Mohan, R. Günthör, D.

Agrawal, A. El Abbadi und M. Kamath. Exo-

tica/FMQM: A Persistent Message-Based Ar-

chitecture for Distributed Workflow Manage-

ment. In Proc. IFIP Working Conf. on

Information Systems for Decentralized Orga-

nisations, Trondheim, August 1995.

[Bau01] T. Bauer. Effiziente Realisierung unter-

nehmensweiter Workflow-Management-Sys-

teme. Dissertation, Universität Ulm, Fakultät

für Informatik, Februar 2001. (erschienen

beim Tenea-Verlag Berlin).

[BD97] T. Bauer und P. Dadam. A Distributed

Execution Environment for Large-Scale

Workflow Management Systems with Subnets

and Server Migration. In Proc. 2nd IFCIS

Conf. on Cooperative Information Systems,

S. 99-108, Kiawah Island, SC, Juni 1997.

[BD99a] T. Bauer und P. Dadam. Efficient Distri-

buted Control of Enterprise-Wide and Cross-

Enterprise Workflows. In Proc. Workshop

Enterprise-wide and Cross-enterprise Work-

Sicht des WF-Servers s1:

Migration vom Server s1 zum Server s2



a



Sicht des WF-Servers s2:



∅

s1 holt Zustandsinformation zur Vorbereitung einer dynamischen Änderung ein (Einfügen von x nach {a} und vor {c, e}

durch den Server s1)



a







Durchführung der dynamischen Änderung durch s1 (Modifikation des Ausführungsgrahpen bei allen aktuellen Servern)



a







Verteilte Ausführung der Aktivitäten b durch s1 und d durch s2 (im Zuge der normalen Ausführung erfolgt keine

Zustandssynchronisation)



a







Legende:

Aktivität ist beendet

Aktivität ist aktiviert

Abb. 5 Auswirkungen von Migrationen und dynamischen Änderungen auf den Zustand und die

Struktur einer WF-Instanz (lokale Sicht der WF-Server)

Dynamische Ablaufänderungen in verteilten Workflow-Management-Systemen

Datenbank-Spektrum 1/2001 77

flow Management: Concepts, Systems, Ap-

plications, 29. Jahrestagung der GI, S. 25-32,

Paderborn, Oktober 1999.

[BD99b] T. Bauer und P. Dadam. Verteilungs-

modelle für Workflow-Management-Systeme

– Klassifikation und Simulation. Informatik

Forschung und Entwicklung, 14(4):203-217,

Dezember 1999.

[BD00] T. Bauer und P. Dadam. Efficient Distri-

buted Workflow Management Based on Va-

riable Server Assignments. In Proc. 12th

Conf. on Advanced Information Systems En-

gineering, S. 94-109, Stockholm, Juni 2000.

[BMR96] D. Barbará, S. Mehrotra und M. Rusin-

kiewicz. INCAs: Managing Dynamic Work-

flows in Distributed Environments. Journal of

Database Management, Special Issue on Mul-

tidatabases, 7(1):5-15, 1996.

[BPS97] P. Bichler, G. Preuner und M. Schrefl.

Workflow Transparency. In Proc. 9th Int.

Conf. on Advanced Information Systems En-

gineering, S. 423-436, Barcelona, 1997.

[BRD01] T. Bauer, M. Reichert und P. Dadam.

Effiziente Übertragung von Prozessinstanz-

daten in verteilten Workflow-Management-

Systemen. Informatik Forschung und Ent-

wicklung, 16(2):76-92, Juni 2001.

[CCPP98] F. Casati, S. Ceri, B. Pernici und G.

Pozzi. Workflow Evolution. Data & Know-

ledge Engineering, 24(3):211-238, 1998.

[CGP+96] F. Casati, P. Grefen, B. Pernici, G.

Pozzi und G. Sánchez. WIDE: Workflow Mo-

del and Architecture. CTIT Technical Report

96-19, University of Twente, 1996.

[DMP97] B. Dellen, F. Maurer und G. Pews.

Knowledge Based Techniques to Increase the

Flexibility of Workflow Management. Data &

Knowledge Engineering, 1997.

[DRK00] P. Dadam, M. Reichert und K. Kuhn.

Clinical Workflows – The Killer Application

for Process-oriented Information Systems? In

Proc. 4th Int. Conf. on Business Information

Systems, S. 36-59, Posen, April 2000.

[EM97] C.A. Ellis und C. Maltzahn. The

Chautauqua Workflow System. In Proc. 30th

Hawaii Int. Conf. on System Sciences, Maui,

Hawaii, 1997.

[GJS+99] B. Gronemann, G. Joeris, S. Scheil, M.

Steinfort und H. Wache. Supporting Cross-

Organizational Engineering Processes by

Distributed Collaborative Workflow Mana-

gement – The MOKASSIN Approach. In Proc.

2nd Symposium on Concurrent Multidiscipli-

nary Engineering, 3rd Int. Conf. on Global

Engineering Networking, Bremen, Septem-

ber 1999.

[GR93] J. Gray und A. Reuter. Transaction Pro-

cessing: Concepts and Techniques. Morgan

Kaufmann Publishers, 1993.

[GT98] A. Geppert und D. Tombros. Event-Ba-

sed Distributed Workflow Execution with

EVE. In Proc. IFIP Int. Conf. on Distributed

Systems Platforms and Open Distributed Pro-

cessing, S. 427-442, Lake District, September

1998.

[HK96] M. Hsu und C. Kleissner. ObjectFlow:

Towards a Process Management Infrastruc-

ture. Distributed & Parallel Databases, 4:169-

194, 1996.

[HR99] T. Härder und E. Rahm. Datenbanksyste-

me: Konzepte und Techniken der Implemen-

tierung. Springer-Verlag, 1999.

[HRB+00] C. Hensinger, M. Reichert, T. Bauer,

T. Strzeletz und P. Dadam. ADEPTworkflow –

Advanced Workflow Technology for the Ef-

ficient Support of Adaptive, Enterprise-wide

Processes. In 7th Int. Conf. on Extending Da-

tabase Technology, Software Demonstrations

Track, S. 29-30, Konstanz, March 2000.

[HSS96] P. Heinl, H. Schuster und H. Stein. Be-

handlung von Ad-hoc-Workflows im MOBILE

Workflow-Modell. In Proc. Softwaretechnik

in Automation und Kommunikation – Rech-

nergestützte Teamarbeit, S. 229-242, Mün-

chen, März 1996.

[Jab97] S. Jablonski. Architektur von Workflow-

Mangement-Systemen. Informatik For-

schung und Entwicklung, Themenheft Work-

flow-Management, 12(2):72-81, 1997.

[JBS97] S. Jablonski, M. Böhm und W. Schulze.

Workflow-Management: Entwicklung von

Anwendungen und Systemen; Facetten einer

neuen Technologie. dpunkt-Verlag, 1997.

[JH98] G. Joeris und O. Herzog. Managing Evol-

ving Workflow Specifications. In Proc. 3rd IF-

CIS Conf. on Cooperative Information Sys-

tems, New York, August 1998.

[KAGM96] M. Kamath, G. Alonso, R. Günthör

und C. Mohan. Providing High Availability in

Very Large Workflow Management Systems.

In Proc. 5th Int. Conf. on Extending Database

Technology, S. 427-442, Avignon, März

1996.

[KG99] M. Kradolfer und A. Geppert. Dynamic

Workflow Schema Evolution Based on Work-

flow Type Versioning and Workflow Migrati-

on. In Proc. 4rd IFCIS Int. Conf. on Coope-

rative Information Systems, Edinburgh,

September 1999.

[KRW90] B. Karbe, N. Ramsperger und P. Weiss.

Support of Cooperative Work by Electronic

Circulation Folders. In Proc. Conf. on Office

Information Systems, S. 109-117, Cam-

bridge, MA, 1990.

[LP98] L. Liu und C. Pu. Methodical Restructu-

ring of Complex Workflow Activities. In Proc.

14th Int. Conf. on Data Engineering, S. 342-

350, Orlando, Florida, Februar 1998.

[LR00] F. Leymann und D. Roller. Production

Workflow – Concepts and Techniques. Pren-

tice Hall, 2000.

[MR00] R. Müller und E. Rahm. Dealing with

Logical Failures for Collaborating Work-

flows. In Proc. 5th Int. Conf. on Cooperative

Information Systems, S. 210-223, Eilat, Sep-

tember 2000.

[MWW+98] P. Muth, D. Wodtke, J. Weißenfels,

A. Kotz-Dittrich und G. Weikum. From Cen-

tralized Workflow Specification to Distribu-

ted Workflow Execution. Journal of Intelli-

gent Information Systems, Special Issue on

Workflow Management Systems, 10(2):159-

184, März/April 1998.

[Obe96] A. Oberweis. Modellierung und Ausfüh-

rung von Workflows mit Petri-Netzen. Teub-

ner-Verlag. 1996.

[RBD99] M. Reichert, T. Bauer und P. Dadam.

Enterprise-Wide and Cross-Enterprise Work-

flow-Management: Challenges and Research

Issues for Adaptive Workflows. In Proc.

Workshop Enterprise-wide and Cross-enter-

prise Workflow Management: Concepts, Sys-

tems, Applications, 29. Jahrestagung der GI,

S. 56-64, Paderborn, Oktober 1999.

[RBFD01] M. Reichert, T. Bauer, T. Fries und P.

Dadam. Realisierung flexibler, unterneh-

mensweiter Workflow-Anwendungen mit

ADEPT. In Proc. Arbeitskonferenz Elektroni-

sche Geschäftsprozesse, Klagenfurt, Septem-

ber 2001.

[RD98] M. Reichert und P. Dadam. ADEPTflex –

Supporting Dynamic Changes of Workflows

Without Losing Control. Journal of Intelligent

Information Systems, Special Issue on Work-

flow Management Systems, 10(2):93-129,

März/April 1998.

[RD00] M. Reichert und P. Dadam. Geschäfts-

prozessmodellierung und Workflow-Manage-

ment – Konzepte, Systeme und deren Anwen-

dung. Industrie Management (Themenheft

Modellierung und Simulation), 16(3):23-27,

Juni 2000.

[Rei00] M. Reichert. Dynamische Ablaufände-

rungen in Workflow-Management-Systemen.

Dissertation, Universität Ulm, Fakultät für

Informatik, Juli 2000.

[Sie98] R. Siebert. An Open Architecture for Ad-

aptive Workflow Management Systems. In

Proc. 3rd Biennial World Conf. on Integrated

Design and Process Technology, Vol. 2 – Is-

sues and Applications of Database Technolo-

gy, S. 79-85, Berlin, Juli 1998.

[SK97] A. Sheth und K.J. Kochut. Workflow Ap-

plications to Research Agenda: Scalable and

Dynamic Work Coordination and Collabora-

tion Systems. In Proc. NATO Advanced Study

Institute on Workflow Management Systems

and Interoperability, S. 12-21, Istanbul, Au-

gust 1997.

[SM96] A. Schill und C. Mittasch. Workflow Ma-

nagement Systems on Top of OSF DCE and

OMG CORBA. Distributed Systems Enginee-

ring, 3(4):250-262, Dezember 1996.

[SNS99] H. Schuster, J. Neeb und R. Schambur-

ger. A Configuration Management Approach

for Large Workflow Management Systems. In

Proc. Int. Joint Conf. on Work Activities

Coordination and Collaboration, San Francis-

co, February 1999.

[Wes98] M. Weske. Flexible Modeling and Exe-

cution of Workflow Activities. In Proc. 31st

Hawaii Int. Conf. on System Sciences, S.

713-722, Hawaii, 1998.

[Wes99] M. Weske. Workflow Management

Through Distributed and Persistent CORBA

Workflow Objects. In Proc. 11th Int. Conf. on

Advanced Information Systems Engineering,

Heidelberg, 1999.

[Zei99] J. Zeitler. Integration von Verteilungs-

konzepten in ein adaptives Workflow-Mana-

gement-System. Diplomarbeit, Universität

Ulm, Fakultät für Informatik, 1999.

Thomas Bauer, Manfred Reichert, Peter Dadam

Universität Ulm

Abt. Datenbanken und Informationssysteme

89069 Ulm

{bauer, reichert, dadam}@informatik.uni-ulm.de