Effiziente Übertragung von Prozessinstanzdaten in verteilten Workflow-Management-Systemen [original]

Informatik Forsch. Entw. (2001) 16: 76–92

Springer-Verlag 2001

Effiziente ¨

Ubertragung von Prozessinstanzdaten

in verteilten Workflow-Management-Systemen

Thomas Bauer, Manfred Reichert, Peter Dadam

Universit¨

at Ulm, Abteilung Datenbanken und Informationssysteme, D-89069 Ulm

(e-mail: {bauer, reichert, dadam}@informatik.uni-ulm.de, http://www.informatik.uni-ulm.de/dbis)

Eingegangen am 22. Juni 2000 / Angenommen am 25. Januar 2001

Zusammenfassung. Zur Unterst¨

utzung von unternehmens-

weiten und -¨

ubergreifenden Gesch¨

aftsprozessen muss ein

Workflow-Management-System (WfMS) eine große Anzahl

von Workflow-Instanzen steuern k¨

onnen. Daraus resultiert

eine hohe Last f¨

ur die Workflow-Server und das zugrunde

liegende Kommunikationssystem. Ein in der Workflow-Lite-

ratur viel diskutierter Ansatz zur Bew¨

altigung der Last ist es,

die Workflow-Instanzen verteilt durch mehrere Workflow-

Server zu kontrollieren. Beim Wechsel der Kontrolle zwi-

schen zwei Workflow-Servern werden dann Migrationen not-

wendig, bei denen Daten der jeweiligen Workflow-Instanz

vom Quell- zum Zielserver ¨

ubertragen werden m¨

ussen, um

dort mit der Steuerung fortfahren zu k¨

onnen. Deshalb be-

lasten Migrationen das Kommunikationssystem zus¨

atzlich.

In diesem Beitrag werden Verfahren entwickelt, mit denen

die bei Migrationen entstehende Kommunikationslast redu-

ziert werden kann, so dass die Skalierbarkeit des WfMS si-

gnifikant verbessert wird. Falls Gesch¨

aftsbereiche aus Kos-

tengr¨

unden nur ¨

uber langsame Kommunikationsverbindun-

gen angebunden sind, wird dadurch der Einsatz eines WfMS

uberhaupt erst erm¨

oglicht.

Schl¨

usselw¨

orter: Workflow-Management, verteilte Ausf¨

uh-

rung, Skalierbarkeit, Migration, Kommunikationskosten

Abstract. For the support of enterprise-wide and cross-

enterprise business processes, a workflow management sys-

tem (WfMS) must be able to control a large number of work-

flow instances. This, in turn, results in a very high load for

the workflow servers as well as for the underlying commu-

nication network. To cope with this load, in the workflow

literature, several approaches suggest to control workflow in-

stances piecewise by multiple, distributed workflow servers.

When transferring the control from one server of a workflow

instance to another, a migration becomes necessary. During

such a migration, data of the corresponding workflow in-

stance have to be transmitted from the source to the target

server. Afterwards, the target server may continue with the

control. Although very advantageous for many applications,

migrations themselves burden the communication network.

In this paper, methods are presented, which allow to reduce

the communication load caused by migrations and which,

therefore, contribute to improve the scalability of the WfMS

significantly. If business units are only connected by a com-

munication network with a low bandwidth (e.g., due to cost

reasons), such an approach is a prerequisite for the broad

usage of a WfMS.

Keywords: workflow management, distributed execution,

scalability, migration, communication costs

CR Subject Classification: H.4.1, H.1.0, C.2.4

1 Einleitung

WfMS erm¨

oglichen die rechnerunterst¨

utzte Ausf¨

uhrung von

Arbeitsabl¨

aufen (engl. Workflows) in einer verteilten Sys-

temumgebung. Ein entscheidender Vorteil des Einsatzes von

WfMS ist, dass sie helfen, große Anwendungssysteme ¨

uber-

schaubarer zu gestalten. Dazu wird der applikationsspezifi-

sche Code der Anwendungen, die zur Ausf¨

uhrung einzel-

ner Prozessschritte verwendet werden, von der Definition

und Steuerung der Ablauflogik des Gesch¨

aftsprozesses ge-

trennt. Anstelle eines großen monolithischen Programmpa-

kets erh¨

alt man einzelne Aktivit¨

aten, welche die Anwen-

dungsprogramme repr¨

asentieren. Ihre Ablauflogik wird in

einer separaten Kontrollflussdefinition festgelegt, welche die

Ausf¨

uhrungsreihenfolgen und -bedingungen der einzelnen

Aktivit¨

aten vorgibt. Zur Ausf¨

uhrungszeit sorgt das WfMS

daf¨

ur, dass diese Aktivit¨

aten entsprechend der festgelegten

Ablauflogik zur Bearbeitung kommen.

Bei unternehmensweiten und -¨

ubergreifenden prozessori-

entierten Anwendungssystemen entsteht wegen der großen

Benutzerzahl eine hohe Last f¨

ur das WfMS.1Um diese

bew¨

altigen zu k¨

onnen, erfolgt bei vielen Ans¨

atzen (z.B.

[AKA+94, CGP+96, DKM+97, Jab97, MWW+98, SM96])

eine Aufteilung auf mehrere Workflow-Server. Dabei kann

eine Workflow-Instanz (abschnittsweise) von verschiedenen

Workflow-Servern gesteuert werden, d.h. die Kontrolle ¨

uber

1In [KAGM96, SK97] werden Anwendungen beschrieben, bei denen die

Zahl der Benutzer des WfMS bis auf einige zehntausend anwachsen kann

oder mehrere zehntausend Workflow-Instanzen gleichzeitig im System sein

k¨

onnen. ¨

Ahnliches gilt auch f¨

ur E-Business-Anwendungen.

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 77

sie wechselt zur Ausf¨

uhrungszeit zwischen den Servern. Ein

solcher Wechsel erfordert eine sog. Migration, bei der die

bei der Ausf¨

uhrung der Workflow-Instanz erzeugten Daten2

an den Zielserver ¨

ubertragen werden, bevor dort mit der

Kontrolle fortgefahren wird. Dadurch kann bei verteilter

Workflow-Steuerung dasselbe logische Verhalten wie im

zentralen Fall erreicht werden, obwohl mehrere Workflow-

Server nacheinander oder gleichzeitig an der Ausf¨

uhrung ei-

ner Workflow-Instanz beteiligt sind. Bei den meisten in der

Literatur diskutierten Ans¨

atze werden bei einer solchen Mi-

gration alle Laufzeitdaten der Workflow-Instanz zum Ziel-

server transferiert. Dies f¨

uhrt im Allgemeinen aber zu einer

redundanten ¨

Ubertragung von Daten. So kann der Zielser-

ver einer Migration bereits fr¨

uher einmal an der Ausf¨

uh-

rung beteiligt gewesen sein, so dass ihm gewisse Instanzda-

ten schon bekannt sind. In diesem Fall ist es unn¨

otig, be-

reits vorhandene Daten nochmals zu ¨

ubertragen. In diesem

Beitrag werden zur Ausf¨

uhrungszeit der Workflow-Instanzen

zur Anwendung kommende Verfahren vorgestellt, die solche

und ¨

ahnliche F¨

alle ausschließen, wodurch das Kommunika-

tionsaufkommen bei Migrationen reduziert wird. Die Aus-

nutzung des existierenden Optimierungspotenzials ist insbe-

sondere f¨

ur unternehmensweite und -¨

ubergreifende Anwen-

dungen unverzichtbar, da bei den entsprechenden Systemen

die Kommunikation h¨

aufig (zumindest teilweise) ¨

uber ein

WAN (Wide Area Network) oder eine sonstige langsame

Verbindung (Internet, ISDN) abgewickelt wird. Auch bei

Workflow-Anwendungen mit mobilen Benutzern sind sol-

che Optimierungen essentiell, da die Kommunikation hier

h¨

aufig ¨

uber Modems oder Mobiltelefone erfolgt. Dennoch

gibt es unseres Wissens bisher keine Arbeiten, die systema-

tisch untersuchen, wie Migrationen effizient realisiert werden

k¨

onnen.

Die Verbesserung der Skalierbarkeit von WfMS ist aber

nur eine von vielen Anforderungen, die sich im unterneh-

mensweiten Einsatz stellen. Um WfMS f¨

ur ein breites Spek-

trum von Anwendungen einsetzbar zu machen, m¨

ussen wei-

tere fortschrittliche Workflow-Konzepte unterst¨

utzt werden.

Zu diesen z¨

ahlen unter anderen:

–die dynamische Ab¨

anderbarkeit laufender Workflows

(z.B. das Einf¨

ugen von Aktivit¨

aten) [KDB98, RD98]

–die Spezifikation und ¨

Uberwachung von Zeitbedingun-

gen (z.B. zeitliche Minimal- und Maximalabst¨

ande zwi-

schen Aktivit¨

aten garantieren) [MO99, Gri97]

–das (partielle) Zur¨

ucksetzen von Workflows [Ley97,

RD98]

–die Verwendung komplexer (abh¨

angiger) Bearbeiterzu-

ordnungen [BF99, Kub98]

Um solche fortschrittlichen Konzepte realisieren zu k¨

onnen,

darf die verteilte Workflow-Steuerung nicht isoliert betrach-

tet werden. Beispielsweise m¨

ussen zur Unterst¨

utzung dieser

Konzepte bei Migrationen gewisse Informationen ¨

uber been-

dete Aktivit¨

aten ¨

ubertragen werden. Bei der Entwicklung der

in dieser Arbeit vorgestellten Verfahren wird deshalb darauf

geachtet, dass diese mit den gestellten Anforderungen ver-

einbar sind.

2Wir nehmen im Folgenden an, dass das Workflow-Schema vollst¨

andig

auf all denjenigen Servern repliziert wird, die potenziell an der Ausf¨

uhrung

einer entsprechenden Instanz beteiligt sein k¨

onnen.

Im nachfolgenden Abschnitt werden grundlegende As-

pekte der zentralen und verteilten Workflow-Steuerung er¨

or-

tert. Außerdem werden die Problemstellungen untersucht,

die sich im Zusammenhang mit der effizienten Realisierung

von Migrationen ergeben. In Abschnitt 3 werden m¨

ogliche

Vorgehensweisen zur Migration von Workflow-Kontrollda-

ten (z.B. Information zum Status einer Workflow-Instanz)

vorgestellt und ein geeignetes Verfahren n¨

aher untersucht.

Dabei m¨

ogliche weitergehende Optimierungen werden im

Abschnitt 4 diskutiert. Die Migration der von Workflow-Ak-

tivit¨

aten gelesenen bzw. geschriebenen Parameterdaten wird

in Abschnitt 5 betrachtet. In Abschnitt 6 wird die Effek-

tivit¨

at der vorgestellten Verfahren durch ein Zahlenbeispiel

belegt. Abschnitt 7 diskutiert verwandte Ans¨

atze. Der Bei-

trag schließt mit einer Zusammenfassung.

2 Grundlagen und Problemstellung

In diesem Abschnitt fassen wir kurz einige f¨

ur das wei-

tere Verst¨

andnis des Beitrags relevante Grundlagen zusam-

men. So werden das im Folgenden verwendete Workflow-

Metamodell und die verteilte Workflow-Ausf¨

uhrung vorge-

stellt. Danach untersuchen wir detailliert die im Zusammen-

hang mit der effizienten Verwirklichung von Migrationen zu

l¨

osenden Problemstellungen.

2.1 Das Workflow-Metamodell

Um einen Arbeitsprozess zu spezifizieren, wird in einem

WfMS ¨

ublicherweise ein Workflow-Schema modelliert (obe-

rer Teil von Abb.1). Ein solches Schema legt die Ausf¨

uh-

rungsreihenfolge und -bedingungen (Kontrollfluss) der ein-

zelnen Prozessschritte (Aktivit¨

aten) fest. Bei vielen WfMS

kann dar¨

uber hinaus auch der Datenfluss zwischen den Ak-

tivit¨

aten definiert werden. Aus Abb.1 zum Beispiel ist er-

sichtlich, welche Aktivit¨

aten die Prozessvariable d1lesen

bzw. schreiben. F¨

ur einzelne Aktivit¨

aten wird festgelegt, ob

sie automatisch gestartet oder manuell bearbeitet werden

sollen. F¨

ur manuelle Aktivit¨

aten muss zur Modellierungs-

zeit zus¨

atzlich eine Bearbeiterzuordnung angegeben wer-

den, welche die zur Bearbeitung der Aktivit¨

at berechtigten

Benutzer festlegt. Eine solche Bearbeiterzuordnung spezifi-

ziert ¨

ublicherweise die Rolle, die potenzielle Bearbeiter ein-

nehmen, oder die Organisationseinheit, der sie angeh¨

oren

sollen. Es sind aber auch komplexere Ausdr¨

ucke m¨

oglich.

Ausgehend von einem solchen Workflow-Schema k¨

onnen

zur Ausf¨

uhrungszeit Workflow-Instanzen erzeugt werden, die

dann ¨

uber ihre komplette Lebenszeit vom WfMS gesteuert

werden. Wenn eine manuelle Aktivit¨

at zur Bearbeitung an-

steht, so wird sie in die Arbeitslisten der entsprechenden Be-

nutzer eingetragen. Nachdem einer von ihnen die Aktivit¨

zur Bearbeitung ausgew¨

ahlt hat, wird das zugeh¨

orige Aktivi-

t¨

atenprogramm gestartet, so dass er die Aktivit¨

at bearbeiten

kann. Nach Beendigung des Programms schaltet das WfMS

zur n¨

achsten Aktivit¨

at weiter, die dann bearbeitet werden

kann.

Um in diesem Beitrag konkrete Algorithmen f¨

ur Mi-

grationen angeben zu k¨

onnen, wird ein formales Workflow-

Metamodell ben¨

otigt. Wir verwenden das Metamodell

78 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

Abb. 1. Modellierung von Workflow-Schemata und Ausf¨

uhrung von Workflow-Instanzen.

[RD98] von ADEPT3[DRK00], die gewonnenen Erkennt-

nisse sind aber auch auf andere Workflow-Metamodelle

ubertragbar. Bei ADEPT k¨

onnen zur Spezifikation des Kon-

trollflusses unter anderem die Konstrukte Sequenz, bedingte

und parallele Verzweigung und Schleife verwendet wer-

den. Zur Festlegung des Datenflusses wird angegeben, wel-

che prozessglobalen Variablen (Datenelemente) von welchen

Aktivit¨

aten gelesen bzw. geschrieben werden. Wie in Abb.1

dargestellt, k¨

onnen Bearbeiterzuordnungen nicht nur Rollen

referenzieren (z.B. Aktivit¨

at a), sondern es werden auch die

in der Praxis h¨

aufig ben¨

otigten abh¨

angigen Bearbeiterzuord-

nungen unterst¨

utzt. Mit diesen kann eine Aktivit¨

at z.B. dem-

selben Bearbeiter wie eine Vorg¨

angeraktivit¨

at oder einem

Benutzer derselben Organisationseinheit zugeordnet werden.

Im unteren Teil von Abb.1 sind zur Ausf¨

uhrungszeit er-

zeugte Workflow-Instanzen dargestellt. Damit der Workflow-

Server die f¨

ur eine bestimmte Workflow-Instanz aktuell

zur Ausf¨

uhrung anstehenden Aktivit¨

ateninstanzen ermitteln

kann, ben¨

otigt er entsprechende Zustandsinformation. In

ADEPT werden dazu den Knoten und Kanten des Aus-

f¨

uhrungsgraphen einer Workflow-Instanz sog. Zustandsmar-

kierungen4zugeordnet. F¨

ur ihre Festlegung bzw. Ver¨

ande-

rung (und die damit zusammenh¨

angende Aktivierung von

Aktivit¨

aten) gibt es wohldefinierte Regeln. Der Zustand ei-

ner Aktivit¨

at ist initial NOT ACTIVATED. Er geht, wenn

alle Vorbedingungen (Signalisierung der eingehenden Kan-

ten) erf¨

ullt sind, in ACTIVATED ¨

uber, was bedeutet, dass

die Aktivit¨

at gestartet werden kann. Bei manuell ausge-

f¨

uhrten Aktivit¨

aten ermittelt der Workflow-Server (mit Hilfe

des Organisationsmodells) dann die potenziellen Bearbeiter

und erzeugt die entsprechenden Arbeitslisteneintr¨

age. Wenn

die Aktivit¨

at von einem Benutzer ausgew¨

ahlt wird, wird

sie aus den entsprechenden Arbeitslisten der anderen po-

tenziellen Bearbeiter wieder entfernt. Nachdem die Daten-

elemente f¨

ur die Versorgung der Eingabeparameter des Ak-

tivit¨

atenprogramms an den entsprechenden Workflow-Client

ubertragen wurden, kann dieses gestartet werden (Zustand

RUNNING). Nach seiner Beendigung werden die Ausgabe-

parameter zum Workflow-Server transportiert und in entspre-

chenden Datenelementen persistent gespeichert. Dann geht

der Zustand der Aktivit¨

at in TERMINATED ¨

uber, woraufhin

die ausgehenden Kanten markiert werden. Dies wiederum

3ADEPT steht f¨

ur Application Development Based on Encapsulated

Pre-Modeled Process Templates.

4Diese Markierung bleiben (anders als bei Petri-Netzen) auch nach Be-

endigung der Aktivit¨

at erhalten, so dass anhand des Zustands unmittelbar

erkannt werden kann, ob eine bestimmte Aktivit¨

at schon ausgef¨

uhrt wurde

(f¨

ur Details siehe [RD98]).

f¨

uhrt zur Berechnung der Zustandsmarkierung der Nachfol-

geraktivit¨

aten.

F¨

ur die Unterst¨

utzung der eingangs erw¨

ahnten fortschritt-

lichen Workflow-Konzepte, wie dynamische ¨

Anderungen,

Uberwachung von Zeitbedingungen und Realisierung ab-

h¨

angiger Bearbeiterzuordnungen, reicht die Zustandsinfor-

mation der Knoten und Kanten alleine noch nicht aus. Hier

wird zus¨

atzlich eine Ablaufhistorie ben¨

otigt, in welcher beim

Starten und Beenden einer Aktivit¨

ateninstanz ein entspre-

chender Eintrag erzeugt wird. Wie in Abb.1 (vereinfacht)

dargestellt, enthalten solche Eintr¨

age Informationen zum

tats¨

achlichen Bearbeiter sowie zum Start- und Endezeitpunkt

der Aktivit¨

at. Auf der Basis dieser Ablaufhistorie ist es dann

z.B. m¨

oglich, abh¨

angige Bearbeiterzuordnungen auszuwer-

ten oder Zeitpl¨

ane f¨

ur die Ausf¨

uhrung der Workflow-Instanz

zu erstellen, da aus ihr die Bearbeiter und die Start- und

Endezeiten der Aktivit¨

aten hervorgehen.

2.2 Verteilte Workflow-Ausf¨

uhrung

Wie bei zahlreichen Ans¨

atzen (siehe [BD99]) besteht bei

ADEPTdistribution, dem Konzept zur verteilten Workflow-

Ausf¨

uhrung von ADEPT, die M¨

oglichkeit, eine Workflow-

Instanz nicht nur durch einen einzigen Workflow-Server

kontrollieren zu lassen, sondern ihre Ausf¨

uhrung verteilt

durch mehrere Server zu steuern [BD97]. Dazu wird das

zugeh¨

orige Workflow-Schema bei der Modellierung in Par-

titionen unterteilt, die zur Ausf¨

uhrungszeit von unterschied-

lichen Servern kontrolliert werden k¨

onnen (vgl. Abb.2).

Wird bei der Ausf¨

uhrung einer Instanz dieses Workflow-

Schemas eine Aktivit¨

at beendet und geh¨

ort ihr Nachfol-

ger einer anderen Partition an, so migriert die Kontrolle

uber diesen Workflow vom Server der aktuellen Partition

(Quellserver der Migration) zum Server der Nachfolgerpar-

tition (Zielserver). Dabei muss eine Beschreibung des Zu-

stands der Workflow-Instanz zum Zielserver transportiert

werden, um dort mit der Kontrolle fortfahren zu k¨

onnen.5

Da eine Migration die ¨

Ubertragung der vom Quellserver ver-

walteten Workflow-Kontrolldaten, workflow-relevanten Da-

ten und Anwendungsdaten (vgl. [WMC99]) der Workflow-

Instanz erfordert, verursacht sie aber Kommunikationskos-

ten. Um keinen unn¨

otigen Aufwand zu generieren, kom-

munizieren Workflow-Server in ADEPT ausschließlich bei

5Eine Alternative hierzu w¨

are, die Ausf¨

uhrung jeder einzelnen Aktivi-

t¨

at am Zielserver zu veranlassen (im Stile eines Remote Procedure Calls).

Diese Vorgehensweise hat aber den Nachteil, dass f¨

ur jede einzelne Aktivi-

t¨

at Nachrichten ¨

ubertragen werden m¨

ussen und dass Daten evtl. redundant

bei der Initiierung mehrerer Aktivit¨

aten transferiert werden.

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 79

P a r t i t i o n 1

n o r m a l e r

K o n t r o l l f l u s s

K o n t r o l l f l u s s u n d

M i g r a t i o n v o n

A k t i v i t ä t x n a c h y

b , c

b , e

d , g

S e r v e r 2 S e r v e r 3

S e r v e r 1

S e r v e r 4 S e r v e r 4

S e r v e r 5

a b

c d

e f

S e r v e r 1

P a r t i t i o n 3

c , d

P a r t i t i o n 4

f , g

P a r t i t i o n 5

P a r t i t i o n 2

x , y

A N D - S p l i t

A N D - J o i n

Abb. 2. Partitionierung eines Workflow-Schemas und verteilte Workflow-Ausf¨

uhrung.

Migrationen, d.h. Partitionen parallel ausgef¨

uhrter Aktivi-

t¨

aten (z.B. Partition 2 und 4 in Abb.2) werden von den

entsprechenden Workflow-Servern unabh¨

angig voneinander

kontrolliert. Bei der Aktivit¨

atenausf¨

uhrung findet dement-

sprechend keine Synchronisation oder Kommunikation zwi-

schen diesen Workflow-Servern statt, weshalb einem Server

der Zustand von parallel ausgef¨

uhrten Aktivit¨

aten in der Re-

gel nicht bekannt ist. So weiß der Workflow-Server der Par-

tition 4 zum Beispiel nicht, ob die parallel ausgef¨

uhrte Akti-

vit¨

at cschon beendet ist oder nicht. Die verschiedenen an ei-

ner Workflow-Instanz beteiligten Workflow-Server verf¨

ugen

also ¨

uber (teilweise) unterschiedliche Zustandsinformation

und dementsprechend ¨

uber unterschiedliche Ablaufhistorien.

Eine Partitionierung des Workflow-Schemas und die da-

durch notwendig werdenden Migrationen zur Ausf¨

uhrungs-

zeit werden auch von einigen anderen in der Literatur dis-

kutierten Ans¨

atzen unterst¨

utzt (z.B. [CGP+96, MWW+98]).

ADEPT verfolgt zus¨

atzlich das Ziel, die Kommunikations-

kosten eines derart verteilten Ansatzes zu minimieren. Un-

sere Erfahrungen mit existierenden WfMS, Modellrechnun-

gen und Simulationen [BD97, BD99, BD00] haben ge-

zeigt, dass zwischen einem Workflow-Server und seinen Cli-

ents zahlreiche Nachrichten und große Datenmengen aus-

getauscht werden. Mit steigender Anzahl von Benutzern

und Workflow-Instanzen kann dies dazu f¨

uhren, dass das

Kommunikationssystem ¨

uberlastet wird. Aus diesem Grund

wird in ADEPT der Workflow-Server f¨

ur jede Aktivit¨

so gew¨

ahlt, dass die insgesamt anfallenden Kommunikati-

onskosten minimiert werden. Dazu wird – vereinfacht aus-

gedr¨

uckt – der Workflow-Server einer Aktivit¨

at so festge-

legt, dass er in demjenigen Teilnetz liegt, dem die Mehr-

zahl ihrer potenziellen Bearbeiter angeh¨

ort. Dadurch gelingt

es weitgehend, teilnetz¨

ubergreifende Kommunikation zwi-

schen einem Workflow-Server und seinen Clients zu vermei-

den. Außerdem werden die Antwortzeiten verbessert und die

Verf¨

ugbarkeit erh¨

oht, da bei der Ausf¨

uhrung von Aktivit¨

aten

kein Gateway oder WAN ben¨

otigt wird (f¨

ur Details und die

zugeh¨

origen Algorithmen siehe [BD97]).

Die Zuordnung von Workflow-Servern zu Aktivit¨

aten

(bzw. Partitionen) ist in ADEPTdistribution sowohl statisch

als auch dynamisch m¨

oglich, abh¨

angig von den f¨

ur die

einzelnen Schritte definierten Bearbeiterzuordnungen. Wer-

den die Bearbeiter einer Aktivit¨

at direkt durch ihre Rolle

und Organisationseinheit festgelegt, so werden statische Ser-

verzuordnungen verwendet. F¨

ur viele Anwendungen wer-

den zus¨

atzlich abh¨

angige Bearbeiterzuordnungen ben¨

otigt

(z.B. derselbe Bearbeiter wie Aktivit¨

at n). Da der ent-

sprechende Bearbeiter erst im Verlauf der Workflow-Aus-

f¨

uhrung feststeht, ist es in solchen F¨

allen vorteilhaft, den

Workflow-Server dieser Aktivit¨

ateninstanz erst zur Ausf¨

uh-

rungszeit festzulegen. F¨

ur diesen Fall ist es m¨

oglich, den

Workflow-Server so auszuw¨

ahlen, dass er sich in der Orga-

nisationseinheit der entsprechenden Bearbeiter befindet. Zu

diesem Zweck wurde f¨

ur ADEPTdistribution das Konzept

der variablen Serverzuordnungen [BD00] entwickelt, bei

denen der tats¨

achliche Server einer Aktivit¨

ateninstanz erst

nach Beendigung der Vorg¨

angeraktivit¨

aten festgelegt wird.

Auch bei einigen anderen Ans¨

atzen kann ein Workflow-

Server dynamisch zur Ausf¨

uhrungszeit festgelegt werden

[AMG+95, BMR96, SM96].

2.3 Problemstellung und Beitrag

Bei Migrationen von Workflow-Instanzdaten zwischen

Workflow-Servern entstehen hohe Kosten (vgl. Abschnitt 6).

Das Ziel dieser Arbeit ist es, Verfahren zu entwickeln, mit

denen dieses Datenvolumen reduziert werden kann. In bis-

herigen Ver¨

offentlichungen zu ADEPTdistribution [BD97,

BD00] haben wir Verfahren zur Reduzierung der Kom-

munikationslast betrachtet, die auf der Vorberechnung von

geeigneten Serverzuordnungen basieren. Diese werden zur

Modellierungszeit eingesetzt. Dagegen werden bei den in

der vorliegenden Arbeit vorgestellten Verfahren die Kom-

munikationskosten durch zur Ausf¨

uhrungszeit durchgef¨

uhrte

Optimierungen reduziert, welche die Serverzuordnung nicht

ver¨

andern. Die Reduktion der Kommunikationskosten wird

erreicht, indem nicht alle f¨

ur die betroffene Workflow-Instanz

verf¨

ugbaren Daten zum Zielserver ¨

ubertragen werden, son-

dern nur diejenigen, die dieser Server tats¨

achlich f¨

ur die kor-

rekte Workflow-Ausf¨

uhrung ben¨

otigt und noch nicht besitzt.

Ein Workflow-Server kann beispielsweise bereits ¨

uber Daten

verf¨

ugen, wenn er fr¨

uher an der Kontrolle der Workflow-

Instanz beteiligt war, oder wenn ihm bestimmte Informa-

tionen bei vorausgehenden Migrationen ¨

ubermittelt worden

sind. Da die Migrationen durch entsprechende Maßnahmen

,,billiger“ werden, k¨

onnen sie ggf. h¨

aufiger und damit auch

f¨

ur kleinere Prozessfragmente durchgef¨

uhrt werden. Die

Workflow-Steuerung erfolgt dementsprechend meist im Teil-

netz derjenigen Benutzer, welche die Aktivit¨

at bearbeiten, so

dass sich die Antwortzeiten und die Verf¨

ugbarkeit des WfMS

verbessern.

Um einen Eindruck zu vermitteln, welche Art von Op-

timierungen im Zusammenhang mit der Durchf¨

uhrung von

Prozessmigrationen im Einzelnen m¨

oglich sind, wollen wir

anhand von Abb.2 einige Beispiele betrachten:

–Die Zustandsinformation (inkl. Ablaufhistorie) zu den

Aktivit¨

aten aund bwird bei herk¨

ommlichen Migratio-

nen ¨

uber beide parallele Zweige zur AND-Join-Aktivit¨

gtransportiert. Das heißt, sie w¨

urde sowohl bei der Mi-

gration Md,g als auch bei Mf,g zum Server 5 ¨

ubertragen.

Wie man leicht sieht, kann eine dieser beiden (redundan-

ten) ¨

Ubertragungen eingespart werden.

80 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

–Angenommen, die Aktivit¨

at cschreibt einen Ausgabepa-

rameter in ein Datenelement, auf das von der Aktivit¨

at g

lesend zugegriffen wird (nicht aber von d). Dann ist es

wenig sinnvoll, das Datenelement entlang des Kontroll-

flusses vom Server 2 ¨

uber den Server 3 zum Server 5 zu

ubertragen. Eine Optimierung w¨

are es, das Datenelement

direkt vom Server 2 zum Server 5 zu ¨

ubertragen. Dies

ist besonders rentabel, wenn sehr große Datenelemente

(z.B. CAD-Pl¨

ane oder Multimediadaten wie Videos und

Bitmaps) betroffen sind. Erw¨

ahnt sei an dieser Stelle,

dass eine Speicherung solcher Daten in einer zentralen

Datenbank nachteilig w¨

are, da dann evtl. mehrfach (bei

der Ausf¨

uhrung mehrerer Aktivit¨

aten) weit entfernt auf

sie zugegriffen werden m¨

usste. Es ist g¨

unstiger, die Da-

ten einmal zu migrieren, um sie dann im lokalen Teilnetz

verf¨

ugbar zu haben.

–Wird von der Aktivit¨

at gein Datenelement ben¨

otigt,

das von der Aktivit¨

at ageschrieben und von cund d

gelesen wurde, dann kann der Wert dieser Variablen

von den Workflow-Servern 1, 2 und 3 bezogen wer-

den. Es existiert insofern Optimierungspotential, als dass

das Datenelement von demjenigen Server bezogen wer-

den kann, zu dem die kosteng¨

unstigste Kommunika-

tionsverbindung besteht. Eine redundante ¨

Ubertragung

sollte dabei vermieden werden. Angenommen, die Ser-

ver 1 und 3 sind mit dem Server 5 nur ¨

uber eine ISDN-

Verbindung verbunden, wohingegen der Server 2 in ei-

nem zum Server 5 benachbarten Teilnetz mit einer Ver-

bindung ¨

uber ein schnelles Gateway liegt. Dann ist es

wesentlich g¨

unstiger, wenn das (große) Datenelement

vom Server 2 bezogen wird.

Die Beispiele zeigen, dass bei ,,naiver“ Realisierung der ver-

teilten Workflow-Steuerung Daten unn¨

otigerweise zu einer

Partition ¨

ubertragen werden k¨

onnen. Eine solche redundante

Ubertragung sollte vermieden werden. Im Folgenden wer-

den Verfahren vorgestellt, mit denen Migrationen effizient

durchgef¨

uhrt werden k¨

onnen, indem die entstehenden Migra-

tionskosten minimiert werden. Dazu werden im Einzelnen

Verfahren zur Migration der Kontrolldaten einer Workflow-

Instanz (Zustand, Ablaufhistorie) und Verfahren zur optima-

len und redundanzfreien ¨

Ubertragung von Datenelementen

vorgestellt.

oglichkeiten zur Migration von Workflow-

Kontrolldaten

In diesem Abschnitt untersuchen wir, wie die Zustands-

information einer Workflow-Instanz (Workflow-Kontrollda-

ten nach [WMC99]) migriert werden soll. Dazu analysieren

wir zuerst die prinzipiell m¨

oglichen Vorgehensweisen und

beschreiben anschließend ein ausgew¨

ahltes Verfahren.

3.1 Auswahl eines geeigneten Verfahrens

Im Folgenden werden alternative Ans¨

atze zur Migration der

Kontrolldaten einer Workflow-Instanz (Zustand und Ablauf-

historie) diskutiert6:

Ansatz 1: Minimall¨

osung. Die ¨

Ubertragung der Zustands-

information ist mit minimalem Kommunikationsaufwand

m¨

oglich, wenn dem Zielserver lediglich die Quell- und Zie-

laktivit¨

at der Migration mitgeteilt wird. Damit weiß er, um

welche Migration es sich handelt, und somit, an welcher

Stelle im Workflow-Ausf¨

uhrungsgraphen er die Abarbeitung

fortsetzen muss.

Der Nachteil dieses einfachen Ansatzes ist das Fehlen

jeglicher Zusatzinformation aus der Ablaufhistorie. Dadurch

k¨

onnen die meisten der in der Einleitung erw¨

ahnten fort-

schrittlichen Workflow-Konzepte nicht realisiert werden. Die

fehlende Information zu Bearbeitern von Vorg¨

angeraktivi-

t¨

aten etwa schließt die Verwendung von abh¨

angigen Bearbei-

terzuordnungen aus. F¨

ur die Berechnung von Zeitpl¨

anen f¨

die Bearbeitung der Aktivit¨

ateninstanzen werden die in der

Ablaufhistorie vermerkten Ausf¨

uhrungszeitpunkte der Vor-

g¨

angeraktivit¨

aten ben¨

otigt.

Ansatz 2: ¨

Ubertragung der aktuellen Zust¨

ande. Um das

Problem fehlender Zustandsinformation zu l¨

osen, k¨

onnen

bei einer Migration alle Zust¨

ande der Aktivit¨

aten und Kan-

ten des Ausf¨

uhrungsgraphen an den Migrationszielserver

ubertragen werden. Bei Synchronisationspunkten (z.B. Zu-

sammenf¨

uhrung paralleler Zweige) werden von verschiede-

nen Migrationsquellservern dann ggf. unterschiedliche Zu-

standsinformationen zu denselben Aktivit¨

aten geliefert, da

diese f¨

ur nicht von ihnen selbst kontrollierte Aktivit¨

aten

evtl. nur veraltete Zustandsinformation besitzen. Damit stellt

sich das Problem, zu entscheiden, welches der aktuelle Zu-

stand einer Aktivit¨

at ist, da dies nicht immer der am weites-

ten fortgeschrittene Zustand sein muss. So kann z.B. beim

Zur¨

ucksetzen der Zustand einer Aktivit¨

at von TERMINA-

TED zu NOT ACTIVATED ¨

ubergehen. Werden nun bei ver-

schiedenen Migrationen unterschiedliche Zust¨

ande f¨

ur diese

Aktivit¨

at empfangen, so kann nicht ohne weiteres entschie-

den werden, welches der aktuell g¨

ultige ist.

Zwar ist bei diesem Ansatz die Zustandsinformation

verf¨

ugbar, allerdings fehlt auch hier jegliche Zusatzinforma-

tion (z.B. zu Bearbeitern oder Ausf¨

uhrungszeitpunkten der

Aktivit¨

aten).

Ansatz 3: ¨

Ubertragung der Zust¨

ande und der Ablaufhisto-

rie. Um das letztgenannte Problem zu l¨

osen, kann die ge-

samte zu dieser Workflow-Instanz gespeicherte Information

(inkl. Ablaufhistorie) ¨

ubertragen werden. Werden an Syn-

chronisationspunkten unterschiedliche Zust¨

ande f¨

ur eine Ak-

tivit¨

at empfangen, so muss wie beim Ansatz 2 der aktuell

g¨

ultige Zustand bestimmt werden.

Da bei diesem Ansatz alle Kontrolldaten der Workflow-

Instanz migriert werden, treten die oben beschriebenen Pro-

bleme nicht auf. Der Nachteil ist aber, dass Ausf¨

uhrungsin-

formationen redundant ¨

ubertragen werden, da sich z.B. die

Information, dass eine Aktivit¨

at beendet wurde, sowohl in

der Ablaufhistorie als auch in den Aktivit¨

atenmarkierungen

widerspiegelt.

Ansatz 4: ¨

Ubertragung (nur) der Ablaufhistorie. Die gesamte

von Nachfolgeraktivit¨

aten ben¨

otigte Information zu einer

Workflow-Instanz findet sich in ihrer Ablaufhistorie wieder.

Deshalb kann, ausgehend vom (auf den Servern repliziert

vorhandenen) Workflow-Schema, durch das ,,Nachspielen“

6Bei einer Migration wird zus¨

atzlich zu der explizit aufgef¨

uhrten

Information stets auch die global eindeutige ID der Workflow-Instanz

transferiert.

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 81

H ( a ) S e r v e r 1

a b

S e r v e r 1

H ( a )

H ( b )

H ( c )

S e r v e r 1

H ( a )

H ( b )

H ( d )

H ( e )

S e r v e r 2

S e r v e r 1

H ( a )

H ( b )

H ( d )

H ( e )

H ( a )

H ( b )

H ( c )

+ =

H ( a )

H ( b )

H ( c )

H ( d )

H ( e )

H ( a )

H ( b )

H ( c )

H ( d )

H ( e )

H ( f )

b , d

e , f

H ( a )

H ( b )

H ( d )

S e r v e r 2

E i n t r a g z u r

A k t i v i t ä t e n -

i n s t a n z a

A b l a u f h i s t o r i e

H ( a )

H ( b )

Abb. 3. Beispiel f¨

ur das Zusammenf¨

uhren von Ablaufhistorien.

der in der Ablaufhistorie vermerkten Aktionen der Zustand

der Workflow-Instanz rekonstruiert werden. Die Zustands-

information einer Workflow-Instanz kann somit ¨

ubertragen

werden, indem ausschließlich die Ablaufhistorie transferiert

wird.

Bewertung. Ein gravierender Nachteil der Ans¨

atze 1 und 2

ist das Fehlen von Zusatzinformation zur Workflow-Instanz.

Sollen bei Zugrundelegung dieser Ans¨

atze fortschrittliche

WfMS-Konzepte realisiert werden, muss h¨

aufig Information

nachtr¨

aglich angefordert werden. Dies f¨

uhrt dazu, dass eine

große Anzahl von ¨

Ubertragungen stattfindet, da die Kon-

trolldaten, die bei den anderen Ans¨

atzen auf einmal ¨

uber-

tragen werden, durch mehrere Anforderungen besorgt wer-

den m¨

ussen. Im Extremfall m¨

ussen von allen Vorg¨

angerak-

tivit¨

aten Daten nachgefordert werden, z.B. wenn die Start-

und Endezeitpunkte aller Aktivit¨

aten ben¨

otigt werden, um

Zeitpl¨

ane f¨

ur die nachfolgenden Aktivit¨

aten zu berechnen

[DRK00]. Das Nachfordern von Kontrolldaten beeintr¨

achtigt

außerdem die Verf¨

ugbarkeit des WfMS, da die Bearbeitung

eines Workflows nur fortschreiten kann, wenn die Server,

von denen Informationen ben¨

otigt werden, gerade verf¨

ugbar

sind. Aus diesen Gr¨

unden scheiden die Ans¨

atze 1 und 2

aus.7Der Ansatz 3 disqualifiziert sich wegen des großen

Umfangs der zu transferierenden Datenmenge. Abgesehen

davon resultiert aus den zus¨

atzlich ¨

ubertragenen Daten kein

Vorteil gegen¨

uber dem Ansatz 4. Der letztgenannte Ansatz

stellt einen guten Kompromiss dar, da hier die Datenmenge

in einem vern¨

unftigen Rahmen bleibt und alle ben¨

otigten

Informationen vorhanden sind. Im Folgenden wird dieser

Ansatz deshalb n¨

aher untersucht.

3.2 Migration der Ablaufhistorie

Nachdem sich gezeigt hat, dass die g¨

unstigste Variante zur

Migration von Zustandsinformation darin besteht, die Ab-

laufhistorie zu ¨

ubertragen, betrachten wir nun diesen An-

satz etwas detaillierter. Von Interesse ist dabei vor allem,

wie an Synchronisationspunkten des Ausf¨

uhrungsgraphen

(AND-Join) die Ablaufhistorien der verschiedenen Vorg¨

an-

geraktivit¨

aten zusammengef¨

uhrt werden.

7In Abschnitt 4 wird ein Verfahren vorgestellt, das mit der ¨

Ubertragung

derselben Information wie der Ansatz 1 beginnt (Workflow-Instanz-ID,

Quell- und Zielaktivit¨

at der Migration). Anschließend wird die zus¨

atzlich

ben¨

otigte Information angefordert und (auf einmal) ¨

ubertragen. Da das Ver-

fahren auf der ¨

Ubertragung von Ablaufhistorien basiert, wird es aber als

Optimierung des Ansatzes 4 betrachtet.

Bei einem Workflow ohne parallel ausgef¨

uhrte Zweige

ist der Ablauf des Verfahrens denkbar einfach: Da eine Ab-

laufhistorie stets von nur einer Vorg¨

angeraktivit¨

at empfangen

wird, kann die lokal evtl. schon vorhandene Historie8durch

diese ersetzt werden. Durch das ,,Nachspielen“ der in der

Ablaufhistorie vorhandenen Eintr¨

age erh¨

alt man dann den

aktuellen Zustand des Ausf¨

uhrungsgraphen.

Interessanter ist der Fall, dass parallele Zweige unter-

schiedlicher Server zusammengef¨

uhrt werden m¨

ussen (z.B.

bei der AND-Join-Aktivit¨

at gin Abb.2), da dann zwei unter-

schiedliche Versionen der Ablaufhistorie aufeinander treffen.

Beim Zusammenf¨

uhren von Historieninformation verschie-

dener Workflow-Server muss gew¨

ahrleistet sein, dass das Er-

gebnis wieder eine korrekte Historie darstellt, d.h., dass eine

Ablaufhistorie entsteht, die auch auf einem zentralen Sys-

tem mit nur einem einzigen Workflow-Server entstanden sein

k¨

onnte. Es m¨

ussen sich also alle im Workflow-Schema defi-

nierten Reihenfolgebeziehungen von Aktivit¨

aten in der Ab-

laufhistorie widerspiegeln, auch wenn diese Aktivit¨

aten von

unterschiedlichen Servern kontrolliert wurden. Außerdem

soll ein Workflow-Server stets den vollst¨

andigen f¨

ur ihn re-

levanten Zustand einer von ihm kontrollierten Workflow-

Instanz kennen. Das heißt, ein Workflow-Server, der gerade

die Aktivit¨

ateninstanz akontrolliert, kennt stets alle Histo-

rieneintr¨

age (und damit den Zustand) der Vorg¨

angeraktivi-

t¨

aten von a, weil diese bei Migrationen zu ihm weitergereicht

wurden. ¨

Uber die Historieneintr¨

age von parallel zu aausge-

f¨

uhrten Aktivit¨

aten muss dieser Server im Allgemeinen aber

nicht verf¨

ugen.

Die bei einer Migration empfangene und die auf die-

sem Server schon lokal vorhandene (bzw. davor empfan-

gene) Ablaufhistorie m¨

ussen zu einer einzigen Ablaufhis-

torie zusammengef¨

uhrt werden. Dies geschieht, indem die

Historieneintr¨

age ,,gemischt“ werden. Wie dieses Mischen

erfolgt, wollen wir am Beispiel der in Abb.3 dargestell-

ten AND-Join-Aktivit¨

at fbetrachten. Wenn sich eine Ak-

tivit¨

ateninstanz (z.B. a) im Kontrollfluss vor einer ande-

ren Aktivit¨

at (z.B. d) befindet, so m¨

ussen auch die zu ihr

geh¨

orenden Eintr¨

age in der resultierenden Historie vor den

Eintr¨

agen der anderen Aktivit¨

at einsortiert werden. Die Rei-

henfolge von Historieneintr¨

agen parallel ausgef¨

uhrter Akti-

vit¨

aten (z.B. cund d) kann dagegen beliebig gew¨

ahlt werden.

Man kann zeigen, dass bei einer Migration empfangene His-

torieneintr¨

age, die dem Zielserver noch nicht bekannt sind,

einfach an die lokal schon vorhandene Ablaufhistorie an-

8Dieser Fall ist gegeben, wenn der Migrationszielserver bereits fr¨

uher

einmal eine Partition des Ausf¨

uhrungsgraphen dieser Workflow-Instanz

kontrolliert hat.

82 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

S e r v e r 1 S e r v e r 2

S e r v e r 1

S e r v e r 1 S e r v e r 2

S e r v e r 2

c d

e g

h i

S e r v e r 1

e , f

S e r v e r 2

S e r v e r 1

b , c

S e r v e r 3

f,g

h , i

a , b

Abb. 4. Beispiel f¨

ur die Migration von Workflow-Kontrolldaten.

geh¨

angt werden k¨

onnen [Zei99], um diesen Bedingungen

zu gen¨

ugen (vgl. Abb.3). Die Position schon vorhandener

Eintr¨

age bleibt unver¨

andert. Dieses Verfahren arbeitet kor-

rekt, weil f¨

ur alle Aktivit¨

aten gilt: Wenn ein Historieneintrag

zu einer Aktivit¨

at am Zielserver bekannt ist, dann sind dort

auch die Historieneintr¨

age zu allen Vorg¨

angeraktivit¨

aten be-

kannt (siehe oben). Deshalb kann es sich bei einer Aktivi-

t¨

ateninstanz, von der erstmalig ein Eintrag empfangen wird

(z.B. d), nicht um eine Vorg¨

angeraktivit¨

at von schon bekann-

ten Aktivit¨

aten (a,bund c) handeln. Diese Aktivit¨

at kann

also nur parallel zu diesen Aktivit¨

aten oder nach diesen aus-

gef¨

uhrt worden sein. Deshalb ist es korrekt, den erstmalig

empfangenen Historieneintrag am Ende der Ablaufhistorie

zu platzieren. Dabei darf die Reihenfolge neuer Eintr¨

age un-

tereinander (z.B. dund e) nat¨

urlich nicht ver¨

andert werden.

Da mittels einer Hash-Tabelle (mit konstantem Zeitaufwand)

gepr¨

uft werden kann, ob ein Eintrag schon bekannt ist, und

neue Eintr¨

age einfach an die Historie angeh¨

angt werden, er-

gibt sich ein ¨

außerst effizienter Algorithmus.

4 Optimierte ¨

Ubertragung von Workflow-Kontrolldaten

Der im vorherigen Abschnitt diskutierte Ansatz 4 ist am bes-

ten f¨

ur die ¨

Ubertragung der Kontrolldaten einer Workflow-

Instanz geeignet, da er das g¨

unstigste Kommunikationsver-

halten aufweist. Bei dem in Abschnitt 3.2 skizzierten Verfah-

ren kann es allerdings zu redundanten Daten¨

ubertragungen

kommen. So werden bei dem in Abb.3 dargestellten Beispiel

die Historieneintr¨

age der Aktivit¨

aten aund bbei der Migra-

tion Me,f zum Server 1 ¨

ubertragen, obwohl sie diesem schon

bekannt sind. Im dem nun folgenden Abschnitt werden ver-

besserte Verfahren vorgestellt, bei denen zum Zielserver nur

die wirklich ben¨

otigten Historieneintr¨

age ¨

ubertragen werden.

4.1 Versenden von Ablaufhistorieneintr¨

agen

Die n¨

achstliegende Idee zur Reduzierung des Datenvolu-

mens beim ¨

Ubertragen von Workflow-Kontrolldaten besteht

darin, nur den ben¨

otigten Ausschnitt der Ablaufhistorie und

nicht die komplette Ablaufhistorie an den Migrationsziel-

server zu senden. Aus Platzgr¨

unden verzichten wir hier auf

eine algorithmische Darstellung dieses Verfahrens. Stattdes-

sen erl¨

autern wir nur das Grundprinzip und diskutieren die

entstehenden Nachteile. In Abschnitt 4.2 wird dann ein ver-

bessertes Verfahren vorgestellt, das diese Nachteile vermei-

det.Um bei einer Migration nicht immer die gesamte Ab-

laufhistorie einer Workflow-Instanz ¨

ubertragen zu m¨

ussen,

berechnet der Quellserver, welcher Teil dieser Historie vom

Zielserver f¨

ur die weitere Ausf¨

uhrung noch ben¨

otigt wird.

Dementsprechend wird nur dieser Ausschnitt bei der Mi-

gration ¨

ubertragen. Dazu sucht der Quellserver in der Histo-

rie nach Eintr¨

agen, deren zugeh¨

orige Aktivit¨

ateninstanz vom

Zielserver kontrolliert wurde (sofern vorhanden). Bei der

Ubertragung der Ablaufhistorie k¨

onnen diese Eintr¨

age dann

weggelassen werden. Dasselbe gilt f¨

ur Historieneintr¨

age,

die sich auf Vorg¨

angeraktivit¨

ateninstanzen (bzgl. des Kon-

trollflusses) dieser Aktivit¨

ateninstanzen beziehen, da auch

diese Historieneintr¨

age dem Zielserver schon bekannt sind.

Der Grund daf¨

ur ist, dass ein Workflow-Server alle His-

torieneintr¨

age kennt, die zu Vorg¨

angeraktivit¨

aten der von

ihm kontrollierten Aktivit¨

ateninstanzen geh¨

oren (vgl. Ab-

schnitt 3.2).

Durch dieses Verfahren werden Historieneintr¨

age, von

denen der Quellserver einer Migration sicher weiß, dass sie

auf dem Zielserver schon bekannt sind, an diesen nicht mehr

ubertragen. So werden bei dem in Abb.4 dargestellten Bei-

spiel einer parallelen Verzweigung die Historieneintr¨

age zu

den Aktivit¨

ateninstanzen aund bweder bei der Migration

Mf,g noch bei Mh,i an den Server 2 ¨

ubertragen, da dieser

bereits die Aktivit¨

at bkontrolliert hat und deshalb die zu

Aktivit¨

at bund zur Vorg¨

angeraktivit¨

at ageh¨

orenden Histo-

rieneintr¨

age schon kennt.

Bei dem oben beschriebenen Verfahren kann es aber im-

mer noch zur redundanten ¨

Ubertragung von Historieninfor-

mation kommen. Das Problem des Verfahrens ist, dass der

Quellserver einer Migration nicht exakt weiß, welche His-

torieneintr¨

age beim Zielserver schon vorhanden sind. Neh-

men wir in dem Beispiel aus Abb.4 an, dass die Migration

Mf,g vor Mh,i ausgef¨

uhrt wird. Dann m¨

ussen bei der Mi-

gration Mf,g die Historieneintr¨

age der Aktivit¨

aten cund d

ubertragen werden. Bei der sp¨

ater ausgef¨

uhrten Migration

Mh,i kann der Quellserver 1 aber nicht wissen, dass die ent-

sprechenden Eintr¨

age dem Zielserver 2 schon bekannt sind.

Diese nicht vorhandene Information f¨

uhrt dazu, dass er die

Eintr¨

age unn¨

otigerweise ¨

ubertr¨

agt. Das vorgestellte Verfah-

ren erm¨

oglicht also zwar eine Reduzierung der zu ¨

ubertra-

genden Datenmenge, redundante Daten¨

ubertragung l¨

asst sich

damit aber nicht v¨

ollig ausschließen.

4.2 Anfordern von Ablaufhistorieneintr¨

agen

Die redundante ¨

Ubertragung von Ablaufhistorieneintr¨

agen

kann ausgeschlossen werden, wenn der Zielserver einer Mi-

gration dem Quellserver Information dar¨

uber liefert, welche

Historieneintr¨

age ihm bereits bekannt sind.9Ein Verfahren

9Eine Alternative dazu w¨

are, dass die anderen Server des WfMS In-

formation dar¨

uber austauschen, welche Historieneintr¨

age schon zu diesem

Zielserver migriert wurden. Da ein solches Verfahren aber sehr komplex

w¨

are und außerdem nicht weniger Kommunikation erfordern w¨

urde, wird

dieser Ansatz nicht weiter verfolgt.

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 83

Algorithmus 1 (Zielserver: Anfordern von Ablaufhistorieneintr¨

agen)

input

SourceAct: Quellaktivit¨

ateninstanz der Migration

OldHistory: am Zielserver bekannter Teil der Ablaufhistorie

output

LastActivities: Menge von Aktivit¨

ateninstanzen, bis zu denen die Ablaufhistorie dem Zielserver

bekannt ist

begin

LastActivities =∅;

// f¨

ur Migration sind nur Vorg¨

angeraktivit¨

ateninstanzen der Quellaktivit¨

at (inklusive) relevant

RelevantHistory =OldHistory ∩HistoryEntries({SourceAct}∪Predecessors(SourceAct));

while RelevantHistory /=∅do

// List der hinterste Eintrag der Historie RelevantHistory,ldie zugeh¨

orige Aktivit¨

ateninstanz

L=LastEntry(RelevantHistory);

l=ActivityInstance(L);

LastActivities =LastActivities ∪{l};

// entferne Eintr¨

age zu lund aller Vorg¨

anger bzgl. Kontrollfluss aus Ablaufhistorie

RelevantHistory =RelevantHistory −HistoryEntries({l}∪Predecessors(l));

end.

hierf¨

ur wird nun vorgestellt. Dabei kann eine redundante

Ubertragung von Historieneintr¨

agen nur dann ausgeschlos-

sen werden, wenn f¨

ur eine Workflow-Instanz nie mehrere

Migrationen zeitlich ¨

uberlappend bei demselben Workflow-

Server eingehen. Ansonsten kann der Zielserver nicht wis-

sen, welche Historieneintr¨

age noch durch die anderen gleich-

zeitig ablaufenden Migrationen geliefert werden. Deshalb

verwendet der Zielserver einer Migration Sperren, um si-

cherzustellen, dass zu jedem Zeitpunkt f¨

ur eine Workflow-

Instanz maximal eine Migration eingehen kann, d.h. er blo-

ckiert ggf. kurzfristig die weitere Bearbeitung einer einge-

henden Migration.

Das im Folgenden vorgestellte Verfahren basiert auf der

Idee, dass der Zielserver der durchzuf¨

uhrenden Migration

beim Quellserver diejenigen Teile der Ablaufhistorie anfor-

dert, die bei ihm noch nicht vorhanden sind. Das Verfahren

gliedert sich in 3 Phasen:

1. Der Quellserver informiert den Zielserver ¨

uber die an-

stehende Migration. Dazu ¨

ubertr¨

agt er ihm außer der ID

der zu migrierenden Workflow-Instanz jeweils die ID der

Quell- und Zielaktivit¨

aten der Migration. F¨

ur das Bei-

spiel der Migration Mf,g aus Abb.4 ergibt sich also die

Ubertragung: <WF-Inst-ID, f,g>

2. Der Zielserver der Migration fordert nun beim Quellser-

ver den noch fehlenden Teil der Ablaufhistorie an. Dazu

muss er ihm mitteilen, ¨

uber welche Historieneintr¨

age

er bereits verf¨

ugt. Die einfachste L¨

osung, die IDs al-

ler zugeh¨

origen Aktivit¨

ateninstanzen zu ¨

ubertragen, w¨

are

aber unn¨

otig aufwendig. Sind die Historieneintr¨

age einer

Aktivit¨

ateninstanz dem Zielserver bekannt, so kennt er

n¨

amlich auch die Eintr¨

age zu Vorg¨

angeraktivit¨

aten die-

ser Aktivit¨

ateninstanz. Deshalb gen¨

ugt es, die Menge

LastActivities zu ¨

ubertragen, welche die IDs derjeni-

gen Aktivit¨

ateninstanzen enth¨

alt, von denen dem Ziel-

server keine Historieneintr¨

age zu Nachfolgeraktivit¨

aten

bekannt sind. Dies sind sozusagen die ,,letzten dem Ziel-

server bekannten Aktivit¨

aten“ der Workflow-Instanz. Es

kann vorkommen, dass die Menge LastActivities meh-

rere Aktivit¨

aten enth¨

alt, da der Zielserver einer Migration

Historieneintr¨

age zu Aktivit¨

aten besitzen kann, die ver-

schiedenen parallelen Zweigen angeh¨

oren. Dann muss

die jeweils letzte bekannte Aktivit¨

at jedes Zweiges in

LastActivities enthalten sein.

Mit dem Algorithmus 1 kann der Zielserver einer Mi-

gration die Menge LastActivities berechnen. Dazu re-

duziert er die lokal bei ihm vorhandene Ablaufhistorie

OldHistory der Workflow-Instanz auf die Vorg¨

angerak-

tivit¨

aten der Migrationsquellaktivit¨

at, da nur dieser Teil

der Workflow-Instanz f¨

ur die Migration relevant ist. Da-

durch ergibt sich die Ablaufhistorie RelevantHistory.

Der hinterste Eintrag Lvon RelevantHistory geh¨

ort

zur einer Aktivit¨

ateninstanz l, deren Historieneintr¨

age

am Zielserver bekannt sind. Da der Zielserver auch ¨

uber

die Historieneintr¨

age aller Vorg¨

angeraktivit¨

aten von l

verf¨

ugt, entfernt er diese aus der Ablaufhistorie Rele-

vantHistory. Die Aktivit¨

ateninstanz lwird in Last-

Activities aufgenommen, weil die Vorg¨

angeraktivit¨

aten

von l(inkl. l) am Zielserver bekannt sind, nicht aber

die Nachfolgeraktivit¨

aten. Der gesamte Vorgang wird so-

lange wiederholt, bis in der Historie RelevantHistory

keine Eintr¨

age mehr existieren. Ist dies erreicht, so wurde

die vollst¨

andige Menge LastActivities ermittelt. Im

Beispiel der Migration Mf,g aus Abb.4 ergibt sich Last-

Activities ={b}, weil der Zielserver (Server 2) nur ¨

uber

Information zu den Aktivit¨

aten aund bverf¨

ugt (bwurde

vom Server 2 kontrolliert). Da aeine Vorg¨

angeraktivit¨

von bist, wird anicht in LastActivities aufgenommen.

3. Nachdem der Quellserver der Migration die Menge Last-

Activities empfangen hat, kann er mit Algorithmus 2

die zu ¨

ubertragende Ablaufhistorie MigrHistory be-

rechnen. Dazu reduziert er die bei ihm vorhandene Ab-

laufhistorie LocalHistory auf Vorg¨

anger der Quellak-

tivit¨

at der Migration (wie der Zielserver in Algorith-

mus 1). Anschließend entfernt er alle Eintr¨

age zu Ak-

tivit¨

ateninstanzen l∈LastActivities und zu deren

Vorg¨

angern aus MigrHistory, so dass sich die zu ¨

uber-

tragende Ablaufhistorie ergibt. Betrachten wir nochmals

das oben angesprochene Beispiel der Migration Mf,g,

bei dem in Schritt 2 die Menge LastActivities ={b}

ermittelt wurde. In Schritt 3 werden dann die Eintr¨

age

zu den Aktivit¨

ateninstanzen aund baus der lokal vor-

handenen Historie (mit Eintr¨

agen zu den Aktivit¨

aten a,

84 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

Algorithmus 2 (Quellserver: Anfordern von Ablaufhistorieneintr¨

agen)

input

SourceAct: Quellaktivit¨

ateninstanz der Migration

LastActivities: Menge der letzten am Zielserver bekannten Aktivit¨

ateninstanzen

LocalHistory: am Quellserver vorhandene Ablaufhistorie

output

MigrHistory: der bei der Migration zu ¨

ubertragende Teil der Ablaufhistorie

begin

// f¨

ur Migration sind nur Vorg¨

angeraktivit¨

aten der Quellaktivit¨

at relevant

MigrHistory =LocalHistory ∩HistoryEntries({SourceAct}∪Predecessors(SourceAct));

// Eintr¨

age zu bekannten Aktivit¨

ateninstanzen aus Ablaufhistorie entfernen

for each l∈LastActivities do

// Eintr¨

age zu lund Vorg¨

angern von laus Historie streichen

MigrHistory =MigrHistory −HistoryEntries({l}∪Predecessors(l));

end.

b,c,d,e,f) entfernt, so dass die Historieneintr¨

age der

Aktivit¨

aten c,d,e,f¨

ubertragen werden.

Wird nach der oben beschriebenen Migration Mf,g die Mi-

gration Mh,i zum selben Zielserver 2 durchgef¨

uhrt,10 so

kennt dieser Server die Eintr¨

age zu den Aktivit¨

aten a,b,c,d,

eund fbereits. Durch Anwendung von Algorithmus 1 ergibt

sich somit die Menge LastActivities ={d}. Algorithmus 2

entfernt dementsprechend die Eintr¨

age zu den Aktivit¨

aten a,

b,cund daus der f¨

ur diese Migration relevanten Historie

(mit Eintr¨

agen zu a,b,c,dund h), so dass nur die Histo-

rieneintr¨

age der Aktivit¨

at h¨

ubertragen werden. Da bei der

Migration Mf,g Historieneintr¨

age zu den Aktivit¨

aten c,d,e

und f¨

ubermittelt wurden (s.o.), findet also keine redundante

Informations¨

ubertragung statt. Im Allgemeinen ist die redun-

dante ¨

Ubertragung von Historieneintr¨

agen bei dem beschrie-

benen Verfahren stets ausgeschlossen: Ist ein Historienein-

trag zu einer Aktivit¨

at nam Zielserver der Migration bereits

bekannt, so wird dieser in der Schleife von Algorithmus 1

aus OldHistory entfernt (sonst w¨

are die Schleife noch nicht

verlassen worden). Deshalb wird der entsprechende Eintrag

beim Durchlaufen der Schleife von Algorithmus 2 auch aus

MigrHistory entfernt und damit nicht ¨

ubertragen.

5¨

Ubertragung von Datenelementen

Nachdem wir in den Abschnitten 3 und 4 untersucht ha-

ben, wie die Kontroll- bzw. Statusdaten einer Workflow-

Instanz bei Migrationen effizient ¨

ubertragen werden k¨

onnen,

wenden wir uns nun der Versorgung und ¨

Ubernahme der

Parameterdaten von Aktivit¨

atenprogrammen zu ([WMC99]:

Workflow-relevante Daten und Anwendungsdaten). In

ADEPT werden diese Daten als globale Prozessvariablen

(sog. Datenelemente) verwaltet. Die im Folgenden beschrie-

benen Verfahren lassen sich aber auch bei anderen Reali-

sierungsformen f¨

ur die Modellierung von Datenfl¨

ussen an-

wenden (z.B. bei Ein- und Ausgabencontainern wie in MQ-

Series Workflow [LR00]). Bei den in der Literatur disku-

tierten Verfahren zur Migration von Datenelementen werden

beim ¨

Ubergang zwischen zwei Partitionen ¨

ublicherweise die

Werte aller Datenelemente zur Nachfolgerpartition ¨

ubertra-

gen. Dies f¨

uhrt zu einer starken Belastung des Kommuni-

10 Wie zu Beginn dieses Abschnitts erl¨

autert, ist die ¨

uberlappende Ausf¨

uh-

rung von Migrationen ausgeschlossen. Wird in dem Beispiel die Migration

Mh,i vor Mf,g ausgef¨

uhrt, so ergibt sich dasselbe Verhalten.

kationssystems, insbesondere dann, wenn sehr große Da-

tenelemente (z.B. multimediale Dokumente) verwendet und

vom WfMS nicht nur Referenzen auf diese Daten verwaltet

werden.11 Im Folgenden werden Verfahren vorgestellt, mit

denen die bei der ¨

Ubertragung von Datenelementen entste-

hende Belastung des Kommunikationssystems deutlich re-

duziert werden kann. Bei der Entwicklung dieser Verfahren

muss beachtet werden, dass von einem WfMS sowohl recht

kleine als auch sehr große Datenelemente verwaltet werden

k¨

onnen und dass nicht jedes Verfahren f¨

ur beide F¨

alle gleich

gut geeignet ist. Zus¨

atzliche Schwierigkeiten ergeben sich

aus der Tatsache, dass die Verfahren nicht auf den Fall sta-

tischer Serverzuordnungen beschr¨

ankt sein d¨

urfen, sondern

auch bei Verwendung variabler Serverzuordnungen anwend-

bar sein m¨

ussen.

5.1 Datenhistorie

Der Wert eines globalen Datenelements kann im Verlauf

der Ausf¨

uhrung einer Workflow-Instanz mehrfach geschrie-

ben werden und sich dadurch ver¨

andern. Da die ,,¨

uber-

schriebenen“ Werte sp¨

ater bei einem eventuellen (partiellen)

Zur¨

ucksetzen noch f¨

ur die Ausf¨

uhrung von Kompensations-

aktivit¨

aten der Workflow-Instanz ben¨

otigt werden, werden

sie in ADEPT bis zu deren Beendigung aufbewahrt. Zu je-

dem Datenelement existiert deshalb eine Historie von Wer-

ten (zu denen jeweils auch die ID der schreibenden Ak-

tivit¨

ateninstanz verwaltet wird). Beim Lesen des Datenele-

ments ist nur der zuletzt von einer Vorg¨

angeraktivit¨

at des

Lesers geschriebene Wert12 g¨

ultig.13 Um das Datenvolumen

bei Migrationen zu reduzieren, wird bei allen im Folgen-

den vorgestellten Verfahren nur der jeweils aktuelle Wert

ubertragen. Dieser aktuelle Wert muss nat¨

urlich auch dann

an den Migrationszielserver ¨

ubertragen werden, wenn dort

schon ein ¨

alterer (und damit ung¨

ultiger) Wert des Datenele-

ments vorliegt. Im Falle einer (selten auftretenden) Kompen-

sation muss der bei der Ausf¨

uhrung der zu kompensierenden

Aktivit¨

at g¨

ultige Wert des Datenelements verwendet werden.

11 Die Nachteile, die sich ergeben, wenn ein WfMS nur Referenzen auf

Daten verwaltet, werden in Abschnitt 7 ausf¨

uhrlich diskutiert.

12 Da in ADEPT das Schreiben eines Datenelements durch Aktivit¨

aten

paralleler Zweige nicht erlaubt ist (Vermeidung von Lost Updates), ist dieser

Wert eindeutig identifizierbar.

13 ADEPT verfolgt hiermit bzgl. der Verwaltung und Speicherung von

Datenelementen einen ¨

ahnlichen Ansatz wie z.B. ConTracts [RS95].

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 85

Algorithmus 3 (¨

Ubertragung kleiner Datenelemente)

input

TargetAct: Zielaktivit¨

ateninstanz der Migration

SmallDataElements: Menge der am Quellserver bekannten kleinen Datenelemente

MigrHistory: der zu ¨

ubertragende Teil der Ablaufhistorie (von Algorithmus 2 ermittelt)

output

MigrDataElements: bei der Migration zu ¨

ubertragende kleine Datenelemente

begin

MigrDataElements =∅;

for each d∈SmallDataElements do

// ahat diejenige Version von dgeschrieben, die f¨

ur TargetAct g¨

ultig ist

a=LastWriter(d, TargetAct);

// der zu ageh¨

orende Ende-Historieneintrag wird bei der betrachteten Migration ¨

ubertragen

if END(a,...)∈MigrHistory then

MigrDataElements =MigrDataElements ∪{d};

end.

Dieser ist noch auf demjenigen Server vorhanden, welcher

die Aktivit¨

at kontrolliert hat.

5.2 Kleine Datenelemente

Viele der von einem WfMS verwalteten Datenelemente, wie

Integer-Werte oder kurze Strings, sind relativ ,,klein“, so

dass f¨

ur sie die im nachfolgenden Abschnitt vorgestellten

Optimierungen nicht lohnend sind. Hier macht es keinen

Sinn, die ohnehin bereits geringe Datenmenge noch wei-

ter zu reduzieren und dabei zu riskieren, dass zus¨

atzliche

Kommunikationszyklen notwendig werden. In diesem Ab-

schnitt wird ein Verfahren vorgestellt, das keine zus¨

atzlichen

Kommunikationszyklen erfordert, das ohne großen Berech-

nungsaufwand auskommt und das vermeidet, dass ein klei-

nes Datenelement von mehreren Quellservern an den Ziel-

server einer Migration ¨

ubertragen wird. Die (durchschnitt-

liche) Gr¨

oße, bis zu der ein Datenelement als klein gilt,

kann vom Administrator des WfMS konfiguriert werden, so

dass sich ein m¨

oglichst g¨

unstiges Laufzeitverhalten ergibt.

In der Regel ist es sinnvoll, ein Datenelement der Menge

der großen Datenelemente LargeDataElements zuzuord-

nen, wenn es mehrere Netzwerkpakete ausf¨

ullt. Andern-

falls wird es der in diesem Abschnitt betrachteten Menge

SmallDataElements zugeordnet.

Die Menge der bei einer Migration MSourceAct,T argetAct

zusammen mit den Ablaufhistorieneintr¨

agen MigrHistory

zu ¨

ubertragenden kleinen Datenelemente (MigrDataEle-

ments) kann mit Algorithmus 3 ermittelt werden. Er ba-

siert auf der folgenden Idee: F¨

ur alle Datenelemente d∈

SmallDataElements kann diejenige Aktivit¨

ateninstanz a

bestimmt werden, die den f¨

ur das Migrationsziel (d.h. den

f¨

ur die Zielaktivit¨

at TargetAct der Migration) g¨

ultigen Wert

von dgeschrieben hat. Diese Aktivit¨

ateninstanz kann unter

Verwendung des Workflow-Schemas und der Ablaufhistorie

der Workflow-Instanz ermittelt werden. Das Datenelement d

wird bei der betrachteten Migration genau dann ¨

ubertragen,

wenn der Historieneintrag f¨

ur die Beendigung der Aktivi-

t¨

at ain der bei der Migration ¨

ubertragenen Ablaufhistorie

MigrHistory enthalten ist (siehe Abschnitt 4.2). Da sicher-

gestellt ist, dass ein solcher Historieneintrag h¨

ochstens ein-

mal zu jedem Server ¨

ubertragen wird, gilt dies auch f¨

ur jede

Version eines Datenelements. Bei dem vorgestellten Verfah-

ren ist eine redundante ¨

Ubertragung von Datenelementen

somit ausgeschlossen. Des Weiteren wird kein zus¨

atzlicher

Kommunikationszyklus ben¨

otigt, da die Datenelemente der

Menge MigrDataElements zusammen mit der Menge der

Historieneintr¨

age MigrHistory zum Migrationszielserver

ubertragen werden. Es kann aber vorkommen, dass Datenele-

mente zu diesem Server ¨

ubertragen werden, obwohl sie dort

uberhaupt nicht ben¨

otigt werden. Da die hier betrachteten

Datenelemente klein sind, ist dies akzeptabel. Ein Verfah-

ren, bei dem solche unn¨

otigen ¨

Ubertragungen ausgeschlos-

sen sind, wird im folgenden Abschnitt f¨

ur große Datenele-

mente vorgestellt.

Angenommen, bei dem in Abb.5 dargestellten Beispiel

wird die Migration Mb,d vor Mc,d ausgef¨

uhrt. Dann werden

bei Verwendung des in Abschnitt 4.2 beschriebenen Ver-

fahrens bei der Migration Mb,d die Historieneintr¨

age der

Aktivit¨

aten aund bzum Server 2 ¨

ubertragen. Damit wird

das von Aktivit¨

at ageschriebene kleine Datenelement d1

bei dieser Migration ebenfalls transferiert. Bei der Migration

Mc,d werden die Historieneintr¨

age von Aktivit¨

at c¨

ubertra-

gen, weshalb auch das von cgeschriebene Datenelement d2

ubermittelt wird. Das Datenelement d1wird bei dieser Mi-

gration aber nicht (redundant) an den Server 2 ¨

ubertragen.

5.3 Große Datenelemente

Da f¨

ur die ¨

Ubertragung großer Datenelemente meist meh-

rere Netzwerkpakete ben¨

otigt werden, ist eine zus¨

atzliche

Kommunikation akzeptabel. Es ist außerdem sehr vorteil-

haft, wenn ein solches Datenelement bei einer Migration

nicht zum Zielserver transportiert werden muss, falls die-

ser es nicht ben¨

otigt. In dem Beispiel aus Abb.6 wird das

Datenelement d1von der Aktivit¨

at ageschrieben und von

cgelesen (aber nicht von b). Deshalb k¨

onnen Kommunika-

tionskosten eingespart werden, wenn das Datenelement d1

direkt vom Server 1 zum Server 3 transportiert wird (ohne

den Umweg ¨

uber den Server 2 der Aktivit¨

at b). Um dies zu

erm¨

oglichen, wird im Folgenden ein Verfahren entwickelt,

bei dem nicht nur die redundante ¨

Ubertragung von Datenele-

menten ausgeschlossen wird, sondern auch nur solche Da-

tenelemente zu einem Server transportiert werden, die von

diesem tats¨

achlich ben¨

otigt werden. Dies ist insbesondere

deshalb nicht trivial, weil im Falle von bedingten Verzwei-

gungen im Voraus nicht feststeht, welche Aktivit¨

aten der

Zielpartition einer Migration tats¨

achlich ausgef¨

uhrt werden,

und damit, welche Datenelemente ben¨

otigt werden.

86 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

S e r v e r 1

S e r v e r 2

Mb , d

Mc , d

S e r v e r 1

H ( a )

H ( b )

H ( c ) d2

H ( a ) d1

H ( a )

H ( b )

H ( a )

H ( c )

H ( a )

H ( b )

H ( c )

H ( d )

Abb. 5. Migration kleiner Datenelemente (Migration Mb,d wird vor Mc,d ausgef¨

uhrt).

S e r v e r 1

S e r v e r 2 S e r v e r 3

S e r v e r 4 S e r v e r 4

S e r v e r 5

A N D - S p l i t A N D - J o i n O R - S p l i t O R - J o i n

Abb. 6. ¨

Ubertragung von großen Datenelementen bei Migrationen.

5.3.1 Versenden von Datenelementen

In [Zei99] wird ein Verfahren beschrieben, bei dem – nach

Ausf¨

uhrung der ,,letzten“ Aktivit¨

at einer Partition – ein in

dieser Partition geschriebenes Datenelement an die Work-

flow-Server derjenigen Partitionen gesendet wird, in denen

dieses Datenelement potenziell gelesen wird. In dem Bei-

spiel aus Abb.6 w¨

urde das Datenelement d1also (nach Be-

endigung der letzten Aktivit¨

at a) vom Server 1 zum Server 3

gesendet, da es in dessen Partition von cgelesen wird. Die-

ses Verfahren weist allerdings einige Nachteile auf: So lassen

sich F¨

alle konstruieren, in denen (ebenso wie beim Versen-

den der Ablaufhistorie) redundante ¨

Ubertragungen auftreten.

Außerdem ist das Verfahren bei variablen bzw. dynamischen

Serverzuordnungen nicht einsetzbar. Der Grund daf¨

ur ist,

dass zum Zeitpunkt des Versendens eines Datenelements der

Server der im Ablauf evtl. erst viel sp¨

ater folgenden Ziel-

partition noch gar nicht bekannt ist. Schließlich weist die-

ses Verfahren ein schlechteres Kommunikationsverhalten auf

als der im nachfolgenden Abschnitt beschriebene Ansatz, da

ein Datenelement ausschließlich von demjenigen Workflow-

Server bezogen werden kann, auf dem es geschrieben wurde.

5.3.2 Anfordern von Datenelementen

Um die gesamte bei der Aktivit¨

atenausf¨

uhrung vorhandene

Zustandsinformation nutzen zu k¨

onnen, ist es vorteilhaft,

große Datenelemente bei einer Migration nicht zu versenden,

sondern sie anzufordern. Um dies zu realisieren, sind zwei

Verfahren denkbar: (1) Alle von einer Partition ben¨

otigten

Datenelemente werden bei ihrer Aktivierung angefordert. (2)

Vor dem Start jeder Aktivit¨

ateninstanz werden die von ihr

ben¨

otigten Datenelemente angefordert. Im Zusammenhang

mit bedingten Verzweigungen f¨

uhrt das erste Verfahren zu

Problemen, da zu Beginn einer Partition evtl. noch nicht fest-

steht, welche Datenelemente tats¨

achlich ben¨

otigt werden. Im

Folgenden gehen wir deshalb auf das zweite Verfahren n¨

aher

ein.Eine Aktivit¨

ateninstanz kann in ADEPT erst dann in den

Zustand ACTIVATED ¨

ubergehen, wenn alle eingehenden

Kanten markiert wurden. Zu diesem Zeitpunkt sind alle Vor-

g¨

angeraktivit¨

aten beendet. Deshalb kann ein Datenelement

prinzipiell vom Workflow-Server jeder Aktivit¨

at angefordert

werden, welche es geschrieben oder gelesen hat. Im Beispiel

aus Abb.6 kann das von der Aktivit¨

at hben¨

otigte Datenele-

ment d1vom Server der Aktivit¨

at aund von den Servern der

parallel ausgef¨

uhrten Aktivit¨

aten cbzw. eund fangefordert

werden. Im Allgemeinen k¨

onnen die Workflow-Server, die

uber eine bestimmte Version eines Datenelements verf¨

ugen,

mit Hilfe der zu diesem Zeitpunkt schon ¨

ubertragenen Ab-

laufhistorie (siehe Abschnitt 4.2) ermittelt werden. Das Da-

tenelement wird dann von demjenigen Workflow-Server an-

gefordert, zu dem die kosteng¨

unstigste Netzwerkverbindung

besteht. Um diesen Server bestimmen zu k¨

onnen, wird eine

,,Kommunikationskosten-Matrix“ vorgegeben, so dass ggf.

WAN-Kommunikation vermieden werden kann.

Bevor f¨

ur eine Aktivit¨

ateninstanz Datenelemente ange-

fordert werden, wird das in Abschnitt 4.2 beschriebene Ver-

fahren zur Migration von Zustandsinformation f¨

ur alle Vor-

g¨

angeraktivit¨

aten abgeschlossen (sofern diese ¨

uberhaupt von

einem fremden Workflow-Server kontrolliert wurden). So-

mit ist die relevante Ablaufhistorie f¨

ur die zu aktivierende

Aktivit¨

at ActualAct bekannt. Mit dem Algorithmus 4 kann

dann ermittelt werden, welche der von dieser Aktivit¨

at noch

ben¨

otigten Datenelemente (RequiredDataElements) von

welchem Workflow-Server angefordert werden sollen. Dazu

wird f¨

ur jedes Datenelement ddieser Menge die Aktivi-

t¨

ateninstanz wbestimmt, von welcher die f¨

ur ActualAct

g¨

ultige Version des Datenelements geschrieben wurde. Die

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 87

Algorithmus 4 (Anfordern großer Datenelemente)

input

ActualAct: die aktuell auszuf¨

uhrende Aktivit¨

ateninstanz

LargeDataElements: Menge der großen Datenelemente

LocalDataElements: Menge der auf dem lokalen Server schon vorhandenen Datenelemente

output

OptServers: Menge von Tupeln <d,s>, die angeben, von welchem Server sdas große

Datenelement dangefordert werden soll

begin

OptServers =∅;

// Menge der von der Aktivit¨

ateninstanz ActualAct gelesenen großen Datenelemente

RequiredDataElements ={d∈LargeDataElements |d∈ReadSet(ActualAct)};

// schon auf dem lokalen Server vorhandene Datenelemente nicht mehr anfordern

RequiredDataElements =RequiredDataElements −LocalDataElements;

for each d∈RequiredDataElements do

// what diejenige Version von dgeschrieben, die f¨

ur ActualAct g¨

ultig ist

w=LastWriter(d, ActualAct);

// Renth¨

alt diejenigen Aktivit¨

ateninst., die das von wgeschriebene Datenelement dgelesen haben

R={r|w∈Predecessors(r)∧r∈Reader(d)};

// sopt ist der bzgl. der Kommunikationskosten vom lokalen Server aus am g¨

unstigsten erreichbare

// Server, von dem dbezogen werden kann

Sources ={Server(w)}∪{Server(r)|r∈R};

w¨

ahle sopt ∈Sources mit CommQual(Server(ActualAct),s opt) ist minimal;

OptServers =OptServers ∪{<d,sopt >};

end.

Aktivit¨

at wist also der ,,letzte“ Vorg¨

anger von ActualAct,

der das Datenelement dgeschrieben hat. Vom Workflow-

Server dieser Aktivit¨

at k¨

onnte das Datenelement nun ange-

fordert werden. Dar¨

uber hinaus verf¨

ugen auch die Server

aller Aktivit¨

ateninstanzen r∈R, welche diese Version des

Datenelements gelesen haben, ¨

uber dessen aktuellen Wert.

Diese Aktivit¨

aten r∈Rsind diejenigen, welche lesend auf

dzugegriffen haben und außerdem im Kontrollfluss auf w

folgen. Das Datenelement dkann also vom Workflow-Server

der Aktivit¨

at wund von den Servern der Aktivit¨

aten r∈R

angefordert werden. Von diesen Servern s∈Sources wird

derjenige ausgew¨

ahlt, der die bzgl. der Kommunikations-

kosten g¨

unstigste Verbindung zu dem Server aufweist, der

ActualAct kontrolliert und damit der Empf¨

anger des Da-

tenelements ist.

Bei dem vorgestellten Verfahren k¨

onnten Datenelemente

redundant ¨

ubertragen werden, wenn durch einen Workflow-

Server f¨

ur mehrere parallele Zweige dasselbe Datenelement

angefordert w¨

urde. Dies wird verhindert, indem Datenele-

mente derselben Workflow-Instanz nicht ¨

uberlappend ange-

fordert werden. Dann kann es zu keiner redundanten ¨

Uber-

tragung kommen, da nur Versionen von Datenelementen an-

gefordert werden, die auf dem Zielserver noch nicht vor-

handen sind. So wird in dem Beispiel aus Abb.6 bei der

Aktivierung der Aktivit¨

at fdas Datenelement d1nicht an-

gefordert, weil es von der Aktivit¨

at egelesen wurde und

deshalb auf diesem Server schon vorhanden ist. Ein Daten-

element wird erst bei der Aktivierung derjenigen Aktivit¨

angefordert, welche es liest. Dies hat den Vorteil, dass es nur

dann ¨

ubertragen werden muss, wenn diese Aktivit¨

at auch

tats¨

achlich aktiviert wird. Wird in dem Beispiel aus Abb.6

der Zweig mit der Aktivit¨

at hnicht gew¨

ahlt, so ben¨

otigt der

Server 5 das Datenelement d1nicht. Bei dem vorgestellten

Verfahren wird d1durch den Server 5 dann auch nicht ange-

fordert. Der Algorithmus 4 wird n¨

amlich f¨

ur ActualAct =h

niemals ausgef¨

uhrt, da die Aktivit¨

at hnicht aktiviert wird.

Dass große Datenelemente f¨

ur jede Aktivit¨

ateninstanz

einzeln angefordert werden, f¨

uhrt zu einer Verz¨

ogerung bei

der Aktivierung dieser Aktivit¨

ateninstanz. Da die Aktivit¨

zu diesem Zeitpunkt noch nicht in die Arbeitslisten der Be-

nutzer eingetragen wurde, bemerken diese die Verz¨

ogerung

nicht. Die Verz¨

ogerungen erh¨

ohen zwar die Ausf¨

uhrungszeit

des Workflows, sie fallen aber im Vergleich zur Gesamt-

ausf¨

uhrungszeit (Tage oder Wochen) nicht ins Gewicht. Ist

ein Workflow-Server, von dem ein Datenelement angefor-

dert werden soll, f¨

ur l¨

angere Zeit nicht erreichbar, so kann

dies die Verf¨

ugbarkeit des WfMS verschlechtern. Um dem

entgegenzuwirken, sollte das Datenelement in diesem Fall

(falls m¨

oglich) von einem anderen Server aus der Menge

Sources angefordert werden. Da die von einer Aktivit¨

ben¨

otigen Datenelemente erst bei ihrer Aktivierung ange-

fordert werden, entsteht ein Problem, wenn disconnected

Clients [AGK+96] verwendet werden. Diese verf¨

ugen ¨

uber

einen eigenen Workflow-Server und sollen evtl. mehrere

Aktivit¨

aten ausf¨

uhren k¨

onnen, ohne mit anderen Workflow-

Servern zu kommunizieren. Deshalb m¨

ussen die Datenele-

mente, die von den im Disconnected-Modus auszuf¨

uhrenden

Aktivit¨

aten ben¨

otigt werden, schon vor dem Verbindungs-

abbau angefordert werden. Dabei muss in Kauf genommen

werden, dass auch Datenelemente f¨

ur m¨

oglicherweise nicht

ausgef¨

uhrte Aktivit¨

aten (z.B. Aktivit¨

at haus Abb.6) an-

gefordert werden m¨

ussen. Dieser Nachteil tritt aber auch

bei klassischen Verfahren zur Migration von Datenelemen-

ten auf, dann aber nicht nur im Disconnected-Modus.

6 Effektivit¨

at der vorgestellten Verfahren

In [BD99] wurde anhand von Simulationen bereits gezeigt,

dass eine verteilte Workflow-Ausf¨

uhrung bzgl. der Kommu-

nikationskosten in vielen F¨

allen wesentlich g¨

unstiger ist als

eine zentrale Workflow-Steuerung mit zentraler Datenhal-

88 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

Loop

S e r v e r 1

3 0

. . .

S e r v e r 2

. . .

S e r v e r 3

. . .

S e r v e r 4

. . .

Abb. 7. Dem Zahlenbeispiel zugrunde liegender Workflow.

tung. Das bedeutet, dass das Konzept der Partitionierung

von Workflow-Schemata zur Modellierungszeit und die da-

mit verbundenen Migrationen zur Ausf¨

uhrungszeit generell

notwendig sind.

Es bleibt zu evaluieren, ob die im vorliegenden Beitrag

vorgestellten Verfahren geeignet sind, das bei Migrationen

zu ¨

ubertragende Datenvolumen gegen¨

uber einer konventio-

nellen Realisierung zu reduzieren. Diese Evaluation wol-

len wir im Folgenden anhand eines Zahlenbeispiels vorneh-

men. Hierzu wird der in der Praxis sehr relevante Fall eines

Workflows mit Schleifen betrachtet. Schleifen werden z.B.

zur Realisierung zahlreicher Krankenhausprozesse [DRK00]

ben¨

otigt, etwa f¨

ur Chemotherapie-Behandlungsprozesse, die

ublicherweise mehrere (identische) Behandlungszyklen um-

fassen. Ein solcher Zyklus kann seinerseits mehrere Organi-

sationseinheiten involvieren, mehrere Tage dauern und meh-

rere Dutzend Aktivit¨

aten umfassen [Sch96]. Aus Gr¨

unden

der besseren Lesbarkeit verzichten wir im Folgenden auf die

Darstellung eines solchen komplexen Prozesses und w¨

ahlen

stattdessen eine abstrakte Darstellung. Bei Prozessen ohne

Iterationen existiert in der Regel ein kleineres Optimierungs-

potential, dessen konkrete Gr¨

oße davon abh¨

angt, wieviele

und welche Partitionen einer Workflow-Instanz vom selben

Workflow-Server kontrolliert werden.

Im Folgenden sei der Workflow aus Abb.7 gegeben. Wir

betrachten die Migration M2vom Server 2 zu der vom Ser-

ver 3 kontrollierten Partition, die aus den f¨

unf Aktivit¨

aten

c1bis c5besteht. Diese Aktivit¨

aten befinden sich innerhalb

einer Schleife, die insgesamt 15 Aktivit¨

aten umfasst. Vor der

Schleife befinden sich die 30 Aktivit¨

aten a1...a

30.

Zuerst wollen wir die f¨

ur die ¨

Ubertragung von Workflow-

Kontrolldaten (siehe Abschnitt 4.2) entstehenden Kosten ei-

ner konventionellen mit denen einer optimierten Migration

vergleichen. Dabei wird pessimistischerweise angenommen,

dass der Workflow bei der ersten Iteration der Schleife zum

ersten Mal vom Server 3 kontrolliert wird, so dass bei

der entsprechenden Migration keine Optimierungen m¨

oglich

sind. Bei jeder weiteren Iteration sind dem Server 3 die

Ablaufhistorieneintr¨

age der Aktivit¨

aten a1...a

30 schon be-

kannt. Außerdem kennt er bereits die Eintr¨

age zu den Akti-

vit¨

aten b1...b

5und c1...c

5der direkten Vorg¨

angeriteration.

F¨

ur alle davor liegenden Schleifendurchl¨

aufe sind ihm die

Eintr¨

age zu den Aktivit¨

aten b1...b

5,c1...c

5und d1...d

bekannt. Nehmen wir nun an, dass (durchschnittlich) n=10

Iterationen der Schleife ausgef¨

uhrt werden.

Bei einer konventionellen Realisierung der Migration

entsteht der folgende ¨

Ubertragungaufwand:

1. Iteration: 30 Eintr¨

age14 (f¨

ur a1...a

30) + 5 Eintr¨

age (f¨

b1...b

5) = 35 Eintr¨

age

F¨

ur jede weitere Iteration kommen bei der entsprechen-

14 Bei der hier durchgef¨

uhrten Analyse werden der Einfachheit halber die

Eintr¨

age f¨

ur das Starten und das Beenden einer Aktivit¨

ateninstanz wie ein

einziger (gr¨

oßerer) Eintrag behandelt.

den Migration 15 zus¨

atzliche Eintr¨

age f¨

ur die zuletzt aus-

gef¨

uhrten Instanzen der Aktivit¨

aten c1...c

5,d1...d

5und

b1...b

5hinzu. Bei der Iteration im¨

ussen also 35+15·(i−1)

Eintr¨

age migriert werden. Damit ergibt sich als die Anzahl

der bei der Migration M2insgesamt (f¨

ur alle nIterationen)

zu ¨

ubertragenden Historieneintr¨

age:



i=1 35+15·(i−1)=35·n+15·(n−1) ·n

Werden die vorgestellten Optimierungsverfahren verwen-

det, so m¨

ussen bei der 1. Iteration ebenfalls 35 Histori-

eneintr¨

age ¨

ubermittelt werden. Bei jeder weiteren Iteration

werden aber nur die 10 neu hinzugekommenen Eintr¨

age

f¨

ur die Aktivit¨

aten d1...d

5und b1...b

5migriert. Damit

ergibt sich als Gesamtzahl der zu ¨

ubertragenden Eintr¨

age:

35+10·(n−1)

Zus¨

atzlich muss bei jeder Migration die ID der letzten be-

kannten Aktivit¨

ateninstanz (c5)¨

ubertragen werden, was die

Ubertragung von insgesamt nIDs erfordert.

Da wir n= 10 Iterationen annehmen, m¨

ussen aufgrund

der Optimierungen lediglich 125 Historieneintr¨

age und 10

IDs anstelle von 1025 Eintr¨

agen ¨

ubermittelt werden. Neh-

men wir weiter an, dass f¨

ur einen Ablaufhistorieneintrag

200 Byte erforderlich sind. Dies ist eher niedrig angesetzt,

da ein solcher Eintrag außer der ID der zugeh¨

origen Aktivi-

t¨

ateninstanz und WfMS-intern genutzter Information [RD98]

noch weitere Daten, wie den Bearbeiter, die Start- und Ende-

zeit und den Workflow-Server der Aktivit¨

at enth¨

alt. Nehmen

wir ferner an, dass die ID eines solchen Eintrags 8 Byte lang

ist. Dann m¨

ussen aufgrund der Optimierungen nur 25,08 kB

anstelle von 205 kB ¨

ubertragen werden. In diesem Beispiel

erm¨

oglichen die vorgestellten Verfahren also eine Reduk-

tion der zu ¨

ubertragenden Kontrolldaten um 88%. Die ent-

sprechende Einsparung entsteht f¨

ur jede einzelne Workflow-

Instanz alleine bzgl. der Migrationen M2vom Server 2 zum

Server 3.

Die Migrationen von kleinen Datenelementen (siehe Ab-

schnitt 5.2) ist an die ¨

Ubertragung von Historieneintr¨

agen

gekoppelt. Deshalb ergibt sich f¨

ur sie dieselbe prozentuale

Lastreduktion. Die ¨

Ubertragung der IDs der letzten bekann-

ten Historieneintr¨

age ist bei dem Verfahren jedoch nicht

nochmals notwendig, so dass sich sogar ein geringf¨

ugig bes-

seres Ergebnis ergibt.

Zus¨

atzlich entsteht eine Lastreduktion durch das in Ab-

schnitt 5.3 vorgestellte Verfahren zur ¨

Ubertragung von

großen Datenelementen (z.B. ein Satz von Computerto-

mographie-Bildern in einem Krankenhausprozess oder eine

technische Zeichnung in einem verteilten Entwicklungspro-

zess). F¨

ur die nun durchgef¨

uhrte Analyse nehmen wir an,

dass in dem Gesamtprozess f¨

unf große Datenelemente mit

einer Gr¨

oße von jeweils 5MB verwendet werden. Von die-

sen werden drei Datenelemente f¨

ur die Ausf¨

uhrung der hier

betrachteten Aktivit¨

aten c1...c

5ben¨

otigt. Bei Verwendung

des vorgestellten Verfahrens werden in der ersten Iteration

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 89

nur drei Datenelemente angefordert, anstatt dass alle f¨

unf

ubertragen werden. Dadurch ergibt sich eine Reduktion der

Datenmenge von 25MB auf 15MB.15 Nehmen wir nun

an, dass in jeder Iteration zwei der drei von den Aktivi-

t¨

aten c1...c

5ben¨

otigten Datenelemente durch die Aktivi-

t¨

aten b1...b

5bzw. d1...d

5ver¨

andert werden. Dann m¨

ussen

bei jeder weiteren Iteration die diesen beiden Datenelemen-

ten entsprechenden 10MB ¨

ubertragen werden. Eine konven-

tionelle Realisierung der Migrationen w¨

urde auch bei jeder

weiteren Iteration die ¨

Ubertragung von 25MB erforderlich

machen. Insgesamt m¨

ussen aufgrund der optimierten ¨

Uber-

tragung von großen Datenelementen also nur 105MB an-

stelle von 250MB transferiert werden. Dies entspricht einer

Reduktion um 58%. Damit wurde gezeigt, dass die in den

Abschnitten 4 und 5 vorgestellten Verfahren geeignet sind,

die bei Migrationen ¨

ubertragene Datenmenge signifikant zu

reduzieren.

7 Diskussion

In dieser Arbeit verzichten wir aus Platzgr¨

unden auf einen

ausf¨

uhrlichen ¨

Uberblick ¨

uber verteilte WfMS (siehe hierzu

[BD99]). Stattdessen diskutieren wir, wie bzw. welche Work-

flow-Daten bei den anderen in der Workflow-Literatur dis-

kutierten Verteilungsans¨

atzen ¨

ubertragen werden und welche

Auswirkungen dies auf die entstehenden Migrationskosten

hat. Auf zentrale WfMS (z.B. Panta Rhei [EG96], WASA

[VW97], [DHL91]) und verteilte Ans¨

atze, bei denen eine

Workflow-Instanz stets nur von einem einzigen Workflow-

Server kontrolliert wird (z.B. Exotica/Cluster [AKA+94],

MOBILE [Jab97]), gehen wir nicht weiter ein, da hier keine

Daten¨

ubertragung zwischen den Workflow-Servern stattfin-

det.In der Literatur werden verteilte WfMS beschrieben, bei

denen die Laufzeitdaten einer Workflow-Instanz bei Migra-

tionen vollst¨

andig ¨

ubertragen werden: So wird bei CodAlf

und BPAFrame (siehe [SM96]) eine Workflow-Instanz als

Objekt repr¨

asentiert (inkl. internem Zustand, Datenelemen-

ten und der Definition des zugeh¨

origen Workflow-Schemas),

welches zwischen den Workflow-Servern migriert. Auch bei

INCAS [BMR96] wurde ein solcher Objektmigrationsan-

satz gew¨

ahlt, allerdings erfolgt die Workflow-Definition hier

durch Regeln. Da zus¨

atzlich zu den schon genannten Da-

ten auch noch die alten Versionen der Datenelemente (vgl.

Datenhistorie aus Abschnitt 5.1) im migrierten Objekt ent-

halten sind, erh¨

oht sich die bei Migrationen zu ¨

ubertragende

Datenmenge weiter.

Es gibt aber auch Ans¨

atze, die nicht nur bei Migratio-

nen Daten ¨

ubertragen: Bei Exotica/FMQM [AMG+95] wer-

den die von einer Aktivit¨

ateninstanz geschriebenen Daten-

elemente an diejenigen Systemkomponenten versendet, die

Aktivit¨

ateninstanzen kontrollieren, welche diese Datenele-

mente lesen (vgl. ,,Versenden von Datenelementen“ in Ab-

schnitt 5.3.1). Die verteilte Workflow-Ausf¨

uhrung in MEN-

TOR [WWK+97] basiert auf der Partitionierung von State-

15 Die f¨

ur die Optimierung zus¨

atzlich notwendige ¨

Ubertragung der drei

IDs der Datenelemente f¨

allt bei diesen Datenmengen nicht ins Gewicht. Ein

zus¨

atzlicher Vorteil ergibt sich bei der Optimierung jedoch dadurch, dass

die Datenelemente von demjenigen Server angefordert werden k¨

onnen, zu

dem die kosteng¨

unstigste Kommunikationsverbindung besteht.

und Activitycharts. Um eine zum zentralen Fall ¨

aquivalente

verteilte Ausf¨

uhrung garantieren zu k¨

onnen, m¨

ussen nach

der Beendigung von parallel ausgef¨

uhrten Aktivit¨

aten Syn-

chronisationsnachrichten und Datenelemente ausgetauscht

werden. Da dies einen großen Kommunikationsaufwand er-

fordert, werden in [MWW+98] Verfahren vorgestellt, mit de-

nen dieser Aufwand reduziert werden kann. Es wird also

nicht das Ziel verfolgt, den Kommunikationsaufwand bei

Migrationen zu reduzieren, sondern der Aufwand f¨

ur die

Synchronisation der Workflow-Server bei parallel ausge-

f¨

uhrten Aktivit¨

aten wird begrenzt. Eine solche Synchroni-

sation der Workflow-Abarbeitung ist in ADEPT nicht not-

wendig, da die Bearbeitung paralleler Zweige unabh¨

angig

voneinander fortschreiten kann. In [GWWK00] wird, basie-

rend auf warteschlangentheoretischen Untersuchungen, ana-

lysiert, welche Konfiguration f¨

ur ein verteiltes WfMS am

g¨

unstigsten ist. Hierbei werden auch Verf¨

ugbarkeitsfragestel-

lungen einbezogen. Allerdings wird der Aspekt der Kommu-

nikationskosten nicht betrachtet.

Einige Ans¨

atze verwenden keine Partitionierung und Mi-

grationen im eigentlichen Sinn, sondern starten Subpro-

zesse auf einem entfernten Workflow-Server. Bei einer Er-

weiterung von MOBILE [SNS99] wird zur Ausf¨

uhrungs-

zeit der Workflow-Instanzen entschieden, welcher Work-

flow-Server einen Sub-Workflow kontrollieren soll. Auch

WIDE [CGP+96] erreicht Verteilung durch die entfernte

Ausf¨

uhrung von Subprozessen. Diese Vorgehensweise hat

den Vorteil, dass an einen Sub-Workflow nur die von ihm

potenziell ben¨

otigten Daten ¨

ubergeben werden m¨

ussen, an-

statt dass alle Daten der Workflow-Instanz migriert werden.

Dies f¨

uhrt zu einem ¨

ahnlichen Effekt wie bei den in die-

ser Arbeit vorgestellten Optimierungen. Eine ausschließlich

auf Subprozessen basierende Verteilung wurde f¨

ur ADEPT

allerdings nicht gew¨

ahlt, weil die Workflow-Kontrolle nach

Beendigung jedes Sub-Workflows zum Server des Super-

Workflows zur¨

uckkehren w¨

urde (auch wenn dies eigentlich

nicht erw¨

unscht ist) und die Ver¨

anderung einer Verteilung

aufwendiger w¨

are (weil dazu eine andere Aufteilung in Sub-

prozesse ben¨

otigt wird).

Bei WIDE [CGP+96] werden Datenelemente nicht direkt

an andere Workflow-Server ¨

ubergeben, sondern nur Referen-

zen auf sie. Diese Vorgehensweise ist h¨

aufig bei solchen Sys-

temen zu finden, die wie WIDE auf einer objektorientierten

Systeminfrastruktur (z.B. CORBA) basieren, da diese den

ortstransparenten Zugriff auf die eigentlichen Datenelemente

erlaubt. Bei METEOR2[DKM+97] steuert ein sog. ,,Task-

manager“ die Ausf¨

uhrung eines bestimmten Aktivit¨

atentyps

und signalisiert den Taskmanagern der Nachfolgeraktivit¨

aten

deren Beendigung. Zugriffe auf Datenelemente erfolgen orts-

transparent durch CORBA. Dasselbe gilt f¨

ur die Systeme

METUFlow [GAC+97], MOKASSIN [GJS+99] und WASA2

[Wes99, WHKS98], bei denen eine Aktivit¨

ateninstanz je-

weils durch ein CORBA-Objekt repr¨

asentiert wird. Da bei

all diesen Ans¨

atzen lediglich Referenzen auf die Datenele-

mente migriert werden, wird zwar die Belastung des WfMS

reduziert, aber nicht die des Kommunikationssystems. Ein

großes Datenelement wird dann nicht nur einmal (durch eine

Migration) in das Teilnetz transportiert, in dem es ben¨

otigt

wird, sondern muss bei jedem einzelnen Zugriff eines Aktivi-

t¨

atenprogramms ¨

ubertragen werden. Dies f¨

uhrt, insbesondere

90 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

in einer weitr¨

aumig verteilten Umgebung, zu einer h¨

oheren

Belastung des Kommunikationssystems.

Eine Fragestellung, die mit der Migration von Zustands-

information in einem verteilten WfMS verwandt ist, wird

von CoAct [WK96] untersucht: Mehrere Personen ver¨

andern

verteilt und parallel dasselbe Dokument, so dass mehrere

g¨

ultige ¨

Anderungshistorien entstehen. Diese werden (wie die

Ablaufhistorien in ADEPT) wieder zu einer einzigen His-

torie zusammengef¨

uhrt (sog. History Merge). Ebenso wie

bei ADEPT wird dabei die jeweilige Semantik der Histori-

eneintr¨

age ausgenutzt.

Zusammenfassend l¨

asst sich feststellen, dass in der Li-

teratur zahlreiche Ans¨

atze f¨

ur verteiltes Workflow-Manage-

ment vorgestellt werden. Allerdings werden bei keinem von

ihnen die bei Migrationen anfallenden Kommunikationskos-

ten – wie bei den in diesem Beitrag vorgestellten Verfahren –

minimiert. Die Ans¨

atze ignorieren weitgehend die in einem

verteilten WfMS anfallenden hohen Kommunikationskosten.

Manche der Ans¨

atze treffen aber Entwurfsentscheidungen,

die auch Einfluss auf die entstehenden Kommunikationskos-

ten haben: (1) Bei Migrationen werden nur Referenzen auf

Datenelemente ¨

ubergeben. Dies f¨

uhrt zu den in diesem Ab-

schnitt schon diskutierten Nachteilen. (2) Bei Migrationen

wird keine explizite Zustandsinformation ¨

ubergeben (es wer-

den lediglich die Nachfolgeraktivit¨

aten ¨

uber die Beendigung

der Aktivit¨

ateninstanz informiert). Dies f¨

uhrt dazu, dass

keine Information ¨

uber beendete Aktivit¨

aten verf¨

ugbar ist,

was die Realisierung fortschrittlicher Workflow-Konzepte,

wie abh¨

angige Bearbeiterzuordnungen und die ¨

Uberwachung

von Zeitbedingungen, beeintr¨

achtigt.

8 Zusammenfassung

Durch die Verwendung von WfMS kann die Entwicklung

von unternehmensweiten und -¨

ubergreifenden prozessorien-

tierten Anwendungssystemen erheblich erleichtert werden,

da der Programmcode einzelner Anwendungsfunktionen von

der Prozesslogik getrennt wird. Dadurch wird die Entwick-

lung von solchen Anwendungssystemen mit vertretbarem

Aufwand ¨

uberhaupt erst m¨

oglich. Bei zahlreichen Anwen-

dungen muss die Workflow-Steuerung verteilt realisiert wer-

den, weil ein zentraler Workflow-Server ¨

uberlastet w¨

are. Ab-

gesehen davon lassen sich durch eine geeignete Verteilung

der Workflow-Steuerung die Kommunikationskosten redu-

zieren, indem ein Workflow-Server ,,nahe“ bei den Bear-

beitern der aktuellen Aktivit¨

at gew¨

ahlt wird [BD97, BD00].

Allerdings entstehen durch die bei der verteilten Workflow-

Ausf¨

uhrung notwendigen Migrationen gewisse Kommunika-

tionskosten, die reduziert werden m¨

ussen, um ein effizientes

verteiltes Workflow-Management zu erm¨

oglichen.

In diesem Beitrag wurden Verfahren vorgestellt, mit de-

nen das bei Migrationen zu ¨

ubertragende Datenvolumen

drastisch reduziert werden kann (vgl. Abschnitt 6). Mit

diesen Verfahren wird sowohl die redundante ¨

Ubertragung

interner Zustandsinformation als auch der Parameterdaten

von Aktivit¨

atenprogrammen verhindert. Kleine Datenele-

mente werden anders behandelt als große, welche stets von

demjenigen Workflow-Server bezogen werden, zu dem die

beste Kommunikationsverbindung besteht. Die Verfahren

sind f¨

ur statische und f¨

ur variable Serverzuordnungen glei-

chermaßen geeignet und ber¨

ucksichtigen alle Konstrukte des

ADEPT-Modells (z.B. bedingte und parallele Verzweigun-

gen, Schleifen). Sie sollten deshalb auch auf andere Mo-

delle ¨

ubertragbar sein. Insbesondere im Zusammenhang mit

Schleifen kann die Belastung des dem WfMS zugrunde lie-

genden Kommunikationssystems drastisch reduziert werden,

weil mehrere Instanzen einer Aktivit¨

at vom selben Server

kontrolliert werden, so dass bereits viel Information lokal

vorhanden ist. Allerdings haben die vorgestellten Optimie-

rungen auch ihren Preis: Die Anwendung der vorgestellten

Verfahren erfordert zus¨

atzlichen Rechenaufwand. Sie soll-

ten deshalb nur in Umgebungen eingesetzt werden, in de-

nen dieser Aufwand durch die Entlastung des Kommuni-

kationssystems gerechtfertigt wird. F¨

ur weitr¨

aumig verteilte

Anwendungen ist dies sehr h¨

aufig der Fall. Die vorgestellten

Verfahren reduzieren die zu ¨

ubertragende Datenmenge durch

die Nutzung von Wissen ¨

uber schon transferierte Daten.

Dadurch l¨

asst sich in einigen F¨

allen eine deutlich st¨

arkere

Reduktion der Datenmenge erreichen als mit klassischen

Komprimierungsverfahren. Selbstverst¨

andlich kann mit die-

sen die zu ¨

ubertragende Datenmenge aber noch weiter redu-

ziert werden.

Verschiedene weitere Aspekte, wie das zugrunde gelegte

Fehlermodell, die Art der Kommunikation oder das Trans-

aktionsmanagement, haben ebenfalls Einfluss auf die bei der

verteilten Workflow-Steuerung entstehenden Kommunikati-

onskosten. Da diese Aspekte aber zu den hier betrachteten

Fragestellungen weitgehend orthogonal sind, gehen wir nicht

n¨

aher auf sie ein. Kommunikationskosten lassen sich auch

reduzieren, indem Workflow-Schemata (bzgl. ihrer Graph-

struktur oder ihrer Bearbeiterzuordnungen) ver¨

andert wer-

den, oder indem die Position einzelner Benutzer im Kom-

munikationsnetzwerk ver¨

andert wird. Solche Modifikationen

sind normalerweise aber nicht akzeptabel, da die Ver¨

ande-

rung von (hoffentlich) optimierten Prozessen in der Regel

negative Auswirkungen auf wichtige Gr¨

oßen wie Prozess-

kosten oder Durchlaufzeiten hat. Es ist wesentlich g¨

unstiger,

die vorgestellten Optimierungen zu verwenden, da diese

keine f¨

ur den Benutzer sichtbaren Auswirkungen haben.

Die in diesem Beitrag beschriebenen Verfahren wur-

den in dem Prototypen ADEPTworkflow [HRB+00] imple-

mentiert. ADEPTworkflow wurde auf der CeBIT’2000, der

EDBT’2000 und der BIS’2000 demonstriert. Durch die Im-

plementierung konnte die Umsetzbarkeit der Verfahren ge-

zeigt und ihr Zusammenspiel mit andern Konzepten (z.B.

dynamischen Workflow- ¨

Anderungen) studiert werden. An-

hand der tats¨

achlich bei Migrationen einer Workflow-Instanz

ubertragenen Datenmenge ist außerdem zu erkennen, dass

die Belastung des Kommunikationssystems deutlich redu-

ziert werden kann.

Danksagung. Wir danken Clemens Hensinger und Jochen Zeitler f¨

ur die

anregenden Diskussionen.

References

[AGK+96] G. Alonso, R. G¨

unth¨

or, M. Kamath, D. Agrawal, A. El Ab-

badi, C. Mohan: Exotica/FMDC: A Workflow Management

System for Mobile and Disconnected Clients. Distributed and

Parallel Databases, 4(3): 229–247 (1996)

T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten 91

[AKA+94] G. Alonso, M. Kamath, D. Agrawal, A. El Abbadi, R.

G¨

unth¨

or, C. Mohan: Failure Handling in Large Scale Work-

flow 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 Ab-

badi, M. Kamath: Exotica/FMQM: A Persistent Message-

Based Architecture for Distributed Workflow Management.

In: Proc. IFIP Working Conf. on Information Systems for

Decentralized Organisations, Trondheim, August 1995

[BD97] T. Bauer, P. Dadam: A Distributed Execution Environment

for Large-Scale Workflow Management Systems with Sub-

nets and Server Migration. In: Proc. 2nd IFCIS Conf. on Co-

operative Information Systems, pp.99–108, Kiawah Island,

SC, Juni 1997

[BD99] T. Bauer, P. Dadam: Verteilungsmodelle f¨

ur Workflow-

Management-Systeme – Klassifikation und Simulation. In-

formatik Forschung und Entwicklung, 14(4): 203–217 (1999)

[BD00] T. Bauer, P. Dadam: Efficient Distributed Workflow Manage-

ment Based on Variable Server Assignments. In: Proc.

12th Conf. on Advanced Information Systems Engineering,

pp.94–109, Stockholm, Juni 2000

[BF99] E. Bertina, E. Ferrari: The Specification and Enforcement

of Authorization Constraints in Workflow Management Sys-

tems. ACM Trans. Inform. Syst. Sec., 2(1): 65–104 (1999)

[BMR96] D. Barbar´

a, S. Mehrotra, M. Rusinkiewicz: INCAs: Mana-

ging Dynamic Workflows in Distributed Environments. Jour-

nal of Database Management, Special Issue on Multidataba-

ses, 7(1): 5–15 (1996)

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

anchez:

WIDE: Workflow Model and Architecture. CTIT Technical

Report 96–19, University of Twente, 1996

[DHL91] U. Dayal, M. Hsu, R. Ladin: A Transactional Model for

Long-Running Activities. In: Proc. 17th Int. Conf. on Very

Large Data Bases, pp.113–122, Barcelona, September 1991

[DKM+97] S. Das, K. Kochut, J. Miller, A. Sheth, D. Worah: ORBWork:

A Reliable Distributed CORBA-based Workflow Enactment

System for METEOR2. Technical Report #UGA-CS-TR-97-

001, Department of Computer Science, University of Geor-

gia, Februar 1997

[DRK00] P. Dadam, M. Reichert, K. Kuhn: Clinical Workflows – The

Killer Application for Process-oriented Information Systems?

In: Proc. 4th Int. Conf. on Business Information Systems,

pp.36–59, Posen, April 2000

[EG96] J. Eder, H. Groiss: Ein Workflow-Managementsystem auf

der Basis aktiver Datenbanken. In: J. Becker, G. Vossen

(Herausgeber): Gesch¨

aftsprozeßmodellierung und Workflow-

Management. Int. Thomson Publishing, 1996

[GAC+97] E. Gokkoca, M. Altinel, I. Cingil, E.N. Tatbul, P. Koksal, A.

Dogac: Design and Implementation of a Distributed Work-

flow Enactment Service. In: Proc. 2nd IFCIS Conf. on Coope-

rative Information Systems, pp.89–98, Kiawah Island, SC,

Juni 1997

[GJS+99] B. Gronemann, G. Joeris, S. Scheil, M. Steinfort, H. Wache:

Supporting Cross-Organizational Engineering Processes by

Distributed Collaborative Workflow Management - The MO-

KASSIN Approach. In: Proc. 2nd Symposium on Concurrent

Multidisciplinary Engineering, 3rd Int. Conf. on Global En-

gineering Networking, Bremen, September 1999

[Gri97] M. Grimm: ADEPTtime: Temporale Aspekte in flexiblen

Workflow-Management-Systemen. Diplomarbeit, Universit¨

Ulm, Fakult¨

at f¨

ur Informatik, 1997

[GWWK00] M. Gillmann, J. Weissenfels, G. Weikum, A. Kraiss: Per-

formance and Availability Assessment for the Configuration

of Distributed Workflow Management Systems. In: Proc. 7th

Int. Conf. on Extending Database Technology, pp.183–201,

Konstanz, M¨

arz 2000

[HRB+00] C. Hensinger, M. Reichert, T. Bauer, T. Strzeletz, P. Dadam:

ADEPTworkflow - Advanced Workflow Technology for the

Efficient Support of Adaptive, Enterprise-wide Processes. In:

7th Int. Conf. on Extending Database Technology, Software

Demonstrations Track, pp.29–30, Konstanz, M¨

arz 2000

[Jab97] S. Jablonski: Architektur von Workflow-Management-

Systemen. Informatik Forsch. Entw. Themenheft Workflow-

Management, 12(2): 72–81 (1997)

[KAGM96] M. Kamath, G. Alonso, R. G¨

unth¨

or, C. Mohan: Providing

High Availability in Very Large Workflow Management Sys-

tems. In: Proc. 5th Int. Conf. on Extending Database Tech-

nology, pp.427–442, Avignon, M¨

arz 1996

[KDB98] M. Klein, C. Dellaroca, A. Bernstein (Herausgeber): Work-

shop Towards Adaptive Workflow Systems, Conf. on

Computer-Supported Cooperative Work, Seattle, WA, No-

vember 1998

[Kub98] M. Kubicek: Organisatorische Aspekte in flexiblen Work-

flow-Management-Systemen. Diplomarbeit, Universit¨

at Ulm,

Fakult¨

at f¨

ur Informatik, 1998

[Ley97] F. Leymann: Transaktionsunterst¨

utzung f¨

ur Workflows. In-

formatik Forsch. Entw. Themenheft Workflow-Management,

12(2): 82–90 (1997)

[LR00] F. Leymann, D. Roller: Production Workflow – Concepts and

Techniques. Englewood Cliffs, NJ: Prentice Hall, 2000

[MO99] O. Marjanovic, M. Orlowska: On Modeling and Verification

of Temporal Constraints in Production Workflows. Know-

ledge and Information Systems, 1(2): 157–192 (1999)

[MWW+98] P. Muth, D. Wodtke, J. Weißenfels, A. Kotz-Dittrich, G. Wei-

kum: From Centralized Workflow Specification to Distributed

Workflow Execution. J. Intell. Inform. Syst., Special Issue

on Workflow Management Systems, 10(2): 159–184 (1998)

[RD98] M. Reichert, P. Dadam: ADEPTflex – Supporting Dynamic

Changes of Workflows Without Losing Control. J. Intell.

Inform. Syst., Special Issue on Workflow Management Sys-

tems, 10(2): 93–129 (1998)

[RS95] A. Reuter, F. Schwenkreis: ConTracts – A Low-Level Me-

chanism for Building General-Purpose Workflow Manage-

ment-Systems. IEEE Computer Society, Bulletin of the Tech-

nical Committee on Data Engineering, 18(1): 4–10 (1995)

[Sch96] B. Schultheiß: Prozeßreengineering in klinischen Anwen-

dungsumgebungen – Beispiele, Vorgehensmodelle, Werk-

zeuge. Diplomarbeit, Universit¨

at Ulm, Fakult¨

at f¨

ur Infor-

matik, 1996

[SK97] A. Sheth, K.J. Kochut: Workflow Applications to Research

Agenda: Scalable and Dynamic Work Coordination and Col-

laboration Systems. In: Proc. NATO Advanced Study Insti-

tute on Workflow Management Systems and Interoperability,

pp.12–21, Istanbul, August 1997

[SM96] A. Schill, C. Mittasch: Workflow Management Systems on

Top of OSF DCE and OMG CORBA. Distrib. Syst. Eng.,

3(4): 250–262 (1996)

[SNS99] H. Schuster, J. Neeb, R. Schamburger: A Configuration

Management Approach for Large Workflow Management

Systems. In: Proc. Int. Joint Conf. on Work Activities Coor-

dination and Collaboration, pp.177–186, San Francisco, Fe-

bruar 1999

[VW97] G. Vossen, M. Weske: The WASA Approach to Workflow

Management for Scientific Applications. In: Proc. NATO

Advanced Study Institute on Workflow Management Systems

and Interoperability, pp.145–164, Istanbul, August 1997

[Wes99] M. Weske: Workflow Management Through Distributed and

Persistent CORBA Workflow Objects. In: Proc. 11th Int.

Conf. on Advanced Information Systems Engineering, Hei-

delberg, 1999

[WHKS98] M. Weske, J. H¨

undling, D. Kuropka, H. Schuschel: Objekt-

orientierter Entwurf eines flexiblen Workflow-Management-

Systems. Informatik Forsch. Entw., 13(4): 179–195 (1998)

[WK96] J. W¨

asch, W. Klas: History Merging as a Mechanism for

Concurrency Control in Cooperative Environments. In: Proc.

6th Int. Workshop on Research Issues in Data Engineering –

Interoperability of Nontraditional Database Systems, pp.76–

85, New Orleans, Februar 1996

[WMC99] Workflow Management Coalition: Terminology & Glossary,

Document Number WFMC-TC-1011, Document Status – Is-

sue 3.0, Februar 1999

92 T. Bauer et al.: Effiziente ¨

Ubertragung von Prozessinstanzdaten

[WWK+97] G. Weikum, D. Wodtke, A. Kotz-Dittrich, P. Muth, J. Wei-

ßenfels: Spezifikation, Verifikation und verteilte Ausf¨

uhrung

von Workflows in MENTOR. Informatik Forsch. Entw., The-

menheft Workflow-Management, 12(2): 61–71 (1997)

Thomas Bauer studierte Informatik in

Ulm. Seit seinem Diplom im Juli 1995 ist

er wissenschaftlicher Mitarbeiter der Uni-

versit¨

at Ulm, Abteilung Datenbanken und

Informationssysteme, wo er im Februar

2001 seine Promotion abschloss. Seine In-

teressen liegen in den Bereichen Work-

flow-Management und Skalierbarkeit.

Peter Dadam ist seit 1990 Professor f¨

Informatik an der Universit¨

at Ulm und

Leiter der Abteilung Datenbanken und In-

formationssysteme. Davor war er Leiter

der Abteilung Advanced Information Ma-

nagement am Wissenschaftlichen Zentrum

der IBM in Heidelberg. Seine aktuellen

Arbeitsgebiete sind: Verteilte, kooperative

Informationssysteme, Workflow-Manage-

ment, Datenbanktechnologie und deren

Anwendungen in anspruchsvollen Anwen-

dungsgebieten.

[Zei99] J. Zeitler: Integration von Verteilungskonzepten in ein adap-

tives Workflow-Management-System. Diplomarbeit, Univer-

sit¨

at Ulm, Fakult¨

at f¨

ur Informatik, 1999

Manfred Reichert studierte Wirtschafts-

mathematik in Ulm. Er ist wissenschaftli-

cher Mitarbeiter an der Abteilung Daten-

banken und Informationssysteme der Uni-

versit¨

at Ulm, wo er im Juli 2000 seine

Promotion abschloss. Seine Interessen lie-

gen in den Bereichen unternehmenswei-

tes Workflow-Management und adaptive

Workflow-Systeme.