Wysoka częstość współbieżności dla pamięci podręcznej

Question

Uczę się buforowania i mam pytanie dotyczące współbieżności pamięci podręcznej.

Jak wiem, buforowanie LRU jest realizowane z podwójnie połączoną listą + hashtable. W jaki sposób pamięć podręczna LRU radzi sobie z wysoką częstotliwością współbieżności? Zauważ, że zarówno pobieranie danych z pamięci podręcznej, jak i umieszczanie danych w pamięci podręcznej spowoduje aktualizację połączonej listy i tabeli mieszania, dzięki czemu pamięć podręczna będzie cały czas modyfikowana.

Jeśli korzystamy z blokady mutex dla wątków bezpieczne, czy prędkość nie zostanie spowolniona, jeśli pamięć podręczna jest odwiedzana przez dużą liczbę osób? Jeśli nie używamy zamka, jakie techniki są stosowane? Z góry dziękuję.

Answer 1

Tradycyjne pamięci podręczne LRU nie są zaprojektowane do dużej współbieżności z powodu ograniczonego sprzętu, a kara za trafienie jest znacznie mniejsza niż kara za błąd (np. Wyszukiwanie bazy danych). W przypadku większości aplikacji blokowanie pamięci podręcznej jest akceptowalne, jeśli służy tylko do aktualizacji podstawowej struktury (nie obliczaj wartości na omijaniu). Proste techniki, takie jak segmentowanie zasad LRU, były na ogół wystarczająco dobre, gdy zamki się stały.

Sposób tworzenia skali pamięci podręcznej LRU ma na celu uniknięcie aktualizacji zasad przy każdym dostępie. Kluczową obserwacją, którą należy wykonać, jest to, że użytkownik pamięci podręcznej nie dba o aktualną kolejność LRU. Jedyną troską wywołującego jest to, że pamięć podręczna utrzymuje rozmiar progu i wysoką częstotliwość trafień. Otwiera to drzwi do optymalizacji poprzez unikanie mutowania zasad LRU przy każdym odczycie.

Podejście przyjęte przez memcached polega na odrzuceniu kolejnych odczytów w oknie czasowym, np. 1 sekunda. Pamięć podręczna ma być bardzo duża, więc istnieje bardzo niska szansa na wyrzucenie słabego kandydata przez ten prostszy LRU.

Podejście przyjęte przez ConcurrentLinkedHashMap (CLHM), a następnie Guava's Cache, służy do rejestrowania dostępu w buforze. Bufor ten jest odwadniany pod blokadą LRU i przy użyciu try-lock żadna inna operacja nie musi być blokowana. CLHM używa wielu buforów pierścieniowych, które są stratne, jeśli bufor nie może nadążyć, ponieważ utrata zdarzeń jest preferowana do pogorszonej wydajności.

Podejście przyjęte przez Ehcache i redis jest probabilistyczną zasadą LRU. Odczyt aktualizuje znacznik czasu wpisu, a zapis iteruje pamięć podręczną, aby uzyskać losową próbkę. Najstarszy wpis zostaje eksmitowany z tej próbki. Jeśli próbka jest szybka do skonstruowania, a pamięć podręczna jest duża, eksmitowany wpis był prawdopodobnie dobrym kandydatem.

Prawdopodobnie istnieją inne techniki i oczywiście zasady pseudo LRU (takie jak ZEGAR), które oferują lepszą współbieżność przy niższym wskaźniku trafień.