Hohe häufige Nebenläufigkeit für den Cache

Question

Ich lerne Caching und habe eine Frage über die Parallelität von Cache.

Wie ich weiß, ist LRU-Caching mit doppelt verketteten Liste + Hashtabelle implementiert. Wie behandelt der LRU-Cache die häufig auftretende Nebenläufigkeit? Beachten Sie, dass sowohl das Abrufen von Daten aus dem Cache als auch das Übergeben von Daten in den Cache die verknüpfte Liste und Hash-Tabelle aktualisiert, so dass der Cache ständig geändert wird.

Wenn wir Mutex Lock für thread-safe verwenden, wird die Geschwindigkeit nicht verlangsamt, wenn der Cache von einer großen Anzahl von Leuten besucht wird? Wenn wir keine Sperre verwenden, welche Techniken werden verwendet? Danke im Voraus.

Answer 1

Herkömmliche LRU-Caches sind aufgrund begrenzter Hardware nicht für hohe Parallelität ausgelegt, und die Trefferpunktzahl ist viel geringer als die Fehleinschätzung (z. B. Datenbanksuche). Für die meisten Anwendungen ist das Sperren des Caches akzeptabel, wenn es nur dazu verwendet wird, die zugrunde liegende Struktur zu aktualisieren (den Wert für einen Fehlversuch nicht berechnen). Einfache Techniken wie das Segmentieren der LRU-Richtlinie waren normalerweise gut genug, wenn die Sperren strittig waren.

Die Möglichkeit, einen LRU-Cache-Maßstab zu erstellen, besteht darin, die Richtlinie nicht bei jedem Zugriff zu aktualisieren. Die kritische Beobachtung ist, dass es dem Benutzer des Caches egal ist, was die aktuelle LRU-Anordnung ist. Das einzige Problem des Aufrufers ist, dass der Cache eine Schwellenwertgröße und eine hohe Trefferrate beibehält. Dies öffnet die Tür für Optimierungen, indem vermieden wird, dass die LRU-Richtlinie bei jedem Lesen mutiert wird.

Der von memcached verfolgte Ansatz besteht darin, nachfolgende Lesevorgänge innerhalb eines Zeitfensters, z. 1 Sekunde. Es wird erwartet, dass der Cache sehr groß ist, so dass eine sehr geringe Chance besteht, einen armen Kandidaten durch diese einfachere LRU zu vertreiben.

Der Ansatz von ConcurrentLinkedHashMap (CLHM) und anschließend Guava's Cache ist, den Zugriff in einem Puffer aufzuzeichnen. Dieser Puffer wird unter der LRU-Sperre entleert, und unter Verwendung einer try-lock muss keine andere Operation blockiert werden. CLHM verwendet mehrere Ringpuffer, die verlustbehaftet sind, wenn der Cache nicht mithalten kann, da das Verlieren von Ereignissen einer schlechteren Leistung vorgezogen wird.

Der Ansatz von Ehcache und redis ist eine probabilistische LRU-Richtlinie. Ein Lesevorgang aktualisiert den Zeitstempel des Eintrags und ein Schreibvorgang wiederholt den Cache, um eine Zufallsstichprobe zu erhalten. Der älteste Eintrag wird aus dieser Stichprobe entfernt. Wenn die Stichprobe schnell erstellt werden muss und der Cache groß ist, war die Räumung wahrscheinlich ein guter Kandidat.

Es gibt wahrscheinlich andere Techniken und, natürlich, Pseudo-LRU-Richtlinien (wie CLOCK), die bessere Parallelität bei niedrigeren Trefferraten bieten.