LRUMap und Synchronisation

[huckfinn]

Hallo Leute,

ich benutze eine LRUMap der jakarta Commons Collecion Map um eine Speichestruktur auf einem begrenzten
Verbrauchsniveau zu halten. Dies tue ich ein einem Servlet, so daß man davon ausgehen kann, daß meherere
Prozesse auf diesen "Cache" gleichzeitig zugreifen. In der Beschreibung der Klasse steht, daß diese adhoc nicht Thread Safe
ist. Ich habe nun folgenden Code der auf den Cache zugreift und sicherstellen soll, daß immer ein Objekt
zurückliefert wird daß daß nicht NULL ist und falls es im Cache nicht gefunden wird dieses nachlädet.

    package ...
    import org.apache.commons.collections.map.LRUMap;
    .....
    //__________________________________________________________________________
    /** Der Dokumentencache */
     private LRUMap documentCache = new LRUMap(defaultLRUMapSize);
    ...INITIALIZIRUNG

    //__________________________________________________________________________
    /** Zugriff auf den Dokumentencache  */
    public OaiDocumentRegisterEntry  getCacheEntry(int docIdent) 
    throws OaiException {
        OaiDocumentRegisterEntry result = null;
        // ____Suche im Cache ____________
        result = (OaiDocumentRegisterEntry)
                                 documentCache.get(Integer.valueOf(docIdent));
        
        // ____Nachladen von der Db und ablegen im Cache _______
        if (result==null) {
            result = loadDocumentEntry(docIdent);
            documentCache.put(Integer.valueOf(docIdent),result);
        }
        return result;
    }

Erste Frage: Bei einer Konkurenz von Prozessen/ Threads kann es nun sein, daß das Objekt aus dem
Cache entfernt wird. Vermutilch währen der Schreiboperation

documentCache.put(Integer.valueOf(docIdent),result);

wird der Cache reorganiziert. Wo muß ich die Synchronization setzen, auf die Leseoperation

result = (OaiDocumentRegisterEntry)
                                 documentCache.get(Integer.valueOf(docIdent));

Zweite Frage: Wenn ich einen Cache der Tiefe/ Größe 64 habe und 128 Threads die auf das System zugreifen, ist die
Wahrscheinlichkeit hoch, daß der Cache in permateneter Überladung der Tabelle endet also nich mehr cached
(Oversampling by request). Gibt es einen etablierten Mechanisnus, der eine quasi optimale Cachgröße berechent (Anzahl der Einträge)
. .sowas wie das Sampling Theorem in der Stochasik/Signaltheorie, welches das mögliche erreichbare
Signalrauschabstandsverhältnis abschätzt..

Vielen Dank huckfinn

 

[huckfinn]

Sorry ..der Abkürzungsteufel LRU ist Least Recently Used (LRU) ein Cache Alogirthmus:

de.wikipedia.org/wiki/Least_recently_used

oder

en.wikipedia.org/wiki/Cache_algorithms

bis denne huckfinn

 

[kleiner_held]

Du mußt alle zusammengehörigen Operationen synchronisieren (passender Synchronisationsmonitor wäre die LRUMap selbst)
In deinem Fall

public OaiDocumentRegisterEntry  getCacheEntry(int docIdent)
    throws OaiException {
        OaiDocumentRegisterEntry result = null;
        synchronized(documentCache) {
          // ____Suche im Cache ____________
          result = (OaiDocumentRegisterEntry)
                                 documentCache.get(Integer.valueOf(docIdent));
       
          // ____Nachladen von der Db und ablegen im Cache _______
          if (result==null) {
            result = loadDocumentEntry(docIdent);
            documentCache.put(Integer.valueOf(docIdent),result);
          }
        }
        return result;
    }

Du musst aber auch alle get() oder put() Operationen auf der LRUMap synchronisieren, die an anderer Stelle auftreten, auch wenn sie dort nur einzeln auftreten und atomar erscheinen (was sie nicht sind).
Um sicherzugehen würde ich dir empfehlen, die Map auch nochmal implizit zu synchronisieren, also

private Map documentCache = Collections.synchronizedMap(new LRUMap(defaultLRUMapSize));

Damit wird aber ein Wrapper um die LRUMap gelegt, und du kannst nur noch auf die Methoden zugreifen, die das Interface Map anbietet. Ein Cast ala

LRUMap castedMap = (LRUMap) documentCache;

funktioniert dann nicht mehr.

Was deine zweite Frage angeht, so kenne ich keinen solchen Mechanismus. Nach meinem Verständnis hängt ja die Hit-Quote eines Caches nicht primär von der Anzahl der zugreifenden Prozesse ab, sondern vom Zugriffsschema. Normalerweise ist die Herangehensweise, dass an der Cachingstrategie optimiert wird, denn wenn ich theoretisch noch Möglichkeiten habe, um die Cachegröße zu erweitern, dann nutze ich sie doch von Anfang an. Soweit ich mich erinnere, gab es auch bei den Cachingstrategien eine (theoretische) optimale Strategie, aber die war nur dazu da, um die Effizienz anderer Strategien daran zu messen. Dabei schaute man sich im Nachhinein an, welche Ersetzung am besten gewesen wäre.

 

[huckfinn]

Hallo kleiner_held,

Vielen Dank für die kompetente und schnelle Antwort. Ich kann sie so direkt implementieren, da ich nur die put() und get() Routinen des Map interfaces nutze.

Nun noch eimal zur 2. Frage. Wenn die Anzahl der gehaltenen Objekte gegenüber der anfragenden Prozesse klein wird, wächst die Wahrscheinlichkeit, daß die Hitquote gleichverteilt ist und damit bei jeder put() Operation ein Entrag mi dem in der Datenbank getauscht wird ..man würde quasi auf der Datenbank arbeiten. Das Problem, daß mich umtreibt ist folgendes. Wenn ich einen Server habe, kann ich die Menge der zugreifenden Nutzer schwer abschätzen, aber im Mittel messen und danach die Cachegröße einstellen. Ich kann also die Größe des jeweilgen Caches nachführen in dem ich ein zeitlich gleitendes Mittel oder eine Trashholdrate der Relaodzyklen nutze, um den Cache auf einem "schnellen" Niveau zu halten. Dabei muß natürlich eine oberen Grenze der Speichernutzung gelten. Hast du/iher vielleicht einen Link oder einen Literaturverweis, der sich mit der Problematik beschäftigt.

Vielen Dank huckfinn

 

[kleiner_held]

Hmm also mit weitergehender Literatur kann ich leider nicht dienen, das letzte mal, als ich das auf theoretischer Basis durchgenommen hab, war auf der Uni. Die Wahl der richtigen Cachegroesse, wenn man einen gewissen Spielraum hat, ist natuerlich immer kritisch. Ich habe sowas bisher immer nach Bauchgefuehl gemacht. Wenn du ueberhaupt keinen Anhaltspunkt hast, kannst du einen (abschaltbaren) Statistik-Logger ueber einen Evaluierungszeitraum mitlaufen lassen, der dir Hit- und Miss-Quote mitloggt. Das Cachingframework welches wir bei uns im Projekt einsetzen (Ehcache), bietet so etwas glaube ich von Haus aus mit an (bin mir aber nicht sicher, ist nicht ganz mein Zustaendigkeitsbereich).

 

[huckfinn]

Hallo kleiner_held,

Das sieht vielversprechend aus. Vielen Dank Huckfinn