© Prof. Dr.-Ing. Wolfgang Lehner | Systemübergreifende Kostennormalisierung für Integrationsprozesse Matthias Böhm 1,2, Dirk Habich 2, Wolfgang Lehner

© Prof. Dr.-Ing. Wolfgang Lehner |

Systemübergreifende Kostennormalisierung für Integrationsprozesse

Matthias Böhm1,2 , Dirk Habich2, Wolfgang Lehner2, Uwe Wloka1

1 Hochschule für Technik und Wirtschaft Dresden (FH), Database Group2 Technische Universität Dresden, Database Technology Group

BTW 2009

Matthias Böhm | Systemübergreifende Kostennormalisierung für Integrationsprozesse | 2

>Problemstellung

Einführung Integrationsprozesse

Invoke o3

Fork o1

Assign o5Assign o2

Selection o4

Join o8

Assign o9

Invoke o10

Invoke o6

Selection o7

Receive o1

Switch o2

Translation o5

Assign o6

Assign o8

Invoke o7

Invoke o9

Translation o3

Assign o4

a) Datengetriebener Integrationsprozess

b) Zeitbasierter Integrationsprozess

SAP R/3

JDBC

Web Service

JDBC JDBC

Web Service


>Problemstellung

Kontext Modellgetriebene Generierung

von Integrationsprozessen GCIP (Generation of Complex

Integration Processes)

Problem Vergleichbarkeit von

Integrationssystemen Voraussetzung für systemübergreifende Optimierung

Überblick Problemstellungen der Kostenmodellierung und -normalisierung Plattforminvariantes Kostenmodell für Integrationsprozesse Algorithmen zur Kostennormalisierung


>Problemstellung

Annahme 1: Generierbarkeit Plattformunabhängige Modellierung möglich Generierung von Plattformspezifischen Integrationsaufgaben

möglich (GCIP, Orchid, ETL Prozesse) Voraussetzung für Wahlmöglichkeit

Annahme 2: Auswahlmöglichkeit Typische IT Infrastruktur umfasst mehrere Integrationssysteme mit überlappenden

Funktionalitäten [Sto02] Spezielle Operatoren Unterstützte externe Systeme Möglichkeiten auf externe Ereignisse zu reagieren Transaktionale Eigenschaften

Auswahl IS ohne externes Verhalten zu beeinflussen (Korrektheit)

[Sto02] Michael Stonebraker. Too Much Middleware. SIGMOD Record, 31(1), 2002.


>Problemstellung

Vision des „Invisible Deployments“ Kernidee

Ebene der Integrationssysteme und -technologien systematisch zu abstrahieren Virtualisierung im Sinne der transparenten Auswahl

1) Auswahl Kandidatenmenge (funktionale Eigenschaften) 2) Auswahl Optimales IS (Performance, Skalierbarkeit, …)


>Herausforderungen

Parallelität Einbeziehung Parallelität von Prozess- und Operatorinstanzen

Ressourcenverwendung Effektive (Re(oi)) und maximale Ressourcenverwendung (Ro(oi))

Unterschiedliche Hardware Heterogene Hardware erfordert Einbeziehung des Zeitaspekts

Unterschiedliche Verarbeitungsmodelle Berücksichtigung von Spezifika wie Sync/Async und Instanz/P&F

Semantik erhobener Statistiken Bezug der Statistiken zu gleichen Aufgaben (Operator, Kardinalität)

Fehlende Statistiken Inkonsistente Statistiken Statistischer Fehler

Hauptproblem der Kostennormalisierung: Die Kostennormalisierung ist per Definition unidirektional, da eine denormalisierte in exakt eine normalisierte Form abgebildet werden kann (jedoch nicht vice versa).


>Gliederung

Problemstellung und Herausforderungen

Plattforminvariante Kostenmodellierung Kostenmodell Erhebung von Verarbeitungsstatistiken

Kostennormalisierung Grundnormalisierung Transformation der Semantik Statistische Korrektur

Anwendungsszenario Plan- und Kostendiagramme

Experimentelle Evaluierung

Zusammenfassung


>Kostenmodellierung

Hauptproblem Systemübergreifender Charakter des Anwendungsgebietes

