Vermeidung von ¨
Uberlastsituationen
durch Replikation von Workflow-Servern in ADEPT
Thomas Bauer, Peter Dadam
Abteilung Datenbanken und Informationssysteme, Universit¨at Ulm
bauer, dadam
@informatik.uni-ulm.de, http://www.informatik.uni-ulm.de/dbis
In einem Workflow-Management-System (WfMS) entsteht durch die Ausf¨
uhrung von Workflows (WF) eine hohe
Last. Dies betrifft sowohl die WF-Server, als auch das zugrunde liegende Kommunikationssystem. Im ADEPT-
Projekt wurde ein Verteilungsmodell entwickelt, das hilft, eine ¨
Uberlastung des Kommunikationssystems zu
vermeiden. Dabei wird zur Reduzierung der Kommunikationslast die Kontrolle ¨
uber einen WF ggf. von einem
WF-Server zu einem anderen WF-Server in einem anderen Teilnetz verlagert. Bei den in [BD97, BD00] be-
schriebenen Verfahren wird angenommen, dass sich genau ein WF-Server in jedem Teilnetz befindet. Da f¨
ur
diesen die zu bew¨
altigende Last m¨
oglicherweise zu hoch werden kann, wird in diesem Beitrag ein Verfahren
zur Replikation von WF-Servern vorgestellt. Dieses erlaubt eine beliebige und ver¨
anderbare Aufteilung der
Last auf die WF-Server eines Teilnetzes. Es zeichnet sich dadurch aus, dass keine zus¨
atzliche Kommunikation
ben¨
otigt wird.
1 Einleitung
WfMS erm¨oglichen die rechnerunterst¨utzte Ausf¨uhrung von Gesch¨aftsprozessen in einer verteilten
Systemumgebung. Der entscheidende Vorteil solcher Systeme ist, dass sie helfen, große Anwen-
dungssysteme ¨uberschaubarer zu gestalten. Dazu wird der applikationsspezifische Code der verwen-
deten Anwendungen von der Ablauflogik des Gesch¨aftsprozesses (”Prozesslogik“) getrennt. Anstelle
eines großen monolithischen Programmpakets erh¨alt man nun einzelne Aktivit¨aten, welche die An-
wendungsprogramme repr¨asentieren. Ihre Ablauflogik wird in einer separaten Kontrollflussdefinition
festgelegt, welche die Ausf¨uhrungsreihenfolge (Sequenz, Verzweigung, Parallelit¨at, Schleifen) der
einzelnen Aktivit¨aten bestimmt. Das WfMS sorgt daf¨ur, dass nur solche Aktivit¨aten ausgef¨uhrt wer-
den k¨onnen, die der Ablauflogik zufolge zur Ausf¨uhrung anstehen. Diese werden in die Arbeitslisten
autorisierter Bearbeiter eingef¨ugt. Welche Benutzer zur Bearbeitung einer bestimmten Aktivit¨at auto-
risiert sind, wird meist durch eine Rolle festgelegt, die auch den entsprechenden Bearbeitern zugeord-
net ist. Dabei ist es durchaus m¨oglich, dass mehrere Benutzer ermittelt werden, die f¨ur die Bearbeitung
einer bestimmten Aktivit¨at in Frage kommen.
Ein gravierender Mangel heutiger WfMS ist ihre schlechte Skalierbarkeit bei wachsenden Benutzer-
zahlen. Die Last f¨ur die WF-Server und f¨ur das zugrunde liegende Kommunikationsnetzwerk kann
sehr groß werden [BD99b, BD00]. Diese muss geeignet auf ausreichend viele Systemkomponenten
verteilt werden, um ¨
Uberlastsituationen zu vermeiden. In dieser Arbeit konzentrieren wir uns auf die
Vermeidung von ¨
Uberlastsituationen f¨ur die WF-Server. Dies soll allerdings so erfolgen, dass dadurch
keine gravierenden Nachteile f¨ur das Kommunikationsverhalten entstehen, d.h., zus¨atzliche Kommu-
nikation soll m¨oglichst vermieden werden.
1.1 Verteilte Workflow-Ausf¨uhrung
Wir betrachten eine unternehmensweite oder sogar unternehmens¨ubergreifende WF-basierte Anwen-
dung im operativen Einsatz. Durch die hohe Anzahl von Benutzern und gleichzeitig aktiven WF-
Instanzen1wird eine sehr große Last erzeugt. Diese kann dazu f¨uhren, dass Komponenten des WfMS
¨uberlastet werden. Deshalb wird in ADEPT
, der verteilten Variante des ADEPT-WfMS2
[DKR
95, RD98], eine WF-Instanz nicht mehr nur von einem WF-Server kontrolliert, sondern sie
wird partitioniert und abschnittsweise 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 diesem Server transportiert werden.
! ! "#%$
&'() ! "#+*
&'! ! "#-,
./021341',
5 6
7
1
8
./021341'2$
90:1'(3;1<*
#4"!=>? 1'
@&"'#A!"? ? 8? BDCC
@&"'#A!"? ? 8? BDCC
B/#D7%EF GD! "#
Abbildung 1 Partitionierung eines WF-Graphen und verteilte WF-Ausf¨uhrung.
Eine solche Partitionierung des WF-Graphen und die zugeh¨origen Migrationen werden auch in ande-
ren Ans¨atzen verwendet (z.B. [MWW
98]). Wir verfolgen in ADEPT zus¨atzlich das Ziel, die Kom-
munikationskosten zu minimieren. Der Grund daf¨ur ist, dass konkrete Erfahrungen mit existieren-
den WfMS gezeigt haben, dass zwischen dem WF-Server und seinen Clients sehr viel kommuniziert
wird und zum Teil auch große Datenmengen ausgetauscht werden. Dies kann dazu f¨uhren, dass das
Kommunikationssystem ¨uberlastet wird. Deshalb wird in ADEPT der WF-Server f¨ur jede Aktivit¨at
so gew¨ahlt, dass der Kommunikationsaufwand minimiert wird. Dazu wird der WF-Server f¨ur eine
Aktivit¨at in der Regel so gew¨ahlt, dass er im Teilnetz3der Mehrzahl ihrer potentiellen Bearbeiter
liegt. Dadurch wird in vielen F¨allen teilnetz¨ubergreifende Kommunikation zwischen dem WF-Server
und seinen Clients vermieden. Außerdem werden die Antwortzeiten verbessert und die Verf¨ugbar-
keit 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 dann der Fall, wenn abh¨
angige Be-
arbeiterzuordnungen (z.B. selber Bearbeiter wie Aktivit¨at
H
) verwendet werden, weil die potentiel-
len Bearbeiter einer Aktivit¨at dann vom Bearbeiter einer Vorg¨angeraktivit¨at abh¨angen. 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 erst zur Ausf¨uhrungszeit der entsprechenden WF-Instanz festzu-
legen. Der Server kann dann in einem f¨ur die entsprechenden Bearbeiter g¨unstigen Domain gew¨ahlt
werden. Zu diesem Zweck wurden f¨ur ADEPT
I(A(
so genannte variable Serverzuordnungen
[BD99a, BD00] entwickelt. Dies sind Ausdr¨ucke (z.B. "Server im Domain des Bearbeiters der Akti-
vit¨at
H
"), die zur Ausf¨uhrungszeit der WF-Instanz ausgewertet werden, um denjenigen WF-Server zu
ermitteln, der die zugeh¨orige Aktivit¨ateninstanz kontrollieren soll.
1In [KAGM96, SK97] werden Anwendungen beschrieben, bei denen die Zahl der Benutzer des WfMS bis auf einige
zehntausend anwachsen kann oder mehrere zehntausend WF gleichzeitig im System sein k¨onnen.
2ADEPT steht f¨ur Application Development Based on Encapsulated Pre-Modeled Process Templates.
3Ein Teilnetz wird zusammen mit den in ihm lokalisierten Clients und WF-Servern als Domain bezeichnet.
2
1.2 Problemstellung und Anforderungen
Der zentrale Aspekt von ADEPT
I
ist also, dass f¨ur jeden WF-Typ eine (bzgl. der bei der
WF-Ausf¨uhrung entstehenden Kommunikationslast) optimale Verteilung der Aktivit¨aten auf die WF-
Server ermittelt wird. Das Teilnetz, in dem sich der WF-Server einer bestimmten Aktivit¨ateninstanz
befindet, wird durch einen Serverzuordnungsausdruck vorgegeben. Um diese optimale Verteilung rea-
lisieren zu k¨onnen, m¨ussen alle Teilnetze ¨uber einen WF-Server verf¨ugen. In den bisherigen Ver¨offent-
lichungen zu ADEPT
(z.B. [BD97, BD99a, BD00]) haben wir angenommen, dass sich in
jedem Teilnetz genau ein WF-Server befindet. Das Problem dabei ist, dass dieser, wegen seiner be-
grenzten Leistungsf¨ahigkeit, ¨uberlastet sein kann, obwohl das zugeh¨orige Teilnetz noch nicht voll
ausgelastet ist. Um dieses Problem zu l¨osen, k¨onnte z.B. ein Hochleistungsrechner als WF-Server
verwendet werden, oder es k¨onnten mehrere WF-Server innerhalb eines Domains eingesetzt werden.
Wie wir noch sehen werden, wird sich letzterer Ansatz als besser geeignet erweisen.
In dieser Arbeit soll ein Verfahren f¨ur die Verwendung mehrerer WF-Server innerhalb eines Domains
entwickelt werden, welches die folgenden Anforderungen erf¨ullt:
1. Es muss m¨oglich sein, die zu bew¨altigende Last auf beliebig viele WF-Server zu verteilen. Diese
Lastaufteilung muss in einem beliebigen, vorzugebenden Verh¨altnis realisierbar sein. Es muss
also z.B. vorgegeben werden k¨onnen, dass sich die Last auf zwei zur Verf¨ugung stehende Server
im Verh¨altnis 3:2 aufteilt. Nur so kann bei einer beliebigen Menge an Server-Rechnern sicherge-
stellt werden, dass keiner dieser Server ¨uberlastet wird.
2. Durch den Einsatz mehrerer WF-Server innerhalb eines Domains d¨urfen die durch das Vertei-
lungsmodell von ADEPT erzielten Vorteile (z.B. die Reduzierung der Kommunikationslast) nicht
konterkariert werden. Deshalb sollte das zu entwickelnde Verfahren m¨oglichst keine (zus¨atzliche)
Kommunikation zwischen den WF-Servern desselben Domains erfordern. Die Auswahl eines
WF-Servers soll also ohne Abstimmungsprozess zwischen den verschiedenen Servern erfolgen.
3. Die Verwendung eines zentralen Servers zur Verteilung der Aufgaben verbietet sich, weil auch
mit diesem kommuniziert werden m¨usste, und weil eine solche zentrale Komponente einen Fla-
schenhals darstellen und die Verf¨ugbarkeit des WfMS beeintr¨achtigen w¨urde. Es wird also ein
verteiltes Verfahren zur Auswahl des Servers einer bestimmten Aktivit¨ateninstanz ben¨otigt.
4. Um eine Integration in ADEPT zu erm¨oglichen, muss das Verfahren auch im Zusammenspiel mit
variablen Serverzuordnungen funktionieren. Es muss also m¨oglich sein, zur Festlegung des WF-
Servers einer Aktivit¨at, Ausdr¨ucke (z.B. "Server im Domain des Bearbeiters der Aktivit¨at
H
") zu
verwenden, anstatt einen Server fest vorzugeben. Außerdem muss es im Falle einer dynamischen
¨
Anderung einer WF-Instanz [RD98, DRK00] ohne gr¨oßeren Aufwand m¨oglich sein, denjenigen
Server eines Domains zu ermitteln, der die WF-Instanz tats¨achlich kontrolliert (vgl. [RBD99]).
5. Es muss m¨oglich sein, die Anzahl der WF-Server und das Verh¨altnis der Lastaufteilung zwischen
ihnen im laufenden Betrieb zu ver¨andern, ohne dass dieser dadurch beeintr¨achtigt wird.
Es ist also das Ziel, ein Verfahren zu entwickeln, das eine beliebige und ver¨anderbare Verteilung der
Last auf die WF-Server erm¨oglicht und dabei m¨oglichst ohne Kommunikation auskommt.
1.3 Annahmen und Rahmenbedingungen
In diesem Abschnitt werden einige Aspekte der in diesem Beitrag zugrunde gelegten Systemumge-
bung er¨ortert. Da wir den operativen Einsatz von WfMS betrachten, kann von den folgenden Annah-
men ausgegangen werden:
3
J
Als WF-Server werden Rechner verwendet, die f¨ur diesen Zweck reserviert sind oder eine f¨ur die-
sen Zweck reservierte Bandbreite haben. Es ist also nicht anzunehmen, dass die Leistungsf¨ahig-
keit eines WF-Servers aufgrund anderer Aufgaben schwankt.
J
Die Leistungsf¨ahigkeit der WF-Server eines Domains ist etwas gr¨oßer als die zu bew¨altigende
Last erfordert (Reserve), so dass Lastschwankungen in einem gewissen Umfang ausgeglichen
werden k¨onnen.
J
Bei Ausfall eines WF-Servers werden dessen Aufgaben von einem Backup-Server ¨ubernommen
(vgl. [KAGM96]). Die Erh¨ohung der Verf¨ugbarkeit ist kein prim¨ares Ziel der in diesem Beitrag
vorgestellten Verfahren.
Im n¨achsten Abschnitt werden einige prinzipiell m¨ogliche L¨osungsans¨atze diskutiert. Das Verfah-
ren, mit dem der konkrete Server f¨ur eine Aktivit¨ateninstanz ausgew¨ahlt wird, wird in Abschnitt 3
vorgestellt. In Abschnitt 4 werden einige Fragestellungen betrachtet, welche die Ver¨anderung einer
gew¨ahlten Lastverteilung betreffen. Abschnitt 5 diskutiert die untersuchte Problemstellung im Kon-
text anderer verteilter WfMS-Ans¨atze. Der Beitrag schließt mit einer Zusammenfassung und einem
Ausblick auf weitere Arbeiten.
2 L¨
osungsans¨
atze
Im Folgenden wird untersucht, ob der in Abschnitt 1.2 angedachte Ansatz tats¨achlich am besten geeig-
net ist, umdie vorliegende Problemstellung zu l¨osen. Zu diesem Zweck werden zun¨achst verschiedene
grundlegende Ans¨atze vorgestellt und analysiert.
2.1 Verwendung eines Hochleistungssystems
Die zu bew¨altigende Last wird bei diesem Ansatz nicht, wie in Abschnitt 1.2 skizziert, auf mehrere
WF-Server verteilt. Stattdessen wird ein einziger, extrem leistungsstarker Rechner verwendet.
Der Vorteil dieses Ansatzes ist, dass die bisher f¨ur ADEPT entwickelten Verfahren unver¨andert wei-
terverwendet werden k¨onnen. Allerdings entstehen f¨ur Hochleistungssysteme in der Regel sehr hohe
Anschaffungskosten, so dass es sich lohnt, andere Alternativen zu betrachten. Außerdem kann auch
ein solcher Rechner an seine Leistungsgrenzen stoßen.
2.2 Ver¨
andern der Serverzuordnungen
Bei diesem Ansatz befindet sich in jedem Domain weiterhin nur ein WF-Server. Um diesen bei Bedarf
zu entlasten, k¨onnen einige der von ihm kontrollierten Aktivit¨aten Servern anderer Domains zugeord-
net werden. Dazu werden die Serverzuordnungen dieser Aktivit¨aten entsprechend ver¨andert.
Durch diese Vorgehensweise werden die Kommunikationskosten erh¨oht, da ein Server ja gerade des-
halb gew¨ahlt wurde, weil durch seine Verwendung die geringsten Kommunikationskosten anfallen.
Dieses Vorgehen widerspricht damit der Kernidee von ADEPT. Außerdem ist das Verfahren ¨uberhaupt
nicht anwendbar ist, wenn eine ”globale ¨
Uberlastung“ der WF-Server vorliegt, d.h., wenn insgesamt
mehr Last zu bew¨altigen ist, als die aktuell vorhandenen WF-Server verarbeiten k¨onnen. Da dieser
Ansatz nicht vorsieht, dass mehrere WF-Server im selben Teilnetz eingesetzt werden, kann deren
Gesamtkapazit¨at nicht durch die Hinzunahme weiterer Server erh¨oht werden.
4
2.3 Aufspaltung eines Domains
Ist der WF-Server eines Domains ¨uberlastet, so wird dieser in mehrere Domains aufgeteilt. Die da-
durch entstehenden Domains verf¨ugen ¨uber jeweils einen WF-Server und ein eigenes Teilnetz. Bei
diesem Ansatz werden also WF-Server und Teilnetze hinzugenommen. Eine Variante dieses Ansatzes
ist die Bildung von logischen Domains, die zwar jeweils ¨uber einen eigenen WF-Server verf¨ugen,
denen aber dasselbe Teilnetz zugrunde liegt. Bei beiden Varianten werden die Benutzer des ”Original-
domains“ auf die resultierenden Domains aufgeteilt.
Dieses Vorgehen ist immer dann empfehlenswert, wenn es eine ”nat¨urliche Zerlegung“ des Domains
gibt, d.h., wenn der Domain in weitgehend disjunkte Teile (getrennte Aktivit¨aten und getrennte Be-
nutzer) aufgespalten werden kann. Ist zudem auch das zugeh¨orige Teilnetz stark belastet, so empfiehlt
sich die Aufspaltung in Domains mit getrennten Teilnetzen. Dann wird allerdings durch die Ver¨ande-
rung der Domains ein Umbau des Kommunikationsnetzwerks notwendig.
Beide Varianten haben die folgenden gravierenden Nachteile: H¨aufig gibt es keine nat¨urliche Zer-
legung eines Domains, so dass keine sinnvolle Aufteilung der Benutzer auf die neu entstandenen
Domains existiert. Außerdem ist es schwierig, die Last im gew¨unschten Verh¨altnis auf die Domains
zu verteilen, weil die Belastung eines WF-Servers davon abh¨angt, wie viele und welche Bearbeiter
und Aktivit¨aten seinem Domain zugeordnet sind. Da also nicht direkt vorgegeben werden kann, in
welchem Verh¨altnis sich die Last auf die WF-Server verteilen soll, verletzt dies die Anforderung 1
(vgl. Abschnitt 1.2).
2.4 Mehrere Workflow-Server in einem Domain
Bei dem schon in Abschnitt 1.2 erw¨ahnten Ansatz bleiben die Domains bez¨uglich ihrer Benutzer und
Teilnetze unver¨andert. Bei Bedarf werden lediglich zus¨atzliche WF-Server in einem Domain verwen-
det. Wie der Server, der eine konkrete Aktivit¨ateninstanz kontrollieren soll, dann bestimmt werden
kann, wird im Abschnitt 3 diskutiert.
Bei diesem Ansatz wird bei der Modellierung nur festgelegt, in welchem Domain der WF-Server ei-
ner Aktivit¨at liegt. Welcher konkrete Server diese kontrollieren soll, ist ein physischer Aspekt, der bei
der Modellierung nicht betrachtet wird. Der Einsatz mehrerer WF-Server je Domain erm¨oglicht im
Prinzip eine beliebige Aufteilung der Last auf die WF-Server dieses Domains. Als positiver Neben-
effekt wird auch die Verf¨ugbarkeit verbessert, da ein Benutzer jetzt von mehreren WF-Servern seines
Domains bedient wird. F¨allt einer von diesen vor¨ubergehend aus, so kann der Benutzer zumindest mit
den anderen weiterarbeiten.
Die Verwendung von mehreren WF-Servern in einem Domain kann allerdings Einfluss auf das Kom-
munikationsverhalten beim Aktualisieren der Arbeitslisten der Benutzer4haben. Ob die zu kom-
munizierende Datenmenge gr¨oßer oder kleiner wird, h¨angt von der f¨ur das Aktualisieren der Ar-
beitslisten verwendeten Methode (vgl. [BD98]) ab. Wird die Arbeitsliste eines Bearbeiters in festen
Zeitabst¨anden aktualisiert, so wird durch das vorgestellte Verfahren eine h¨ohere Anzahl von Kom-
munikationen n¨otig, da diese Aktualisierungen nun von mehreren Servern pro Domain durchgef¨uhrt
werden m¨ussen. Die kommunizierte Datenmenge ver¨andert sich insgesamt gesehen jedoch nicht, da
jeder WF-Server nur den von ihm verwalteten Teil der Gesamtarbeitsliste des Benutzers ¨ubertragen
4Ein Benutzer erh¨alt in ADEPT seine Arbeitsliste von mehreren WF-Servern aus verschiedenen bzw. gleichen Domains.
Dies ist aber f¨ur den Anwendungsentwickler transparent. Um dies zu erreichen, kapselt das API des WF-Client die verteilte
Arbeitslistenverwaltung und bietet die Gesamtarbeitsliste des Benutzers an.
5
muss. Wird dagegen die Arbeitsliste eines Benutzers bei jeder ¨
Anderung stets sofort aktualisiert, so
¨andert sich die Anzahl der Kommunikationen nicht, da die Anzahl der ¨
Anderungen gleich bleibt.
Da jeweils nur noch der zu diesem WF-Server geh¨orende Teil der Arbeitsliste (komplett) ¨ubertragen
wird, wird die insgesamt kommunizierte Datenmenge sogar kleiner. Wird jeweils nur der neu hinzu-
gekommene Eintrag ¨ubertragen (das ”Delta“), so bleibt die kommunizierte Datenmenge unver¨andert.
Zusammenfassend l¨asst sich also feststellen, dass die Verwendung von mehreren WF-Servern in ei-
nem Domain Auswirkungen auf das Kommunikationsverhalten beim Aktualisieren der Arbeitslisten
haben kann. Diese sind nicht besonders gravierend, da die zur Aktualisierung der Arbeitslisten ¨uber-
tragene Datenmenge i.d.R. klein ist, verglichen mit der sonstigen Kommunikation eines WfMS (Start
von Aktivit¨aten, Migrationen). Insbesondere ist es von der f¨ur die Aktualisierung verwendeten Me-
thode abh¨angig, ob diese Auswirkungen positiv, negativ oder neutral sind.
Da die Verfahren aus Abschnitt 2.1 - 2.3 nicht geeignet sind, um das gegebene Problem zu l¨osen, wird
nur der zuletzt vorgestellte Ansatz weiter verfolgt. Im nun folgenden Abschnitt wird beschrieben, wie
bei diesem Verfahren die Auswahl eines konkreten WF-Servers f¨ur eine Aktivit¨ateninstanz ablaufen
muss, um damit eine beliebige Verteilung der Last auf die Server erreichen zu k¨onnen.
3 Auswahl des Workflow-Servers eines Domains
Im vorherigen Abschnitt haben wir uns daf¨ur entschieden, den WF-Server eines Domains zu repli-
zieren. Um diese Entscheidung umsetzen zu k¨onnen, muss ein Verfahren entwickelt werden, welches
f¨ur eine Aktivit¨ateninstanz einen Server des vorgesehenen Domains ausw¨ahlt. Ein solches Verfah-
ren muss die in Abschnitt 1.2 aufgestellten Anforderungen erf¨ullen, damit es nicht der Zielsetzung
von ADEPT entgegenwirkt. Insbesondere muss es eine beliebige Lastaufteilung erm¨oglichen und die
Konzepte von ADEPT, wie z.B. variable Serverzuordnungen [BD00], unterst¨utzen. Außerdem sollte
es m¨oglichst ohne zus¨atzliche Kommunikationen realisiert werden. Um die Erf¨ullung der Anforde-
rung 5, welche die ¨
Anderbarkeit der Lastaufteilung im laufenden Betrieb fordert, k¨ummern wir uns
im Abschnitt 4. Im Folgenden werden nun einige m¨ogliche Vorgehensweisen untersucht und ein Ver-
fahren entwickelt, welches die Anforderungen 1-4 erf¨ullt.
3.1 Statische Festlegung des Workflow-Servers zur Modellierungszeit
Eine einfache M¨oglichkeit, die Last auf mehrere Server aufzuteilen, ist, den WF-Server f¨ur eine Ak-
tivit¨at (so wie schon bisher den Domain) im WF-Modell explizit festzulegen (z.B. Aktivit¨at
K
wird
von Server 2 des Domains 7 kontrolliert). Unterschiedliche Aktivit¨atentypen (aus unterschiedlichen
Partitionen) k¨onnen so von verschiedenen WF-Servern eines Domains kontrolliert werden.
Da konkrete Server f¨ur die Aktivit¨aten vorgegeben werden, ist es kaum m¨oglich, ein gew¨unschtes
Verh¨altnis der Lastaufteilung zu realisieren. Wie bei den Verfahren aus Abschnitt 2.3 ist damit die
Anforderung 1 verletzt. Außerdem kann das Verfahren nicht in Verbindung mit variablen Serverzu-
ordnungen eingesetzt werden, weil diese durch einen Ausdruck, der erst zur Ausf¨uhrungszeit aus-
gewertet wird, den Domain einer Aktivit¨at festlegen (z.B. "Server im Domain des Bearbeiters der
Aktivit¨at 1"). Eine explizite Festlegung eines WF-Servers innerhalb des resultierenden Domains ist
deshalb nicht m¨oglich.
6
3.2 Lastabh¨
angige Auswahl des Workflow-Servers
Eine Aufteilung der Last auf die WF-Server l¨asst sich auch erreichen, indem derjenige WF-Server
ausgew¨ahlt wird, der aktuell am wenigsten belastet ist (gemessen an seiner Soll-Last). Die Identifika-
tion des entsprechenden WF-Servers erfordert, dass Lastinformation ¨uber dessen Domain verf¨ugbar
ist. Um diese zur Verf¨ugung zu stellen, sind prinzipiell zwei Vorgehensweisen denkbar:
1. Die Lastinformation wird (periodisch oder falls m¨oglich ”Huckepack“ mit sonstigen Kommuni-
kationen) an alle WF-Server des WfMS verteilt. Soll eine Migration durchgef¨uhrt werden, so ist
die Lastinformation lokal vorhanden, so dass der Zielserver ausgew¨ahlt werden kann.
2. Die Lastinformation wird ausschließlich einem Dispatcher im jeweiligen Domain gemeldet. Soll
der WF-Server f¨ur eine Aktivit¨ateninstanz ausgew¨ahlt werden, so f¨uhrt der Dispatcher des jewei-
ligen Domains diese Auswahl durch.
Die erste Methode erfordert einen h¨oheren Aufwand bei der Verteilung der Lastinformation, weil je-
der WF-Server die aktuelle Belastung jedes anderen Servers kennen muss. Bei der zweiten Methode
wird der Aufwand f¨ur die Verteilung der Lastinformation reduziert, da nur der Dispatcher diese Infor-
mationen ben¨otigt. Andererseits wird ein gr¨oßerer Aufwand f¨ur die Auswahl des WF-Servers n¨otig,
da zuerst mit dem jeweiligen Dispatcher kommuniziert werden muss. Außerdem stellt der Dispatcher
eine zentrale Komponente dar, welche die Verf¨ugbarkeit seines Domains verschlechtert, da er bei je-
der Migration ben¨otigt wird. Beide Varianten verletzen also die Anforderung 2, die zweite Methode
zus¨atzlich die Anforderung 3.
Der Vorteil von lastabh¨angigen Verfahren ist, dass Schwankungen in der Belastung der WF-Server
ausgeglichen werden k¨onnen. Diese k¨onnen aufgrund WfMS-externer Ereignisse auftreten, oder weil
die von einem Server verwalteten WF-Instanzen in einem bestimmten Zeitintervall besonders viel
Last erzeugen. Der entscheidende Nachteil beider Verfahren ist der zus¨atzlich entstehende Aufwand
f¨ur Kommunikation und Synchronisation. Dieser f¨uhrt dazu, dass die von den WF-Servern bew¨altigte
Last nicht mehr linear zu deren Leistungsf¨ahigkeit w¨achst. Außerdem ist – wie schon von Scheduling-
Verfahren bekannt ist [Gos91] – f¨ur den Erfolg eines lastabh¨angigen Verfahrens die Qualit¨at der Last-
information und eine geeignet gew¨ahlte Frequenz f¨ur den Lastinformationsaustausch ¨außerst kritisch.
Dies gilt umso mehr, weil WF eine komplexe interne Struktur aufweisen und f¨ur mehrere Wochen am
gew¨ahlten Server verweilen k¨onnen. Zusammenfassend l¨asst sich also feststellen, dass lastabh¨angige
Verfahren ein (akademisch) interessanter Ansatz sind, da sie potentiell die M¨oglichkeit bieten, Last-
schwankungen auszugleichen. Sie sind aber schwer zu realisieren und erzeugen selbst zus¨atzliche
Kommunikationslast.
3.3 Zuf¨
allige Auswahl des Workflow-Servers zur Laufzeit
Wenn f¨ur eine WF-Instanz mit der Ausf¨uhrung einer Partition (in dem vorgegebenen Domain) begon-
nen wird (WF-Start oder Migration), dann kann zuf¨allig ein WF-Server dieses Domains ausgew¨ahlt
werden. Dazu wird eine Zufallszahl
L
aus dem Intervall
M NOPAQ
berechnet. Dieses Intervall wird in
disjunkte Teilintervalle zerlegt, die den WF-Servern des Domains zugeordnet sind. F¨ur die fragliche
Partition wird derjenige WF-Server gew¨ahlt, in dessen Teilintervall
L
f¨allt. Die Wahrscheinlichkeit,
dass ein bestimmter WF-Server gew¨ahlt wird (und damit sein Anteil an der Gesamtlast), entspricht
der L¨ange seines Intervalls.
Ein solches Verfahren hat einige sehr sch¨one Eigenschaften: Es erm¨oglicht eine beliebige Aufteilung
der Last. Diese ist zudem, durch eine Ver¨anderung der Teilintervalle, leicht ¨anderbar. Das Verfahren
7
ist auch f¨ur variable Serverzuordnungen anwendbar und es ist sogar m¨oglich, die Last f¨ur die Steue-
rung eines einzigen Aktivit¨atentyps auf mehrere WF-Server zu verteilen. Wegen der großen Anzahl
von WF-Instanzen ist es sehr unwahrscheinlich, dass, aufgrund von Unzul¨anglichkeiten des Zufalls-
zahlengenerators, deutlich von der geplanten Lastverteilung abgewichen wird.
Das Verfahren hat allerdings einen entscheidenden Nachteil: Es f¨uhrt zu einem Problem bei der Zu-
sammenf¨uhrung paralleler WF-Zweige. Dies soll an dem in Abb. 2 dargestellten Beispiel erl¨autert
werden: Angenommen, f¨ur die aktuelle WF-Instanz findet die Migration
RST U
vor
RSVT W
statt. Dann
wird bei der Ausf¨uhrung von
RXT U
der konkrete WF-Server innerhalb des Domains 3 festgelegt. Die-
ser ist aber dem WF-Server des Domains 2 nicht ohne weiteres bekannt. Bei einer naiven Implemen-
tierung dieses Verfahrens k¨onnte es deshalb vorkommen, dass dieser bei der Migration
RXYT W
einen
anderen WF-Server aus dem Domain 3 (zuf¨allig) ausw¨ahlt, was zu einem Problem bei der Zusam-
menf¨uhrung der parallelen Zweige an der Aktivit¨at
Z
f¨uhren w¨urde. Eine Abstimmung des Zielservers
zwischen den verschiedenen Startservern der Migration erfordert jedoch zus¨atzliche Kommunikation,
was der Anforderung 2 widerspricht.
[]\D^`_4a bdc
e
f g
h i
j
k]lDm`n4o p+q
k]lDm`n4o p`r
sut!v w
xdyz {
|~})
Abbildung 2 Problem bei der Zusammenf¨uhrung paralleler Zweige bei zuf¨alliger Serverwahl.
3.4 Pseudo-zuf¨
allige Auswahl des Workflow-Servers zur Laufzeit
Wir wollen die positiven Eigenschaften des vorherigen Verfahrens erhalten, jedoch das Problem bei
der Zusammenf¨uhrung paralleler Zweige vermeiden. Dies gelingt durch folgenden Trick: Der WF-
Server wird nicht rein zuf¨allig gew¨ahlt, sondern so, dass f¨ur eine WF-Instanz in einem Domain stets
derselbe WF-Server ermittelt wird. Dazu wird ein WF-instanzspezifisches Datum (z.B. die WF-ID)
mit einem Pseudo-Zufallszahlengenerator auf ein
LM NOPAQ
abgebildet. Dadurch ergibt sich f¨ur eine
WF-Instanz stets dasselbe
L
und damit derselbe WF-Server.
Alle Vorteile des vorherigen Verfahren bleiben erhalten: Es wird eine beliebige Aufteilung der Last
auf die WF-Server erm¨oglicht, alle Konzepte von ADEPT (inkl. variabler Serverzuordnungen) werden
unterst¨utzt und das Verfahren kommt ohne zus¨atzliche Kommunikation aus. Die Probleme bei der Zu-
sammenf¨uhrung paralleler Zweige werden vermieden, da innerhalb eines Domains f¨ur alle parallelen
Zweige einer WF-Instanz derselbe Server ermittelt wird. Weil es ebenfalls keine Kommunikation er-
fordert, erf¨ullt das Verfahren die Anforderungen 1-4 aus Abschnitt 1.2. F¨ur die Praxis ist zu erwarten,
dass es besser funktioniert als lastabh¨angige Verfahren. Die Gr¨unde daf¨ur sind, dass keine zus¨atzliche
Kommunikation notwendig wird, und dass das zu erwartende Systemverhalten leichter absch¨atzbar
ist. Da die WF-Server ¨uber eine Lastreserve verf¨ugen, spielt eine leichte Ungleichverteilung der Last
keine große Rolle. Auch deshalb wird kein Verfahren ben¨otigt, das eine solche Ungleichverteilung ak-
tiv ausgleicht. Aus diesen Gr¨unden wird das pseudo-zuf¨allige Verfahren weiter verfolgt. Im Folgenden
wird noch gekl¨art, wie die geforderte pseudo-zuf¨allige Aufteilungsfunktion realisiert und die von den
WF-Servern ben¨otigte Information bereitgestellt werden kann. In Abschnitt 4 wird dann diskutiert,
wie zus¨atzlich die Anforderung 5 ( ¨
Anderbarkeit der Lastaufteilung) erf¨ullt werden kann.
8
3.4.1 Realisierung der Aufteilungsfunktion
Bei dem Verfahren wird ein instanzspezifisches Datum der WF-Instanz Inst verwendet, um z.B. bei
einer Migration einen WF-Server des Zieldomains
auszuw¨ahlen. Diese Berechnung ¨ubernimmt
die domainspezifische Aufteilungsfunktion
'
Inst
Q
(siehe Algorithmus 1). Das unver¨anderliche in-
stanzspezifische Datum InstDat (z.B. die WF-ID) der WF-Instanz Inst wird mit Hilfe eines Pseudo-
Zufallszahlengerators auf einen Wert
L
im Intervall
M NOPAQ
abgebildet. Die Funktion
ZL<Q
bildet die-
sen Wert
L
auf einen Server
des Domains
ab. Durch die Wahl dieser Funktion
Z
l¨asst sich die
Lastverteilung auf die WF-Server steuern. Da ein Pseudo-Zufallszahlengerator ausgehend vom sel-
ben Startwert InstDat stets dasselbe Ergebnis
L
berechnet, ergibt sich f¨ur eine WF-Instanz Inst stets
derselbe WF-Server
im Domain
.
Algorithmus 1 (Berechnung der Aufteilungsfunktion
Inst
)
input
Inst: WF-Instanz, f¨ur die der WF-Server ermittelt werden soll
: Domain, aus dem ein WF-Server gew¨ahlt werden soll
result
logische Server-ID des f¨ur die WF-Instanz Inst ausgew¨ahlten WF-Servers aus dem Domain
begin
InstDat
4]4';'V
4¡<¢¤£
Inst
¥
;
>¦§;¨ ©V4]§;¨Y¢¤£
InstDat
¥
;
Funktion
ª«£)D¥
definiert durch
4ª ¬®Dª¯D°]¬
und
¬
®
¯
:
case
²±¤³ ´µ ª¬ ¥~¶
return
¬
;
case
²±¤³ ª¬·µ ª¸ ¥d¶
return
¸
;
...
case
²±¤³ ª¯D°]¬ µ¹¥~¶
return
¯
;
end.
Die Wahrscheinlichkeit f¨ur die Auswahl des WF-Servers
durch den Algorithmus 1 entspricht
der L¨ange des zugeh¨origen Intervalls
M º 9»:¼ O½º Q
. Dieser Aussage liegt die Annahme zugrunde, dass
die Werte von
L
¨uber
M NOPAQ
gleichverteilt sind. Dies kann durch den Einsatz eines ”guten“ Pseudo-
Zufallszahlengenerators bei der Berechnung der Funktion
¾¿4ÀVÁ¿Âà Äź<HÆÂÃ4Ç
erreicht werden. In Al-
gorithmus 1 kann als instanzspezifisches Datum die z.B. die ID der WF-Instanz verwendet werden.
Stattdessen kann auch die Startzeit der WF-Instanz (oder ein speziell f¨ur diesen Zweck generierter Zu-
fallswert) gew¨ahlt werden. Wird z.B. von der Startzeit nur der Wert f¨ur die Millisekunden als InstDat
verwendet, so ist es realistisch anzunehmen, dass die Werte von InstDat gleichm¨aßig ¨uber das In-
tervall
M NOPVNÅNÅNQ
verteilt sind. Deshalb ist in diesem Fall die Funktion
¾¿;ÀÁ&Â<à ÄźHÆÂ<Ã4ÇS
InstDat
QÉÈËÊ
InstDat
Ì'PVNÅNÅN
ausreichend, um eine Gleichverteilung von
L
¨uber
M NOPAQ
zu erreichen.
3.4.2 Verteilung der ben¨
otigten Information
Beim Start von WF-Instanzen und bei deren Migration muss entschieden werden k¨onnen, welcher
Server
des Domains
f¨ur die WF-Instanz Inst verwendet werden soll. Dazu muss die Funktion
'²
Inst
Q
allen WF-Servern des WfMS bekannt sein. Diese Funktion berechnet eine logische Server-
ID, die mit einer anderen Funktion
Íu¡4Q
auf eine physische Rechneradresse (z.B. IP-Adresse) abge-
bildet wird. Auch
Íu¡4Q
muss allen Servern bekannt sein. Da diese beiden Funktionen selten ge¨andert
werden, werden sie auf allen WF-Servern repliziert (¨ahnlich wie die WF-Vorlagen). Aspekte, welche
die ¨
Anderung dieser Funktionen betreffen, werden im n¨achsten Abschnitt diskutiert. Da solche ¨
Ande-
9
rungen eher selten auftreten, fallen die durch die Replikation entstehenden Kommunikationskosten
nicht ins Gewicht.
4¨
Anderung der Lastaufteilung
Das in Abschnitt 3.4 vorgestellte, pseudo-zuf¨allige Verfahren erf¨ullt die Anforderungen 1-4. In der
oben beschriebenen Form wird die Anforderung 5, dass die Aufteilung der Last ver¨anderbar sein
muss, noch nicht erf¨ullt. Dies ist aber notwendig, damit eine existierende ¨
Uberlastung behoben oder
eine Systemkonfiguration ver¨andert werden kann. Die Aufteilungsfunktion zu ver¨andern ist allerdings
nicht unproblematisch, weil eine WF-Instanz stets vom selben Server innerhalb eines Domain kontrol-
liert werden muss, um das in Abschnitt 3.3 beschriebene Problem beim Zusammenf¨uhren paralleler
Zweige zu vermeiden. Ung¨unstigerweise erfordert eine Ver¨anderung der Lastaufteilung jedoch eine
Ver¨anderung dieser Zuordnung. Im Folgenden wird untersucht, wie Server ausgetauscht, hinzugef¨ugt
und weggenommen werden k¨onnen und wie die Lastaufteilung ver¨andert werden kann, so dass die
Anforderung 5 erf¨ullt wird, ohne dadurch die Anforderungen 1-4 zu verletzen.
4.1 Physische Server austauschen
Soll der WF-Server mit der logischen ID
AUÎAϽ4ЮW
durch einen anderen ersetzt werden, so wird dieser
durch Algorithmus 2 zuerst gestartet. Nachdem die M¨oglichkeit zur Migration zu dem von der ¨
Ande-
rung betroffenen Server gesperrt wurde, wird die Abbildungsfunktion
Í¡DQ
der logischen Server-IDs
auf die Rechneradressen ver¨andert. Dann werden die WF-Instanzen, welche vom stillzulegenden Ser-
ver kontrolliert werden, zum neuen Server transportiert. Die neue Funktion
Í2Ñ
¼Ò
¡4Q
, welche die
bisher g¨ultige Funktion
ÍÑ
ÅÒ
¡DQ
ersetzt, wird repliziert, so dass sie jedem Server des WfMS bekannt
ist. Die ¨
Anderung der Funktion
Íu¡4Q
bewirkt, dass am alten WF-Server zuk¨unftig keine Migrationen
mehr eingehen. Jetzt k¨onnen die Sperren aufgehoben werden, so dass auch wieder Migrationen zum
Server
AUIÎϽ4ЮW
stattfinden k¨onnen. Schließlich kann der zu ersetzende Server gestoppt werden.
Algorithmus 2 (Austauschen eines WF-Servers)
input
Ó¡ÔYÕ
¯Ö×
: logische ID des Servers, welcher ersetzt werden soll
4§;©
: physische Adresse des Servers, welcher die logische ID
YÓ¡ÔYÕ
¯VÖ½×
erhalten soll
ÙØ
¯AÚ
£!Y¥
: bisherige Abbildungsfunktion logischer IDs von WF-Servern auf deren physische Adresse
begin
starte den neuen WF-Server
D§;©
;
sperre (bei allen WF-Servern) die Migrationen zum (bisherigen) Server
Ó¡ÔYÕ
¯VÖ½×
;
// ordne
Ó¡ÔÕ
¯VÖ½×
die neue Server-ID zu und ¨ubernehme die anderen Eintr¨age
ÙØ
¯AÛ&¬Ú
£9 Ó¡ÔÕ
¯VÖ½×
¥~¶ÜSD§A©
;
ÝÙÞS Ó¡ÔYÕ
¯VÖ½×
:
]Ø
¯Û&¬IÚ
£!Y¥~¶ßS]Ø
¯Ú
£9¥
;
transferiere alle WF-Instanzen vom Server
]Ø
¯Ú
£9 Ó¡ÔYÕ
¯Ö×
¥
zum Server
]Ø
¯Û&¬IÚ
£! Ó¡ÔYÕ
¯VÖ½×
¥
;
repliziere
]Ø
¯Û¿¬Ú
£9¥
an alle WF-Server;
gebe Migrationen zum WF-Server
YÓ¡ÔÕ
¯VÖ½×
wieder frei;
stoppe den zu deaktivierenden WF-Server
]Ø
¯Ú
£9YÓ¡ÔÕ
¯VÖ½×
¥
;
end.
Eigentlich m¨usste das Sperren, das Replizieren von
Í:Ñ
¼Ò
¡DQ
und das Freigeben der Sperren in einer
verteilten Transaktion stattfinden. Dadurch w¨aren aber Migrationen zum Server
;UÎϽ4ЮW
nichtm¨oglich,
solange die Transaktion nicht bei allen Servern beendet wurde. Der Server
;UÎÏ®;ÐW
w¨urde also durch
10
den Ausfall eines beteiligten Servers w¨ahrend der Ausf¨uhrung von Algorithmus 2 blockiert werden.
Außerdem w¨urde ein solches Vorgehen die Ausf¨uhrung eines teuren 2-Phasen-Commit-Protokolls er-
forderlich machen. Um diese Nachteile zuvermeiden, wird f¨ur den Algorithmus 2 und die nachfolgend
beschriebenen Algorithmen der folgende Trick verwendet: Die M¨oglichkeit zur Migration wird wei-
terhin bei allen WF-Servern gesperrt. Nach Ausf¨uhrung des entsprechenden ”Sperrbefehls“ k¨onnen
bei
AUIÎϽ4ЮW
also keine neuen Migrationen mehr eingehen. Die Replikation der Funktion
Í:Ñ
¼Ò
¡DQ
wird nun mit dem Freigeben der Sperre zu einer einzigen Transaktion zusammengefasst. Sobald nun
ein Server die neuen Daten erfolgreich (lokal) gespeichert hat, hebt er die Sperre f¨ur Migrationen zu
;UÎϽ4ЮW
auf, so dass Migrationen zu
;UÎÏ®;ЮW
(auf Basis der neuen Funktion) von ihm durchgef¨uhrt
werden k¨onnen. Durch diese Vorgehensweise wird zwar die Sperre nicht bei allen Servern gleich
lange gehalten, die M¨oglichkeit zur Migration ist aber entweder noch gesperrt oder es wird schon
die neue Funktion
Í:Ñ
¼Ò
¡DQ
verwendet. Deshalb k¨onnen keine Inkonsistenzen durch die Verwendung
der unterschiedlichen Funktionen
Í2Ñ
DÒ
¡DQ
und
Í2Ñ
¼Ò
¡4Q
entstehen. Der große Vorteil dieser Vorge-
hensweise ist, dass jeder WF-Server sofort nach der erfolgreichen (lokalen) Speicherung der Daten
wieder ohne Einschr¨ankung weiterarbeiten kann, auch wenn noch nicht alle Server die ¨
Anderung der
Abbildungsfunktion (z.B. wegen eines lokalen Systemausfalls) vollzogen haben.
4.2 Lastverteilung ¨
andern
Wenn zwar weiterhin dieselben WF-Server verwendet werden sollen, aber die Verteilung der Last zwi-
schen ihnen ge¨andert werden soll, so muss die bisher g¨ultige Aufteilungsfunktion
Ñ
DÒ
Inst
Q
durch eine
neue Aufteilungsfunktion
'
Ñ
¼Ò
Inst
Q
ersetzt werden. Durch diese Ver¨anderung k¨onnen Probleme
bei der Zusammenf¨uhrung paralleler Zweige einer WF-Instanz entstehen: Wenn einzelne Zweige ei-
ner WF-Instanz die alte Funktion verwenden und andere die neue, so kann es vorkommen, dass eine
WF-Instanz von verschiedenen WF-Servern eines Domains kontrolliert wird. Dies wollen wir jedoch
ausschließen, um Kommunikation zwischen WF-Servern desselben Domains zu vermeiden (Anfor-
derung 2). Zu diesem Zweck kann eines der folgenden Verfahren verwendet werden:
1. In Algorithmus 3 wird die neue Aufteilungsfunktion
Ñ
¼Ò
Inst
Q
des Domains
mit einem Zeit-
stempel
à
Ñ
¼Ò
versehen, der mit ihr repliziert wird. Die neue Funktion
Ñ
¼Ò
Inst
Q
wird dann
nur f¨ur WF-Instanzen Inst verwendet, f¨ur die gilt:
á~âºÄDâLÀVãIâ)¾Á&HK'âY
Inst
QåäæàF
Ñ
¼Ò
. W¨ahrend der
Algorithmus 3 ausgef¨uhrt wird, ist die M¨oglichkeit zur Migration in den Domain
gesperrt.
F¨ur WF-Instanzen, die nach dem Start von Algorithmus 3 erzeugt wurden, ist damit zum Zeit-
punkt einer etwaigen Migration in den Domain
die neue Funktion
'
Ñ
¼Ò
Inst
Q
und der zu-
geh¨orige Zeitstempel bekannt, so dass die Migration auch wirklich auf Basis der neuen Funktion
'
Ñ
¼Ò
Inst
Q
durchgef¨uhrt werden kann.
Algorithmus 3 (1. Verfahren zur ¨
Anderung von
Inst
)
input
: Domain, in dem die Lastaufteilung ver¨andert werden soll
ç
ª
Ø
¯Û&¬IÚ
£
Inst
¥
: neue Aufteilungsfunktion f¨ur den Domains
begin
sperre (bei allen WF-Servern) die Migrationen in den Domain
;
è
ª
Ø
¯Û&¬IÚ
é¡9¢êD£!¥
; // Zeitstempel auf die aktuelle Zeit setzen
repliziere
£
ç
ª
Ø
¯Û&¬IÚ
£
Inst
¥½µ
è
ª
Ø
¯Û¿¬Ú
¥
;
gebe Migrationen in den Domain
wieder frei;
end.
11
2. Bei dem in Algorithmus 4 dargestellten Verfahren wird die Menge
ë
Ñ
¼Ò
der IDs von WF-
Instanzen berechnet, die zur Zeit der ¨
Anderung in der Datenbank eines WF-Servers
des Do-
mains
gespeichert sind und f¨ur die sich durch die ¨
Anderung der WF-Server ¨andert. F¨ur eine
WF-Instanz Inst mit ID
Inst
Q¦ìë
Ñ
¼Ò
wird nicht die neue Funktion
Ñ
¼Ò
Inst
Q
verwendet,
sondern weiterhin die alte Funktion
'
Ñ
ÅÒ
Inst
Q
(bzw.
'
Ñ
<»:¼Ò
Inst
Q
, falls zus¨atzlich ID
Inst
Qåíë
Ñ
ÅÒ
gilt, usw.). Die Menge
ë
Ñ
¼Ò
enth¨alt also die IDs derjenigen WF-Instanzen, die zum Zeitpunkt
der ¨
Anderung von einem WF-Server des Domains
kontrolliert werden und f¨ur die sich durch
Ñ
¼Ò
der Server ¨andern w¨urde. F¨ur diese WF-Instanzen wird weiterhin die ”alte“ Aufteilungs-
funktion verwendet, so dass der entsprechende WF-Server alle parallelen Zweige kontrolliert.
Deshalb entsteht f¨ur diese Instanzen kein Problem beim Zusammenf¨uhren paralleler Zweige. F¨ur
alle anderen WF-Instanzen (ID
Inst
Qïî.ë
Ñ
¼Ò
) wird ausschließlich die ”neue“ Funktion
Ñ
¼Ò
verwendet, so dass auch hier kein Problem auftreten kann.
Algorithmus 4 (2. Verfahren zur ¨
Anderung von
Inst
)
input
: Domain, in dem die Lastaufteilung ver¨andert werden soll
ç
ª
Ø
¯Û&¬IÚ
£
Inst
¥
: neue Aufteilungsfunktion des Domains
ª
: Menge der WF-Server des Domains
begin
sperre (bei allen WF-Servern) die Migrationen in den Domain
;
activeWFs
XðFñò;óAôuõ
Inst
ö
WF-Instanz Inst ist am WF-Server
aktiv
÷
;
// im Domain
aktive WF-Instanzen, f¨ur die sich der Server ver¨andern w¨urde:
ø
ª
Ø
¯Û¿¬Ú
æõ
ID
£
Inst
¥uö
Inst
±
activeWFs
ùú:©YûD© ª£
Inst
¥üÞ
ç
ª
Ø
¯AÛ&¬Ú
£
Inst
¥÷
;
repliziere
£
ç
ª
Ø
¯Û&¬IÚ
£
Inst
¥½µ
ø
ª
Ø
¯Û&¬IÚ
¥
;
gebe Migrationen in den Domains
wieder frei;
end.
Der Vorteil des ersten Verfahrens ist, dass es einen sehr geringen Aufwand erfordert. Allerdings wird
die neue Funktion
'
Ñ
¼Ò
Inst
Q
erst dann f¨ur alle WF-Instanzen verwendet, wenn keine WF-Instanzen
mehr existieren, die ¨alter als diese Funktion sind. Da WF-Instanzen h¨aufig mehrere Wochen laufen,
kann es entsprechend lange dauern, bis die neu eingestellte Lastverteilung tats¨achlich erreicht wird.
Das zweite Verfahren erfordert wegen der Berechnung und Replikation von
ë
Ñ
¼Ò
einen wesentlich
gr¨oßeren Aufwand als das erste Verfahren. Es hat aber den Vorteil, dass auch f¨ur schon lange lau-
fende WF-Instanzen der Migrationszielserver auf Basis der neuen Aufteilungsfunktion ermittelt wird.
Welches der beiden Verfahren besser geeignet ist, ist von der jeweiligen Situation abh¨angig. Soll die
Lastaufteilung lediglich l¨angerfristig angepasst werden, so ist die 1. Variante ausreichend. Sollen aber
die Auswirkungen der ¨
Anderung m¨oglichst ab sofort beobachtet und bewertet werden, so ist die lange
Verz¨ogerung nicht akzeptabel. Dann muss die 2. Variante verwendet werden. Die dabei entstehenden
Kosten relativieren sich, da Ver¨anderungen der Lastaufteilung i.d.R. doch eher selten sind.
4.3 Anzahl der Server eines Domains erh¨
ohen
Soll die Anzahl der WF-Server eines Domains
erh¨oht werden, so muss eine neue logische Server-ID
4Wý
definiert werden. Nachdem der Algorithmus 5 den neuen WF-Server gestartet hat, wird dessen
logische ID
4Wý
auf dessen physische Adresse
º'Â/Ä DWIý
abgebildet. Dies geschieht durch die ¨
Ande-
rung und Replikation der Funktion
Íu¡4Q
. F¨ur diesen Vorgang sind keine Sperren erforderlich, weil
4Wý
noch kein Intervall der Aufteilungsfunktion
Inst
Q
zugeordnet ist; der Server
4Wý
wird also
12
¨uberhaupt noch nicht verwendet. Damit er jedoch in Zukunft WF-Instanzen kontrollieren kann, muss
zus¨atzlich die Funktion
Inst
Q
, wie im vorherigen Abschnitt beschrieben, ge¨andert werden. Dem
neuen WF-Server muss also ein Intervall der Aufteilungsfunktion zugeordnet werden.
Algorithmus 5 (Neuen WF-Server einf¨uhren)
input
¯;סþ
: logische ID des neuen WF-Servers
4§;©
¯;סþ
: physische Adresse des neuen Servers
ÙØ
¯AÚ
£!Y¥
: aktuelle Funktion, die logische Server-IDs auf physische Server-Adressen abbildet
ç
ª
Ø
¯ÿ Û¿¬Ú
£
Inst
¥
: neue Aufteilungsfunktion des Domains
, in der auch
¯Aסþ
ber¨ucksichtigt wird
begin
starte den WF-Server
D§;©
¯A×þ
;
ÙØ
¯AÛ&¬Ú
£9
¯Aסþ
¥ ¶ß.D§A©
¯Aסþ
;
ÝÙÞS
¯Aסþ
:
]Ø
¯Û&¬IÚ
£!Y¥~¶ßS]Ø
¯Ú
£9¥
;
repliziere
]Ø
¯Û¿¬Ú
£9¥
;
¨andere
ç
ª
Ø
¯
ÿ
Ú
£
Inst
¥
in
ç
ª
Ø
¯
ÿ
Û&¬Ú
£
Inst
¥
mit Algorithmus 3 oder 4;
end.
4.4 Anzahl der Server eines Domains reduzieren
Wenn die Anzahl der WF-Server des Domains
verringert werden soll, so verhindert der Algorith-
mus 6 zuerst durch eine Sperre weitere Migrationen zu dem stillzulegenden Server
;
. Dann werden
alle bei ihm vorhandenen WF-Instanzen zu dem Server
4Wý
transferiert, welcher dessen Aufgaben
(vorl¨aufig) ¨ubernimmt. Damit zuk¨unftig keine Migrationen an dem stillzulegenden Server mehr ein-
gehen, wird die logische Server-ID
;
auf die physische Adresse des ¨ubernehmenden WF-Servers
”umgelenkt“, indem die Funktion
Í¡DQ
ver¨andert wird. Nun wird die neue Funktion
ÍÑ
¼Ò
¡DQ
re-
pliziert und die Sperren werden freigegeben. Da der stillzulegende Server keine WF-Instanzen mehr
kontrolliert und auch keine Migrationen mehr bei ihm eingehen k¨onnen, wird er gestoppt. Um auch die
logische ID des stillgelegten Servers auslaufen zu lassen, sollte nach Beendigung von Algorithmus 6
mit den Verfahren aus Abschnitt 4.2 die Aufteilungsfunktion
Inst
Q
so ver¨andert werden, dass
;
kein Intervall mehr zugeordnet ist. Im Zuge dieser Ver¨anderung kann zus¨atzlich die bisher von
;
bew¨altigte Last geeignet auf andere WF-Server verteilt werden, indem die Intervalle entsprechend
angepasst werden.
Algorithmus 6 (WF-Server stilllegen)
input
: logische ID des stillzulegenden WF-Servers
¯;סþ
: logische ID des Servers, der die Aufgaben von
¨ubernehmen soll
ÙØ
¯AÚ
£!Y¥
: aktuelle Funktion, die logische Server-IDs auf physische Server-Adressen abbildet
begin
sperre (bei allen WF-Servern) die Migrationen zum Server
;
ÙØ
¯AÛ&¬Ú
£9
¥~¶ßS]Ø
¯Ú
£9
¯Aסþ
¥
;
ÝÙÞS
:
]Ø
¯Û¿¬Ú
£9¥~¶ßXÙØ
¯AÚ
£!Y¥
;
transferiere alle WF-Instanzen vom Server
]Ø
¯Ú
£9
¥
zum Server
ÙØ
¯AÚ
£!
¯Aסþ
¥
;
repliziere
]Ø
¯Û¿¬Ú
£9¥
;
gebe Migrationen zum WF-Server
wieder frei;
stoppe den WF-Server
ÙØ
¯Ú
£!
¥
;
end.
Wie wir gesehen haben, ist es also nicht nur m¨oglich, die Aufteilungsfunktion der WF-Instanzen auf
die WF-Server effizient und mit guten statistischen Eigenschaften zu realisieren, sie kann außerdem
13
im laufenden Betrieb beliebig ver¨andert werden. Damit erf¨ullt das oben beschriebene Verfahren nicht
nur – wie schon in Abschnitt 3 festgestellt wurde – die Anforderungen 1-4, sondern zus¨atzlich auch
die Anforderung 5 aus Abschnitt 1.2.
5 Diskussion
Unseres Wissens gibt es bisher keine Arbeiten, die sich mit dem Problem der ¨
Uberlastung des WF-
Servers eines Domains befassen. Der vorliegende Beitrag untersucht also erstmalig die durch die Ver-
wendung mehrerer WF-Server innerhalb desselben Domains resultierenden Probleme und die Frage-
stellung, wie dann ein geeigneter Server ausgew¨ahlt werden kann. Der nun folgende Abschnitt bietet
einen kurzen ¨
Uberblick ¨uber Verteilungsmodelle f¨ur WfMS. Eine detaillierte Diskussion zu diesem
Thema findet sich in [BD98, BD99b]. Außerdem wird nun diskutiert, wie das vorgestellte Verfahren
bei verschiedenen Verteilungsstrategien eingesetzt werden kann.
Einige Forschungsprototypen, die sich nicht prim¨ar um Skalierbarkeit k¨ummern (z.B. Panta Rhei
[EG96], WASA [WHKS98]), und die meisten kommerziellen Systeme verwenden einen zentralen
WF-Server. Da dieser einen potentiellen Flaschenhals darstellt, k¨onnen solche WfMS nicht als ska-
lierbar bezeichnet werden. Bei voll verteilten Ans¨atzen (z.B. Exotica/FMQM [AMG
95] und INCAS
[BMR96]) ¨ubernimmt der Rechner jedes Benutzers Serverfunktionalit¨at. Da es keine WF-Server im
eigentlichen Sinn gibt, bei denen sich die Last konzentriert, k¨onnen auch keine WF-Server ¨uberlastet
werden. Deshalb besteht keine Notwendigkeit f¨ur die Verwendung des vorgestellten Verfahrens. Im
Exotica-Projekt wurde ein Ansatz entwickelt, bei dem der WF-Server (Cluster) f¨ur eine WF-Instanz
bei deren Start zuf¨allig ausgew¨ahlt wird [AKA
94]. In diesem Cluster verbleibt der WF f¨ur seine
gesamte Laufzeit, es gibt also keine Migrationen. Dies entspricht einem zentralen Ansatz mit repli-
ziertem WF-Server. Die Serverwahl findet zuf¨allig statt (vgl. Abschnitt 3.3). Da eine WF-Instanz den
Cluster nie wechselt, treten keine Probleme bei der Zusammenf¨uhrung paralleler Zweige auf, so dass
die zuf¨allige Serverwahl ausreichend ist.
Bei zahlreichen Ans¨atzen werden wie bei ADEPT mehrere WF-Server verwendet, wobei ebenfalls der
Wechsel des Servers m¨oglich ist. In MENTOR [MWW
98] und WIDE [CGS97] wird der WF-Server
nahe bei den potentiellen Bearbeitern der Aktivit¨at allokiert; bei METEOR
[DKM
97], CodAlf und
BPAFrame (beide [SM96]) liegt er nahe bei der zur Aktivit¨at geh¨orenden Anwendung. Bei all diesen
Ans¨atzen kann ein WF-Server ¨uberlastet sein. Mit dem vorgestellten pseudo-zuf¨alligen Verfahren
w¨are es m¨oglich, ihn zu replizieren und die Last auf die Replikate zu verteilen.
In MOBILE [HS96] werden verschiedene WF-Typen von unterschiedlichen WF-Servern kontrolliert.
Migrationen sind nicht vorgesehen. Allerdings k¨onnen Subprozesse von einem anderen WF-Server
kontrolliert werden [SNS99]. Dieser wird zur Laufzeit aufgrund verschiedener Kriterien (z.B. Rechte,
Gewichte) ausgew¨ahlt. Auch bei diesem Ansatz k¨onnen WF-Server ¨uberlastet sein, so dass die vorge-
stellten Verfahren angewendet werden k¨onnen. Aufgrund der ”Subprozess-Semantik“ werden paral-
lele Zweige stets auf dem WF-Server zusammengef¨uhrt, auf dem sie sich aufgeteilt haben. Da deshalb
das in Abschnitt 3.3 geschilderte Problem beim Zusammenf¨uhren paralleler Zweige nicht auftreten
kann, ist das Verfahren mit zuf¨alliger Serverwahl v¨ollig ausreichend.
Die Anwendung des vorgestellten Verfahrens ist also nicht auf ADEPT beschr¨ankt. Zahlreiche andere
Ans¨atze k¨onnen auch von ihm profitieren. Dabei gen¨ugt f¨ur Ans¨atze ohne Migrationen eine zuf¨allige
Serverwahl; ansonsten ist (wie bei ADEPT
) die pseudo-zuf¨allige Variante am besten geeig-
net.
14
6 Zusammenfassung und Ausblick
Die zahlreichen Aufgaben eines WF-Servers k¨onnen zu dessen ¨
Uberlastung f¨uhren. Um dies zu ver-
hindern, kann ein WF-Server repliziert und die Last zwischen den entstehenden Replikaten aufgeteilt
werden. In diesem Beitrag wurde ein Verfahren vorgestellt, bei dem f¨ur eine WF-Instanz pseudo-
zuf¨allig ein WF-Server ausgew¨ahlt wird. Dieses Verfahren realisiert eine Art ”Hashing“ der WF-
Instanzen auf die WF-Server eines Domains. Es erm¨oglicht eine beliebige Aufteilung der Last zwi-
schen den WF-Servern, generiert im wesentlichen keine zus¨atzliche Kommunikation und erfordert nur
sehr wenig Rechenaufwand. Weiter wurde gezeigt, wie es m¨oglich ist, die Lastaufteilung zwischen
den WF-Servern im laufenden Betrieb zu ver¨andern. Damit ist das Problem der ¨
Uberlastung der WF-
Server gel¨ost, so dass eine Konzentration auf den Kommunikationsaspekt m¨oglich ist, d.h. auf die
geeignete Auswahl des Domains f¨ur eine Aktivit¨at. Da bei der Modellierung nur Domains – und nicht
konkrete Rechner – vorgegeben werden, k¨onnen die verschiedenen WF-Server eines Domains als ein
einziger leistungsstarker Server betrachtet werden (”virtual powerful server“).
In diesem Beitrag wurde auch die Anwendbarkeit lastabh¨angiger Verfahren zur Serverauswahl unter-
sucht. Diese haben zwar im Allgemeinen Nachteile gegen¨uber dem pseudo-zuf¨alligen Verfahren, sind
aber evtl. f¨ur bestimmte Spezialanwendungen interessant. Eine vertiefte Untersuchung dieser Verfah-
ren bietet sich vor allem an, wenn die verf¨ugbare Leistung der WF-Server stark schwankt, wenn der
Ausfall von WF-Servern durch dieses Verfahren kompensiert werden soll, oder wenn ein WF-Server
nur sehr wenige WF-Instanzen gleichzeitig kontrollieren kann, so dass schon kleine Ungleichvertei-
lungen, wie sie beim pseudo-zuf¨allige Verfahren entstehen k¨onnen, zu Problemen f¨uhren w¨urden.
F¨ur große WF-Anwendungen, die operativ eingesetzt werden, ist aber das vorgestellte Verfahren den
lastabh¨angigen Verfahren vorzuziehen.
Danksagung: Wir danken unseren Kollegen Manfred Reichert und Clemens Hensinger f¨ur ihre hilfreichen
Anregungen.
Literatur
[AKA
94] G. Alonso, M. Kamath, D. Agrawal, A. El Abbadi, R. G¨unth¨or und C. Mohan: Failure
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: Exo-
tica/FMQM: A Persistent Message-Based Architecture for Distributed Workflow Ma-
nagement. In: Proc. IFIP Working Conf. on Information Systems for Decentralized
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.
[BD98] T. Bauer und P. Dadam: Architekturen f¨
ur skalierbare Workflow-Management-Systeme –
Klassifikation und Analyse. Ulmer Informatik-Berichte 98-02, Universit¨at Ulm, Fakult¨at
f¨ur Informatik, Januar 1998.
15
[BD99a] T. Bauer und P. Dadam: Efficient Distributed Control of Enterprise-Wide and Cross-
Enterprise Workflows. In: Proc. Workshop Enterprise-wide and Cross-enterprise Work-
flow Management: Concepts, Systems, Applications, 29. Jahrestagung der GI, S. 25–32,
Paderborn, Oktober 1999.
[BD99b] T. Bauer und P. Dadam: Verteilungsmodelle f¨
ur Workflow-Management-Systeme – Klas-
sifikation und Simulation. Informatik Forschung und Entwicklung, 14(4):203–217, De-
zember 1999.
[BD00] T. Bauer und P. Dadam: Efficient Distributed Workflow Management Based on Variable
Server Assignments. In: Proc. 12th Conf. on Advanced Information Systems Enginee-
ring, S. 94–109, Stockholm, Juni 2000.
[BMR96] D. Barbar´a, S. Mehrotra und M. Rusinkiewicz: INCAs: Managing Dynamic Workflows
in Distributed Environments. Journal of Database Management, Special Issue on Mul-
tidatabases, 7(1):5–15, 1996.
[CGS97] S. Ceri, P. Grefen und G. S´anchez: WIDE – A Distributed Architecture for Workflow
Management. In: Proc. 7th Int. Workshop on Research Issues in Data Engineering,
Birmingham, April 1997.
[DKM
97] S. Das, K. Kochut, J. Miller, A. Sheth und D. Worah: ORBWork: A Reliable Distributed
CORBA-based Workflow Enactment System for METEOR
. Technical Report #UGA-
CS-TR-97-001, Department of Computer Science, University of Georgia, Februar 1997.
[DKR
95] P. Dadam, K. Kuhn, M. Reichert, T. Beuter und M. Nathe: ADEPT: Ein integrierender
Ansatz zur Entwicklung flexibler, zuverl¨
assiger kooperierender Assistenzsysteme in kli-
nischen Anwendungsumgebungen. In: Proc. GI/SI-Jahrestagung, S. 677–686, Zurich,
September 1995.
[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.
[EG96] J. Eder und H. Groiss: Ein Workflow-Managementsystem auf der Basis aktiver Daten-
banken. In: J. Becker, G. Vossen (Herausgeber): Gesch¨
aftsprozeßmodellierung und
Workflow-Management. Int. Thomson Publishing, 1996.
[Gos91] A. Goscinski: Distributed Operating Systems: The Logical Design. Addison-Wesley,
1991.
[HS96] P. Heinl und H. Schuster: Towards a Highly Scaleable Architecture for Workflow Mana-
gement Systems. In: Proc. 7th Int. Workshop on Database and Expert Systems Applica-
tions, S. 439–444, Zurich, September 1996.
[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.
16
[MWW
98] P. Muth, D. Wodtke, J. Weißenfels, A. Kotz-Dittrich und G. Weikum: From Centralized
Workflow Specification to Distributed Workflow Execution. Journal of Intelligent In-
formation Systems, Special Issue on Workflow Management Systems, 10(2):159–184,
M¨arz/April 1998.
[RBD99] M. Reichert, T. Bauer und P. Dadam: Enterprise-Wide and Cross-Enterprise Workflow-
Management: Challenges and Research Issues for Adaptive Workflows. In: Proc. Work-
shop 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
W
– Supporting Dynamic Changes of Workflows
Without Losing Control. Journal of Intelligent Information Systems, Special Issue on
Workflow Management Systems, 10(2):93–129, M¨arz/April 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, Istan-
bul, 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 Activities
Coordination and Collaboration, San Francisco, Februar 1999.
[WHKS98] M. Weske, J. H¨undling, D. Kuropka und H. Schuschel: Objektorientierter Entwurf ei-
nes flexiblen Workflow-Management-Systems. Informatik Forschung und Entwicklung,
13(4):179–195, 1998.
17
