Code-Kata: Cache-Klasse. Wer produziert den besten Code

[Stevie]

[OT] Fiel mir grad so ein, als ich das hier las: http://martinfowler.com/bliki/TwoHardThings.html [/OT]

[Dejan Vu]

Wo hast Du das denn schon wieder her

Ich hatte meinen Ansatz mit der MRU-Strategie ('Most Recently Used') umgesetzt, so wie sie im SQL-Server zum Einsatz kommt. Sie ist verblüffend einfach.

In einer Dictionary werden die gecachten Objekte vorgehalten. Zusätzlich sind sie in einer verketteten Liste verbunden. Wird der Cache zu voll, werden die Items, die am Ende der Liste sind, entfernt (aus der Liste und dem Dictionary).

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

Das kann man dann alles wunderbar testen.

Bezüglich der 'Vorgaben'... Ich habe einfach mal angefangen. Und der kleinste Nenner wäre etwas ohne Generics. Ich denke, eine entsprechende Implementierung ist davon unabhängig, aber sinnvoller wäre natürlich eine, die wirklich wiederverwendbar wäre, und das geht nun mal nur mit Generics.

Bezüglich der Testsuite... Das wäre wirklich optimal, aber ich hab keine ;-(

Ich poste später vielleicht meinen Ansatz. Nur sitze ich bei 36°C und da denkt man nicht direkt daran, alten Code rauszukramen und zu reinigen.

[Uwe Raabe]

Zitat von Dejan Vu:

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread). Schreib doch die Vorgabe einfach um:

Zitat:

Der Cache soll die maximal N zuletzt verwendeten Elemente im Speicher halten.

Der Satz mit Wahrscheinlichkeit und häufiger kann dann entfallen. Damit ist die Cache-Strategie klar definiert und es kommt nur noch auf die Implementierung an.

[Dejan Vu]

Zitat von Uwe Raabe:

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread).

Du irrst . Wahrscheinlichkeiten und Ausnahmen, d.h. konkrete Einzelbeispiele, widersprechen sich nicht.

Wenn in deinem Beispiel der Cache für alle 10 Elemente und 1000 (=10 x 100) Zugriffe einen Treffer erzielt hat, dann ist Quote 100%. Wenn nun ein 11. Element hinzukommt und dafür eines der vorherigen weicht, dann ändert sich zunächst einmal an der Wahrscheinlichkeit eines Treffers gar nichts. Erst die folgenden Zugriffe entscheiden dann, ob die gewählte Strategie gut ist, oder nicht. Und wenn nun nicht mehr die Elemente 1-10 sondern 2-11 benötigt werden, dann liegt die Quote wieder bei 100%.

[idefix2]

Uwe Raabe hat es richtig geschrieben. Es fehlt in deiner Vorgabe eine zeitliche Komponente, ohne die wird keine gute Performance herauskommen (und dein eigener Lösungsansatz ignoriert deine Vorgabe übrigens komplett, der implementiert NUR die zeitliche Komponente).
Das Problem dabei: Wenn ab irgendeinem Zeitpunkt ein anderes (ganz neues) Element als die bisher häufigsten öfter gebraucht wird, dauert es sehr lange, bis das Element im Cache gelassen wird. Zu Beginn ist die "Wahrscheinlichkeit" nahe 0, und das Element wird sehr oft hinausgeworfen (und verursacht dadurch viele cache misses), bis es aufgeholt hat und im Speicher bleiben darf. Deshalb gehört unbedingt auch der Zeitfaktor in irgendeiner Form ins Spiel, in der einfachsten Form z.B., dass ein Element, das neu in den Cache geholt wurde, bei den nächsten n (n deutlich kleiner als die Cachegrösse) Malen, die ein Element aus dem Cache fliegt, geschützt wird.

Elemente, die vor langer Zeit oft benötigt wurden, inzwischen aber längst nicht mehr, behalten nach deiner Vorgabe eine sehr hohe "Wahrscheinlichkeit". Auch dagegen gibt es ein einfaches Mittel:
Für den ganzen Cache wird eine Zugriffsnummer bei jedem Zugriff hochgezählt. Bei jedem Element, auf das zugegriffen wurde, wird zuzätzlich zur um 1 erhöhten Häufigkeit auch die Zugriffsnummer gespeichert. Dann ergibt die Zugriffsnummer des Cache minus Zugriffsnummer eines Elements sein Alter (= wie lange wurde das Element nicht gebraucht). Für die Berechnung, welches Element rausfliegt, wird dann nicht nur die Zugriffshäufigkeit hergenommen, sondern (Zugriffshäufigkeit*a-Alter*b), wobei man mit den Parametern a und b die Gewichtung der beiden Faktoren zueinander optimieren kann.

Und natürlich muss die Häufigkeit auch für die Elemente gespeichert bleiben, die schon aus dem Cache rausgeflogen sind.

[Dejan Vu]

Dann scheinen ja mindestens zwei sinnvolle Strategien zu existieren.

Für jede Strategie lassen sich ja Szenarien entwickeln, die den Cache alt aussehen lassen.

Die Zugriffsquote (d.h. Effizienz) ist ja auch abhängig von der Cache-Größe: Beim Beispiel von Uwe reicht es, die Cache-Größe auf 11 zu erhöhen und schon klappt alles wieder.

Ich finde den MRU-Ansatz deshalb sehr charmant, weil er so einfach ist und scheinbar auch sehr effizient: Er findet im SQL-Server Verwendung (zumindest in den älteren Versionen). Nachzulesen bei 'Inside SQL-Server 2000' von Ron Soukup und Kalen Delaney. In einer meiner NoSQL-Versuche war ein solcher Cache im Einsatz und hatte Hitraten von um die 97%. Mir hat das gereicht.