Beispiel

Plan/System

Statistik o1 o2 o3 Summe

Ps1 |dsin| - 1573 1345

|dsout| 1573 1345 0

Ps2 |dsin| - 1105 1017

|dsout| 1105 1017 0

Abstrakter Kostenvergleich (z.B. auf Ebene der Kardinalitäten) schlägt fehl, da unterschiedliche Arbeitslast

Receive o1 Translation o2

Invoke o3

|dsout| |dsin|+|dsout|

|dsin|+|dsout|

Ps2

???

Plan/System


Ps1 |dsin| - 1573 1345

|dsout| 1573 1345 0

C(ol) 1573 2918 1345 5836

Ps2 |dsin| - 1105 1017

|dsout| 1105 1017 0

C(ol) 1105 2122 1017 4244


>Kostenmodellierung (2)

Hauptproblem Systemübergreifender Charakter des Anwendungsgebietes

BeispielReceive o1 Translation

o2

Invoke o3

te(ol) te(ol) te(ol)

Plan/System


Ps1 te(ol) 10 ms 150 ms 70 ms

Ps2 te(ol) 10 ms 140 ms 61 ms

Vergleich normalisierter Verarbeitungsstatistiken (Ausführungszeit) schlägt ebenfalls fehlt, da keine Aussage über Arbeitslast

Ps2

???

Plan/System


Ps1 te(ol) 10 ms 150 ms 70 ms 230 ms

Ps2 te(ol) 10 ms 140 ms 61 ms 211 ms



Lösungsansatz Zweistufiges Verfahren der Kostenmodellierung Stufe 1: Bestimmung absoluter Kosten auf abstraktem Niveau Stufe 2: Gewichtung mit normalisierten Statistiken

Plan/System


Ps1

C(ol) 1573 2918 1345 5836

Ps2

C(ol) 1105 2122 1017 4244

Receive o1 Translation o2

Invoke o3

te(ol) |dsout|

te(ol)|dsin|+|dsout|

te(ol)|dsin|+|dsout|

Ps1

Plan/System


Ps1 te(ol) 10 ms 150 ms 70 ms 230 ms

C(ol) 1573 2918 1345 5836

Ps2 te(ol) 10 ms 140 ms 61 ms 211 ms

C(ol) 1105 2122 1017 4244

Plan/System


Ps1 te(ol) 10 ms 150 ms 70 ms 230 ms

C(ol) 1573 2918 1345 5836

NC(ol) 0.0064 0.0514 0.0420 0.1098

Ps2 te(ol) 10 ms 140 ms 61 ms 211 ms

C(ol) 1105 2122 1017 4244

NC(ol) 0.0091 0.0660 0.0599 0.1350



Plattforminvariantes Kostenmodell Ausgelegt für Message Transformation Model (MTM)

Interaktionsorientierte Operatoren Datenflussorientierte Operatoren (angelehnt an [Mak07]) Kontrollflussorientierte Operatoren

Problembehebung Herstellung der Vergleichbarkeit bei disjunkten Prozessinstanzen Unterschiedliche Hardware wird modellinhärent berücksichtigt

Im Papier: Vollständiges plattforminvariantes Kostenmodell Erhebung von Statistiken (Anforderungen, Vorgehensweise)

[Mak07] Mazeyar E. Makoui. Anfrageoptimierung in objektrelationalen Datenbanken durch kostenbedingte Termersetzungen. Dissertation, Universität Hannover, 2007.


>Gliederung






Zusammenfassung


>Kostennormalisierung

Überblick zur Kostennormalisierung

Detaillierte Verarbeitungsstatistiken

Grundnormalisierung Algorithmus BaseNormalization- Parallelität von Instanzen- Ressourcenverwendung- Unterschiedliche Verarbeitungsmodelle

Plattforminvariantes Kostenmodell

Aggregate

Semantik Transformation

Aggregate

Algorithmus SemanticTransformation- Semantik erhobener Statistiken

Statistische Korrektur

Aggregate

Algorithmus StatisticalCorrection- Fehlende Statistiken- Inkonsistente Statistiken- Statistischer Fehler

Kostenmodell- Systemübergreifende Vergleichbarkeit - Unterschiedliche Hardware


