Cache LRU: Zrzucanie najmniej ostatnio użytego elementu

Dlaczego pamięci podręczne potrzebują polityki wygrywania

Pamięć podręczna istnieje, aby utrzymywać małą i szybką kolekcję elementów blisko siebie, co pozwala na powtórne żądania bez ponoszenia kosztu pobierania z wolniejszego źródła, czy to pamięci RAM, dysku, bazy danych lub oddalonego serwera. Jednak szybkie magazyny zawsze są skończone: cache CPU mierzy się megabajtami, bufor bazy danych — gigabajtami, a węzły CDN mają tylko ułamki przestrzeni dostępnej na serwerach źródłowych. Gdy ta ustalonej pojemności jest pełna, dodanie nowego elementu oznacza, że coś już istniejącego musi wyjść. Zasada decydująca, który element ma wyjść, to polityka wygrywania, a jej wybór ma ogromne znaczenie dla wydajności. Gubicia słabej polityki przekształca dostępne dane w nowe żądanie kosztowne, co przekształca pamięć podręczną z przyspieszającego elementu w dodatkowe obciążenie. Dobrych polityk zachowuje elementy najbardziej prawdopodobne do ponownego użycia i usuwa te, które już się chłodziły. Ponieważ rzeczywiste obciążenia tendencjonalnie wykazują lokalizację w czasie — jeśli coś zostało niedawno odwiedzone, jest przewyższo prawdopodobne, że zostanie ponownie odwiedzone wkrótce — polityki wygrywające śledzący recencyjność tendencjonalnie działają bardzo dobrze na praktyce. To cała motywacja za taktiką Least Recently Used: zamiast losowo przewidzielić czy usuwać w porządku przybycia, używa historii dostępu każdego elementu jako sygnału, czy należy go zachować.

Ponure zasada

Eviction Least Recently Used (LRU) obserwuje jedno przepisane zasady: gdy bufor jest pełny i należy wstawić nowy element, usuń ten, który najdłużej nie był używany. Każdego razu, gdy element jest odczytany lub zaktualizowany, traktuje się go jako nowo użyty i przenosi na początek urojonego kolejki uporządkowanej według recencyjności. Element zającający ostatnie miejsce w tej kolejce, taki, który nie był dotychczas używany przez najdłuższy czas, zawsze jest kandydatem do usuwania. Działa to tak, że LRU jest dobrym przybliżeniem idealnej (ale praktycznie niemożliwej) strategii usuwania tego, co będzie potrzebne najbardziej w przyszłości, ponieważ ostatnie użycie często najlepiej przewiduje użycie blisko przyszłe. Dwa operacje definiują politykę: get, który odczytuje element, jeśli jest obecny, i oznacza go jako niedawno użyty, a put, który wstawia lub aktualizuje element, a jeśli bufor jest już pełen, spowoduje usunięcie najdłużej nieużywanego wpisu. Elegancja LRU polega na tym, że potrzebuje ona tylko pamięci o porządku, bez statystyk, liczników ani modeli przewidywania; wystarczy znać kolejność. Ta prosta konstrukcja jest dokładnie to, co pozwala na efektywną implementację, co jest tematem następnego rozdziału.

Hash Map Plus Doubly Linked List

Klasyczna implementacja LRU połącza dwie struktury danych w taki sposób, że każda operacja wykonuje się w czasie stałym, niezależnie od liczby elementów przechowywanych w buforze. Mapa hashewna zapisuje klucz bezpośrednio do lokalizacji węzła, co daje czas odczytu stały: podanej klucza wystarczy znaleźć pasującą pozycję w pamięci bez konieczności przeszukiwania. Lista dwukierunkowa łączy wszystkie elementy w porządku najnowszej użyteczności, z najbardziej ostatnio używanym elementem na początku i najmniej używanym na końcu. Ponieważ jest dwukierunkowa, każdy węzeł można odłączyć z bieżącej pozycji i przylecić do innej w czasie stałym, bez konieczności przechodzenia przez listę. Podczas odczytu mapa hashewna lokalizuje węzeł natychmiastowo, a następnie odłączony jest i wprowadzany na początek, ponieważ teraz jest najbardziej ostatnio używanym elementem — obie operacje są operacjami wskaźnikowymi o czasie stałym. Podczas dodawania nowego klucza (put) tworzony jest węzeł, który jest dodawany na początek i wprowadzany do mapy hashewnej; jeśli bufor był pełny, węzeł na końcu jest odłączony i jego klucz usunięty z mapy, co dokładnie odpowiada kroku usuwania. Podczas aktualizacji istniejącego klucza (put) węzeł jest przesuwany na początek tak samo jak podczas odczytu. Nie obie struktury samodzielnie bylibyły tak dobrze działające: mapa hashewna sama nie ma pojęcia o porządku, a prosta lista oparta na tablicach potrzebowałaby przesunięć liniowych do zmiany kolejności lub usuwania elementów. Wspólne działanie obu struktur daje O(1) dla operacji odczytu i O(1) dla operacji reorganizacji, kombinacja, która sprawia, że LRU jest praktyczny nawet na bardzo dużych skalach.

