Adaptives und verteiltes Workflow-Management
Thomas Bauer, Manfred Reichert, Peter Dadam
Universit¨at Ulm, Abteilung Datenbanken und Informationssysteme
f
bauer, reichert, dadam
g
@informatik.uni-ulm.de, http://www.informatik.uni-ulm.de/dbis
Zusammenfassung Die Unterst¨utzung unternehmensweiter und -¨ubergreifen-
der Gesch¨aftsprozesse stellt f¨urein Workflow-Management-System (WfMS)eine
besondere Herausforderung dar. So sind Skalierbarkeit bei hoher Last und die
M¨oglichkeit, zur Ausf¨uhrungszeit eines Workflows (WF)dynamisch vom vormo-
dellierten Ablauf abweichen zu k¨onnen, unbedingt erforderlich, damit ein WfMS
f¨ur ein breites Spektrum von Anwendungen eingesetzt werden kann. Allerdings
wurden diese beiden Aspekte in der WF-Literatur bisher weitestgehend getrennt
betrachtet. Dies ist ¨außerst problematisch, da mit ihnen entgegengesetzte Anfor-
derungen verbunden sind. So wird zur Erzielung einer guten Skalierbarkeit ange-
strebt, dass eine WF-Instanz von mehreren WF-Servern – m¨oglichst unabh¨angig
voneinander – kontrolliert werden kann, wohingegen f¨ur dynamische WF-¨
Ande-
rungen eine (logisch) zentrale Kontrollinstanz ben¨otigt wird, die den aktuellen
und globalen Zustand der WF-Instanz kennt. In diesem Beitrag werden Verfahren
vorgestellt, die es erlauben, dynamische ¨
Anderungen in einem verteilten WfMS
durchzuf¨uhren. Besonders bemerkenswert istdabei, dassesgelungen ist,die volle
aus dem zentralen Fall bekannte Funktionalit¨at zu realisieren, und trotzdem ein
bez¨uglich der Kommunikationskosten ¨außerst g¨unstiges Verhalten zu erreichen.
1 Einleitung
WfMS [JBS97, LR00, Obe96] erm¨oglichen die rechnerunterst¨utzte Ausf¨uhrung von
Gesch¨aftsprozessenineiner verteiltenSystemumgebung.DerentscheidendeVorteilsol-
cher Systeme ist, dass sie helfen, große vorgangsorientierteAnwendungssysteme ¨uber-
schaubarer zu gestalten. Dazu wird der applikationsspezifische Code der verwende-
ten Anwendungenvon der Ablauflogik des Gesch¨aftsprozesses getrennt.Anstelle eines
großen monolithischen Programmpakets erh¨alt man nun einzelne Aktivit¨aten, welche
die Anwendungsprogramme repr¨asentieren. Ihre Ablauflogik wird in einer separaten
Kontrollflussdefinition festgelegt, welche die Ausf¨uhrungsreihenfolge (Sequenz, Ver-
zweigung, Parallelit¨at, Schleifen) der einzelnen Aktivit¨aten bestimmt. Das WfMS sorgt
zurAusf¨uhrungszeitdaf¨ur,dass nursolcheAktivit¨ateneinerWF-Instanzbearbeitetwer-
den k¨onnen,die der Ablauflogik zufolge zur Ausf¨uhrunganstehen. Diese werden in die
Arbeitslisten autorisierter Bearbeiter eingef¨ugt. Welche Benutzer zur Bearbeitung einer
bestimmten Aktivit¨at autorisiert sind, wird meist durch eine Rolle festgelegt, die auch
den entsprechenden Bearbeitern zugeordnet ist.
Die Funktionalit¨at heutiger WfMS ist allerdings f¨ur viele der in der Praxis vorkommen-
den prozessorientierten Anwendungen nicht ausreichend. Ein Mangel ist insbesondere
Heuer, A.; Leymann, F.; Priebe, D. (Hrsg.): Proc. Datenbanksysteme in Büro, Technik und Wissenschaft,
Oldenburg, März 2001, Springer Verlag, 2001, S. 47-66
die unzureichende Skalierbarkeit bei hoher Last. Der Forderung nach Skalierbarkeit
kommen wir in ADEPT1dadurch nach, dass ein WfMS aus mehreren WF-Servern be-
steht. Um ein g¨unstiges Kommunikationsverhalten zu erzielen, kann eine WF-Instanz
abschnittsweise von verschiedenen WF-Servern kontrolliert werden [BD97, BD00].
Eine ebenfalls erkannte Schwachstelle existierender WfMS ist ihre unzureichende Ad-
aptivit¨at. In ADEPT ist es m¨oglich, eine laufende WF-Instanz bei Bedarf (z.B. in Aus-
nahmesituationen) dynamisch zu ver¨andern, so dass von dem vorgesehenen Ablauf ab-
gewichenwird. ImGegensatzzu vielenanderenAns¨atzen wirddabei dieKonsistenz der
WF-Instanz auch nach der ¨
Anderung garantiert, d.h. Laufzeitfehler (z.B. Verklemmun-
gen in Folge zyklischer Reihenfolgebeziehungen) sind ausgeschlossen [RD98,Rei00].
In den bisherigen Ver¨offentlichungen zu ADEPT haben wir, ebenso wie die anderen
uns bekannten Gruppen, verteilte WF-Ausf¨uhrung und Adaptivit¨at nur getrennt be-
trachtet. Das Zusammenspiel dieser beiden f¨ur ein WfMS essentiellen Aspekte wurde
dabei nichtsystematisch untersucht.Dies ist problematisch,weil mit den beidenAspek-
ten entgegengesetzte Anforderungen verbunden sind: Zur Durchf¨uhrung einer dynami-
schen ¨
Anderungwird eine zentrale Kontrollinstanz ben¨otigt[RD98]. Die Existenz einer
solchen konterkariertaber die durch verteilte WF-Ausf¨uhrung erzielten Errungenschaf-
ten, da eine zentrale Komponente die Verf¨ugbarkeit des WfMS verschlechtert und den
Kommunikationsaufwand erh¨oht. Ein Grund daf¨ur ist, dass eine solche Komponente
¨uber jede ¨
Anderung des Zustands jeder WF-Instanz informiert werden muss. Der Zu-
stand der zu modifizierenden WF-Instanz wird n¨amlich ben¨otigt, um entscheiden zu
k¨onnen, ob eine geplante ¨
Anderung ¨uberhaupt durchf¨uhrbarist [RD98].
Das Ziel des vorliegenden Beitrags ist es, dynamische ¨
Anderungen in einem verteil-
ten WfMS zu erm¨oglichen. Dabei soll die Adaptivit¨at gegen¨uber der zentralen WF-
Ausf¨uhrung nicht eingeschr¨ankt sein, d.h. jede f¨ur den zentralen Fall erlaubte dynami-
sche ¨
Anderung muss im verteilten Fall weiterhin zul¨assig sein. Die Unterst¨utzung sol-
cher dynamischer Abweichungen darf die Effizienz der verteilten WF-Steuerung aber
keinesfalls beeintr¨achtigen. Insbesonderesoll bei der ”normalen“ WF-Ausf¨uhrung kein
großer zus¨atzlicher Kommunikationsaufwand notwendig werden. Außerdem sollen in
dem angestrebten System (verteilte) dynamische ¨
Anderungen auf m¨oglichst effiziente
Art und Weise durchgef¨uhrt werden k¨onnen.
Zur Behandlung dieser Anforderungen ist zu untersuchen (siehe auch [RBD99]), mit
welchen Servern des WfMS eine dynamische ¨
Anderung synchronisiert werden muss.
Vermutlich m¨ussen dabei zumindest die aktuell an der WF-Instanz beteiligten Server
einbezogen werden, da sie die resultierende Struktur und den Zustand der WF-Instanz
(den sog. Ausf¨uhrungsgraphen) ben¨otigen, um diese korrekt steuern zu k¨onnen. Des-
halb wird ein Verfahren ben¨otigt, mit dem die Menge dieser Server ohne großen Auf-
wand ermittelt werden kann. Außerdem ist zu kl¨aren, wie diesen und anderen Servern
der durch die ¨
Anderung resultierende Ausf¨uhrungsgraph der WF-Instanz ¨ubermittelt
werden kann. Dabei ist essentiell, dass kein inakzeptabel großer Kommunikationsauf-
wand verursacht wird.
1ADEPT steht f¨ur Application Development Based on Encapsulated Pre-Modeled Process
Templates.
Im nachfolgenden Abschnitt wird auf Grundlagen der verteilten WF-Ausf¨uhrung und
der dynamischen ¨
Anderungen in ADEPT eingegangen, die f¨ur das weitere Verst¨andnis
notwendig sind. Der Abschnitt 3 besch¨aftigt sich mit der Durchf¨uhrung von dynami-
schen ¨
Anderungen in einem verteilten WfMS. In Abschnitt 4 wird dann erl¨autert, wie
auch zuvor ver¨anderte WF-Instanzen effizient gesteuert werden k¨onnen. Eine Einord-
nung der beschriebenen Verfahren in die WF-Literatur findet sich in Abschnitt 5. Der
Beitrag schließt mit einer Zusammenfassung und einem Ausblick auf zuk¨unftige Ar-
beiten.
2 Grundlagen
Im ADEPT-Projekt [DKR
+
95,DRK00,RD98] betrachten wir Anforderungen, die sich
bei der Unterst¨utzung unternehmensweiter und -¨ubergreifender WF-basierter Anwen-
dungen ergeben. Im vorliegenden Abschnitt fassen wir die hieraus hervorgegangenen
Konzepte zur verteilten WF-Steuerung und zu dynamischen WF- ¨
Anderungen kurz zu-
sammen.
2.1 Verteilte Workflow-Ausf¨uhrung in ADEPT
Aufgrund der großen Anzahl von Benutzern und gleichzeitig aktiven WF-Instanzen
resultiert in unternehmensweiten Anwendungen eine sehr hohe Last.2Diese kann
dazu f¨uhren, dass Komponenten des WfMS ¨uberlastet werden. Deshalb wird in
ADEPT
distr ibution
, der verteilten Variante von ADEPT, eine WF-Instanz nicht nur
von einem einzigen WF-Server kontrolliert, sondern sie wird ggf. partitioniert und ab-
schnittsweise von verschiedenen Servern gesteuert [BD97] (vgl. Abb. 1). Wird bei der
Ausf¨uhrung von Instanzen dieses WF-Typs das Ende einer Partition erreicht, so wird
die Kontrolle ¨uber diesen WF an den n¨achsten WF-Server weitergereicht (Migration).
Damit dies m¨oglich ist, muss eine Beschreibung des Zustands der WF-Instanz zu die-
sem Server transportiert werden.3Um unn¨otigen Kommunikationsaufwand zwischen
WF-Servernzu vermeiden,erfolgtinADEPT dieSteuerungvonparallelenZweigenun-
abh¨angig voneinander (wenn zur Zeit keine dynamische ¨
Anderung durchgef¨uhrt wird).
Im Beispiel aus Abb. 1 weiß der WF-Server
s
3
, der gerade die Aktivit¨at
e
kontrolliert,
nicht, wie weit die Bearbeitung im oberen Zweig der Parallelit¨at fortgeschritten ist.
Dies hat den Vorteil, dass keine Synchronisation zwischen WF-Servern notwendig ist,
die Aktivit¨aten paralleler Zweige steuern.
Die Partitionierung von WF-Graphen und die verteilte WF-Steuerung werden auch in
anderen Ans¨atzen verwendet (z.B. [CGP
+
96,MWW
+
98]). Wir verfolgen in ADEPT
zus¨atzlich das Ziel, die Kommunikationskosten zu minimieren. Konkrete Erfahrungen
mit existierenden WfMS haben gezeigt, dass zwischen dem WF-Server und seinen
2In [KAGM96,SK97] werden Anwendungen beschrieben, bei denen die Zahl der Benutzer des
WfMS bis auf einige zehntausend anwachsen kann oder mehrere zehntausend WF-Instanzen
gleichzeitig im System sein k¨onnen.
3Die WF-Vorlagen werden in ADEPT repliziert bei allen (relevanten) WF-Servern gespeichert.
Partition 1
Partition 2
Partition 3
a
bc
de
f
norm aler Kontrollfluss
Kontrollfluss und M igration
v o n A k tiv itä t x n a c h y
s
3
s
3
s
3
s
2
s
2
s
1
Mx,y
Mc,f
Ma,b
Ma,d
A N D -S p lit AND-Join
Abbildung1. Partitionierung eines WF-Graphen und verteilte WF-Ausf¨uhrung.
Clients sehr viel kommuniziert wird und zum Teil auch große Datenmengen ausge-
tauscht werden m¨ussen. Dies kann dazu f¨uhren,dass das Kommunikationssystem ¨uber-
lastet wird. Deshalb werden in ADEPT die WF-Server der Aktivit¨aten so festgelegt,
dass der Gesamtkommunikationsaufwand minimiert wird. Dazu wird der WF-Server
f¨ur eine Aktivit¨at in der Regel so gew¨ahlt, dass er im Teilnetz der Mehrzahl ihrer poten-
tiellen Bearbeiter liegt. Dadurch wird in vielen F¨allen eine teilnetz¨ubergreifendeKom-
munikationzwischendem WF-Serverund seinenClients vermieden.Außerdemwerden
die Antwortzeiten verbessert und die Verf¨ugbarkeit erh¨oht, da bei der Ausf¨uhrung von
Aktivit¨aten kein Gateway oder WAN (Wide Area Network) zwischengeschaltet ist.
Bei diesem Ansatz wird also bereits zur Modellierungszeit eine (statische) Zuordnung
von WF-Servern zu den Aktivit¨aten vorgenommen. Es gibt aber auch F¨alle, in denen
diese Vorgehensweise nicht ausreichend ist, um gute Resultate zu erzielen. Dies ist
der Fall, wenn bei der WF-Definition abh¨
angige Bearbeiterzuordnungen (z.B. "selber
Bearbeiter wie Aktivit¨at
n
") verwendet werden. Hier h¨angen die potentiellen Bear-
beiter einer Aktivit¨at vom Bearbeiter einer Vorg¨angeraktivit¨at ab. Da sich die Menge
der potentiellen Bearbeiter einer solchen Aktivit¨at erst im Verlauf der WF-Ausf¨uhrung
ergibt, ist es vorteilhaft, ihren WF-Server ebenfalls erst zur Ausf¨uhrungszeit festzu-
legen. Der Server kann dann in einem f¨ur die entsprechenden Bearbeiter g¨unstigen
Teilnetz gew¨ahlt werden. Zu diesem Zweck wurde f¨ur ADEPT
distr ibution
das Kon-
zept der variablen Serverzuordnungen [BD99a,BD00] entwickelt. Hierbei handelt es
sich um Ausdr¨ucke (z.B. "Server im Teilnetz des Bearbeiters der Aktivit¨at
n
"), die
zur Ausf¨uhrungszeitder WF-Instanz ausgewertet werden. Dadurch wird derjenige WF-
Server ermittelt, der die zugeh¨orige Aktivit¨ateninstanz kontrollieren soll.
2.2 Dynamische ¨
Anderungen
Um auf Ausnahmesituationen flexibel reagieren zu k¨onnen, muss der Ausf¨uhrungs-
graph einer WF-Instanz zur Ausf¨uhrungszeit modifiziert werden k¨onnen. Das
ADEPT
flex
-Kalk¨ulbietet z.B. die M¨oglichkeit,Aktivit¨atendynamischeinzuf¨ugenoder
zu l¨oschen. Dabei sind auch sehr komplexe Operationen realisierbar, wie das Einf¨ugen
einer Aktivit¨at, die erst nach der Beendigung einer beliebigen Menge von Aktivit¨aten
ausf¨uhrbar sein soll und vor dem Starten einer anderen Menge von Aktivit¨aten beendet
sein muss. Auf die Verfahren zur Durchf¨uhrungsolcher dynamischen ¨
Anderungenwird
hier nicht n¨aher eingegangen, da dies f¨ur das weitere Verst¨andnis dieses Beitrags nicht
notwendig ist (f¨ur Details siehe [RD98,Rei00]).
Das WfMS bestimmt aus der Spezifikation einer ¨
Anderung automatisch eine
Menge von Basisoperationen (z.B. Aktivit¨at einf¨ugen, Kante einf¨ugen), die auf
den Ausf¨uhrungsgraphen der entsprechenden WF-Instanz angewandt werden. Wie in
Abb. 2c dargestellt,werden diese Basisoperationenzusammen mit der Spezifikationder
¨
Anderung in einer ¨
Anderungshistorie vermerkt. Diese wird ben¨otigt, um im Falle des
partiellen Zur¨ucksetzens einer WF-Instanz ggf. auch tempor¨are ¨
Anderungsoperationen
r¨uckg¨angig machen zu k¨onnen (vgl. [DRK00]). Außerdem wird die dynamische ¨
Ande-
rung in der Ablaufhistorie der WF-Instanz vermerkt (Eintrag DynModif(1) in Abb. 2b
f¨ur die ¨
Anderung 1), in welcher ansonsten f¨ur die WF-Ausf¨uhrung ben¨otigte Informa-
tionen, wie die Start- und Endezeitpunkte und die Bearbeiter der Aktivit¨aten, abgelegt
werden.
b
a)
b)
a b c
c)
1 . In s e rtA c tiv ity x A fte r {a } B e fo re {c }:
_C hangeN odeType(a, AN D -Split), _C hangeN odeType(c, AN D -Join),
_InsertN ode(x), _InsertC ontrolEdge(a,x), _InsertC ontrolEdge(x,c)
axc
S ta rt(a , ...), E n d (a , ...), D y n M o d if(1 )
S ta rt(a , ...), E n d (a , ...)
A k tiv itä t x z w is c h e n
a und c einfügen
Æ
A N D -S p lit A N D -J o in
a)
b)
c)
Abbildung2. Beispiel f¨ur eine dynamische ¨
Anderung mit a) Ausf¨uhrungsgraph, b) Ablaufhisto-
rie und c) ¨
Anderungshistorie (vereinfacht dargestellt).
Um eine robuste WF-Ausf¨uhrung zu erm¨oglichen, muss die Konsistenz eines WF-
Ausf¨uhrungsgraphenjederzeit garantiert werdenk¨onnen.Prinzipiell k¨onnenaber durch
eine dynamische Modifikation Inkonsistenzenentstehen. So k¨onnen durch das L¨oschen
einer Aktivit¨at evtl. EingabedatennachfolgenderAktivit¨aten nicht mehr sicher versorgt
sein, oder nach dem Einf¨ugen einer Kante k¨onnen Verklemmungen durch zyklische
Kontrollflussreihenfolgen entstehen. Solche F¨alle sind in ADEPT
f lex
ausgeschlossen,
weil das WfMS vor der Durchf¨uhrung einer ¨
Anderung stets pr¨uft, ob der resultie-
rende Ausf¨uhrungsgraph wieder eine fehlerfreie WF-Ausf¨uhrung garantiert. Zu die-
sem Zweck wird analysiert, ob die ¨
Anderung aufgrund des aktuellen Zustands und der
Struktur der WF-Instanz zul¨assig ist, d.h., ob die f¨ur die entsprechenden Basisoperatio-
nen(formal)definiertenVor-und Nachbedingungenerf¨ulltsind. Nurwenndies gegeben
ist, wird die Struktur und der Zustand des Ausf¨uhrungsgraphenentsprechendver¨andert.
3 Dynamische ¨
Anderungen in verteilten WfMS
Prinzipiell laufen dynamische ¨
Anderungenin einem verteilten WfMS ebenso ab, wie in
einem zentralen System: Anhand der Struktur und des Zustands der WF-Instanz wird
¨uberpr¨uft, ob die gew¨unschte ¨
Anderungzul¨assig ist oder nicht. Falls dem so ist, werden
die zugeh¨origen Basisoperationen ermittelt und der Ausf¨uhrungsgraph der WF-Instanz
wird entsprechend modifiziert. F¨ur die ¨
Uberpr¨ufung der Zul¨assigkeit einer ¨
Anderung
wird der globale, aktuelle Zustand der WF-Instanz ben¨otigt. Um diesen Zustand zu
ermitteln, muss im Allgemeinen Zustandsinformation von anderen Servern eingeholt
werden (wie die ¨
Ubertragung eines Zustandes effizient m¨oglich ist, wird in [BRD00]
beschrieben). Im vorliegenden Abschnitt wird ein Verfahren vorgestellt, mit dem die
Menge der WF-Server bestimmt werden kann, von denen entsprechende Zustandsin-
formation ben¨otigt wird. Im Gegensatz zum zentralen Fall reicht es in einem verteil-
ten WfMS in der Regel nicht aus, den Ausf¨uhrungsgraphen der WF-Instanz nur auf
demjenigen Server zu modifizieren, der die ¨
Anderung steuert. Deshalb wird in diesem
Abschnitt gekl¨art, bei welchen Servern eine ¨
Anderung eingebracht werden soll.
3.1 Synchronisation von Workflow-Servern bei dynamischen ¨
Anderungen
Eine dynamische ¨
Anderung kann von einem beliebigen Server, der die betroffene WF-
Instanz gerade kontrolliert, initiiert werden. Dieser WF-Server kann die ¨
Anderung im
Allgemeinen aber nicht alleine durchf¨uhren, sondern er muss f¨ur den Fall, dass aktu-
ell mehrere Server an der WF-Kontrolle beteiligt sind, ggf. Zustandsinformation von
diesen einholen. Des weiteren muss er veranlassen, dass die ¨
Anderung auch in die
von anderen Servern verwalteten Ausf¨uhrungsgraphen dieser WF-Instanz eingebracht
wird. Als naive L¨osung k¨onnten alle Server des WfMS in eine ¨
Anderung mit einbe-
zogen werden, indem entsprechende Aufrufe per Broadcast verbreitet werden. Dieser
Ansatz scheidet aber aus, weil er in den meisten F¨allen zu einem unn¨otig hohen Auf-
wand f¨uhren w¨urde, und außerdem eine dynamische ¨
Anderung nur dann durchgef¨uhrt
werden k¨onnte, wenn alle Serverrechner des WfMS erreichbar sind. Deshalb werden
im Folgenden alternative Vorgehensweisen untersucht.
Ansatz 1: Einbeziehung aller Server der betroffenen Workflow-Instanz
Bei diesem Ansatz werden nur diejenigen WF-Server bei der ¨
Anderung ber¨ucksichtigt,
die bisher an der WF-Steuerung beteiligt waren bzw. es aktuell sind, oder die zuk¨unftig
in die Steuerung der WF-Instanz involviert sein werden. Dadurch wird der Kommu-
nikationsaufwand gegen¨uber der oben erw¨ahnten naiven L¨osung zwar merklich redu-
ziert, er ist aber immer noch unn¨otig groß. Diejenigen Server, welche die WF-Instanz
ausschließlich in der Vergangenheit kontrolliert haben, m¨ussen n¨amlich nicht in die
¨
Anderung einbezogen werden. Mit diesen Servern ist keine Synchronisation notwen-
dig und die von ihnen verwaltete Zustandsinformationwurde schon durch Migrationen
weitergegeben.
Ansatz 2: Einbeziehung der aktuellen und zuk¨unftigen Server der Workflow-
Instanz
Um eine WF-Instanz steuern zu k¨onnen, m¨ussen dem entsprechenden WF-Server alle
bisher erfolgten dynamischen ¨
Anderungenbekannt sein. Deshalb ist eine ¨
Anderungf¨ur
alle WF-Server relevant, welche die WF-Instanz aktuell kontrollieren oder zuk¨unftig
kontrollieren werden. Darum scheint es naheliegend zu sein, diese in die ¨
Anderungs-
operation einzubeziehen. Sollen aber die zuk¨unftigen Server ber¨ucksichtigt werden, so
entsteht im Kontext von variablen Serverzuordnungen(vgl. Abschnitt 2.1) ein Problem.
Es kann n¨amlich im Allgemeinen nicht ermittelt werden,welche Server die WF-Instanz
zuk¨unftig steuern werden, da die zur Auswertung der Serverzuordnungsausdr¨uckenot-
wendigen Laufzeitdaten der WF-Instanz evtl. noch nicht existieren. So kann in Abb. 3
bei der Ausf¨uhrung der Aktivit¨at
g
der Server der Aktivit¨at
j
nicht ermittelt werden, da
derBearbeiter derAktivit¨at
i
nochnichtfeststeht. Eine Synchronisationmit zuk¨unftigen
Servern der WF-Instanz ist also nicht m¨oglich. Diese Server m¨ussen auch noch nicht
¨uber die ¨
Anderunginformiert 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 dem-
nach die einzigakzeptable L¨osung.Es ist aber keineswegs trivial, diese Server zu ermit-
teln, weil der Ausf¨uhrungszustand von parallel ausgef¨uhrten Aktivit¨aten bei verteilter
WF-Steuerung nicht bekannt sein muss. So weiß z.B. in Abb. 3 der Server
s
4
, der die
Aktivit¨at
g
kontrolliert, nicht, ob die Migration
M
c;d
schon ausgef¨uhrt worden ist, und
damit, ob der parallele Zweig vom Server
s
2
oder
s
3
kontrolliert wird. Außerdem ist es
nicht ohne weiteres m¨oglich, den f¨ur einen parallelen Zweig zust¨andigen Server zu er-
mitteln, wenn variable Serverzuordnungenverwendetwerden. So referenziert in Abb. 3
die Serverzuordnungder Aktivit¨at
e
den Bearbeiter der Aktivit¨at
c
. Dieser ist aber dem
Server
s
4
nicht bekannt.
a
g
b
i j
s1
s4
s5
s1
Teilnetz(
Bearb(i))
d
s3
e
h
s4
Teilnetz(
Bearb(c))
c
s2
f
s1
x
Abbildung3. Einf¨ugen der Aktivit¨at
x
durch den Server
s
4
zwischen den Aktivit¨aten
g
und
d
.
3.2 Bestimmung der aktuellen Server einer Workflow-Instanz
Wie soeben erl¨autert, ist es einem WF-Server nicht m¨oglich, die anderen aktuell an
einer WF-Instanz beteiligten Server aus der lokal vorhandenen Zustandsinformation
zu ermitteln. Diese durch einen Broadcast-Aufruf zu ”suchen“, verbietet sich, da dann
dieselben Nachteile wie bei der eingangs des vorangehenden Abschnitts skizzierten
naiven L¨osung entstehen. Deshalb muss ein Verfahren entwickelt werden, bei dem die
Menge der an der Ausf¨uhrung einer WF-Instanz aktuell beteiligten Server explizit ver-
waltet wird. Diese Verwaltungsollte aber nichtdurch einen festen(und damit zentralen)
Server erfolgen, da dieser die Verf¨ugbarkeit des gesamten WfMS beeintr¨achtigen und
einen potentiellen Flaschenhals darstellen w¨urde. Deshalb wird diese Menge Active-
Servers in ADEPT von einem WF-instanzspezifischen ServerManager verwaltet. Als
ServerManager wird normalerweise jeweils derjenige Server verwendet, auf dem die
entsprechendeWF-Instanz gestartet wurde.4Dieser kann von jedem an der WF-Instanz
beteiligten Server mit Hilfe der (lokal vorhandenen) Ablaufhistorie ermittelt werden
und variiert f¨ur verschiedene WF-Instanzen (auch desselben Typs). Deshalb stellt er
keinen Flaschenhals dar. Im nun folgenden Abschnitt wird beschrieben, wie die Menge
der aktuell f¨ur eine WF-Instanz aktiven Server vom ServerManager verwaltet wird. In
Abschnitt 3.2.2 wird dann erl¨autert, wie diese Menge bei dynamischen ¨
Anderungen
ermittelt und verwendet wird.
3.2.1 Verwaltung der aktuell an einer Workflow-Instanz beteiligten Server
Um die Menge der an der Ausf¨uhrung einer WF-Instanz aktuell beteiligten Server ver-
waltenzu k¨onnen,wirdein Verfahrenben¨otigt,welches dieaus einer Migrationresultie-
rende Ver¨anderung der Menge ActiveServers an den jeweiligen ServerManager meldet
(siehe Algorithmus 1). Dieser ServerManager verwendet wiederum ein Verfahren, mit
dem diese Menge manipuliert wird (Algorithmus 2). Bei der Realisierung dieser bei-
den Verfahren muss beachtet werden, dass nicht mehrere Migrationen derselben WF-
Instanz beliebig ¨uberlappenddurchgef¨uhrtwerden d¨urfen, da ansonsten Inkonsistenzen
bei der Ver¨anderung der Menge der aktuellen Server entstehen k¨onnen. Außerdem darf
sich die Menge ActiveServers w¨ahrendder Durchf¨uhrungeiner dynamischenModifika-
tion nicht durchMigrationen ver¨andern,um in eine dynamische ¨
Anderungdie richtigen
Server einbeziehen zu k¨onnen. Dies wird verhindert, indem von den beiden genannten
Verfahren und von dem im Abschnitt 3.2.2 vorgestellten Verfahren zur Durchf¨uhrung
von dynamischen ¨
Anderungen verschiedene Sperren verwendet werden, deren Zusam-
menspiel im Folgenden erl¨autert wird.
Der Algorithmus 1 zeigt den Ablauf einer Migration. Zuerst fordert der Migrations-
quellserver beim ServerManager eine nicht exklusive Sperre an.5Dann wird eine ex-
klusiveKurzzeitsperreangefordert,6durch diesichergestellt wird,dass die Ver¨anderung
derServermengef¨ureine gegebeneWF-Instanznichtgleichzeitigf¨urmehrereMigratio-
nen paralleler Zweige vorgenommenwird. Die bei einer Migration resultierende ¨
Ande-
rung der Servermenge wird vom Quellserver an den ServerManager gemeldet. Dabei
wirdangegeben,obderQuellserverder MigrationweiterhinanderentsprechendenWF-
4Es kann Szenarien geben, bei denen sich durch diese Strategie stets derselbe Server ergibt, weil
alle WF-Instanzen auf demselben WF-Server instanziiertwerden (z.B. dem Server, der in einer
Bank f¨ur die Terminals der Schalter zust¨andig ist). In einem solchen Fall sollte beim Erzeugen
einer WF-Instanz z.B. ein zuf¨allig ausgew¨ahlter Server als ServerManager festgelegt werden.
5Die Sperre verhindert nicht, dass mehrere Migrationen derselben WF-Instanz gleichzeitig
durchgef¨uhrt werden. Ihr Zweck wird im Zusammenhang mit Algorithmus 3 klar.
6Die beiden Sperranforderungen k¨onnen auch zu einem einzigen Aufruf zusammengefasst wer-
den, um so einen Kommunikationszyklus einzusparen.
Instanzbeteiligt ist (Stay) odernicht(LogOff).Findet indemBeispiel aus Abb.3 dieMi-
gration
M
b;c
vor
M
f;g
statt, so wird bei
M
b;c
die Option Stay verwendet, da der Server
s
1
diese WF-Instanz weiterhin kontrolliert. Dementsprechend erfolgt die sp¨ater statt-
findende Migration
M
f;g
mit der Option LogOff, weil hiermit der letzte vom Server
s
1
kontrollierte Zweig beendet wird. Dass die beiden Migrationen gleichzeitig ausgef¨uhrt
werden, ist wegen der zuvor gew¨ahrten (exklusiven) Kurzzeitsperre ausgeschlossen.
Deshalb ist stets klar, ob ein WF-Server nach Beendigung einer Migration noch an
der WF-Instanz beteiligt ist oder nicht. Als n¨achstes werden die WF-Instanzdaten zum
Migrationszielserver ¨ubertragen. Da zu diesem Zeitpunkt die exklusive Kurzzeitsperre
schon freigegeben wurde (durch MigrateWorkflowInstance), k¨onnen weiterhin mehrere
Migrationen derselben WF-Instanz gleichzeitig durchgef¨uhrtwerden. Der Algorithmus
endet damit, dass auch die nicht exklusive Sperre wieder freigegeben wird.
Algorithmus 1 (Durchf¨uhrung einer Migration)
input
Inst: ID der zu migrierenden WF-Instanz
SourceServer: Quellserver der Migration (f¨uhrt diesen Algorithmus aus)
TargetServer: Zielserver der Migration
begin
// Verwaltungsserver f¨ur die WF-Instanz aus Ablaufhistorie ermitteln
ServerManager = StartServer(Inst);
// nicht exklusive Sperre und exklusive Kurzzeitsperre beim ServerManager anfordern7
RequestSharedLock(Inst)
!
ServerManager;
RequestShortTermLock(Inst)
!
ServerManager;
// Menge der aktuellen Server ¨andern (UpdateActiveServers, siehe Algorithmus 2)
if LastBranch(Inst) then
// die Migration erfolgt im letzten beim SourceServer aktiven Ausf¨uhrungszweig der
// WF-Instanz
UpdateActiveServers(Inst, SourceServer, LogOff, TargetServer)
!
ServerManager;
else // ein weiterer Ausf¨uhrungszweig ist bei SourceServer aktiv
UpdateActiveServers(Inst, SourceServer, Stay, TargetServer)
!
ServerManager;
// eigentliche Migration durchf¨uhren und nicht exklusive Sperre freigeben
MigrateWorkflowInstance(Inst)
!
TargetServer;
ReleaseSharedLock(Inst)
!
ServerManager;
end.
Der Algorithmus 2 wird vom ServerManager verwendet, um die aktuell an einer be-
stimmten WF-Instanz beteiligten Server zu verwalten. Um diese Aufgabe erf¨ullen zu
k¨onnen,muss derServerManagerzus¨atzlich die erw¨ahntenSperrenverwalten.Wird die
Funktion UpdateActiveServers mit der Option LogOff aufgerufen, so wird der Migra-
tionsquellserver aus der Menge ActiveServers(Inst) der aktuellen WF-Server entfernt,
weil dieser Server dann nicht mehr an der WF-Instanz beteiligt ist. Der Migrations-
zielserver wird stets in diese Menge aufgenommen, unabh¨angig davon, ob er schon
7p()
!
s
bedeutet, dass die Prozedur paufgerufen wird, die dann vom Server
s
ausgef¨uhrt
wird.
enthalten ist oder nicht, da die entsprechende Operation idempotent ist. Durch die vom
Algorithmus 1 vor dem Aufruf von UpdateActiveServers angeforderte Kurzzeitsperre
wird schließlich verhindert, dass der Algorithmus 2 f¨ur eine WF-Instanz mehrfach par-
allel durchlaufen wird, so dass Fehler durch das ¨uberlappende Ver¨andern der Menge
ActiveServers(Inst) ausgeschlossen sind. Nach der Anpassung dieser Menge wird die
erw¨ahnte Kurzzeitsperre wieder freigegeben.
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¨ur die WF-Instanz Inst aktiven WF-Server aktualisieren
if Option = LogOff then
ActiveServers(Inst) = ActiveServers(Inst)
f
SourceServer
g
;
ActiveServers(Inst) = ActiveServers(Inst)
[f
TargetServer
g
;
// die Kurzzeitsperre wieder freigeben
ReleaseShortTermLock(Inst);
end.
3.2.2 Durchf¨uhrung dynamischer ¨
Anderungen
Im vorherigenAbschnitt wurde beschrieben,wie der ServerManager die Mengeder ak-
tuell an einer WF-Instanz beteiligtenServer verwaltet. ImFolgendenwird erl¨autert, wie
diese Menge bei der Durchf¨uhrung einer dynamischen ¨
Anderung verwendet wird. Zu
diesemZweck fordertsie derjenigeWF-Server,dereine ¨
Anderungdurchf¨uhrenm¨ochte,
beim ServerManager an.
Wichtig ist, dass sich w¨ahrend der Durchf¨uhrung einer dynamischen ¨
Anderung die
Menge der an der betroffenen WF-Instanz beteiligten Server nicht durch Migratio-
nen ver¨andert, weil sonst evtl. die falschen Server in die ¨
Anderung einbezogen wer-
den w¨urden. Außerdem darf der Ausf¨uhrungsgrapheiner WF-Instanz nicht gleichzeitig
durch mehrere ¨
Anderungenumstrukturiert werden, da dies zu einem unzul¨assigen Gra-
phen f¨uhren k¨onnte. Um beides zu verhindern, fordert der Algorithmus 3 beim Server-
Manager eine exklusive Sperre an. Diese entspricht einer Schreibsperre [GR93,HR99]
in einem Datenbanksystem und ist mit Lesesperren (RequestSharedLock aus Algorith-
mus 1) und weiteren Schreibsperrenderselben WF-Instanz unvertr¨aglich.Dadurch wird
verhindert, dass f¨ur eine zu ¨andernde WF-Instanz zeitgleich Migrationen stattfinden.
Nach Gew¨ahrung der Sperre wird die Menge der f¨ur diese WF-Instanz aktiven Server
erfragt.8Bei allen Servern der Menge ActiveServers wird nun eine Sperre angefordert,
8Dies kann auch mit dem Anfordern der Sperre zu einem einzigen Aufruf zusammengefasst
werden, um so einen Kommunikationszyklus einzusparen.
die lokale Ver¨anderungen des Zustands der WF-Instanz verhindert. Bereits gestartete
Aktivit¨aten k¨onnen aber weiterhin beendet werden, da die entsprechenden Zust¨ande im
ADEPT
flex
-Modell ¨aquivalent sind. Dann wird die (gesperrte) Zustandsinformation
bei allen an der WF-Instanz beteiligten Servern eingeholt. Der hierdurch resultierende
globale und aktuelle Zustand einer WF-Instanz wird ben¨otigt, um pr¨ufen zu k¨onnen,
ob eine bestimmte ¨
Anderung zul¨assig ist oder nicht. So ist in dem Beispiel aus Abb. 3
dem Server
s
4
, der gerade die Aktivit¨at
g
kontrolliert und eine Aktivit¨at
x
nach der
Aktivit¨at
g
und vor
d
einf¨ugen will, der aktuelle Zustand der Aktivit¨at
d
des parallelen
Zweiges nicht bekannt. Die dynamische ¨
Anderung ist aber nur dann zul¨assig, wenn die
Aktivit¨at
d
zumZeitpunktder ¨
Anderungnoch nicht gestartet wurde[RD98]. Ist dies der
Fall, so wird sie bei allen an der WF-Instanz beteiligten Servern durchgef¨uhrt(Perform-
DynamicModification). Anschließend werden die Sperren wieder freigegeben, worauf-
hin blockierte Migrationen und ¨
Anderungsoperationendurchgef¨uhrt werden k¨onnen.
Algorithmus 3 (Durchf¨uhrung einer dynamischen ¨
Anderung)
input
Inst: ID der zu ¨andernden WF-Instanz
Modification: Spezifikation der dynamischen ¨
Anderung
begin
// Verwaltungsserver f¨ur 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. ¨
Anderung
// durchf¨uhren
for each Server
s
2
ActiveServers do
RequestStateLock(Inst)
!
s
;
GlobalState = GetLocalState(Inst);
for each Server
s
2
ActiveServers do
LocalState = GetLocalState(Inst)
!
s
;
GlobalState = GlobalState
[
LocalState;
if DynamicModificationPossible(Inst, GlobalState, Modification) then
for each Server
s
2
ActiveServers do
PerformDynamicModification(Inst, GlobalState, Modification)
!
s
;
// alle Sperren wieder freigeben
for each Server
s
2
ActiveServers do
ReleaseStateLock(Inst)
!
s
;
ReleaseExclusivLock(Inst)
!
ServerManager;
end.
4 Verteilte Ausf¨uhrung ver¨
anderter Workflow-Instanzen
Bei einer Migration muss der aktuelle Zustand der betroffenen WF-Instanz ¨ubermittelt
werden. Dies geschieht in ADEPT
distr ibution
, indem die Ablaufhistorie (partiell) ¨uber-
tragen wird [BRD00]. Außerdem werden die Werte von WF-relevanten Daten transfe-
riert. Im Falle von dynamischen ¨
Anderungen muss der Migrationszielserver zus¨atzlich
den ver¨anderten Graphen der WF-Instanz kennen, damit er diese korrekt steuern kann.
Bei dem im vorherigenAbschnitt vorgestellten Verfahren werden nur die aktuell an der
zuver¨anderndenWF-Instanz beteiligtenServerin die ¨
Anderungeinbezogen.DieServer
nachfolgenderAktivit¨atenm¨ussendagegenggf.noch ¨uberdie erfolgten ¨
Anderungenin-
formiert werden. Die hierzu erforderliche Informations¨ubermittlung findet jeweils bei
den Migrationen der WF-Instanz zu diesen Servern statt. Da Migrationen recht h¨aufige
Operationen sind, muss die ¨
Ubertragung der entsprechenden Information auf eine ef-
fiziente Art und Weise erfolgen. Im Abschnitt 4.1 wird ein Verfahren vorgestellt, das
diese Bedingung schon recht gut erf¨ullt. Dieses wird in Abschnitt 4.2 noch optimiert,
so dass redundante Daten¨ubertragungenv¨ollig ausgeschlossen sind.
4.1 Effiziente ¨
Ubermittlung von dynamischen ¨
Anderungen
Im Folgenden wird untersucht, wie ein ver¨anderter WF-Ausf¨uhrungsgraph dem Ziel-
server einer Migration bekannt gemacht werden kann. Dabei wird angestrebt, ein
bez¨uglich der Kommunikationskosten m¨oglichst effizientes Verfahren zu erhalten.
Die einfachste M¨oglichkeit, um dem Migrationszielserver den aktuellen Ausf¨uhrungs-
graphen bekannt zu machen, ist nat¨urlich, diesen vollst¨andig zu ¨ubertragen. Allerdings
resultiert aus dieser Vorgehensweise eine unn¨otig hohe Belastung f¨ur das Kommuni-
kationssystem, da diese Graphen viele Knoten und Kanten umfassen k¨onnen, weshalb
ihre Beschreibung sehr groß sein kann. Aus diesem Grund scheidet dieser ineffiziente
Ansatz aus.
Es ist auch nicht notwendig, den gesamten Ausf¨uhrungsgraphen an den Zielserver
einer Migration zu ¨ubertragen, da dieser Server die zugeh¨orige WF-Vorlage schon
kennt. Diese stimmt weitestgehend mit dem aktuellen Ausf¨uhrungsgraphen der WF-
Instanz ¨uberein, so dass es wesentlich effizienter ist, lediglich die verh¨altnism¨aßig
kleine Beschreibung der angewandten ¨
Anderungsoperation(en)zu ¨ubertragen. Die Ver-
wendung der ¨
Anderungshistorie bietet eine gute M¨oglichkeit, um diese Idee umzu-
setzen. Diese Historie wird im ADEPT
f lex
-Modell vom Migrationszielserver ohnehin
ben¨otigt [RD98], so dass aus ihrer ¨
Ubertragung kein zus¨atzlicher Aufwand resultiert.
Werden die in der ¨
Anderungshistorie vermerkten Basisoperationen auf die urspr¨ung-
liche WF-Vorlage angewandt, so ergibt sich der ben¨otigte aktuelle Graph der WF-
Instanz. Wir erhalten somit ein einfach zu realisierendes Verfahren zur ¨
Ubermittlung
eines Ausf¨uhrungsgraphen,durch das der Kommunikationsaufwanddrastisch reduziert
wird. Da auf eine einzelne WF-Instanz in der Regel nur sehr wenige ¨
Anderungenange-
wandt werden, ist der zum Berechnen des aktuellen Ausf¨uhrungsgraphen notwendige
Aufwand gering.
4.2 Optimierung des Verfahrens zur ¨
Ubermittlung von ¨
Anderungshistorien
Im Allgemeinen kann derselbe WF-Server mehrere Male an der Steuerung einer WF-
Instanz beteiligt sein. So gibt der Server
s
1
in dem Beispiel aus Abb. 4 die Kontrolle
nach Beendigungder Aktivit¨at
d
ab, erh¨alt sie sp¨ater aber zur Steuerung der Aktivit¨at
f
wieder zur¨uck.Ein solcher Server kennt deshalbbereits die ¨
Anderungshistorieneintr¨age
zu den von ihm selbst durchgef¨uhrten ¨
Anderungen (da er die ¨
Anderungshistorie so-
lange aufbewahrt, bis er ¨uber die Beendigung der entsprechenden WF-Instanz infor-
miert wird). Zus¨atzlich kennt er alle ¨
Anderungen, die erfolgt sind, bevor er letztmals
die WF-Instanz kontrolliert hat. Der zu solchen ¨
Anderungen geh¨orende Teil der ¨
Ande-
rungshistorie muss also nicht mehr zu diesem Server ¨ubertragen werden, wodurch das
zur Migration des ”aktuellen Ausf¨uhrungsgraphen“ notwendige Datenvolumen weiter
reduziert werden kann.
a
d
h
f g
c
e
b
s
1
s
1
s
3
s
1
s
2
s
1
s
4
s
4
a)
b) S ta rt(a , s 1, ...), D y n M o d if(1 ), E n d (a , s 1, ...), D y n M o d if(2 ), S ta rt(d , s 1, ...), E n d (d , s 1, ...),
S ta rt(e , s 2, ...), D y n M o d if(3 ), E n d (e , s 2, ...)
Abbildung4. a) WF-Instanz und b) Ablaufhistorie10des Servers
s
2
nach Beendigung der Akti-
vit¨at
e
.
4.2.1 Versenden von ¨
Anderungshistorieneintr¨
agen
Die naheliegendeste Idee, um redundante ¨
Ubertragungen von ¨
Anderungshistorien-
eintr¨agen zu vermeiden, besteht darin, dass der Migrationsquellserver aus der ihm be-
kannten Ablaufhistorie ermittelt, welche ¨
Anderungen dem Zielserver schon bekannt
sein m¨ussen. Die entsprechendenEintr¨age werdendann nicht mehr ¨ubertragen.So kann
in dem in Abb. 4 dargestellten Beispiel der Server
s
2
nach Beendigung der Aktivit¨at
e
ermitteln, dass der Migrationszielserver
s
1
die ¨
Anderungen 1 und 2 schon kennen
muss. Der Grund daf¨ur ist, dass sich in der Ablaufhistorie die Verweise (DynModif)
auf diese ¨
Anderungen vor dem Eintrag f¨ur die Beendigung der vom Server
s
1
kontrol-
lierten Aktivit¨at
d
befinden. Deshalb muss bei der Migration
M
e;f
ausschließlich der
¨
Anderungshistorieneintragzur ¨
Anderung 3 ¨ubertragen werden.
Allerdings kannmit dem skizzierten Verfahreneine redundante ¨
Ubertragungvon ¨
Ande-
rungshistorieneintr¨agennicht immer verhindertwerden: Bei den Migrationen
M
f;g
und
10 Bei verteilter WF-Steuerung wird in einer Ablaufhistorie, zus¨atzlich zu den in Abschnitt 2.2
beschriebenen Werten, in jedem Eintrag vermerkt, welcher Server die entsprechende Aktivit¨at
kontrolliert hat.
M
c;h
zum Server
s
4
m¨ussen prinzipiell die Eintr¨age zu den ¨
Anderungen 1, 2 und 3
¨ubertragen werden, da der Server
s
4
bisher nicht an der Ausf¨uhrung der WF-Instanz
beteiligt war. Der Migrationsquellserver
s
1
bzw.
s
3
kann aber aus der bei ihm lokal
vorhandenen Information nicht ableiten, ob die jeweils andere Migration schon erfolgt
ist. Deshalb muss bei beiden Migrationen die gesamte ¨
Anderungshistorie ¨ubertragen
werden. Durch das im n¨achsten Abschnitt vorgestellte Verfahren wird eine solch redun-
dante Daten¨ubertragung vermieden.
4.2.2 Anfordern von ¨
Anderungshistorieneintr¨
agen
Um das im vorherigen Abschnitt beschriebene Problem zu l¨osen, wird nun ein Ver-
fahren vorgestellt, bei dem die noch ben¨otigten ¨
Anderungshistorieneintr¨age durch den
Migrationszielserverexplizit angefordertwerden. Dieser teilt dem Quellserver bei einer
Migration mit, welche Eintr¨age ihm schon bekannt sind, so dass die fehlenden ¨
Ande-
rungshistorieneintr¨age gezielt ¨ubertragen werden k¨onnen. In ADEPT
distr ibution
wird
f¨ur die ¨
Ubertragung von Ablaufhistorien ein ¨ahnliches Verfahren verwendet, das eben-
falls auf dem Anfordern von noch ben¨otigter Informationbasiert (siehe [BRD00]). Das
Anfordern und ¨
Ubertragen von ¨
Anderungshistorieneintr¨agen kann im selben Kommu-
nikationszyklus erfolgen, so dass hierf¨ur keine zus¨atzliche Kommunikation notwendig
wird.
Das Anfordern des noch fehlenden Teils der ¨
Anderungshistorie ist bei dem hier be-
schriebenen Verfahren relativ einfach und effizient implementierbar, da stets jeder an
einer WF-Instanz beteiligte Server alle bis zum aktuellen Zeitpunkt erfolgten ¨
Anderun-
gen kennt. Deshalb ist einem Migrationszielserver der ”Anfang“ der ¨
Anderungshistorie
bekannt, d.h. er verf¨ugt bis zu einer bestimmten Stelle ¨uber alle Eintr¨age und ab die-
ser Stelle kennt er keine weiteren Eintr¨age. Zum Anfordern der fehlenden Teile der
¨
Anderungshistorie gen¨ugt es also, die ID des letzten bekannten Eintrags an den Quell-
server der Migration zu ¨ubertragen, woraufhin dieser alle auf diesen Eintrag folgenden
Eintr¨age ¨ubermittelt.
Das soeben angedeutete Verfahrenwird durch den Algorithmus4 realisiert. Dieser wird
von dem Migrationsquellserverals Teil der Prozedur MigrateWorkflowInstance des Al-
gorithmus 1 ausgef¨uhrt, von der außerdem die Ablaufhistorie und die WF-relevanten
Daten ¨ubertragen werden (siehe [BRD00]). Der Algorithmus 4 st¨oßt die ¨
Ubertragung
der ¨
Anderungshistorie an, indem die ID des neuesten beim Migrationszielserver be-
kannten ¨
Anderungshistorieneintrags erfragt wird. Ist diesem Server noch keine ¨
Ande-
rungshistorie zu dieser WF-Instanz bekannt, so gibt er NULL zur¨uck. In diesem Fall ist
f¨ur ihn die gesamte am Quellserver bekannte ¨
Anderungshistorie relevant. Andernfalls
ist f¨ur den Zielserver die ¨
Anderungshistorie erst ab dem Historieneintrag relevant, der
auf den zur¨uckgemeldetenEintrag folgt. Der jeweils relevanteTeil der ¨
Anderungshisto-
rie wird in die Historie RelevantChangeHistory kopiert und zum Zielserver ¨ubertragen.
Dies kann in einer einzigen ¨
Ubertragung gemeinsam mit den anderen oben erw¨ahnten
WF-Daten geschehen.
Die Funktionsweise des Algorithmus 4 soll noch an dem in Abb. 4 dargestellten Bei-
spiel verdeutlicht werden: Bei der Migration
M
e;f
kennt der Zielserver
s
1
die dynami-
Algorithmus 4 ( ¨
Ubermittlung einer dynamischen ¨
Anderung)
input
Inst: ID der zu ¨andernden WF-Instanz
TargetServer: Server, an den die ¨
Anderungshistorie ¨ubertragen wird
begin
// ¨
Ubertragung der ¨
Anderungshistorie anstoßen, indem ID des letzten bekannten Eintrags
// erfragt wird
LastEntry = GetLastEntry(Inst)
!
TargetServer;
// f¨ur ¨
Ubertragung relevanten Teil der ¨
Anderungshistorie ermitteln
if LastEntry = NULL then
// am Zielserver ist ¨
Anderungshistorie ¨uberhaupt noch nicht bekannt
Relevant = True;
else // alle Eintr¨age bis einschließlich LastEntry sind am Zielserver schon bekannt
Relevant = False;
// Positionsz¨ahler f¨ur originale und zu erzeugende ¨
Anderungshistorie initialisieren
i=1; j=1;
// gesamte ¨
Anderungshistorie der WF-Instanz Inst durchlaufen
while ChangeHistory(Inst)[i]
6
=
EOF do
if Relevant = True then // Eintrag ggf. in Ergebnis ¨ubernehmen
RelevantChangeHistory[j] = ChangeHistory(Inst)[i];
j=j+1;
// Pr¨ufen, ob das Ende der am Zielserver bekannten Historie erreicht wurde
if EntryID(ChangeHistory(Inst)[i]) = LastEntry then Relevant = True;
i=i+1;
// ¨
Ubertragung der ¨
Anderungshistorie durchf¨uhren
TransmitChange(Inst, RelevantChangeHistory)
!
TargetServer;
end.
schen ¨
Anderungen1 und 2. Deshalb gibt er LastEntry = 2 zur¨uck,woraufhinder Migra-
tionsquellserverdie ¨
Anderungshistorieneintr¨age1 und 2 ignoriertund nur den Eintrag3
¨ubertr¨agt. Damit ergibt sich dasselbe Ergebnis, wie bei dem im Abschnitt 4.2.1 vorge-
stellten Ansatz. F¨ur die Migrationen
M
c;h
und
M
f;g
wird o.B.d.A. angenommen, dass
M
c;h
zuerst durchgef¨uhrt wird.11 Da der Server
s
4
noch ¨uber keine ¨
Anderungshisto-
rie zu dieser WF-Instanz verf¨ugt, ergibt sich bei dieser Migration LastEntry = NULL,
weshalb die gesamte Historie ¨ubertragen wird. Bei der anschließend stattfindenden Mi-
gration
M
f;g
sind dem Zielserver
s
4
die Historieneintr¨age 1 bis 3 bekannt, weshalb
LastEntry den Wert 3 erh¨alt. Beim Durchlaufen der While-Schleife von Algorithmus 4
wird die Variable Relevant erst dann auf True gesetzt, nachdem die Eintr¨age 1 bis 3
bearbeitet wurden. Da keine weiteren Eintr¨age in der ¨
Anderungshistorie folgen, bleibt
RelevantChangeHistoryleer,sodass keine ¨
Anderungshistorieneintr¨age ¨ubermitteltwer-
11 Dass die Migrationen gleichzeitig durchgef¨uhrt werden, wird durch eine vom Migrationsziel-
server gehaltene Sperre verhindert. Diese sorgt daf¨ur, dass die zur selben WF-Instanz einge-
henden Migrationen serialisiert werden, d.h. die Sperre wird ab dem Anstoßen der Migration,
w¨ahrend dem Ermitteln und ¨
Ubertragen der ¨
Anderungshistorieneintr¨age (und der anderen WF-
Daten [BRD00]), bis zur Integration der Eintr¨age in die ¨
Anderungshistorie gehalten. Diese
Sperre verhindert, dass Eintr¨age redundant angefordert werden, weil von veralteter lokaler
Information ausgegangen wird.
den.Das aus Abschnitt 4.2.1bekannteProblem derredundantenDaten¨ubertragungwird
hier also vermieden.
Es ist somit nicht nur m¨oglich, dynamische ¨
Anderungen in einem verteilten WfMS ef-
fizient durchzuf¨uhren (siehe Abschnitt 3), ver¨anderte WF-Instanzen k¨onnen außerdem
mit sehr geringen ¨
Ubertragungskostenmigriert werden.
5 Diskussion
In der WF-Literatur finden sich zahlreiche Arbeiten, die sich mit Skalierbarkeitsfra-
gestellungen und verteilter WF-Ausf¨uhrung besch¨aftigen (z.B. [AKA
+
94,AMG
+
95,
BMR96,CGP
+
96,GJS
+
99,GT98,Jab97,MWW
+
98,SK97,SM96,Wes99]),einen um-
fassenden ¨
Uberblick bietet [BD99b]. Ebenso gibt es viele Ver¨offentlichungen zu dem
Thema dynamische WF- ¨
Anderungen (z.B. [BPS97, CCPP98, DMP97, EM97, HK96,
HSS96,JH98, KG99, KRW90, LP98,MR00, Sie98, Wes98]), die in [Rei00] diskutiert
werden. Jedoch gibt es kaum Projekte, die beide Aspekte gemeinsam betrachten – ins-
besondere wird derenZusammenspiel nicht hinreichendgew¨urdigt.Es ist nicht das Ziel
dieser Arbeiten, ein bez¨uglich der Kommunikationskosten effizientes WfMS zu ent-
wickeln, das skalierbar und flexibel ist. Dieser Aspekt wird in der vorliegenden Arbeit
erstmalig systematisch untersucht.
WIDE erlaubt dynamische ¨
Anderungen einer WF-Vorlage und deren Propagierung
auf laufende WF-Instanzen [CCPP98]. Außerdem werden WF-Instanzen verteilt ge-
steuert [CGP
+
96], wobei die Bearbeiter einer Aktivit¨at den WF-Server determinie-
ren, der diese Aktivit¨at kontrolliert. Bei MOKASSIN [GJS
+
99, JH98] und WASA
[Wes98, Wes99] wird die verteilte WF-Ausf¨uhrung durch eine zugrunde liegende
CORBA-Infrastruktur realisiert. Außerdem sind ¨
Anderungen auf Schema- und auf In-
stanzebene m¨oglich, wobei auch Konsistenzfragestellungen betrachtet werden. INCAs
[BMR96] verwirklicht die Steuerung der WF-Instanzen durch Regeln, die modifiziert
werden k¨onnen, um dynamische ¨
Anderungendurchzuf¨uhren.Die WF-Steuerung findet
verteilt statt, wobei eine WF-Instanz stets von dem Rechner desjenigen Benutzers kon-
trolliert wird, der die aktuelle Aktivit¨at bearbeitet. Bei all diesen Ans¨atzen wird aber
nicht explizit auf das Zusammenspiel der dynamischen ¨
Anderungen und der verteilten
WF-Ausf¨uhrung eingegangen.
In der Literatur finden sich auch einige Ans¨atze f¨ur verteiltes WF-Management, bei
denen eine WF-Instanz w¨ahrend ihrer gesamten Lebenszeit von nur einem einzigen
WF-Server kontrolliert wird (z.B. Exotica [AKA
+
94], MOBILE [Jab97] - wurde aber
in [SNS99] erweitert). Es finden also keine Migrationen statt, unterschiedliche WF-
Instanzen k¨onnen aber von verschiedenen Servern kontrolliert werden. Da f¨ur jede
WF-Instanz eine zentrale Kontrollinstanz existiert, k¨onnten dynamische ¨
Anderungen
bei diesen Ans¨atzen also genauso wie in einem zentralen WfMS durchgef¨uhrt werden.
Allerdings ist es bei diesem Verteilungsmodell nicht m¨oglich, f¨ur jede einzelne Akti-
vit¨at einen bez¨uglich der Kommunikationskosten g¨unstigen WF-Server auszuw¨ahlen.
Da deshalb bei der ”normalen WF-Ausf¨uhrung“ h¨ohere Mehrkosten entstehen, als die
bei den (verh¨altnism¨aßig seltenen) dynamischen ¨
Anderungen erzielten Einsparungen,
wurde f¨ur ADEPT kein solcher Ansatz gew¨ahlt.
6 Zusammenfassung und Ausblick
Verteilte WF-Ausf¨uhrung und dynamische ¨
Anderungen sind essentiell, um WfMS
auch zur Unterst¨utzung von anspruchsvollen vorgangsorientierten Anwendungssyste-
men einsetzen zu k¨onnen. Allerdings sind mit diesen beiden Aspekten teilweise entge-
gengesetzte Anforderungen und Ziele verbunden, da die f¨ur dynamische ¨
Anderungen
notwendige zentrale Kontrollinstanz die Effizienz der verteilten WF-Ausf¨uhrung be-
eintr¨achtigt. Deshalb k¨onnen die beiden Themen nicht getrennt voneinander betrachtet
werden. Ihre Wechselwirkungen werden in dieser Arbeit erstmalig untersucht, mit dem
Ergebnis, dass die beiden Aspekte durchaus vereinbar sind. Es ist gelungen, dynami-
sche ¨
Anderungenin einem verteilten WfMS auf effiziente Art und Weise zu realisieren.
Auch die verteilte Steuerung einer zuvor ver¨anderten WF-Instanz ist ¨außerst effizient
m¨oglich, da zur ¨
Ubermittlung des modifizierten Ausf¨uhrungsgraphenlediglich ein Teil
der ohnehin relativ kleinen ¨
Anderungshistorie ¨ubertragen werden muss. Dies ist beson-
ders wichtig, da Migrationen h¨aufige Operationen sind. Zusammenfassend l¨asst sich
feststellen, dass es gelungen ist, verteilte WF-Ausf¨uhrung und dynamische ¨
Anderun-
gen nahtlos in ein System zu integrieren.
Alle in diesem Beitrag vorgestellten Verfahren wurden in dem WfMS-Prototypen
ADEPT
workf low
implementiert [Zei99]. Dieser Prototyp wurde auf der CeBIT’2000,
der EDBT’2000 [HRB
+
00] und der BIS’2000 [DRK00] einem breiten Publikum
pr¨asentiert. Durch die Implementierung konnte die Umsetzbarkeit der Verfahren ge-
zeigt werden. Außerdem ist bei der Durchf¨uhrung von Migrationen zu erkennen, dass
nur moderate Datenmengen ¨ubertragen werden.
Optimierungspotential besteht noch hinsichtlich der Wahl der WF-Server, die in eine
dynamische ¨
Anderung einbezogen werden m¨ussen: Betrifft eine ¨
Anderung nur einen
Ausschnitt des WF-Graphen, so k¨onnte eine ¨
Anderung auch nur von einem Teil der
aktuell in die WF-Instanz involvierten WF-Server durchgef¨uhrt werden, wodurch der
Synchronisations- und Kommunikationsaufwand reduziert wird. Im Extremfall wird
nur ein einziger Zweig einer Parallelit¨at ver¨andert, weshalb eigentlichauch nur ein Ser-
ver f¨ur die Durchf¨uhrung der ¨
Anderung ben¨otigt wird. Allerdings k¨onnen Aktivit¨aten
paralleler Ausf¨uhrungszweige (z.B. durch Abh¨angigkeiten im Datenfluss oder durch
entsprechend festgelegte temporale Bedingungen) von dieser ¨
Anderung betroffen sein,
so dass die zugeh¨origen Server in diesem F¨allen doch einbezogen werden m¨ussen. Un-
sere bisherigen Untersuchungen ergaben, dass eine solche Optimierung deshalb eher
selten eingesetzt werden kann, so dass eine signifikante Verbesserung des Systemver-
haltens nicht zu erwarten ist. Dennoch bietet dieser Aspekt Ansatzpunkte f¨ur weiterge-
hende Forschung.
Danksagung: Wir danken Clemens Hensinger, Thomas Strzeletz und Jochen Zeitler f¨ur die an-
regenden Diskussionen.
Literatur
[AKA
+
94] G. Alonso, M. Kamath, D. Agrawal, A.El Abbadi, R.G¨unth¨or und C. Mohan: Fai-
lure Handling in Large Scale Workflow Management Systems. Technischer Bericht
RJ9913, IBM Almaden Research Center, November 1994.
[AMG
+
95] G. Alonso, C. Mohan, R. G¨unth¨or, D. Agrawal, A. El Abbadi und M. Kamath:
Exotica/FMQM: A Persistent Message-Based Architecture for Distributed Work-
flow Management. In: Proc. IFIP Working Conf. on Information Systems for De-
centralized Organisations, Trondheim, August 1995.
[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 Distributed Control of Enterprise-Wide and
Cross-Enterprise Workflows. In: Proc. Workshop Enterprise-wide and Cross-
enterprise Workflow Management: Concepts, Systems, Applications, 29. Jahres-
tagung der GI, S. 25–32, Paderborn, Oktober 1999.
[BD99b] T. Bauer und P. Dadam: Verteilungsmodelle f¨ur Workflow-Management-Systeme –
Klassifikation und Simulation. Informatik Forschung und Entwicklung, 14(4):203–
217, Dezember 1999.
[BD00] T. Bauer und P. Dadam: Efficient Distributed Workflow Management Based on Va-
riable Server Assignments. In: Proc. 12th Conf. on Advanced Information Systems
Engineering, S. 94–109, Stockholm, Juni 2000.
[BMR96] D. Barbar´a, S. Mehrotra und M. Rusinkiewicz: INCAs: Managing Dynamic Work-
flows in DistributedEnvironments. Journal of Database Management, Special Issue
on Multidatabases, 7(1):5–15, 1996.
[BPS97] P. Bichler, G. Preuner und M. Schrefl: Workflow Transparency. In: Proc. 9th
Int. Conf. on Advanced Information Systems Engineering, S. 423–436, Barcelona,
1997.
[BRD00] T. Bauer, M. Reichert und P. Dadam: Effiziente Durchf¨uhrung von Prozessmigra-
tionen in verteilten Workflow-Management-Systemen. Ulmer Informatik-Berichte
2000-08, Universit¨at Ulm, Fakult¨at f¨ur Informatik, Juni 2000.
[CCPP98] F. Casati, S. Ceri, B.Pernici und G. Pozzi: Workflow Evolution. Data & Knowledge
Engineering, 24(3):211–238, 1998.
[CGP
+
96] F. Casati, P. Grefen, B. Pernici, G. Pozzi und G. S´anchez: WIDE: Workflow Model
and Architecture. CTIT Technical Report 96-19, University of Twente, 1996.
[DKR
+
95] P. Dadam, K. Kuhn, M. Reichert, T. Beuter und M. Nathe: ADEPT: Ein integrie-
render Ansatz zur Entwicklung flexibler, zuverl¨assiger kooperierender Assistenz-
systeme in klinischen Anwendungsumgebungen. In: Proc. GI/SI-Jahrestagung,S.
677–686, Z¨urich, September 1995.
[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 DistributedCollaborative Workflow Ma-
nagement - The MOKASSIN Approach. In: Proc. 2nd Symposium on Concurrent
Multidisciplinary Engineering, 3rd Int. Conf. on Global Engineering Networking,
Bremen, September 1999.
[GR93] J. Gray und A. Reuter: Transaction Processing: Concepts and Techniques. Morgan
Kaufmann Publishers, 1993.
[GT98] A. Geppert und D. Tombros: Event-Based Distributed Workflow Execution with
EVE. In: Proc. IFIP Int. Conf. on Distributed Systems Platforms and Open Distri-
buted Processing, 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¨arder und E. Rahm: Datenbanksysteme: Konzepte und Techniken der Imple-
mentierung. Springer-Verlag, 1999.
[HRB
+
00] C. Hensinger, M. Reichert, T. Bauer, T. Strzeletz und P. Dadam: ADEPT
wor kf low
- Advanced Workflow Technology for the Efficient Support of Adaptive, Enterprise-
wide Processes. In: 7th Int. Conf. on Extending Database Technology, Software
Demonstrations Track, S. 29–30, Konstanz, M¨arz 2000.
[HSS96] P. Heinl,H. Schuster und H. Stein:Behandlung von Ad-hoc-Workflows im MOBILE
Workflow-Modell. In: Proc. Softwaretechnik in Automation und Kommunikation –
Rechnergest¨utzte Teamarbeit, S. 229–242, M¨unchen, M¨arz 1996.
[Jab97] S. Jablonski: Architektur von Workflow-Mangement-Systemen. Informatik For-
schung und Entwicklung, Themenheft Workflow-Management, 12(2):72–81,
1997.
[JBS97] S. Jablonski, M. B¨ohm und W. Schulze: Workflow-Management: Entwicklung von
Anwendungen und Systemen; Facetten einer neuen Technologie. dpunkt-Verlag,
1997.
[JH98] G. Joeris und O. Herzog: Managing Evolving Workflow Specifications. In: Proc.
3rd IFCIS Conf. on Cooperative Information Systems, New York, August 1998.
[KAGM96] M. Kamath, G. Alonso, R. G¨unth¨or 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¨arz 1996.
[KG99] M. Kradolfer und A. Geppert: Dynamic Workflow Schema Evolution Based on
Workflow Type Versioning and Workflow Migration. In: Proc. 4rd IFCIS Int. Conf.
on Cooperative 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,
Cambridge, MA, 1990.
[LP98] L. Liu und C. Pu: Methodical Restructuring 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¨uller und E. Rahm: Dealing with Logical Failures for Collaborating Work-
flows. In: Proc. 5th Int. Conf. on Cooperative Information Systems, S. 210–223,
Eilat, September 2000.
[MWW
+
98] P. Muth, D. Wodtke, J. Weißenfels, A. Kotz-Dittrich und G. Weikum: From Cen-
tralized Workflow Specification to Distributed Workflow Execution. Journal of In-
telligent Information Systems, Special Issue on Workflow Management Systems,
10(2):159–184, M¨arz/April 1998.
[Obe96] A. Oberweis: Modellierung und Ausf¨uhrung von Workflows mit Petri-Netzen.
Teubner-Verlag, 1996.
[RBD99] M. Reichert, T. Bauer und P. Dadam: Enterprise-Wide and Cross-Enterprise
Workflow-Management: Challenges and Research Issues for Adaptive Workflows.
In: Proc. Workshop Enterprise-wide and Cross-enterprise Workflow Management:
Concepts, Systems, Applications, 29. Jahrestagung der GI, S. 56–64, Paderborn,
Oktober 1999.
[RD98] M. Reichert und P. Dadam: ADEPT
f lex
– Supporting Dynamic Changes of Work-
flows Without Losing Control. Journal of Intelligent Information Systems, Special
Issue on Workflow Management Systems, 10(2):93–129, M¨arz/April 1998.
[Rei00] M. Reichert: Dynamische Ablauf¨anderungen in Workflow-Management-Systemen.
Dissertation, Universit¨at Ulm, Fakult¨at f¨ur Informatik, Juli 2000.
[Sie98] R. Siebert: An Open Architecture for Adaptive Workflow Management Systems.
In: Proc. 3rd Biennial World Conf. on Integrated Design and Process Technology,
Vol. 2 - Issues and Applications of Database Technology, S. 79–85, Berlin, Juli
1998.
[SK97] A. Sheth und K.J. Kochut: Workflow Applications to Research Agenda: Scalable
and Dynamic Work Coordination and Collaboration Systems. In: Proc. NATO
Advanced Study Institute on Workflow Management Systems and Interoperability,
S. 12–21, Istanbul, August 1997.
[SM96] A. Schill und C. Mittasch: Workflow Management Systems on Top of OSF DCE
and OMG CORBA. Distributed Systems Engineering, 3(4):250–262, Dezember
1996.
[SNS99] H.Schuster, J. Neeb und R. Schamburger: A Configuration Management Approach
for Large Workflow Management Systems. In: Proc. Int. Joint Conf. on Work Acti-
vities Coordination and Collaboration, San Francisco, Februar 1999.
[Wes98] M. Weske: Flexible Modeling and Execution 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 Verteilungskonzepten in ein adaptives Workflow-Mana-
gement-System. Diplomarbeit, Universit¨at Ulm, Fakult¨at f¨ur Informatik, 1999.