>Grundnormalisierung

Intuition zum Algorithmus BaseNormalization Problem: Parallelität von Instanzen verfälscht erhobene Statistiken

p2

Zeit t

p1

p3

Prozess 1

Prozess 2

Prozess 3

∆t ∆t / 2 ∆t / 3 ∆t / 2 ∆t Idee

Vertikale Unterteilung der Zeitachse in Abschnitte(Grenzen durch Beginn und Ende von Instanzen determiniert)

Berechnung der normalisierten Abschnittszeiten Berechnung der normalisierten Statistiken (a.G. Abschnittszeiten)


>

NC14.09

6.00

6.09

NC14.09

6.00

6.09

15.13

6.25

6.88

NC14.09

6.00

6.09

15.13

6.25

6.88

14.00

6.00

6.00

Time18.00

6.00

10.00

17.00

7.50

7.50

14.00

6.00

6.00

PTID PID NID Start End1 1 -1 0.0 18.0

1 1 1 1.0 7.0

1 1 2 7.5 17.5

1 2 -1 8.0 25.0

1 2 1 8.5 16.0

1 2 2 16.5 24.0

1 3 -1 26.0 40.0

1 3 1 27.0 33.0

1 3 2 33.5 39.5

Grundnormalisierung (2)

Am Beispiel te(P)

o1Prozess 1

Prozess 2

Prozess 3

Zeit t0 4020

o2

o1 o2

o2o1

Time = End - Start

te(P1)= 0.1/0.1 * 1.00ms

Re(o)=min(1/num, Ro(Pi) )

+ te(o1) + 0.1/0.1 * 0.50ms + te(o2) + 0.1/0.1 * 0.50ms mitte(o1)= 0.6/0.6 * 6.00ms te(o2)= 0.85/0.85 * 0.50ms + 0.5/0.85 * 0.50ms + 0.5/0.85 * 7.50ms + 0.5/0.85 * 0.50ms + 0.5/0.85 * 1.00ms

AVG

P 14.42

o1 6.50

o2 6.32

Wiederverwendung von Abschnittsmengen möglich

NC(o)=∆t * Re(o)/ Ro(o)

Ro(Pi)=0.10Ro(o1)=0.60Ro(o2)=0.85


>Grundnormalisierung (3)

Problembehebung Parallelität von Instanzen Ressourcenverwendung Unterschiedliche Verarbeitungsmodelle (mit Einschränkungen)

Im Papier: Algorithmus 1 BaseNormalization Formale Komplexitätsanalyse des Algorithmus: O(n2 m2)

n … Anzahl Prozessinstanzen m … Anzahl Operatoren

Problem Statistiken beziehen sich semantisch auf Integrationsaufgabe/Operationen des

konkreten Integrationssystems


>Semantik Transformation

Intuition zum Algorithmus SemanticTransformation Problem: Erhobene Statistiken beziehen sich semantisch auf Operatoren des

Zielsystems (und nicht die zentrale Repräsentation)

PETL

PMTM

o1 o2 o3 o4 o6o5

o1‘ o2‘ o3‘ o4‘ o6‘o5‘ o7‘

1:1 N:1 1:N N:M(1:1) (N:1)

Problem: Fehlende Statistiken

Idee Bestimmung des semantischen Bezugs (invers zur Generierung) Verwendung bidirektionaler Transformationsregel (falls vorhanden) Übernahme von Statistiken

Direkte Übernahme falls verlustfrei möglich Andernfalls Gruppierung der Statistiken als Teilprozesse


>Semantik Transformation (2)

Problembehebung Semantik erhobener Statistiken

Im Papier: Algorithmus 2 SemanticTransformation Formale Komplexitätsanalyse des Algorithmus: O(m2 + m´)

m … Anzahl Operatoren (Quellsystem) m´… Anzahl Operatoren (Zielsystem)

Problem Inkonsistente und fehlende Statistiken


>Statistische Korrektur

Intuition zum Algorithmus StatisticalCorrection Problem: Inkonsistente und unvollständige Statistiken

PMTM o1 o2 o3 o4 o6o5 o7

te(op1)|dsin||dsout|


