CDN Buforowanie: LRU vs LFU w Warunkach Rzeczywistego Ruchu o Rozkładzie Zipfa

Dlaczego w ogóle istnieje CDN?

Światło w włóknie światłowodowym porusza się z prędkością około dwóch trzecich c, co stawia twardy próg dla opóźnień: podróż z Nowego Jorku do Sydney i z powrotem zajmuje około 160 milisekund, niezależnie od tego, jak dobry jest serwer. Sieć Dostarczania Treści (CDN) nie rozwiązuje tego poprzez przyspieszenie serwera źródłowego, ale poprzez uczynienie go zbędnym dla większości żądań – umieszcza kache pamięci podręczne w setkach lokalizacji fizycznych, blisko użytkowników, i kieruje każde żądanie do najbliższej, wykorzystując DNS lub Anycast. Jeśli zawartość znajduje się już w tej pamięci podręcznej CDN, serwer źródłowy nigdy nie jest nawet kontaktowany.

Współczynnik trafień jest całym argumentem ekonomicznym

Współczynnik trafień – czyli ułamek żądań, które węzeł brzegowy może obsłużyć z własnego pamięci podręcznej – to jedyne kryterium decydujące o tym, czy sieć CDN jest opłacalna. Porażka oznacza, że węzeł brzegowy musi pobrać dane z źródła (lub węzła nadrzędnego), ponieść pełne opóźnienie w obie strony i następnie zdecydować, czy zapisać wynik na przyszłość. Każda pamięć podręczna ma ograniczoną pojemność, więc gdy jest pełna, a pojawia się nowy obiekt, musi zostać usunięty – a który obiekt zostanie usunięty to cała sztuka.

LRU: Recency jako jedyny sygnał

Strategia Least Recently Used (LRU) polega na usuwaniu obiektów w oparciu o czas ich ostatniego dostępu, a konkretnie poprzez usunięcie tego, który był nieużywany najdłużej. Zaimplementowana jako podwójnie połączona lista z dodatkiem mapy hash, zarówno operacja wyszukiwania jak i przesunięcie elementu na początek listy w przypadku trafienia (hit) są O(1):

przy żądaniu(klucz): jeśli klucz znajduje się w pamięci podręcznej: przesuń węzeł[klucz] na początek listy // O(1) — recency zaktualizowana zwróć węzeł[klucz].wartość // TRAFIENIE else: jeśli pamięć podręna jest pełna: usuń węzeł z końca // najzimniejszy element, O(1) pobierz dane z źródła, wstaw węzeł[klucz] na początek // BRAK TRAFIENIA LRU jest tania, prosta i natychmiast reaguje na zmieniającą się popularność — wczorajszy wirujący film naturalnie wypada, a dzisiejszy przejmuje jego miejsce. Jej słabością jest traktowanie pojedynczego dostępu dokładnie tak samo jak setka: duży obiekt zażądany raz (przeglądarka indeksująca katalog, ktoś przeglądający wideo) może usunąć z pamięci podręcznej naprawdę popularny content wyłącznie dlatego, że został dotknię najnowszy – błąd, który zwykle nazywa się zanieczyszczeniem pamięci podręcznej lub niezdolnością do odporności na skanowanie.

on request(key):
  if key in cache:
    move node[key] to front of list        // O(1) — recency updated
    return node[key].value                 // HIT
  else:
    if cache is full: evict node at back    // the coldest item, O(1)
    fetch from origin, insert node[key] at front   // MISS

LFU: częstotliwość jako sygnał zamiast

Najrzadziej Używany algorytm usuwania utrzymuje licznik trafień dla każdego obiektu i usuwa ten z najniższą liczbą, zazwyczaj implementowany za pomocą mapy hash plus kopce minimalnej lub listy koszyków o kluczu częstotliwości dla operacji O(1) lub O(log n). Odporny jest na problem jednorazowego skanowania, który szkodzi algorytmowi LRU – popularny obiekt gromadzi liczbę, której pojedynczy skan nie może odzwierciedlić.

Jednak LFU ma odwrotność: zator zapomnianych danych. Obiekt, który był bardzo popularny w zeszłym tygodniu, ale jest teraz nieistotny, może utrzymać wysoką liczbę i odmówić usunięcia, permanentnie zajmując przestrzeń potrzebną nowo popularnemu zawartości. Systemy produkcyjne prawie zawsze dodają zanik – okresowe dzielenie przez 2 wszystkich liczników lub ważenie w oparciu o niedawno (oraz częstotliwość) – jak w rodzinach LRU-K i ARC, oraz w własnym przybliżonym LFU Redis z licznikiem logarytmicznym i opóźnionym przez czas (wszystkie te próby połączenia tych dwóch sygnałów zamiast wyboru jednego).

