Wynajmować czy kupować pamięć? Google zapożyczyło algorytm z wyciągu narciarskiego

Wyobraź sobie wyjazd na narty o nieznanej długości. Codziennie decydujesz: wypożyczyć sprzęt za drobną opłatę czy kupić go raz, drożej, ale na zawsze? Ten klasyczny dylemat matematyczny posłużył inżynierom Google do rozwiązania zupełnie innego problemu — kosztów pamięci w chmurze.

Dlaczego pamięć podręczna to kosztowny dylemat?

→ Czytaj też: Google wypuszcza tani model AI do cyberbezpieczeństwa. Konkurencja dla Mythos za ułamek ceny

Nowoczesne bazy danych trzymają często używane dane w pamięci RAM, by ominąć powolne operacje dyskowe. Problem w tym, że szybka pamięć jest droga. Jak podaje zespół Google Research, niektórzy dostawcy chmury liczą sobie nawet 3 dolary dziennie za zaledwie 1 GiB pamięci.

Dotąd cache traktowano jako zasób o stałym rozmiarze. Inżynier przydzielał konkretną ilość pamięci, a system usuwał dane według reguł takich jak LRU (least recently used), gdy zabrakło miejsca. To rodzi klasyczny problem „Złotowłosej”: za mały cache — wydajność leci na łeb, za duży — marnujesz tysiące dolarów na bezczynną pamięć.

Jak działa problem wynajmu nart w pamięci?

→ Czytaj też: X przyznaje: algorytm zmienił platformę w pole bitwy. Teraz ma to naprawić

W pracy zaprezentowanej na Conference on Innovative Data Systems Research (CIDR) badacze Todd Lipcon i Manish Purohit opisali podejście nazwane linear elastic caching. Zamiast traktować pamięć jako stały, z góry przydzielony zasób, ujmują ją jako usługę, której koszt rośnie liniowo wraz z ilością danych i czasem ich przechowywania.

Każdy fragment danych staje przed wyborem analogicznym do narciarza. Można „wynająć” miejsce — trzymać dane w RAM i płacić ciągły koszt za zajmowaną pamięć. Albo „kupić” pominięcie — usunąć dane, by zaoszczędzić, ryzykując karę w postaci opóźnienia i operacji dyskowej, gdy dane szybko znów będą potrzebne.

Kluczowy wkład teoretyczny dowodzi, że dwa czynniki — politykę usuwania i czas „wynajmu” — można optymalizować osobno. Algorytm wynajmu nart wyznacza czas życia strony (TTL). Jeśli strona nie zostanie odczytana przed wygaśnięciem TTL, jest automatycznie usuwana. A gdy cache fizycznie się zapełni, do gry wchodzi tradycyjna polityka LRU.

Co pokazały testy na bazie Spanner?

Teorię sprawdzono w boju. System wpięto do Spanner — globalnie rozproszonej bazy danych Google, która obsługuje miliardy zapytań na sekundę. Dlatego model przewidujący TTL musiał być wyjątkowo lekki: zastosowano płytkie drzewo decyzyjne, które tłumaczy się na kilka linijek kodu C++.

Model uwzględnia rozmiar danych, koszt pominięcia oraz typ operacji bazodanowej. Po kilku miesiącach działania na serwerach produkcyjnych wyniki wyglądały tak:

• Zużycie pamięci: spadek o 15,5 proc.
• Pominięcia cache: wzrost zaledwie o 5,5 proc.
• Całkowity koszt posiadania (TCO): spadek o około 5 proc.

Najistotniejsze, że algorytm jest „świadomy kosztów”. Niewielki wzrost liczby pominięć skupił się na danych tanich w pobraniu z dysku. Realny wpływ na koszty operacji wejścia-wyjścia wyniósł pomijalne 0,5 proc.

Czy to działa poza infrastrukturą Google?

By upewnić się, że efekt nie wynika ze specyfiki Google, zespół przetestował metodę na publicznie dostępnych śladach cache z branżowych benchmarków. Jako punkt odniesienia posłużył zoptymalizowany algorytm GDSF (greedy dual size frequency) — uogólnienie LRU dopuszczające strony różnej wielkości.

Elastyczne podejście konsekwentnie wypadało lepiej niż cache o stałym rozmiarze, w różnorodnych obciążeniach. Co ciekawe, im droższa staje się pamięć względem kosztu pominięcia, tym wyraźniejsze oszczędności. Przy porównywalnym rozmiarze elastyczne polityki notowały też niższy współczynnik pominięć.

Wniosek jest prosty, choć elegancki: produkcyjne obciążenia są w większości przewidywalne. Dostęp do danych w systemach takich jak Spanner układa się we wzorce, które można wykorzystać do lepszych decyzji o „wynajmie”. Klasyczny problem narciarza, znany teoretykom od dekad, właśnie pokazał, że potrafi oszczędzić realne dolary w centrach danych.