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

„W informatyce są tylko dwa poważne problemy: 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?

Na przykład rozważmy funkcję, getData()która pobiera dane z pliku. Buforuje go na podstawie czasu ostatniej modyfikacji pliku, który sprawdza przy każdym wywołaniu.
Następnie dodajesz drugą funkcję, transformData()która przekształca dane i zapisuje jej wynik w pamięci podręcznej do następnego wywołania funkcji. Nie ma wiedzy o pliku - jak dodać zależność, że jeśli plik zostanie zmieniony, ta pamięć podręczna stanie się nieważna?

Możesz zadzwonić za getData()każdym razem, gdy transformData()zostanie wywołany i porównać go z wartością użytą do zbudowania pamięci podręcznej, ale może to być bardzo kosztowne.

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

Jeśli masz idempotentną funkcję od a, bdo cgdzie, jeśli ai bsą takie same, to cjest to samo, ale koszt sprawdzenia bjest wysoki, to albo:

1. zaakceptuj, że czasami korzystasz z nieaktualnych informacji i nie zawsze sprawdzaj b
2. postaraj się, aby sprawdzanie było bjak najszybsze

Nie możesz mieć ciasta i go zjeść ...

Jeśli możesz nałożyć dodatkową pamięć podręczną w oparciu o agórną część, to nie wpłynie to na początkowy problem. Jeśli wybierzesz 1, masz swobodę, jaką sobie dałeś, i możesz w ten sposób buforować więcej, ale musisz pamiętać, aby wziąć pod uwagę ważność zbuforowanej wartości b. Jeśli wybrałeś 2, nadal musisz sprawdzać za bkażdym razem, ale możesz wrócić do pamięci podręcznej, ajeśli się bsprawdzisz.

Jeśli tworzysz warstwy pamięci podręcznej, musisz rozważyć, czy nie naruszyłeś „reguł” systemu w wyniku połączonego zachowania.

