Cache

Related Topics:
Cache :: Cache_Tools :: Cache_Junction :: Cache_Creek

Cache (pamięć podręczna) to mechanizm, w którym ostatnio pobierane dane dostępne ze źródła o wysokiej latencji i niższej przepustowości są przechowywane w pamięci o lepszych parametrach.

Cache jest elementem właściwie wszystkich systemów - współczesny procesor ma 2 albo 3 poziomy pamięci cache oddzielającej go od pamięci RAM. Dostęp do dysku jest buforowany w pamięci RAM, a dokumenty HTTP są buforowane przez pośredniki HTTP oraz przez przeglądarkę.

Systemy te są tak wydajne dzięki lokalności odwołań - jeśli nastąpiło odwołanie do pewnych danych, jest duża szansa, że w najbliższej przyszłości będą one potrzebne ponownie. Niektóre systemy cache próbują przewidywać, które dane będą potrzebne i pobierają je wyprzedzając żądania. Np. cache procesora pobiera dane w pakietach po kilkadziesiąt czy też więcej bajtów, cache dysku zaś nawet do kolejnych kilkuset kilobajtów czytanego właśnie pliku.

Niektóre systemy pamięci cache umożliwiają informowanie systemu na temat charakteru danych by umożliwiać bardziej efektywne buforowanie. Służy temu np. wywołanie systemowe madvise.

Zasady projektowania cache

Część systemu komputerowego zajmująca się buforowaniem danych powinna charakteryzować się następującymi właściwościami:

powinna być jak najbardziej automatyczna
jej działanie nie powinno wpływać na semantykę pozostałych części systemu
powinna w jak największym stopniu poprawiać wydajność systemu w warunkach rzeczywistej pracy

Projektując cache rozpatruje się pewne typowe warunki, w jakich będzie on wykorzystywany. Program korzystający z cache ma więcej informacji na temat użycia pamięci w najbliższym czasie, i wydajność systemu można polepszyć jeśli zrezygnuje się z pełnej automatyzacji a pozwoli na dawanie cache'owi sugestii co do właściwego zachowania w danej sytuacji. W ten sposób działa m.in. wywołanie systemowe madvise, specjalne instrukcje asemblera na niektórych procesorach, nagłówki kontroli cache'owania w HTTP; wiele DBMS pozwala też na przekazywanie kontrolerowi pamięci sugestii.

Zadanie cache można wyrazić w następujący sposób: mamy duży zbiór obiektów w powolnej pamięci, i niewielką ilość szybkiej pamięci, w której na pewno nie pomieszczą się wszystkie obiekty. Ciągle napływają żądania dostępu do obiektów, a cache musi je wszystkie spełnić w jak najmniejszym stopniu korzystając z pamięci powolnej.

Temperatura danych

Przy rozpatrywaniu systemu cache przydatne jest pojęcie "temperatury" - czyli prawdopodobieństwa, że w najbliższym czasie wpłynie żądanie dostępu do tego obiektu (jeśli obiekt jest duży, temperatura poszczególnych części może się różnić). Jest oczywiste, że powinniśmy w szybkiej pamięci trzymać obiekty o możliwie wysokiej temperaturze. Jednak temperatura obiektu nie jest znana, i musimy jakoś ją oszacować. Typowe heurystyki to:

lokalność czasowa - jeśli obiekt był ostatnio żądany, to jest duże prawdopodobieństwo, że będzie żądany ponownie w najbliższym czasie
lokalność przestrzenna - jeśli obiekt był ostatnio żądany, to prawdopodobnie będą też żądane obiekty leżące blisko niego. Położenie w wypadku pamięci komputera oznacza zwykle adres maszynowy. W przypadku plików na stronie internetowej, pliki linkujące do siebie leżą blisko siebie.
o niektórych typach obiektów wiemy, że ich średnia temperatura jest wyższa niż innych typów - np. temperatura pliku (z grubsza proporcjonalna do liczby ściągnięć) html na stronie internetowej jest zazwyczaj wyższa niż temperatura pliku pdf.

Żeby zmaksymalizować średnią temperaturę cache chcielibyśmy operować na poziomie jak najmniejszych jednostek, np. kilku bajtów. Byłoby to jednak bardzo niepraktyczne, więc używa się większych jednostek - np. w DBMS kilkudziesięciokilobajtowych stron. Strona taka może zawierać wiele obiektów. W miarę możliwości powinno się tak projektować strony, aby obiekty na jednej stronie miały podobną i skorelowaną temperaturę.

Jeśli na każdej stronie znajdowałyby się zarówno obiekty gorące jak i chłodne, niemożliwe byłoby uzyskanie wysokiej temperatury cache. Jeśli natomiast niektóre strony będą znacznie cieplejsze od innych, cache może zawierać te pierwsze i osiągnąć wyższą temperaturę. Na przykład w typowym drzewie indeksowym obiekty są relatywnie chłodne, natomiast wskaźniki są znacznie gorętsze. Tak więc trzymanie danych tylko na liściach pozwala na znacznie lepszą separację niż gdyby trzymać je na każdym węźle.

W miarę możliwości powinno się trzymać na stronie obiekty o skorelowanej temperaturze, np. strony pamięci wirtualnej procesora zawierają leżące po kolei bajty, które ze względu na lokalność przestrzenną mają prawdopodobnie skorelowane temperatury. Z tego też powodu używa się osobnych linii cache dla danych i dla kodu.

Przykłady cache

Cache procesora

Pamięć cache przyspiesza dostęp do relatywnie wolnej pamięci RAM. Charakteryzuje się bardzo krótkim czasem dostępu. Jest używana do przechowywania danych, które będą w niedługim czasie przetwarzane. Na współczesnych procesorach są 2 lub 3 poziomy pamięci cache: L1 (zintegrowana z procesorem), a także L2 i L3 (umieszczone w jednym chipie razem z procesorem, lub na płycie głównej).

Cache dysku twardego

Pamięć cache dysku twardego przyspiesza dostęp do bardzo wolnej pamięci masowej (w porównaniu do pamięci RAM do której dane są pobierane). Cache o wielkości od 128 KiB do 16 MiB jest zazwyczaj podzielony na dwie części: obszar podsystemu odpowiedzialnego za odczyt z wyprzedzeniem i buforowanie odczytu oraz mniejszy obszar opóźnionego zapisu. Ponieważ dysk z kontrolerem komunikuje się magistralą szybszą niż najszybsze budowane dyski twarde możliwość przechowania danych w buforze i wysłania do kontrolera bez wykonywania cyklu dostępu do nośnika wpływa pozytywnie na szybkość całego systemu.

Cache przeglądarki

Nazwa cache oznacza też miejsce na dysku twardym, w którym przeglądarka internetowa przechowuje odwiedzone uprzednio strony (lub części stron) WWW. Ma to na celu przyspieszenie przeglądania stron internetowych, gdyż nie ma potrzeby ściągania odwiedzonych już stron z Internetu.