te(o2)|dsin||dsout|

te(o1)|dsout|

1) Prüfung |dsout|(oi) == |dsin|(oi+1)

te(o3)|dsin||dsout|

te(o4)|dsin||dsout|

te(o5)|dsin||dsout|

te(o7)|dsin||dsout|

te(o6)|dsin||dsout|

2) Interpolation

Idee Bestimmung von Inkonsistenzen zwischen Statistiken Löschung von inkonsistenten Statistiken Berechnung (Interpolation) fehlender Statistiken

Statistiken welche nicht erhobenen werden konnten Statistiken welche aus 1:N / N:M Abbildungen hervorgegangen sind Statistiken welche im Zuge der Konsistenzanalyse gelöscht wurden


>Statistische Korrektur (2)

Problembehebung Fehlende Statistiken Inkonsistente Statistiken Statistischer Fehler

Im Papier: Algorithmus 3 StatisticalCorrection Formale Komplexitätsanalyse des Algorithmus: O(m)

m … Anzahl Operatoren


>Gliederung






Zusammenfassung


>Anwendungsszenario

Plandiagramm Zwei-Dimensionale Darstellung optimaler Pläne hinsichtlich zwei

Variabilitätsparameter

Kostendiagramm Drei-Dimensionale Darstellung der

Plandiagramme, gewichtetmit normalisierten Kosten

Hierarchie von Plan- und Kosten-diagrammen Systemtypdiagramme Systemdiagramme Plandiagramme


>Anwendungsszenario (2)

Beispielprozess Variabilitäts

parameter:

Invoke o3

Fork o1

Assign o5Assign o2

Selection o4

Join o8

Assign o9

Invoke o10

Invoke o6

Selection o7

VP1: dsout(o3) [0; 1.000.000] --cardinality

VP3: dsout(o4)/ dsin(o4) [0; 1.0] --selectivity

VP2: dsout(o6) [0; 1.000.000] --cardinality

VP4: dsout(o7)/ dsin(o7) [0; 1.0] --selectivity

VP5: dsout(o8)/ max(dsin1(o8), dsin2(o8)) [0; 1.0] --selectivity


>

Invoke o3

Selection o4

Anwendungsszenario (3)

Beispiel Systemtypdiagramme (FDBMS, ETL) Plan-

diagramm

x=VP1y=VP3

Kosten-diagramm

x=VP1y=VP3z=te(P)

Invoke o3

Fork o1

Assign o5Assign o2

Selection o4

Join o8

Assign o9

Invoke o10

Invoke o6

Selection o7

VP1: dsout(o3) VP3: dsout(o4)/ dsin(o4)


>

Invoke o3

Join o8

Anwendungsszenario (4)

Beispiel Systemdiagramme (FDBMS x, FDBMS y) Plan-

diagramm

x=VP1y=VP5

Kosten-diagramm

x=VP1y=VP5z=te(P)

Invoke o3

Fork o1

Assign o5Assign o2

Selection o4

Join o8

Assign o9

Invoke o10

Invoke o6

Selection o7

VP1: dsout(o3)

VP5: dsout(o8)/ max(dsin1(o8), dsin2(o8))


>Gliederung






Zusammenfassung


>Experimentelle Evaluierung

Qualität der Kostennormalisierung

Grad der Parallelität(variiert von p=1 bis p=4)

Datenmenge i.S.v. Kardinalitäten*(variiert von d=0.001 bis d=0.004)

*Skalierungsfaktor des DIPBench (Data-Intensive Integration Process Benchmark)


>Experimentelle Evaluierung (2)

Problem „Unterschiedliche Verarbeitungsmodelle“ WFPE: Instanz-basierte Prozessverarbeitung VWFPE: Prozessverarbeitung entsprechend des Pipes&Filter-Modells

Normalisierung für Extremfälle (hier n=250) ungenügend Ursache: Lange Wartezeiten in Warteschlangen einbezogen Einbeziehung des Durchsatzes bringt geringfügige Verbesserung Ausweg: Wartezeiten müssten einbezogen werden (aber: systemübergreifend schwierig)


>Experimentelle Evaluierung (3)

Effizienz der Kostennormalisierung Quadratische Zeitkomplexität