Jeśli wiesz, że azawsze jest ważne, jeśli btak, możesz zorganizować pamięć podręczną w ten sposób (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 nawarstwianie (powiedzmy x) jest trywialne, tak długo, jak na każdym etapie ważność nowo dodanego wejścia odpowiada a: brelacje dla x: bi x: a.

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

jeśli (endCache [a] wygasł lub nie istnieje)

Problem z unieważnieniem pamięci podręcznej polega na tym, że rzeczy zmieniają się bez naszej wiedzy. Dlatego w niektórych przypadkach rozwiązanie jest możliwe, jeśli jest jakaś inna rzecz, która o tym wie i może nas o tym powiadomić. W podanym przykładzie funkcja getData mogłaby podłączyć się do systemu plików, który wie o wszystkich zmianach w plikach, niezależnie od tego, jaki proces zmienia plik, a ten komponent z kolei może powiadomić komponent, który przekształca dane.

Nie sądzę, aby istniała jakakolwiek ogólna magiczna poprawka, która rozwiązałaby problem. Jednak w wielu praktycznych przypadkach mogą istnieć okazje do zmiany podejścia opartego na „odpytywaniu” w podejście oparte na „przerwaniu”, co może sprawić, że problem po prostu zniknie.

Jeśli zamierzasz uzyskać getData () za każdym razem, gdy wykonujesz transformację, wyeliminujesz całą korzyść z pamięci podręcznej.

Na przykład wydaje się, że rozwiązaniem byłoby, gdy generujesz przekształcone dane, zapisując również nazwę pliku i czas ostatniej modyfikacji pliku, z którego dane zostały wygenerowane (już zapisałeś to w dowolnej strukturze danych zwróconej przez getData ( ), więc po prostu kopiujesz ten rekord do struktury danych zwróconej przez transformData ()), a następnie, gdy ponownie wywołasz transformData (), sprawdź czas ostatniej modyfikacji pliku.

IMHO, funkcjonalne programowanie reaktywne (FRP) jest w pewnym sensie ogólnym sposobem rozwiązania problemu unieważnienia pamięci podręcznej.

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

FRP jest wyjaśnione bardziej szczegółowo w tym wykładzie „Essence of FRP” oraz w tej odpowiedzi SO .

W rozmowie z Cells stanowią buforowane Object / podmiot i Celljest odświeżany jeśli jeden jest to zależność jest odświeżany.

FRP ukrywa kod hydrauliczny powiązany z wykresem zależności i zapewnia, że ​​nie ma nieaktualnych plików Cell.

Innym sposobem (innym niż FRP), który przychodzi mi do głowy, jest zawijanie obliczonej wartości (typu b) do pewnego rodzaju pisarza Monad, w Writer (Set (uuid)) bktórym Set (uuid)(notacja Haskell) zawiera wszystkie identyfikatory zmiennych wartości, od których bzależy obliczona wartość . Tak więc uuidjest to jakiś unikalny identyfikator, który identyfikuje zmienną wartość / zmienną (powiedzmy wiersz w bazie danych), od której bzależy obliczenie .

Połącz ten pomysł z kombinatorami, które działają na tego rodzaju pisarzu Monad, a to może prowadzić do pewnego rodzaju ogólnego rozwiązania do unieważniania pamięci podręcznej, jeśli użyjesz tych kombinatorów tylko do obliczenia nowego b. Takie kombinatory (powiedzmy specjalna wersja filter) przyjmują monady i (uuid, a)-s Writer'a jako dane wejściowe, gdzie asą zmiennymi danymi / zmiennymi, identyfikowanymi przez uuid.

Tak więc za każdym razem, gdy zmieniasz "oryginalne" dane (uuid, a)(powiedzmy znormalizowane dane w bazie danych, z której bzostała obliczona), od której bzależy obliczona wartość typu , możesz unieważnić pamięć podręczną, która zawiera, bjeśli zmienisz jakąkolwiek wartość, aod której bzależy obliczona wartość , ponieważ na podstawie Set (uuid)Monady Writer możesz powiedzieć, kiedy to się stanie.

Więc za każdym razem, gdy mutujesz coś z danym uuid, transmitujesz tę mutację do wszystkich pamięci podręcznych i unieważniają one wartości, bktóre zależą od wartości mutowalnej identyfikowanej za pomocą said, uuidponieważ monada Writer, w której bjest zapakowana, może stwierdzić, czy bzależy to od said, uuidczy nie.

Oczywiście opłaca się to tylko wtedy, gdy czytasz znacznie częściej niż piszesz.

Trzecim, praktycznym podejściem jest użycie zmaterializowanych widoków w bazach danych i wykorzystanie ich jako pamięci podręcznych. AFAIK mają również na celu rozwiązanie problemu unieważnienia. To oczywiście ogranicza operacje, które łączą zmienne dane z danymi pochodnymi.

Pracuję teraz nad podejściem opartym na PostSharp i funkcjach zapamiętywania . Przeszedłem przez 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 wygaśnięcia. Każda zaznaczona w ten sposób funkcja jest zapamiętywana, a wynik zapisywany w pamięci podręcznej wraz z hashem wywołania funkcji i parametrami używanymi jako klucz. Używam Velocity dla backendu, który obsługuje dystrybucję danych z pamięci podręcznej.

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

Nie, ponieważ wszystkie dane są inne. Niektóre dane mogą być „nieaktualne” po minucie, inne po godzinie, a inne mogą działać przez kilka dni lub miesięcy.

Jeśli chodzi o Twój konkretny przykład, najprostszym rozwiązaniem jest skorzystanie z funkcji sprawdzania pamięci podręcznej plików, którą wywołujesz zarówno z, jak getDatai transformData.

Nie ma ogólnego rozwiązania, ale:

• Twoja pamięć podręczna może działać jako proxy (pull). Załóżmy, że twoja pamięć podręczna zna sygnaturę czasową ostatniej zmiany pochodzenia, kiedy ktoś dzwoni getData(), pamięć podręczna pyta o pochodzenie o znacznik czasu ostatniej zmiany, jeśli jest taka sama, zwraca pamięć podręczną, w przeciwnym razie aktualizuje zawartość za pomocą źródłowej i zwraca jej zawartość. (Odmiana polega na tym, że klient bezpośrednio przesyła znacznik czasu w żądaniu, źródło zwróci treść tylko wtedy, gdy jego znacznik czasu jest inny).

• Nadal można korzystać z procesu powiadamiania (push), pamięć podręczna obserwuje źródło, jeśli źródło się zmieni, wysyła powiadomienie do pamięci podręcznej, które jest następnie oznaczane jako „brudne”. Jeśli ktoś getData()wywoła, że ​​pamięć podręczna zostanie najpierw zaktualizowana do źródła, usuń flagę „dirty”; następnie zwróć jego zawartość.

Ogólnie rzecz biorąc, wybór zależy od:

• Częstotliwość: wiele wywołań getData()wolałoby push, aby uniknąć zalania źródła przez funkcję getTimestamp
• Twój dostęp do źródła: czy jesteś właścicielem modelu źródłowego? Jeśli nie, prawdopodobnie nie możesz dodać żadnego procesu powiadamiania.

Uwaga: Ponieważ używanie znacznika czasu jest tradycyjnym sposobem działania serwerów proxy http, innym podejściem jest udostępnianie skrótu przechowywanej zawartości. Jedyny sposób, w jaki wiem, że dwie jednostki mogą się zaktualizować razem, to albo zadzwonię do ciebie (pociągnij) albo zadzwonisz do mnie… (pchnij) to wszystko.

pamięć podręczna jest trudna, ponieważ musisz wziąć pod uwagę: 1) pamięć podręczna zawiera wiele węzłów, potrzebujesz konsensusu dla nich 2) czas unieważnienia 3) stan wyścigu, gdy nastąpi wiele operacji pobierania / ustawiania

to dobra lektura: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

Być może algorytmy nieświadome pamięci podręcznej byłyby najbardziej ogólne (lub przynajmniej mniej zależne od konfiguracji sprzętowej), ponieważ najpierw użyją najszybszej pamięci podręcznej i przejdą dalej. Oto wykład MIT na ten temat: Cache Oblivious Algorithms