Dlaczego rozkład Zippfa, a nie równomierny, zmienia wszystko

Rzeczywisty ruch żądań do CDN nie jest równomiernie rozłożony na obiekty — podąża za rozkładem Zippfa: jeśli posortujesz obiekty według popularności, częstotliwość żądań dla k-tego obiektu uszeregowanego jest proporcjonalna do 1/k^s, gdzie s jest parametrem skośności (s = 1 to klasyczny praw Zippfa; zmierzony ruch internetowy i wideo zwykle mieści się w okolicach s = 0.6-0.9):

częstotliwość(stopień k) ∝ 1 / k^s s = 1,0, górnych 1% obiektów → odpowiada około 60-70% wszystkich żądań s = 1,0, górnych 10% obiektów → odpowiada ponad 90% wszystkich żądań To jest główny powód, dla którego buforowanie działa na skalę internetu: ponieważ niewielka grupa bardzo popularnych obiektów odpowiada za zdecydowaną większość żądań, a bufor zawierający nawet 1-5% całkowitej liczby obiektów może osiągnąć współczynnik trafień powyżej 80%, pod warunkiem, że polityka wygaszania utrzymuje tę grupę w pamięci. W przypadku ruchu rozłożonego zgodnie z prawem Zippfa LFU zwykle działa lepiej niż LRU pod względem pierwotnego współczynnika trafień, ponieważ bezpośrednio śledzi ilość (częstotliwość), którą generuje rozkład Zippfa; LRU nadal może sobie dobrze radzić, ponieważ popularne obiekty również mają tendencję do częstego żądania w niedawno, ale jest bardziej narażony na zanieczyszczenie spowodowane przez zimne skany w długim ogonie.

frequency(rank k)  ∝  1 / k^s

s = 1.0, top 1% of objects  →  carries roughly 60-70% of all requests
s = 1.0, top 10% of objects →  carries roughly 90%+ of all requests

Czas Żyzności i Wymazanie Cache'u: Inny Element Problem

Współczynnik trafień sam w sobie nie oddaje całej historii – obiekt przechowywany w cache'u ma również Czas Żyzności, po którym uważa się go za przestarzały i musi zostać zweryfikowany z źródłem (poprzez żądanie warunkowe używające nagłówka ETag lub Last-Modified), nawet jeśli nigdy nie został usunięty z cache'u. Ustawienie Czasu Żyzności zbyt długo powoduje, że użytkownicy widzą przestarzałe treści po zmianach w źródle; ustawienie go zbyt krótko powoduje spadek współczynnika trafień, ponieważ obiekty wygasają przed ponownym wykorzystaniem. Słynny cyt Phil Karltona – „w informatyce istnieją tylko dwie rzeczy, które są trudne: wymazanie cache'u i nazewnictwo rzeczy” – odnosi się bezpośrednio do tego kompromisu, a produkcyjne CDN-y angażują ogromne nakłady pracy inżynierskiej na szybkie API usuwania i strategie stale-while-revalidate, ponieważ błędne ustawienie Czasu Żyzności w dowolnym kierunku jest kosztowne.

Wielowarstwowe buforowanie: krawędź, regionalne i serwer główny (origin shield)

Jednolewarglowe buforowanie, polegające na jednoczesnym pobieraniu wszystkich brakujących danych bezpośrednio do serwera głównego (tzw. problem 'gromu'), jest powodem, dla którego duże CDN wstawiają warstwę pośrednią – bufery regionalne lub serwer główny – pomiędzy setki węzłów krawędziowych a serwerem głównym. Błąd w węźle krawędziowym sprawdza najpierw bufor główny; błąd tylko w buforze głównym dociera do serwera głównego. To przekształca co najmniej setki jednoczesnych żądań do serwera głównego na maksymalnie jedno na unikalny obiekt w regionie, a jest to ta sama hierarchiczna zasada jak bufor L1/L2/L3 w procesorze, tylko w skali internetu i z opóźnieniami sieciowymi zastępującymi opóźnienia pamięci.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz CDN & Cache Hit Rate i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.