Eine Algebra für Cache-Modelle zum methodenbasierten Caching im Applikationsserver-Bereich

Der vorliegende Bericht behandelt vornehmlich die formalen
Aspekte für ein Verfahren zur Spezifikation von
Schreib-Lese-Abhängigkeiten für Methoden aus objektorientierten
Dienstschnittstellen.
Die Spezifikation der Schreib-Lese-Abhängigkeiten wird mit Hilfe
sogenannter Cache-Modelle repräsentiert; sie bestimmen, in
welcher Weise ein Methodenaufruf von einem anderen
Methodenaufruf bei der Nutzung der Dienstschnittstelle abhängt.

Cache-Modelle spielen eine wichtige Rolle beim konsistenten
Cachen von Methodenresultaten auf der Klientenseite eines
Applikationsserver-Systems. Ein Applikationsserver ist im
Kontext dieses Berichts ein Server oder Dienstgeber, der für
entfernte Klienten eine objektorientierte Dienstschnittstelle
mit Methoden anbietet.
Genauer besteht die Dientschnittstelle dabei aus einer Menge
abstrakter Klassen mit stark typisierten Methodensignaturen.

Ein methodenbasierter Cache dient zur Verbesserung vor allem der
Antwortzeiten eines Applikationsserversystems und hält bereits
einmal berechnete Methodenresultate von lesenden Aufrufen
bezüglich der Dienstschnittstellen beim Klienten vor.
Bei einem wiederholten Methodenaufruf vom Klienten kann das
... mehrResultat des Aufrufs aus dem methodenbasierten Cache geholt
werden. Sofern der Aufruf mit den gleichen Argumenten wie zuvor
stattfindet und sofern das vorgehaltene Resultat gültig ist,
muss der eigentlich entfernte Methodenaufruf dann nicht an den
Applikationsserver gesendet werden.

Eines der größten Probleme beim methodenbasierten Caching ist
die Gültigkeit der beim Klient vorgehaltenen Methodenresultate
zuzusichern:
Das Resultat aus dem Cache sollte identisch sein zu dem
Resultat, das der entsprechende lesende Methodenaufruf bei
Übergabe an den Applikationsserver liefern würde. "Lesend"
bedeutet hier hauptsächlich, dass der Aufruf den Zustand des
Applikationsserver garantiert nicht verändert.

Um lesende Methodenaufrufe bzw. Methoden zu bestimmen und um
ungültig gewordene Methodenresultate aus dem Cache entfernen zu
können, spezifiziert ein Anwendungsentwickler ein Cache-Modell
bezüglich der vorhandenen Dienstschnittstelle.
Das Cache-Modell identifiziert solche Methoden, die
ausschließlich lesen und gibt vor, wie die Abhängigkeiten
zwischen schreibenden und lesenden Methoden im Klienten
berechnet bzw. abgeschätzt werden können. Dies geschieht
auf der Basis eines Formalismus, der im Rahmen des Berichts
diskutiert wird.

Bei der Spezifikation von Cache-Modellen ist es wichtig, dass
diese korrekt sind, das heißt, das sie die tatsächlichen
Scheib-Lese-Eigenschaften der Implementierungen der
Dienstmethoden reflektierten. Ansonsten besteht die Gefahr, dass
ein methodenbasierter Cache ungültige Methodenresultate an den
Klienten zurückliefert oder nicht alle schreibenden
Methodenaufrufe für notwendige Zustandsveränderungen an den
Applikationsserver delegiert.

Um die Korrektheit von Cache-Modellen abzusichern, wird hier ein
einfaches, wenig aufwändiges Testverfahren vorgeschlagen.
Streng genommen, kann damit allerdings nur die Anwesenheit von
Fehlern in einem Cache-Modell nachgewiesen werden (also
Inkorrektheit) und nicht deren Abwesenheit.

Der Entwickler eines Cache-Modells hat zahlreiche Freiheitsgrade
bei der Entwicklung eines Cache-Modells, denn es gibt im
Allgemeinen viele korrekte Cache-Modelle zu einer
Dienstschnittstelle. Weniger "präzise" Cache-Modelle schätzen
die Schreib-Lese-Eigenschaften von Dienstmethoden sehr grob
(aber konservativ) ab und sind mit geringem Aufwand zu
erstellen. Der resultierende Nachteil sind eventuell häufige und
unnötige Invalidierungen im Cache und geringe Cache-Trefferraten.
Präzisere Cache-Modelle hingegen führen meist zu besseren
Trefferraten, sind aber aufwändiger zu spezifizieren.

Der Bericht formalisiert alle angesprochenen Aspekte von
Cache-Modellen also deren Struktur, den Korrektheitsbegriff
sowie die Präzision. Letztere wird dabei als eine
Ordnungsrelation auf der Menge der korrekten Cache-Modelle zu
einer gegebene Dienstschnittstelle eingeführt.

Neben der Wahl der Präzision gibt es auch die Möglichkeit, dass
mehrere Entwickler verschiedene, aber korrekte Cache-Modelle zur
gleichen Dienstschnittstelle definieren. Unter anderem kann
damit eine Art Arbeitsteilung für die Entwickler erreicht
werden, so dass diese sich relativ unabhängig voneinander auf
verschiedene Teile der Dienstschnittstelle konzentrieren. Die
korrekten Cache-Modelle können dann durch eine besondere
Vereinigungsoperation zu einem gemeinsamen und korrekten
Cache-Modell zusammengeführt werden, dass mindestens so präzise
ist wie jedes der Operandenmodelle. In diesem Zusammenhang
werden drei Vereinigungsoperationen unterschiedlicher Qualität
und Komplexität vorgestellt und verschiedene, zum Großteil
praxisrelevante algebraische Eigenschaften für diese nachgewiesen.

Darüber hinaus wird die Möglichkeit zur Normalisierung von
Cache-Modellen untersucht, die allerdings vornehmlich von
theoretischem Interesse ist. Abschließend handelt der Bericht
einige Detailprobleme ab, die beim praktischen Einsatz eines
Methoden-Caches entstehen können.