experimentell nachgewiesen Effiziente Verarbeitung durch

Partitionierung der Detailstatistiken möglich


>Gliederung






Zusammenfassung


>Zusammenfassung

Problem Vergleichbarkeit von Integrationssystemen Voraussetzung für systemübergreifende Optimierung

Überblick/Zusammenfassung Problemstellungen der Kostenmodellierung und -normalisierung Plattforminvariantes Kostenmodell für Integrationsprozesse

Zweistufiges Kostenmodell Anforderungen an Statistikerhebung

Algorithmen zur Kostennormalisierung Algorithmus BaseNormalization Algorithmus SemanticTransformation Algorithmus StatisticalCorrection

Unterschiedliche Anwendungsgebiete ...


>Schlussfolgerungen

Wesentliche Beobachtungen Effizienz hängt sehr stark von

der dynamischen Workload-Charakteristik ab

Break-even-points bei sich verändernder Charakteristik

Mögliche Anwendungsgebiete What-If Schnittstelle für Integrationssysteme

Plandiagramme Kostendiagramme

Einsatz im Rahmen der modellgetriebenen Generierung Auswahl von Generierungszielen (Systemen)

- z.B.: Orchid (Prof. Dessloch), GCIP (HTW, TUD), Verwaltung von ETL-Prozessen (Prof. Naumann)- Robustheitsentscheidungen (im Hinblick auf Statistiken)

Lastbalancierung mit heterogenen Integrationssystemen

© Prof. Dr.-Ing. Wolfgang Lehner |

Systemübergreifende Kostennormalisierung für Integrationsprozesse

Matthias Böhm1,2 , Dirk Habich2, Wolfgang Lehner2, Uwe Wloka1

1 Hochschule für Technik und Wirtschaft Dresden (FH), Database Group2 Technische Universität Dresden, Database Technology Group

BTW 2009


>Backup

Plattform-invariantesKostenmodell


>Backup (2)

Beispiel SemantischeTransformation*

PETL

PMTM

o1 o3 o4 o6o5

o1‘ o2‘ o3‘ o4‘ o6‘o5‘ o7‘

te(o1

)te(o2

)te(o3

)te(o4

)te(o5

)te(o6

)1:1

te(o1‘)=

te(o1)

te(o1‘)

N:1te(o2‘)= te(o2)+te(o3)

te(o2‘)

1:Nte(op1‘)

=te(o4)

te(op1‘)

N:Mte(op2‘)

= te(o5)+te(o6)

te(op2‘)

*Am Beispiel der Verarbeitungszeit von Operatoren te(oi)

Problem: Fehlende Statistiken

o2


>Backup (3)

Beispiel Statistische Korrektur

PMTM o1 o2 o3 o4 o6o5 o7



te(o2)|dsin||dsout|

te(o1)|

dsout|

PMTM‘o1‘ o2‘ o3‘ o4‘ o6‘o5‘ o7‘

te(o2)|dsin||dsout|

te(o1)|

dsout||dsin|

1) Übernahme dsin(o3‘)= dsin(op1)dsout(o4‘)= dsout(op1)

|dsout|

Allgemeine Interpolationdsin(oi‘)= dsin(o)-(i-1)*(dsin(o)-dsout(o))/|o‘|dsout(oi‘)= dsin(o)-(i)*(dsin(o)-dsout(o))/|o‘|te(oi‘)= te(o) * C(oi‘)/ ∑ C(oi‘)

2) Interpolationdsout(o3‘)= dsin(o4‘)= dsin(op1) - (dsin(o)-dsout(o))/2te(oi‘)= te(op1) * C(oi‘)/ ∑ C(oi‘)

te(o3)|dsin|

|dsout|

te(o4)|dsin|

|dsout|

|dsin||

dsout|

1) Übernahme 2) Interpolation

te(o6)|dsin|

|dsout|

te(o5)|dsin|

|dsout|

te(o7)|dsin|

|dsout|

Documents

© Prof. Dr.-Ing. Wolfgang Lehner | Systemübergreifende Kostennormalisierung für Integrationsprozesse Matthias Böhm 1,2, Dirk Habich 2, Wolfgang Lehner