Page View Cache


Created on 27.02.2006
by pmenzel


F: Warum reicht der mitgelieferte Cache nicht aus?

A: Weil er nur für den anonymen Zugriff funktioniert. Für eingeloggte Nutzer werden Seite nie gecached.
Außerdem verlässt sich der Cache nur auf eine TTL und bezieht Änderungen von abhängigen Seiten
(z.B. über Includes oder Tree-Actions) nicht mit ein.


Why is the supplied cache not enough?

F: Was soll der neue Page-Cache können?

A: Er soll generell alle Seiten cachen können, Cache-Einträge auch bei Änderungen abhängiger Seiten
invalidieren und diese Cache-Einträge ggf. im Hintergrund aktualisieren.


What should the new page cache can?

F: Wie soll das mit dem Cache für angemeldete Nutzer funktionieren?

A: Jede aufgerufene Seite lässt sich durch einen eindeutigen Schlüssel identifizieren. Dieser
Schlüssel besteht aus: dem Seiten-Tag (sozusagen der URI), der Methode (standardmäßig ist das "show")
und der Nutzer-Id des angemeldeten Nutzers. Eine ausgelieferte Seite wird mit diesen Schlüssel
im Cache abgespeichert und bei Bedarf wieder abgefragt.
Aus Platzgründen können die gespeicherten Seiten (es ist jeweils der auszuliefernde HTML-Code, der 
vom Output-Buffer abgefangen wurde), gepackt werden. Die Zuordnung von Schlüssel und Cache-Eintrag
könnte über eine Datenbank-Tabelle erfolgen. Auf diese Weise können auch mehrere Cache-Eintrag auf 
einmal entfernt werden, z.B. wenn sich eine Seite ändert und für sie mehrere Einträge für merhrere
Nutzer existieren.


How will this work with the cache for registered users?

F: Wie soll mit abhängigen Seiten umgegangen werden?

A: Das Problem ist, dass häufig auf einer Seite andere Seiten statisch oder dynamisch eingebunden
sind. Dabei kann die gesamte Seite eingebunden sein (bei Includes), nur der Seitentitel (bei
der Tree-Action) oder bestimmte Metadaten (bei "Letzte Änderungen" oder zukünftigen coolen Actions).
Bei statischen Referenezen wird durch den Autor der Seite angegeben, welche externe Seite eingebunden
sein soll. Dies kann schon beim Editieren in der Datenbank abgespeichert werden. Dynamische Referenzen
hingegen ändern sich zur Laufzeit, ohne dass der Autor Einfluss darauf nimmt. Deshalb muss hier ein
leistungsfähigeres Modell her, bei dem Änderungen von abhänigen Seiten sofort weitergereicht und die
Cache-Eintrage umgehend invalidiert werden.
Ich stelle mir dabei folgendes Design vor: zu jeder Seite wird erfasst, welche Actions und Links es
gibt und was sie referenzieren. Bei Links ist das einfach, da wird nur angegeben, welche Seite
referenziert ist und welche Metadaten evtl. angezeigt werden. Bei Tree-Actions und dergleichen wird
das über Wildcards o.ä. erledigt. Wenn sich nun irgendeine Seite ändern, erstellt oder gelöscht wird,
so wird zum Abschluss dieser Bearbeitungsaktion geprüft, von welchen Seiten die betreffende Seite
statisch referenziert ist oder dynamisch eingebunden sein könnte. Für diese Seiten wird dann geprüft,
ob sie sich tatsächlich ändern. Das muss nämlich nicht immer der Fall sein. Wenn bspw. der Text einer
Seite geändert wird, hat das keinen Einfluss auf den Link zu dieser Seite. Liegt tatsächlich eine
Änderung der referenzierenden Seite vor, so muss ihr Cache-Eintrag invalidiert werden.
Das Abspeichern einer Seite ist mit dieser Strategie vergleichsweise teuer. Da das Verhältnis zwischen
lesendem und schreibendem Zugriff auf das Wiki aber deutlich zu Gunsten der Lesezugriffe ausfallen
dürfte, kann diese Strategie ruhig verfolgt werden.


How should we deal with dependend pages?

F: Wie soll das Pre-Caching implementiert werden?

A: Beim Pre-Caching werden Seiten in den Cache gepackt, bevor der Nutzer sie anfordert. Auf diese
Weise kann er stets auf den schnellen Cache zugreifen und nicht erst nachdem er die Seiten einmal
angefordert hat. Da aber nicht immer alle Seiten (potentiell sind das tausende!) im voraus angefordert
und im Cache abgelegt werden können, muss eine Auswahl getroffen werden.
Das erste Kriterium ist, ob sich eine Seite überhaupt geändert hat. Das betrifft Änderungsaktionen
an der Seite selbst und Änderungen an referenzierten Seiten, die Auswirkungen auf die referenzierende
Seite haben (z.B. bei Includes). Da sich nur wenige Seiten auf einmal ändern, reduziert sich die 
Anzahl vorzuladender Seiten erheblich.
Es kann aber sein, dass ein Nutzer lange Zeit nicht im Wiki war und sich sehr viele Seiten seit seinem
letzten Besuch geändert haben. In diesem Fall müsste ein Großteil der Cache-Einträge für den Nutzer
invalidiert und anschließend vorgeladen werden. Es ist allerdings unsinnig in einem einzigen Request
1000 Seiten vorzuladen, weil anschließend ohnehin nur eine einzige Seite aufgerufen werden wird. Nur 
eine Seite vorzuladen ist aber genauso unklug, denn die Chance, dass das diejenige Seite sein ist, die 
der Nutzer als nächstes aufrufen wird, ist sehr gering. Diese Chance ist aber nicht über alle Wikiseiten
gleichverteilt. Bestimmte Seiten werden bevorzugt aufgerufen, z.B. die Startseite oder "Letzte
Änderungen". Die Chance auf einen Precache-Hit lassen sich also maximieren, wenn diejenigen Seiten
vorgeladen werden, deren Aufrufwahrscheinlichkeiten am größten sind. Diese Wahrscheinlichkeiten lassen
sich im Laufe der Zeit vom Nutzerverhalten ableiten. Dazu wird für jede Seite die durchschnttliche
Zugriffszahl ermittelt. Dabei sollte ein Moving Average eingesetzt werden, um das sich ändernde
Nutzerverhalten widerzuspiegeln. Auf Basis der Zugriffswahrscheinlichkeiten lassen sich nun die X
erfolgversprechendssten Seiten vorladen (für die der Cache-Eintrag nicht gültig ist). Die Zahl X lässt
sich generell festlegen (z.B. auf 10) oder aus Basis der Varianz der Seitenaufrufe bestimmen. Bei einem
Nutzer, der stets nur fünf Seiten aufruft, liegt die summierte Trefferwahrscheinlichkeit dieser fünf
Seiten schon hoch genug, wohingegen ein anderer Nutzer vielleicht 20 vorgeladene Seiten benögit, um eine
ähnlich hohe Gesamttrefferwahrscheinlichkeit zu bekommen. Zusätzlich kann die die Häufigkeit der 
Nutzung des Wikis die Anzahl der vorgeladenen Seiten beienflussen. Ein ständiger Nutzer bekommt dabei
einen Bonus und es werden für ihn mehr Seiten vorgeladen als bei einem Nutzer, der nur selten auf 
das Wiki zugreift. Dieser Nutzer muss dann u.U. mit häufigeren Cache-Misses und längeren Ladezeiten
zu Beginn seiner Wiki-Sitzung rechnen.


How should the pre-caching be implemented?