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!