Andere Strategien dürften vielleicht noch effizienter sein, aber die Maxime beim SQL-Server lautet ja eh: RAM, RAM and more RAM (analog dem ultimativen Gegenmittel: Erhöhe die Cache-Größe, bis es passt)

Allen Caches gemein ist übrigens das Fehlen einer Glaskugel, um in die Zukunft zu schauen und dann zu entscheiden, welches Element fliegt.

Um die Strategien jedoch zu vergleichen benötigen wir deterministische Szenarien.
Wie wäre folgende:

Delphi-Quellcode:

N := 10000;
RangeSize := 100;

Cache := TCache.Create(SampleCacheSize); 

Randomize(123);

Range := N div RangeSize; // oder irgend eine andere Zahl
For i:=Range+1 to N-Range do 
  For j:=1 to RangeSize do begin
    Cache.Put(Random (i-Range, i+Range), nil);
    Cache.Get(Random (i-Range, i+Range), Dummy);
  end;

Ich fülle (Put) den Cache also mit einer zufälligen ID innerhalb eines bestimmten Bereiches und lese dann einen zufällig anderen Wert aus diesem Bereich. Nach einigen Versuchen bewege ich den Bereich um eins nach oben.

Eine andere Variante wäre dann z.B.

Delphi-Quellcode:

For i:=Range+1 to N-Range do 
  For j:=i-Range To i+Range-1
    Cache.Put(j, nil);
    Cache.Get(j, Dummy);
  end;

Achtung! Das sind nur Vorschläge. Wer es verbessern oder erweitern will: Nur Zu!

[Captnemo]

Das ist zwar nicht unbedingt mein Thema, aber ich hätte hier noch einen Vorschlag.

Nehmen wir an wir haben 100 Items und einen Cache von 10.
Item[45] wir 99 mal angesprochen, Item[54] wird 50 mal angesprochen. Danach werden 9 andere Items angesprochen. Jetzt müsste also Item[45] hinten rausfallen.
Danach wird aber wieder Item[45] angesprochen, muss es wieder geladen werden und Item[45] fliegt raus.
Die anderen 9 Items liegen nur rum, obwohl sie nur ein mal angesprochen wurde, und sorgen dafür, dass Item[45] und Item[54] trotz ihrer häufigen Verwendung aus dem Cache fliegen.

Ich würde mal versuchen, die Häufigkeit und die Historie eines Objects mit einzubeziehen.

Je Object im Cache kommt ein Zähler hinzu, der der bei Verwendung und Nichtverwendung dessen Wert nach oben oder nach unten verändert wird.
Wird ein Object angesprochen, so wird sein Wert z.B. auf 50 gesetzt. Wird er geladen, wird sein Wert z.B. auf 10 gesetzt. Wird bei eine Cacheanfrage ein Object nicht angesprochen, wird er z.B. um 1 verringert. Wird er bei einer weiteren Cacheanfrage auch nicht angesprochen, wird der Zähler z.B. um 2 veringert. (und möglicherweise so weiter).

Wird Platz benötigt, wird aus dem Cache das Element entfernt, welches den geringsten Wert hat. Wenn es mehrere mit gleichem geringstem Wert gibt, dann halt das älteste.

Auf diese Weise könnte nun also Item[45] und Item[54] trotz der neuen 9 Items im Cache bleiben, außer sie werden einige Zeit nicht benutzt. Die Werte, die gesetzt werden müssen natürlich der Gesamtgröße des Caches angepasst sein.

Ist nur mal so eine Idee. Also nicht steinigen, wenn's ne blöde Idee ist.

Jetzt kann es natürlich sein, dass der Verwaltungsoverhead für die Werte einen möglichen Performancegewinn wieder auffressen.

[Edit] Grad gesehen, dass Idefix2 fast das gleiche geschrieben hat [/Edit]

[idefix2]

Zitat von Dejan Vu:

Zitat von Uwe Raabe:

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread).

Du irrst .

Uwe Raabe hat Recht. Deine Vorgabe verlangt, dass die Häufigkeit der Zugriffe berücksichtigt wird, in deinem Ansatz geht es nur darum, auf welches Element am längsten nicht zugegriffen worden ist, auch wenn davor die Zugriffe sehr häufig waren.

Zitat:

So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden

Eben nicht. Sie enthält vorne die Elemente, die vor kurzem abgefragt wurden. Was in der Tendenz öfter war, darüber speicherst du keinerlei Informationen.

[Daniel]

Es ist doch nur eine Spiel-Aufgabe. Wenn sich herausstellt, dass die Vorgaben unterschiedlich interpretiert werden können, dann legt sie doch einfach für Eure Lösung fest, das dürfte schneller gehen, als sich mit allen auf eine Interpretation zu einigen. Und eine starre Skala, auf der man die "absolut beste" Lösung wird bewerten können, dürfte so oder so schwierig werden.
Ich sehe den Variationen absolut gespannt entgegen.

[Memnarch]

Zitat von idefix2:

Zitat:

So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden

Eben nicht. Sie enthält vorne die Elemente, die vor kurzem abgefragt wurden. Was in der Tendenz öfter war, darüber speicherst du keinerlei Informationen.

Der unterschied: ich habe 5 elemente (A, B, C, D, E). 3 Elemente werden maximal gecached.

Bisherige anzahl an abfragungen/einträgen:

A = 10
B = 1
C = 1
---------<cachende>
D = 0
E = 0

Jetzt frage ich E, D und C an. A fällt aus dem cache raus. Bei Abfrageanzahl-Orientiertem Caching sehe das nach meiner Abfrage anders aus:

A = 10
B = 1
C = 2
D = 1
E = 1

was so ended:
A = 10
C = 2
D = 1
-----<cachende>
E = 0
B = 0