Przykładowy Obliczeniowy Przepis, Krok Po Kroku

Załadujmy pamięć podręczną o pojemności 3 i sekwencję dostępu do kluczy A, B, C, D, B, E. Początkowo jest ona pusta. Dostęp A: nie ma go w pamięci podręcznej, więc go wpisujemy; kolejność od najnowszej do najstarszej to A. Dostęp B: nie ma go w pamięci podręcznej, więc go wpisujemy; kolejność to B, A. Dostęp C: nie ma go w pamięci podręcznej, więc go wpisujemy; pamięć podręczna jest pełna i kolejność to C, B, A. Dostęp D: nie ma go w pamięci podręcznej i pamięć jest pełna, więc evicujemy najstarszy element, który to A na końcu; wpisujemy D na początek; kolejność to D, C, B, a A jest już usunięty. Dostęp B: jest on obecny, co oznacza trafienie; przenosimy go na początek bez evicowania czegoś innego; kolejność to B, D, C. Dostęp E: nie ma go w pamięci podręcznej i pamięć jest pełna, więc evicujemy element na końcu, który to C; wpisujemy E na początek; kolejność to E, B, D, a C jest już usunięty. Zauważmy, że B przetrwał pierwszy cykl evicji dokładnie dlatego, że został ponownie dostarczony przed tym, jak doleciałby do końca i zostałby evicowany jako najstarszy element w pełnej pamięci podręcznej, podczas gdy A i C były evicowane na moment, gdy stały się najstarszymi elementami w pełnej pamięci. Ta ścieżka pokazuje mechanizmy, które symulator robi widocznymi w czasie rzeczywistym: każdy dostęp albo przenosi element do początku, albo wyzwania dokładnie jedno evicowanie z końca, a kombinacja mapy hash i listy skojarzonej wykonuje te kroki bez konieczności przeszukiwania całego cache.

Porównanie Polityk i Zastosowań Wirtualnych

LRU jest jedną z wielu strategii wycofywania (eviction strategies), a właściwy wybór zależy od wzoru dostępu. FIFO (first in, first out) wycofuje najwcześniej wstawiony element, ignorując, ile razy był on ostatnio używany; jest prościej zaimplementować, ale wykonuje się gorsze, gdy stary element nadal jest często używany, ponieważ FIFO go wycofuje, jak tylko dojdzie do jego tur. LFU (least frequently used) śledzi ile razy każdy element został użyty i wycofywało ono ten z najmniejszą liczbą użyci; nagradza elementy, które są popularne w długiej perspektywie, ale może mieć trudności przy dostosowywaniu się do sytuacji, gdy poprzednio popularny element nagle staje się niepopularny, ponieważ jego wysoka historia użycia pozostawia go w pamięci po tym, jak przestał być użyteczny. LRU znajduje się pomiędzy: reaguje szybko na zmieniające się wzory, ponieważ uwzględnia tylko recency, a nie zbilansowane historie, co sprawia, że jest silnym domyślnym rozwiązaniem ogólne. Te kompromisy mają znaczenie dalej niż podręczniki akademickie. Bufor cache CPU używa podobnych do LRU polityk (często przybliżonych w harware dla szybszego działania) do decyzji, które linie cache zachować podczas dostępu do pamięci przez programy. Bazy danych używają LRU lub jego wariantów do decyzji, które strony dysku pozostawić w pamięci, ponieważ odczytywanie strony z dysku jest znacznie wolniejsze niż serwowanie jej z RAMu. Bufor cache brzegowe sieci web i CDN używa LRU do decyzji, które odpowiedzi zachować na brzegowych węzłach bliskich użytkownikom, wycofując stare lub rzadko żądane treści, aby miejsce zajmowały obecnie popularne. W każdym z tych systemów, ten sam wzorzec mapy hash i list dwukierunkowych, lub jego przybliżenie, działa w tle.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz LRU Cache: Evicting the Least Recently Used Item i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.