Page View Cache

Created on 27.02.2006^[link1]
by pmenzel

Warum reicht der mitgelieferte Cache nicht aus?

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 sufficient?

Because it only works for anonymous access. For logged-in users, pages are never cached.
Furthermore, the cache relies on a TTL and refers to changes of dependent pages
(for example, using includes or tree actions).

Was soll der neue Page-Cache können?

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 be able to do?

It should generally be able to cache all pages, cache entries also for changes of dependent pages
and update these cache entries in the background if necessary.

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 is this supposed to work with the cache for registered users?

A: Each page you visit can be identified by a unique key. This
key consists of: the page tag (the URI, so to speak), the method (by default this is "show")
and the user ID of the registered user. A delivered page is generated with these keys
is stored in the cache and retrieved when needed.
For space reasons, the cached pages (the HTML code to be delivered, the
has been intercepted by the output buffer), can be packed. The assignment of key and cache entry
could be done via a database table. In this way, several cache entries can be made on
be removed once, e.g. if a page changes and several entries for several
Users exist.

Wie soll mit abhängigen Seiten umgegangen werden?

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 dependent pages be handled?

The problem is that often on one page other pages are statically or dynamically integrated
are. The entire page can be included (for includes), only the page title (for
of the tree action) or certain metadata (for "Last Changes" or future cool actions).
For static references, the author of the page specifies which external page is included
is supposed to be. This can be saved in the database during editing. Dynamic references
on the other hand, change at runtime without the author having any influence. Therefore a
more powerful model, where changes from dependent sites are immediately passed on and the
cache entries can be invalidated immediately.
I have the following design in mind: for each page it is recorded which actions and links there
and what they refer to. With links, this is easy, they just indicate which page
is referenced and which metadata may be displayed. For tree actions and the like
that's done via wildcards or similar. If any page changes, is created or deleted,
at the end of this editing action, the system checks from which pages the page in question
is statically referenced or could be dynamically integrated. The system then checks for these pages,
whether they actually change. Because that does not always have to be the case. For example, if the text of a
page is changed, this has no influence on the link to this page. If there is actually a
If the referencing page is changed before, its cache entry must be invalidated.
Saving a page with this strategy is comparatively expensive. Since the relationship between
read and write access to the Wiki but clearly in favour of read access
this strategy can be pursued without hesitation.

Wie soll das Pre-Caching implementiert werden?

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?

In pre-caching, pages are cached before the user requests them. On these
This way he can always access the fast cache and not only after he has once
has requested. But since not all pages (potentially thousands!) are requested in advance
and can be stored in the cache, a selection must be made.
The first criterion is whether a page has changed at all. This concerns change actions
on the page itself and changes to referenced pages that affect the referencing
page (for example, for Includes). Since only a few pages change at once, the
Number of pages to be preloaded is considerable.
However, it may be that a user has not been in the Wiki for a long time and has downloaded a lot of pages since his
last visit. In this case, a large part of the cache entries for the user would have to
be invalidated and then subpoenaed. However, it is nonsensical in a single request
1000 pages, because afterwards only one page will be called anyway. only.
but it is just as unwise to preload a page, because the chance that this is the page that
the user will call next is very low. But this chance is not the case for all wiki pages
equally distributed. Certain pages are called preferentially, e.g. the start page or "Last
Changes". The chance of a precache hit can therefore be maximized if those pages
be subpoenaed, whose chances of being called are the highest. These probabilities leave
can be derived from user behaviour over time. For this purpose, the average
Access number determined. A moving average should be used to determine the changing
to reflect user behaviour. Based on the access probabilities, the X
preload the most promising pages (for which the cache entry is not valid). The number X leaves
define yourself generally (e.g. to 10) or determine from the variance of the page views. With a
Users who only call up five pages at any one time, the cumulative hit probability of these five
pages are already high enough, whereas another user may need 20 preloaded pages to create a
to get a similarly high overall hit probability. Additionally, the frequency of the
Use of the wiki influences the number of preloaded pages. A permanent user gets
a bonus and more pages will be preloaded for him than for a user who is rarely
to access the wiki. This user may then have to deal with more frequent cache misses and longer loading times
at the beginning of his wiki session.

Links

[link1] https://sourceforge.net/p/wackofork/code/HEAD/tree/trunk/wiki/classes/PageViewCache.php?revision=144