Cache (pamięć podręczna): definicja, działanie i strategie zastępowania
Pamięć podręczna (cache): definicja, zasada działania i strategie zastępowania — praktyczny przewodnik po przyspieszaniu dostępu do danych i optymalizacji wydajności systemów.
Caching to termin używany w informatyce. Idea cache'a (wymawiane "gotówka" /ˈkæʃ/ KASH) jest prosta: często uzyskanie lub wygenerowanie pewnych danych jest czasochłonne lub kosztowne, więc zamiast za każdym razem powtarzać kosztowną operację, przechowuje się jej wynik w miejscu, do którego dostęp jest znacznie szybszy. W praktyce używa się dwóch klas nośników danych: jeden jest zwykle duży, lecz „powolny” (np. dysk twardy, pamięć masowa sieciowa), drugi jest mniejszy, ale dużo szybszy (np. pamięć SRAM w procesorze, pamięć RAM jako bufor). Podstawową ideą jest przechowywanie kopii często używanych fragmentów danych w szybkim nośniku — pamięci podręcznej. Kopia nie różni się semantycznie od oryginału, ale dostęp do niej jest zwykle szybszy lub tańszy czasowo, co zmniejsza średni czas potrzebny na odczyt danych.
Jak działa pamięć podręczna (cache)
Pamięć podręczna trzyma fragmenty danych (zwykle zorganizowane w tzw. bloki lub linie cache). Gdy system żąda pewnego bloku, najpierw sprawdzana jest pamięć podręczna — jeśli blok tam jest (tzw. cache hit), dostęp jest szybki. Gdy go nie ma (tzw. cache miss), blok trzeba pobrać z wolniejszego nośnika i często umieścić go w cache, co może wymagać usunięcia innego bloku (tzw. eviction).
Lokalność odniesienia
Skuteczność cache'a opiera się na dwóch rodzajach lokalności:
- Temporalna — jeśli dany blok był użyty niedawno, istnieje duże prawdopodobieństwo, że będzie użyty ponownie;
- Przestrzenna — dostęp do pewnego bloku często oznacza, że nastąpi dostęp do bloków „bliskich” mu logicznie lub adresowo.
Te właściwości powodują, że nawet mała pamięć podręczna poprawia średnią wydajność dostępu do danych. W tekście pierwotnym wspomniano lokalizację odniesienia — to właśnie opisane wyżej zasady lokalności.
Rodzaje cache i przykłady zastosowań
- Pamięć cache procesora (L1, L2, L3) — najmniejsze i najszybsze, trzyma instrukcje i dane najczęściej używane przez CPU.
- Cache dyskowy / systemu plików — RAM używany do buforowania odczytów/zapisów z dysku, przyspiesza operacje we/wy.
- Przeglądarki i CDN — przechowują kopie stron i zasobów, zmniejszając opóźnienia i obciążenie sieci.
- Cache DNS — przechowuje ostatnio rozwiązane nazwy domen, skracając czas odpowiedzi.
- Cache aplikacyjne i bazy danych — np. pamięci podręczne w pamięci (Redis, Memcached) przyspieszają odczyty często używanych rekordów.
Strategie zastępowania (eviction)
Gdy trzeba wstawić nowy blok do pełnego cache'a, wybiera się blok do usunięcia według określonej strategii:
- LRU (Least Recently Used) — usuwa się element najmniej niedawno używany;
- FIFO (First In, First Out) — usuwa się najstarszy wpis;
- LFU (Least Frequently Used) — usuwa się element z najmniejszą liczbą użyć;
- Random — usuwa się losowy wpis (czasem prostsze i wystarczające);
- oraz ich warianty i hybrydy (np. approximated LRU dla oszczędności pamięci).
Polityki zapisu (write policies)
W przypadku zapisu danych wyróżnia się m.in.:
- Write-through — zapis trafia jednocześnie do cache i do pamięci głównej (łatwe zapewnienie spójności, ale wolniejsze);
- Write-back — zapisuje się tylko w cache, a do pamięci głównej zmienione bloki są zapisywane później (wydajniejsze, ale wymaga oznaczania „brudnych” bloków i mechanizmów ich wypychania);
- Write-allocate vs no-write-allocate — decyzja, czy przy zapisie brakującego bloku najpierw wczytać go do cache, czy zapisać bezpośrednio do pamięci głównej.
Parametry projektowe
Podstawowe parametry cache'a to:
- rozmiar (ilość pamięci dostępnej na cache),
- rozmiar linii/bloku (jednostka przenoszona między pamięcią a cache),
- asocjacyjność (direct-mapped, set-associative, fully-associative) określająca, ile miejsc w cache może przechowywać dany blok adresowy),
- czas dostępu i przepustowość,
- współczynnik trafień (hit rate) i stawka błędów (miss rate) — kluczowe miary skuteczności.
Im większy cache, tym zwykle wyższy współczynnik trafień, ale też większy koszt fizyczny i — w niektórych konstrukcjach — dłuższy czas wyszukiwania wpisu. Stąd projektanci dobierają optymalny rozmiar i asocjacyjność dla danego zastosowania.
Spójność i problemy wieloprocesorowe
W systemach wielordzeniowych pamięci podręczne poszczególnych rdzeni mogą mieć kopie tych samych danych — konieczne są mechanizmy zapewniające spójność (cache coherence), np. protokoły MESI, aby uniknąć odczytów przestarzałych wartości.
Praktyczne uwagi i optymalizacje
- Dobór strategii zastępowania i parametrów zależy od wzorca dostępu do danych — LRU dobrze działa przy silnej lokalności temporalnej, LFU przy powtarzalnych wzorcach dostępu.
- Prefetching (wczytywanie kolejnych bloków przewidywanych do użycia) może zwiększyć trafienia przy przewidywalnych wzorcach.
- Cache warming — wstępne załadowanie często używanych danych po uruchomieniu systemu poprawia wydajność startową.
- W aplikacjach sieciowych warto pamiętać o mechanizmach unieważniania (cache invalidation) i czasie życia danych (TTL) — by nie serwować przestarzałych informacji.
Bufor a pamięć podręczna — różnice
Bufor i cache pełnią podobne role, ale różnią się celem i modelem użycia. Bufor (ang. buffer) służy zwykle do wyrównania prędkości między producentem a konsumentem danych (np. bufor dysku lub bufor sieciowy) i często jest jawnie zarządzany przez aplikację; klient może być świadomy istnienia bufora i korzystać z niego w określony sposób. Pamięć podręczna natomiast jest częściej mechanizmem transparentnym, którego celem jest przyspieszenie wielokrotnych odczytów poprzez przechowywanie kopii; klient zwykle nie musi explicitnie zarządzać cache'em ani wiedzieć o jego istnieniu.
Podsumowanie
Pamięć podręczna to uniwersalne narzędzie poprawiające wydajność systemów poprzez przechowywanie często używanych kopii danych w szybszym medium. Jej efektywność opiera się na lokalności odniesienia, odpowiednim doborze rozmiaru, asocjacyjności, polityk zapisu oraz strategii zastępowania. W praktyce cache występuje w wielu warstwach systemów komputerowych — od CPU, przez system plików, aż po warstwę aplikacyjną i sieciową — i jest jednym z najważniejszych mechanizmów optymalizacyjnych w informatyce.
Jak działają skrytki
Pamięć podręczna (cache) to blok pamięci do przechowywania danych, który prawdopodobnie zostanie ponownie wykorzystany. Procesor i dysk twardy często korzystają z pamięci podręcznej, podobnie jak przeglądarki internetowe i serwery internetowe.
Skrytka składa się z wielu wpisów, zwanych pulą. Każdy wpis przechowuje w sobie datum (bit danych), które jest kopią datum w innym miejscu. Skrytki zazwyczaj korzystają z tego, co nazywane jest skrytką zapasową. Sklepy, do których dostęp jest powolny lub kosztowny, w porównaniu do skrytki. Na przykład pamięć podręczna dysku używa dysku twardego jako magazynu kopii zapasowej. Do każdego wpisu dołączona jest również niewielka ilość informacji, zwana tagiem. Znacznik ten jest używany do wyszukiwania miejsca, w którym przechowywane są oryginalne dane.
Skrytki do czytania
Klient (procesor, przeglądarka internetowa, system operacyjny) chce uzyskać dostęp do pewnej ilości danych, uważa, że znajdują się one w magazynie, najpierw sprawdza, czy dane znajdują się w pamięci podręcznej. Jeśli dane można znaleźć w pamięci podręcznej, klient może z niej korzystać i nie musi korzystać z pamięci głównej. Jest to tzw. cache hit. Tak więc, na przykład, program przeglądarki internetowej może sprawdzić, czy na dysku znajduje się lokalna kopia zawartości strony internetowej pod określonym adresem URL. W tym przykładzie, adres URL jest znacznikiem, a zawartość strony internetowej jest punktem odniesienia.
Inną sytuacją, która może się zdarzyć jest to, że w pamięci podręcznej nie można znaleźć danych z tagiem. Jest to tzw. cache miss. Dane muszą zostać pobrane z magazynu, w którym znajduje się nośnik danych. Zazwyczaj jest on kopiowany do pamięci podręcznej, więc następnym razem nie musi być już pobierany z magazynu, w którym znajduje się nośnik danych.
Skrytka ma tylko ograniczony rozmiar. Aby zrobić miejsce dla wcześniej nie buforowanego wpisu, może być konieczne usunięcie innego zbuforowanego wpisu z pamięci podręcznej. Specjalne zasady są stosowane w celu znalezienia wpisu, który najlepiej jest usunąć. Zasady te są zazwyczaj nazywane Heurystyką. Heurystyka używana do znalezienia wpisu nazywana jest polityką zastępowania. Bardzo prosta reguła nazywana jest Najświeżej używaną (lub LRU). Polega ona po prostu na znalezieniu wpisu, który był używany najdłużej. Inne heurystyki są wymienione w algorytmie cache...
Skrytki do pisania
Cache może być również używany do zapisu danych; zaletą tego jest to, że klient może kontynuować swoją pracę po zapisaniu wpisu do pamięci podręcznej; nie musi czekać, aż wpis zostanie zapisany na nośniku.
Wpis musi być jednak w pewnym momencie zapisany na nośniku. Moment, w którym to nastąpi, jest kontrolowany przez zasady zapisu.
W pamięci podręcznej każdy wpis jest natychmiast zapisywany na nośniku, jak również przechowywany w pamięci podręcznej.
Drugą opcją jest tylko zapis do pamięci podręcznej, a następnie zapis do magazynu kopii zapasowych. Jest to tzw. write-back (lub write-behind) cache. Pamięć podręczna oznacza wpisy, które nie zostały jeszcze zapisane w pamięci podręcznej; znak, który jest używany jest często określany jako brudna flaga. Przed usunięciem wpisów z pamięci podręcznej, są one zapisywane w pamięci podręcznej. Jest to tzw. leniwe pismo. Braki w pamięci podręcznej typu write-back (która wymaga zastąpienia bloku przez inny) często wymagają dwóch dostępów do pamięci: jednego, aby uzyskać potrzebne dane, a drugiego, aby zapisać zastąpione dane z pamięci podręcznej do magazynu.
Polityka buforowania może również stanowić, że do buforowania musi być zapisany pewien punkt odniesienia. Klient mógł dokonać wielu zmian w bazie danych w buforze. Po tym jak to zostanie zrobione, może on wyraźnie powiedzieć cache'owi, aby spisał dane odniesienia.
Alokacja bez zapisu to polityka pamięci podręcznej, w której buforowane są tylko odczyty. Pozwala to na uniknięcie konieczności zapisu zwrotnego lub zapisu przez buforowanie. Zapisy są cały czas wykonywane do magazynu kopii zapasowych.
Klient nie jest aplikacją, która zmienia dane w sklepie z kopiami zapasowymi. W przypadku zmiany danych w magazynie kopii zapasowej, kopia w pamięci podręcznej będzie nieaktualna lub nieaktualna. Alternatywnie, gdy klient zaktualizuje dane w buforze, kopie tych danych w innych buforach staną się nieaktualne. Istnieją specjalne protokoły komunikacyjne, które pozwalają menedżerom pamięci podręcznej rozmawiać ze sobą w celu zachowania znaczenia danych. Są one znane jako protokoły spójności.
Schemat pamięci podręcznej procesora
Wybranie pozycji do zastąpienia
Skrytka jest mała, i przez większość czasu będzie pełna, lub prawie pełna. Więc kiedy dodawana jest nowa wartość, stara musi zostać usunięta. Istnieją różne sposoby, na jakie można dokonać tego wyboru:
- Pierwszy na pierwszym miejscu: Po prostu zmień wpis, który został dodany do pamięci podręcznej najdłuższy czas temu
- Najmniej ostatnio używany: Ten pomysł jest podobny do powyższego FIFO, ale kiedy wpis jest używany, jego znacznik czasowy/etat jest aktualizowany.
- Najrzadziej używany: Ponownie, podobnie jak w przypadku FIFO, zamiast używać znacznika czasu używa się licznika, który jest zwiększany za każdym razem, gdy używany jest wpis.
- Wybierz losowo wpis
Historia
Słowo "cache" zostało po raz pierwszy użyte w informatyce w 1967 roku, kiedy to przygotowano artykuł naukowy do opublikowania w IBM Systems Journal. Artykuł ten dotyczył nowego usprawnienia pamięci w Modelu 85. Model 85 był komputerem z linii produktów IBM System/360. Redaktor czasopisma chciał lepszego słowa na temat bufora o dużej szybkości, który został wykorzystany w artykule. Nie dostał żadnego wejścia i zasugerował cache, od francuskiego cache'a, czyli "ukryć". Artykuł został opublikowany na początku 1968 roku, a jego autorzy zostali uhonorowani przez IBM. Ich praca została szeroko przyjęta i poprawiona. Cache szybko stał się standardem w literaturze komputerowej.
W przypadku korzystania ze skrytek
skrytki procesora
Małe wspomnienia na układzie CPU lub w jego pobliżu mogą być wykonane szybciej niż znacznie większa pamięć główna. Większość procesorów od lat 80-tych używa jednej lub więcej pamięci podręcznych. Nowoczesne procesory ogólnego przeznaczenia w komputerach osobistych mogą mieć aż pół tuzina. Każda pamięć podręczna może być wyspecjalizowana do innej części zadań związanych z wykonywaniem programów.
Skrytki dyskowe
Skrytki procesora są zazwyczaj zarządzane całkowicie przez sprzęt, inne są zarządzane przez różne rodzaje oprogramowania. System operacyjny zazwyczaj zarządza stroną w pamięci głównej. Użytkownicy spoza branży informatycznej zazwyczaj nazywają tę pamięć podręczną pamięcią wirtualną. Jest ona zarządzana przez jądro systemu operacyjnego.
Nowoczesne dyski twarde posiadają bufory dyskowe. Bufory te są czasami nazywane "disk cache", ale to jest złe. Główną funkcją tych buforów jest porządkowanie zapisów dyskowych i zarządzanie odczytami. Powtarzające się uderzenia pamięci podręcznej są rzadkie, ponieważ bufor jest bardzo mały w porównaniu do rozmiaru dysku twardego.
Lokalne dyski twarde są szybkie w porównaniu z innymi urządzeniami pamięci masowej, takimi jak serwery zdalne, lokalne napędy taśmowe lub szafy grające. Wykorzystanie lokalnych dysków twardych jako pamięci podręcznej jest główną koncepcją hierarchicznego zarządzania pamięcią masową.
Skrytki internetowe
Przeglądarki internetowe i serwery proxy używają pamięci podręcznej do przechowywania poprzednich odpowiedzi z serwerów internetowych, takich jak strony internetowe. Skrytki internetowe zmniejszają ilość informacji, które muszą być przesyłane przez sieć. Informacje wcześniej zapisane w pamięci podręcznej mogą być często wykorzystywane ponownie. Zmniejsza to przepustowość i wymagania dotyczące przetwarzania danych przez serwer sieciowy, a także pomaga poprawić szybkość reakcji użytkowników sieci.
Nowoczesne przeglądarki internetowe używają wbudowanej pamięci podręcznej, ale niektórzy dostawcy usług internetowych lub organizacje również używają serwera proxy z funkcją buforowania. Jest to web cache, który jest wspólny dla wszystkich użytkowników tej sieci.
Wyszukiwarki internetowe często udostępniają również strony internetowe, które zaindeksowały, z ich pamięci podręcznej. Na przykład, Google udostępnia link "Cache" obok każdego wyniku wyszukiwania. Jest to przydatne, gdy strony internetowe są chwilowo niedostępne z serwera WWW.
Cachowanie z nierzetelnymi sieciami
Praca przelotowa jest powszechna w zawodnych sieciach (np. Ethernet LAN). Protokół używany do zapewnienia, że dane w pamięci podręcznej zapisu mają sens w przypadku zastosowania kilku pamięci podręcznych zapisu, jest w takim przypadku bardzo skomplikowany.
Na przykład, cache stron internetowych i cache systemów plików sieciowych po stronie klienta (jak te w NFS lub SMB) są zazwyczaj tylko do odczytu lub zapisu, aby zachować prosty i niezawodny protokół sieciowy.
Różnica między buforem a skrytką
Bufor i pamięć podręczna nie wykluczają się wzajemnie; są też często używane razem. Powód, dla którego są one używane, jest jednak inny. Bufor to miejsce w pamięci, które jest tradycyjnie używane, ponieważ instrukcje CPU nie mogą bezpośrednio adresować danych przechowywanych w urządzeniach peryferyjnych. Pamięć komputerowa jest używana jako pamięć pośrednia.
Ponadto taki bufor może być wykonalny, gdy duży blok danych jest montowany lub demontowany (zgodnie z wymogami urządzenia pamięci masowej) lub gdy dane mogą być dostarczane w innej kolejności niż ta, w której są wytwarzane. Również cały bufor danych jest zazwyczaj przesyłany sekwencyjnie (np. na dysk twardy), więc samo buforowanie czasami zwiększa wydajność transferu. Korzyści te są obecne nawet wtedy, gdy dane buforowane są zapisywane do bufora raz i odczytywane z niego raz.
Pamięć podręczna również zwiększa wydajność transferu. Część tego wzrostu wynika również z możliwości połączenia wielu małych transferów w jeden duży blok. Ale główny wzrost wydajności występuje, ponieważ istnieje duża szansa, że te same dane zostaną odczytane z cache'u kilka razy, lub że zapisane dane zostaną wkrótce odczytane. Jedynym celem cache'ów jest ograniczenie dostępu do bazowej wolniejszej pamięci masowej. Cache jest również zazwyczaj warstwą abstrakcyjną, która jest zaprojektowana tak, aby była niewidoczna z perspektywy sąsiednich warstw. W ten sposób aplikacje lub klienci mogą nie być świadomi istnienia pamięci podręcznej.
Pytania i odpowiedzi
P: Co to jest buforowanie?
O: Buforowanie to termin używany w informatyce, który odnosi się do praktyki przechowywania kopii danych, które są często używane, aby uzyskać do nich dostęp szybciej niż ponowne pobieranie lub przeliczanie oryginalnych danych.
P: Jak działa buforowanie?
O: Buforowanie działa poprzez wykorzystanie dwóch rodzajów nośników danych, jednego, który jest zazwyczaj dość duży, ale wolno dostępny, i drugiego, do którego dostęp jest znacznie szybszy, ale który jest ogólnie mniejszy. Ideą buforowania jest wykorzystanie szybkiego nośnika do przechowywania kopii danych, tak aby dostęp do oryginalnych danych trwał krócej lub był mniej kosztowny.
P: Co to jest bufor?
O: Bufor jest podobny do pamięci podręcznej, ponieważ przechowuje kopie danych w celu uzyskania szybszego dostępu, jednak w przypadku bufora klient uzyskujący dostęp do danych wie, że istnieje bufor i jest on zarządzany przez aplikację, podczas gdy w przypadku pamięci podręcznej klient nie musi wiedzieć, że istnieje pamięć podręczna.
P: Co oznacza lokalność odniesienia?
O: Lokalność odniesienia oznacza, że kiedy aplikacja uzyskuje dostęp do pewnych bloków danych strukturalnych, prawdopodobnie uzyska również dostęp do innych bloków, znajdujących się w pobliżu tych, do których uzyskała dostęp. Dzięki temu pamięć podręczna działa dobrze, ponieważ jest ona zazwyczaj niewielka w porównaniu do wszystkich dostępnych danych.
P: Dlaczego większe pamięci podręczne dłużej szukają wpisów?
O: Większe pamięci podręczne działają dłużej, ponieważ zawierają więcej zapisanych informacji i dlatego wymagają więcej czasu na wyszukiwanie. Są one również droższe, ponieważ wymagają więcej zasobów do przechowywania.
P: Jak lokalność może pomóc w lepszym funkcjonowaniu pamięci podręcznej?
O: Lokalność pomaga usprawnić działanie pamięci podręcznej, ponieważ gdy aplikacje mają dostęp do pewnych bloków danych strukturalnych, prawdopodobnie będą również potrzebować innych pobliskich bloków, które można szybko pobrać z pamięci podręcznej, zamiast pobierać je z innego miejsca lub ponownie obliczać.
Przeszukaj encyklopedię