Unieważnienie pamięci podręcznej - czy istnieje rozwiązanie ogólne?

Question

"Istnieją tylko dwa trudne problemy w informatyce: unieważnianie pamięci podręcznej i nazywanie rzeczy."

Phil Karlton

Czy istnieje ogólne rozwiązanie lub metoda unieważniania pamięci podręcznej; wiedzieć, kiedy wpis jest nieaktualny, więc masz gwarancję, że zawsze otrzymasz świeże dane?

Weźmy na przykład funkcję getData(), która pobiera dane z pliku. Buforuje go na podstawie czasu ostatniej modyfikacji pliku, który sprawdza za każdym razem, gdy jest wywoływany.
Następnie dodajemy drugą funkcję transformData(), która przekształca dane i zapisuje w pamięci podręcznej wynik, aby następnym razem wywołać funkcję. Nie ma wiedzy o pliku - jak dodać zależność, że jeśli plik zostanie zmieniony, pamięć podręczna zostanie unieważniona?

Można zadzwonić pod numer getData() za każdym razem, gdy wywoływana jest nazwa transformData() i porównać ją z wartością użytą do zbudowania pamięci podręcznej, ale może to okazać się bardzo kosztowne.

Answer 1

To, o czym mówisz, to łańcuch zależności zależny od życia, że ​​jedna rzecz jest zależna od innej, którą można modyfikować poza jej kontrolą.

Jeśli masz funkcję idempotent z a, b do c gdzie, jeśli a i b są takie same wtedy c jest taka sama, ale koszt sprawdzenia b jest wysoka to albo:

1. przyjąć, że czasami używasz nieaktualnych informacji i nie zawsze sprawdzasz, czy Twój poziom jest najlepszy, aby sprawdzenie b było tak szybkie, jak to możliwe:

Nie można mieć ciastko i je zjeść ...

Jeśli można warstwy dodatkowej pamięci podręcznej w oparciu o a na szczycie wtedy ma to wpływ na początkowe problemy nie jeden bit. Jeśli wybrałeś 1, masz dowolną swobodę, którą sam sobie dałeś i możesz w ten sposób buforować więcej, ale musisz pamiętać, aby rozważyć ważność buforowanej wartości b. Jeśli wybierzesz 2, musisz zawsze sprawdzać za każdym razem, b, ale może wrócić do pamięci podręcznej dla a, jeśli wymelduje się b.

W przypadku warstw pamięci podręcznej należy wziąć pod uwagę, czy w wyniku połączonego zachowania naruszyliśmy "reguły" systemu.

Jeśli wiesz, że a zawsze ma ważność jeśli b ma wtedy można zorganizować pamięć podręczną jak SO (Pseudokod):

private map<b,map<a,c>> cache // 
private func realFunction // (a,b) -> c 

get(a, b) 
{ 
    c result; 
    map<a,c> endCache; 
    if (cache[b] expired or not present) 
    { 
     remove all b -> * entries in cache; 
     endCache = new map<a,c>();  
     add to cache b -> endCache; 
    } 
    else 
    { 
     endCache = cache[b];  
    } 
    if (endCache[a] not present)  // important line 
    { 
     result = realFunction(a,b); 
     endCache[a] = result; 
    } 
    else 
    { 
     result = endCache[a]; 
    } 
    return result; 
} 

Oczywiście kolejne warstwowanie (słownie x) jest trywialne, tak długo, jak na każdym etapie ważność nowo dodanych danych wejściowych jest zgodna z relacją a: : b i .

Jednak jest całkiem możliwe, że można uzyskać trzy wejścia, których ważność była całkowicie niezależna (lub cykliczna), więc nie byłoby możliwe nawarstwianie. Oznaczałoby to linia oznaczona // ważne musiałby zmienić

if (endCache [a] wygasły lub nie występuje)

Answer 2

Być może algorytmy nieprzestrzegające pamięci podręcznej są najbardziej ogólne (lub przynajmniej mniej zależne od konfiguracji sprzętu), ponieważ najpierw będą używać najszybszej pamięci podręcznej i będą z niej korzystać. Oto wykład MIT na ten temat: Cache Oblivious Algorithms

Answer 3

Pracuję nad podejściem teraz na podstawie PostSharp i memoizing functions. Przebiegłem go obok mojego mentora i zgadza się, że jest to dobra implementacja buforowania w sposób niezależny od treści.

Każda funkcja może być oznaczona atrybutem określającym jej okres ważności. Każda funkcja oznaczona w ten sposób jest pamiętana, a wynik jest zapisywany w pamięci podręcznej, z hashiem wywołania funkcji i parametrami używanymi jako klucz. Używam Velocity dla zaplecza, który obsługuje dystrybucję danych z pamięci podręcznej.

Answer 4

Czy istnieje ogólne rozwiązanie lub metoda tworzenia pamięci podręcznej, aby wiedzieć, kiedy wpis jest nieaktualny, więc masz gwarancję, że zawsze otrzymasz świeże dane?

Nie, ponieważ wszystkie dane są różne. Niektóre dane mogą być "nieaktualne" po minucie, niektóre po godzinie, a niektóre mogą być dobre przez kilka dni lub miesięcy.

Jeśli chodzi o konkretny przykład, najprostszym rozwiązaniem jest posiadanie funkcji "sprawdzania pamięci podręcznej" dla plików, które wywoływane są zarówno z getData jak i transformData.

Answer 5

Jeśli zamierzasz pobraćData() za każdym razem, gdy dokonasz transformacji, wyeliminujesz całą zaletę pamięci podręcznej.

Dla przykładu, wydaje się, że rozwiązaniem byłoby generowanie przekształconych danych, przechowywanie nazwy pliku i czasu ostatniej modyfikacji pliku, z którego dane zostały wygenerowane (już to zapisane w dowolnej strukturze danych zwracane przez getData(), więc wystarczy skopiować ten rekord do struktury danych zwróconej przez transformData()), a następnie ponownie wywołać metodę transformData(), sprawdzić ostatni czas modyfikacji pliku.

Answer 6

Problem w pamięci podręcznej unieważnienia jest to, że zmiany stuff bez nas wiedząc o tym. W niektórych przypadkach rozwiązanie jest możliwe, jeśli istnieje inna rzecz, która o tym wie i może nas powiadomić. W podanym przykładzie funkcja getData może podłączyć się do systemu plików, który wie o wszystkich zmianach w plikach, niezależnie od tego, który proces zmienia plik, a ten komponent z kolei może powiadomić komponent, który transformuje dane.

Nie sądzę, że istnieje jakaś ogólna magiczna poprawka, która sprawi, że problem zniknie. Jednak w wielu praktycznych przypadkach mogą pojawić się możliwości przekształcenia podejścia opartego na "głosowaniu" na podejście oparte na "zakłócaniu", które może sprawić, że problem po prostu zniknie.

Answer 7

Nie ma jednak rozwiązanie ogólne:

• Ty cache może działać jako serwer proxy (ciągnąć).Załóżmy, że pamięć podręczna rozpoznaje sygnaturę czasową ostatniej zmiany pochodzenia, gdy ktoś zadzwoni pod numer getData(), pamięć podręczna zapyta o pochodzenie datownika ostatniej zmiany, jeśli to samo, zwróci pamięć podręczną, w przeciwnym razie zaktualizuje zawartość źródłową i zwróci treść. (Odmianą jest klient, który bezpośrednio wysyła znacznik czasu na żądanie, źródło zwróci treść tylko wtedy, gdy jego znacznik czasu będzie inny).

• Nadal można korzystać z procesu powiadomienia (push), pamięć podręczna obserwować źródło, jeśli źródło ulegnie zmianie, wysyła powiadomienie do pamięci podręcznej, która jest oznaczana jako "brudna". Jeśli ktoś zadzwoni pod numer getData(), pamięć podręczna zostanie najpierw zaktualizowana do źródła, usuń "brudną" flagę; następnie zwróć jego zawartość.

wybór generalnie zależy od:

• Częstotliwość: wielu wzywa getData() woleliby push tak aby uniknąć źródło zostać zalane przez funkcję getTimestamp
• Twój dostęp do źródło: Czy jesteś właścicielem modelu źródłowego? Jeśli nie, najprawdopodobniej nie możesz dodać żadnego procesu powiadamiania.

Uwaga: Ponieważ używanie znacznika czasu jest tradycyjnym sposobem działania serwerów proxy http, innym sposobem jest udostępnianie skrótu przechowywanej zawartości. Jedyny sposób, w jaki wiem, że dwie jednostki mogą być aktualizowane razem, to albo ja nazywam (pull), albo nazywasz mnie ... (push) to wszystko.

Answer 8

IMHO, Functional Reactive Programming (FRP) jest w pewnym sensie ogólnym sposobem rozwiązywania problemów z unieważnieniem pamięci podręcznej.

Oto dlaczego: nieaktualne dane w terminologii FRP są nazywane glitch. Jednym z celów FRP jest zagwarantowanie braku usterki.

FRP jest wyjaśnione bardziej szczegółowo w tym 'Essence of FRP' talk iw tym SO answer.

s oznaczają buforowany obiekt/obiekt, a Cell jest odświeżany, jeśli jedna z jego zależności jest odświeżana.

FRP ukrywa kod hydrauliczny powiązany z wykresem zależności i upewnia się, że nie ma nieaktualnych wersji Cell.